close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Aktuelle Gottesdienstordnung zum

EinbettenHerunterladen
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Inhalte
• Anforderungen
• Klassifizierungen
• Verschiedene Verfahren: FIFO, Round Robin, Least Laxity, EDF, fixed/dyn. Prio.
• Beispiele und Aufgaben
Seite 1
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Motivation
Gegeben:
• Ein Einprozessorsystem, das Multiprogrammierung erlaubt.
• Prozess, der von der CPU bedient wird, ist im Status running.
• Prozesse, die auf CPU warten, sind im Status ready.
Frage: Welcher der lauffähigen Prozesse soll als nächster bedient werden?
• Kriterien aus Sicht der Prozesse:
–
–
•
Kriterien aus Sicht der CPU:
–
–
–
–
•
•
Fairness: kein Prozess soll zu lange auf CPU-Zuteilung warten.
Wichtigkeit: Prozesse mit hoher Priorität werden bevorzugt abgearbeitet.
Maximaler Durchsatz
Maximale Auslastung der CPU
Minimale mittlere Wartezeit (= Zeit, bis ein Prozess abgearbeitet wird = Reaktionszeit))
Minimale mittlere Systemzeit (= Wartezeit + Ausführungszeit)
Kriterien sind z.T. widersprüchlich.
Im Allgemeinen wird eine Mischung dieser Kriterien gewählt.
Seite 2
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling: Unter Scheduling versteht man die Vergabe des Prozessors an ablaufwillige
Tasks nach einem festgelegten Algorithmus (Schedulingverfahren), so dass alle
harten/festen Echtzeitanforderungen und möglichst viele weiche Echtzeitanforderungen
erfüllt werden.
Der Scheduler stellt die Tasks in die Bereitliste, die der Dispatcher abarbeitet, indem er
die „nächste“ Task dem Prozessor übergibt.
Problemstellungen beim Scheduling
• Ist es für eine Menge von Tasks möglich, alle Zeitbedingungen einzuhalten?
– falls ja, existiert (mindestens) ein Schedule, d.h. zeitliche Aufteilung der CPU an
die Tasks
– mathematische Analyse: Scheduling Analysis ggf. unter Berücksichtigung eines
Schedulingverfahrens
• Kann der Schedule in endlicher Zeit berechnet werden?
• Findet das benutzte Schedulingverfahren diesen Schedule?
– ein optimales Schedulingverfahren findet den Schedule immer, falls dieser
existiert
Seite 3
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling Analysis (Feasibility Analysis)
• Vorab-Analyse, ob für eine Taskmenge ein Schedule existiert
• Zentrale Größe: Prozessorauslastung H
• Notwendige Bedingung für Existenz eines Schedule: H ≤ 1 (bzw. 100%)
– Gilt auch für periodische Tasks, falls Zeitschranke = Periode
•
Beispiel:
Seite 4
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Klassifizierung von Schedulingverfahren:
Statisches Scheduling
Nicht-präemptives
Scheduling
Präemptives
Scheduling
Dynamisches Scheduling
Nicht-präemptives
Scheduling
Statische
Prioritäten
Dynamische
Prioritäten
Nicht prioritätsbasiert
Präemptives
Scheduling
Statische
Prioritäten
Dynamische
Prioritäten
Nicht prioritätsbasiert
Seite 5
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Klassifizierung von Schedulingverfahren:
• Statisches oder dynamisches Scheduling
–
–
•
Statische oder dynamische Prioritäten
–
•
statisch: Schedule wird bereits vor der Ausführung berechnet
• Zuordnungstabelle enthält Startzeit für jede Task
• CPU-Zuteilung zur Laufzeit durch Dispatcher
• entspricht Prinzip der synchronen Programmierung (determiniertes Verhalten)
dynamisch: Zuordnung Task - CPU zur Laufzeit berechnet
• entspricht asynchroner Programmierung (flexibel bei Änderungen)
es gibt aber auch Verfahren ganz ohne Prioritäten
Präemptives oder nicht-präemptives Scheduling
–
–
–
Präemptiv: höherpriore Task verdrängt niederpriore
Nicht-präemptiv: Prozessorfreigabe durch die Task selbst
präemptives Scheduling meist vorteilhafter (Reaktionszeit!)
Seite 6
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Klassifizierung von Schedulingverfahren:
Task 1 fertig
Task 2 fertig
Task 1 (wichtig)
Präemption
Task 2 (weniger
wichtig)
Ruhe
Ereignis
für Task 2
Ereignis
für Task 1
a) Präemptives Scheduling
Ereignis
für Task 2
Ereignis
für Task 1
b) Nicht-präemptives Scheduling
Seite 7
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling in Abhängigkeit der Ausführungszeiten der Prozesse
• Grundlegendes Problem: Woher weiß man a-priori, wie lange ein Prozess dauern wird?
• Lösung: Aus der Dauer der Prozesse in der Vergangenheit auf das Verhalten in der
Zukunft schließen.
–
–
Einfache Schätzverfahren verwenden Zeitfenster, z.B. den Durchschnitt der letzten n Prozesse
oder 80% des Maximalwerts der letzten n Prozesse
Exponential-Averaging versucht, adaptiv aus der Vergangenheit zu lernen:
Sei T(n) die Schätzung für den n-ten Prozess und t(n) seine tatsächliche Dauer, dann erhält
man die Schätzung für den (n+1)-Prozess durch
T(n+1) = α * t(n) + (1−α) * T(n)
mit: α liegt in [0,1] und beeinflusst die Art des Lernens:
Extremfälle: α = 0 => T(n+1) = T(n), d.h. die Schätzung ist immer gleich. Es findet
kein Lernen statt.
α = 1 => T(n+1) = t(n), d.h. nur der letzte Wert wird für die Schätzung
herangezogen, was einem hektischen Verhalten entspricht.
Kompromiss: Verwendung von 0 < α < 1, wodurch ein exponentielles Abklingen der
Vergangenheit erreicht wird (je größer α, desto schneller wird die Vergangenheit vergessen).
Seite 8
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling in Abhängigkeit der Ausführungszeiten der Prozesse
• Exponential-Averaging: Schaue in die Vergangenheit und versuche, die Zukunft
vorherzusagen (mittels gewichteter Mittelwertbildung)
Tatsächliche Dauer
t(n) des Prozesses
Geschätzte Dauer
T(n+1) des folgenden
Prozesses
Seite 9
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verschiedene Schedulingverfahren:
•
FIFO-Verfahren
•
Zeitscheibenverfahren (Round Robin, time slice scheduling)
•
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
– Für zyklische Tasks: Ratenmonotones Scheduling (RMS)
•
Verfahren der kleinsten Restantwortzeit (earliest deadline first (EDF))
•
Verfahren des kleinsten Spielraums (least laxity first (LLF))
•
Verfahren Guaranteed Percentage Scheduling (GP)
Seite 10
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
FIFO Scheduling (first-in-first-out):
• Dynamisch, nicht-präemptiv, ohne Prioritäten
• Task, deren Einplanung am weitesten zurückliegt, bekommt
Prozessor
• Einfache Realisierung, aber keine Berücksichtigung der
Zeitbedingungen
• Beispiel. Siehe Gantt Diagramm (Balkenplan) unten
• Für harte Realzeitsysteme nicht geeignet
Task A bereit
Task B
bereit
Task C
bereit
Task
Ausführungs
zeit
A
8 ms
B
5 ms
C
2 ms
D
10 ms
Task D bereit
t [ms]
B
A
5
10
C
D
15
20
25
t [ms]
Seite 11
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
FIFO Scheduling (first-in-first-out):
• Warteschlangenmodell:
[ neue Task ]
CPU
[ Task fertig ]
FIFO-Warteschlange
•
Es gibt auch die LIFO-Strategie, bei der der Prozess, der als letzter CPU-Zeit
angefordert hat und damit am kürzesten wartet, CPU-Zugriff erhält; für diese Strategie
gibt es auch eine präemptive Variante:
Seite 12
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
FIFO Scheduling (first-in-first-out):
• Beispiel
Task
Periode pi
Ausführungszeit ei
1
150 ms
15 ms
2
10 ms
1 ms
H = 20%
Deadline für 1. AusFührung von Task 2
1. Ausführung von
Task 2 fertig
Task 1
Task 2
verpasst
ruhend
0
Ereignis für
Task 1
5
Ereignis für
Task 2
10
15
20
25
t [ms]
Ereignis für
Task 2
Seite 13
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
FIFO Scheduling (first-in-first-out):
• Übung: Zeichnen Sie den Ablauf
der einzelnen Tasks und
berechnen Sie die
durchschnittliche Reaktionszeit
(Wartezeit im Zustand „bereit“)
dieser Tasks beim FIFOVerfahren.
Task
Ankunftszeit
Ausführungszeit
A
0 ms
4 ms
B
2 ms
3 ms
C
4 ms
6 ms
D
11 ms
3 ms
Deadline für 1. AusFührung von Task 6
2 ms
12 ms
E
Task A
Task B
Task C
Task D
Task E
ruhend
0
5
10
15
20
25
t [ms]
Seite 14
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
FIFO Scheduling (first-in-first-out):
• Hauptproblem bei FIFO ist die Benachteiligung kurzlaufender Jobs durch Langläufer
– Beispiel aus dem täglichen Leben: analoges Problem an Supermarktkassen
– Lösung hier: Schnellkassen für Kunden mit maximal 10 Artikeln
• Entsprechend beim CPU-Scheduling: ausführungszeitabhängige Strategien
– Shortest-Processing-Time-First (SPT), auch Shortest-Job-First (SJF)
– Voraussetzung: Ausführungszeit der Tasks ist bekannt
– Man kann zeigen, dass die mittlere Reaktionszeit von SPT für die Klasse der
nicht-präemptiven Strategien minimal ist, d.h. SPT ist die optimale Strategie bzgl.
der Wartezeit.
• Übung: Zeichnen Sie den Ablauf der einzelnen Tasks
Task Ausführungszeit
und berechnen Sie die durchschnittliche Reaktionszeit
(Wartezeit) dieser Tasks für FIFO und SPT unter der
A
6 ms
Voraussetzung, dass alle zum Zeitpunkt
B
8 ms
T=0 kurz hintereinander eintreffen: A,B,C,D.
C
7 ms
D
3 ms
Seite 15
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren (RR):
• Dynamisch, präemptiv, ohne Prioritäten
• Jede Task bekommt einen festgelegten Zeitschlitz, zu der sie
den Prozessor bekommt
• Reihenfolge nach zeitlichem
Eintreffen oder auch gem. Kreis
• Periodendauer abh. von
A
B
der Anzahl der Tasks
• Für harte Realzeitsysteme
D
C
untauglich
Task
Ausführungs
zeit
A
25 ms
B
20 ms
C
30 ms
D
20 ms
Zeitschlitz (Quantum) = Q = 10 ms
A
0
A, B, C, D
B
10
C
D
A
40
B
50
C
D
A
80
t [ms]
C
100
Seite 16
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren (RR):
[ neue Task ]
•
Warteschlangenmodell:
CPU
FIFO-Warteschlange
[ Task fertig ]
[ Task nicht fertig ]
•
•
•
RR versucht, Fairness gegenüber Kurzläufern und soweit möglich auch gegenüber
Langläufern zu gewähren
rechnender Prozess wird vom BS nach dem Ablauf einer Zeitscheibe (time slice,
Q=Quantum) unterbrochen und wieder hinten in die Warteschlange eingefügt
Wichtige Frage: Wie lang ist Q?
–
–
–
–
Q → ∞ : FIFO
Q → 0 : Prozessor-Sharing, d.h. CPU wird gleichmäßig auf die z. Zt. Aktiven Prozesse
aufgeteilt, wodurch jeder Prozess genau 1/n der CPU-Leistung erhält.
sehr problematische Annahme, dass Zerhacken in kleinste Scheiben nichts kostet.
Richtwerte: 20 bis 50 ms
Seite 17
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren (RR), wenn neuer Prozess bereit ist
und Zeitscheibenablauf zur gleichen Zeit passieren:
• Konvention: Wenn ein Prozess bereit wird, kommt er ans
Ende der Warteschlange und zwar gegebenenfalls kurz vor
dem eigentlich gleichzeitig fälligen Zeitscheibenablauf.
• Beispiel für Zeitschlitz (Quantum) = Q = 10 ms
• Warteschlange bei 20 ms wird zuerst mit B (1. Zeitschlitz)
und dann mit A (3. Zeitschlitz) gefüllt
0
exec
Ws.:
Ws.:
10
A
20
A
30
40
50
60
Task
Ankunfts
-zeit
Ausführungszeit
A
0 ms
40 ms
B
20 ms
30 ms
C
40 ms
30 ms
70
80
90
B
A
C
B
A
C
B
A
B
B
A
C
B
C
A
C
B
100
C
Seite 18
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren (RR), wenn Reihenfolge immer
gemäß Kreiseinteilung: A – B – C usw:
Kreis entspricht der Warteschlange:
Bei 0 ms ist A gefüllt
Nach 20 ms ist B gefüllt
Nach 40 ms ist C gefüllt
A
C
Task
Ankunfts
-zeit
Ausführungszeit
A
0 ms
40 ms
B
20 ms
30 ms
C
40 ms
30 ms
B
0
exec
10
A
20
A
30
B
40
A
50
B
60
C
70
A
80
B
90
C
100
C
Seite 19
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren:
Übung: Zeichnen Sie den Ablauf der
einzelnen Tasks und berechnen Sie
die durchschnittliche Reaktionszeit für
Zeitschlitz = 1ms und = 5ms).
Task
Ankunftszeit
Ausführungszeit
A
0 ms
4 ms
B
2 ms
3 ms
C
4 ms
6 ms
D
11 ms
3 ms
Deadline für 1. AusFührung von Task 6
2 ms
12 ms
E
Task A
Task B
Task C
Task D
Task E
ruhend
0
5
10
15
20
25
t [ms]
Seite 20
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Multilevel Feedback Scheduling (MFS): mehrere Warteschlangen mit
Prioritäten, Zeitscheiben und Rückkopplung:
• Neu ankommende Jobs werden in die höchste Prioritätsklasse eingeordnet
• Abarbeitung nach Round-Robin: unterschiedliche Quantengröße, Klassen
hoher Priorität haben kleine Quanten, bei kleiner Priorität große Quanten, d.h.
Q1 < Q2 < …< Qn.
• Wenn Job in seiner Zeitscheibe nicht fertig wird, wandert er in die nächst
niedrigere Prioritätsklasse
• Bedient wird nicht-präemptiv
• Beispiel: 3 Warteschlangen: Q1=8ms mit max. 10 Zeitschlitzen, Q2=16ms mit
max. 5 Zeitschlitzen, Q3=FIFO:
–
–
Ein neuer Prozess landet in Warteschlange Q1 die mittels FIFO verwaltet wird. Wenn
der Prozess an der Reihe ist erhält er 8 ms CPU-Zeit. Wenn der Prozess nicht fertig
geworden ist, landet er unmittelbar in Q2.
In Q2 wartet der Prozess wieder gemäß FIFO und erhält zusätzliche 16 ms. Reicht
dies immer noch nicht, dann wir der Prozess unterbrochen und in Warteschlange Q3
verschoben.
Seite 21
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Multilevel Feedback Scheduling (MFS): mehrere Warteschlangen mit
Prioritäten, Zeitscheiben und Rückkopplung:
Seite 22
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Übung zum MFS Verfahren:
• Für das MFS Verfahren stehen 6
Warteschlangen zur Verfügung.
• Jeder Prozess in einer Warteschlange
bekommt seine eigene Zeitscheibe,
jedoch alle mit dem Quantum Q = 1.
• Jeder Prozess beginnt in der
Warteschlange 1. Wenn ein Prozess
nicht fertig wird, wandert er in die
nächst niedere (FIFO-)
Warteschlange.
0
1A
1
2
3
A
B
A
1B
2A
1C
4
5
6
7
8
9
Task
Ankunftszeit
Ausführungszeit
A
0 ms
6 ms
B
1 ms
2 ms
C
3 ms
3 ms
D
4 ms
6 ms
E
8 ms
1 ms
F
16 ms
1 ms
Übung: Zeichnen Sie den Ablauf der
einzelnen Tasks in ein Gantt-Diagramm
10
11
12
13
14
15
16
17
18
19
20
2B
Seite 23
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Round Robin Verfahren mit individueller Zeitscheibenlänge:
• Dauer der Zeitscheibe einer Task sollte proportional zu deren
Prozessorauslastung H = e/p sein
• Beispiel:
Task T1
Task
Periode pi
Ausführungszeit ei
H
Zeitscheibe
T1
10 ms
1 ms
10%
0,5 ms
T2
10 ms
5 ms
50%
2,5 ms
T3
15,4 ms
5,5 ms
36%
1,8 ms
0,5
0,5
0,5
0,5
Deadline
2,5
Task T2
2,5
1,8
Task T3
1,8
1,8
T1, T2
idle
0
Ereignis für T1, T2, T3
5
2,5
2,5
10
Ereignis für T1 und T2
Task ist
fertig
0,1
T3
15
T1, T2
20
t [ms]
Seite 24
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Vergleich der Verfahren FIFO und Round Robin anhand der Übungen:
•
Bei FIFO werden keine Prozesse verdrängt, das spart Prozesswechselzeiten
•
FIFO begünstigt lange Prozesse
•
RR begünstigt die Antwortzeiten bei kurzen Prozessen und benachteiligt die langen
Prozesse
•
Bei großen Zeitschlitzen geht RR über in FIFO
•
Bei kleinen Zeitschlitzen nimmt der Zeitaufwand für den Prozesswechsel überhand
•
Kleine Zeitschlitze bedeuten kurze Antwortzeiten
Seite 25
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS)) :
• Dynamisches Scheduling mit statischen Prioritäten
• präemptive und nicht-präemptive
Strategie ist möglich, wobei die
Task Ausführungszeit
präemptive Variante unter Umständen
die Einhaltung von Zeitbedingungen
A
8 ms
garantieren kann
B
5 ms
• Task mit höchster Priorität
C
2 ms
bekommt Prozessor
D
10 ms
• für harte Echtzeitsysteme
nur bedingt geeignet
Priorität
1 (höchste)
1 (höchste)
2
3
Bei Tasks mit gleicher Priorität: Weitere Bedingung nötig, z.B. FIFO
B
A
5
10
C
D
15
20
25
t [ms]
Seite 26
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS)) :
Rate monotonic scheduling (RMS) ist Spezialfall des Verfahrens und gilt für rein
periodische Anwendungen:
•
•
•
Priorität ist umgekehrt proportional zur Periodendauer, d.h. Task mit der kleinsten
Zykluszeit erhält die höchste Priorität
Präemptive Strategie
Task
Ausführungszeit
Periode
Einhaltung der Zeitschranken (Deadlines)
ist vorab überprüfbar, falls
A
10 ms
40 ms
–
–
–
•
Periodendauer ist konstant
und Zeitschranke = Deadline
Ausführungszeit ist
konstant und bekannt
Tasks sind voneinander
unabhängig (Keine Synchr.)
–
20 ms
50 ms
2
C
10 ms
80 ms
3
D
20 ms
100 ms
4
Task D wird unterbrochen
Erste geplante Ausführung aller Tasks bei t = 0 ms.
Danach werden die Tasks zyklisch wiederholt
A
ABCD
0
B
10
C
A
A
B
D1
B
50
AC
A
80
1
B
Beispiel:
–
Prio
C
BD
B
100
A
A
120
D2
t [ms]
Seite 27
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
• Beispiel für das RMS:
Task
Periode pi
Ausführungszeit ei
Priorität
1
150 ms
15 ms
2 (niedrig)
2
10 ms
1 ms
1 (hoch)
Präemption
2 ms
Task 1
Task 2
Präemption
4 ms
9 ms
1 ms
1 ms
idle
0
Ereignis
für Task 1
5
Ereignis
für Task 2
10
15
20
t [ms]
Ereignis
für Task 2
Seite 28
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
• Beispiel für das RMS:
– Worst Case: Ereignisse treten gleichzeitig auf
Task
Periode pi
Ausführungszeit ei
Priorität
1
150 ms
15 ms
2 (niedrig)
2
10 ms
1 ms
1 (hoch)
Task 1
Task 2
idle
0
Ereignis
für Task 1
und Task 2
5
10
Ereignis
für Task 2
15
20
t [ms]
Ereignis
für Task 2
Seite 29
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
Busy Period Analysis: Tritt bei periodischen Tasks keine Verletzung der Zeitschranken
bis zu dem Zeitpunkt auf, an dem der Prozessor das erste Mal in den Ruhezustand
geht, dann wir auch danach keine Verletzung der Zeitschranken mehr auftauchen.
(gilt für die o.g. Voraussetzungen, d.h. präemptiv, Periodendauer=konstant, ..)
RMS liefert für feste Prioritäten und Präemption für periodische Tasks mit Periode =
Deadline eine optimale Prioritätenzuordnung
RMS ist jedoch kein optimales Scheduling-Verfahren (s. Seite 4), aber es findet immer
einen ausführbaren Schedule, falls die Prozessorauslastung
H ≤ Hmax ist mit n = Anzahl der Tasks:
Seite 30
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
Beispiel: Transportsystem mit
– T1 = Kameradatenverarbeitung,
Task Periode pi
Ausführungszeit ei
– T2 = Motorsteuerung und
T1
10 ms
1 ms
– T3 = Transpondererkennung
T2
10 ms
5 ms
(aperiodische Task T3 wird mit
T3
15,4 ms
5,5 ms
Deadline periodisiert)
– H = e1/p1+ e2/p2 + e3/p3 = 95,71 %
– 2 mögliche Prioritätenfestlegung für T1 und T2, da p1 = p2:
H
10%
50%
36%
• T1 > T2 > T3
• T2 > T1 > T3
–
Es gibt keinen Schedule mit festen Prioritäten, denn
Seite 31
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
• Ablauf mit Prioritäten
Task Periode pi
Ausführungszeit ei
T1 > T2 > T3
Prio
T1
10 ms
1 ms
1
T2
10 ms
5 ms
2
T3
15,4 ms
5,5 ms
3
Präemption
1
Task T1
1
Deadline
5
Task T2
5
Task T3
T1, T2
idle
0
Ereignis für T1, T2, T3
5
Task ist
fertig
1,5
4
10
Ereignis für T1 und T2
T3
T1, T2
15 verpasst (um 2,1) 20
t [ms]
Seite 32
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
• Ablauf mit Prioritäten
Task Periode pi
Ausführungszeit ei
T2 > T1 > T3
T1
10 ms
1 ms
2
T2
10 ms
5 ms
1
T3
15,4 ms
5,5 ms
3
Präemption
1
1
Task T1
Prio
Deadline
5
Task T2
5
Task T3
T1, T2
idle
0
Ereignis für T1, T2, T3
5
Task ist
fertig
1,5
4
10
Ereignis für T1 und T2
T3
T1, T2
15 verpasst (um 2,1) 20
t [ms]
Seite 33
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Scheduling mit festen Prioritäten (fixed priority scheduling (FPS))
mit Rate monotonic scheduling (RMS):
•
•
•
Zuteilung der Prioritäten gemäß dem Rate Monotonic Prinzip ist essentiell!
Würde man keine Präemption zulassen oder die Prioritäten anders herum verteilen,
so würde im obigen Beispiel Task 2 ihre Zeitschranken verletzen.
Beispiel:
Task
Periode pi
Ausführungszeit ei Prioritäten
vertauscht
1
150 ms
15 ms
1 (hoch)
2
10 ms
1 ms
2 (niedrig)
Task 1
Task 2
Ereignis
für Task 1
und Task 2
Deadline für 1. Ausführung von Task 2
verpasst
Ereignis
für Task 2
Ereignis
für Task 2t [ms]
Seite 34
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren der kleinsten Restantwortzeit (earliest deadline first (EDF))
• Dynamisches Scheduling mit dynamischen Prioritäten, i.d.R. präemptiv
• Task mit kleinster Restantwortzeit
Task
Ausführungszeit Ankunfts
bekommt den Prozessor,
zeit
d.h. wo die Deadline am nächsten ist
A
10 ms
0 ms
• Optimales Scheduling-Verfahren,
B
10 ms
0 ms
das immer einen ausführbaren
C
30 ms
30 ms
Schedule findet, wenn H ≤ 100% ist
D
40 ms
50 ms
• Jedoch hoher Rechenaufwand
E
10 ms
70 ms
für das Scheduling
B
AB
0
A
10
D1
C
C
D
50
E
E
D2
Deadline
40 ms
30 ms
100 ms
200 ms
90 ms
t [ms]
100
Deadline von B ist früher als von A, und von E ist früher als von D (Präemption)
Seite 35
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren der kleinsten Restantwortzeit (earliest deadline first (EDF))
• Beispiel Transportsystem:
gemäß Busy Period Analysis
Task Periode pi
Ausführungszeit ei
werden die Zeitschranken auch
T1
10 ms
1 ms
in Zukunft eingehalten
Deadline T3=15,4; T1=T2=10
Prio
dyn.
T2
10 ms
5 ms
dyn.
T3
15,4 ms
5,5 ms
dyn.
Deadline T3=14,4; T2=9
Deadline T3=5,4; T1=T2=10
1
Task T1
1
Deadline
5
Task T2
5
Task T3
T1, T2
idle
0
Ereignis für T1, T2, T3
5
Task ist
fertig
1,5
5,5
10
Ereignis für T1 und T2
T3
15
T1, T2
20
t [ms]
Seite 36
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren des kleinsten Spielraums (least laxity first (LLF))
• Dynamisches Scheduling mit dynamischen Prioritäten, i.d.R. präemptiv
• Task mit kleinstem Spielraum (Laxity)
Task
Ausführungszeit Ankunfts
bekommt den Prozessor
zeit
• Optimales Scheduling-Verfahren
A
30 ms
0 ms
• Jedoch sehr hoher Rechenaufwand
B
10 ms
0 ms
• für harte Echtzeitsysteme
C
30 ms
30 ms
am besten geeignet
Laxity A=10; B=20
Laxity A=10; B=0
Deadline
40 ms
30 ms
100 ms
D
40 ms
50 ms
200 ms
E
10 ms
70 ms
90 ms
Laxity D=90; E=10
Merkregel:
B
A1
AB
0
10
C
A2
C
D
50
E
E
D
100
t [ms]
120
• Laxity der rechnenden
Task bleibt konstant
• Laxity der anderen
Tasks sinkt stetig
Seite 37
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren des kleinsten Spielraums (least laxity first (LLF))
• Beispiel Transportsystem:
Task Periode pi
Spielraum (Laxity): L1, L2 und L3
T1
10 ms
Grob-Darstellung: in ms statt 1/10 ms
L1=9, L2=5, L3=9,9
L1=9, L2=5, L3=3,9
L1=5, L2=5, L3=5,9
Prio
1 ms
dyn.
T2
10 ms
5 ms
dyn.
T3
15,4 ms
5,5 ms
dyn.
L1=8, L2=4, L3=3,9
L1=4, L3=4,9
L1=7, L2=3
L3=3,9
L1=3, L2=3
1
1
Task T1
Ausführungszeit ei
Deadline
5
Task T2
5
Task ist
fertig
5,5
Task T3
T1, T2
idle
0
Ereignis für T1, T2, T3
5
10
Ereignis für T1 und T2
T3
15
T1, T2
20
t [ms]
Seite 38
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren des kleinsten Spielraums (least laxity first (LLF))
• Beispiel Transportsystem:
Task Periode pi
Spielraum (Laxity): L1, L2 und L3
T1
10 ms
Fein-Darstellung: in 1/10 ms
T2
10 ms
– Schon bei 4 ms beginnt
T3
15,4 ms
der Taskwechsel in 0,1 Schritten
Ausführungszeit ei
Prio
1 ms
dyn.
5 ms
dyn.
5,5 ms
dyn.
Seite 39
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren Guaranteed Percentage Scheduling (GP)
• Dynamisches, präemptives Scheduling ohne Prioritäten
• Jeder Task wird fester Teil des Prozessors zugewiesen, d.h. feingranulares
Round Robin mit HW-Unterstützung
• Optimales Scheduling-Verfahren auf Einprozessorsystemen: H=100%
• Tasks sind zeitlich isoliert, laufen gleichmäßig ab und starten sofort
• Periodendauer unabhängig von der Anzahl der Tasks
• für harte Echtzeitsysteme gut geeignet
•
...
Beispiel: Threads
Periode = 100 Taktzyklen
Thread A
30 Taktzyklen
Thread B
20 Taktzyklen
Thread C
40 Taktzyklen
100 Taktzyklen
Thread A, 30%
Thread B, 20%
Thread C, 40%
Thread A
Thread B
30 Taktzyklen 20 Taktzyklen
Thread C
40 Taktzyklen
...
100 Taktzyklen
Seite 40
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Verfahren Guaranteed Percentage Scheduling (GP)
• Beispiel: Transportsystem
Task
Periode pi
Ausführungszeit ei
H
T1
10 ms
1 ms
10%
T2
10 ms
5 ms
50%
T3
15,4 ms
5,5 ms
36%
Task T1
Deadline
Task T2
Task ist
fertig
Task T3
T1, T2
idle
0
Ereignis für T1, T2, T3
5
10
Ereignis für T1 und T2
T3
15
T1, T2
20
t [ms]
Seite 41
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Okt 2014
5) Realzeitscheduling
Übung zum Scheduling-Verfahren
Gegeben ist nebenstehender Taskplan.
Bitte füllen Sie die u.s. Tabelle entsprechend des
geforderten Scheduling -Verfahrens aus:
1.
FIFO
2.
Round Robin
3.
Earliest Deadline
4.
Least Laxity
Task
Dauer
in ms
Ankunftszeit
in ms
Deadline
in ms
A
20
10
100
B
10
10
30
C
20
0
50
D
30
30
100
E
20
60
90
In dem Fall, dass Prioritäten gesetzt werden müssen, soll dies gemäß der Buchstabenreihenfolge im
Alphabet erfolgen. Falls eine Zeitscheibe notwendig ist, ist diese mit 10 ms anzunehmen.
10 ms
20 ms
30 ms
40 ms
50 ms
60 ms
70 ms
80 ms
90 ms
100 ms
1.
2.
3.
4.
Seite 42
Document
Kategorie
Technik
Seitenansichten
4
Dateigröße
1 188 KB
Tags
1/--Seiten
melden