Einheit 6: Fortgeschrittene Scheduler
Lernziele
Funktionsweise realer Scheduler kennen lernen
I/O und Overlapping
Wir haben zwei Typen von Schedulern kennen gelernt
SJF/STCF optimiert Turnaround-Zeiten, ist jedoch ungĂŒnstig fĂŒr Antwortzeiten
RR optimiert die Antwortzeit, ist aber ungĂŒnstig fĂŒr die Turnaround-Zeit
Es gibt auf Basis des vorangehenden Abschnitts noch zwei Annahmen/Restriktionen, die »aufgelöst« werden mĂŒssen
Alle Jobs verwenden ausschlieĂlich die CPU
Laufzeit eines jedes Jobs ist bekannt
Input/Output
Lösen wir daher die nÀchste Restriktion: Ab sofort können Jobs auch I/O-Operationen aufrufen
Scheduler muss nun entscheiden wann eine I/O-Operation durchgefĂŒhrt wird, da in der Zeit der laufende Prozess die CPU nicht nutzen kann und sich somit im Status »blocked« befindet
Scheduler kann demnach in dieser Zeit einen anderen Job laufen lassen
Ist die I/O-Operation fertig (wird ĂŒber Interrupt angezeigt), wird der zuvor geblockte Job wieder auf »ready« gesetzt
Ab jetzt kann er Job potentiell wieder la
Overlapping
Schlechte Ressourcen-Nutzung
Bessere Ressourcen-Nutzung dank Overlapping
Prozessdauer
In Wirklichkeit haben wir kein Wissen ĂŒber Prozessdauer
Als letzte Restriktion lösen wir nun die Kenntnisse ĂŒber die Prozesslaufzeit auf
D.h. der Scheduler weiĂ nichts ĂŒber die Restlaufzeit eines Prozesses
Wie kann dann sinnvoll gescheduled werden?
Zuletzt lassen wir daher die Annahme fallen, dass wir die Laufzeit eines Prozesses im Vorhinein wissen
Wie kann ohne diese Kenntnisse ein Scheduler gebaut werden, er sowohl Antwortzeiten (z.B. fĂŒr interaktive Anwendungen) als auch die Turnaround-Zeiten (d.h. ein Job möglichst schnell fertig stellen) ohne Wissen ĂŒber die Laufzeit eines Prozesses minimiert?
Lösungsidee: sog. »Multi-Level Feedback Queue«-AnsĂ€tze verwenden die nahe Vergangenheit, um die Zukunft vorauszusagen! đ€©
Multi Level Feedback Queue (MLFQ)
Grundlegende Regeln
MLFQ hat mehrere Queues, jede mit einem PrioritÀts-Level
Jobs mit höherer PrioritÀt laufen zuerst (=höhere Queue)
Falls sich mehrere Jobs in der gleichen Queue befinden gilt:
Regel 1:
If Priority(A) > Priority(B), A runs (B doesnât)
Regel 2:
If Priority(A) == Priority(B), A & B run in Round Robin
Wie wird jedoch die PrioritĂ€t fĂŒr ein Job festgelegt?
PrioritÀt nicht fix, sondern hÀngt vom beobachteten Verhalten des Jobs ab
Wenn die ganze CPU-Zeit auf A und B verteilt wird, wie kommen dann aber C und D zum Zug?
Um die Fragen zu beantworten nÀhern wir uns der Lösung schrittweisen:
1. Versuch - PrioritÀten Àndern
Workload Betrachtung: Mischung aus...
interaktiven Jobs, die kurz laufen, geben CPU schnell wieder frei und
langlaufende Jobs, die die CPU-intensiv in Anspruch nehmen, aber deren Antwortzeit »nicht relevant« ist.
ZusÀtzliche Regeln:
Regel 3: Ein neu eintreffender Job erhÀlt immer die höchste PrioritÀt (oberste Queue)
Regel 4a: Wenn ein Job die gesamte Zeitscheibe aufbraucht, wird seine PrioritÀt herabgestuft (d.h. eine Queue nach unten geschoben)
Regel 4b: Wenn ein Job die CPU vor Ablauf der Zeitscheibe freigibt, bleibt er auf der gleichen PrioritÀt (d.h. bleibt in der aktuellen Queue)
Beispiel 1: Ein langlaufender Job
Job lÀuft immer bis ans Ende der Time Slice
Nach jeder Time Slice wird der Job heruntergestuft
Am Ende lÀuft der Job auf der niedrigsten PrioritÀt
Beispiel 2: Ein zusÀtzlicher »KurzlÀufer«
Bei đ=100 trifft ein zweiter, kurzlaufender Job ein
MLFQ trifft immer die Annahme, dass ein neuer Job ein »KurzlÀufer« ist
Mischung aus I/O-intensivem und CPU-intensivem Job
Nach Regel 4 bleibt der Job, der die CPU schnell freigibt, weil er z.B. auf die Tastatur wartet, hoch priorisiert
Wer sieht denn das Problem?
Game the Scheduler
Programm so schreiben, dass es kurz vor Ablauf der Zeitscheibe einen Dateizugriff ausfĂŒhrt (die Datei selbst ist uns komplett egal)
Programm bleibt hoch priorisiert, da Zeitscheibe nicht vollstÀndig aufgebraucht
Machen wir das immer bei â 99% der Zeitscheibe, könnten wir die CPU 99% ĂŒbernehmen
Langlaufende Jobs bleiben auf der Strecke (engl. starvation)
Job A kommt nie mehr in eine bessere Queue, selbst wenn sich sein Verhalten Àndert
Wie könnten wir das besser machen?
Versuch 2: Priority Boost
Neue Regel
Regel 5: Nach definierten Zeit s werden alle Jobs wieder in die oberste Queue verschoben
Regel 5 löst zwei Probleme
Prozesse laufen nicht mehr Gefahr der »Starvation«
Wenn ein Job »plötzlich« interaktiv wĂŒrde, kann er entsprechend priorisiert werden (s. folgende Seiten)
Voodoo Constant
Spannende Frage: Wie lange sollte die Zeitspanne s sein?
Der Wert s heiĂt nach John Ousterhout »Voodoo Constant«.
FĂŒr die Bestimmung sog. Voodoo-Konstanten benötigt das System etwas »schwarze Magie« zu deren Bestimmung
Dilemma: Wenn s zu groĂ gewĂ€hlt wird, können CPU-intensive Jobs doch verhungern, ist sie zu klein gewĂ€hlt bekommen interaktive Jobs nicht genĂŒgend CPU
Generell sollten Voodoo-Konstanten vermieden werden (Ousterhout's Law)
Versuch 3: Verbesserte BuchfĂŒhrung
Problem: Regel 4a und 4b ermöglichen immer noch, dass der Scheduler ausgespielt wird
Lösungsidee: Eine verbesserte BuchfĂŒhrung
Merken wie viel Zeit ein Prozess in einer Queue verbracht hat
Sobald ein Prozess kumuliert eine Zeitscheibe aufgebraucht hat, wandert er eine Queue nach unten
Aus den Regeln 4a und 4b wird
Regel 4: Sobald ein Job seine gesamte Zeit auf einer PrioritĂ€tsebene genutzte hat (ungeachtet dessen, wie viel Zeit er der CPU »zurĂŒck gibt«), wird seine PrioritĂ€t reduziert (d.h. er wandert eine Queue nach unten).
Tuning und MLFQ Probleme
Wie sollte MLFQ priorisiert werden?
Wie viele Queues
Wie groĂ sollte die Zeitspanne (engl. time slice) pro Queue sein?
Machen unterschiedliche Time Slices pro Queue Sinn?
Wie oft findet Priority Boost statt?
MLFQ Regeln
R 1: If Priority(A) > Priority(B), A runs (B doesnât)
R 2: If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
R 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
R 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).
R 5: After some time period s, move all the jobs in the system to the topmost queue.
Wird MLFQ ĂŒberhaupt irgendwo verwendet?
Solaris
MLFQ Time-Sharing Scheduling Class wird ĂŒber eine Reihe von Tabellen konfiguriert
Diese können durch einen Admin angepasst werden đ±
60 Queues, mit langsam steigenden Time Slices von 20 ms bis zu 1 Sekunde
FreeBSD
Scheduler nutzt Formel um PrioritÀt eines Jobs zu berechnen
Wie viel CPU hat der Prozess schon verbraucht + wie ist der Verbrauch abgefallen (sog. Decay-Usage Algorithms)
Lottery Scheduling
Proportional / Fair Share Scheduler
Anstelle Turnaround-Zeiten zu optimieren, versuchen Fair Share Scheduler sicherzustellen, dass jeder Job einen gewissen Prozentsatz der CPU-Ressourcen erhÀlt
Beispiel: Lottery Scheduling
Grundidee: Es werden Tickets vergeben, die wie in einer Lotterie gezogen werden
Prozesse, die öfters laufen sollen, erhalten schlicht mehr LotterieloseâŠ
Grundkonzept: Tickets represent your share
Grundlegendes Konzept: Es werden Tickets vergeben (entsprechen einem CPU Share)
Beispiel:
Job A erhÀlt 75% der Tickets (hier: Lose 0..74)
Job B erhÀlt 25% der Tickets (hier: Lose 75..99)
Scheduler muss nun wissen, wie viele Lose es insgesamt gibt (hier: 100)
Gewinnerticket gibt an, welcher Prozess lÀuft
Lottery Scheduler - Ăberlegungen
Statistische AnnĂ€herung an gewĂŒnschte Aufteilung
Je lÀnger die Jobs laufen, desto besser ist die AnnÀherung
Was ist bei einer Verteilung 99% zu 1%?
Man benötigt einen guten Zufallsgenerator
Was macht man wenn ein neuer Job dazu kommt?
Ticket WĂ€hrung
User mit mehreren Tickets, kann diese einer eigene »WÀhrung« zuordnen
Beispiel
A und B haben je 100 Tickets
A hat zwei Jobs, A1 und A2, jeder Job bekommt 500 (von insg. 1.000) User Tickets in Aâs WĂ€hrung
B hat 1 Job B1, dieser bekommt 10 von 10 (User Tickets) in Bâs WĂ€hrung
System konvertiert Aâs Tickets pro Job zu je 50 Tickets in der SystemwĂ€hrung
System konvertiert Bâs Ticktes zu 100 Tickets in SystemwĂ€hrung
Linux Completely Fair Scheduler (CFS)
Problem: Scheduling kann bis zu 5% der CPU-Ressource ausmachen
CFS fĂŒhrt eine virtual runtime (vruntime) ein
Jeder Prozess, der lÀuft, sammelt vruntime an Bei Scheduling-Entscheidung wÀhlt der Scheduler den Prozess mit der geringsten vruntime aus
CFS: Wie oft sollte ein Prozess gewechselt werden?
sched_latency
Time Slice Dauer, typischerweise 48ms
Wird durch Anzahl der Prozesse n geteilt
Ergibt die Zeitscheibe pro Prozess
Somit ist die Zeitverteilung vollstÀndig fair
min_granularity
Mindestdauer, typischerweise 6ms
Dieser Wert wird niemals unterschritten (Bsp. 10 Prozesse ergÀbe 4,8ms pro Prozess)
CFS - Beispiel
CFS nutzt regelmĂ€Ăige Timer Interrupts, der Scheduler kann Entscheidungen also immer nur zu fixen Zeitpunkten treffen
Vier Jobs (A,B,C,D), wobei B, C und D kurz nach A eintreffen
Nach der ersten Zeitscheibe wird einer der Jobs aus (B,C,D) gewÀhlt da hier vruntime von B, C und D < vruntime von A
Nach t = 100 sind C und D fertig, danach wird die vruntime zwischen A und B aufgeteilt
CFS - Weighting / Niceness
CFS ermöglicht die Angabe von PrioritÀten, damit Prozesse mehr CPU-Ressourcen erhalten können.
In UNIX entspricht das dem »nice level«
Kann zwischen -20 und + 19 gesetzt werden
0 ist Standardwert
< 0 höhere Prio, > 0 kleinere Prio
CFS: Zeitscheibe berechnen
Gewichtungen erlauben es die Zeitscheibe pro Prozess zu berechnen:
Beispiel:
2 Prozesse A (Prio=-5), B (Prio=0)
đ€đđđâđĄđŽ = 3121, đ€đđđâđĄđ”=1024
A erhÀlt 36ms, B erhÀlt 12ms
CFS: vruntime berechnen
Hinweis:
Gewichtung bleibt im VerhÀltnis gleich, wenn andere PrioritÀten gewÀhlt werden
Annahme A hat 5 und B hat 10
A und B werden noch im selben VerhÀltnis wie zuvor gescheduled
CFS Prozesslisten
Problem: Bei mehreren hundert oder gar 1.000 Prozessen, wie wird der nÀchste Prozess gefunden?
Kurzes Gedankenspiel: Skalieren Listen? Hier mĂŒssten man immer aller linear durchsuchen, was in einem linearen Aufwand von đ(đ) resultiert.
Lösung: Geschickte Wahl der Datenstruktur:
CFS speichert Prozesse in Rot-Schwarz-BĂ€umen (ausgeglichener Baum)
Algorithmen auf Rot-Schwarz-BĂ€umen sind logarithmisch mit einem Aufwand von đ(lđđđ)
Deswegen: Algorithmen und Datenstrukturen
Am Beispiel des CFS sieht man, dass die Wahl einer geeigneten Datenstruktur eine signifikante Auswirkung auf ein System haben kann. Deswegen macht es durchaus Sinn, sich mit dem Thema Algorithmen und Datenstrukturen in SEB3 auseinanderzusetzen.
CFS und I/O
Was passiert eigentlich wenn ein Prozess A permanent lÀuft, weil B aufgrund einer I/O-Operation blockiert (z.B. 10s)?
B wacht auf und hat die niedrigste vruntime (10s kleiner als bei A)
B wĂŒrde nun die CPU fĂŒr 10s monopolisieren, »Starvation« von A wĂ€re potentiell möglich
Lösung: CFS setzt die vruntime zurĂŒck
Sobald ein Job aufwacht, erhÀlt er den Minimum Wert im Baum (Liste aller laufende Jobs)
»Starvation« wird vermieden
Nachteil: Jobs, die nur kurz schlafen, bekommen hierdurch keinen fairen Anteil
Hausaufgabe
Machen Sie sich mit dem Befehl nice
(Linux) und start
(Windows) vertraut
Last updated