Prioritätsgrenze

Die Prioritätsgrenze (Vorlage:EnS) ist eine Methode zur Behebung des Problems der Prioritätsinversion und der Vermeidung von Deadlocks. Sie ist eine Erweiterung der Prioritätsvererbung, kann aber im Gegensatz zu dieser einen Deadlock ausschließen.

Voraussetzungen für die Anwendung des Protokolls

• Prioritätsgetriebenes präemptives Scheduling mit festen Prioritäten
• Ein-Prozessor-System
• Alle Anforderungen an Ressourcen sind im Voraus bekannt

Protokollablauf

Die Prioritätsschranke eines Systems zu einem festen Zeitpunkt ist bestimmt durch das Maximum der Prioritätsschranken aller Ressourcen, die zu diesem Zeitpunkt benutzt werden. Die Prioritätsschranke einer Ressource entspricht dem Maximum der Prioritäten der Prozesse, die überhaupt auf diese Ressource zugreifen. Dementsprechend verändert sich die Prioritätsschranke eines Systems dauernd. Sie wechselt zwischen den Prioritätsschranken der Ressourcen im System und 0.

Zuteilungsregel

Möchte ein Prozess eine Ressource nutzen, so wird zuerst geprüft, ob diese verfügbar ist:

• ist die Ressource bereits vergeben, so wird die Anforderung verweigert und der Prozess blockiert an dieser Ressource
• ist die Ressource verfügbar, so wird die aktuelle Prioritätsschranke des Systems geprüft:
  • hat der Prozess eine höhere Priorität als die aktuelle Prioritätsschranke, so bekommt er die Ressource zugeteilt
  • hat er keine höhere Priorität, so bekommt er die Ressource nur dann, wenn er schon die Ressource, die die aktuelle Prioritätsschranke des Systems begründet, besitzt. Ansonsten wird ihm die Ressource verweigert.

Prioritätsvererbungsregel

Blockiert ein Prozess an einer Ressource, so erbt der Prozess, der diese Ressource momentan besitzt, die (höhere) Priorität des anfragenden Prozesses. Der Prozess, der die Ressource schon besitzt, wird nun unter dieser Priorität weiterverarbeitet, bis er alle Ressourcen freigegeben hat, deren Prioritätsschranke größer oder gleich der geerbten Priorität ist.

Beispiel mit Semaphor

(kleinere Zahlen bedeuten hier höhere Prioritäten)

3 Semaphoren:

• $S_1$
• $S_2$
• $S_3$

2 Prozesse:

• $T_1$ mit Priorität 1 und verwendet die Ressourcen $S_1$, $S_2$
• $T_2$ mit Priorität 2 und verwendet die Ressourcen $S_2$, $S_3$

Prioritätsgrenzen der Semaphoren:

• $S_1$: Priorität 1 wegen $T_1$
• $S_2$: Priorität 1 wegen $T_1$
• $S_3$: Priorität 2 wegen $T_2$

Ablauf:

• $T_2$ fängt an zu arbeiten, er verwendet sofort $S_2$. Damit steigt die Prioritätsschranke des Systems auf die Priorität der Semaphore $S_2$, also 1.
• $T_1$ startet und verdrängt $T_2$.
• $T_1$ versucht nun $S_1$ zu belegen. Dies scheitert jedoch zunächst, weil die Prioritätsschranke des Systems bei 1 liegt und Prozess $T_1$ keine höhere Priorität hat.
• $T_2$ Bekommt nun die Priorität von $T_1$ auf Grund der Prioritätsvererbung.
• $T_2$ belegt jetzt zusätzlich $S_3$. Dies ist möglich, da $T_2$ momentan ein Betriebsmittel mit der höchsten Priorität hat.
• $T_2$ gibt $S_2$ frei und bekommt wieder seine Ausgangspriorität.
• $T_1$ kann nun $S_1$ belegen.

Abwandlungen

OSEK Priority Ceiling Protocol

Auch Immediate Priority Ceiling Protocol (engl. für unverzügliches Prioritäts-Obergrenzen-Protokoll). Bei diesem Protokoll erhält der belegende Thread sofort die Priorität der Prioritätsgrenze der Ressource.

Literatur

• L. Sha, R. Rajkumar, J.P. Lehoczky: Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, pp. 1175–1185, September, 1990