Prozeß-Scheduling

• Gerechtigkeit: Jeder Prozeß erhält einen "gerechten" CPU-Anteil
• Effizienz: Die CPU sollte immer zu 100% ausgelastet sein
• Antwortzeit: Minimale Antwortzeit für interaktive Benutzer
• Verweilzeit: Angemessen kurze Verweilzeit für Batch-Aufträge
• Durchsatz: Möglichst viele Aufträge/Zeitraum abarbeiten
• Terminerfüllung: Bereitstellung bestimmter Ergebnisse zu festgelegten Zeitpunkten

Bei Multitasking-Betriebssystemen werden zwei Grundsysteme für das Scheduling unterschieden:

• kooperatives Multitasking (non preemptive)
  Der aktive Prozeß gibt von sich aus die CPU zu einem geeigneten Zeitpunkt frei. Es ist nur ein geringer Verwaltungsaufwand nötig. Es besteht jedoch die Gefahr, daß ein "unkooperativer" oder fehlerhafter Prozeß alle anderen Prozesse blockiert.

• verdrängendes Multitasking (preemptive) Der Scheduler kann einem Prozeß die CPU entziehen (z. B. ausgelöst durch einen Timer-Interrupt). Dadurch kann die Bearbeitung dringlicherer Aufgaben jederzeit begonnen werden (z. B. bei Echtzeit-BS). Ein fehlerhafter Prozeß kann das System nicht blockieren.
  Anstoß für den Prozeßwechsel durch Verdrängung:
  • Zeitgesteuerte Strategien
    Jeder Prozeß erhält die CPU für eine bestimmte Zeitspanne (Zeitscheibe). Danach wird die CPU dem nächsten Prozeß zugeteilt (Zeitscheibenverfahren, round robin).
  • Ereignisgesteuerte Strategien
    Ein Prozeßwechsel findet statt, wenn ein Ereignis (z. B. ein Hardwareinterrupt) einen anderen Prozeß benötigt. Hier werden allgemein den einzelnen Prozessen Prioritäten zugeordnet, die sich dynamisch ändern. Ein bestimmtes Ereignis verleiht "seinem" Prozeß eine höhere Priorität.

Scheduling-Strategien

Bei kooperativem Multitasking oder ereignisgesteuerten Schedulern wird die Zuteilungsstrategie über Prioritäten gesteuert, wobei man beim kooperativen System von relativem Vorrang spricht (der erst nach Freigabe der CPU durch den aktiven Prozeß wirksam wird) und beim ereignisgesteuerten System vom absoluten Vorrang (der sofort zum Prozeßwechsel führt).
Die Zeitscheibensteuerung kann als Sonderfall der Ereignissteuerung betrachtet werden, das Ereignis ist in diesem Fall der Ablauf der zugeteilten Zeitscheibe.

Einige Strategien, die in der Praxis verwendet werden, sind:

• Wer zuerst kommt, wird zuerst bedient (first come, first served):
  Verteilung der Prioritäten nach Ankunftszeit, ohne Vorrechte. Kommen zwei Prozesse genau gleichzeitig, wird eine zufällige Auswahl getroffen. Gute Systemauslastung, aber schlechtes Antwortzeitverhalten (lang laufende Prozesse behindern Kurzläufer). Einfach zu implementieren.
• Zeitscheibenverfahren (round robin):
  Jeder Prozeß erhält eine feste Zeitspanne (time slice) zugeordnet. Nach Ablauf dieser Zeitspanne wird er verdrängt und der nächste Prozeß erhält die CPU --> zyklische Zuteilung. Alle Prozesse haben immer die gleiche Priorität. Die Zeitspanne kann konstant sein oder abhängig von der Prozessorbelastung variieren. Kurze Antwortzeiten bei kleinen Zeitscheiben, aber dann höhere Verluste durch die häufigen Prozeßwechsel.
• Prioritätssteuerung:
  Jedem bereiten Prozeß wird eine Priorität zugeordnet. Vergabe der CPU in absteigender Priorität. Ein Prozeß niedrigerer Priorität kann die CPU erst erhalten, wenn alle Prozesse höherer Priorität abgearbeitet sind. Ein bereit werdender Prozeß höherer Priorität verdrängt einen aktiven Prozeß niedrigerer Priorität. Alle Prozesse gleicher Priorität werden i.a. in jeweils einer eigenen Warteschlange geführt Realisierung mehrerer unterschiedlicher Verfahren, z. Teil gemischt mit anderen Strategien , z. B.
  • Reine Prioritätssteuerung: Prozesse gleicher Priorität werden nach der Eingangsreihenfolge abgearbeitet (z. B. in Echtzeit-BS)
  • Prioritätsgesteuerung mit unterlagertem Zeitscheibenverfahren: Prozesse gleicher Priorität werden nach dem Zeitscheibenverfahren abgearbeitet
  • Dynamische Prioritätsvergabe: Die Priorität auf die CPU wartender Prozesse wird allmählich erhöht
  • Mehrstufiges Herabsetzen (multilevel feedback): Festlegung einer maximalen Rechenzeit für jede Prioritätsstufe. Hat ein Prozeß die max. Rechenzeit seiner Priorität verbraucht, bekommt er die nächstniedrigere Priorität, bis er die niedrigste Stufe erreicht hat.
• Es gibt noch zahlreiche weitere Scheduling-Strategien.

In Dialogsystemen wird normalerweise Round Robin verwendet, um den Benutzern akzeptable Antwortzeiten zu bieten. Bei Batchbetrieb und gemischten Systemen kommen oft Kombinationen der o. g. Strategien vor - z. B. getrenntes Scheduling für Dialog- und Batchbetrieb.

Zurück

Inhaltsverzeichnis

Nächste

Diplomarbeiten zum Runterladen: