Wenn man Scheduling bei Google eingibt, spuckt es einem erst einmal direkt als Erstes diese Definition aus:

„Scheduling ist ein Anglizismus für die Erstellung eines Ablaufplanes, der Prozessen zeitlich begrenzt Ressourcen zuteilt.“

Hier in diesem Beitrag beschreibe ich noch genauer, was ein Scheduler ist, wie Scheduling funktioniert, wozu es dient und viel mehr.

Lies den Beitrag von Anfang an, wenn du damit noch gar nicht vertraut bist oder benutze das Inhaltsverzeichnis, um direkt zum für dich interessanten Thema zu gelangen.

Die Aufgaben des Schedulers

1. Wenn ein aktiver Prozess aus irgendwelchen Gründen blockiert wird, z. B. weil er auf eine Reaktion wartet oder auf Ressourcen, dann entscheidet der Scheduler welcher der anderen Prozesse die CPU erhält
2. Hat ein Prozess die CPU schon „zu lange“, dann verdrängt der Scheduler diesen und gibt einem anderen die CPU
3. Kommt ein neuer Prozess dazu, entscheidet der Scheduler darüber, ob diesen nun die CPU bekommt.
4. Wenn ein blockierter Prozess wieder auf „bereit“ ist, entscheidet der Scheduler darüber, ob der gerade laufende verdrängt werden soll, damit der „bereite“ wieder „aktiv“ sein kann.

Ziele eines Schedulers

• Stabilität: flüssiges Laufen im Overload-Fall
• Rechtzeitige Reaktion: Garantiert die Einhaltung von „Terminen“
• Kurze Antwortzeit: schnelle Reaktion, vor allem z. B. bei Interaktion
• Kein Verhungern: kein Prozess der kaum bis gar nicht mehr in den „aktiv“ Modus kommt
• Fairness: jeder Prozess soll ungefähr die gleiche CPU bekommen
• Hoher Durchsatz: es sollen möglichst viele Aufgaben pro Zeiteinheit erledigt werden
• Prozessorauslastung: die CPU ist nie idle

Zielkonflikte

Wie aus den Zielen vielleicht schon ersichtlich ist, kann es zwischen den Zielen des Schedulers zu Konflikten kommen. Zum Beispiel kann es zwischen dem Einhalten von Terminen und der Fairness zum Konflikt kommen, weil ein Prozess immer wieder die CPU benötigt, um seine „Termine“ einzuhalten, das ist für die anderen Prozesse dann natürlich unfair, weil sie weniger CPU bekommen.

Scheduling Verfahren

Da die Anforderungen an den Scheduler, der Zweck und das System unterschiedlich sein können, gibt es nicht nur ein Scheduling-Verfahren, sondern verschiedene.

Diese werde ich hier kurz erklären.

Einfache Scheduling Verfahren

Kommen wir zunächst einmal zu den Erklärungen der einfachen Scheduling-Verfahren. Das Prinzip ist bei diesen unkompliziert und leicht verständlich.

First Come First Serve (FCFS)

Bei diesem Verfahren bekommt der Prozess die CPU, der schon am längsten „bereit“ ist. Die CPU wird erst wieder abgegeben, wenn der Prozess fertig ist.

Shortest Job First (SJF)

Hier bekommt der Prozess die CPU, der die geringste Bearbeitungszeit hat. Die CPU kann erst entzogen werden, wenn der Prozess fertig ist oder schon wenn einer mit einer noch kürzeren Bearbeitungszeit hereinkommt.

Shortest Remaining Time (SRT)

Beim SRT ist es fast das gleiche Prinzip wie oben beim Shortest Job First nur dass hier die Restlaufzeit der Bearbeitungszeit genommen wird statt der Gesamtzeit.

Prioritätsbasiertes Scheduling

Hier werden Prioritäten vergeben, nach denen der Scheduler den Prozessen die CPU zu ordnet. Diese Prioritäten legt natürlich der Programmierer anhand der Anforderungen fest. Die Prioritäten können statisch sein oder natürlich auch dynamisch, d.h. sie passen sich zur Laufzeit eines Prozesses an. Hierbei kann allerdings das Problem der Prioritätsinvertierung passieren.

Prioritätsinvertierung Beispiel

Ein niedrig priorisierter Prozess Z kann das Betriebsmittel „E/A-Gerät“ haben und sich in der ready-queue befinden, bereit das Betriebsmittel wieder freizugeben.

Ein Prozess Y mit einer mittleren Priorität läuft jetzt aber aktiv (bedeutet hat die CPU).

Der Prozess X mit einer hohen Priorität wäre eigentlich bereit, wenn er das Betriebsmittel „E/A-Gerät“ bekommen würde, muss jetzt aber warten bis Prozess Z es freigibt.

Wie man sieht, kann Prozess X jetzt trotz der höheren Priorität nicht starten, weil das Scheduler dem Prozess Z nicht die CPU gibt, sodass dieser das Betriebsmittel freigeben könnte, weil er von dieser Abhängigkeit nichts weiß.

Round Robin

Beim Round Robin Prinzip kann man sich, das so vorstellen, als würden die Prozesse im Kreis stehen (daher auch der Name „Round“) und jeder einzelne bekommt nun einfach der Reihe nach für eine festgelegte Zeit die CPU.

Echtzeit-Scheduling

Ein Echtzeit-Scheduler muss, wie aus dem Namen schon hervorgeht, die CPU in Echtzeit an die Prozesse verteilen & z. B. auf Interaktionen des Benutzers reagieren können.

Anforderung an Echtzeit-Scheduler

• Er muss klein & kompakt sein
• Schnelle Prozessumschaltung
• Schnelle Interruptbehandlung
• Unterstützung von periodisch wiederkehrenden Aufgaben
• Programmierer kann starken Einfluss auf die Ausführungsabfolge haben (z. B. Vorgabe von Prioritäten)
• Ein stabiles Verhalten z. B. bei Teilausfällen des Systems ist wichtig

Die Vor- und Nachteile von allen Scheduling Verfahren stehen in meinem kostenlosen PDF, die du hier einfach downloaden kannst.

Außerdem erfährst du dort noch alles Weitere und viel mehr im Detail zu:

1. Earliest Deadline First Scheduling
2. Rate Monotonic Scheduling
3. RMS Optimalitätssatz
4. RMS Bewertung
5. Scheduling in Mehrprozessorumgebung
6. Standard Time-Sharing Scheduling
7. Gang Scheduling