Prioritätsgrenze

Die Prioritätsgrenze (englisch priority ceiling protocol) 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.

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

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.

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.

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.

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

3 Semaphoren:

• ${\displaystyle S_{1}}$
• ${\displaystyle S_{2}}$
• ${\displaystyle S_{3}}$

2 Prozesse:

• ${\displaystyle T_{1}}$ mit Priorität 1 und verwendet die Ressourcen ${\displaystyle S_{1}}$, ${\displaystyle S_{2}}$
• ${\displaystyle T_{2}}$ mit Priorität 2 und verwendet die Ressourcen ${\displaystyle S_{2}}$, ${\displaystyle S_{3}}$

Prioritätsgrenzen der Semaphoren:

• ${\displaystyle S_{1}}$: Priorität 1 wegen ${\displaystyle T_{1}}$
• ${\displaystyle S_{2}}$: Priorität 1 wegen ${\displaystyle T_{1}}$
• ${\displaystyle S_{3}}$: Priorität 2 wegen ${\displaystyle T_{2}}$

Ablauf:

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

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.

• 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