CSI
Technische Universität Ilmenau
www.tu-ilmenau.de
-
Verteilte Echtzeit-Systeme
Hans-Albrecht Schindler
Wintersemester 2018/19
Teil C: Echtzeit-Betriebssysteme
Abschnitt 8:
Off-line-Scheduling von Echtzeitprozessen und
Scheduling aperiodischer Echtzeit-Prozesse
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 28. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Off-line-Scheduling: Prinzipielles
Vollständiger Schedule:• bereits beim Entwurf des Systems entwickelt (d.h. vor irgendeiner
Aktivierung)
• wird System als Tabelle übergeben
Konsequenzen:1. Run-Time-System (z.B. Pseudo-Betriebssystem):
enthält keinen on-line-Scheduling-Algorithmus2. benötigt:
nur Dispatcher, der Prozesse oder Pseudo-Prozesse entsprechend
Zeitangaben in Tabelle ausführt
3. für off-line-Scheduling-Algorithmus:
auch lange Laufzeiten möglich, da diese nicht zu Run-Time-Overhead führen
4. Prozesse (oder Pseudo-Prozesse):
benötigen hier keine Prioritäten
8.1 Vorbemerkungen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 38. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Off-line-Scheduling: Prinzipielles
Entwicklung des Schedule:a) mehr oder weniger empirischb) mit speziellem (oft optimalem) Algorithmus
Anwendung:• kleine unkomplizierte Echtzeitsysteme
• typisch: harte Echtzeitanforderungen
• Hyperperiode oder nur einmalige Aktivierung
Implementierung:• möglich: 2 Varianten
a) Zeit gesteuert
b) basiert auf konstanten Zeitslots
Vorbemerkungen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 48. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
8.2 Empirischer Schedule für zeitgesteuerte Implementierung
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
camera sensor robot monitor
force
vision display
control
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 58. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Empirischer Schedule für zeitgesteuerte Implementierung
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
Echtzeitanwendung• beinhaltete 4 Prozesse• müssen noch um Bearbeitungszeit Ci ergänzt werden
damit: folgende Tabelle
Hinweis:
1. Periodendauer für Pcontrol auf 30 ms leicht erhöht (nur Darstellungsgründe)
Pforce
Ti
Ci
Pvision Pcontrol Pdisplay
20 ms 80 ms 30 ms 60 ms
5 ms 20 ms 9 ms 6 ms
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 68. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
Entwicklung des Schedule
• notwendig: Auslastungsuntersuchung der Prozessoren
1 Prozessor: maximale Auslastung 100%
Berechnung:
U: Utilization (Auslastung)
= 5/20 + 20/80 + 9/30 + 6/60
= 25% + 25% + 30% + 10%
= 90% prinzipiell Schedules realisierbar
Empirischer Schedule für zeitgesteuerte Implementierung
=n
i = 1
UCi
Ti
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 78. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
Empirischer Schedule für zeitgesteuerte Implementierung
Bild 8-1: Empirisch entwickelter Schedule u. alternativer Schedule (angedeutet)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 88. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Empirischer Schedule für zeitgesteuerte Implementierung
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
bei Schedule-Entwicklung beachten Fristen: dürfen niemals überschritten werden!!
Frage: Besondere Behandlung weicher Echtzeitprozesse?
( )
Hyperperiode• im Beispiel: nach 240 ms wiederholt sich Gesamtvorgang
• Bereich bis 240 ms: Hyperperiode
• zur Steuerung der Prozessumschaltung:
System muss Prozess-Startzeiten innerhalb der 1. Hyperperiode als Tabelle erhalten
Pdisplay
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 98. Scheduling aperiodischer Echtzeit-Prozesse / 8.1 Vorbemerkungen
Empirischer Schedule für zeitgesteuerte Implementierung
Ein Beispiel: Weiterbetrachtung Roboterarm nach Abschn. 3
Tabelle:
Zeitpunkt Starten Prozess
0 Pforce
5 Pdisplay
11 Pcontrol
20 Pforce
25 Pvision
45 Pforce
50 Pcontrol
… …
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 10
Vorbemerkungen
Beispiel
• zeigte: empirische Ermittlung von Schedules möglich
• besser: Verwendung von Algorithmen
• dabei: oft Algorithmen mit nachgewiesener Optimalität
8.3 Algorithmen zum Off-line-Scheduling f. aperiod. Prozesse
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.2 Notation nach Graham u. Lawler
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 11
| |
Notation von Graham u. Lawler
1 | prec | Lmax
1-Prozessor-
Maschine
Prozessmenge mit Restriktionen
durch Vorrang-Beziehungen
(precedence)(keine weiteren Einschränkungen:
Verdrängung erlaubt
beliebige Ankunftszeiten)
Minimierung des
Maximalwertes der
Unpünktlichkeit
(Lateness)
Lmax = max (fi – di)
Rechner-
charakteristik Charakteristika der Prozessmenge
(typischerweise: Einschränkungen)
Optimalitäts-
Kriterium
Beispiel:
Algorithmen zur off-line-Ermittlung für aperiodische Prozesse
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.2 Notation nach Graham u. Lawler
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 12
3 | no-preem | fi
3-Prozessor- keine Verdrängung Minimierung der
Maschine (keine Vorrang- od. Summe der
Ressourcen-Restriktionen, Beendigungszeiten
beliebige Ankunftszeiten)
2 | sync | Latei
2-Prozessor- synchrone Minimierung der
Maschine Ankunftszeiten, Anzahl verspäteter
keine weiteren Prozesse
Restriktionen
Notation von Graham u. Lawler – weitere Beispiele
Notation nach Graham u. Lawler
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.2 Notation nach Graham u. Lawler
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 13
8.4 Scheduling nach Jackson (EDD: „Earliest Due Date“ )
1 | sync | Lmax Maximalwert der
Unpünktlichkeit minimieren
Lmax = maxi(fi - di)
Scheduling-Bedingungen
alle Prozesse:• … haben synchrone Ankunftszeiten
(d.h. werden zur gleichen Zeit bereit)
Rechenzeit-Bedarf u. Frist unterschiedlich für jeden Prozess
keine weiteren Restriktionen: unabhängige Prozesse (keine Reihenfolge-Restriktionen,
keine Restriktionen durch Ressourcenbenutzung)
Verdrängung:
kein Thema, da alle Prozesse zur gleichen Zeit bereit
(Verdrängung nur sinnvoll bei dynamischen Ankunftszeiten, wenn neu hinzukommende Prozesse höhere Priorität als
laufende haben können.)8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 14
Li : Unpünktlichkeit (Lateness) Li = fi – di
Zeitquantum, das Prozess bezogen auf Frist zu spät bzw. „zu früh“
beendet wird (bei Beendigung vor Frist: Li negativ)
LiLi
bei Frist-Über-
schreitung
ohne Frist-
Überschreitung
a i s i f i d i
t
Prozess
Pi
C i
Scheduling nach Jackson (EDD)
Bild 8-2: Zur Erinnerung: Unpünktlichkeit („Lateness“)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Scheduling-Bedingungen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 15
Theorem von Jackson (1955)
Jeder Algorithmus, der Prozesse in Reihenfolge nicht
abnehmender Fristen ausführt, ist optimal. (beweisbar)
ein möglicher Algorithmus: EDD : Prozesse in Reihenfolge ansteigender Fristen ausgeführt
(≡ EDF bei synchronen Ankunftszeiten)
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 16
Darstellungen nach [Buttazzo97] S.55 – Bild 3.3
P1 P2 P3 P4 P5
Ci 1 1 1 3 2
di 3 10 7 8 5
0
P 5P 1 P 4P 3 P 2
d1 d2d3 d4d5
Lmax = L4 = -1
t
1 2 3 4 5 6 7 8 9 10 11
P1 P2 P3 P4 P5
Ci 1 2 1 4 2
di 2 5 4 8 6
0
P 3P 1 P 5P 2 P 4
d1 d2 d5 d4d3
t
1 2 3 4 5 6 7 8 9 10 11
Lmax = L4 = 2
Bild 8-3: durch EDD erzeugter „brauchbarer“ Plan (feasible schedule)
Bild 8-4: durch EDD erzeugter „unbrauchbarer“ Plan (infeasible schedule)
Darstellungen nach [Buttazzo97] S. 55 - Bild 3.2
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 17
P4 kann Frist nicht einhalten!
Optimalität u. Ausführbarkeit
Optimalität von EDD:kann nicht Ausführbarkeit eines gefundenen Schedules garantieren!
Optimalität:garantiert nur, dass – falls ausführbarer Schedule existiert – dieser durch
EDD gefunden wird!
Beispiele:a) Bild 8-2: brauchbarer, optimaler Schedule mit minimierter
Unpünktlichkeit mit Lmax = L4 = -1
b) Bild 8-3: unbrauchbarer Schedule, optimiert bezgl. Minimum der
Unpünktlichkeit mit Lmax = L4 = 2
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 18
Garantiebedingungen für ausführbaren Schedule
Falls Optimalitätskriterium ≠ feasible schedule:
• notwendig: gesonderte Untersuchung nach fristengerechter
Ausführbarkeit des Schedules(gilt auch für weitere Verfahren)
zu zeigen: im „worst case“ werden alle Prozesse vor ihrer Frist beendet
D.h. für jeden Prozess muss gelten:
fi di , i = 1, ..., n
(worst-case-Beendigungszeit Frist)
Wenn gilt: Prozesse P1, P2, ...Pn seien in Reihenfolge nichtabnehmender Fristen
geordnet, ist worst-case-Beendigungszeit leicht berechenbar:
=
i
k 1
fi = Ck
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 19
i = 1, ..., n Ck di=
i
k 1
Garantietest
Verifizierung folgender n Bedingungen:
Weiteres zu EDD• siehe Übungsblatt 2 / Aufgaben 1 u. 5
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 20
Scheduling nach Jackson (EDD)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.3 Scheduling nach Jackson (EDD)
Bild 8-5: Scheduling nach Jackson: ungeeignet für periodische Prozesse
Planungsversuch für Roboterarm-Beispiel
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 21
8.5 Scheduling nach Horn – EDF
1 | preem | Lmax
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.4 Scheduling nach Horn (EDF)
Scheduling-Bedingungen u. Theorem
anders als bei EDD: anstelle synchroner Ankunftszeiten: Ankunftsprozess
Horn‘sches Theorem (1974)
Jeder Algorithmus, der in jedem Moment aus Menge aller
rechenbereiten Prozesse den mit frühester absoluter Frist ausführt, ist optimal in Bezug auf Minimierung des Maximalwertes
der Pünktlichkeit
wegen Ankunftsprozess: Verdrängung wird wichtig
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 22
Scheduling-Bedingungen u. Theorem
Lösung u. Scheduling-Verfahren • siehe EDF im Abschnitt 9 („Scheduling rein periodischer Echtzeitprozesse“)
Da für EDF nur die Fristen maßgebend sind, unterscheidet das
Verfahren bei der Ablaufplanung (Schedule-Erstellung) nicht
zwischen periodischen u. aperiodischen Prozessen!
Damit: alle Angaben, Beweise u. Garantie-Bedingung unverändert gültig!(alle weiteren Ausführungen zu EDF im Abschnitt 9)
Weiterhin• EDF kann sowohl für off-line-Scheduling (wenn alle Prozess-
Parameter im Voraus bekannt sind) als auch für on-line-Schedulingverwendet werden (Hierbei müssen die Prozess-Parameter nicht im
Voraus bekannt sein.)
Scheduling nach Horn – EDF
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.4 Scheduling nach Horn (EDF)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 23
Darstellung nach /Buttazzo97/ Bild 3.6 S.60
Bild 8-6: Beispiel-Schedule nach EDF für aperiodische Echtzeitprozesse
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.4 Scheduling nach Horn (EDF)
Scheduling nach Horn – EDF
6
P4
P3
P2
P1
P5
0 7 8 9 104 52 31t/Zeitein-
heiten
P1 P2 P3 P4 P5
ai 0 0 2 3 6
Ci 1 2 2 2 2
di 2 5 4 10 9
Prozess-Parameter:
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 24
Verdrängung – generelle Bemerkung
Allgemein:
Ein Scheduling-Problem ist bei erlaubter Verdrängung leichter lösbar!
Dazu: Vergleich mit nicht-präemptivem Scheduling-Algorithmus
Hierbei:
Scheduler muss sichern, dass neu hinzukommender Prozess nie
laufenden Prozess unterbrechen muss, um eigene Frist einzuhalten
Dazu erforderlich:
beachtlicher Suchaufwand!
• bei erlaubter Verdrängung:
dieser Aufwand nicht erforderlich!
Scheduling nach Horn – EDF
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.4 Scheduling nach Horn (EDF)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 25
8.6 Prozessorleerlauf- u. -nicht-Leerlauf-Algorithmen
Algorithmen ohne Verdrängung
Beispiel: EDF im nichtpräemptiven Fall
Obwohl Schedule ohne Fristüberschreitung existiert (Fall a), findet EDF diesen nicht (Fall b).
Darstellung nach /Buttazzo97/ Bild 3.8 S.62
8. Sched. Aperiod. Echtz.-Proz. / 8.5 Prozessorleerlauf- u. –nicht-Leerlauf-Algorithmen
0 74 5 62 31
0 74 5 62 31
P1
P1
P2
P2
Optimaler
Schedule
EDF-
Schedule
t
t
t
t(a)
(b)
P1 P2
ai 0 1
Ci 4 2
di 7 5
Bild 8-7: Ohne Verdrängung: EDF liefert keinen optimalen Schedule
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 26
Algorithmen ohne Verdrängung
Fazit:
EDF für nichtpräemptiven Fall kein optimaler Algorithmus!
bei optimalem Schedule (a):
Prozessor zunächst im Leerlauf, obwohl P1 rechenbereit
bei EDF anders:
EDF ist Nichtleerlauf-Algorithmus!
Prozessorleerlauf- u. -nicht-Leerlauf-Algorithmen
8. Sched. Aperiod. Echtz.-Proz. / 8.5 Prozessorleerlauf- u. –nicht-Leerlauf-Algorithmen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 27
Prozessorleerlauf- u. -nicht-Leerlauf-Algorithmen
Algorithmen ohne Verdrängung
Generelle Erkenntnis:
Ohne Vorauskenntnis aller Prozess-Ankunftszeiten:kann kein on-line-Algorithmus entscheiden
• soll er bei Vorliegen rechen-bereiter Prozesse
a) rechnen – oder
b) noch im Leerlauf bleiben
Zusatzbemerkung:
Bei Beschränkung auf Nichtleerlaufalgorithmen:
ist EDF auch im nicht-präemptiven Fall noch optimal!(Beweis 1991)
8. Sched. Aperiod. Echtz.-Proz. / 8.5 Prozessorleerlauf- u. –nicht-Leerlauf-Algorithmen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 28
8.7 Scheduling unter Vorrang-Restriktionen
8. Sched. aperiodischer Echtzeit-Prozesse / 8.6 Scheduling unter Vorrang-Restriktionen
Bemerkungen
für Prozessmengen mit Vorrang-Restriktionen:
Auffinden optimaler Schedules im Allgemeinen NP-hart.
unter speziellen Bedingungen:optimale Algorithmen mit nur polynomialer Komplexität auffindbar
Beispiel-Algorithmen
• 2 Algorithmen mit Minimierung der maximalen Unpünktlichkeit
1. Latest Deadline First (LDF)
Einschränkung: synchrone Ankunftszeiten
2. EDF* (modifiziertes EDF)
Einschränkung: Verdrängung erlaubt
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 29
8.8 Latest Deadline First (LDF)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.7 Latest Deadline First (LDF)
Scheduling-Bedingungen
Vorrang-Restriktionen synchrone
(precedence constraints) Ankunftszeiten!!
Vorgehensweise /Lawler, 1973/
Bei gegeb. Prozessmenge u. gegeb. gerichtetem azyklischen Graphen: Schedule von hinten nach vorn aufbauen
1 | prec, sync | Lmax
t
PL-1 PL
Richtung für Aufbau des Schedules
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 30
Latest Deadline First (LDF)
Algorithmus
im Zyklus {
aus den Prozessen ohne Nachfolger bzw. deren Nachfolger schon
eingeplant sind,
wähle den mit der spätesten Frist
}
( Bild )
Bemerkungen1. optimaler Algorithmus (beweisbar)2. Komplexität O(n2)
t
PL-1 PL
Richtung für Aufbau des Schedules
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.7 Latest Deadline First (LDF)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 31
P1 P2 P3 P4 P5 P6
Ci 1 1 1 1 1 1
di 2 5 4 3 5 6
P5P4
gerichteter
azyklischer
Graph
5
35 6
4
2
P2 P5
0 1 2 3 4 5 6 7
d1 d4 d3 d2 d5 d6
Lmax = L4 = 1EDF
t
P4 P5
d1 d4 d3 d2 d5 d6LDF
Lmax = 0
0 1 2 3 4 5 6 7
t
Darstellung nach /Buttazzo97/ Bild 3.13 S.70
Zum
Vergleich:
P1 P3 P4 P6
P1
P1
P2
P2
P3
P3
P6
P6
Bild 8-8: Vergleich von Ablaufplänen nach EDF u. LDF
Prozessmenge für beide
Verfahren:
Latest Deadline First (LDF)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.7 Latest Deadline First (LDF)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 32
LDF
Erkenntnis: unter Vorrang-Restriktionen ist EDF nicht optimal!
Latest Deadline First (LDF)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.7 Latest Deadline First (LDF)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 33
8.9 EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Scheduling-Bedingungen
(wie LDF)
Entwickler: / Chetto, Silly, Bouchentouf, 1990 /
Grundidee: Transformation einer Menge abhängiger Prozesse in Menge
unabhängiger Prozesse
durch Modifikation aller Ankunftszeiten u. Fristen, so dass kein Prozess vor seinem Vorgänger starten bzw. seinen
Nachfolger verdrängen kann
1 | prec, sync | Lmax
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 34
Modifikation der Ankunftszeiten (release times)
bei 2 Prozessen mit
Pa Pb (Pa unmittelbarer Vorgänger von Pb )
gilt in jedem gültigen Schedule – der Vorrangbeziehungen einhält:
1. sb rb Pb kann nicht vor seinem Bereitwerden starten
2. sb ra + Ca Pb darf nicht vor der minimalen Beendigungszeit
seines unmittelbaren Vorgängers starten
( Skizze umseitig)
Deshalb kann Pb – ohne Änderung der Problemstellung – als neue
Ankunftszeit erhalten:
rb* = max ( rb, ra + Ca )
EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 35
Modifikation der Ankunftszeiten
Aufwand:Modifikationsalgorithmus für alle betroffenen Prozesse:
Komplexität O(n2)
Pb
Pa
ra rb sb da db
sb rb
sb ra + Ca
ra + CaCa
Cb
rb* rb
Bild 8-9: Zur Modifikation der Ankunftszeiten
EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 36
Modifikation der Fristen (deadlines)
wiederum für
Pa Pb (Pa unmittelbarer Vorgänger von Pb )
muss bei den Fristen analog gelten:
1. fa da Pa muss spätestens zu seiner Frist beendet sein
2. fa db – Cb Pa muss spätestens zur maximal möglichen
Startzeit von Pb beendet sein
( Skizze umseitig)
Deshalb ergibt sich für Pa als neue Frist – ohne Änderung der
Problemstellung:
da* = min ( da, db - Cb )
EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 37
Modifikation der Fristen (deadlines)
Aufwand:Modifikationsalgorithmus für alle betroffenen Prozesse:
Komplexität O(n2)
Optimalität:EDF* – unter angegebenen Bedingungen – optimal (beweisbar!)
Ca
Pb
PaCb
ra rb fa
da
dbfa da
fa db - Cb db - Cb
da*
da
Bild 8-10: Zur Modifikation der Fristen
EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 38
Modifikation der Fristen (deadlines)
Beispiel:siehe Übungsblatt 2/Aufgabe 4
EDF mit Vorrang-Restriktionen (EDF*)
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.8 EDF mit Vorrang-Restriktionen (EDF*)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 39
8.10 Branch-and-Bound-Algorithmen (Suchbäume)
Suchbäume
bei Prozessen mit vorbekannten Ankunftszeiten:
die typische Herangehensweise zur Lösung nichtpräemptiver
Scheduling-Probleme
Ziel dieser Algorithmus-Klasse:Auffinden von Teilbäumen, die aussführbare Schedules darstellen
(nicht alle Teilbäume stellen ausführbare Schedules dar ....)
Optimaler Algorithmus:• bei n Prozessen: „ermüdende“ Analyse von n! Pfaden der Länge n• Komplexität: O(n . n!)
• für Systeme mit hoher Prozess-Anzahl: nicht auswertbar!
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.9 Branch-and-Bound-Alg. (Suchbäume)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 40
Suchbäume
„Ausweg“:• Suche nach Algorithmen mit Begrenzung des Suchraumes
• damit: Verminderung der Komplexität
Branch-and-Bound-Algorithmen
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.9 Branch-and-Bound-Alg. (Suchbäume)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 41
Darstellung nach /Buttazzo97/ Bild 3.9 S.63
FFF
leerer Schedule
Teil-Schedule
brauchbarer Schedule
(feasible schedule)
vollständiger
Schedule
Bild 8-11: Suchbaum zur Ermittlung eines nichtpräemptiven Schedules
Branch-and-Bound-Algorithmen
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.9 Branch-and-Bound-Alg. (Suchbäume)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 42
Praxistaugliche Algorithmen
1. Variante: Suchalgorithmus nach Bratley• benutzt zusätzliche Information, um Bäume zu „beschneiden“
Komplexität im Durchschnittsfall reduziert
2. Variante: Spring-Algorithmus• Verwendung von Heuristiken, um versprechendem Pfad zu folgen
• heuristische Algorithmen:
können in „polynomialer Zeit“ ausführbaren Schedule entwickeln garantieren aber nicht, ihn zu finden, weil sie nicht alle
möglichen Lösungen untersuchen ...
Branch-and-Bound-Algorithmen
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.9 Branch-and-Bound-Alg. (Suchbäume)
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 43
beliebige Ankunftszeiten
8.11 Algorithmus nach Bratley (1971)
1 | no_preem | feasible
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.10 Algorithmus nach Bratley
Scheduling-Bedingungen
Algorithmus: im Zyklus {
• untersuche, ob durch Hinzufügen irgendeines weiteren Knotens
am betrachteten Teilbaum Fristverletzung auftreten kann
• falls ja: gehe um einen Knoten zurück und betrachte
neuenTeilbaum• Abbruchkriterium: ein(!) ausführbarer Schedule ermittelt
}
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 44
Scheduling-Bedingungen
Bewertung/Komplexität:• „Baum-Beschneidungs-Techniken“ (pruning) zur Verkleinerung des
Suchraumes im Allgemeinen sehr effizient
• aber: worst-case-Komplexität noch immer O(n.n!)
Anwendung:
• nur für off-line-Scheduling verwendbar
• alle Prozess-Parameter – einschließlich Ankunftszeitpunkte – müssen
im Voraus bekannt sein(z.B. bei zeitgesteuerten Systemen)
Beispiel: siehe Übungsblatt 2 / Aufgabe 2
Algorithmus nach Bratley
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.10 Algorithmus nach Bratley
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 45
P1 P2 P3 P4
ai 4 1 1 0
Ci 2 1 2 2
di 7 5 6 4
P2†
P4† P2
†
P1†P3
†
P3†
P4†
P3†
1
1
1 1
1
1
2
23
3 3
4
43223
34
4
5
6
666
6
6
7
Pi†
Nummer innerhalb des Knotens:eingeplanter Prozess
Nummer außerhalb des Knotens:Beendigungszeit
... Prozess, der seine Frist verpasst
... ausführbarer Schedule
Darstellung nach /Buttazzo97/ Bild 3.10 S.65
Bild 8-12: Suchbeispiel entsprechend Bratley-Algorithmus
Algorithmus nach Bratley
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.10 Algorithmus nach Bratley
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 46
Vorbemerkungen
Spring-Algorithmus• Scheduling-Algorithmus – implementiert im Betriebssystem Spring
Betriebssystem Spring• „hartes“ Echtzeit-Betriebssystem
• University of Massachusetts: Stankovic & Ramamritham, ca. 1990• für kritische Regelungsapplikationen in dynamischen Umgebungen
Ziel des Algorithmus• Auffinden eines ohne Fristüberschreitung ausführbaren Schedules für
Prozesse mit unterschiedlichen Arten von Restriktionen
8.12 Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 47
Vorbemerkungen
Behandelbare Restriktionen• Vorrang-Beziehungen
• Betriebsmittelrestriktionen
• beliebige Ankunftszeiten
• keine Verdrängung (Nichtpräemptivität)
• Wichtigkeitsebenen• …
Problematik:• im allgemeinen Fall: NP-hart
behandelbar gemacht:
durch heuristischen Ansatz – in Form von heuristischer Funktion
für allgemeinen Fall:
verteilte
Rechnerarchitekturen
Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 48
Heuristische Funktion H steuert Suche nach brauchbarem Schedule
dirigiert Suche auf plausiblen Pfad
mittels H: Scheduling-Strategie sehr flexibel definier- bzw. änderbar
H = a First Come First Served (FCFS)
H = C Shortest Job First (SJF)
H = d Earliest Deadline First (EDF)
Darstellung nach /Buttazzo97/ Bild 3.11 S.67
H = Test Earliest Start Time First (ESTF)
H = d + w C EDF + SJF
H = d + w Test EDF + ESTF
Tabelle 8-1: Beispiele für die heuristische Funktion H des
Spring-Algorithmus
Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 49
Vorgehensweise
Ausgangspunkt: partieller Schedule
1. ermittle H für alle noch zu planenden Prozesse
2. füge Prozess mit niedrigstem H als nächsten in Schedule ein
zu ermitteltender Schedule: ausführbar im strengen Sinne*
* ausführbar im strengen Sinne (strongly feasible):
Partieller Schedule – erweitert um beliebigen der verbliebenen
Prozesse – muss gleichfalls noch ausführbar sein
Falls ein Teil-Schedule nicht brauchbar im strengen Sinne ist –stoppt Algorithmus
Es kann dann Backtracking ausgeführt werden:
Suche wird vom vorhergehenden Teil-Schedule mit Prozess
mit zweit-niedrigstem H-Wert weitergeführt. (Maximalzahl möglicher Backtracks muss jedoch begrenzt werden)
Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 50
Komplexität
O(n2) (ohne Backtracking)
1. brauchbarer Schedule: enthält n Knoten (Prozesse)
2. für jeden Teil-Schedule: maximal n heuristische Funktionen zu
bestimmen
Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 51
Betrachtung von Betriebsmittelrestriktionen / Test
Jeder Prozess Pi muss binäres Ressourcen-Array für nicht-entziehbare,
exklusiv-genutzte Ressourcen deklarieren:
wenn partieller Schedule vorliegt:
für jede Ressource Rk wird frühester Zeitpunkt ermittelt, zu dem diese
verfügbar ist:
• EATk (earliest available time)
Dann ist Test(i) (earliest start time für Prozess Pi ), an dem dieser
Ausführung beginnen kann, ohne an Ressource blockiert zu werden:
• Test(i) = max [ai, max (EATk)] mit ai : Ankunftszeit von Pi
Ri = [R1 (i), ... Rr(i)] mit: Rk(i) = 0 – falls Pi Rk nicht benutzt
Rk(i) = 1 – falls Pi Rk benutzt
Spring-Algorithmus
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 52
Spring-Algorithmus
Betrachtung von Betriebsmittelrestriktionen / Test
Mit Suchstrategie ESTF („earliest start time first“), d.h.
• H = Test
wird jeweils Prozess mit kleinstem Test als nächster ausgewählt
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 53
Spring-Algorithmus
Vorrang-Restriktionen
Berücksichtigung möglich durch: Hinzufügen eines Summanden E zur
Funktion H:
• H* = H + E ( E ... Eligibility = Teilnahme-/Startberechtigung )
Hierbei gilt:
• Ei Ti kann nicht zur Weiterführung eines Teil-Schedulesverwendet werden
(Vorgänger im Vorranggraphen nicht beendet)
• Ei = 1 alle Vorgänger jetzt beendet, Ti kann jetzt verwendet werden
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 54
Spring-Algorithmus
zusammengesetzte Funktionen
benutzbar: zur Integration weiterer wichtiger Informationen über
Prozess
Beispiele:
H = d + w C EDF + SJF
Frist Rechenzeitbedarf
Gewichtsfaktor für unterschiedliche
Applikations-Umgebungen
H = d + w Test EDF + ESTF
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 55
Komplexität: O(k·n) linear, Anzahl der Prozesse
mit k = const. k << n n ... Anzahl der Prozesse
Spring-Algorithmus
weitere Reduzierung der Komplexität
Für als brauchbar im strengen Sinne ermittelten Teil-Schedule:
• H wird nur für k Prozesse mit frühesten Fristen berechnet (nicht für
alle)
dann gilt:
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 56
Spring-Algorithmus
Hauptnachteil eines heuristischen Scheduling-Ansatzes
nicht optimal:
d.h. falls brauchbarer Schedule existiert, kann es sein, dass ein
heuristischer Algorithmus (wie Spring-Algorithmus) diesen nicht findet
Beispiel-Anwendung zum Spring-Algorithmus• siehe Übungsblatt 2 / Aufgabe 3
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.11 Spring-Algorithmus
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 57
1. Es wurden verschiedenartige Algorithmen zur Einplanung von aperiodischen
Prozessen an 1-Prozessor-Maschinen besprochen (gewisse Ausnahme:
Spring-Alg.), so dass für spezielles Problem am besten geeigneter Algorithmus
ausgewählt werden kann. (Tabelle 8-2)
2. Jeder Algorithmus stellt dabei eine Lösung für ein spezielles Scheduling-
Problem dar (ausgedrückt durch eine Menge von Annahmen/Einschränkungen
bezüglich der Prozessmenge u. ein Optimalitätskriterium).
3. Diese Restriktionen reduzieren die Komplexität ( Berechenbarkeit).
4. Ohne restriktive Annahmen kann die Komplexität auch durch heuristische
Ansätze reduziert werden. Die können aber nicht garantieren, eine optimale bzw. überhaupt eine Lösung zu finden, selbst wenn sie existiert.
5. Obwohl die Verfahren für 1-Prozessor-Rechner vorgestellt wurden, können
viele für Multiprozessor- bzw. Multirechner-Architekturen erweitert werden.
8.13 Abschließende Bemerkungen
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.12 Abschließende Bemerkungen
Verteilte Echtzeitsysteme:
© ws 2018/19 H.-A. Schindler Folie: 8 - 58
Zusammenfassung: Scheduling-Algorithmen für aperiodische Prozesse
Darstellung nach /Buttazzo97/ Bild 3.17 S.75
EDD (Jackson ́ 55) EDF (Horn ´74) Tree search(Bratley ´71)
O(n log n) O(n2) O(n . n!)
optimal optimal optimal
EDF * Spring(Stankovic
LDF (Lawler ´73) (Chetto et al.´90) & Ramamritham ´87)
O(n2) O(n2) O(n2)
optimal optimal heuristisch
Un
ab
hä
ng
ige
Pro
ze
sse
synchrone Aktivierung
Pro
ze
sse
mit R
estr
iktio
ne
n
du
rch
Vo
rra
ng
-
Be
zie
hu
ng
en
präemptive
asynchrone Aktivierungnicht-präemptive
asynchrone Aktivierung
ENDE Abschnitt 8
8. Scheduling aperiodischer Echtzeit-Prozesse / 8.12 Abschließende Bemerkungen
Tabelle 8-2: Behandelte Verfahren (Übersicht)