Prozessplanung — Betriebssystemkonzepte

Prozessplanung ist die Entscheidung des Betriebssystems, welcher bereite Prozess als Nächstes die CPU bekommt. Einfach gesagt ist es die Regel dafür, wer jetzt läuft und wer warten muss. Diese Regel verändert Wartezeit, Antwortzeit, Fairness und den gesamten Durchsatz.

Prozessplanung ist wichtig, weil dieselbe Menge von Prozessen unter FCFS, SJF oder Round Robin in sehr unterschiedlicher Reihenfolge enden kann. Wenn du diese eine Idee verstehst, werden die meisten Lehrbuchbeispiele deutlich leichter lesbar.

Was Prozessplanung im Betriebssystem bedeutet

Im üblichen Betriebssystemmodell wechseln Prozesse zwischen Zuständen wie bereit, laufend und wartend. Der Scheduler wählt unter den bereiten Prozessen aus.

Deshalb wird Prozessplanung oft auch CPU-Scheduling genannt. Sie erzeugt keine neue Arbeit. Sie entscheidet über die Reihenfolge, in der wartende Arbeit CPU-Zeit bekommt.

In modernen Systemen plant der Kernel oft direkt Threads ein, aber der klassische Begriff „Prozessplanung“ ist weiterhin der übliche Lehrbegriff.

Was ein Scheduler zu optimieren versucht

Ein Scheduler versucht normalerweise, mehrere Ziele auszubalancieren:

• geringe Wartezeit
• schnelle Reaktion bei interaktiven Aufgaben
• guter Durchsatz
• Fairness
• vorhersagbares Verhalten

Diese Ziele können miteinander in Konflikt stehen. Eine Strategie, die in einem vereinfachten Beispiel die durchschnittliche Wartezeit senkt, kann sich in der Praxis trotzdem unfair anfühlen, und eine faire Zeitteilung kann die Fertigstellung eines kurzen Jobs verzögern.

Präemptives vs. nicht-präemptives Scheduling

Ein nicht-präemptiver Scheduler lässt einen laufenden Prozess die CPU behalten, bis sein CPU-Burst endet oder er blockiert. First-Come, First-Served ist das Standardbeispiel.

Ein präemptiver Scheduler kann einen laufenden Prozess unterbrechen und die CPU einem anderen geben. Round Robin und viele Prioritätsscheduler tun das.

Dieser Unterschied ist wichtig, weil sich die Antwortzeit oft verbessert, wenn das System lang laufende Arbeit unterbrechen darf.

Häufige Prozessplanungsalgorithmen

First-Come, First-Served

First-Come, First-Served oder FCFS führt Prozesse in der Reihenfolge ihrer Ankunft aus. Es ist leicht zu verstehen und einfach zu implementieren, aber ein langer Job am Anfang kann dafür sorgen, dass jeder kurze Job dahinter warten muss.

Shortest Job First

Shortest Job First oder SJF bevorzugt den Prozess mit dem kleinsten CPU-Burst. In einer vereinfachten Situation, in der Burst-Längen genau bekannt sind, kann es die durchschnittliche Wartezeit verringern. In realen Systemen muss diese Burst-Länge meist geschätzt werden.

Round Robin

Round Robin gibt jedem bereiten Prozess ein kleines Zeitfenster, das Quantum genannt wird. Wenn der Prozess in diesem Zeitfenster nicht fertig wird, geht er zurück in die Ready Queue. Das verbessert meist Fairness und Reaktionsfähigkeit bei interaktiven Arbeitslasten.

Prioritätsscheduling

Prioritätsscheduling führt zuerst den bereiten Prozess mit der höchsten Priorität aus. Das kann nützlich sein, wenn manche Aufgaben wichtiger sind als andere. Wenn Prozesse mit niedriger Priorität aber zu lange warten, entsteht das Risiko von Verhungern.

Ein Rechenbeispiel mit Wartezeit

Angenommen, drei Prozesse kommen alle zur Zeit $0$ an und benötigen jeweils nur CPU-Zeit:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Angenommen:

• es gibt eine CPU
• es gibt keine I/O-Blockierung
• die Kosten für Kontextwechsel werden ignoriert

Unter diesen Bedingungen bedeutet Wartezeit die Zeit, die ein Prozess in der Ready Queue verbringt, bevor er läuft. Die Turnaround-Zeit ist

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Wenn FCFS verwendet wird, ist die Reihenfolge $P_1 \rightarrow P_2 \rightarrow P_3$.

Zeitleiste:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Wartezeiten:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Durchschnittliche Wartezeit:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Wenn nicht-präemptives SJF verwendet wird, ist die Reihenfolge $P_3 \rightarrow P_2 \rightarrow P_1$.

Zeitleiste:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Wartezeiten:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Durchschnittliche Wartezeit:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Dieses Beispiel zeigt die wichtigste Intuition. Die Arbeitslast hat sich nicht geändert, aber die Regel hat das Ergebnis verändert. Hier liefert SJF eine geringere durchschnittliche Wartezeit, weil die kurzen Jobs nicht hinter dem langen feststecken.

Das bedeutet nicht, dass SJF immer die beste Wahl in der Praxis ist. Es bedeutet, dass unter den Annahmen dieses Beispiels die Planungsreihenfolge sehr wichtig ist.

Die Intuition, die du dir merken solltest

Betrachte Prozessplanung als Warteschlangendisziplin für die CPU. Die Ready Queue kann dieselben Jobs enthalten, aber die Regel für ihre Bedienung verändert, was Nutzer erleben.

Wenn dir schnelle erste Reaktionen am wichtigsten sind, bevorzugst du vielleicht häufiges Teilen. Wenn dir wichtig ist, viele kurze Jobs schnell abzuschließen, bevorzugst du vielleicht eine Strategie, die kurze Bursts begünstigt. Wenn dir strikte Zeitvorgaben wichtig sind, brauchst du vielleicht wieder einen anderen Scheduler.

Häufige Fehler bei Scheduling-Aufgaben

Annehmen, dass eine Strategie immer die beste ist

Es gibt keinen einzigen Gewinner für jede Arbeitslast. Eine Strategie kann bei der durchschnittlichen Wartezeit hervorragend aussehen und trotzdem schlecht für Fairness oder Deadlines sein.

Wartezeit, Antwortzeit und Turnaround-Zeit verwechseln

Diese Metriken hängen zusammen, sind aber nicht identisch. Insbesondere bedeutet Antwortzeit meist die Zeit bis zur ersten CPU-Zuteilung oder zur ersten sichtbaren Reaktion, während die Turnaround-Zeit den gesamten Job von der Ankunft bis zum Abschluss misst.

Die Bedingung hinter der Formel ignorieren

Metriken sind nur unter den angegebenen Annahmen sinnvoll. Wenn eine Aufgabe I/O-Blockierung, unterschiedliche Ankunftszeiten oder Overhead durch Kontextwechsel enthält, ändern sich Zeitleiste und Ergebnisse.

Vergessen, ob die Strategie präemptiv ist

SJF und Shortest Remaining Time First sind nicht dieselbe Regel. Auch Prioritätsscheduling verhält sich unterschiedlich, je nachdem, ob ein Job mit höherer Priorität den aktuellen unterbrechen darf.

Wo Prozessplanung verwendet wird

Prozessplanung ist überall dort wichtig, wo ein Betriebssystem CPU-Zeit teilen muss:

• Desktop- und mobile Systeme, die reaktionsfähige Apps brauchen
• Server, die viele Anfragen bearbeiten
• Batch-Systeme, bei denen der Durchsatz wichtig ist
• Echtzeitsysteme, bei denen Zeitgarantien wichtig sind

Reale Scheduler sind meist komplexer als Lehrbuchversionen, aber dieselben Zielkonflikte tauchen weiterhin auf.

Probiere deine eigene Variante aus

Ändere das Beispiel so, dass $P_2$ später ankommt, oder ersetze FCFS durch Round Robin mit einem Quantum von $2\ \mathrm{ms}$, und beobachte, wie sich das Wartemuster verändert. Wenn du nach der Handrechnung noch einen Schritt weitergehen willst, probiere deine eigene Variante im GPAI Solver aus und vergleiche deine vorhergesagte Zeitleiste mit der berechneten.