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

    1. Alle Jobs verwenden ausschließlich die CPU

    2. 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:

time_sclicek=weightk∑i=0nweighti⋅sched_latencytime\_sclice_k = \frac{weight_k}{\sum\limits_{i=0}^{n}weight_i}\cdot sched\_latency
  • Beispiel:

    • 2 Prozesse A (Prio=-5), B (Prio=0)

    • đ‘€đ‘’đ‘–đ‘”â„Žđ‘ĄđŽ = 3121, đ‘€đ‘’đ‘–đ‘”â„Žđ‘Ąđ”=1024

    • A erhĂ€lt 36ms, B erhĂ€lt 12ms

CFS: vruntime berechnen

vruntimei=vruntime⋅weight0weighti⋅runtimeivruntime_i = vruntime\cdot \frac{weight_0}{weight_i} \cdot runtime_i
  • 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