Unter einem Realzeitbetriebssystem versteht man ein Betriebsystem mit deterministischem Zeitverhalten. Typischerweise werden von außen (Sensoren, Benutzereingaben, etc.) ein oder mehrere Tasks an einem Realzeitsystem erzeugt, auf welche dieses innerhalb einer festen Zeit reagiert haben muss.
Neben die zeitkritische Komponente tritt noch eine sicherheitskritische Komponente: bei Nichteinhaltung der Frist eines so genannten essentiell kritischen Tasks kann das Überleben des Gesamtsystems nicht garantiert werden, d.h. das System kann zerstört oder schwer beschädigt werden. Man spricht von funktionskritischen Systemen (mission critical systems). Außer der Bedingung an die Überlebensfähigkeit (survivability) sind Zuverlässigkeit und Fehlertoleranz weitere Anforderungen, die erfüllt werden müssen. Da funktionskritische Systeme außerdem meistens in unvorhersehbaren Umgebungen operieren, sind die Designanforderungen an ein derartiges Betriebsystem sehr komplex. Kontrollsysteme für Kernkraftwerke, Industrieroboter oder Flugzeuge sind Beispiele für derartige Systeme.
MELODY ist ein verteiltes Realzeitbetriebssystem für zeitkritische Anwendungen, in dem lokal verteilte Tasks mit unterschiedlichen Prioritäten und Fristen (deadlines) um verteilte Dateien (files) konkurrieren. Die Tasks sind jeweils an einen Knoten gebunden, d.h. es findet keine Prozessmigration statt. Dateien hingegen können von einem Knoten auf einen anderen kopiert oder verlagert werden, um ihre Verfügbarkeit (accessability) zu erhöhen. Man spricht dabei von Replikation bzw. Relokation.
Für jedes File gibt es über die Systemknoten verteilte Filekopien verschiedener "Qualität", deren Anzahl und Verteilung dynamisch von File-Assignern an jedem Knoten verwaltet werden:
In Abhängigkeit davon, wie oft hintereinander Deadlines eines Tasks nicht eingehalten worden sind, werden diese immer kritischer (degree of criticality). Wird ein Task wesentlich kritisch, d.h. die Deadline wird hart, so werden rechtzeitig vorher (mindestens private) Kopien der benötigten Files lokal zugänglich gemacht.
Um Überlebensfähigkeit (survivability) sinnvoll zu ermöglichen, wird die traditionelle Service-Reihenfolge (Ressourcenscheduling vor Task-Scheduling) in MELODY umgekehrt. Dabei wird zwar die Garantie rechtzeitiger Ausführung von Tasks durch den Task-Scheduler unmöglich (in verteilten Systemen auf jeden Fall fragwürdig), jedoch wird die unnötige Blockierung von Ressourcen (zu Lasten von Tasks an anderen Knoten) minimiert. Dies erfordert eine neue Systemfunktion pro Knoten, den Run-Time Monitor (RTM).
Die besondere Betonung von schicht-durchgreifender und funktionaler Integration in MELODY ist richtungweisend für Vorstellungen in vielen laufenden und geplanten Betriebssystem-Projekten, besonders in komplexen Anwendungen wie verteilter Informationsgewinnung und -auswertung in Hypermedia-Systemen.
Es ergeben sich drei eng verknüpfte Diplomarbeiten, die sich mit der Implementierung der Hauptmodule des MELODY-Systems befassen:
Dabei macht der gemeinsame Entwurf (Schnittstellen, geeignete Einbindung in ein Echtzeit-Linux) einen beträchtlichen Teil aller Arbeiten aus. Die Arbeiten sollen auf Xenomai [Xen06], einem Echtzeit Framework auf der Basis von RTAI [RTA06] aufsetzen, das eine aktive Community besitzt und sehr umfangreich dokumentiert ist. Hier ist die Funktionsweise des vorhanden Schedulers zu analysieren und ein geeignetes Konzept für die Integration der MELODY-Systemmodule zu entwerfen. Ziel ist die Entwicklung eines RTAI-MELODY-Mods.
Jeder File-Server (FS) beschäftigt sich mit der nebenläufigen Bereitstellung (allocation) der benötigten Dateien für k Tasks in seiner Queue (nach einem auf den Anwendungsfall angepassten Algorithmus). Wird der FS über eine Aktualisierung einer öffentlichen Kopie benachrichtigt, so beantragt dieser die Aktualisierung einer evtl. lokal vorhandenen privaten Kopie.
Der FS verwaltet außerdem eine Historie über Lese- und Schreibzugriffe für jede Datei, die von einem Task angefordert wird. Diese wird verwendet, um eine geschätzte Ausführungszeit (estimated execution time, EETj) für eine Taskinstanz Tj zu berechnen, die eine Liste von Dateien LRFj in ihrem kritischen Bereich benötigt.
EETj - Estimated_Computation_Time(Tj) | Σ rεLRFj Computation_Time(r)
Hierbei ist Estimated_Computation_Time von Tj die durchschnittliche geschätzte Datei-Ausführungszeit der letzen 5 Instanzen von Tj, während Computation_Time die Zeit angibt, die benötigt wird, um auf die benötigten Kopien der Datei r zuzugreifen (inklusive des Lockings und der Kommunikationslatenzen, die durch mögliche remote-Aufrufe verursacht werden).
[HaS90] D. HABAN, K. SHIN, Application of Real-Time Monitoring to Scheduling Task with Random Execution Times; IEEE Trans. on Software Engineering; Vol. 6 No. 12; 1990
[JaR94] F. JAHANIAN, R. RAJKUMAR, S. RAJU, Runtime Monitoring of Timing Constraints in Distributed Real-Time Systems; Real-Time Systems; Vol. 7. No. 3 (1994)
[Lin99] Jon A. Lind. Realisation of the Highly Integrated Distributed Real-Time Safety-Critical System Melody. PhD thesis, University of Dortmund, Fachbereich Informatik, Universität Dortmund, Jan 1999.
[RTA06] RTAI – the RealTime Application interface for Linux from DIAPM, official homepage. URL: http://www.rtai.org
[WeK93] Horst F. Wedde, Bogdan Korel, and Jon Lind. Highly Integrated Task and Resource Scheduling for Mission-Critical Systems. In Proc. of the EUROMICRO'93 Workshop on Real-Time Systems, Oulu, Finland, June 1993. Euromicro, IEEE Computer Society Press.
[WeL97] Horst F. Wedde and Jon A. Lind. Building Large, Complex, Distributed Safety-Critical Systems. Real-Time Systems, 13(3), November 1997.
[WeX92] Horst F. Wedde and Mengdal Xu. Scheduling Critical and Sensitive Tasks with Remote Requests in Mission-Critical Systems. In Proc. of the EUROMICRO '92 Workshop on Real-Time Systems, Athens, Greece, 1992. Euromicro, IEEE Computer Society Press.
[WH+90] Horst F. Wedde, Dorota Huizinga, Gookhai Kang, and Bo-Kyung Kim. Melody: A Complete Decentralized Adaptive File System for Handling Real-Time Tasks in Unpredictable Environments. Real-Time Systems, 2(4):347-364, 1990.
[WLE94] Horst F. Wedde, Jon A. Lind, and Andreas Eiss. Achieving Dependability in Safety-critical Operating Systems Through Adaptability and Large-Scale Functional Integration. In Proc. of the ICPAPDS'94 International Conference on Parallel and Distributed Systems, Hsinchu, Taiwan, December 1994.
[Xen06] Real-time Framework for Linux, official homepage. URL: http://www.xenomai.org
[XuP93] J. XU, D.L.PARNAS, On Satisfying Timing Constraints in Hard Real-Time Systems;IEEE-TSE Vol.19 No.1 (1993)