View
213
Download
0
Category
Preview:
Citation preview
Scheduling
Prof. Dr. Margarita Esponda
Freie Universität Berlin
WS 2011/2012
Prozess-Ablaufplanung
Scheduler
Der Scheduler ist ein besonders wichtiges Programmteil
jedes Betriebssystems.
...
P1 P2 P3 Pn
Prozesse
Scheduler
M. Esponda-Argüero
SchedulingScheduling oder Prozess-Ablaufplanung sind die Schlüssel jedes Mehrprogrammbetriebssystems.
Ziele sind:
- kurze Antwortzeiten
- hoher Durchsatz
- hohe Auslastung der Prozessoren
Zeit zwischen Eingabe und Reaktion
Maximierung der Prozessanzahl pro Zeiteinheit
Maximierung der CPUs-Beschäftigungszeiten
- Einhaltung von DeadlinesInteressant für Echtzeit-Scheduling
- niedriger Durchlaufzeit
Minimierung der Zeit zwischen Prozess-Start und Prozess-Beendigung
M. Esponda-Argüero
SchedulingScheduling-Modelle
- Prozess-basiertes Scheduling
- Thread-basiertes Scheduling
Drei Verarbeitungsumgebungen für Scheduling:
- Stapelverarbeitung - nicht interaktive Programme (häufig bei Großrechnern)
- typisch für Arbeitsplatzrechner und Server
- Multimedia Anwendungen oder Steuerungsaufgaben
- Interaktive Systeme
- Echtzeit-Systeme
- preemptive Scheduling-Algorithmen
- nicht preemptive Scheduling-Algorithmen
Grundlegende Unterteilung
M. Esponda-Argüero
Scheduling
Overhead
Eigentliche Prozess-Umschaltung
Prozess-Entscheidung
Alle Teile des Prozesskontextes, die auf irgendeine Weise beschädigt werden könnten, müssen gespeichert werden.
Hier werden meistens einfache
Algorithmen verwendet.
M. Esponda-Argüero
Scheduling
Zwei Ebenen
long-term Scheduling
short-term Scheduling
Prozesse werden zur weiteren Ausführung aus dem Massenspeicher geholt und im Hauptspeicher wieder geladen.
Aus der Liste der Prozesse, die
ausführungsbereit sind, wird einer
ausgewählt.
"swaping"
M. Esponda-Argüero
SchedulingZwei Ebenen
swap outswap in swapped-out Prozesse
Pb1Pb2Pb3CPU
Ein-/Ausgabe Pio3Pio2Pio1 Pio4
Zeit abgelaufen
End
Wartet auf andere Ereignisse
M. Esponda-Argüero
Dispatcher❖ Das Dispatcher-Modul übergibt die Kontrolle der CPU
an den vom Scheduler ausgewählten Prozess.
Aufgaben:
✴ Kontextwechsel
✴ Umschaltung im Benutzer-Modus
✴ Springt in die Adresse des Prozesses, dessen
Ausführung wieder gestartet werden muss.
❖ Dispatch latency – Zeit zwischen Prozess-Stop und
Prozess-Start
M. Esponda-Argüero
Verschiedene Sorten von Prozessen
Rechenintensiver Prozess
Ein-/Ausgabeintensiver Prozess
Ausführungszeit
Ausführungszeit
E/A-Wartezeit
E/A-Wartezeit
M. Esponda-Argüero
CPU-I/O Burst Cycle
CPU-Burst
I/O Burst
CPU-I/O Burst Cycle
Maximale Durchsatz +
Optimale I/O-Geräte Auslastung
⇒ Überlappung der Aktivitäten mit Multiprogramming
M. Esponda-Argüero
CPU-Burst Dauer
Freq
uen
zWie oft eine CPU-Burst Länge vorkommt?
CPU-I/O Burst Cycle
- Anwendungsabhängig- Systemabhängig
(Hardware)Typisches Verhalten
M. Esponda-Argüero
Anforderungen an den Scheduler
Aus der Benutzersicht:
- Minimierung der Durchlaufzeit
(absolute Ausführungszeit + Wartezeiten)
- Minimierung der Antwortzeit (interaktive Systeme)
- Einhaltung von Zeitschranken (Deadlines)
Besonders wichtig für Echtzeit-Betriebssysteme
Aus der Systemsicht:
- Maximierung des Durchsatzes
- Maximierung der Prozessorauslastung
- Balance. Auslastung aller Ressourcen
- Fairness. Gleichwichtige Prozesse sollen möglichst gleich behandelt werden
M. Esponda-Argüero
Kriterien für das Scheduling
CPU-Auslastung
Ausführungszeit
Wartezeit
Durchsatz Anzahl der Prozesse, die pro Zeiteinheit ausgeführt werden.
Effektive CPU-Zeit, die ein Prozess von der CPU in Anspruch nimmt.
Zeit, die ein Prozess in Warteschlangen verbringt.
Antwortzeit Zeit zwischen Anforderung und Antwort.
Turnaround Time Durchschnittszeit der Verarbeitung einzelner Jobs.
Beschäftigungszeit (in Prozent).
Overhead Zeitaufwand für die Entscheidung + Kontextwechsel.
M. Esponda-Argüero
Ziele verschiedener Scheduling-Strategien
Alle Systeme
Nach Tanenbaum:
Fairness- jeder Prozess bekommt einen fairen Anteil des CPU.Policy Enforcement- vorgegebene Strategien werden durchgesetzt.Balance- alle Teile des Systems sind ausgelastet.
Stapel-Systeme Durchsatz- Maximierung der Jobs pro Stunde.Durchlaufzeit- Minimierung der Zeit vom Start bis zur BeendigungCPU-Ausnutzung- der CPU ist immer ausgelastet
Interaktive-Systeme
Antwortzeit- schnelle Reaktion auf Anfragen.Proportionalität- Erwartungen des Benutzers erfüllen.
Echtzeit-Systeme
Deadlines einhalten- Datenverlust ausschließen.Vorhersagbarkeit- Qualitätseinbußen in Multimedia-Systemen vermeiden.
M. Esponda-Argüero
Zwei Kategorien von Schedulern
• Nicht unterbrechend (nonpreemptive)
Unterbrechungen nur bei
a) Terminierung
b) Selbstblockierung (Warten auf externe Ereignisse)
c) Ein-/Ausgabe
• Unterbrechend (preemptive)
aktive Prozesse können in den Bereit-Zustand
des Betriebssystems versetzt werden.
M. Esponda-Argüero
Scheduling-AlgorithmenFirst-Come First-Served FCFS
- einfachster aller Scheduling-Algorithmen
- FIFO-Warteschlange
- nicht unterbrechbarer Stapel-Algorithmus
5 9 160P1 P2 P3
ProzesseP1
P2
P3
Ankunft0
1
4
Ausführungszeit5
4
7
Wartezeit0
4
5
Durchschnittliche Wartezeit
3
P1 P2 P3
Zeit
Beispiel:
M. Esponda-Argüero
First-Come First-Served FCFS
Probleme
- convoy effect
- niedrigere CPU-Auslastung
- schlechte Nutzung von Ein-/Ausgabe-Geräten
- ungeeignet für interaktive Systeme
Vorteile
- sehr einfach zu implementieren
- niedriger Scheduling-Overhead
M. Esponda-Argüero
Scheduling-Algorithmen
Shortest Job First SJF
- Laufzeiten sind vorher bekannt
- nicht präemptiver Stapelverarbeitungsalgorithmus
Der Prozess mit der kürzesten Ausführungszeit wird zuerst ausgeführt
Die durchschnittliche Wartezeit wird minimiert.
Shortest Remaining Time First
Die präemptive Version von Shortest Job First
M. Esponda-Argüero
SJF
FCFS
Shortest Job First SJF
Beispiel:
0 4 11 16
P1 P2 P4P3
12
ProzesseP1
P2
P3
P4
Ankunft0
14
4
Ausführungszeit4
71
4
Wartezeit037
8
4 5 160
P1 P2P4P3
9
Wartezeit0018
Durchschnittliche Wartezeit
4,5
Durchschnittliche Wartezeit
2,25
M. Esponda-Argüero
Shortest Job First SJF
Der SJF-Scheduling scheint optimal, um die
durchschnittliche Wartezeit der Prozesse zu minimieren.
Wie können wir wissen, welche CPU-Burst ein
Prozess haben wird?
Batch System
Der Benutzer kann eine Schätzung eingeben.
Kurzzeit-Scheduling
Eine Voraussage kann approximiert werden.
M. Esponda-Argüero
CPU-Burst Approximierung
die Zeiten verlieren mit der Zeit an Bedeutung.
Exponentieller Durchschnitt
τ n+1 = α ⋅ tn + (1−α ) ⋅τ n
τ n+1 = αtn + (1−α )ατ n−1 + ...+ (1−α )nαt1 + (1−α )
n+1t0
τ n+1 Voraussage des nächsten CPU-Burst
tn Zeit des letzten CPU-Burst
τ n Letzte Voraussage
α = 0 die nahe Vergangenheit ist unwichtigWenn ⇒τ n+1 = τ nα = 1Wenn ⇒τ n+1 = tn (nur der letzte CPU-Burst ist wichtig)
α = 12Wenn
τ n+1 = α ⋅ tn + (1−α ) ⋅ (α ⋅ tn−1 + (1−α ) ⋅τ n−1)
M. Esponda-Argüero
CPU-Burst Approximierung
...
...6
8
7
6
6,5
4
5,25
6
5,7
9
7,3
9
8,2
9
8,6
t1τ1
10
9
8
7
6
5
4
3
2
1
0
Voraussage τ iCPU Burst t1
α = 12
M. Esponda-Argüero
Round-Robin Scheduling
- benutzt in interaktiven Systemen
- ältester, einfachster und meist verwendeter Algorithmus
- jedem Prozess wird ein Zeitabschnitt zugewiesen (Quantum)
- ein Prozess wird an das Ende der Warteschlange geschickt, wenn er blockiert wird oder sein Quantum verbraucht hat
Die einzige interessante Frage von Round-Robin betrifft die Länge des Zeitquantums.
Gewöhnliches Quantum = 10 bis 100 ms
M. Esponda-Argüero
Round-Robin RR
A B C D E
Aktiver Prozess
A
B C D EB
AC D E
Wenn das Quantum zu groß ist -> FCFS
Wenn das Quantum zu klein ist, ist der Aufwand des Kontext-Wechsels zu groß.
M. Esponda-Argüero
Durchschnittliche Verarbeitungszeit mit verschiedenen Quanten
Die Durchschnittszeit
der Verarbeitung
einzelner Jobs wird
nicht unbedingt besser
mit der Vergrößerung
des Quantums.Beispiel aus Silberschatz:
Prioritätsbasiertes Scheduling
Jeder Prozess bekommt eine Prioritätszahl zugewiesen und der Prozess mit der höchsten Priorität wird bevorzugt.
Prioritäten können statisch oder dynamisch zugewiesen werden.
Prioritäten Vergabe
nach internen Kriterien
nach externen Kriterien
Durchschnitt E/A-Zeit
Speicherbedarf
durchschnittliche CPU-Zeit
Zeitgrenzen
usw.
M. Esponda-Argüero
Prioritätsbasiertes Scheduling Probleme:
Starvation
Lösung:
Prozesse mit niedriger Priorität verbessern ihre Priorität, je länger sie warten.
Prioritätsumkehrproblem
Ein Prozess mit niedriger Priorität blockiert durch die Verwendung von gemeinsamen Ressourcen Prozesse mit höherer Priorität.
Prozesse mit niedriger Priorität warten ewig.
Lösung:
Prioritätsvererbung.
Der Ressourcenbesitzer bekommt temporär höhere Priorität.
"aging"
M. Esponda-Argüero
Vererbung von Prioritäten
T1
T2
T3
lock R fails lock(R)
lock(R)
unlock(R)
unlock(R)
T3 blockiert T2
T1 blockiert T2 und T3
T3 bekommt die Priorität p1
T1 startet hier und hat
die höchste Priorität (p1)
T2 startet
T2 blockiert T1
M. Esponda-Argüero
Multilevel Queue SchedulingVerschiedene Scheduling-Algorithmen für verschiedene Gruppen von Prozessen.
Beispiel: Systemprozesse
S4 S3 S2 S1PRIO
Benutzer iterativer Prozesse
B5 B4 B3 B2 B1RR
Stapelprozesse
P5 P4 P3 P2 P1FCFSpreemptive
M. Esponda-Argüero
Highest Response Ratio NextVerwendet den Antwortquotienten der Prozesse
R = w + s
s
R = Antwortquotient
w = Wartezeit
s = erwartete Bearbeitungszeit
Es wird der Prozess ausgewählt, dessen Wert R am höchsten
ist.
Prozesse mit kürzerer Bearbeitungszeit werden bevorzugt,
aber Prozesse mit langen Wartezeiten verhungern nicht.
M. Esponda-Argüero
Multilevel Feedback Queue SchedulingVier Prioritätsklassen
Beispiel:
Höchste Priorität
Niedrigste Priorität
Die Prozesse wandern mit der Zeit nach unten.
Niedrigere Priorität, aber größere Quantum.
Quantum = 4
Quantum = 8
Quantum = 16
FCFS
neue Prozesse
M. Esponda-Argüero
Multilevel Feedback Queue Scheduling
Parameter:
- Anzahl der Warteschlangen.
- Scheduling-Algorithmen für jede Warteschlange.
- Wann können Prozesse zwischen den Warteschlangen
wandern.
- Wo werden neu gestartete Prozesse eingeordnet.
- Wie oft wird Scheduling-Information aktualisiert
- Welches Feedback wird verwendet.
M. Esponda-Argüero
freeBSD-Scheduler
✴ Dynamische Prioritäten
✴ nice-Wert. Nettigkeit eines Threads gegenüber den anderen.
"multilevel feedback queue scheduler"
0-20
sehr nett und gibt CPU-Zeit ab
20
nicht nett und willmehr CPU-Zeit
er will gleich bleiben
✴ 128 verschiedene Prioritäten von 0 (PRI_MIN) bis 127 (PRI_MAX)
✴ In jedem 4. Zeit-Quantum werden die Prioritäten neu berechnet
M. Esponda-Argüero
Aktive Tasks
.
.
.
freeBSD-Scheduler
0..3
4..7
8..11
124..127
120..123
- 32 Warteschlangen
- Prozesse der Warteschlange, mit der höchsten Priorität werden zuerst gewählt.
- RR-Strategie innerhalb einer Warteschlange
- Ein-/Ausgabeintensive Prozesse werden gegenüber rechenintensiven Prozessen favorisiert.
M. Esponda-Argüero
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
Berechnung der Prioritäten in Pintos
recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice
load_avg = (59/60)*load_avg + (1/60)*ready_threads
nice = wird vom Benutzer gesetzt
PRI_MAX = 63
mit
freeBSD-Scheduler
M. Esponda-Argüero
Recommended