Systeme 1
Kapitel 5Scheduling
WS 2009/10 1
Scheduling• Verteilung und Zuweisung von begrenzten
Ressourcen an konkurrierende ProzesseZeitablaufsteuerung
• Beispiel:– Zwei Prozesse zur gleichen Zeit rechenbereit auf
einem Ein-Prozessor System.– Betriebssystem muss entscheiden, welcher Prozess
als Nächstes läuft.Scheduler
– Entscheidung auf Grund eines Schedulingalgorithmus• Ziel: optimale! Verteilung
WS 2009/10 2
Optimierungsziele• Mehrere verschiedene Optimierungsziele denkbar
Verschiedene Scheduling-Algorithmen• Optimierungsziele
– Alle Systeme• Fairness (“jeder Prozess erhält die CPU”)• Effizienz
– Stapelverarbeitungssysteme• Maximiere mittleren Durchsatz (Anzahl Jobs pro Zeiteinheit)• Minimiere mittlere Durchlaufzeit (Zeit von Prozessstart bis Prozessbeendigung)• Maximiere CPU-Auslastung• Bemerkung: Maximierung des mittleren Durchsatzes und Minimierung der
mittleren Durchlaufzeit sind nicht dasselbe!– Interaktive Systeme
• Minimiere Antwortzeit– Echtzeit-Systeme
• Einhalten von Deadlines
WS 2009/10 3
Beispiel: Feste Prioritäten
• Prozess mit der höchsten Priorität erhält CPU• Problem: Livelock für Prozesse mit geringer Priorität– Fairness nicht garantiert!
WS 2009/10 4
Schedulingalgorithmen: Charakteristika
• Prozessauswahl:– Bestimmt nächsten Prozess für CPU-Zuteilung– Basierend auf Ressourcenbenutzung, Prioritäten, …– Insbesondere:
• w (Wartezeit auf CPU)• e (bisher verbrauchte CPU-Zeit)• s (insgesamt benötigte CPU-Zeit)
• Zeitpunkt der Auswahlentscheidung:– Nicht-präemptives Scheduling:
• CPU kann einem Prozess nur entzogen werden, wenn er beendet ist, oder auf Ein-/Ausgaben wartet.
– Präemptives Scheduling :• Aktueller Prozess kann unterbrochen werden durch sog. Interrupts.
WS 2009/10 5
First Come First Served (FCFS)• Nicht-präemptiv• Strategie:
Wenn ein Prozess beendet ist oder blockiert, kommt der Prozess an die Reihe, der schon am längsten wartet.
• Analyse :– FCFS begünstigt lange Prozesse, kurze Prozesse können
durch lange Prozesse stark verzögert werden.– FCFS begünstigt Prozesse ohne Ein-/Ausgabe (die den
Prozessor vor Beendigung nicht abgeben).
FCTS alleine nicht sehr interessant.
WS 2009/10 6
Shortest Job First (SJF)
• Nicht-präemptiv• Strategie: – Benutzt Abschätzungen der Gesamtlaufzeit von
Prozessen. – Prozess mit kürzester geschätzter Laufzeit erhält
CPU als erstes. Minimiert durchschnittliche Durchlaufzeit
= durchschnittliche Wartezeit
WS 2009/10 7
Shortest Job First (SJF) - Beispiel• Prozesse A, B, C, D– Laufzeit von A = 8 Min. und Laufzeit von B, C, D = 4 Min.– Alle Prozesse gleichzeitig rechenbereit
• Variante 1: – Reihenfolge A, B, C, D– Wartezeit bis Prozess beendet:
• A = 8 Min., B = 12 Min., C = 16 Min., D = 20 Min.• Durchschnittliche Wartezeit 14 Min.
• Variante 2: SJF – Reihenfolge B, C, D, A– Wartezeit: B = 4 Min., C = 8 Min., D = 12 Min., A = 20 Min.
• Durchschnittliche Wartezeit 11 Min.
WS 2009/10 8
Shortest Job First (SJF)• Allgemein:
Prozess 1: Laufzeit t1, Wartezeit t1Prozess 2: Laufzeit t2, Wartezeit t1+ t2......Prozess N: Laufzeit tn, Wartezeit t1+ t2 +…+ tn
=> durchschnittliche Durchlaufzeit:
D.h. kürzeste durchschnittliche Durchlaufzeit, wenn t1 bis tn aufsteigend nach Laufzeit sortiert.
WS 2009/10 9
Shortest Job First (SJF)
• Analyse– SJF begünstigt kurze Prozesse.– Antwortzeit für lange Prozesse variiert stark in
Abhängigkeit von der Zahl der kürzeren Jobs. – Livelock für lange Prozesse möglich.– Problem : Wie erhält man Abschätzungen der
Gesamtlaufzeit von Prozessen?SJF nicht geeignet für Allzweck-OS.Eher für Stapelverarbeitungssysteme
(Mainframes).
WS 2009/10 10
Shortest Remaining Time (SRT)• Präemptiv• Strategie: – Benutzt Abschätzungen der Restlaufzeiten von
Prozessen. – Prozess mit kürzester geschätzter Restlaufzeit erhält
CPU. – Keine Unterbrechungen laufender Prozesse durch
Timer. Auswertung der Restlaufzeiten nur, wenn ein neuer Prozess gestartet wird.
• Analyse:– Ähnliche Probleme wie SJF.
WS 2009/10 11
Highest Response Ration Next (HRRN)
• Nicht-präemptiv• Strategie:
– Basiert auf • rt = geschätzte Laufzeit eines Prozesses• wt = Wartezeit eines Prozesses (bisher angesammelte Wartezeit)• “Response ratio” rr = (rt + wt) / rt• Ein Prozess startet mit rr = 1.0.
– Der Prozess mit der höchsten response ratio rr erhält die CPU als erster.
• Analyse:– Für kurze Prozesse wächst rr schnell an.– HRRN begünstigt kurze Prozesse (wie SJF und SRT).– Aber: Keine Livelocks für längere Prozesse.– Ähnliches Problem wie SJF, SRT: Laufzeitabschätzungen
benötigt.WS 2009/10 12
Round Robin (RR)• Präemptiv• Strategie:
– Scheduler wird nach Ablauf fester Zeitintervalle immer wieder (periodisch) aktiviert (“Zeitscheiben”, „Quanten“).• Quantum bei realen Systemen ~ 20-100 ms
– Laufender Prozess wird dann in eine Warteschlange wartender Prozesse eingefügt.
– Der am längsten wartende Prozess wird aktiviert.• Analyse:
– Länge der Zeitscheiben ist essentiell • Zu kurz: Overhead durch viele Prozesswechsel• Zu lang: Ähnlich FCFS
– RR begünstigt Prozesse ohne Ein-/Ausgabe etwas. – Prozesse mit Ein-/Ausgabe geben CPU ab, bevor ihre Zeitscheibe
abgelaufen ist, erhalten dafür aber keine “Gutschrift”.WS 2009/10 13
Feedback
• Präemptiv• Problem: – Laufzeitberechnung nur ganz selten möglich.
• Idee:– Nutze bereits verbrauchte CPU Zeit als Kriterium.
• Strategie:– Muss ein Prozess die CPU abgeben wird er in eine
Warteschlange niederer Priorität eingefügt.– Da die Zeitintervalle eine feste Größe haben,
modellieren Warteschlangen verschiedener Prioritäten verbrauchte CPU-Zeit.
WS 2009/10 14
Feedback
• Alle Warteschlangen FCFS, letzte Warteschlange RR.WS 2009/10 15
Feedback
• Analyse– Prozesse, die in der Vergangenheit viel CPU Zeit
verbraucht haben, werden bestraft.– Lange Jobs werden bestraft (können „verhungern“).
• Abhilfe:– Wechseln von niedrigster Priorität zurück in die höchste.– Neuberechnung der Priorität in gewissen Zeitabstände unter
Einbeziehen von Wartezeit etc....
Feedback-Scheduling wird in modifizierter Form auf verschiedenen UNIX Systemen eingesetzt.
WS 2009/10 16
Garantiertes Scheduling• Strategie– Gebe Benutzern / Prozessen Garantien, die einzuhalten
sind.– n Prozesse gleicher Priorität:
• jedem wird 1/n der CPU versprochen– Dynamische Priorität =
(garantierte Zeit) / (tatsächlich verbrauchte Zeit) , – Wobei
garantierte Zeit = (Zeit seit Prozesserzeugung) / n– Bediene Prozesse in Reihenfolge fallender Priorität.
• Hier: Gleichbehandlung, keine Unterscheidung zwischen CPU-lastigen und interaktiven Prozessen.
WS 2009/10 17
Lotterie Scheduling
(Waldspurger, Weihl, 1994)• CPU-Zeit wird in regelmäßigen Abständen verlost.• Wichtige Prozesse haben mehr Lose als andere.• Weitergabe von Losen zwischen kooperierenden
Prozessen ist möglich.
Ähnlich vorhersagbarer CPU-Anteil wie bei „Garantiertem Scheduling“.
Einfachere ImplementierungWS 2009/10 18
Zusammenfassung
• Es gibt viele verschiedene Scheduling-Strategien.• Qualität verschiedener Ansätze hängt ab von
Anwendung / Anforderung.• Exakter Vergleich schwierig, da meistens
Kostenfunktion / genaue Ziele des Scheduling nicht formal spezifiziert sind.
• Meist Analyse durch Simulationen.
• Analytische Methoden: WarteschlangentheorieWS 2009/10 19