Prozessplanung in Betriebssystemen: Ziele, Kriterien und Algorithmen

Scheduling-Level

• Kurzfristiger Scheduler: Zuweisung des Prozessors an bereite Prozesse; schnelle Entscheidungen.
• Mittelfristiger Scheduler: Ein- und Auslagerung (Swapping) von Prozessen zur Steuerung des Mehrprogrammbetriebs.
• Langfristiger Scheduler: Auswahl der Jobs, die in das System aufgenommen werden.

Ziele der Planung

• Maximierung der CPU-Auslastung
• Maximierung des Durchsatzes
• Minimierung der Antwortzeit für interaktive Benutzer
• Vorhersehbarkeit der Ausführungszeiten
• Gerechte Verteilung der Ressourcen (Fairness)
• Ausgleich zwischen Prozessorlast und Systembelastung
• Sicherstellung der Prioritäten

Kriterien der Planung

• Durchlaufzeit (Turnaround-Zeit): Zeit von der Ankunft bis zum Abschluss eines Prozesses.
• Wartezeit: Zeit, die ein Prozess in der Bereitschaftsliste verbringt.
• Antwortzeit: Zeit bis zur ersten Reaktion des Systems; hier nicht entscheidend, sobald ein Prozess erstmals ausgeführt wird.
• Verhältnis Ausführungszeit/Durchlaufzeit: Maß für die Effizienz der Bedienung.

Politiken der Planung

• Verdrängende (präemptive) Politik: Der laufende Prozess kann jederzeit unterbrochen und in die Bereitschaftsliste zurückgesetzt werden.
• Nicht verdrängende Politik: Ein Prozess behält den Prozessor, bis er terminiert oder auf eine Ressource wartet.

Algorithmen der Planung

• FCFS (First Come, First Served) bzw. FIFO: Bedienung in der Reihenfolge der Ankunft; nicht verdrängend.
• Round Robin (RR): Zyklische Zuteilung fester Zeitscheiben (Quantum); verdrängend.
• SJF (Shortest Job First): Auswahl des Prozesses mit der kürzesten Rechenzeit; nicht verdrängend.
• SRT (Shortest Remaining Time): Auswahl des Prozesses mit der kürzesten Restzeit; verdrängende Variante von SJF.
• Prioritätsplanung: Auswahl des Prozesses mit der höchsten Priorität; verdrängend oder nicht verdrängend.
• Mehrstufige Rückkopplungswarteschlangen (Multilevel Feedback Queues): Mehrere Warteschlangen mit Prozessen, die je nach Verhalten zwischen den Ebenen wechseln können.

FCFS im Detail

• Prozesse werden in der Reihenfolge ihrer Ankunft bedient.
• Ein Prozess läuft, bis er terminiert oder blockiert.
• Einfach umzusetzen, aber lange Wartezeiten bei kurzen Prozessen hinter langen Prozessen (Convoy-Effekt).

Round Robin im Detail

• Jeder Prozess erhält ein Zeitquantum (q).
• Nach Ablauf des Quantums wird der Prozess an das Ende der Warteschlange gesetzt.
• Die Größe von q beeinflusst das Verhalten: zu klein führt zu hohem Kontextwechsel-Aufwand, zu groß nähert sich FCFS an.
• Die Warteschlange wird meist als FIFO geführt.

SJF im Detail

• Der Prozess mit der kürzesten erwarteten Rechenzeit wird zuerst ausgeführt.
• Minimiert die mittlere Wartezeit, erfordert jedoch eine Schätzung der Laufzeit.
• Gefahr des Verhungerns (Starvation) langer Prozesse.

SRT im Detail

• Verdrängende Variante von SJF: Ein neu ankommender Prozess mit kürzerer Restzeit verdrängt den laufenden.
• Sehr effizient, aber mit höherem Verwaltungsaufwand.

Prioritäten

• Prioritäten können statisch (unveränderlich) oder dynamisch (veränderlich) sein.
• Prozesse mit gleicher Priorität werden meist nach FCFS oder Round Robin bedient.
• Problem: Verhungern niedrig priorisierter Prozesse.
• Lösung: Alterung (Aging), bei der die Priorität eines wartenden Prozesses mit der Zeit steigt.

Mehrstufige Warteschlangen

• Prozesse werden dauerhaft verschiedenen Warteschlangen zugeordnet, etwa nach Typ (interaktiv oder Batch).
• Zwischen den Warteschlangen erfolgt die Planung meist prioritätsbasiert und verdrängend.
• Innerhalb der Warteschlangen können unterschiedliche Algorithmen eingesetzt werden, z. B. RR oder FCFS.

Mehrstufige Rückkopplungswarteschlangen

• Prozesse können zwischen den Warteschlangen wechseln.
• CPU-intensive Prozesse werden in niedrigere Prioritätsebenen verschoben, E/A-intensive Prozesse bleiben in höheren Ebenen.
• Flexibel und an das Verhalten der Prozesse angepasst; in den meisten realen Systemen wird eine Kombination verschiedener Algorithmen verwendet.