Prioritätsgrenze

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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.

Voraussetzungen für die Anwendung des Protokolls[Bearbeiten]

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

Protokollablauf[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

(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[Bearbeiten]

OSEK Priority Ceiling Protocol[Bearbeiten]

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.