232
4 Systemsoftware
als bei nicht-Echtzeit-Anwendungen. Gegenseitiger Ausschluss kann zur Prioritätsumkehr führen, welche die effektive Priorität von Jobs ändert. Auch bei nicht eingebetteten Systemen kommt Prioritätsumkehr vor. Aus den vorher genannten Gründen
ist das Problem der Prioritätsumkehr aber bei eingebetteten Systemen schwerwiegender.
Ein erstes Beispiel für die Folgen, die aus einer Kombination von gegenseitigem
Ausschluss und Nichtentzug von Prozessorressourcen entstehen, ist in Abb. 4.5
dargestellt. In diesem Unterabschnitt nutzen wir Material aus dem Buch von Buttazzo
[81].
b lo c k ie r t
kritischer Abschnitt
Normale Ausführung
V(S)
P(S) 1
P(S)
V(S)
2
1
4
3
2
0
1
t
t
t
t
t
t
J
J
J
Abb. 4.5 Blockieren eines Jobs durch einen Job niedrigerer Priorität
Fettgedruckte, nach oben zeigende Pfeile kennzeichnen die Zeitpunkte, zu denen
Jobs ausführbar oder „bereit” werden. Zum Zeitpunkt t 0 betritt Job J 2 einen kritischen Abschnitt, nachdem er exklusiven Zugriff auf eine Ressource mittels einer
P-Operation angefordert und erhalten hat. Zum Zeitpunkt t 1 wird Job J 1 ausführbereit und verdrängt J 2 . Zum Zeitpunkt t 2 erhält J 1 keinen exklusiven Zugriff auf die
gerade von J 2 belegte Ressource und wird blockiert. Job J 2 kann fortfahren und gibt
die Ressource einige Zeit später wieder frei. Die Freigabeoperation prüft, ob Jobs
höherer Priorität warten und verdrängt J 2 . Während der Zeit, in der J 1 blockiert war,
hat also ein Job niederer Priorität einen Job mit höherer Priorität effektiv blockiert.
Die Notwendigkeit, exklusiven Zugriff auf einige Ressourcen zur Verfügung zu stellen, ist die Hauptursache für diesen Effekt. Im Fall von Abb. 4.5 kann die Dauer
der Blockierung die Länge des kritischen Abschnitts von J 2 glücklicherweise nicht
überschreiten. Diese Situation ist problematisch, aber nur schwierig zu vermeiden.
Im allgemeinen Fall kann die Situation noch deutlich schlimmer sein. Dies ist
z.B. in Abb. 4.6 dargestellt. Gegeben seien die Jobs J 1 , J 2 und J 3 . J 1 besitzt die
höchste Priorität, J 2 eine mittlere und J 3 die niedrigste Priorität. Wir nehmen an,
dass J 1 und J 3 exklusiven Zugriff auf eine Ressource mittels der Operation P(S)
anfordern. Sei J 3 nun in seinem kritischen Abschnitt, wenn er von J 2 verdrängt wird.
Wenn J 1 nun J 2 verdrängt und versucht, auf dieselbe Ressource zuzugreifen, auf die
J 3 gerade exklusiven Zugriff hat, blockiert dieser und J 2 kann fortfahren. Solange
J 2 fortfährt, kann J 3 die Ressource nicht freigeben. Daher blockiert J 2 effektiv J 1 ,
obwohl die Priorität von J 1 höher als die von J 2 ist. In diesem Beispiel wird J 1 bis
4 Systemsoftware
als bei nicht-Echtzeit-Anwendungen. Gegenseitiger Ausschluss kann zur Prioritätsumkehr führen, welche die effektive Priorität von Jobs ändert. Auch bei nicht eingebetteten Systemen kommt Prioritätsumkehr vor. Aus den vorher genannten Gründen
ist das Problem der Prioritätsumkehr aber bei eingebetteten Systemen schwerwiegender.
Ein erstes Beispiel für die Folgen, die aus einer Kombination von gegenseitigem
Ausschluss und Nichtentzug von Prozessorressourcen entstehen, ist in Abb. 4.5
dargestellt. In diesem Unterabschnitt nutzen wir Material aus dem Buch von Buttazzo
[81].
b lo c k ie r t
kritischer Abschnitt
Normale Ausführung
V(S)
P(S) 1
P(S)
V(S)
2
1
4
3
2
0
1
t
t
t
t
t
t
J
J
J
Abb. 4.5 Blockieren eines Jobs durch einen Job niedrigerer Priorität
Fettgedruckte, nach oben zeigende Pfeile kennzeichnen die Zeitpunkte, zu denen
Jobs ausführbar oder „bereit” werden. Zum Zeitpunkt t 0 betritt Job J 2 einen kritischen Abschnitt, nachdem er exklusiven Zugriff auf eine Ressource mittels einer
P-Operation angefordert und erhalten hat. Zum Zeitpunkt t 1 wird Job J 1 ausführbereit und verdrängt J 2 . Zum Zeitpunkt t 2 erhält J 1 keinen exklusiven Zugriff auf die
gerade von J 2 belegte Ressource und wird blockiert. Job J 2 kann fortfahren und gibt
die Ressource einige Zeit später wieder frei. Die Freigabeoperation prüft, ob Jobs
höherer Priorität warten und verdrängt J 2 . Während der Zeit, in der J 1 blockiert war,
hat also ein Job niederer Priorität einen Job mit höherer Priorität effektiv blockiert.
Die Notwendigkeit, exklusiven Zugriff auf einige Ressourcen zur Verfügung zu stellen, ist die Hauptursache für diesen Effekt. Im Fall von Abb. 4.5 kann die Dauer
der Blockierung die Länge des kritischen Abschnitts von J 2 glücklicherweise nicht
überschreiten. Diese Situation ist problematisch, aber nur schwierig zu vermeiden.
Im allgemeinen Fall kann die Situation noch deutlich schlimmer sein. Dies ist
z.B. in Abb. 4.6 dargestellt. Gegeben seien die Jobs J 1 , J 2 und J 3 . J 1 besitzt die
höchste Priorität, J 2 eine mittlere und J 3 die niedrigste Priorität. Wir nehmen an,
dass J 1 und J 3 exklusiven Zugriff auf eine Ressource mittels der Operation P(S)
anfordern. Sei J 3 nun in seinem kritischen Abschnitt, wenn er von J 2 verdrängt wird.
Wenn J 1 nun J 2 verdrängt und versucht, auf dieselbe Ressource zuzugreifen, auf die
J 3 gerade exklusiven Zugriff hat, blockiert dieser und J 2 kann fortfahren. Solange
J 2 fortfährt, kann J 3 die Ressource nicht freigeben. Daher blockiert J 2 effektiv J 1 ,
obwohl die Priorität von J 1 höher als die von J 2 ist. In diesem Beispiel wird J 1 bis