Embed Size (px)
Citation preview
Scheduling in Echtzeitbetriebssystemen
Prof. Dr. Margarita EspondaFreie Universität Berlin
EchtzeitsystemeKorrekte Ergebnissezum richtigen Zeitpunkt
Echtzeitsysteme
Hart
Weich
Eine verspätete Antwort ist eine falsche Antwort
Eine verspätete Antwort bedeutet schlechte Qualität
M. Esponda-Argüero
Scheduler
Task = Ausführung eines Programms oder Teile eines Programms
Task = Prozess
In Echtzeitbetriebssystemen wird sehr oft
der Begriff Task verwendet.
M. Esponda-Argüero
Scheduling in Echtzeitbetriebssystemen
Algorithmen
off-line on-line
statische Prioritäten dynamische Prioritäten
RMS DMS EDF LLFRate
Monotonic Scheduling
DeadlineMonotonic Scheduling
Earliest Deadline
First
Least Laxity First
M. Esponda-Argüero
Scheduling-Algorithmen
Vereinfachung: Die Prozesse sind voneinander unabhängig
Die Prozesse sind alle unterbrechbar
Notation: r = release = Startpunkt, an dem der Prozess zur Ausführung bereit ist.
e = execution = Zeiteinheiten für die CPU. Schlimmste Ausführungszeit.
d = deadline = Zeiteinheiten bis zur nächsten Zeitschranke.
p = period = Zeit bis zum nächsten Aufruf desselben Prozesses.
Prozess: Ti = ( ri, ei, di, pi ) Beispiel: T1 = ( 1, 3, 7, 10 )
M. Esponda-Argüero
Notation
Prozess: Ti = ( ri, ei, di, pi )
Beispiel: T1 = ( 1, 3, 7, 10 )
Zeit81 11
r =1
e =3
d =7
p =10
T1
M. Esponda-Argüero
Beispiel: drei Prozesse (Tasks)
0 5 10 15 20
Prozesse
T1
T2
T3
T1 = ( 0, 1, 3, 3 )
Start CPU Deadline Periode
T2 = ( 0, 1, 4, 4 )
T3 = ( 0, 2, 5, 5 )
3 CPUs
M. Esponda-Argüero
RMS Rate Monotonic Scheduling
Feste Prioritäten
Die Prioritäten werden umgekehrt proportional zur Periode vergeben
Beispiel: T1 = ( 0, 2, 5, 5 )
T2 = ( 0, 3, 10, 10 )
T3 = ( 0, 4, 20, 20 )
Deadline = Periode
r e d p
M. Esponda-Argüero
Beispiel: RMS
T1 = ( 0, 2, 5, 5 )
T2 = ( 0, 2, 7, 7 )
T3 = ( 0, 3, 18, 18 )
r e d p
Auslastung der CPU2
5
2
7
3
18+ + = 86 %
Der RMS-Algorithmus ist der am besten untersuchte und der am
häufigsten eingesetzte Algorithmus.
Anim
M. Esponda-Argüero
DMS Deadline Monotonic Scheduling
Die Prioritäten der Prozesse sind umgekehrt proportional zur Länge der Deadlines.
Feste Prioritäten
Deadline Periode
Beispiel: T1 = ( 0, 2, 3, 5 )
T2 = ( 0, 3, 10, 10 )
T3 = ( 0, 4, 8, 20 )
r e d p
M. Esponda-Argüero
DMS
1
2
0 5 10 15 20
Prozesse
T1
T2
T3
4
5
3 6
Deadline verletzt !
T1 = ( 0, 1, 3, 3 )
T2 = ( 0, 1, 4, 4 )
T3 = ( 0, 2, 5, 5 )
Mit DMS nicht lösbar
M. Esponda-Argüero
DMS
12
0 5 10 15 20
Prozesse
T1
T2
T3
4
53
Deadline verletzt !
3
M. Esponda-Argüero
Beispiel: DMS
Erfüllbarkeitstest
Prüft, ob alle Deadlines eingehalten werden können.
e2 /p2 = 40 %
e1 /p1 = 50 % CPU Auslastung
CPU Auslastung 90%
T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
r e d p
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) > Priorität ( T2 )
0 25 50 75 100 125 150
r e d p
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) > Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) > Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) > Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) > Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
T2 verpasst die erste Deadline
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) < Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
Priorität ( T1 ) < Priorität ( T2 )
0 25 50 75 100 125 150
d1 d1d2 d2
T1 verpasst die erste Deadline
M. Esponda-Argüero
EDF Earliest Deadline First
Früheste Deadline zuerst
Der Prozess mit der nächsten Deadline wird als nächster
abgearbeitet.
Priorität von Ti(t) = di(t) - t
M. Esponda-Argüero
Earliest Deadline First
1
2
0 5 10 15 20
Prozesse
T1
T2
T3
3T1 = ( 0, 1, 3, 3 )
T2 = ( 0, 1, 4, 4 )
T3 = ( 0, 2, 5, 5 )
M. Esponda-Argüero
Earliest Deadline First
1
2
0 5 10 15 20
Prozesse
T1
T2
T3 3
4 6 9 11 13 16
5 8 12 14
10 157
T1 = ( 0, 1, 3, 3 )
T2 = ( 0, 1, 4, 4 )
T3 = ( 0, 2, 5, 5 )
M. Esponda-Argüero
LLF Least Laxity First
Kleinster zeitlicher Spielraum
Der Prozess mit der kleinsten Zusatzzeit wird als nächster abgearbeitet.
li(t) = di(t) – t – ei(t)
Zeitlicher Spielraum
M. Esponda-Argüero
Beispiel: zwei Prozesse
0 5 10 15 20
Prozesse
T1
T2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
T1
T2
3
4
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
T1
T2
3
3
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
3
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
T1
T2
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
1
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
1
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
1
3
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
4
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
3
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
3
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
3
3
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
3
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
2
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
1
2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
1
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Least Laxity First
0 5 10 15 20
Prozesse
t1
t2
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
t
M. Esponda-Argüero
Earliest Deadline FirstProzesse
t1
t2
0 5 10 15
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
M. Esponda-Argüero
Earliest Deadline FirstProzesse
t1
t2
0 5 10 15 20
1
2
3 5 6
4 7
25
8 10
30 35
9
T1 = ( 0, 3, 6, 6 )
T2 = ( 0, 4, 8, 9 )
idle
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
5
9
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d25
8
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d25
7
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d25
6
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d25
5
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d25
4
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
4
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
4
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
4
Least Laxity First
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
9
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
8
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
8
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
7
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
6
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
5
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
5
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
4
4
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
3
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
Least Laxity First
M. Esponda-Argüero
Beispiel: Keine Lösung mit DMS
CPU Auslastung 90%T1 = ( 0, 25, 50, 50 )
T2 = ( 0, 30, 75, 75 )
0 25 50 75 100 125 150
d1 d1d2 d2
aber mit Least Laxity First
d1
idle
M. Esponda-Argüero
Scheduling in Echtzeitbetriebssystemen
Echtzeitbetriebssysteme müssen Zeitanforderungen
erfüllen
Scheduling wird häufig durch Prioritätsvergabe gesteuert
Prioritäten können statisch oder dynamisch vergeben
werden
Wir haben vier grundlegende Algorithmen besprochen
Was noch fehlt: Scheduling mit abhängigen Prozessen
M. Esponda-Argüero
