238
4 Systemsoftware
J 1 . Zum Zeitpunkt t 2 möchte J 3 Semaphor c sperren, aber die Priorität von J 3 ist
kleiner als C(a) für die bereits gesperrte Semaphore a und J 4 erhält die Priorität von
J 3 . Zum Zeitpunkt t 3 gibt es einen Sperrwunsch für b, aber die Priorität von J 2 ist
wieder kleiner als C(a) des bereits gesperrten Semaphors a und J 4 erhält die Priorität
von J 2 . Zum Zeitpunkt t 5 gibt es einen Sperrwunsch für a, aber die Priorität von
J 1 übersteigt nicht C(a) und J 4 erhält die Priorität von J 1 . Nachdem J 4 Semaphor
a freigibt, ist kein Semaphor gesperrt und seine Priorität fällt auf seine normale
Priorität. Zu dieser Zeit hat J 1 die größte Priorität und wird bis zu seinem Ende
ausgeführt. Die verbleibenden Ausführungen sind durch die normalen Prioritäten
bestimmt.
∇
Es kann gezeigt werden, dass PCP Deadlocks vermeidet (siehe [81], Theorem
7.3). Es gibt Varianten von PCP, die sich dadurch von PCP unterscheiden, dass
die Prioritäten zu anderen Zeitpunkten geändert werden. Das Distributed Priority
Ceiling Protocol (DPCP) [466] und das Multiprocessor Priority Ceiling Protocol
(MPCP) [465] sind Erweiterungen von PCP auf Multiprozessoren.
4.2.4 Stack Resource Policy-Protokoll
Im Unterschied zu PCP unterstützt die Stack Resource Policy (SRP) dynamisches
Scheduling, insbesondere kann SRP mit den dynamischen Prioritäten benutzt werden, die im EDF-Scheduling berechnet werden (siehe Unterabschnitt 6.2.1 auf Seite
332). Bei SRP müssen wir zwischen Jobs und Tasks unterscheiden. Tasks können
sich wiederholende Berechnungen beschreiben (siehe auch Definition 2.2). Jede
Berechnung bildet einen Job entsprechend unserer bisherigen Benutzung. Unter
dem Begriff Task erfassen wir jetzt alle Eigenschaften, die auf eine Menge von
gleichartigen Jobs zutreffen, d.h. Jobs, die periodisch denselben Code ausführen.
Dementsprechend gehört zu jeder Task τ i eine Menge von Jobs. Siehe dazu auch
Definition 6.1 auf Seite 324. SRP betrachtet nicht jeden Job einer Task einzeln,
sondern definiert Eigenschaften, die global auf Tasks Anwendung finden. Zusätzlich unterstützt SRP Ressourcen, die aus mehreren Einheiten bestehen, wie z.B.
Speicherpuffer. Die folgenden Größen werden definiert:
• Der preemption level l i einer Task τ i gibt Informationen darüber, welche anderen
Tasks durch Jobs von τ i verdrängt werden können. Eine Task τ i kann eine andere
Task τ j nur verdrängen, wenn l i > l j ist. Wir verlangen: Wenn Task τ i nach τ j
im System ankommt und τ i hat eine höhere Priorität als τ j , dann muss l i > l j
sein. Für EDF-Scheduling (siehe Seite 332) bedeutet dies, dass die preemption
levels eine monoton fallende Folge der relativen Deadlines sind. Umso später die
Deadline, umso leichter wird es sein, einen Job zu verdrängen. l i ist ein statischer
Wert.
• Die resource ceiling einer Ressource ist der größte preemption level der Tasks, die
dadurch blockiert werden könnten, dass sie ihre Maximalforderung an Einheiten
4 Systemsoftware
J 1 . Zum Zeitpunkt t 2 möchte J 3 Semaphor c sperren, aber die Priorität von J 3 ist
kleiner als C(a) für die bereits gesperrte Semaphore a und J 4 erhält die Priorität von
J 3 . Zum Zeitpunkt t 3 gibt es einen Sperrwunsch für b, aber die Priorität von J 2 ist
wieder kleiner als C(a) des bereits gesperrten Semaphors a und J 4 erhält die Priorität
von J 2 . Zum Zeitpunkt t 5 gibt es einen Sperrwunsch für a, aber die Priorität von
J 1 übersteigt nicht C(a) und J 4 erhält die Priorität von J 1 . Nachdem J 4 Semaphor
a freigibt, ist kein Semaphor gesperrt und seine Priorität fällt auf seine normale
Priorität. Zu dieser Zeit hat J 1 die größte Priorität und wird bis zu seinem Ende
ausgeführt. Die verbleibenden Ausführungen sind durch die normalen Prioritäten
bestimmt.
∇
Es kann gezeigt werden, dass PCP Deadlocks vermeidet (siehe [81], Theorem
7.3). Es gibt Varianten von PCP, die sich dadurch von PCP unterscheiden, dass
die Prioritäten zu anderen Zeitpunkten geändert werden. Das Distributed Priority
Ceiling Protocol (DPCP) [466] und das Multiprocessor Priority Ceiling Protocol
(MPCP) [465] sind Erweiterungen von PCP auf Multiprozessoren.
4.2.4 Stack Resource Policy-Protokoll
Im Unterschied zu PCP unterstützt die Stack Resource Policy (SRP) dynamisches
Scheduling, insbesondere kann SRP mit den dynamischen Prioritäten benutzt werden, die im EDF-Scheduling berechnet werden (siehe Unterabschnitt 6.2.1 auf Seite
332). Bei SRP müssen wir zwischen Jobs und Tasks unterscheiden. Tasks können
sich wiederholende Berechnungen beschreiben (siehe auch Definition 2.2). Jede
Berechnung bildet einen Job entsprechend unserer bisherigen Benutzung. Unter
dem Begriff Task erfassen wir jetzt alle Eigenschaften, die auf eine Menge von
gleichartigen Jobs zutreffen, d.h. Jobs, die periodisch denselben Code ausführen.
Dementsprechend gehört zu jeder Task τ i eine Menge von Jobs. Siehe dazu auch
Definition 6.1 auf Seite 324. SRP betrachtet nicht jeden Job einer Task einzeln,
sondern definiert Eigenschaften, die global auf Tasks Anwendung finden. Zusätzlich unterstützt SRP Ressourcen, die aus mehreren Einheiten bestehen, wie z.B.
Speicherpuffer. Die folgenden Größen werden definiert:
• Der preemption level l i einer Task τ i gibt Informationen darüber, welche anderen
Tasks durch Jobs von τ i verdrängt werden können. Eine Task τ i kann eine andere
Task τ j nur verdrängen, wenn l i > l j ist. Wir verlangen: Wenn Task τ i nach τ j
im System ankommt und τ i hat eine höhere Priorität als τ j , dann muss l i > l j
sein. Für EDF-Scheduling (siehe Seite 332) bedeutet dies, dass die preemption
levels eine monoton fallende Folge der relativen Deadlines sind. Umso später die
Deadline, umso leichter wird es sein, einen Job zu verdrängen. l i ist ein statischer
Wert.
• Die resource ceiling einer Ressource ist der größte preemption level der Tasks, die
dadurch blockiert werden könnten, dass sie ihre Maximalforderung an Einheiten