Echtzeitsysteme – Weiche Echtzeit
6.1 Einführung
Echtzeitsysteme
Sommersemester 2016
6.1 Einführung
▸
Bisher: Jeder Job muss Deadline einhalten
▸
Nicht immer günstig:
▸
Echtzeitsysteme
▸
▸
6. Kapitel
▸
Weiche Echtzeit
Weichere“ Ansätze:
” ▸
▸
▸
Prof. Matthias Werner
▸
Professur Betriebssysteme
Spiegelt nicht immer die Realität
Verbraucht ggf. zuviel Ressourcen
Nicht realisierbar
Verminderte Pünktlichkeit
Verminderte Qualität (QoS)
Verminderte Garantien
Allgemein gilt:
Doing hard realtime is hard...
... but doing soft realtime is much harder!
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.1 Einführung
6.2 Reduzierte Pünktlichkeit
Skip-Over
Anmerkung
Soft real-time problems could fill an own course. Thus, we consider few typical approaches only.
▸
▸
Idee [KS95]
So lange es nicht zu viele sind, können ab und zu Jobs ihre Deadline verpassen und im
Ganzen übersprungen werden.
Idee: Verminderte Pünktlichkeit
Ansätze:
▸
Jobs werden gelegentlich ausgelassen
Zeit-Wert-Funktionen statt harter Deadlines
▸
Modellannahmen
▸
▸
▸
Idee: Verminderte Qualität
Ansätze:
▸
▸
▸
▸
▸
▸
Tasks haben optionale Komponenten, die unterbrochen werden können
Mehrere Versionen (Primary/Backup) eines Programms
▸
Akzeptanz, dass zugrundeliegende Annahmen werden (nicht immer) garantiert
werden
Probabilistische Garantien
SoSe 2016 ⋅ M. Werner
▸
n periodische Tasks Ti (ei , Pi )
präemptive Zuteilung
1 Prozessor
Vorgegebener Skip-Faktor si
Definition 6.1 (Skip-Faktor)
Idee: Verminderte Garantien
Ansätze:
▸
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Ansätze
▸
2 / 37
3 / 37
osg.informatik.tu-chemnitz.de
Der minimale zeitliche Abstand zwischen den Startpunkten zweier Jobs einer
periodischen Task Ti , die ausgelassen werden können, beträgt stets Pi ⋅ si .
SoSe 2016 ⋅ M. Werner
4 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Skip-Faktor
Ansatz
Unterscheidung von roten und blauen Jobs
▸
▸
▸
P
rote Jobs: müssen Deadline einhalten
blaue Jobs: können ausgelassen werden
▸
Unterschiedliche Ergebnisse, je nachdem ob mit blauem oder rotem Job gestartet
wird
▸
Schlechtester Fall: alle Tasks starten mit dem jeweiligen Maximum an roten Jobs
á alle blauen Jobs als jeweils letzte der Periode geplant (tiefrotes System).
t
Theorem 6.2
▸
▸
Die Entscheidung, ob eine gegebene Taskmenge mittels Skip-Over ausführbar ist, ist
N P-hart.
Hier: Skip-Faktor si = 4
Allgemein: 2 ≤ si ≤ ∞
▸
▸
si = 1 á aperiodische Task
si = ∞ á kein Skipping
Beweis: siehe [KS95]
▸
SoSe 2016 ⋅ M. Werner
5 / 37
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Lastgrenze
Beispiel 1
n
Notwendige Bedingung bleibt: U = ∑
▸
Allerdings ist ei nicht bei jedem Job konstant
á effektive Last: e′i = sis−1
⋅ ei
i
T1
▸
Es folgt
T3
i=1
Beispiel 1: n = 5, Ti (0.25, 1) und si = 5
▸
ei
Pi
▸
≤ 1,
J1,1
T2
J2,1
ei (si − 1)
U =∑
⋅
≤ 1.
si
i=1 Pi
J5,1
▸
osg.informatik.tu-chemnitz.de
J4,2
J3,3
J1,5
J3,4
J3,5
J4,4
J5,3
J4,5
J5,5
J5,4
2
J1,6
J2,4 J2,5
J4,3
J5,2
1
J1,4
J2,3
J3,2
J4,1
0
J1,3
J2,2
J3,1
T5
n
7 / 37
J1,2
T4
Theorem 6.3 (Lastgrenze bei Skip-Over [notwendige Bedingung])
SoSe 2016 ⋅ M. Werner
6 / 37
3
4
5
t
U = 1, System (geradeso) planbar
SoSe 2016 ⋅ M. Werner
8 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Beispiel 2
▸
▸
Beispiel 3
T1 (1, 1) mit s1 = 10 und T2 (0.05, 1) mit s2 = ∞
Last: u = 0.95 < 1
▸
T1 (1, 1) mit s1 = 10 und T2 (1, 15) mit s2 = ∞
▸
U=
29
30
= 0.96
T1
T1 braucht spätestens in der 2. Periode die gesamte Rechenzeit
T2 hat gleiche Periode wie T1
á Taskmenge ist nicht ausführbar
▸
▸
T2
0
▸
2
9 / 37
osg.informatik.tu-chemnitz.de
12
t
10 / 37
osg.informatik.tu-chemnitz.de
Optimalität von RTO
▸
Bisher nur die Möglichkeit von Schedules betrachtet
▸
Wie gelangt man zum Schedule?
Ansatz: Red Tasks Only (RTO)
Theorem 6.5 (Optimalität von RTO)
RTO ist im allgemeinen Fall nicht optimal.
▸
1. Rote Jobs werden nach EDF geplant
2. Blaue Jobs werden nicht geplant
Beweis von Theorem 6.5:
▸
▸
Theorem 6.4 (Spezielle Optimalität von RTO)
▸
Im tiefrotem Modell ist RTO optimal.
▸
Beweis von Theorem 6.4 á Heimarbeit/Übung (wer will, schaue in [KS95] nach)
SoSe 2016 ⋅ M. Werner
10
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Red Tasks Only (RTO)
▸
8
Aber: Last ist größer als im Beispiel 2
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
▸
6
System ist planbar, da im Skip von T1 eine Aktivierung von T2 rechtzeitig
komplettiert werden kann
▸
SoSe 2016 ⋅ M. Werner
4
11 / 37
osg.informatik.tu-chemnitz.de
Nutzen Gegenbeispiel:
Taskmenge T = {T1 , T2 }, T1 = (6, 4) und T2 = (4, 3) mit s1 = s2 = 2
Betrachten interessantes Intervall [0, 24]
Wenn System tiefrot, dann ist T nicht planbar, da entweder T1 oder T2 seine jeweils
erste Deadline verpasst
Restliche Startkonfigurationen“:
”
▸
▸
Jobs von T1 : J11 (0, 6, 4), J12 (6, 12, 4), J13 (12, 18, 4), J14 (18, 24, 4)
Jobs von T2 : J21 (0, 4, 3), J22 (4, 8, 3), J23 (8, 12, 3), J24 (12, 16, 3),
J25 (16, 20, 3), J26 (20, 24, 3)
SoSe 2016 ⋅ M. Werner
12 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Optimalität von RTO (Forts.)
Optimalität von RTO (Forts.)
▸
Entstehende Schedules:
J12
J11
T1
J14
▸
J21
T2
0
2
J22
4
6
J24
8
10
12
14
Aber: T ist ausführbar:
J26
16
18
20
22
24
J1,1
T1
T1
J11
T2
J21
0
2
J12
J22
4
6
J11
T1
J24
8
10
0
2
12
14
16
18
6
8
J1,3
J1,4
22
J2,2
J2,3
J2,4
J2,5
J2,6
24
J14
J23
4
20
J2,1
T2
J26
J12
J21
T2
J1,2
J13
10
12
á Gegenbeispiel gefunden, Theorem 6.5 ist bewiesen
J25
14
16
18
20
22
24
á nicht unter RTO ausführbar!
SoSe 2016 ⋅ M. Werner
13 / 37
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Beispiel
▸
Betrachten alternativen Algorithmus: Blue When Possible (BWP)
▸
Algorithmus:
▸
▸
▸
beliebig
blauer job mit der spätesten Deadline
blauer job mit frühester Deadline á EDF
blauer job, dessen nächster roter Job die früheste Deadline hat
...
J1,1
15 / 37
6
J2,2
2
7
J1,3
T2
0
J1,4,b
J1,4,a
7
4
6
6
J2,3
8
10
J2,5
12
14
16
18
J2,6
20
22
24
Merke!
Beispielsweise ist die Taskmenge von Folie -12 unter BWP und Strategie 4 für die
blauen Jobs ausführbar
SoSe 2016 ⋅ M. Werner
J1,2,b
J1,2,a
T1
Rote Jobs werden nach EDF geplant
Blaue Jobs werden ausgeführt, wenn sie die Komplettierung eines roten Jobs nicht
behindern
Die Planung der blauen Jobs kann nach verschiedenen Kriterien erfolgen, z. B.:
1.
2.
3.
4.
5.
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Blue When Possible (BWP)
▸
14 / 37
osg.informatik.tu-chemnitz.de
Wenn ein blauer Job komplettiert wird, wird die folgende Instanz dieser Task blau.
SoSe 2016 ⋅ M. Werner
16 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.2 Pünktlichkeit
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
Diskussion
6.3 Reduzierte QoS
Idee
▸
▸
▸
▸
Blaue Jobs werden im Hintergrund“ ausgeführt
”
Bessere Ausnutzung der Prozessorzeit
▸
Es gibt Probleme, bei denen mit längerer Laufzeit ein besseres“ Ergebnis erzielt
”
werden kann
BWP kann jede Taskmenge ausführen, die unter RTO ausführbar ist á BWP ist für
tiefrote Taskmengen ebenfalls optimal
▸
Unterschiedliche Laufzeiten je nach Situation einsetzen
▸
Zwei Ansätze:
Es gibt weitere Heuristiken, die unter Berücksichtigung der Laufzeit noch bessere
Ergebnisse erbringen
▸
▸
Betrachten letzteren Ansatz
▸
SoSe 2016 ⋅ M. Werner
17 / 37
osg.informatik.tu-chemnitz.de
Primary/Backup
Increased reward with increased service – IRIS
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
18 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
IRIS
Scheduling von IRIS-Tasks
Ziel:
▸
▸
IRIS – Increased reward with increased service
Modell: Task besteht aus zwei Teilen
▸
▸
▸
▸
Obligatorischer Teil (mandatory portion): Dieser Teil der Task muss bis zur Deadline
ausgeführt werden (kann auch leer sein)
Optionaler Teil (optional portion): Dieser Teil der Task kann ausgeführt werden, wenn
die Zeit es zulässt
▸
Ergebnisse nach der Deadline haben keinen Wert; Task beendet Ausführung
spätestens mit der Deadline
Laufzeit kann variieren
SoSe 2016 ⋅ M. Werner
19 / 37
Gesamtnutzen:
▸
▸
Unterschied zu Scheduling mit Werte-Funktion:
▸
▸
osg.informatik.tu-chemnitz.de
Deadlines müssen eingehalten werden (d.h. alle obligatorischen Teile müssen
ausgeführt werden)
Maximierung des Nutzens
ist Funktion der Nutzenfunktionen der einzelnen Tasks (beispielsweise
gleichwertige Aufsummierung)
kann zielgerichtet durch verschiedene Bewertung einzelner Tasks parametrisiert
werden
Komplexität:
▸
Allgemein wieder N P
▸
Es existieren Spezialfälle mit optimalen Lösungen
SoSe 2016 ⋅ M. Werner
20 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
Nutzen einer IRIS-Task
Nutzen einer IRIS-Task (Forts.)
Modell:
R(x)
⎧
≤0
⎪
⎪
⎪
R(t) = ⎨ r(t)
⎪
⎪ r(to + tm )
⎪
⎩
⇐ t < tm
⇐ tm ≤ t ≤ to + tm
⇐ to + tm < t
dabei:
r(t) Nutzen (reward) der Bedienzeit t
tm Länge des obligatorischen Teils
to Maximal mögliche Länge des optionalen Teils, danach keine Verbesserung des Ergebnisses
mehr möglich
Nebenbedingung:
SoSe 2016 ⋅ M. Werner
21 / 37
Zeit x
m
!
tc,o ≤ td
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.3 QoS
22 / 37
o
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Identische, lineare Nutzenfunktionen
6.4 Verminderte Garantien
Betrachten Spezialfall: Identische, lineare Nutzenfunktionen
▸
▸
Zerlegung der Task Ti in Mi (obligatorischer Teil) und Oi (optionaler Teil) als
Teiltasks
Erstelle Schedule St nach EDF für T
▸
▸
Sonst: Erstelle Schedule Sm nach EDF für M = {M1 , . . . , Mn }
▸
▸
Wenn St ausführbar á fertig (optimaler Schedule)
Wenn Sm nicht ausführbar á Es gibt keinen Schedule
Sonst:
▸
Beginnend von Sm , minimieren der Idle-Zeiten durch Verschieben der Tasks und
Ausnutzen der freien Zeiten für die Ausführung (beliebiger) optionaler Teile der Tasks
SoSe 2016 ⋅ M. Werner
23 / 37
osg.informatik.tu-chemnitz.de
Idee
Harte“ Echtzeit-Ansätze können in Systemen genutzt werden, in denen die
”
grundlegenden Annahmen nicht gewährleistet sind, solange die Annahmen meist
funktionieren.
▸
Nutzung von Standardsystemen (comercial off-the-shelf systemen, COTS)
▸
Wie können wir ein COTS etwas mehr“ echtzeitfähig machen?
”
SoSe 2016 ⋅ M. Werner
24 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Betrachten COTS Scheduling
▸
▸
▸
▸
Benutzung eines Scheduling Servers“
”
(Fast) jedes Betriebssystem arbeitet mit verschiedenen Prioritätsebenen und
Prioritäts-Scheduling
Diese Prioritäten können benutzt werden, wenn man Mechanismen wie Aging und
Priority-Boosts abschaltet (fixed priority scheduling)
Scheduling obliegt OS-Scheduler
Probleme:
▸
▸
▸
▸
▸
▸
▸
▸
Betriebssysteminterne Prozesse hoher Priorität können stören“
”
Abbildung auf Prioritäten ist nicht einfach, da Bereich begrenzt ist (muss oberhalb
aller anderen Prioritäten liegen)
Implementation des OS-Schedulers nicht immer bekannt
Systeminterne Abläufe sind nicht immer bekannt
SoSe 2016 ⋅ M. Werner
25 / 37
Benutzung der Prioritäten des Betriebssystems als Grundlage
Nutzung der beiden höchsten Prioritätsebenen für die Implementation eines
Echtzeit-Schedulers“ für die Verwaltung der zeitkritischen Tasks
”
Scheduling der Echtzeit-Tasks“ obliegt Scheduling Server
”
Funktion:
▸
▸
osg.informatik.tu-chemnitz.de
Scheduling Server läuft periodisch auf höchster Priorität
Manipuliert Prioritäten der anderen Prozesse so, dass zweite Prioritätsstufe für
Echtzeit-Tasks benutzt wird
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
26 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Scheduling Server – Funktion
Scheduling Server – Vorteile
priority
31
Scheduling
Server
kernel
tasks
interactive
tasks
▸
Keine Modifikationen am Betriebssystem erforderlich
▸
Keine Kenntnis des Source-Codes erforderlich
▸
Scheduling Server kann intern beliebige Schedulingverfahren implementieren
▸
System bleibt (mit reduzierter Leistung) für Nicht-Echtzeit-Aufgaben benutzbar
▸
Leistung für Echtzeit-Tasks weitgehend konstant
realtime
tasks
time
SoSe 2016 ⋅ M. Werner
27 / 37
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
28 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Scheduling Server – Nachteile
▸
Scheduling Server – Anforderungen an OS
Abläufe im Betriebssystemkern sind nicht vollständig bekannt, damit
unvorhersehbare Einflüsse möglich
▸
Benutzung von Systemaufrufen kann unvorhersehbare Auswirkungen auf das
zeitliche Verhalten haben
▸
Scheduling Server kann Systemprozesse behindern (z.B. grafische Oberflächen)
▸
Für harte Echtzeit nicht geeignet
SoSe 2016 ⋅ M. Werner
29 / 37
osg.informatik.tu-chemnitz.de
▸
(Near) Fixed Priority Scheduling
▸
Möglichkeit, Scheduling Politiken umzuschalten
▸
Möglichkeit, Prioritäten umzuschalten
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
30 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Scheduling Server – Implementationen
Scheduling Server – Mach
thread_t th_id;
mutex_t th_list_lock;
condition_t new_th_reg;
Auf folgenden Plattformen wurde die Idee des Scheduling Servers implementiert und
untersucht (u.a.):
▸
Mach (NeXTStep/Darwin)
▸
Solaris
▸
rtLinux 0.x
▸
LynxOS 3.0
▸
Windows NT
while(TRUE) {
mutex_lock(th_list_lock);
while ((th_id = next_edf(thread_list)) == THREAD_NULL)
condition_wait(new_th_reg, th_list_lock);
/* set scheduling policy and quantum, resume thread */
thread_policy(th_id, POLICY_FIXEDPRI, time_rt);
thread_resume(th_id);
thread_priority(th_id,real_time_prio,FALSE);
/* handoff scheduling, real−time thread runs until its quantum expires */
thread_switch(th_id, SWITCH_OPTION_DEPRESS, 0);
thread_suspend(th_id);
mutex_unlock(th_list_lock);
/* give remains of the system a chance, invoke Mach scheduler */
thread_switch(THREAD_NULL, SWITCH_OPTION_WAIT, time_os);
}
SoSe 2016 ⋅ M. Werner
31 / 37
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
32 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Scheduling Server – Stabilität mit Last
▸
▸
Anwendung auf eine Multimedia-Anwendung
Messung mit Linpack
System: NeXTStep 3.3
▸
Multimedia-Anwendungen haben weiche Echtzeit-Anforderungen
▸
Verletzung dieser Anforderungen führt zu verminderter oder inakzeptabler
Qualität
Beispiel: MPEG-Player
MFLOPS
▸
▸
▸
▸
SoSe 2016 ⋅ M. Werner
33 / 37
osg.informatik.tu-chemnitz.de
auf unbelastetem System benutzbar
Belastung des Systems führt zu reduzierter verfügbarer Rechenleistung á
unakzeptables Resultat
Scheduling Server sorgt für annährend garantierte Rechenzeit für MPEG-Player
SoSe 2016 ⋅ M. Werner
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
34 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
6.4 Garantien
Anwendung auf eine Multimedia-Anwendung (Forts.)
Scheduling Server – Erfahrungen
MPEG-player
average frame distance with increasing load
t in ms
▸
Alle Teile einer zeitkritischen Anwendung müssen unter Kontrolle des Scheduling
Servers laufen
▸
Benutzung von Systemdiensten vermeiden, die auch von anderen Prozessen
benutzt werden
▸
Synchronisation in einer Applikation muss mit Scheduling Server abgestimmt
werden
▸
Parameter des Scheduling Servers (Scheduling-Periode und High/Low-Verhältnis)
bestimmen Vorhersagbarkeit sehr und müssen an Applikation angepasst werden
450
400
350
300
250
200
150
100
50
0
0 processes
no Scheduling Server
SoSe 2016 ⋅ M. Werner
5 processes
10 processes
10/30 high/low prio phase
35 / 37
osg.informatik.tu-chemnitz.de
SoSe 2016 ⋅ M. Werner
36 / 37
osg.informatik.tu-chemnitz.de
Echtzeitsysteme – Weiche Echtzeit
Anhang A: Literatur
Anhang A: Literatur
[KS95]
Gilad Koren und Dennis Shasha. Skip-Over: Algorithms and Complexity for Overloaded
”
Systems that Allow Skips“. In: Proceedings of the 16th IEEE Real-Time Systems
Symposium. Pisa, Italy, Dez. 1995, S. 110–117
[KS97]
C. M. Krishna und Kang G. Shin. Real-Time Systems. McGraw-Hill, 1997, Section 3.3
[Pol96]
Andreas Polze. How to Partition a Workstation“. In: Proceedings of 8th IASTED/ISMM
”
International Conference on Parallel and Distributed Computing and Systems. Chicago, 1996
SoSe 2016 ⋅ M. Werner
37 / 37
osg.informatik.tu-chemnitz.de
© Copyright 2024 ExpyDoc
