IST - Arbeitsgruppe Zöbel
Verifikation der Echtzeifähigkeit von Systemen
View this page in english: 
[ Übersicht | Personen | Projekte | Literatur | Studien- und Diplomarbeiten | Lehre ]
Konformität von Protokollen zur Vermeidung der Prioritätsumkehr
Ein Echtzeitsystem muss korrekte Berechnungen bzw. Reaktionen innerhalb vorgegebener Zeitschranken zusichern können und damit Vorhersagbarkeit garantieren.
Implementierungstechnisch besteht ein Echtzeitsystem typischerweise aus mehreren Prozessen mit unterschiedlicher Priorität. Um Vorhersagen über die Einhaltung von Zeitschranken machen zu können, wird jeweils der höchstpriorisierte rechenbereite Prozess ausgeführt. Bei der Synchronisierung solcher Prozesse tritt das Phänomen der Prioritätsumkehr auf, bei dem ein hoch priorisierter Prozess unbeschränkt lange verzögert werden kann. Zur Vermeidung der Prioritätsumkehr wurden verschiedene Protokolle entwickelt und stehen auf der Ebene von Betriebssystemen und Laufzeitsystemen zur Verfügung.
In der Praxis ist dabei meistens die sogenannte Prioritätsvererbung (priority inheritance), seltener die Prioritätsobergrenzen (priority ceiling), in Betriebssystemen anzutreffen.
Die ursprüngliche Beschreibung dieser Protokolle [Sha, Rajkumar, Lehozcky 1990] wurde im wesentlichen natürlichsprachig vorgenommen. Dies führte dazu, dass in den beschriebenen Protokollen Fehler und Missverständlichkeiten enthalten waren.
Betrachtet man die Beschreibung der Protokolle in real existierenden Laufzeitumgebungen und Betriebssystemen, so kann man erkennen, dass viele Betriebssysteme z.B. das Protokoll ,priority inheritance' unterstützen, dass das implementierte Protokoll aber von dem ursprünglich propagierten Protokoll abweicht. Es stellt sich die Frage, wie es bei denjenigen Betriebssystemen aussieht, die nur angeben, die Prioritätsvererbung zu unterstützen, auf eine Beschreibung des implementierten Verfahrens aber verzichten?
Zusätzlich wird die Frage aufgeworfen, welche Zeitbedingungen die modifizierten Protokolle garantieren können? Stimmen diese mit den originalen Zeitbedingungen überein, oder müssen diese abgeschwächt werden?
Das Ziel unseres Projektes ist es, eine eindeutige Darstellung verschiedener Protokolle zur Vermeidung der Prioritätsumkehr zu entwickeln und aus dieser Testszenarien abzuleiten, welche von einem generischen Testtool dazu genutzt werden, die reale Implementation der Protokolle in einem beliebigen Betriebssystem zu testen.
Erste Ergebnisse zeigen, dass die vermuteten Fehler in der Protokollimplementation auch bei weit verbreiteten Betriebssystemen auftreten [PZ00].
