Betriebssysteme // Kapitel 4: Scheduling

Was ist das 'Scheduling Problem' und welche Kriterien gibt es?
Frage: In welcher Reihenfolge Prozesse ausgeführt werden sollen.
Kriterien: Schnellste Reaktionszeit, Maximale garantierte Reaktionszeit, Kürzeste Gesamtausführungszeit, Minimale durchschnittliche Wartezeit.
Unterschied: Präemptives vs. Nicht-Präemptives Scheduling?
Nicht-Präemptiv: Prozess gibt CPU freiwillig auf (z.B. bei I/O). Nachteil: Denial-of-Service möglich (z.B. Win 3.1).
Präemptiv: Scheduler unterbricht Prozess aktiv. Vorteil: Einfachere Programmierung, gerechtere Verteilung (z.B. Linux, Windows NT).
Wie funktioniert 'First Come, First Serve' (FCFS) Scheduling?
Prozesse werden in der Eingangsreihenfolge abgearbeitet. Nachteil: Durchschnittliche Wartezeit stark von Reihenfolge abhängig.
Wie funktioniert 'Shortest Job First' (SJF) Scheduling?
Der Prozess mit der kürzesten geschätzten Laufzeit wird als nächstes ausgeführt. Führt zumeist zu geringerer durchschnittlicher Wartezeit als FCFS.
Wie funktioniert 'Round-Robin' Scheduling?
Prozesse werden in einer FIFO-Liste (Queue) geführt. Jeder Prozess bekommt eine feste Zeitscheibe (Quantum).
Vorteil: Einfach, O(1) Auswahl, Fair.
Nachteil: Hoher Scheduler-Overhead bei kleinem Quantum.
Was ist der Nachteil von einfachem prioritätsgesteuertem Scheduling?
Prozesse niedrigerer Priorität werden eventuell nie ausgeführt (Starvation).
Was ist die Idee des 'Completely Fair Scheduler' (CFS) in Linux?
Jeder Prozess soll fair behandelt werden. Nutzt eine 'virtuelle Laufzeit' (vruntime). Der Prozess mit der niedrigsten vruntime wird als nächstes ausgeführt. Implementiert mit einem Red-Black Tree (O(log n)).
Was bedeutet 'Echtzeit-Scheduling'?
Strikte Einhaltung von maximalen Zeitschranken (Deadlines), z.B. für Industrieroboter.
Was ist ein 'Prozess-Kontext'?
Alle Daten, die gespeichert werden müssen, um einen Prozess zu pausieren und später fortzusetzen. Z.B.: Register (EAX, EBX...), Programm-Zähler, Stack-Zeiger, Offene Dateien, MMU-Konfiguration.
Wie löst der Scheduler einen Prozess-Wechsel aus (präemptiv)?
Über einen Timer-Interrupt in einem fixen Zeitintervall, der vom Prozessor ausgelöst wird und den Scheduler aufruft.