4.2 Protokolle für Ressourcen-Zugriffe
233
t
3
1
2
P(S)
J
J
J
P(S) [blockiert]
fortfahren
blockieren
kritischer Abschnitt
normale Ausführung
V(S)
Abb. 4.6 Prioritätsumkehr mit möglicher großer Verzögerung
zum Ende der Laufzeit von J 2 blockiert. J 1 wird von einem Job niederer Priorität
blockiert, der sich nicht in seinem kritischen Abschnitt befindet. Dieser Effekt wird
Prioritätsumkehr7 genannt. Tatsächlich findet die Prioritätsumkehr statt, obwohl
J 2 nicht direkt mit J 1 und J 3 in Verbindung steht. Die Dauer der Prioritätsumkehr
ist nicht durch die Länge irgendeines kritischen Abschnitts beschränkt. Dieses und
weitere Beispiele können mit Hilfe der levi-Simulationssoftware simuliert werden
[497].
Einer der bekanntesten Fälle von Prioritätsumkehr betraf den Mars Pathfinder,
in dem ein exklusiver Zugriff auf einen gemeinsam benutzten Speicherbereich zur
Prioritätsumkehr auf dem Mars führte [276].
4.2.2 Prioritätsvererbung
Ein Ansatz zum Umgang mit Prioritätsumkehr ist die Verwendung des Prioritätsvererbungs-Protokolls (engl. Priority Inheritance Protocol (PIP)). Dieses Protokoll ist
in vielen Echtzeitbetriebssystemen verfügbar. Es funktioniert wie folgt:
• Jobs werden entsprechend ihrer aktiven Prioritäten zugeteilt. Jobs mit derselben
Priorität werden auf first-come, first-served-Basis zugeteilt.
• Wenn ein Job J 1 die Operation P(S) ausführt und ein anderer Job J 2 bereits exklusiven Zugriff darauf hat, wird J 1 blockiert. Wenn die Priorität von J 2 niedriger
als die von J 1 ist, erbt J 2 die Priorität von J 1 . Damit kann J 2 die Ausführung
fortsetzen. Allgemein betrachtet, erbt jeder Job die höchste Priorität aller Jobs,
die durch ihn blockiert werden.
• Wenn ein Job J 2 die Operation V(S) ausführt, wird seine Priorität auf die höchste
Priorität aller Jobs, die von ihm blockiert werden, reduziert. Wenn kein weiterer
Job von J 2 blockiert wird, wird dessen Priorität auf den ursprünglichen Wert
zurückgesetzt. Zudem wird der Job mit der höchsten Priorität, der bisher beim
Zugriff auf S blockiert wurde, fortgesetzt.
7 Einige Autoren sehen bereits den in Abb. 4.5 gezeigten Fall als Prioritätsumkehr an. Dies war
auch in früheren Ausgaben dieses Buchs der Fall.
233
t
3
1
2
P(S)
J
J
J
P(S) [blockiert]
fortfahren
blockieren
kritischer Abschnitt
normale Ausführung
V(S)
Abb. 4.6 Prioritätsumkehr mit möglicher großer Verzögerung
zum Ende der Laufzeit von J 2 blockiert. J 1 wird von einem Job niederer Priorität
blockiert, der sich nicht in seinem kritischen Abschnitt befindet. Dieser Effekt wird
Prioritätsumkehr7 genannt. Tatsächlich findet die Prioritätsumkehr statt, obwohl
J 2 nicht direkt mit J 1 und J 3 in Verbindung steht. Die Dauer der Prioritätsumkehr
ist nicht durch die Länge irgendeines kritischen Abschnitts beschränkt. Dieses und
weitere Beispiele können mit Hilfe der levi-Simulationssoftware simuliert werden
[497].
Einer der bekanntesten Fälle von Prioritätsumkehr betraf den Mars Pathfinder,
in dem ein exklusiver Zugriff auf einen gemeinsam benutzten Speicherbereich zur
Prioritätsumkehr auf dem Mars führte [276].
4.2.2 Prioritätsvererbung
Ein Ansatz zum Umgang mit Prioritätsumkehr ist die Verwendung des Prioritätsvererbungs-Protokolls (engl. Priority Inheritance Protocol (PIP)). Dieses Protokoll ist
in vielen Echtzeitbetriebssystemen verfügbar. Es funktioniert wie folgt:
• Jobs werden entsprechend ihrer aktiven Prioritäten zugeteilt. Jobs mit derselben
Priorität werden auf first-come, first-served-Basis zugeteilt.
• Wenn ein Job J 1 die Operation P(S) ausführt und ein anderer Job J 2 bereits exklusiven Zugriff darauf hat, wird J 1 blockiert. Wenn die Priorität von J 2 niedriger
als die von J 1 ist, erbt J 2 die Priorität von J 1 . Damit kann J 2 die Ausführung
fortsetzen. Allgemein betrachtet, erbt jeder Job die höchste Priorität aller Jobs,
die durch ihn blockiert werden.
• Wenn ein Job J 2 die Operation V(S) ausführt, wird seine Priorität auf die höchste
Priorität aller Jobs, die von ihm blockiert werden, reduziert. Wenn kein weiterer
Job von J 2 blockiert wird, wird dessen Priorität auf den ursprünglichen Wert
zurückgesetzt. Zudem wird der Job mit der höchsten Priorität, der bisher beim
Zugriff auf S blockiert wurde, fortgesetzt.
7 Einige Autoren sehen bereits den in Abb. 4.5 gezeigten Fall als Prioritätsumkehr an. Dies war
auch in früheren Ausgaben dieses Buchs der Fall.