- Priority Ceiling Protocol
-
Die Prioritätsgrenze, - engl. 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 eine Verklemmung ausschließen.
Inhaltsverzeichnis
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 Ressource 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:
- S1
- S2
- S3
2 Prozesse:
- T1 mit Priorität 1 und verwendet die Ressourcen S1, S2
- T2 mit Priorität 2 und verwendet die Ressourcen S2, S3
Prioritätsgrenzen der Semaphoren:
- S1: Priorität 1 wegen T1
- S2: Priorität 1 wegen T1
- S3: Priorität 2 wegen T2
Ablauf:
- T2 fängt an zu arbeiten, er verwendet sofort S2.
- T1 startet und verdrängt T2.
- T1 versucht nun S1 zu belegen. Dies scheitert jedoch, weil ein anderer Prozess S2 bereits reserviert hat, welcher dieselbe Priorität hat wie T1. (T1 kann zu diesem Zeitpunkt überhaupt keine Betriebsmittel reservieren, auch wenn sie die Priorität 0 hätten.)
- T2 Bekommt nun die Priorität von T1 auf Grund der Prioritätsvererbung.
- T2 belegt jetzt zusätzlich S3. Dies ist möglich, da T2 momentan ein Betriebsmittel mit der höchsten Priorität hat.
- T2 gibt S2 frei und bekommt wieder seine Ausgangspriorität
- T1 sichert sich nun S2
Abwandlungen
OSEK Priority Ceiling Protocol
auch Immediate Priority Ceiling Protocol (eng. "unverzügliches Prioritäts-Obergrenzen-Protokoll")
Bei diesem Protokoll erhält der belegende Thread sofort die Priorität der Prioritätsgrenze der Ressource.
Wikimedia Foundation.
