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

Beispiel 3: ZusƤtzliche I/O

  • 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

PreviousExercise: SchedulerNextFortgeschrittene Speicherverwaltung

Last updated