Prozess Scheduling

In einem Betriebssystem werden laufend Programme gestartet und beendet. Ein Programm und damit ein Prozess existiert also nicht ewig. Die Verwaltung wird dabei nicht von den Prozessen selbst durchgeführt. Diese Aufgabe übernimmt eine besondere Instanz des Betriebssystems, der Scheduler.
Definition: Unter Scheduling versteht man die Verteilung und Zuweisung von begrenzten Ressourcen an konkurrierende Prozesse (konkurrierende Prozesse sind Prozesse die Systemweit existieren). Wenn zum Beispiel 2 Prozesse zur gleichen Zeit rechenbereit sein sollen entscheidet der Scheduler welcher Prozess zuerst an die Reihe kommt.

Man unterscheidet hier zwischen Langzeitscheduling (Das Planen der Jobausführung) und Kurzzeitscheduling (das Planen der aktuellen Prozessorzuteilung). Genauer gesagt wird beim Langzeitscheduling entschieden welcher Prozess vom Sekundärspeicher in den Hauptspeicher geladen wird. Beim Kurzzeitscheduling wird entschieden welcher Prozess als nächstes vom bereit-Zustand in den aktiv-Zustand gelangt.
Aus diesem Grund werden diese Arten auch Jobscheduling bzw. Prozessorscheduling genannt. Weiterhin unterscheidet man das Planen der Zuteilung (Scheduling) und die tatsächliche Zuteilung (Dispatching).

Im Folgenden betrachten wir einige der gängigsten Schedulingstrategieen, die alle versuchen folgende Ziele zu erreichen:

• Fairness: Prozesse sollen fair behandelt werden. D.h. jeder Prozess soll nach einer gewissen Zeit seine Betriebsmittel erhalten.
• Auslastung der CPU: möglichst hohe Auslastung der CPU.
• Durchsatz maximieren: Die Anzahl der zu bearbeiteten Jobs pro Zeitintervall sollte maximiert werden.
• Minimierung der Ausführungszeit: Die Ausführungszeit ist die Zeit des gesamten Ablaufes. Sie beginnt von der Ankunft des Prozesses bis hin zur endgültigen Ausgabe. Diese Zeit sollte minimiert werden.
• Antwortzeit minimieren: Die Zeitspanne zwischen Eingabe der Daten und Ausgabe des Ergebnisses sollte minimiert werden. Der Nutzer wünscht schnelle Reaktion des Systems auf seine Eingaben.

Hier ist jedoch anzumerken, dass nicht alle Ziele erreicht werden können, da einige durchaus widersprüchlich sind. Liegt die Priorität zum Beispiel auf kurzen Prozessen, so ist es sinnvoll die Antwortzeit und den Durchsatz zu maximieren und ggf. Fairness und Ausführungszeit langer Prozesse zu vernachlässigen.

Prozesse werden vom Betriebssystem nicht vorzeitig unterbrochen. Die Prozesse laufen so lange bis sie den Aktivzustand freiwillig verlassen und auf das nächste Ereignis warten oder sich selbst beenden.

In allen Schedulingvarianten wird auf folgendes Beispiel eingegangen:
Gegeben sind 4 Prozesse mit Ihren Bedienzeiten (Zeit, in der sich ein Prozess im Besitz des Prozessors befindet), Startprioritäten und Startquanten

Geht nach einer sehr einfachen Strategie vor. Prozesse werden in der Reihenfolge des Eintreffens in die Warteschlange einsortiert. Somit kommen alle Prozesse an die Reihe. Die durchschnittliche Ausführungszeit ist jedoch nicht optimal.

1. Wie ist die Wartezeit der einzelnen Prozesse?
   P1 = 0
   P2 = 17
   P3 = 20
   P4 = 25
2. Wie ist die durchschnittliche Wartezeit?
   ((0+17+20+25)/4) = 15,5
3. Nach welcher Zeit hat der letzte Prozess seine Tätigkeit beendet?
   17+3+5+7 = 32

Bei diesem Verfahren wird der Job mit der kürzesten Bedienzeit zuerst in die Warteschlange einsortiert. Dies führt zu einer besseren durchschnittlichen Ausführungszeit wie die des FCFS Verfahrens. Das Problem liegt jedoch darin, dass Prozesse mit hohen Bedienzeiten „verhungern“ können.

1. Wie ist die Wartezeit der einzelnen Prozesse?
   P1 = 15
   P2 = 0
   P3 = 3
   P4 = 8


2. Wie ist die durchschnittliche Wartezeit?
   ((15+0+3+8)/4) = 6,5
3. Nach welcher Zeit hat der letzte Prozess seine Tätigkeit beendet?
   17+3+5+7 = 32

Das Highest Response Ratio Next-Verfahren weist dem Prozessor immer den Prozess zu mit dem größten Verhältnis (Antwortzeit / Bedienzeit). Dies lässt sich wie folgt berechnen.
R = (Wartezeit + Bedienzeit) / Bedienzeit

Bei dieser Variante kann ein Job vorzeitig vom Betriebssystem unterbrochen werden. Außerdem können Betriebsmittel entzogen werden. Die wichtigste Aufgabe aller preemtive Verfahren besteht darin, die Arbeitszeit der CPU in Zeitscheiben aufzuteilen.

Round Robin (Rundlauf-Verfahren) ist das am häufigsten verwendete Verfahren. Es funktioniert ähnlich wie das FCFS verfahren, ist also eine Kombination aus FCFS und Zeitscheibenverfahren. Alle Prozesse erhalten in der Reihenfolge ihres Eintreffens eine Zeitscheibe und werden hinten in die Warteschlange eingereiht.
Schauen wir uns die Ausführungsreihenfolge mit einer Zeitscheibenlänge q = 4 einmal genauer an.

1. Wie ist die Wartezeit der einzelnen Prozesse?
   P1 = 15
   P2 = 4
   P3 = 15
   P4 = 16


2. Wie ist die durchschnittliche Wartezeit?
   ((15+4+15+16)/4) = 12,5
3. Nach welcher Zeit hat der letzte Prozess seine Tätigkeit beendet?
   32

Somit wird die Prozessbearbeitung durch das System beeinflusst, es besteht aber keine Möglichkeit, dass ein Job verhungert.

Hier handelt es sich um die Analogie zum Shortest Job first Verfahren. Derjenige Job mit der kürzesten Bedienzeit wird bevorzugt.
Die Ankunftszeiten der Prozesse sind: P1/P2 = 0, P3/P4 = 4

1. Wie ist die Wartezeit der einzelnen Prozesse?
   P1 = 15
   P2 = 0
   P3 = 0
   P4 = 5


2. Wie ist die durchschnittliche Wartezeit?
   ((15+0+0+5)/4) = 5
3. Nach welcher Zeit hat der letzte Prozess seine Tätigkeit beendet?
   32

Dieses Verfahren berücksichtigt die Vergangenheit vorheriger Prozesse, um zu entscheiden welcher Prozess als nächstes an die Reihe kommt. Wartende Prozesse, die gerade keine CPU Zeit zugewiesen bekommen, erhalten eine höhere Priorität (Verhungern somit nicht). Prozesse die gerade aktiv bearbeitet werden, erhalten nach Ablauf ihrer Zeitscheibe (Quantum) eine niedrigere Priorität. Ihr Quantum verdoppelt sich jedoch, sollte die vollständige Bedienzeit noch nicht aufgebraucht sein.

Bemerkung: Die durchschnittliche Wartezeit kann verbessert werden indem die Startpriorität und Startquanten angepasst werden.

Den Prozessen sollen alle notwendigen Ressourcen unter Einhaltung garantierter Zeitforderungen zugeteilt werden. Zu den „klassischen“ Zielen kommt somit ein neues Ziel hinzu: Die Einhaltung der vorgegebenen Zeitschranken.

Minimal Deadline First

Bei diesem Verfahren wird der Prozess mit der nächstliegenden Deadline abgearbeitet. Haben mehrere Prozesse eine gleiche Deadline wird eine zusätzliche Strategie benötigt.

Minimal Processing Time First

Siehe Shortest Job First (SJF)-Verfahren

Minimum Earliest Start

Der Prozess, der die kleinste Zeit TStart besitzt, zu der alle seine benötigten Betriebsmittel frei sind, wird gewählt.

Rate-Monotonic Scheduling (RMS)

Hier handelt es sich um ein Prioritätsscheduling-Verfahren. Prioritäten werden gemäß der Ausführungsrate („Rate monotonic“) eines Jobs festgelegt. Je höher die Ausführungsrate eines Jobs, desto höher ist seine Priorität.