CPU-Prozess-Scheduling (Prozessablaufplanung)

In den letzten Abschnitten dieses Kapitels haben wir die grundsätzlichen Ideen des Multitaskings und des Multithreadings kennengelernt. Ein Frage blieb aber noch offen. Erinnern wir uns an das Diagramm in Abbildung , so ist die Frage welche Prozesse sich im Moment in rechnenden Zustand und welche sich im rechenbereiten Zustand befinden noch offen. Dieser Frage wollen wir uns nun zuwenden. Vor einem ähnlichen Problem steht man bei dem Konzept der Threads. Kernel-Threads haben dabei eine große Ähnlichkeit zu Prozessen, da diese ebenfalls vom Betriebssystem gescheduled werden müssen. Das Scheduling von Userlevel-Threads dagegen ist ein Problem, das nicht vom Betriebssystem gelöst werden muss. Letztendlich ist es ein Software-Problem auf der Programmierebene. Wir werden uns das Threadschudulingkonzept von Java näher anschauen.

Im Folgenden werden wir nun verschiedenen Verfahren kennenlernen, nach denen Prozesse vom rechenbereiten in den rechnenden Zustand überführt werden. Man nennt dieses Verfahren CPU-Prozess-Scheduling oder in deutsch Prozessablaufplanung. Prozess-Scheduling wird dann nötig, wenn einer der folgenden vier Fälle eintritt:

1. Wenn ein Prozess vom rechnenden in rechenbereiten Zustand überführt wird.
2. Wenn ein Prozess blockiert wird (z.B. Warten auf ein I/O-Gerät oder Empfang eines wait-Signals
3. Wenn ein Prozess vom blockierten Zustand in den rechenbereiten Zustand überführt wird.
4. Wenn ein Prozess beendet wird.

Wenn Prozess-Scheduling nur in den Fällen 2 und 4 erfolgt, so spricht man von non-preemtivem oder kooperativem Scheduling. Für non-preemtives Scheduling ist es nicht nötig nach einem bestimmten Verfahren ein Prozess vom rechnenden in den rechenbereiten Zustand zu überführen.

In der Regel geschieht die Überführung vom rechnenden in rechenbereiten Zustand beim preemtivem Scheduling dadurch, dass einem Prozess der vom rechenbereiten Zustand in den rechnenden Zustand überführt ein Zeitquantum zugeordnet wird. Wenn das Zeitquantum verbraucht ist, wird er wieder zurück in den rechenbereiten Zustand versetzt. Aus diesem Grund braucht man für preemtives Scheduling Hardware, die einen Timer zur Verfügung stellt. Beim Windows 3.11 Betriebssystem von Mircosoft wurde non-preemtives Scheduling benutzt.

Eine weitere Komponente, die in das Scheduling mit einbezogen ist, ist der Dispatcher. Er ist für die Durchführung des Prozessaustauschs zuständig. Es ist wichtig, dass dieser Austausch möglich effizient vollzogen wird. Dennoch ist es nicht möglich ganz ohne zusätzliche Rechenzeit auszukommen. die Verzögerung, die durch den Dispatcher entsteht nennt man dispatch latency.

Wenden wir uns nun Algorithmen (Schedulern) zu, die das CPU-Prozess-Scheduling durchführen. Zunächst wollen wir uns Kriterien überlegen, denen Scheduler genügen sollten.

1. CPU-Auslastung Ein Kriterum könnte sein, wie ausgelastet die CPU ist.
2. Beendigungsrate Die Rate der beendeten Prozesse innerhalb eines bestimmten Zeitraums könnte ein weiteres Maß sein.
3. Rückkkehrzeit Aus Sicht eines Prozesses könnte die Zeitspanne vom Start bis zu seiner Beendigung ein Kriterum sein.
4. Zeit im rechenbereiten Zustand Die Zeit, die sich ein Prozess im rechenbereiten Zustand befindet, könnte ebenfalls ein Kriterium sein, weil die Zeit im blockierten Zustand uninteressant ist, da in dieser Zeit der Prozess ohnehin nicht rechnen könnte.
5. Antwortzeit Für einen Benutzer an einem interaktiven System kann auch die Antwortzeit von Interesse sein. Wenn der Benutzer eine relativ lange Antwort lesen muss, so kann durchaus während der Benutzer schon die ersten Zeilen der Ausgabe liest, noch weiter gerechnet werden.