Dieter Zobel¨ - userpages.uni-koblenz.dezoebel/EZmat/Skript/Core.pdf · Echtzeitsysteme Dieter Zobel¨ Universitat Koblenz-Landau¨ Fachbereich Informatik, Institut fur Softwaretechnik¨

Echtzeitsysteme

Dieter Zobel

Universitat Koblenz-LandauFachbereich Informatik, Institut fur Softwaretechnik

Inhaltsverzeichnis

1 Einfuhrung 21.1 Merkmale von Echtzeitsystemen . . . . . . . . 3

1.1.1 Harte und weiche Echtzeitbedingungen 61.1.2 Determiniertheit und Vorhersagbarkeit . 111.1.3 Sicherheit und Zuverlassigkeit . . . . . 12

1.2 Das Grundmodell eines Echtzeitsystems . . . . 161.2.1 Paradigmatische Beispiele . . . . . . . 171.2.2 Aktionen und Akteure . . . . . . . . . . 201.2.3 Eingebettete Systeme . . . . . . . . . . 21

1.3 Prozesse . . . . . . . . . . . . . . . . . . . . . 261.3.1 Rechenprozesse . . . . . . . . . . . . . 271.3.2 Regelungstechnik . . . . . . . . . . . . 31

1.4 Echt und Zeit . . . . . . . . . . . . . . . . . . . 33

1.4.1 Schnelligkeit und Rechtzeitigkeit . . . . 341.4.2 Zeit auf dem Rechensystem . . . . . . . 371.4.3 Echtzeit . . . . . . . . . . . . . . . . . . 40

1.5 Beispiele . . . . . . . . . . . . . . . . . . . . . 41

2 Echtzeitplanung 452.1 Grundlagen der Echtzeitplanung . . . . . . . . 46

2.1.1 Prozessmodelle . . . . . . . . . . . . . 472.1.2 Prozessparameter . . . . . . . . . . . . 542.1.3 Echtzeitplanung . . . . . . . . . . . . . 60

2.2 Planen durch Suchen . . . . . . . . . . . . . . 702.3 Planen nach Fristen . . . . . . . . . . . . . . . 752.4 Planen nach Spielraumen . . . . . . . . . . . . 852.5 Planen nach festen Prioritaten . . . . . . . . . 882.6 Planen nach monotonen Raten . . . . . . . . . 902.7 Planen nach monotonen Fristen . . . . . . . . 992.8 Planen nach dem Server-Modell . . . . . . . . 103

2.8.1 Server fur feste Prioritaten . . . . . . . 1052.8.2 Server fur dynamische Prioritaten . . . 106

2.9 Zyklische Planungsverfahren . . . . . . . . . . 1072.10 Vergleich der Planungsverfahren . . . . . . . . 109

3 Betriebssysteme 1103.1 Merkmale von Echtzeitbetriebssystemen . . . . 111

i

3.2 Aufbauprinzipien . . . . . . . . . . . . . . . . . 1193.3 Speicherverwaltung . . . . . . . . . . . . . . . 1243.4 Datei und Gerateverwaltung . . . . . . . . . . . 1283.5 Treiber . . . . . . . . . . . . . . . . . . . . . . . 1323.6 Unterbrechungen . . . . . . . . . . . . . . . . . 1363.7 Beispiele fur Echtzeitbetriebssysteme . . . . . 139

3.7.1 Solaris . . . . . . . . . . . . . . . . . . . 1403.7.2 VxWorks . . . . . . . . . . . . . . . . . 1413.7.3 QNX . . . . . . . . . . . . . . . . . . . . 1433.7.4 POSIX . . . . . . . . . . . . . . . . . . . 1463.7.5 µITRON . . . . . . . . . . . . . . . . . . 1513.7.6 OSEK/VDX . . . . . . . . . . . . . . . . 0

4 Synchronisierung 24.1 Grundlagen . . . . . . . . . . . . . . . . . . . . 34.2 Prioritatsumkehr . . . . . . . . . . . . . . . . . 134.3 Prioritatsvererbung . . . . . . . . . . . . . . . . 174.4 Prioritatsobergrenzen . . . . . . . . . . . . . . 214.5 Ubersicht zur Prioritatsinversion . . . . . . . . 24

5 Rechnernetze 265.1 Grundlagen . . . . . . . . . . . . . . . . . . . . 275.2 Grundlagen . . . . . . . . . . . . . . . . . . . . 28

5.2.1 Formale Strukturen von Rechnernetzen 29

5.2.2 Aufbau von Rechnernetzen . . . . . . . 315.2.3 Drahtgebundene und drahtlose Rech-

nernetze . . . . . . . . . . . . . . . . . 395.3 Zugriffsprotokolle . . . . . . . . . . . . . . . . . 40

5.3.1 Zentralisierte Verfahren . . . . . . . . . 415.3.2 Arbitrationsverfahren . . . . . . . . . . . 425.3.3 Markengesteuerte Verfahren . . . . . . 445.3.4 Zeitmultiplex-Verfahren . . . . . . . . . 455.3.5 Modifikation nicht echtzeitfahiger Zu-

griffsprotokolle . . . . . . . . . . . . . . 465.4 Abschatzung der Echtzeiteigenschaften . . . . 51

5.4.1 Prozesse und Zugriffsprotokolle . . . . 525.4.2 Zeitgesteuerte Zugriffsprotokolle . . . . 585.4.3 Arbitrierende Zugriffsprotokolle . . . . . 625.4.4 Markengesteuerte Zugriffsprotokolle . . 72

6 Planung fur Mehrprozessorsysteme 776.1 Einfuhrung und Modellbildung . . . . . . . . . . 786.2 Anwendbarkeit klassischer Planungsverfahren 806.3 Proportional faires Scheduling . . . . . . . . . 936.4 Affinitaten zwischen Prozessen und Prozessoren102

6 Modellbildung 766.1 Entwurfsmuster . . . . . . . . . . . . . . . . . . 77

ii

6.2 Modellierungssprachen und Zustandsautomaten 816.3 Logiken und Algebren . . . . . . . . . . . . . . 826.4 Petri-Netze . . . . . . . . . . . . . . . . . . . . 83

7 Zeiten und Uhren 847.1 Echtzeit und physikalische Zeit . . . . . . . . . 857.2 Uhren und Wecker . . . . . . . . . . . . . . . . 907.3 Uhrsynchronisierung . . . . . . . . . . . . . . . 977.4 Ausfuhrungzeiten von Anweisungen . . . . . . 103

7.5 Ableitung von Zeitbedingungen . . . . . . . . . 104

8 Rechnerarchitekturen und Prozessoren 105

9 Programmiersprachen 106

10 Softwaretechnik 107

11 Nachlese 108

iii

Kapitel 6

Planung fur Mehrprozessorsysteme

• Modellbildung bei Mehrprozessorsysteme

• Anwendbarkeit klassischer Verfahren der Echtzeitplanung

• spezielle Planungsverfahren fur Mehrprozessorsysteme

Beachte: Die Modellbildung und Echtzeitplanung bei Mehrkernprozessoren ist weit-gehend identisch zu der bei Mehrprozessorsystemen, wie sie bereits seit den 70-gerJahren zur Erreichung hoherer Rechnerleistung entwickelt und eingesetzt wurden.

77

EchtzeitsystemeKAPITEL 6. PLANUNG FUR MEHRPROZESSORSYSTEME

6.1 Einfuhrung und ModellbildungKernfrage:

Klassische Echtzeitplanung geht von Rechnerplattformen mit einem Prozessoraus. Langst haben jedoch die Mehrkernprozessoren den Markt erobert undstehen fur die Entwicklung von Echtzeitanwendungen bereit. Es stellt sich so-mit die Frage, ob die klassischen Methoden der Echtzeitplanung unmittelbarauf Rechnerplattformen mit mehreren Kernen ubertragen werden konnen oderganz neue Methoden der Echtzeitplanung zu entwickeln sind.

Folgende Antwort steht im Raum [12]:

Few of the results obtained for a single processor generalize directly to the mul-tiple processor case; bringing in additional processors adds a new dimensionto the scheduling problem. The simple fact that a task can use only one proces-sor even when several processors are free at the same time adds a surprisingamount of difficulty to the scheduling of multiple processors.

Dieter Zobel 6.1 - 1 2


Modellbildung

Wenn nicht anders beschrieben, wird davon ausgegangen, dass alle vorhandenen Ker-ne eines Mehrkernprozessors gleich sind. Insgesamt sei die Zahl der Kerne fest undmit m bezeichnet.Handelt es sich um eine Prozessmenge P periodischer Prozesse mit, dann ist dieAuslastung in folgender Weise zu berechnen:

U =

n∑i=1

∆ei∆pi

In diesem Sinne ist die Bedingung U ≤ m eine notwendige Vorraussetzung fur dieBrauchbarkeit einer Prozessmenge P .



6.2 Anwendbarkeit klassischer PlanungsverfahrenFur die Planung bei Mehrprozessorsyste-me stellt sich die Frage, inwiefern sichhierfur die grundlegenden Planungsver-fahren eignen. Wegen der Dominanz derperiodischen unterbrechbaren Prozessestehen die Planungsverfahren RMS (bzw.DMS), EDF und LLF bei einer solcheBetrachtung im Vordergrund. Alle dieseVerfahren basieren auf Prioritaten, unter-scheiden sich dabei aber in den Zeitpunk-ten, zu denen die Prioritaten vergebenoder verandert werden.• (RMS) Die Prioritatenzuordnung ist

statisch. D.h., sie ist fur alle Pro-

zessausfuhrungen gleich.

• (EDF ) Die Prioritatszuordnung istdynamisch. D.h., sie wird bei je-der Startzeit fur die nachste Pro-zessausfuhrung festgelegt.

• (LLF ) Die Prioritatszuordnung ist dy-namisch. D.h., sie kann, im Ge-gesatz zu EDF, wahrend der Pro-zessausfuhrung verandert werden. ImFolgenden ist der Mindestabstand zwi-schen zwei Anderungen der Prioritatauf die Bezugszeitspanne ∆tG festge-setzt.



Dhall-Effekt

Sehr fruh schon wurde festgestellt, dass sich die klassiischen Verfahren fur Einprozes-sorsysteme nicht auf den Mehrkernfall ubertragen lassen. Hier spricht man auch vomDhall-Effekt [18], was folgendermaßen belegt werden kann:Beispiel: Anwendung von EDF auf m + 1 Prozesse und m Kerne:

P ∆e ∆p

1 2ε 1

: : :m 2ε 1

m + 1 1 1 + ε

Unter EDF werden zunachst die Prozesse 1 bis mauf den m Prozessoren verplant. Dann bleibt je-doch auf keinem der Prozessoren mehr genugendZeit, um den Prozess m mit seiner 1 + ε lan-gen Ausfuhrungszeit zu verplanen. Diese Fristver-letzung passiert bei einer Auslastung von:

U =1

m + 1



Migrationseigenschaften von Prozessen (1)

Ein anderes Kriterium, das bei derPlanung bei Mehrprozessorsysteme zuberucksichtigen ist, betrifft die Fahigkeitder Prozesse, von Prozessorkern zu Pro-zessorkern migrieren zu konnen:• (NoM) Ausschluss von Migration,

d.h. Prozesse werden fest zu Pro-zessorkernen zugeordnet. Hier sprichtman auch von der Partitionierung derProzessorkerne unter den Prozessen.

• (ExM) Migration von einer Pro-zessausfuhrung zur nachsten.

• (PrM) Migration wahrend der Pro-zessausfuhrung.

In der Literatur spricht man bei der Partitio-nierung auch von static binding, wahrenddie beiden anderen Varianten unter demBegriff global binding zusammengefasstwerden.




Eine weitergehende Klassifizierung der Migrationseigenschaften findet man bei [24].Hier wird neben partitioniert und global weiterhin unterschieden zwischen:

• clustered: Zunachst werden die Prozessoren in disjunkte Mengen, sogenannteCluster, zerlegt. Prozessobjekte (tasks) werden fest genau einem Cluster von Pro-zessoren zugeordnet, wo ihre Prozessausfuhrung (job) stattfinden kann.

• arbitrary processor affinity oder kurz APA: Jedes Prozessobjekt (tasks) kann ei-ner beliebigen Menge von Prozessoren zugeordnet werden. Entspechend dieserZuordnung kann die Prozessausfuhrung (job) stattfinden.

Beachte: Die beschriebenen Zuordnungen sind orthogonal zu den Zeitpunkten, wanndiese Zuordnung gesetzt werden kann. Das bedeutet, dass der Zeitpunkt der Vergabevon Prioriaten nach TLFP, JLFP oder JLDP1 festgelegt sein kann.

1Den Akronymen sind folgende Bedeutungen zugrunde gelegt: task level fixed priority bedeutet feste Zuordnung von Prioritaten wie beispielsweiseunter RMS, job level fixed priority steht fur die Vergabe einer festen Prioritat fuir eine Prozessausfuhrung wie bei EDF und schließlich meint job leveldynamic priority standig anderbare Prioritaten wie unter LLF.




Die nachfolgende Darstellung macht deut-lich, dass die globale und das parti-tionierte Zuordnung von Prozessobjektenzu Prozessoren Spezialfalle der Cluster-orientierten Zuordnung sind. Jene wieder-um ist ein Spezialfall der APA-orientiertenZuordnung.

Anders als bei [10] wird bei [24] die strik-te Orthogonalitat von Zuordnung von Pro-zessen zu Prozessoren einerseits und derzeitlichen Gultigkeit der Zuordnung zu Pro-zessobjekten oder Prozessausfuhrungenandererseits betont. Deshalb wird der An-satz von [24] spater in Unterkaptel Affi-nitaten zwischen Prozessen und Pro-zessoren noch einmal aufgegriffen.



Inklusionsbeziehungen (1)

Beide Kriterien, Auswahl des Planungsverfahrens und Fahigkeit zur Migration nach[24], sind unabhangig voneinander. Somit kann ein spezielles Planungsverfahren A

bei einem Mehrprozessorsystem, das einen speziellen Grad B der Migration von Pro-zessen zulasst, angewendet werden. Auf diese Weise ergeben sich bereits (3 × 3)

Moglichkeiten der Kombinationen von Planungsverfahren. Um diese vergleichen zukonnen, soll FA,B ⊂ 2P fur die Menge der Prozessmengen stehen, die unter einerKombination (A,B) einen brauchbaren Plan s besitzen.

Wahrend fur Einprozessorsysteme FRMS ⊂ FEDF = FLLF gilt, sind die brauchbarenProzessmengen bei den Verfahren RMS, EDF und LLF angewandt auf Mehrprozes-sorsysteme unterschiedlich.



Inklusionsbeziehungen (2)Die Kombination (RMS,ExM) steht fur ein Planungsverfahren nach monotonen Ra-ten, wobei die Prozessausfuhrung auf wechselnden Prozessorkernen stattfinden kann.Gegeben sei die Prozessmenge P = {1, 2, 3, 4} bei m = 2 Prozessorkernen und denProzessparametern:

P ∆e ∆p

1 2 62 3 53 1 44 2 3



Inklusionsbeziehungen (3)Die Zuordnung des Prozessorkerns erfolgt zur fruhstmoglichen Startzeit des Prozes-ses und bleibt dann fur die gesamte Zeitspanne dieser Prozessausfuhrung bestehen.Betrachtet man Prozess 1, dann wird er in seiner ersten Periode ab dem Zeitpunkt 2auf dem Prozessor 2 ausgefuhrt. In der nachsten Periode ist es der Zeitpunkt 8, abdem Prozess 1 auf Prozessor 1 ausgefuhrt wird.




Betrachtet werden die Kombinationen(LLF, PrM) und (EDF,PrM). Gegebensei die Prozessmenge P = {1, 2, 3} beim = 2 Prozessoren und den Prozesspa-rametern:

P ∆e ∆p

1 2 32 2 33 2 3

Es gilt unmittelbar: P ∈ FLLF,PrM

Nach jeweils ∆tG erfolgt eine neue Berech-nung der Prioritaten, um die jeweils beidenhochstpriorisierten Prozesse auf den vor-handenen Prozessoren auszufuhren.

Eine vergleichbare Auswahl der Prozes-se findet zwar auch bei der Kombination(EDF,PrM) statt, gilt dann jedoch fur diegesamte Ausfuhrung. So ergibt sich, dasseiner der drei Prozesse fruhestens zumZeitpunkt 2 starten kann und seine Fristverletzt. Also gilt: P 6∈ FEDF,PrM




Von RMS uber EDF bis hin zu LLF unterliegt die Planung fur Ein- und Mehrprozessor-systeme immer weniger Einschrankungen. Bezogen auf einen festen Grad der Migrati-on von Prozessen herrscht deshalb eine einfache und einsichtige Inklusionsbeziehung(vgl. [10]):

FRMS,X ⊂ FEDF,X ⊂ FLLF,X X ∈ {NoM,ExM,PrM}

Betrachtet man hingegen mehrere Grade der Migration von Prozessen fur ein einzel-nes Verfahren, dann findet sich keine gleichermaßen einfache Inklusionsbeziehung.So kann es sein, dass bei einem Planungsverfahren A und zwei Graden B1 und B2

der Migration weder FA,B1 ⊂ FA,B2 noch FA,B2 ⊂ FA,B1 erfullt ist.




Zwei Prozessmengen P und Q werdenmiteinander verglichen. Zunachst wird dieProzessmenge P = {1, 2, 3} beim = 2 Pro-zessoren und den folgenden Prozesspara-metern betrachtet:

P ∆e ∆p

1 3 62 3 63 6 7

Unter der Kombination (RMS,NoM) lasstsich die Prozessmenge so partitionieren,dass die Prozesse 1 und 2 auf dem Pro-

zessor 2 und Prozess 3 auf dem Prozessor1 ausgefuhrt wird. Es gibt keine Fristverlet-zung:

Unter der Kombination (RMS,ExM) sinddie beiden Prozesse 1 und 2 zum Zeit-punkt 6 bereit und erhalten die Prozesso-ren 2 und 1. Prozess 3 wird deshalb seineFrist verletzen. Somit gilt: P ∈ FRMS,NoM

und P 6∈ FRMS,ExM




Fur eine andere Prozessmenge Q =

{1, 2, 3} ergibt sich die umgekehrte Bezie-hung: Q 6∈ FRMS,NoM und Q ∈ FRMS,ExM .Sei m = 2 und Q haben die Prozesspara-meter:

P ∆e ∆p

1 1 22 2 33 2 3

Bei der Kombination (RMS,ExM) ergibtsich ein brauchbarer Plan:

Ein solcher Plan kommt nur deshalb zu-stande, weil Prozess 1 einmal auf demProzessor 2 und dann zweimal auf demProzessor 1 ausgefuhrt wird. Wurde mandie Prozesse partitionieren, wie es dieKombination (RMS,NoM) verlangt, danngabe es immer ein Paar von Prozessen,das auf einem Prozessor ausgefuhrt wirdund dessen Auslastung U großer als 1wird.




Eine Betrachtung aller Beziehungen von Kombinationen (A,B) ist sehr aufwandig undlasst nur wenige generalisierende Aussagen zu. Eine davon ist jedoch besonders wich-tig. Sie besagt, dass die Kombination (LLF, PrM) die großte Menge von Prozessmen-gen brauchbar einplant (vgl. [10]):

FA,B ⊂ FLLF,PrM A ∈ {RMS,EDF,LLF}, B ∈ {NoM,ExM,PrM}

Aus diesem Grunde hat die Kombination (LLF, PrM) eine herausragende Bedeutung,wenn es darum geht, nach der optimalen Auslastung U Ausschau zu halten.



6.3 Proportional faires SchedulingDie nachfolgenden Uberlegungen gehen davon aus, dass fur jeden Prozess i einerProzessmenge P die Bedingung 0 < ∆ei/∆pi ≤ 1 erfullt ist, und die Auslastung dieZahl der Prozessoren nicht ubersteigt: U ≤ m. Unter diesen Voraussetzungen besitztdie Prozessmenge P in der Kombination (LLF, PrM) einen brauchbaren Plan s.

Die Konstruktion beschreibt eine Klasse FPFAIR von Planungsverfahren, die als pro-portional faire Planungsverfahren bezeichnet werden.



Plane fur Mehrprozessorsysteme

Ein Plan s fur einen Mehrkernprozessor ist eine Abbildung, die aussagt, ob ein Prozessin einem Intervall der Lange der Bezugszeitspanne ∆tG rechnet oder nicht:

s : P × N→ {0, 1}

Es gilt: s(i, j) = 1, gdw. Prozess i im j-ten Intervall [j ∆tG, (j + 1)∆tG) auf einem derProzessorkerne ausgefuhrt wird2.Abbildung s liefert nur dann einen brauchbaren Plan, wenn fur alle Intervalle j gilt:∑

i∈P

s(i, j) ≤ m

2Dabei darf im j-Intervall hochstens ein Prozess auf einem Kern ausgefuhrt werden



Konzept der proportionalen Fairness (1)

Der Gedanke der proportionalen Fairness, oder kurz P-Fairness, wurde entscheidendvon Baruah (vgl. [6]) gepragt. Die P-Fairness zielt darauf ab, die Ausfuhrungszeit ∆eiso gleichmaßig wie moglich uber die Periode ∆pi aufzuteilen. Fur die Aufteilung wirddie Bezugszeitspanne ∆tG als kleinstmogliche Einheit zugrunde gelegt.Ein Plan s heißt P-fair, wenn fur alle i ∈ P und alle j ∈ N0 gilt:

−1 < lag(s, i, j) < 1 mit lag(s, i, j) =∆ei∆pi

(j + 1) −∑

k∈{0,...,j}

s(i, k)




Gegeben sei ein Prozess i mit der Ausla-stung ∆ei/∆pi = 5/9. Gesucht sind mogli-che Anfangsstucke eines Plans s, in denProzess i P-fair eingeplant ist. Betrachtetwird zunachst das Intervall j = 0. BeideAlternativen sind P-fair:

sa(i, 0) = 0

sb(i, 0) = 1

Bei Alternative sa ist lag(sa, i, 0) = 5/9−0 =

5/9 und bei Alternative sb ist lag(sb, i, 0) =

5/9− 1 = −4/9.Verlangert man den Plan um das Intervall

j = 1, dann hat man jeweils wieder zwei Al-ternativen, also insgesamt vier. Diese sind:

saa(i, 1) = 0 lag(saa, i, 1) = 10/9− 0 = 10/9

sab(i, 1) = 1 lag(sab, i, 1) = 10/9− 1 = 1/9

sba(i, 1) = 0 lag(sba, i, 1) = 10/9− 1 = 1/9

sbb(i, 1) = 1 lag(sbb, i, 1) = 10/9− 2 = −8/9

Nur die Alternative saa, bei der der Pro-zess i in den ersten beiden Bezugszeit-spannen nicht eingeplant wird, erfullt dieKriterien der P-Fairness nicht. Umgekehrtdarf der Prozess i in Plan sbb zweimalhintereinander eingeplant werden und derPlan ist immer noch P-fair.




Da die Ausfuhrungszeit eines Prozessesi in Einheiten der Bezugszeitspanne ge-messen wird, ist es naheliegend, den Pro-zess in li = ∆ei/∆tG Schlitze slot aufzutei-len. Jeder Schlitz l ∈ {1, . . . , li} ist bei derPlanung wie ein selbstandiger Prozess, imWeiteren auch Pseudoprozess genannt,zu betrachten, der uber eine eigene Bereit-zeit ri,l und eine eigene Frist di,l verfugt.

Aus der Bedingung der P-Fainess lasstsich auf die Anzahl l der Schlitze schlie-ßen, die fur einen Prozess i, angefangenvom 0-ten bis einschließlich zum j-ten In-tervall einer Periode ∆pi, bereits zugeord-net sind3:

l =∑

k∈{0,...,j}

s(i, k)

3Betrachtet man die Ausfuhrung von Zeitpunkt 0 an, dann liegt das j-te Intervall in der c-ten Periode des Prozesses i: rci ≤ j < rc+1i . Daraus folgt

die verallgemeinerte Beziehung:

(c− 1)∆ei∆tG

+ l =∑

k∈{0,...,j}

s(i, k)




Es gilt nach Definition:

−1 <∆ei∆pi

(j + 1)− l < 1

Umgeformt ergibt das: ⌈∆ei∆pi

(j + 1)

⌉≥ l ≥

⌊∆ei∆pi

(j + 1)

⌋Somit kann die Anzahl der bis zum Intervall j verplanten Ausfuhrungen des Prozessesi nur um 1 schwanken.




Vom Standpunkt der Planung aus ist eswichtig, die Prozessparameter der Pseu-doprozesse zu kennen, konkret die Bereit-zeit ri,l und die Frist di,l fur den l-ten Schlitzdes Prozesses i. Bezogen auf die Bereit-zeit ri,l ist der Beginn des fruhesten In-tervalls [j ∆tG, (j + 1)∆tG) gesucht, in dasder l-te Schlitz nach den Regeln der P-Fairness schon eingeplant werden darf:

ri,l = min{j | 1 +∆ei∆pi

(j + 1) > l}

= min{j | j > ∆pi∆ei

(l − 1)− 1}

=

⌊∆pi∆ei

(l − 1)

⌋

Bezogen auf die Frist di,l ist das Ende desspatesten Intervalls [j ∆tG, (j + 1)∆tG) ge-sucht, in das der l-te Schlitz nach den Re-geln der P-Fairness noch eingeplant wer-den darf. Dies korrespondiert zum maxi-malen j, bis zu dem es moglich ist, nur l−1

Schlitze einzuplanen.

di,l − 1 = max{j | l − 1 > −1 +∆ei∆pi

j}

= max{j | j < ∆pi∆ei

l}

=

⌈∆pi∆ei

l

⌉− 1




Gegeben sei wieder ein Prozess i mit derAuslastung ∆ei/∆pi = 5/9 und li = 5. Die-sem Prozess entsprechen 5 Pseudopro-zessen, die uber eigene Bereitzeiten undFristen verfugen, wie die folgende Tabellezeigt:

l ∆pi∆eil ri,l di,l

1 9/5 0 22 18/5 1 43 27/5 3 64 36/5 5 85 45/5 7 9

Zu erkennen ist Prozess i, der in li = 5

Pseudoprozesse aufgespalten ist, die ubereigene Bereitzeiten und Fristen verfugen.



Ergebnisse bei der proportionalen Fairness

Satz: Zu einer Prozessmenge P existiert bei m Prozessoren genau dann ein brauch-barer P-fairer Plan s, wenn gilt: U ≤ 1

Satz: Das PF-Verfahren ist optimal.



6.4 Affinitaten zwischen Prozessen und ProzessorenAllgemein, d.h. nach der APA-orientierten Zuordnung, wird bei [24] die Menge der Pro-zessoren mit CPUS = {cpu1, ..., cpum} bezeichnet. Grundsatzlich ist jedem Prozessi ∈ P zu jedem Zeitpunkt mit der Abbildung AFFi eine Menge von Prozessoren zuge-ordnet, auf denen Prozess i ausgefuhrt werden darf. Dies wird als Affinitat bezeichnetund folgendermaßen modelliert:

AFFi ⊂ CPUS

Mit CPUS(X) undX ⊂ P werden die Prozessoren bezeichnet, auf denen die Prozessei ∈ X prinzipiell ausgefuhrt werden konnen4:

CPUS(X) =⋃i∈X

AFFi

4In Linux lassen sich die Affinitaten mittels des Systemeaufrufs sched setaffinity() erzeugen.



Affinitaten (1)

Umgekehrt kann man nach den Prozessen fragen, die grundsatzlich auf einer MengeY ⊂ CPUS ausgefuhrt werden konnen5:

AFP (Y ) = {i ∈ P |AFFi ∩ Y 6= ∅}Dagegen soll CPUTP fur einen Prozessor cpuj ∈ CPUS denjenigen Prozess, genauerProzessobjekt, anzeigen, der gerade auf diesem Prozessor ausgefuhrt wird. Damit istCPUTP eine partielle Abbildung, die den Wert ⊥ liefert6, wenn gerade kein Prozesszugeordnet ist.

5Das Akronym AFP soll die Affinitat der Prozessoren zu den Prozessen anzeigen.6Ist Prozess i rechenbereit und fur alle cpuj ∈ CPU gilt CPUTP (cpuj) 6= i, dann ist Prozess i verdrangt. Bei [24] heißt dieser Zustand auch

backlogged.



Affinitaten (2)

Beispiel: Sei P = {1, 2, 3, 4, 5, 6} und CPU = {cpu1, cpu2, cpu3, cpu4}. Folgende Affi-nitaten seien bereits festgelegt:

P AFFi1 {cpu1, cpu2}2 {cpu1}3 {cpu1, cpu3, cpu4}4 {cpu1, cpu4}5 {cpu1}6 {cpu3, cpu4}

So ist CPUS({1, 2, 5}) = {cpu1, cpu2} und AFP ({cpu1, cpu2}) = {1, 2, 3, 4, 5}.



Affinitaten (3)

Fortsetzung Beispiel: Angenommen alle Prozesse i ∈ P sind im Zustand bereit und diePrioritaten identisch mit ihren Indizees. Dann wurden bei einer globalen Zuordnungdie Prozesse {3, 4, 5, 6} auf je einem Prozessor ausgefuhrt werden, wahrend die Pro-zesse {1, 2} verdrangt sind. Im Allgemeinen gilt hier, dass fur jeden Prozess i aus derMenge X der hochspriorisierten rechenbereiten Prozesse mit |X| ≤ m genau einenProzessor cpuj gibt mit CPUTP (cpuj) = i.

Es stellt sich die Frage, ob sich durch das explizite Setzen von Affinitaten eine andereZuordnung ergibt.



Affinitaten (4)

Fortsetzung Beispiel: Eine gleiche Zuordnung bei gesetzten Affinitaten scheitert hierdaran, dass die Prozesse {3, 4, 5, 6} nur auf den Prozessoren {cpu1, cpu3, cpu4} aus-gefuhrt werden konnen wie mit

CPU({3, 4, 5, 6}) = {cpu1, cpu3, cpu4}

zu sehen ist.Grundsatzlich kann fur einen Prozess i ∈ P mit IFE(i) festgehalten werden, mit wel-chen anderen Prozessen er in Konkurrenz um Prozessoren steht7:

IFE(i) = {j ∈ P |j 6= i ∧ AFFi ∩ AFFj 6= ∅}

Demensprechend gilt:IFE(5) = {1, 2, 3, 4}

7Das Akronym IFE steht fur interfere.



Affinitaten (5)

Fortsetzung Beispiel: Wann immer Prioritaten zu beachten sind, ist mit PFE(i) dieProzessmenge gemeint, die Prozess i auf einem Prozessor verdrangen kann:

PFE(i) = {j ∈ P |j > i ∧ AFFi ∩ AFFj 6= ∅}So ist fur die vier hochst priorisierten Prozesse:

PFE(3) = {4, 5, 6}PFE(4) = {5, 6}PFE(5) = {}PFE(6) = {}



Affinitaten (6)

Fortsetzung Beispiel: Dennoch gelingtes unter Berucksichtigung der Affinitatennicht, die vier hochst priorisierten Pro-zesse gleichzeitig auf den vier Prozes-soren auszufuhren. Folgende Abbildungware moglich:

CPUTP (cpu4) = 4

CPUTP (cpu3) = 6

CPUTP (cpu1) = 5

Aber cpu2 kann nicht an einen der vierhochst priorisierten Prozesse vergebenwerden. Hier steht nur die Moglichkeit of-fen, cpu2 an den Prozess 1 zu vergeben:

CPUTP (cpu2) = 1

Damit geht Prozess 3 leer aus. Aber auchProzess 2 kommt nicht zum Zug.



Affinitaten (7)

Fortsetzung Beispiel: Eine andere Zuord-nung ware ebenfalls moglich gewesen:

CPUTP (cpu4) = 6

CPUTP (cpu3) = 3

CPUTP (cpu1) = 5

Dann geht Prozess 4 leer aus. Hier stehtwieder nur die Moglichkeit offen, cpu2 anden Prozess 1 zu vergeben:

CPUTP (cpu2) = 1

Grundsatzlich lauft die Fragestellung aufdie Losung der bipartiten Matching hinaus,

die sich mit den Methoden zur Berechungdes maximalen Flusses losen lassen8.

8Das klassische Verfahren nach Ford und Fulkerson angewandt aus eine Graphen G = (V,E) benotigt einen Aufwand von O(|V | |E|)



Affinitaten (8)

Fortsetzung Beispiel: Damit liegen zwei verschiedene Zuordnungen vor:

CPUTP (cpu4) = 4

CPUTP (cpu3) = 6

CPUTP (cpu1) = 5

CPUTP (cpu4) = 6

CPUTP (cpu3) = 3

CPUTP (cpu1) = 5

Es stellt sich die Frage, ob sie im Sinne einer prioritatsbasierten Prozessausfuhrungals gleichwertig zu betrachten sind.



Affinitaten (9)

Fortsetzung Beispiel: Bei [24] soll fur APA Scheduling die Invariante gelten, dass einverdrangter Prozess i niedriger priorisiert ist als alle Prozesse k ∈ X(i). Dabei ist X(i)

die Menge der Prozesse, deren Affinitaten sich mit denen des Prozesses i uberschnei-den und gerade auf einem Prozessor ausgefuhrt werden:

X(i) = {CPUTP (cpuj) | cpuj ∈ AFFi}

Im Sinne der prioritatsbasierten Prozessausfuhrung muss fur alle Prozess k ∈ X(i)

gelten:k > i ∧ |X(i)| = |AFFi|



Affinitaten (10)

Fortsetzung Beispiel: Anwendung der APAScheduling Invariante auf die beiden Zu-ordnungen von Prozessen zu Prozesso-ren. Zunachst:

CPUTP (cpu4) = 4

CPUTP (cpu3) = 6

CPUTP (cpu1) = 5

Berechnet wird X(3) und umfasst die Pro-zesse, die auf den Prozessoren AFF3 =

{cpu1, cpu3, cpu4} ausgefuhrt werden:

X(3) = {4, 5, 6}

Es ist |X(3)| = |AFF3| und fur alle k ∈ X(3)

gilt k > i.Die andere Zuordnung lautet:

CPUTP (cpu4) = 6

CPUTP (cpu3) = 3

CPUTP (cpu1) = 5

Berechnet wird X(4) und umfasst die Pro-zesse, die auf den Prozessoren AFF4 =

{cpu1, cpu4} ausgefuhrt werden:

X(4) = {5, 6}

Auch hier ist |X(4)| = |AFF4| und fur allek ∈ X(4) gilt k > i.



Affinitaten (11)

Fortsetzung Beispiel: Somit erfullen beide Zuordnungen die APA Scheduling Invarian-te.

Aber ist diese Invariante richtig und sinnvoll, denn in der letzteren Zuordnung ist Pro-zess 3 in Ausfuhrung, der hoher priorisierte Prozess 4 nicht, wahrend es eine Zuord-nung gibt, unter der Prozess 4 ausgefuhrt werden konnte?

Dennoch verhindert die APA Scheduling Invariante Zuordnungen, die der prioritatsba-sierten Prozessausfuhrung widersprechen, d.h. bei denen bezogen auf einen Prozes-sor ein direkter Austausch eines niedriger priorisierten Prozesses durch einen hoherpriorisierten moglich ware.


Literaturverzeichnis

[1] QNX Operating System. QNX Software Systems Ltd., Kanata,Ontario, Canada, 1997.

[2] G. R. Andrews. Concurrent Programming. The Benja-min/Cummings Publishing Company, 1991.

[3] N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. Wel-lings. Absolute and relative temporal constraints in hard real-time databases. In Proc. of IEEE Euromicro Workshop on RealTime Systems, February 1992.

[4] N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings.Hard real-time scheduling: The deadline monotonic approach.In Proc. 8th IEEE Workshop on Real-Time Operating Systemsand Software, Atlanta, May 1991.

[5] Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, andCarl E. Landwehr. Basic concepts and taxonomy of depen-dable and secure computing. IEEE Trans. Dependable Sec.Comput., 1(1):11–33, 2004.

[6] Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, and Do-nald A. Varvel. Proportionate progress: A notion of fairnessin resource allocation. Algorithmica, 15(6):600–625, 1996.

[7] Arnold Berger. Embedded Systems Design. CMP Books, La-wrence, Kansas 66046, 2002.

[8] Enrico Bini, Giorgio Buttazzo, and Giuseppe Buttazzo. Ratemonotonic scheduling: The hyperbolic bound. IEEE Transacti-ons on Computers, 52(7):933–942, July 2003.

[9] Giorgio C. Buttazzo. Hard Real-Time Computing Systems:Predictable Scheduling, Algorithms and Applications. KluwerAcademic Publishers, 1997.

[10] John Carpenter, Shelby Funk, Anand Srinivasan, James An-derson, and Sanjoy Baruah. A categorization of real-time mul-tiprocessor scheduling problems and algorithms. In JosephY.-T. Leung, editor, Handbook of Scheduling - Algorithms, Mo-dels, and Performance Analysis, pages 30(1)–30(19). Chap-man and Hall, Boca Raton, 2004.

[11] Anton Cervin and Johan Eker. Control-scheduling codesignof real-time systems: The control server approach. Journal ofEmbedded Computing, 1(2):209–224, 2005.

[12] c.L. Liu. Scheduling algorithms for hard real-time system mul-tiprogramming of a single processor. JPL Space ProgramsSummary, II(1):37–60, 1969.

[13] Robert I. Davis and Alan Burns. A survey of hard real-timescheduling for multiprocessor systems. ACM Computing Sur-veys, 43(4):239–272, October 2011.

[14] Robert I. Davis, Alan Burns, Reinder J. Bril, and Johan J.Lukkien. Controller area network (CAN) schedulability ana-lysis: Refuted, revisited and revised. Rael-Time Systems,35(0):239–272, January 2007.

109

EchtzeitsystemeLITERATURVERZEICHNIS

[15] Michael L. Dertouzos. Control robotics: The procedural controlof physical processes. IFIP Congress, pages 807–813, 1974.

[16] Deutsches Institut fur Normung. Informationsverarbeitung –Begriffe, DIN 43000. Beuth-Verlag, Berlin, Koln, 1985.

[17] Deutsches Institut fur Normung. Funktionale Sicherheit sicher-heitsbezogener elektrischer/elektronischer/programmierbarerelektronischer Systeme, DIN 61508-5. VDE-Verlag, Berlin,1998.

[18] S. K. Dhall and C. L. Liu. On a real-time scheduling problem.Operations Research, 26:127–140, February 1978.

[19] Stuart Faulk, John Brackett, Paul Ward, and James Kirby. Thecore method for real-time requirements. IEEE Software, 9:22–33, September 1992.

[20] Hugo Fierz. Eingebettete Systeme als Architektur mechani-stischer Modelle. www.ciptool.ch/data/cip mech.pdf, ZurcherHochschule Winterthur.

[21] Borko Furht, Dan Grostick, David Gluch, Guy Rabbat, JohnParker, and Meg McRoberts. Real-Time UNIX Systems: De-sign and Application Guide. Kluwer Academic Publishers, Bo-ston, 1991.

[22] Carlo A. Furia, Dino Mandrioli, Angelo Marzenti, and MatteoRossi. Modeling time in computing: a taxonomy and a compa-rative survey. ACM Computing Surveys, 42(2):6:1–6:51, Fe-bruary 2010.

[23] Michael R. Garey and David S. Johnson. Computers and In-tractability. A Guide to the Theory of NP-Completeness. W. H.Freeman and Company, New York, San Francisco, 1979.

[24] A. Gujarati, F. Cerqueira, and B. J. Brandenburg. Multiproces-sor real-time scheduling with arbitrary affinities: From practi-ce to theory. Journal of Real-Time Systems, 51(4):440–483,2015.

[25] W. A. Halang and R. Konakovsky. Sicherheitsgerichtete Echt-zeitsysteme. Oldenbourg-Verlag, Munchen, 1999.

[26] Fred Halsall. Data communications, computer networks, andopen systems. Addison-Wesley, third edition, 1992.

[27] R. G. Herrtwich. Betriebsmittelvergabe unter Echtzeitgesichts-punkten. Informatik-Spektrum, 14(2):123–136, 1991.

[28] R. G. Herrtwich and G. Hommel. Kooperation und Konkurrenz.Nebenlaufige, verteilte und echtzeitabhangige Programmsy-steme. Springer-Verlag, Berlin, 1989.



[29] W. A. Horn. Some simple scheduling algorithms. Naval Rese-arch Logistics Quaterly, 21:177–185, 1974.

[30] Hermann Kopetz. Real-Time Systems - Design Principles forDistributed Embedded Applications. Kluwer Academic Publis-hers, Boston, 1997.

[31] Th. S. Kuhn. Die Struktur der wissenschaftlichen Revolutio-nen. Suhrkamp Verlag, Frankfurt, 1969.

[32] Phil Laplante. Real-Time Systems Design and Analysis: AnEngineer’s Handbook. IEEE Press, New York, 1993.

[33] J. P. Lehoczky, L. Sha, and Y. Ding. The rate monotonic sche-duling algorithm: Exact characterization and average case be-havior. In Proceedings of the 10th IEEE Symposium on Real-Time Systems, pages 166–171, December 1989.

[34] Jochen Liedtke. Toward real microkernels. Communicationsof the ACM, 39(9):70–77, September 1996.

[35] C. L. Liu and James W. Layland. Scheduling algorithms formultiprogramming in a hard-real-time environment. Journal ofthe ACM, 20(1):46–61, January 73.

[36] Peter Marwedel. Eingebettete Systeme. Springer-Verlag, Ber-lin, 2007.

[37] A. K. Mok. Fundamental design problems of distributed sy-stems for the hard-real-time environment. PhD thesis, Massa-chusetts Institute of Technology, 1983.

[38] Philipp Nenninger. Vernetzung verteilter sicherheitsrelevanterSysteme im Kraftfahrzeug. Dissertation, Universitat Karlsruhe,2007.

[39] Ulrich Rembold and Paul Levi. Realzeitsysteme zur Prozeß-automatisierung. Hanser Verlag, Munchen, 1994.

[40] Sebastian Rieger. Streaming-Media und Multicasting in draht-losen Netzwerken. Technical Report Nr. 61, Gesellschaft furwissenschaftliche Datenverarbeitung mbH Gottingen, 2003.

[41] Ken Sakamura. µITRON 3.0 – An open and portable real-timeoperation system for embedded systems. Los Alamitos, Cali-fornia, USA, ieee computer society press edition, 1998.

[42] Kenneth C. Sevcik and Marjory J. Johnson. Cyclic time pro-perties of the FDDI token ring protocol. IEEE Transactions onSoftware Engineering, 13(3):376–385, March 1987.

[43] Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky. Prio-rity inheritance protocols: An approach to real-time synchro-nisation. IEEE Transactions on Computers, 39(9):1175–1185,September 1990.



[44] John A. Stankovic. Misconceptions about real-time computing:A serious problem for next generation systems. IEEE Transac-tions on Computers, 21(10):10–19, 1988.

[45] Mark J. Stanovich, Theodore P. Baker, and An-I Andy Wang.Throtteling on-disk schedulers to meet soft-real-time require-ments. In Real-Time and Embedded Technology and Appli-cation (RTAS’08), pages 331–341, St. Louis, Missouri, April2008. IEEE Computer Society.

[46] A. S. Tanenbaum. Computer Networks. Prentice-Hall Interna-tional Editions, Englewood Cliffs, NJ, second edition, 1988.

[47] Martin Torngren. Fundamentals of implementing real-timecontrol applications in distributed computer systems. Real-Time Systems, 14:219–250, 1998.

[48] Victor Varshavsky. Time, timing and clock in massively par-allel computing systems. In Third International Conferenceon Massively Parallel Computing Systems (PCS98), ColoradoSprings, Colorado, April 6-9 1998.

[49] Dieter Zobel. Echtzeitsysteme - Grundlagen der Planung. eX-amen.press. Springer-Verlag, Berlin, 2008.

[50] Dieter Zobel and Wolfgang Albrecht. Echtzeitsysteme -Grundlagen und Techniken. Lehrbuch. International ThomsonPublishing Company, Bonn, Albany, 1995.

[51] Dieter Zobel and Horst Hogenkamp. Konzepte der parallelenProgrammierung. Teubner-Verlag, Stuttgart, 1988.


Documents

Dieter Zobel¨ - userpages.uni-koblenz.dezoebel/EZmat/Skript/Core.pdf · Echtzeitsysteme Dieter Zobel¨ Universitat Koblenz-Landau¨ Fachbereich Informatik, Institut fur Softwaretechnik¨