CPU-Scheduling
von D.F.
von D.F.
Was ist die generelle Aufgabe eines Schedulers?
Verwalten de verfügbaren CPU Kapazität, in dem er verschidenen Porzessen die Möglichkeit die CPU zu nutzen einräumt und entzieht.
Bei der zeitlichen Anordnung verschiedener Prozesse sind verschiedene Interessen zu berücksichtigen, nenne diese und beschreibe sie?
(6 Punkte)
- Fairness => Kein Prozess solte benachteiligt werden, gleiche Verteilung von Ressourcen
- Wirkungsgrad => Anteil der CPU-Zyklen, welche Produktiv genutzt werden (Also nicht für den Prozesswechsel oder Scheduler)
- Response-Zeit => Wie lange dauert es bis ein Prozess erneut an der reihe ist
- Turn-Arount-Zeit => Dauer der Festigstellung eines Prozess (v.a. Batch)
- Durchsatz => Erfüllen einer bestimmten Menge pro Zeit => Multimedial (60 Bilder/sec)
Beschreibe die Funktion des Zeitscheibenverfahrens bzw. Round-Robin?
Jeder laufbereite Prozess bekommt jeweils eine "Zeitscheibe" (einen Teil) der CPU Zeit.
Das Betriebsystem überprüft regelmäßig ob die Zeitscheibe des Prozess zuende ist. Ist dies der fall wird, auch wenn dieser Prozess nocht laufbereit ist, dem nächsten Prozess die CPU zugeteilt, dies nennt man Präemptives Scheduling (engl. preemptive multitasking).
Beendet sich ein Prozess selbständig, währen seine Zeitscheibe noch nicht zuende ist, wird der nachste Prozess gestartet.
Was passiert wenn die "Zeitscheiben" zu lange bzw. zu kurz sind?
Zu kurze Zeitscheiben: Der Wechsel zwischen Pozessen benötigt für das bereitstellen der Umgebung des neuen Prozesses eine gewisse Zeit (Overhead). Bedingt durch kurze Zeitscheiben gibt es viele Prozesswechsel was zu einem großen Overhead führt, durch welchen die CPU uneffizient genutzt wird.
Zu lange Zeitscheiben: Durch die geringere Anzahl der Wechsel zwischen den Prozessen ist der Overhead deutlich geringer dementsprechend wird auch die CPU deutlich effiienter genutzt. Allerdings wird die Antwortzeit eines Prozess dadurch erheblich länger. Was vorallem bei Interaktiven Prozessen zu problemen führen kann, wenn der Nutzer auf die Reaktion des Systems warten muss.
Das Ziel ist es ein möglichst gutes Gleichgewicht zwischen einem geringen Overhead und akzeptablen Antwortzeiten zu finden.
Wie funktioniert das Priority Scheduling?
- Prozesse haben unterschiedliche Prioritäten
- Ein höher priorisierter Prozess verhindert die Ausführung eines niedriger priorisierten Prozesses
- Um niedrig priorisierten Prozessen eine Chance zu geben, wird die Priorität eines laufenden Prozesses kontinuierlich reduziert
- Innerhalb einer Prioritätsebene werden Jobs nach dem Round-Robin-Verfahren abgearbeitet
Wie funktionieren Multiple Queues, für welche systeme sind sie interessant?
Multiple Queues sind vorallem für Batch Systeme interessant.
Alle Prozesse erhalten zuerst eine Zeitscheibe, sind sie nach dieser noch nicht fertig erhalten sie 2n Zeitscheiben ( n Nummer des Aufrufs durch den Scheduler). Dies wiederholt sich so lange bis der Prozess erledigt ist.
Fazit: lang laufende Prozesse werden seltener gewechselt (Reduktion des Overheads)
Wie funktioniert das Shortest Job First Scheduling?
- Von allen zur Auswahl stehenden Prozessen wird der vermutlich am kürzesten laufende ausgeführt
- Bei interaktiven Prozessen nicht realistisch, da die Prozesse sehr lange laufen und kein bestimmtes Ende haben
- Im Batch-Betrieb üblich, um die Turn-Around-Zeiten kleiner Jobs zu reduzieren
- Ideal für Batch Systeme
- In Quingsystemen wird teilweise die maximale Zeit des Skriptes vom Benutzer festgelegt
Wie funktioniert das Two-Level-Scheduling?
(5 Punkte)
- Anwendbar, wenn z.B. Prozesse teilweise auf Platte ausgelagert sind
- Zweistufiges Scheduling
- Nur Prozesse im Hauptspeicher können ausgeführt werden
- Low-Level Scheduler wählt nur unter diesen Prozesse aus
- High-Level-Scheduler wählt die Prozesse aus, die in den Hauptspeicher geladen bzw. ausgelagert weden
Was sind die Ziele des Linux Scheduling, nenne 3 Scheduler?
- Ziele
- Fairness
- Flüssiges Antwortverhalten von interaktiven Prozessen
- Kein Prozess soll "ewig" warten müssen
- Effiziente nutzung der CPU wenig Overhead
- Scheduler
- O(n) Scheduler (Kernel Version 2.4)
- O(1) Scheduler (Kernel Version <= 2.6.22)
- Completely Fair Scheduler (CFS) (Kernel Version >= 2.6.23) Aktueller Scheduler!
Wie funktioniert ein O(n) Scheduler Prinzipiell, bescheibe
- die 3 Scheduling Klassen
- Objekte des Scheduling
- Scheduling Priorität
- Die Drei Scheduling Klassen
- Real-Time FIFO => Nicht unterbrechbar
- Real-Time Round Robin => unterbrechbar, nur vom Timer
- Timesharing => normale Prozesse
- Objekte des Scheduling
- Die Objekte des Scheduling sind Threads
- Scheduling-Priorität (höherer Wert, höhere Priorität)
- Standard-Wert 20
- Kann durch einen "nice-Wert" zwischen -20 und 19 verändert werden (Befehle nice und renice)
Wie wird beim O(n) Scheduler die Länge der Zeitscheibe berechnet?
Quntum = Restquantum / 2 + Priorität
(Durch die Berucksichtigung des Restquantums werden Interaktive Prozesse bevorzugt)
Wie wird die Goodness beim O(n) Scheluder berechnet?
Beschreibe die tatsächliche funktionsweise des O(n) Schedulers?
- Der Scheduler durchsucht regelmäßig die Runqueue nach dem Thread mit der größten "goodness", der dann zum Zug kommt
- Ein laufender Thread wird unterbrochen wenn
- er sein Quantum verbraucht hat (Wird pro Tick um eins reduziert)
- er blockiert (I/O, Semaphor, ...)
- ein anderer Prozess mit höherer goodness bereit steht. (Preemption)
- Fazit
- CPU-Zeit eines Prozesses ist i.W. proportional zu seiner Priorität
- Interaktive Prozesse werden bevorzugt (Anrechnung von Restquanta)
- Aufwand für den Scheduler O(n) => Aufand proportional zur Anzahl der verwalteten Therads
- Multicore-CPUs nur unzureichend unterstützt
Nenne die Besonderheiten des O(1) im vergleich zum O(n) Schedulers?
(3 Punkte)
- Aufwand des Schedulers ist unabhäning von der Anzahl der lauffähigen Threads ( O(1) )
- Separate Run-Queues
- für jeden Prozessor (Bessere Unterstüzung von Multiprozessorsystemen)
- für jede Prioritätsebene
- Verändertes Berechnungsschema für die Quantum Länge
- Jiffies können jetzt 10ms (für Server) oder 1ms (für Interaktive Multimediale Systeme) sein
- Aufwändige Heuristiken zur Bestimmung der Interaktivität von Threads
Wie sind die möglichen Prioritäten beim O(1) Scheduler aufgebaut, in welchem bereich befinden sich Echtzeit / Standard Prozesse? Welche Zahl ist mit einer hohen Priorität verknüpft?
- Realtime: 0-99
- Standard: 100-139
Wie läuft das Scheduling beim O(1) Scheduler ab?
- Welche Threads werden ausgeführt?
- Was passiert wenn das Quantum eines Threads verbraucht ist?
- Was passiert wenn alle "active" Runqueues abgearbeitet sind?
- Suche die höchste Priorität, zu der ein Thread in der zugehörigen active-Runqueue verfügbar ist (ist durch die Bitmap einfach zu erledingen)
- Führt den Thread aus. Wenn das Quantum aufgebraucht ist
- Hänge interaktive Threads wieder an das Ende der "active" Queue an
- Hänge nicht-interaktive Threads an das Ende der "expired" Queue an
- Wenn alle "active" Runqueues abgearbeitet sind
- werden "active" und "expired" Runqueues vertauscht
- Für alle Prozesse werden Dynamische Priorität und Quantum neu berechnet
Wie wird das Quantum beim O(1) Scheduler berechnet?
- Wie wir die Dynamische Priorität berechnet?
- Dynamische Priorität
- Statische Priorität + sleep time
- Es wird ein Bonus [0,10] berechnet, der den Anteil der CPU-Zeit angibt, die der Prozess in letzter Zeit schlafend zugebracht hat
- DP=max(100,min(SP-Bonus+5,139)
Nenne die Besonderheiten des Completely Fair Scheduler (CFS)?
(3 Punkte)
- Wesentlich schlanker als der O(1) Scheduler
- Unterstützt Timesharing-Threads
- Realtime-Threads nutzen weiterhin
- FIFO Scheduling => nicht unterbrechbar
- Round Robin Scheduling => nur vom Timer unterbrechbar
Wie Funktioniert der Completely Fair Scheduler?
- Wie viel CPU-Zeit erhalten die Threads?
- Welcher Thread wird als nächstes ausgeführt?
- Wie werden die Thread-Informationen gespeichert?
- Jeder Thread soll im Mittel einen fairen Anteil an der CPU-Zeit erhalten
- z.B. bei 4 Threads 25%
- aktiver Thread bekommt mehr als ihm zusteht
- interaktiver Thread bekommt weniger als ihm zusteht
- Für jeden Thread wird eine Variable vruntime angelegt in der die virtuelle CPU-Zeit auf Nanosekunden-Zeit gespeichert ist
- Keine Zeitscheiben, keine klassischen Prioritäten
- Priorität/Nice-Wert beschreibt eine "Zerfallskonstante" der Zeit, die ein Thread ausgeführt werden darf
- Als nächstes wird immer der Thread ausgewählt, der am weitesten vom Gleichgewicht entfernt ist (kleinster Wert von vruntime)
- Keine Heuristiken zur Interaktivität von Threads
- Speicherung von Thread-Informationen in einem balancierten Binärbaum (Red-Black-Baum), sortiert nach vruntime-Wert
- Threads können auch in Gruppen behandelt werden
-
- 1 / 19
-
Flashcards
Was ist die generelle Aufgabe eines Schedulers?
Verwalten de verfügbaren CPU Kapazität, in dem er verschidenen Porzessen die Möglichkeit die CPU zu nutzen einräumt und entzieht.
Bei der zeitlichen Anordnung verschiedener Prozesse sind verschiedene Interessen zu berücksichtigen, nenne diese und beschreibe sie?
(6 Punkte)
- Fairness => Kein Prozess solte benachteiligt werden, gleiche Verteilung von Ressourcen
- Wirkungsgrad => Anteil der CPU-Zyklen, welche Produktiv genutzt werden (Also nicht für den Prozesswechsel oder Scheduler)
- Response-Zeit => Wie lange dauert es bis ein Prozess erneut an der reihe ist
- Turn-Arount-Zeit => Dauer der Festigstellung eines Prozess (v.a. Batch)
- Durchsatz => Erfüllen einer bestimmten Menge pro Zeit => Multimedial (60 Bilder/sec)
Beschreibe die Funktion des Zeitscheibenverfahrens bzw. Round-Robin?
Jeder laufbereite Prozess bekommt jeweils eine "Zeitscheibe" (einen Teil) der CPU Zeit.
Das Betriebsystem überprüft regelmäßig ob die Zeitscheibe des Prozess zuende ist. Ist dies der fall wird, auch wenn dieser Prozess nocht laufbereit ist, dem nächsten Prozess die CPU zugeteilt, dies nennt man Präemptives Scheduling (engl. preemptive multitasking).
Beendet sich ein Prozess selbständig, währen seine Zeitscheibe noch nicht zuende ist, wird der nachste Prozess gestartet.
Was passiert wenn die "Zeitscheiben" zu lange bzw. zu kurz sind?
Zu kurze Zeitscheiben: Der Wechsel zwischen Pozessen benötigt für das bereitstellen der Umgebung des neuen Prozesses eine gewisse Zeit (Overhead). Bedingt durch kurze Zeitscheiben gibt es viele Prozesswechsel was zu einem großen Overhead führt, durch welchen die CPU uneffizient genutzt wird.
Zu lange Zeitscheiben: Durch die geringere Anzahl der Wechsel zwischen den Prozessen ist der Overhead deutlich geringer dementsprechend wird auch die CPU deutlich effiienter genutzt. Allerdings wird die Antwortzeit eines Prozess dadurch erheblich länger. Was vorallem bei Interaktiven Prozessen zu problemen führen kann, wenn der Nutzer auf die Reaktion des Systems warten muss.
Das Ziel ist es ein möglichst gutes Gleichgewicht zwischen einem geringen Overhead und akzeptablen Antwortzeiten zu finden.
Wie funktioniert das Priority Scheduling?
- Prozesse haben unterschiedliche Prioritäten
- Ein höher priorisierter Prozess verhindert die Ausführung eines niedriger priorisierten Prozesses
- Um niedrig priorisierten Prozessen eine Chance zu geben, wird die Priorität eines laufenden Prozesses kontinuierlich reduziert
- Innerhalb einer Prioritätsebene werden Jobs nach dem Round-Robin-Verfahren abgearbeitet
Wie funktionieren Multiple Queues, für welche systeme sind sie interessant?
Multiple Queues sind vorallem für Batch Systeme interessant.
Alle Prozesse erhalten zuerst eine Zeitscheibe, sind sie nach dieser noch nicht fertig erhalten sie 2n Zeitscheiben ( n Nummer des Aufrufs durch den Scheduler). Dies wiederholt sich so lange bis der Prozess erledigt ist.
Fazit: lang laufende Prozesse werden seltener gewechselt (Reduktion des Overheads)
Wie funktioniert das Shortest Job First Scheduling?
- Von allen zur Auswahl stehenden Prozessen wird der vermutlich am kürzesten laufende ausgeführt
- Bei interaktiven Prozessen nicht realistisch, da die Prozesse sehr lange laufen und kein bestimmtes Ende haben
- Im Batch-Betrieb üblich, um die Turn-Around-Zeiten kleiner Jobs zu reduzieren
- Ideal für Batch Systeme
- In Quingsystemen wird teilweise die maximale Zeit des Skriptes vom Benutzer festgelegt
Wie funktioniert das Two-Level-Scheduling?
(5 Punkte)
- Anwendbar, wenn z.B. Prozesse teilweise auf Platte ausgelagert sind
- Zweistufiges Scheduling
- Nur Prozesse im Hauptspeicher können ausgeführt werden
- Low-Level Scheduler wählt nur unter diesen Prozesse aus
- High-Level-Scheduler wählt die Prozesse aus, die in den Hauptspeicher geladen bzw. ausgelagert weden
Was sind die Ziele des Linux Scheduling, nenne 3 Scheduler?
- Ziele
- Fairness
- Flüssiges Antwortverhalten von interaktiven Prozessen
- Kein Prozess soll "ewig" warten müssen
- Effiziente nutzung der CPU wenig Overhead
- Scheduler
- O(n) Scheduler (Kernel Version 2.4)
- O(1) Scheduler (Kernel Version <= 2.6.22)
- Completely Fair Scheduler (CFS) (Kernel Version >= 2.6.23) Aktueller Scheduler!
Wie funktioniert ein O(n) Scheduler Prinzipiell, bescheibe
- die 3 Scheduling Klassen
- Objekte des Scheduling
- Scheduling Priorität
- Die Drei Scheduling Klassen
- Real-Time FIFO => Nicht unterbrechbar
- Real-Time Round Robin => unterbrechbar, nur vom Timer
- Timesharing => normale Prozesse
- Objekte des Scheduling
- Die Objekte des Scheduling sind Threads
- Scheduling-Priorität (höherer Wert, höhere Priorität)
- Standard-Wert 20
- Kann durch einen "nice-Wert" zwischen -20 und 19 verändert werden (Befehle nice und renice)
Wie wird beim O(n) Scheduler die Länge der Zeitscheibe berechnet?
Quntum = Restquantum / 2 + Priorität
(Durch die Berucksichtigung des Restquantums werden Interaktive Prozesse bevorzugt)
Wie wird die Goodness beim O(n) Scheluder berechnet?
Beschreibe die tatsächliche funktionsweise des O(n) Schedulers?
- Der Scheduler durchsucht regelmäßig die Runqueue nach dem Thread mit der größten "goodness", der dann zum Zug kommt
- Ein laufender Thread wird unterbrochen wenn
- er sein Quantum verbraucht hat (Wird pro Tick um eins reduziert)
- er blockiert (I/O, Semaphor, ...)
- ein anderer Prozess mit höherer goodness bereit steht. (Preemption)
- Fazit
- CPU-Zeit eines Prozesses ist i.W. proportional zu seiner Priorität
- Interaktive Prozesse werden bevorzugt (Anrechnung von Restquanta)
- Aufwand für den Scheduler O(n) => Aufand proportional zur Anzahl der verwalteten Therads
- Multicore-CPUs nur unzureichend unterstützt
Nenne die Besonderheiten des O(1) im vergleich zum O(n) Schedulers?
(3 Punkte)
- Aufwand des Schedulers ist unabhäning von der Anzahl der lauffähigen Threads ( O(1) )
- Separate Run-Queues
- für jeden Prozessor (Bessere Unterstüzung von Multiprozessorsystemen)
- für jede Prioritätsebene
- Verändertes Berechnungsschema für die Quantum Länge
- Jiffies können jetzt 10ms (für Server) oder 1ms (für Interaktive Multimediale Systeme) sein
- Aufwändige Heuristiken zur Bestimmung der Interaktivität von Threads
Wie sind die möglichen Prioritäten beim O(1) Scheduler aufgebaut, in welchem bereich befinden sich Echtzeit / Standard Prozesse? Welche Zahl ist mit einer hohen Priorität verknüpft?
- Realtime: 0-99
- Standard: 100-139
Wie läuft das Scheduling beim O(1) Scheduler ab?
- Welche Threads werden ausgeführt?
- Was passiert wenn das Quantum eines Threads verbraucht ist?
- Was passiert wenn alle "active" Runqueues abgearbeitet sind?
- Suche die höchste Priorität, zu der ein Thread in der zugehörigen active-Runqueue verfügbar ist (ist durch die Bitmap einfach zu erledingen)
- Führt den Thread aus. Wenn das Quantum aufgebraucht ist
- Hänge interaktive Threads wieder an das Ende der "active" Queue an
- Hänge nicht-interaktive Threads an das Ende der "expired" Queue an
- Wenn alle "active" Runqueues abgearbeitet sind
- werden "active" und "expired" Runqueues vertauscht
- Für alle Prozesse werden Dynamische Priorität und Quantum neu berechnet
Wie wird das Quantum beim O(1) Scheduler berechnet?
- Wie wir die Dynamische Priorität berechnet?
- Dynamische Priorität
- Statische Priorität + sleep time
- Es wird ein Bonus [0,10] berechnet, der den Anteil der CPU-Zeit angibt, die der Prozess in letzter Zeit schlafend zugebracht hat
- DP=max(100,min(SP-Bonus+5,139)
Nenne die Besonderheiten des Completely Fair Scheduler (CFS)?
(3 Punkte)
- Wesentlich schlanker als der O(1) Scheduler
- Unterstützt Timesharing-Threads
- Realtime-Threads nutzen weiterhin
- FIFO Scheduling => nicht unterbrechbar
- Round Robin Scheduling => nur vom Timer unterbrechbar
Wie Funktioniert der Completely Fair Scheduler?
- Wie viel CPU-Zeit erhalten die Threads?
- Welcher Thread wird als nächstes ausgeführt?
- Wie werden die Thread-Informationen gespeichert?
- Jeder Thread soll im Mittel einen fairen Anteil an der CPU-Zeit erhalten
- z.B. bei 4 Threads 25%
- aktiver Thread bekommt mehr als ihm zusteht
- interaktiver Thread bekommt weniger als ihm zusteht
- Für jeden Thread wird eine Variable vruntime angelegt in der die virtuelle CPU-Zeit auf Nanosekunden-Zeit gespeichert ist
- Keine Zeitscheiben, keine klassischen Prioritäten
- Priorität/Nice-Wert beschreibt eine "Zerfallskonstante" der Zeit, die ein Thread ausgeführt werden darf
- Als nächstes wird immer der Thread ausgewählt, der am weitesten vom Gleichgewicht entfernt ist (kleinster Wert von vruntime)
- Keine Heuristiken zur Interaktivität von Threads
- Speicherung von Thread-Informationen in einem balancierten Binärbaum (Red-Black-Baum), sortiert nach vruntime-Wert
- Threads können auch in Gruppen behandelt werden
