Prozessorzuteilung (Scheduling)
Vorlesung Betriebssysteme I
I
Thema 7: Zuteilung des Prozessors
Robert Baumgartl
11. Januar 2016
= Beantwortung der Frage:
„Welche Aktivität soll zu einem bestimmten
Zeitpunkt abgearbeitet werden (und für wie
lange)?“
I
Komponente im Betriebssystem: der Scheduler (Planer)
I
Verfahren zur Ermittlung einer Abarbeitungsplans
(Schedule)
2 / 33
1 / 33
Typische Zielgrößen
Planung anderer Ressourcen
Je nach betrachteter Systemklasse (z. B. Batchsysteme,
Interaktive Systeme, Echtzeitsysteme) existieren verschiedene
zu optimierende Parameter:
I
mittlere Reaktionszeit aller Prozesse
I
mittlere Verweilzeit aller Prozesse (turnaround time)
I
maximale CPU-Ausnutzung
I
maximale Anzahl gleichzeitiger Datenströme
I
Garantie einer maximalen Reaktionszeit
I
Fairness: n Prozesse → jeder 1/n der Prozessorzeit
I
Quality-of-Service (QoS): „Jeder bekommt so viel, wie er
bezahlt hat.“
I
Ausschluss des Verhungerns einzelner Prozesse
Außer dem Prozessor können (müssen aber nicht) die
folgenden Ressourcen geplant werden:
I
Hauptspeicher,
I
Aufträge an den Massenspeicher,
I
Kommunikationsbandbreite,
I
Interrupts
I
...
Beispiel: Linux besitzt einen sog. I/O-Scheduler, der
Festplattenaufträge plant (d. h. , ggf. umsortiert).
3 / 33
4 / 33
Beispiel: Schedulingebenen in einem Batch-System
Off-Line- vs. On-Line-Verfahren
Off-Line
CPU
CPU
Scheduler
I
komplette Ermittlung des Abarbeitungsplans vor
Inbetriebnahme des Systems
I
Zur Laufzeit des Systems wird der vorbereitete Plan
abgearbeitet (keine Entscheidungen mehr notwendig).
I
inflexibel
I
sehr hohe Auslastung möglich
I
Startzeitpunkte, Ausführungszeiten, Abhängigkeiten aller
Aktivitäten müssen a priori bekannt sein.
I
z. B. bei autonomen oder Echtzeit-Systemen
I
situationsspezifische Pläne möglich, System unterscheidet
mehrere Modi
Arriving Job
Input Queue
Haupt−
speicher
Admission
Scheduler
Disk
Memory
Scheduler
Quelle: Andrew Tanenbaum, Modern Operating Systems. 2000,
S. 141
5 / 33
6 / 33
1
Off-Line- vs. On-Line-Verfahren
Beispiel für Off-Line-Scheduling
Ein (nicht näher spezifiziertes) Rechensystem bestehe aus 3
Prozessen, die wiederum aus den folgenden unabhängigen
Teilprozessen bestehen (benötigte Rechenzeit in Klammern):
On-Line
I
Auswahl des jeweils nächsten abzuarbeitenden Prozesses
erfolgt zur Laufzeit des Systems.
I
Flexibel: System kann auf Änderungen verschiedener
Parameter, Umwelteinflüsse, Nutzeranforderungen
reagieren
I
keine Zeit für langwierige Auswahlverfahren →
Kompromiss zwischen Optimalität des ausgesuchten
Prozesses und Dauer für die Entscheidung notwendig.
P1 : { p11 (3), p12 (2), p13 (2), p14 (5) }
P2 : { p21 (5), p22 (7) }
P3 : { p31 (5), p32 (2) }
Außerdem bestehen die folgenden expliziten zeitlichen
Abhängigkeiten zwischen den Teilprozessen:
p21 vor p12 , p12 vor p22 , p13 vor p31 ,
p14 vor p32 , p22 vor p32 .
Typische interaktive Betriebssysteme wie Windows oder Linux
planen on-line.
Darüberhinaus müssen die Teilprozesse ein- und desselben
Prozesses hintereinander liegen.
7 / 33
8 / 33
Präzedenzgraph
Ableitung eines Schedules (off-line)
Die zeitlichen Abhängigkeiten veranschaulicht man am besten
in einem Präzedenzgraphen:
I einen Knoten für jeden Teilprozess
I eine Kante zwischen zwei Knoten genau dann, wenn der
erste Knoten beendet sein muss, bevor der zweite
gestartet werden darf
p11
1. Bildung der Bereit-Menge B (enthält alle Prozesse, die
abgearbeitet werden können)
2. Auswahl von n Prozessen aus B (n ist die
Prozessoranzahl, im einfachsten Falle also 1) nach
vorgegebenem Kriterium (z. B. „den kürzesten Prozess
zuerst“)
p14
p13
3
Verfahren:
5
2
p12
3. Planung der ausgewählten Prozesse für bestimmte
Zeitspanne (im einfachsten Falle: für eine Zeiteinheit)
p31
2
5
p21
p22
5
p32
4. Falls noch nicht alle Prozesse geplant sind → Goto 1
2
5. Stop
7
Abbildung: Präzedenzgraph des Beispielprozesssystems
9 / 33
10 / 33
Anwendung auf Beispieltaskmenge
I
I
I
Resultierender Schedule
n = 2 (z. B. Dualcore-Prozessor)
Auswahl des jeweils kürzesten Prozesses (Shortest Job
Next)
Abarbeitung ohne Unterbrechung, wenn einmal gestartet
(Run-to-Completion)
Zeit
0
3
5
7
9
14
19
B
p11 , p21
(p21 )
p12
p13 , p22
p14 , p31
p31
p32
p 11
P1
p 12
0
2
p 14
p 13
p 31
p 32
p 22
p 21
P2
4
6
8
10
12
14
16
18
20
22
Abbildung: Off-Line Schedule für Beispieltaskmenge und ohne
Unterbrechungen
Auswahl
p11 , p21
(p21 )
p12
p13 , p22
p14
p31
p31
I
Resultat: Gantt-Diagramm (benannt nach dem
Unternehmensberater (!) Henry L. Gantt)
I
Komplettierung des letzten Teilprozesses zu t = 21
I
Prozessoren nicht voll ausgelastet (idle time); Ursache:
Präzedenzen zwischen Teilprozessen
Tabelle: Schedulingzeitpunkte für Beispiel
11 / 33
12 / 33
2
Zeitgesteuertes Scheduling
Time Division Multiple Access
I
alle Abläufe im System erfolgen in festem zeitlichen
Rahmen, periodisch
I
keine Interrupts → keine unvorhergesehenen Aktivitäten
I
Prinzip:
I Übertragungszeit wird in (unendlich viele) Perioden fester
Länge aufgeteilt
I innerhalb jeder Periode erhält jeder (potentielle)
Kommunikationsteilnehmer 1/n der Periodenlänge, einen
sog. Slot
I in seinem Slot kann jeder senden oder nicht
I → keine Kollisionen möglich
Kommunikation mit externe Komponenten: Abfragen
(Polling)
I
typisch für autonome und Echtzeitsysteme
I
Nutzung von off-line ermittelten Schedules, zwischen
denen umgeschaltet werden kann (Moduswechsel)
I
Beispiel: Medienzugriffsverfahren Time Division Multiple
Access (TDMA)
Prozess sendet nicht.
...
0
1
2
3
4
5
6
7
t
Slot
Periode
14 / 33
13 / 33
Ereignisgesteuertes Scheduling
Was passiert denn eigentlich beim Interrupt?
Prozess
Prinzip:
I
System reagiert auf Einflüsse von außen (Interrupts)
I
Aktivitäten werden als Reaktion auf Interrupts bereit
I
prinzipiell keine Garantie von Ausführungszeiten möglich,
da Auftrittszeitpunkte von Interrupts nicht vorhersehbar
I
typisch für interaktive Systeme
I
Beispiel: Grafische Benutzeroberflächen (Ereignisse:
Mausbewegung, Klick, Tastendruck, aber auch Interrupt
durch die Netzwerkkarte)
Instruktion n
Instruktion 1
Instruktion n+1
Instruktion 2
Interruptservice−
Routine (ISR)
Interrupt
Instruktion n+2
IRET
Abbildung: Ablauf einer Interruptbehandlung (vereinfacht)
I
Interrupts sind asynchron zum Programmablauf
I
Quellen: Geräte (I/O), Programm, Betriebssystem
15 / 33
16 / 33
Interrupt: Ablauf in der CPU
Hardware
Device controller or
other system hardware
issues an interrupt
Processor finishes
execution of current
instruction
Schedulingzeitpunkt beim On-Line Scheduling
Software
Unterbrechung eines aktiven Prozesses:
I durch das BS, (prinzipiell) jederzeit (präemptives
Multitasking):
Save remainder of
process state
information
I
I
Process interrupt
Processor signals
acknowledgment
of interrupt
Processor pushes PSW
and PC onto control
stack
Processor loads new
PC value based on
interrupt
I
wenn ein Prozess blockiert (z. B. an Ressource),
wenn ein Prozess bereit wird (z. B. als Reaktion auf einen
Interrupt oder durch eine Ressourcenfreigabe),
wenn ein Prozess endet.
Restore process state
information
I
durch das BS, jedoch nur an bestimmten Stellen,
sogenannten Preemption Points
Restore old PSW
and PC
I
freiwillig, an bestimmten Stellen, z. B. Systemruf
(kooperatives Multitasking)
I
nach Komplettierung einer Aktivität (run-to-completion)
(William Stallings: Operating
Systems.
6th ed., Pearson, 2009)
Figure 1.10 Simple
Interrupt Processing
17 / 33
18 / 33
3
Prioritäten und Priorisierung
I
Implizite Prioritäten: ein bestimmter Parameter jedes
Prozesses wird „zweckentfremdet“ zur Bestimmung der
Priorität herangezogen.
Beispiele:
(gewollt) unfair, Prozesse besitzen unterschiedliche
Wichtigkeit
I
einfachste Möglichkeit: Fixed External Priorities (FEP))
I
d. h. , jeder Prozess erhält vor der Laufzeit des Systems
einen Parameter fest zugeordnet, der seine Wichtigkeit
ausdrückt, seine Priorität
I
Prioritäten zum zweiten
zur Laufzeit wird stets der höchstpriorisierte unter allen
bereiten Prozessen ausgewählt
I
Länge des Jobs
I
verbleibende Abarbeitungszeit
I
Zeit seit letzter Aktivierung
I
Deadline (Zeit bis zur unbedingten Komplettierung)
19 / 33
20 / 33
Statische und dynamische Prioritäten
Uniprozessor- vs. Multiprozessor-Scheduling
I
Statisch: Priorität eines Prozesses ist konstant.
I
einfacher Scheduler
I
gut zu analysieren
I
nicht besonders flexibel (was ist, wenn sich die Wichtigkeit
eines Prozesses ändert?)
I
I
I
Dynamisch: Priorität eines Prozesses ändert sich mit der Zeit.
I
periodische Neuberechnung (Aufwand!)
I
erlaubt situationsspezifische Anpassungen
I
schwieriger zu analysieren
zusätzlich nötige Entscheidung, wo Prozess abgearbeitet
wird
Ziel: Load Balancing
zu starr: möglicherweise schlechte Ausnutzung der
Prozessoren
zu flexibel: häufiger Wechsel des Prozessors (Thrashing)
→ sehr hoher Overhead
I
ideal: auf einem unbeschäftigten Prozessor fortsetzen
I
günstig: Prozessor, auf dem der Prozess unterbrochen
wurde (Cache, TLB)
I
Parameter Affinität des Prozesses zu einem bestimmten
Prozessor
21 / 33
22 / 33
Round Robin – Zeitscheibenverfahren
Veranschaulichung Round-Robin
Idee: Jeder Prozess erhält den Prozessor für eine bestimmte
Zeitspanne (Quantum tq ), dann ist der nächste dran.
I
Grundgedanke: Fairness
I
tq klein → Umschaltaufwand im Verhältnis zur Nutzarbeit
groß, kleine Reaktionszeit pro Prozess
I
tq groß → relativer Umschaltaufwand klein, Reaktionszeit
pro Prozess groß
I
wichtiger Parameter: Umschaltzeit tcs (Context Switch
Time)
I
Reaktionszeit eines Prozesses abhängig von tcs , Anzahl
Prozesse, tq
I
häufig Kombination mit Prioritäten (RR innerhalb einer
Prioritätsklasse)
t cs
...
P1
P2
P3
P1
...
tq
t rsp
Abbildung: Parameter beim Zeitscheibenverfahren
23 / 33
24 / 33
4
Beispiel: Einfache Batch-Verfahren
Beispiel zu SJN
First In First Out (FIFO, FCFS)
I
Job
Prozesse werden in der Reihenfolge ihres Eintreffens
(vollständig abgearbeitet)
I
fair
I
leicht zu analysieren (→ Warteschlangentheorie)
4 Beispieltasks:
Shortest Job Next (SJN)
I
Idee: schnell ein paar kurze Jobs fertigstellen, bevor alle
auf einen langen Job warten müssen.
I
Prozess mit der kürzesten Dauer wird ausgewählt,
run-to-completion
I
Ausführungszeit muss bekannt sein
I
minimiert mittlere Verweilzeit (t v ) und mittlere Wartezeit
(t w )
I
ungerecht, Verhungern möglich
J4
J1
0
3
Dauer
J1
J2
J3
J4
6
8
7
3
J3
J2
9
16
24
Abbildung: Resultierender SJN-Schedule
tw =
0 + 3 + 9 + 16
=7
4
tv =
3 + 9 + 16 + 24
= 13
4
25 / 33
26 / 33
Unix
Linux?
I
I
zeitscheibengesteuert (Quantum)
versucht, 2 Klassen von Prozessen zu unterscheiden und
getrennt zu behandeln:
Rechnende Prozesse nutzen ihre Zeitscheibe voll aus
I
Interaktive Prozesse nutzen ihre Zeitscheibe häufig nicht
aus (warten auf Interaktion durch Nutzer oder Gerät; d. h.
blockieren häufig)
wenn Zeitscheibe nicht ausgenutzt, wird Priorität (leicht)
erhöht → Unix bevorzugt interaktive Prozesse:
I
I
I
dynamische Prioritäten mit Zeitscheiben
I
genaues Verfahren ziemlich kompliziert
I
jeder interaktive Prozess besitzt einen sog. nice-Value
dieser beschreibt, wie der betreffende Prozess im
Vergleich zu anderen interaktiven Prozessen priorisiert
wird
I
1. interaktive („I/O-bound“)
2. (vorwiegend) rechnende („compute-bound“)
I
I
I
I
I
I
interaktive Prozesse reagieren besser
rechnende Prozesse werden etwas benachteiligt
-20: höchste Priorität
0: default
19: niedrigste Priorität
Kommandos nice und renice (für bereits laufende
Prozesse) ändern diesen Wert
~> renice 20 -p 24195
24195: old priority 0, new priority 19
Achtung: normale Nutzer dürfen Priorität nur monoton ändern.
27 / 33
28 / 33
Anzeige Priorität und nice-Wert mittels top
Scheduling in Windows 2000/XP/Vista
I
top - 14:31:23 up 3:28, 6 users, load average: 1.68, 0.67, 0.30
Tasks: 91 total,
4 running, 87 sleeping,
0 stopped,
0 zombie
Cpu(s): 42.1%us, 44.7%sy, 13.2%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Mem:
256396k total,
239564k used,
16832k free,
31364k buffers
Swap: 1048568k total,
84k used, 1048484k free,
100936k cached
PID
3735
24194
24195
23793
23928
1
2
3
4
5
6
9
10
104
138
139
140
USER
root
robge
robge
robge
robge
root
root
root
root
root
root
root
root
root
root
root
root
PR
16
15
39
15
15
15
RT
34
10
10
11
17
19
10
15
15
10
NI
0
0
19
0
0
0
0
19
-5
-5
-5
-5
-5
-5
0
0
-5
VIRT
161m
7404
5672
9640
7408
1948
0
0
0
0
0
0
0
0
0
0
0
RES
12m
3216
2636
5808
3260
648
0
0
0
0
0
0
0
0
0
0
0
SHR
4400
2244
1412
4272
2264
552
0
0
0
0
0
0
0
0
0
0
0
S
R
S
R
S
R
S
S
S
S
S
S
S
S
S
S
S
S
%CPU %MEM
50.9 4.9
26.6 1.3
15.6 1.0
6.0 2.3
0.3 1.3
0.0 0.3
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
TIME+
3:08.68
1:59.25
2:08.29
0:01.57
0:01.82
0:01.14
0:00.00
0:00.00
0:00.08
0:00.00
0:00.00
0:00.00
0:00.00
0:00.02
0:00.01
0:00.08
0:01.04
prioritätsgesteuert, präemptiv
31
"real−time" levels
COMMAND
Xorg
xterm
bash
WindowMaker
xterm
init
migration/0
ksoftirqd/0
events/0
khelper
kthread
kblockd/0
kacpid
kseriod
pdflush
pdflush
kswapd0
16
15
variable levels
1
0
system level
Abbildung: Prioritätsstufen im Windows 2000/XP
29 / 33
30 / 33
5
Scheduling in Windows 2000/XP/Vista
I
Round-Robin bei Threads gleicher Priorität
I
Länge des Quantums differiert für Desktop- und
Server-Variante (Server: 6fach länger!)
I
Quantum wird für Vordergrundthreads verdoppelt
temporäre Prioritätsanhebung (Priority Boost) in den
Levels 1-15 u. a. bei
I
I
I
I
Prinzip des Priority Boost
tq
Priorität
Basis−
priorität
Komplettierung einer I/O-Operation
Fensterthreads, die in den Vordergrund gelangen,
Gefahr des Verhungerns.
aktiv
wartend
aktiv
preempted
aktiv
Zeit
32 / 33
31 / 33
Was haben wir gelernt?
1. on-line vs. off-line Scheduling
2. zeitgesteuertes vs. ereignisgesteuertes Scheduling
3. Interrupts
4. kooperatives vs. präemptives Multitasking
5. statische vs. dynamische Prioritäten
6. Round Robin; Einfluss der Zeitscheibenlänge
7. Priority Boost
33 / 33
6
© Copyright 2024 ExpyDoc
