Bsp: Deadlock trotz PI

Gegeben sind zwei Tasks $\tau_{1}$ und $\tau_{2}$ mit folgenden kritischen Sektionen: $\tau_{1} = \langle ... L(S_{a})...L(S_{b})... U(S_{b})...U(S_{a}) \rangle$ und $\tau_{2} = \langle ... L(S_{b})...L(S_{a})... U(S_{a})...U(S_{b}) \rangle$. Task $\tau_{2}$ startet zuerst. Während der Ausführung mit Semaphor $S_{b}$ startet Task $\tau_{1}$. Beide Tasks 'verhakeln' sich durch wechselseitige Anforderungen, da das Priority Inference Protokoll keine Regel besitzt, um Konflikte bei wechselseitigen Anforderungen zu verhindern.

Im Detail: Task $\tau_{2}$ tritt als erster auf und kann seine Ausführung beginnen, da kein anderer Task ihn daran hindert. Der Eintritt in die kritische Sektion mit Semaphor $S_{b}$ ist problemlos. Während der Nutzung von Semaphor $S_{b}$ tritt Task $\tau_{1}$ auf. Da er eine höhere nominelle Priorität besitzt als Task $\tau_{2}$ kann er seine nichtkritische Sektion ausführen und Task $\tau_{2}$ muß warten. Dies gilt auch dann, wenn Task $\tau_{1}$ in die Abarbeitung seiner kritrischen Sektion mit Semaphor $S_{a}$ eintreten will. Da dieser Semaphor zu diesem Zeitpunkt von keinem anderen Task direkt belegt wird, kann Task $\tau_{1}$ die Abarbeitung beginnen, da er auch eine höhere Priorität als Task $\tau_{2}$ besitzt. Innerhalb der Nutzung von Semaphor $S_{b}$ stößt Task $\tau_{1}$ dann auf die eingebettete kritische Sektion mit Semaphor $S_{b}$. Bei der Anforderung von Semaphor $S_{b}$ stößt er auf Task $\tau_{2}$, der diesen Semaphor noch unter Kontrolle hat. Task $\tau_{1}$ wird durch Task $\tau_{2}$ blockiert und muß zusätzlich noch für die Dauer der Nutzung von Semaphor $S_{b}$ seine Priorität an Task $\tau_{2}$ abgeben. Nun kann Task $\tau_{2}$ seine Nutzung von Semaphor $S_{b}$ fortsetzen. Während dieser Nutzung stößt task $\tau_{2}$ auf die kritische Sektion mit Semaphor $S_{a}$. Dieser wird aber von Task $\tau_{1}$ kontrolliert. Also muß auch Task $\tau_{2}$ warten. Da nun beide Tasks wechselseitig aufeinander warten müssen, liegt ein Deadlock vor.

Intuitiv ist klar, dass der Konflikt dadurch auftritt, dass im Fall von eingebetteten kritischen Sektionen eigentlich alle Semaphoren $S^{*}$, die relativ zum ersten Semaphor einer kritischen Sektion eingebettet sind, 'vorbeugend' reserviert werden müssen, um solche Blockaden zu verhinden. Eine Strategie, um solche Blockierungen vorbeugend auszuschließen, bietet das Priority-Ceiling Protokoll von Sha et al. (1990)[102] Dies soll kurz besprochen werden.

Figure 5.4: Wechselseitige Anforderungen führen unter PI zum Deadlock