Bsp: Priority Inversion ohne PI Protokoll

Hier sei zunächst ein Beispiel vorgestellt, das nach den Regeln des RM-Algorithmus bearbeitet wird. Wie man sieht, führt dies zum sogenannten Priority Inversion Phänomen: der Task mit der höchsten Priotität muß auf Tasks mit niedrigerer Priorität warten, da diese eine Ressource blockieren, die ihn von der Ausführung abhält.

in der technischen Tabelle 5.1 kann man sehen, dass die Ausführungszeiten der Tasks zergliedert wurden in Bereiche mit einer kritischen Ausführung ( $C_{i}(critical)$) und in solche, die unkritisch sind ($C_{i}(before)$), ($C_{i}(after)$). Nur die kritischen Bereiche erfordern die Nutzung einer Ressource -hier $R_{1}$-, die über einen Semaphor -hier $S_{1}$- verwaltet wird.

Figure 5.1: Technische Tabelle

Im Bild 5.2 kann man sehen, wie Task $\tau_{1}$, der die höchste Priorität hat, zweimal auf Tasks warten muß, die eine nieedrigere Priorität haben. Im ersten Fall wartet er zunächst auf Task $\tau_{3}$, der dann zusätzlich durch Task $\tau_{2}$ aufgehalten wird. Im zweiten Fall wartet er nur auf Task $\tau_{3}$. durch dieses Warten wird die Priorität von Task $\tau_{1}$ faktisch weniger Wert -Inversion des Wertes, 'priority inversion'- als die der anderen Tasks mit den ursprünglich niedrigeren Prioritäten. Von besonderem Interesse ist hier Fall 1, in dem der Task $\tau_{2}$ zum Zuge kommt, obwohl er eine niedrigere Priorität besitzt als Task $\tau_{1}$. strenggenommen wird nur eine Konstellation wie im Fall 1 als Priority Inversion bezeichnet, da das Warten auf einen Task, der aktuell eine Ressource benutzt, als solches noch nicht eine völlige Entwertung einer höheren Priorität bedeutet. Nur wenn weitere Tasks $\Gamma^{*} \subseteq \Gamma$ mit einer niedrigeren nominellen Priorität einen Task mit höherer nominellen Priorität wie im Beispiel Task $\tau_{1}$ blockieren können, dann tritt Priority Inversion i.e.S. auf (vgl. Cottet et al. (2002)[17]:S.60). Dies ist allerdings nur möglich, weil hier mehrere Regeln ineinandergreifen:

Figure 5.2: RM Ausführung der Techn.Tabelle

• Ein Task, der eine Ressource über einen Semaphor besitzt ('hold', 'keep', 'lock'...) hat immer Vorfahrt vor einem anfordernden Task, selbst wenn dieser eine höhere nominelle Priorität besitzt.
• Ein Task $\tau_{j}$ mit einer höheren nominellen Priorität als ein Task $\tau_{i}$ kann den Task $\tau_{i}$ aussetzen lassen ('preempt'), selbst wenn dieser eine Ressource besitzt, sofern der Task $\tau_{j}$ nicht die gleiche Ressource anfordert. Ein weiterer Task $\tau_{k}$, der eine höhere nominelle Priorität wie Task $\tau_{j}$ besitzt, kann den Task $\tau_{j}$ nicht hindern, solange er sich selber in einer Warteschleife ('queue') für eine Ressource befindet. Letzteres bedeutet, daß Tasks, die sich in Warteschleifen für Ressourcen befinden, für das normale Scheduling ausgeschlossen sind.