CPU-Scheduling-Algorithmen in Betriebssystemen erklärt
Kurze Antwort
CPU-Scheduling-Algorithmen steuern, welcher bereite Prozess als Nächstes die CPU nutzt. Sie beeinflussen Auslastung, Wartezeit, Durchsatz und Antwortzeit. Die Wahl hängt von Systemtyp, Last und Fairnessanforderungen ab.
Das Wichtigste
- Der Scheduler wählt aus der Ready-Queue einen Prozess für die CPU aus.
- Preemptive Verfahren können laufende Prozesse unterbrechen, nicht-preemptive nicht.
- FCFS, SJF, SRTF, Priorität und Round Robin lösen unterschiedliche Probleme.
- Metriken wie Wartezeit und Turnaround-Zeit machen Algorithmen vergleichbar.
- Mehrere Kerne erfordern zusätzliche Verteilungsentscheidungen.
CPU-Scheduling-Algorithmen legen fest, welcher bereite Prozess als Nächstes Rechenzeit erhält. Zu einem Zeitpunkt bearbeitet ein Prozessor nur eine Aufgabe, auch wenn viele Programme warten. Der Scheduler wählt aus den bereiten Prozessen einen aus und übergibt ihm die CPU. So bleibt der Prozessor ausgelastet und das System reagiert zügiger.
CPU-Scheduling-Algorithmen: Grundbegriffe
Ein Prozess durchläuft Zustände wie neu, bereit, laufend, wartend und beendet. Der Scheduler arbeitet mit der Menge der bereiten Prozesse. Er berücksichtigt die Reihenfolge, Prioritäten, Restlaufzeiten und Zeitanteile.
Die Auswahl erfolgt nach festen Regeln. Diese Regeln bilden den Scheduling-Algorithmus. Ziel sind hohe CPU-Auslastung und akzeptable Wartezeiten. In Echtzeitsystemen variiert die Auslastung zwischen 40 und 90 Prozent, abhängig von der Systemlast.
Preemptiv und nicht-preemptiv
Preemptive Verfahren können einen laufenden Prozess unterbrechen, etwa bei höherer Priorität oder abgelaufenem Zeitquantum. Nicht-preemptive Verfahren lassen den laufenden Prozess arbeiten, bis er die CPU freiwillig abgibt.
Nicht-preemptive Planung gilt, sobald ein Prozess beendet wird oder in den Wartezustand wechselt. Für Unterbrechungen kommt sie ohne Timer-Hardware aus. Preemptive Planung ermöglicht feinere Reaktionszeiten, erzeugt aber mehr Kontextwechsel.
Wichtige Algorithmen im Vergleich
Die folgenden Verfahren decken die wichtigsten Ansätze ab. Jedes Verfahren optimiert andere Ziele und bringt eigene Risiken mit.
| Algorithmus | Prinzip | Stärke | Schwäche |
|---|---|---|---|
| FCFS | Reihenfolge des Eintreffens | Einfach und vorhersehbar | Lange Prozesse können kurze blockieren |
| SJF | Kürzeste geschätzte Laufzeit zuerst | Geringe durchschnittliche Wartezeit | Laufzeitschätzung nötig |
| SRTF | Kürzeste Restlaufzeit zuerst | Reagiert auf neue kurze Prozesse | Häufige Unterbrechungen |
| Priorität | Höchste Priorität zuerst | Wichtige Aufgaben zuerst | Niedrige Prioritäten können verhungern |
| Round Robin | Feste Zeitquanten im Kreis | Fairer CPU-Anteil | Viele Kontextwechsel bei kleinen Quanten |
First Come First Serve
FCFS bearbeitet Prozesse in der Reihenfolge ihres Eintreffens. Das Verfahren ist leicht zu verstehen und zu implementieren. Lange Prozesse können nachfolgende kurze Prozesse lange warten lassen. Deshalb eignet sich FCFS vor allem für einfache oder batch-orientierte Systeme.
Shortest Job First und SRTF
SJF wählt den Prozess mit der kürzesten geschätzten Laufzeit. Dadurch sinkt die durchschnittliche Wartezeit, wenn die Schätzung stimmt. SRTF ist die preemptive Variante und wechselt zur kürzesten Restlaufzeit. Beide Verfahren brauchen verlässliche Laufzeitschätzungen und können kurze Prozesse bevorzugen.
Prioritätsscheduling
Beim Prioritätsscheduling erhält der Prozess mit der höchsten Priorität die CPU. Prioritäten können statisch oder dynamisch vergeben werden. Ohne Gegenmaßnahmen können Prozesse mit niedriger Priorität lange warten. Aging, also das schrittweise Erhöhen der Priorität wartender Prozesse, kann dieses Problem mildern.
Round Robin
Round Robin gibt jedem Prozess ein festes Zeitquantum. Nach Ablauf des Quantums wechselt der Scheduler zum nächsten bereiten Prozess. Das Verfahren ist fair und verhindert dauerhafte CPU-Blockaden durch einen einzelnen Prozess. Die Größe des Zeitquantums beeinflusst Reaktionszeit und Anzahl der Kontextwechsel.
Metriken zur Bewertung
Metriken machen Scheduler vergleichbar. Sie beschreiben, wie lange Prozesse warten und wie viel Arbeit das System erledigt.
- CPU-Auslastung: Anteil der Zeit, in der die CPU arbeitet.
- Durchsatz: Anzahl abgeschlossener Prozesse pro Zeiteinheit.
- Turnaround-Zeit: Zeit von der Ankunft eines Prozesses bis zu seinem Abschluss.
- Wartezeit: Zeit in der Ready-Queue.
- Antwortzeit: Zeit bis zur ersten Reaktion in interaktiven Systemen.
Die Metriken stehen in Konflikt. Ein Verfahren kann die durchschnittliche Wartezeit senken und gleichzeitig die Antwortzeit erhöhen. Deshalb bewertet man Scheduler anhand des Systemtyps, nicht anhand einer einzelnen Zahl.
Fairness und Verhungern
Fairness bedeutet, dass kein Prozess dauerhaft CPU-Zeit verliert. Round Robin erreicht dies durch gleiche Zeitanteile. Prioritätsscheduling kann Verhungern verursachen, wenn niedrige Prioritäten nie an die Reihe kommen. Aging und dynamische Prioritäten sind Gegenmaßnahmen.
Batch-, interaktive und Echtzeitsysteme
Batch-Systeme verarbeiten Aufträge ohne direkte Benutzerinteraktion. Dort zählen Durchsatz und Turnaround-Zeit. Interaktive Systeme müssen schnell auf Eingaben reagieren, daher ist die Antwortzeit wichtig. Echtzeitsysteme haben feste Fristen; ein verspätetes Ergebnis kann nutzlos sein. Deshalb wählt man in Echtzeitsystemen oft prioritätsbasierte oder fristenorientierte Verfahren.
Ein Desktop-System profitiert von Round Robin mit kleinem Quantum, weil Fenster und Eingaben flüssig wirken. Ein Server für Hintergrundaufgaben kann FCFS oder SJF nutzen, wenn Vorhersagbarkeit wichtiger ist als Reaktionszeit. Die gleiche Hardware kann also unterschiedliche Scheduler erfordern.
Kontextwechsel und Overhead
Jeder Wechsel zwischen Prozessen kostet Zeit. Register, Programmzähler und Speicherzuordnungen müssen gesichert und wiederhergestellt werden. Zu viele Wechsel senken den nutzbaren CPU-Anteil. Round Robin mit sehr kleinem Quantum erzeugt deshalb oft mehr Overhead als Nutzen.
Preemptive Verfahren erhöhen die Anzahl der Wechsel, weil sie laufende Prozesse unterbrechen können. Nicht-preemptive Verfahren reduzieren diesen Aufwand, reagieren aber langsamer auf neue Prozesse. Die Wahl ist ein Kompromiss zwischen Reaktionszeit und Effizienz.
Zeitquantum wählen
Das Zeitquantum bestimmt, wie lange ein Prozess maximal am Stück läuft. Ein zu großes Quantum nähert Round Robin an FCFS an und verschlechtert die Reaktionszeit. Ein zu kleines Quantum erhöht die Zahl der Kontextwechsel. In der Praxis wählt man ein Quantum, das deutlich größer ist als die Dauer eines Kontextwechsels, aber klein genug für interaktive Antwortzeiten.
Es gibt keine universelle Größe. Die passende Wahl hängt von der typischen Prozessdauer und der Hardware ab. Messungen und Gantt-Diagramme helfen, die Auswirkungen zu prüfen.
Starvation und Aging
Starvation entsteht, wenn ein Prozess dauerhaft nicht an die CPU gelangt. Prioritätsscheduling begünstigt dieses Risiko. Aging erhöht die Priorität wartender Prozesse schrittweise, bis sie an die Reihe kommen. Dynamische Prioritäten können ähnliche Effekte erzielen.
Round Robin vermeidet Starvation durch gleiche Zeitanteile, kann aber bei sehr unterschiedlichen Prozesslängen ineffizient sein. Kombinierte Verfahren, etwa mehrstufige Warteschlangen, versuchen Fairness und Effizienz zu verbinden. Solche Kombinationen sind in realen Systemen üblich.
Gantt-Diagramme als Werkzeug
Gantt-Diagramme stellen CPU-Nutzung über die Zeit dar. Sie zeigen, wann ein Prozess läuft, wartet oder blockiert. Aus dem Diagramm lassen sich Wartezeiten und Turnaround-Zeiten ablesen. Deshalb dienen sie in der Lehre und in der Analyse als einfaches Hilfsmittel.
Ein Diagramm macht Engpässe sichtbar. Wenn ein langer Prozess die CPU blockiert, erkennt man die Wartezeit nachfolgender Prozesse sofort. Änderungen am Algorithmus lassen sich so vor der Implementierung vergleichen.
Häufige Missverständnisse
Ein Scheduler verbessert nicht die reine Rechenleistung der CPU. Er verteilt vorhandene Zeit besser. Auch ein optimaler Algorithmus kann keine zusätzliche Rechenkapazität erzeugen.
Eine niedrige durchschnittliche Wartezeit bedeutet nicht automatisch eine gute Antwortzeit. Interaktive Systeme brauchen schnelle erste Reaktionen, auch wenn die Gesamtlaufzeit länger ist. Deshalb ist die Wahl des Algorithmus immer an den Anwendungsfall gebunden.
Mehrkernsysteme und Betriebssysteme
Mehrere Kerne erlauben die gleichzeitige Ausführung mehrerer Prozesse. Der Scheduler verteilt Aufgaben auf Kerne und muss Lastungleichgewichte vermeiden. Je nach Leistungsziel und Systementwurf setzen Betriebssysteme unterschiedliche Planungsverfahren ein, etwa Zeitteilung oder prioritätsbasierte Planung. Die Wahl hängt von Hardware, Workload und Echtzeitanforderungen ab.
Grundlagen des Systems erklärt Was ist ein Betriebssystem? Funktion und Ablauf. Kernelarchitekturen beeinflussen Planung; siehe monolithischer kernel vs microkernel: Kernelarchitekturen. Speicherverwaltung und Prozesszustände hängen zusammen; siehe Wie funktioniert virtueller Speicher? Paging erklärt.
Typische Fehler bei der Auswahl
Komplexe Verfahren in einfachen Systemen erhöhen den Overhead ohne zusätzlichen Nutzen. Umgekehrt können einfache Verfahren in Echtzeitumgebungen zu späten Reaktionen führen. Auch ein ungeeigneter Algorithmus für den Systemtyp kann die Leistung verschlechtern. Gantt-Diagramme helfen, Abläufe und Wartezeiten sichtbar zu machen.
Weitere häufige Fragen
Was ist der Unterschied zwischen preemptivem und nicht-preemptivem Scheduling?
Preemptive Verfahren können einen laufenden Prozess unterbrechen. Nicht-preemptive Verfahren warten, bis der Prozess die CPU freiwillig abgibt oder endet.
Welcher CPU-Scheduling-Algorithmus ist der fairste?
Round Robin gilt als fair, weil jedem Prozess ein gleiches Zeitquantum zusteht. Die tatsächliche Fairness hängt aber von der Quantumgröße und der Last ab.
Warum kann Prioritätsscheduling zu Starvation führen?
Prozesse mit niedriger Priorität können dauerhaft zurückgestellt werden, wenn ständig höher priorisierte Prozesse bereit sind. Aging kann dieses Problem mildern.
Welche Metrik ist für interaktive Systeme am wichtigsten?
Die Antwortzeit ist entscheidend, weil Benutzer eine schnelle erste Reaktion erwarten. Turnaround-Zeit allein reicht dafür nicht aus.
Verwandte Seiten
- Wie funktionieren Treiber im Betriebssystem?
Gerätetreiber sind Programme, die zwischen Betriebssystem und Hardware vermitteln. Sie übersetzen Systembefehle in gerätespezifische Aktionen und melden Ergebnisse zurück. Ohne passende Treiber arbeitet Hardware oft nur eingeschränkt oder gar nicht.
- RTOS vs GPOS Unterschied: Echtzeit- und Universal-OS
Ein RTOS ist auf deterministische Reaktionszeiten und strenge Zeitvorgaben für zeitkritische Anwendungen ausgelegt. Ein GPOS priorisiert Flexibilität, Benutzerfreundlichkeit und Durchsatz für allgemeine Aufgaben. Der Unterschied zeigt sich vor allem in Scheduling, Preemption, Speicheroptimierung und typischen Einsatzgebieten.
- Deadlock Betriebssystem Ursachen Vermeidung: Bedingungen
Ein Deadlock blockiert mehrere Prozesse dauerhaft, weil jeder eine Ressource hält und auf eine andere wartet. Er tritt nur auf, wenn vier Bedingungen gleichzeitig erfüllt sind. Betriebssysteme verhindern, vermeiden, erkennen oder ignorieren ihn je nach Kosten und Häufigkeit.
- Bootvorgang Betriebssystem Ablauf: Schritt für Schritt
Der Bootvorgang beginnt mit dem Einschalten und endet, wenn das Betriebssystem im Arbeitsspeicher läuft. Dazwischen prüft die Firmware die Hardware, wählt ein Startgerät, lädt den Bootloader und übergibt an den Kernel. Kalte und warme Starts unterscheiden sich vor allem im Umfang der Hardwareprüfung.
- Dateisysteme im Vergleich: NTFS, FAT32, exFAT und ext4
NTFS, FAT32, exFAT und ext4 unterscheiden sich bei Dateigrößenlimits, Kompatibilität und Metadatenfunktionen. NTFS und ext4 bieten Journaling und Rechte, FAT32 maximale Kompatibilität und exFAT große Dateien auf Wechseldatenträgern. Die passende Wahl hängt vom Betriebssystem und vom Einsatzzweck ab.
- Unterschied 32 bit und 64 bit: Betriebssysteme
Ein 32-Bit-System kann bis zu 4 GB RAM adressieren, ein 64-Bit-System theoretisch 16 Exabyte. Der Unterschied betrifft Speicher, Datenverarbeitung, Software und Treiber. Für moderne Rechner mit mehr als 4 GB RAM ist 64-Bit die passende Wahl.
Wie diese Seite entstanden ist
Vor dem Schreiben wurde das Thema in den unten genannten Quellen recherchiert. Danach hat die Seite automatische Qualitätsprüfungen bestanden.