236
4 Systemsoftware
und wird ausgeführt bis er P(b) ruft, während b durch J 2 gehalten wird. Daher wird
J 2 wieder ausgeführt. Job J 2 wird blockiert, wenn er P(a) aufruft. Dieser Deadlock
würde auch ohne Nutzung eines Protokolls zum Ressourcenzugriff existieren.
∇
4.2.3 Priority Ceiling-Protokoll
Deadlocks können mit dem Priority Ceiling-Protokoll (PCP) [485] vermieden werden, bei dem die Jobs zur Entwurfszeit bekannt sein müssen. Bei PCP dürfen Jobs
keinen kritischen Abschnitt betreten, wenn es bereits gesperrte Semaphoren
gibt, die diesen Job irgendwann blockieren könnten. Wenn ein Job einen kritischen Abschnitt betritt, kann er vor dem Verlassen desselben mithin nicht durch
Jobs einer niedrigeren Priorität blockiert werden. Dies wird mit der Bildung eines
Maximums von Prioritäten (engl. priority ceiling) erreicht. Jedem Semaphor S wird
ein Maximum C(S) zugeordnet. Dies ist die statische Priorität des Jobs der höchsten
Priorität, der S sperren kann. Das PCP-Protokoll geht wie folgt vor:
• Wir nehmen an, dass Job J läuft und Semaphor S sperren möchte. Dann kann
J S nur sperren, wenn die Priorität von J den Wert C(S’) des Semaphors S’
übersteigt, wobei S’ der Semaphor mit dem höchsten Wert von C(S) unter allen
Semaphoren ist, die gegenwärtig durch von J verschiedene Jobs gesperrt werden.
Wenn ein solcher Semaphor existiert, dann gilt J als durch S’ und den S’ haltenden
Job blockiert. Wenn J durch S’ blockiert wird, erhält der Job, der S’ sperrt, die
Priorität von J.
• Wenn ein Job J einen kritischen Abschnitt, der durch S geschützt ist, verlässt,
entsperrt er S. Sofern mindestens ein Job vorhanden ist, der durch S blockiert
ist, wird unter diesen der Job der höchsten Priorität aufgeweckt. Die Priorität
von J wird auf die höchste Priorität unter allen Jobs gesetzt, die noch durch eine
Semaphore blockiert sind, die J hält. Wenn J durch keinen anderen Job blockiert
wird, wird seine Priorität wieder auf seine normale Priorität zurückgesetzt.
Beispiel 4.3: In der Abb. 4.11 werden Semaphore a, b und c benutzt8. Die höchste
Priorität von a und b ist p 1 , die höchste Priorität von c ist p 2 . Zum Zeitpunkt t 2
möchte J 2 Semaphor c sperren, aber c ist schon gesperrt. Außerdem übersteigt die
Priorität von J 2 nicht den Wert C(c). Trotzdem resultiert der Versuch, c zu sperren,
in einem Erhöhen der Priorität von J 3 auf p 2 .
Zum Zeitpunkt t 5 versucht J 1 , Semaphor a zu sperren. a ist noch nicht gesperrt,
aber J 3 hat b gesperrt und die gegenwärtige Priorität von J 1 übersteigt nicht den
Wert C(b). Deswegen wird J 1 blockiert. Dies ist die wesentliche Eigenschaft von
PCP: dieses Blockieren vermeidet ansonsten mögliche spätere Deadlocks. J 3 erhält
die Priorität von J 1 . Darin drückt sich aus, dass J 1 darauf wartet, dass Semaphor b
durch J 3 freigegeben wird.
8 Wir nutzen hier ein Beispiel von Bordoloi [59].
4 Systemsoftware
und wird ausgeführt bis er P(b) ruft, während b durch J 2 gehalten wird. Daher wird
J 2 wieder ausgeführt. Job J 2 wird blockiert, wenn er P(a) aufruft. Dieser Deadlock
würde auch ohne Nutzung eines Protokolls zum Ressourcenzugriff existieren.
∇
4.2.3 Priority Ceiling-Protokoll
Deadlocks können mit dem Priority Ceiling-Protokoll (PCP) [485] vermieden werden, bei dem die Jobs zur Entwurfszeit bekannt sein müssen. Bei PCP dürfen Jobs
keinen kritischen Abschnitt betreten, wenn es bereits gesperrte Semaphoren
gibt, die diesen Job irgendwann blockieren könnten. Wenn ein Job einen kritischen Abschnitt betritt, kann er vor dem Verlassen desselben mithin nicht durch
Jobs einer niedrigeren Priorität blockiert werden. Dies wird mit der Bildung eines
Maximums von Prioritäten (engl. priority ceiling) erreicht. Jedem Semaphor S wird
ein Maximum C(S) zugeordnet. Dies ist die statische Priorität des Jobs der höchsten
Priorität, der S sperren kann. Das PCP-Protokoll geht wie folgt vor:
• Wir nehmen an, dass Job J läuft und Semaphor S sperren möchte. Dann kann
J S nur sperren, wenn die Priorität von J den Wert C(S’) des Semaphors S’
übersteigt, wobei S’ der Semaphor mit dem höchsten Wert von C(S) unter allen
Semaphoren ist, die gegenwärtig durch von J verschiedene Jobs gesperrt werden.
Wenn ein solcher Semaphor existiert, dann gilt J als durch S’ und den S’ haltenden
Job blockiert. Wenn J durch S’ blockiert wird, erhält der Job, der S’ sperrt, die
Priorität von J.
• Wenn ein Job J einen kritischen Abschnitt, der durch S geschützt ist, verlässt,
entsperrt er S. Sofern mindestens ein Job vorhanden ist, der durch S blockiert
ist, wird unter diesen der Job der höchsten Priorität aufgeweckt. Die Priorität
von J wird auf die höchste Priorität unter allen Jobs gesetzt, die noch durch eine
Semaphore blockiert sind, die J hält. Wenn J durch keinen anderen Job blockiert
wird, wird seine Priorität wieder auf seine normale Priorität zurückgesetzt.
Beispiel 4.3: In der Abb. 4.11 werden Semaphore a, b und c benutzt8. Die höchste
Priorität von a und b ist p 1 , die höchste Priorität von c ist p 2 . Zum Zeitpunkt t 2
möchte J 2 Semaphor c sperren, aber c ist schon gesperrt. Außerdem übersteigt die
Priorität von J 2 nicht den Wert C(c). Trotzdem resultiert der Versuch, c zu sperren,
in einem Erhöhen der Priorität von J 3 auf p 2 .
Zum Zeitpunkt t 5 versucht J 1 , Semaphor a zu sperren. a ist noch nicht gesperrt,
aber J 3 hat b gesperrt und die gegenwärtige Priorität von J 1 übersteigt nicht den
Wert C(b). Deswegen wird J 1 blockiert. Dies ist die wesentliche Eigenschaft von
PCP: dieses Blockieren vermeidet ansonsten mögliche spätere Deadlocks. J 3 erhält
die Priorität von J 1 . Darin drückt sich aus, dass J 1 darauf wartet, dass Semaphor b
durch J 3 freigegeben wird.
8 Wir nutzen hier ein Beispiel von Bordoloi [59].