Priority Ceiling Protokoll

Ebenfalls von den Autoren Sha, Rajkumar und Lehoczky (1990)[102] stammt das Priority Ceiling Protokoll (PCP). Es stellt eine Erweiterung des Priority Inheritance Protokolls dar, das geschaffen wurde, um Phänomene wie Chaining (verkettete Verzögerung) oder Deadlocks (Pattsituationen) auszuschließen.

An der originalen Definition von Sha et al.(1990) kann man sehr schön die verschiedenen 'Regelungstiefen' erkennen (das Wort 'Regelungstiefe' im folgenden Text ist nicht Bestandteil der ursprünglichen Definition. Ich habe es dazugesetzt, um die unterschiedlichen Komponenten der Definition klarer hervorheben zu können; ebenso ist in der ursprünglichen Definition die Abfolge genau umgekehrt):

Regelungstiefe 1: Rate Monotonic/DM/ EDF:

A job J, when it does not attempt to enter a critical section, can preempt another job $J_{L}$ if its priority is higher than the priority, inherited or assigned, at which job $J_{L}$ is executing.(Sha, Rajkumar und Lehoczky (1990)[102]:p.1180)

Regelungstiefe 2-Vererbung: Priority Inheritance:

A job J uses its assigned priority, unless it is in its critical section and blocks higher priority jobs. If job J blocks higher priority jobs, J inherits $P_{H}$, the highest priority of the jobs blocked by J. When J exits a critical section, it resumes the priority it had at the point of entry into the critical section. Priority inheritance is transitive. Finally, the operations of priority inheritance and of the resumption of previous priority must be indivisible.(Sha, Rajkumar und Lehoczky (1990)[102]:p.1180)

Regelungstiefe 2-Zugriff auf Ressource: Ceiling Zusatz:

Job J , which has the highest priority among the jobs ready to run, is assigned the processor, and let $S^{*}$ be the semaphore with the highest priority ceiling of all semaphores currently locked by jobs other than job J. Before job J enters its critical section, it must first obtain the lock on the semaphore S guarding the shared data structure. Job J will be blocked and the lock on S will be denied, if the priority of job J is not higher than the priority ceiling of semaphore $S^{*}$. In this case, job J is said to be blocked on semaphore $S^{*}$ and to be blocked by the job which holds the lock on $S^{*}$. Otherwise, job J will obtain the lock on semaphore S and enter its critical section. When a job J exits its critical section, the binary semaphore associated with the critical section will be unlocked and the highest priority job, if any, blocked by job J will be awakened.(Sha, Rajkumar und Lehoczky (1990)[102]:p.1180)

Diese Definition folgt den unterschiedlichen Komplexitätsgraden, die man in der Praxis vorfinden kann. Im einfachsten Fall -Regelungstiefe 1- hat meine eine Taskmenge $\Gamma$ mit ausschließlich unabhängigen Tasks. Keiner muß eine Ressource mit einem anderen Task teilen. In diesem Fall genügt es für den Scheduler, die Tasks anhand ihrer nominellen Priorität zu organisieren.

Handelt es sich dagegen um eine abhängige Taskmenge, dann gibt es zwei interessante Zustände: ein Task $\tau$ hat schon die Kontrolle über eine Ressource oder er will die Kontrolle erst erlangen.

Im ersten Fall, wenn er die Kontrolle schon hat, dann wird die Idee des Priority Inheritance Protokolls übernommen -Regelungstiefe 2-Vererbung-: alle anfragenden Tasks $\tau^{*}$ müssen auf die Freigabe der Ressource durch den kontrollierenden Task $\tau$ warten. Sofern einer der anfragenden Tasks eine höhere Priorität $P_{H}$ als jene des kontrollierenden Tasks hat, übernimmt der kontrollierende Task diese höhere Priorität $P_{H}$ für die Dauer der Abarbeitung als seine aktuale/ technische Priorität. Dies verkürzt im allgemeinen die Wartezeiten der höherwertigen Tasks. Nicht ausgeschlossen ist hiermit allerdings -siehe das vorausgehende Deadlock-Beispiel5.4- der Fall, daß ein anderer Task $\tau^{*}$ mit höherer Priorität unterbrechen und eine Ressource beanspruchen kann, die im späteren Verlauf auch noch von dem gerade aktiven Task $\tau$ benötigt werden wird. Hier greift nun die neue Erweiterung gegenüber dem PI-Protokoll.

Will nämlich ein Task $\tau^{*}$ mit höherer Priorität als der gerade aktive Task $\tau$ auf eine Ressource zugreifen, die von dem aktiven Task $\tau$ momentan noch nicht benutzt wird -Regelungstiefe 2-Zugriff auf Ressource-, dann wird jetzt verlangt, daß der anfordernde Task $\tau^{*}$ eine Priorität besitzt, die höher ist als der Ceilingwert $C(S)$ -Definition siehe unten- der gewünschten noch nicht genutzten Ressource. Das Konzept des Ceilingwertes ist das neue Hilfsmittel, mit dem im Priority Ceiling Protokoll die Wechselwirkung zwischen den verschiedenen Tasks kontrolliert wird.

Def.: Priority Ceiling Gegeben sei eine Taskmenge $\Gamma$ und ein Semaphor S. Sei $\Gamma^{*} \subseteq \Gamma$ jene Menge von Tasks, die den Semaphor S benutzen können. Sei $P^{*} = \{ P_{1}, ..., P_{k} \}$ die Menge der Prioritäten der Tasks von $\Gamma^{*}$. Dann soll gelten:

$$C(S) = max(P^{*})$$

(siehe: (Sha, Rajkumar und Lehoczky (1990)[102]:p.1178) Der Ceilingwert $C(S)$ des Semaphjors S entspricht der Priorität des benutzenden Tasks mit der höchsten Priorität.

Die Idee hinter dieser Regelung ist einfach: um zu verhindern, dass die Tasks der Taskmenge $\Gamma^{*}$ sich bei der Benutzung einer gemeinsamen Ressource gegenseitig blockieren, wird verlangt, daß ein Zugriff eines Task $\tau$ auf eine aktuell noch freie Ressource S nur möglich ist, wenn die Priorität des anfragenden Tasks $\tau$ höher ist als der Ceilingwert aller aktuell benutzten Semaphoren $S^{+}$. Denn, sollte der aktuell anfragende Task $\tau$ später auch noch eine der jetzt schon kontrollierten Ressource benutzen wollen, dann würde dies zum Deadlock/ Gleichstand führen können, würde auch die Ressource S immer noch von $\tau$ kontrolliert und einer der aktuell kontrollierenden Tasks $\tau^{+}$ würde S anfragen. Die aktuell kontrollierenden Tasks $\tau^{+}$ werden also dadurch geschützt, daß Tasks, die gemeinsame Ressourcen anfragen wollen, dies nicht können, da sie grundsätzlich keine höhere Priorität als den Ceilingwert der gemeinsamen Ressorcen besitzen. Dies sei am vorausgehenden Beispiel mit dem Deadlock/ Gleichstand illustriert.