Quelltext der Seite Prioritätsgrenze

{{Belege fehlen|1=[[Diskussion:Prioritätsgrenze|Siehe Diskussionsseite]]|2=Dieser Artikel|Plural=0}}

Die '''Prioritätsgrenze''' ({{enS|''priority ceiling protocol''}}) ist eine Methode zur Behebung des Problems
der [[Prioritätsinversion]] und der Vermeidung von [[Deadlock (Informatik)|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 [[Semaphor (Informatik)|Semaphoren]]:'''
* <math>S_{1}</math>
* <math>S_{2}</math>
* <math>S_{3}</math>

'''2 Prozesse:''' 
* <math>T_{1}</math> mit Priorität 1 und verwendet die Ressourcen <math>S_{1}</math>, <math>S_{2}</math>
* <math>T_{2}</math> mit Priorität 2 und verwendet die Ressourcen <math>S_{2}</math>, <math>S_{3}</math>

'''Prioritätsgrenzen der Semaphoren:'''
* <math>S_{1}</math>: Priorität 1 wegen <math>T_{1}</math>
* <math>S_{2}</math>: Priorität 1 wegen <math>T_{1}</math>
* <math>S_{3}</math>: Priorität 2 wegen <math>T_{2}</math>

'''Ablauf:'''
* <math>T_{2}</math> fängt an zu arbeiten, er verwendet sofort <math>S_{2}</math>. Damit steigt die Prioritätsschranke des Systems auf die Priorität der Semaphore <math>S_{2}</math>, also 1.
* <math>T_{1}</math> startet und verdrängt <math>T_{2}</math>.
* <math>T_{1}</math> versucht nun <math>S_{1}</math> zu belegen. Dies scheitert jedoch zunächst, weil die Prioritätsschranke des Systems bei 1 liegt und Prozess <math>T_{1}</math> keine höhere Priorität hat.
* <math>T_{2}</math> Bekommt nun die Priorität von <math>T_{1}</math> auf Grund der [[Prioritätsvererbung]].
* <math>T_{2}</math> belegt jetzt zusätzlich <math>S_{3}</math>. Dies ist möglich, da <math>T_{2}</math> momentan ein Betriebsmittel mit der höchsten Priorität hat.
* <math>T_{2}</math> gibt <math>S_{2}</math> frei und bekommt wieder seine Ausgangspriorität.
* <math>T_{1}</math> kann nun <math>S_{1}</math> 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

{{SORTIERUNG:Prioritatsgrenze}}
[[Kategorie:Betriebssystemtheorie]]