CPU-Scheduling

CPU-Scheduling ist die Betriebssystemfunktion, die entscheidet, welcher bereite Prozess oder Thread als Nächstes auf einem Prozessor ausgeführt wird, wobei Ziele wie Reaktionsfähigkeit, Durchsatz, Fairness und die Einhaltung von Fristen abgewogen werden.

Definition

CPU-Scheduling ist die Richtlinie und der Mechanismus, mit dem ein Betriebssystem aus den ausführbaren Prozessen oder Threads auswählt, welchem der Prozessor zugewiesen wird und für wie lange, um die gewählten Leistungs- und Fairnessziele zu optimieren.

Scope

Dieses Thema behandelt Scheduling-Richtlinien und deren Bewertung: First-Come-First-Served, Shortest-Job-First, Round-Robin, Priorität und Multilevel-Feedback-Queues; präemptives versus nicht-präemptives Scheduling; die Kriterien CPU-Auslastung, Durchsatz, Durchlaufzeit, Wartezeit und Antwortzeit; sowie Scheduling auf Multiprozessoren und für Echtzeitsysteme. Ausgeschlossen sind die Darstellung der zu planenden Aufgaben (Prozess- und Thread-Management) und die Synchronisation (Parallelität).

Core questions

• Nach welchen Kriterien wird die Scheduling-Qualität gemessen?
• Wie unterscheiden sich gängige Scheduling-Algorithmen in Fairness und Effizienz?
• Wann sollte der Scheduler eine laufende Aufgabe präemptieren?
• Wie wird Scheduling für Multiprozessoren und Echtzeitfristen angepasst?

Key concepts

• First-Come-First-Served
• Shortest-Job-First
• Round-Robin und Zeitquantum
• Prioritäts-Scheduling
• Multilevel-Feedback-Queues
• präemptiv vs. nicht-präemptiv
• Durchlaufzeit, Wartezeit und Antwortzeit
• Starvation und Aging
• Echtzeit-Scheduling

Key theories

Scheduling-Ziele und Kompromisse

Keine einzelne Richtlinie optimiert alle Ziele: Shortest-Job-First minimiert die durchschnittliche Wartezeit, kann aber lange Jobs aushungern (Starvation), Round-Robin begrenzt die Antwortzeit auf Kosten eines gewissen Durchsatzes, und Prioritätsschemata bergen das Risiko der Starvation. Daher gleichen Scheduler Durchsatz, Fairness und Reaktionsfähigkeit für ihren Workload aus.

Mechanisms

Der Scheduler läuft, wenn ein Prozess blockiert, abgibt oder sein Zeitquantum abläuft, und wählt die nächste Aufgabe aus der Ready-Queue gemäß seiner Richtlinie aus. Round-Robin gibt jeder Aufgabe der Reihe nach ein Zeitfenster; Prioritäts- und Multilevel-Feedback-Queues ordnen Aufgaben nach Wichtigkeit und beobachtetem Verhalten, wobei Aging verwendet wird, um Starvation zu verhindern. Präemptive Scheduler können eine laufende Aufgabe unterbrechen, um zu einer Aufgabe mit höherer Priorität zu wechseln, was für Interaktivität und Echtzeitfristen unerlässlich ist.

Clinical relevance

Scheduling prägt direkt die Benutzererfahrung und die Systemeffizienz: Es bestimmt, ob interaktive Anwendungen reaktionsschnell wirken, ob Batch-Workloads schnell abgeschlossen werden und ob Echtzeitaufgaben Fristen einhalten. Scheduler in Produktionssystemen wie Linux gleichen diese konkurrierenden Ziele über viele Kerne und diverse Workloads hinweg aus.

History

Scheduling-Probleme entstanden mit Multiprogrammierung und Time-Sharing in den 1960er Jahren, als Round-Robin- und Prioritätsschemata entwickelt wurden, um Prozessoren zu teilen. Die Theorie des Echtzeit-Scheduling, einschließlich Rate-Monotonic- und Earliest-Deadline-First-Analysen, wurde in den 1970er Jahren formalisiert, und moderne Multicore-Scheduler erweiterten diese Ideen auf viele Prozessoren.

Debates

Fairness versus Durchsatz und Priorität

Scheduler müssen die Fairness zwischen Aufgaben mit der Maximierung des Durchsatzes und der Einhaltung von Prioritäten in Einklang bringen; aggressive Priorisierung verbessert wichtige Aufgaben, birgt aber das Risiko, andere auszuhungern, während strikte Fairness das System unterauslasten kann. Daher stimmen praktische Scheduler das Gleichgewicht ab.

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

Was ist der Unterschied zwischen präemptivem und nicht-präemptivem Scheduling?

Nicht-präemptives Scheduling lässt eine laufende Aufgabe den Prozessor behalten, bis sie blockiert oder beendet ist. Präemptives Scheduling kann den Prozessor gewaltsam entziehen – zum Beispiel, wenn ihr Zeitfenster abläuft oder eine Aufgabe mit höherer Priorität bereit wird – was die Reaktionsfähigkeit verbessert und für Echtzeitgarantien erforderlich ist.

Was ist Starvation und wie wird sie verhindert?

Starvation tritt auf, wenn eine Aufgabe nie eingeplant wird, weil Aufgaben mit höherer Priorität ständig den Vorrang erhalten. Sie wird üblicherweise durch Aging verhindert, das die Priorität von lange wartenden Aufgaben allmählich erhöht, sodass sie schließlich ausgeführt werden.