Echtzeit-Betriebssysteme

Das RTOS der Zukunft

14.11.2005 | Autor / Redakteur: David Kalinsky* / Martina Hafner

Die Zukunft vorherzusagen, ist eine recht esoterische Angelegenheit. Bei den Echtzeit-Betriebssystemen sind einige Trends dennoch deutlich sichtbar. Wagen wir also einen Blick auf die Task-Scheduler, Interprozesskommunikation, Timer und Speicherverwaltung des Jahres 2010.

Die Echtzeit-Betriebssysteme der Gegenwart sind umfangreiche und komplexe Gebilde geworden. Sie bieten zahlreiche Dienste wie Netzwerkkommunikation, die Verwaltung von File-Systemen, die Kontrolle verteilter Systeme, Redundanzmechanismen und das dynamische Laden von Applikationssoftware. Die meisten Basisdienste im Kernel des Echtzeit-Betriebssystems (Bild 1) dürften in den nächsten Jahren wesentlichen Änderungen unterworfen sein, nicht zuletzt getrieben von der wachsenden Komplexität und dem steigenden Einsatz von verteilten und Multicore-Designs bei Embedded-Systemen. Wir beginnen unsere Zukunftsreise im Herzen des Echtzeit-Betriebssystems, bei den Task-Schedulern.

Das Task-Scheduling wird modular

Derzeit steuern die meisten Echtzeit-Betriebssysteme die Ausführung von Applikationssoftware mittels prioritätsbasiertem preemptivem Scheduling. Bei dieser Methode läuft immer der zur Abarbeitung bereite Task mit der höchsten Priorität ab. Obwohl die prioritätsbasierten preemptiven Scheduler in der Vergangenheit gute Dienste geleistet haben, gibt es einige Vorbehalte gegen sie. So können Tasks mit geringerer Priorität unter einem prioritätsbasierten preemptiven Scheduler „verhungern“, sprich nicht zur Ausfüh-rung gelangen. Und selbst wenn der Task nicht völlig „verhun-gert“, kann ein prioritätsbasierter preemptiver Scheduler Tasks mit niedriger Priorität häufig erst nach einer langen Verzögerung abarbeiten. Und manch ein Entwickler stellt sich die Frage, wie er seinem Scheduler die Vorgaben zu seinen Echtzeitbe-dingungen mitteilen kann. Es gibt tatsächlich keinen direkten Weg, einem prioritätsbasierten preemptiven Scheduler etwas über die Zeitgrenzen, die Dead-lines, der Software mitzuteilen.

Als Lösung sind bereits mehrere Alternativen für Task-Scheduling am Horizont zu sehen. Die erste nennt sich „Deadline Scheduling“. Bei dieser Methode ist der Task-Scheduler des Echtzeit-Kernels über die Zeitgrenzen von Tasks informiert und erhöht temporär deren Prioritäten, wenn sie an ihre Zeitgrenzen stoßen und noch nicht abgelaufen sind. Er stellt sicher, dass Tasks ablaufen, bevor sie ihre Deadlines überschreiten, indem er preemptiv Laufzeit von Tasks mit eigentlich höherer Priorität „ausborgt“. Deadline-Scheduler sind interessant für DSP- und Multimedia-Applikationen, in denen exaktes Timing und die Konsistenz des Timings der Task-Ausführung die wichtigsten Eigenschaften sind.

Es gibt weitere Wege für ein Echtzeit-Betriebssystem, Dead-line-Scheduling auszuführen. Beim EDF-Scheduling (Earliest Deadline First) darf der Task, der seiner Deadline am nächsten ist, zuerst ablaufen. Deshalb betrachtet ein Deadline-Scheduler die Zeitgrenzen als wesentlich, noch vor der Task-Priorität. Ein etwas komplexerer Deadline-Scheduler ist der LL-Scheduler (Least Laxity). Er beachtet sowohl die Zeitgrenze eines Tasks als auch die Verarbeitungslast.

Ein Beispiel (Bild 2): In einer Zeitspanne tritt die Deadline von Task X früher ein als die von Task Y. Ein EDF-Scheduler würde es Task X erlauben, vor Task Y abzulaufen, selbst wenn Task Y normalerweise eine höhere Priorität hätte. Dabei könnte jedoch der Fall eintreten, dass Task Y seine Zeitgrenze nicht mehr einhalten kann. Ist deshalb ein LL-Scheduler bes-ser? Er evaluiert die Dringlich-keit der Tasks mit einem Wert, der Laxity genannt wird: Laxity = (Task Deadline ] Ausfüh-rungszeit der Task).

Laxity ist die Zeitspanne, die verbleiben würde, bevor die Zeitgrenze einer Task erreicht wird, wenn diese sofort vollstän-dig ablaufen würde. Hat ein LL-Scheduler die Laxity von allen Tasks evaluiert, findet er die Task mit dem kleinsten Wert für die Laxity. Dies ist der Task, der als nächster ablaufen muss.

Ein Least-Laxity-Deadline-Scheduler berücksichtigt also sowohl die Zeitgrenze als auch die Ausführungszeit. Das LL-Scheduling eignet sich hervorragend für zeitkritische Tasks, ist aber für weniger zeitempfindli-che Aufgaben ein Overkill. Deshalb gibt es eine dritte Variante des Deadline-Scheduling, das so genannte MUF-Scheduling (Maximum Urgency First), welches das LL-Scheduling mit dem traditionellen prioritätsbasierten preemptiven Scheduling kombiniert. Beim MUF-Scheduling werden zeitkritische Tasks mit hoher Priorität mit dem LL-Deadline-Scheduling abgearbeitet, während im selben Scheduler die anderen Tasks mit niedrigerer Priorität mit dem prioritätsbasierten preemptiven Ablauf abgearbeitet werden.

Das Deadline-Scheduling ist nicht die einzige Alternative zum heute gängigen prioritätsbasierten preemptiven Scheduling. Es eignet sich exzellent, um die Abläufe von zeitkritischen Tasks zu verbessern, aber es löst nicht das Problem, dass Tasks „verhungern“ können. Schutz gegen die Nichtausführung von Tasks bieten Partition-Scheduler. Hier werden Tasks in Gruppen zusammengefasst, die als Partitionen, manchmal auch als Prozes-se oder Blöcke, bezeichnet werden. Typischerweise besteht eine Partition aus mehreren Tasks, die zusammenarbeiten, wie zum Beispiel für die Daten-erfassung oder Bewegungssteue-rung (Bild 3). Für den Partition-Scheduler sind jeder Partition ein oder mehrere Zeitfenster für die Ausführung in einer sich wiederholenden Zeitlinie zugeord-net. Innerhalb jedes Zeitfensters können nur die Tasks der derzeit aktiven Partition ablaufen. Die Tasks in der aktiven Partition werden üblicherweise auf konventionelle Weise abgearbeitet. Ist das Zeitfenster der Partition einer bestimmten Applikation aktiv, hat diese Task-Gruppe garantierten Zugriff auf die CPU des Prozessors. Ein „Verhungern“ beim Zugriff auf den Prozessor wird innerhalb der Task-Gruppen vermieden.

Angesichts mehrerer Mög-lichkeiten für Task-Scheduling stellt sich die Frage, welcher der Beste für das Echtzeit-Betriebssystem der Zukunft ist. Nun, es gibt wahrscheinlich keinen alleinigen besten Scheduler für alle Embedded-Systeme. Deshalb ist wohl die Vorhersage gerechtfertigt, dass künftige Echtzeit-Betriebssysteme dem Entwickler die Möglichkeit geben werden, aus einem modu-laren, austauschbaren Repertoire an Task-Schedulern zu wählen. Dieses könnte von den heute gängigen prioritätsbasierten preemptiven Schedulern über verschiedene Deadline- und Partition-Scheduler und darüber hinaus reichen. Zum Beispiel ist eine Kombination aus Schedulern denkbar, die das Partition-Scheduling auf der Ebene der Task-Gruppen verwendet und für die einzelnen Tasks innerhalb der Gruppe das MUF-Deadline-Scheduling.

Tasks sprechen Message-Passing

Der zweite Hauptbereich eines Echtzeit-Kernels umfasst die Inter-Task-Kommunikation und Synchronisation. Echtzeit-Betriebssysteme bieten derzeit zahlreiche Kommunikations- und Synchronisationsmechanismen zwischen den Tasks, einschließlich Message-Queues, Mailboxen, Pipes, Semaphoren, Mutexes, Event-Flags, Signale, Bedingungsvariablen und viele weitere. Ein klarer Trend ist der wachsende Fokus auf Message-Passing für die Kommunikation zwischen den Tasks, während die anderen Mechanismen an Bedeutung verlieren werden. Message-Passing ist einfach, intuitiv und ein konzeptionelles Gateway für Multicore- und verteilte Mehrprozessorsysteme.

Insbesondere das asynchrone Message-Passing bietet eine sichere Methode, um Daten von einer Task zur anderen zu über-tragen. Eine Task, die eine Nachricht sendet, wartet dabei auf keinerlei Information von der empfangenden Task. Sie kann daher nicht „sterben“, selbst wenn die empfangende Task stirbt oder nicht mehr auf sie zugegriffen werden kann. Asynchrones Message-Passing bietet ideale Rahmenbedingungen für das fehlertolerante Design von Embedded-Systemen.

Mechanismen wie Semaphoren können große Verzögerungen in Mehrprozessorsystemen hervorrufen, wenn Tasks auf entfernte Semaphoren warten, um ein „Lock“ oder „Unlock“ durchzuführen. Das asynchrone Message-Passing vermeidet typische Probleme der Semaphoren wie Unbounded-Priority-Inversion, Deadlocks, und Schwierigkeiten beim Debug-ging. Mutexes arbeiten mit Prioritätsänderungen von Tasks. Sie eignen sich deswegen nicht für Multicore- und Mehrprozes-sorumgebungen und viele Em-bedded-Entwickler genießen Mutex selbst in Einprozessor-umgebungen nur mit Vorsicht.

Deswegen können wir davon ausgehen, dass in Zukunft das Message-Passing dominieren wird. Die einfachste Art des asynchronen Message-Passing-Modells wird direktes Message-Pasing genannt, wobei Tasks Nachrichten über das Echtzeit-Betriebssystem direkt zu einer anderen Task senden, ohne dass sich die Applikationssoftware um Queues, Mailboxen oder andere intervenierende Echtzeit-Betriebssystem-Mechanismen kümmern muss (Bild 4).

Timer behält die Tasks im Auge

Der dritte Hauptbereich eines Echtzeit-Betriebssystem-Kerns sind die Timer. Die meisten heutigen Echtzeit-Betriebssysteme bieten sowohl „relative Timer“, die mit Einheiten von Ticks (Passermarken, Teilstriche) arbeiten als auch „absolute Timer“, die mit Kalenderdaten und Uhrzeit arbei-ten. Für jede Timer-Art bieten heutige Echtzeit-Betriebssysteme einen Verzögerungsdienst für Tasks und oft auch einen Task-Alert-Dienst, der auf Signaling-Mechanismen wie zum Beispiel Event-Flags basiert. Die Timer-Dienste der Zukunft werden sich auf ihre Grundaufgabe fokussieren, Zeitgrenzen zu sichern. Sie werden dazu sehr eng mit den Task-Schedulern zusammenarbeiten und so helfen festzustellen, ob Task-Ketten ihre Echt-zeitbedingungen einhalten. Andere Timer-Dienste werden die Vitalitätsprüfung von Tasks betreffen, beispielsweise um anzuzeigen, ob Tasks unter Problemzuständen wie Dead-locks, Lockouts oder „Verhungern“ leiden.

Speicher wird dynamisch verwaltet

Die meisten gängigen Echtzeit-Betriebssysteme bieten den Tasks die Möglichkeit, sich Bereiche des RAMs für den zeitweisen Gebrauch zu borgen. Einige bieten die Speicher-Allokierung aus „Heaps“, welche aber zu Speicherfragmentie-rung neigen. Andere Echtzeit-Betriebssysteme bieten „Pools“, die dieses Problem vermeiden.

Alle genannten Methoden bergen die Gefahr, dass nicht genügend Speicher zur Verfügung steht (Memory-Starvation). Eine mögliche Lösung besteht darin, Tasks in Gruppen anzuordnen (Bild 3). Jeder Gruppe wird ein jeweiliger Speicher-Heap oder Pool zugeordnet. Damit ist es für andere Task-Gruppen unerheblich, was mit den RAM-Speicherbereichen innerhalb einer Gruppe passiert. Sie werden davon nicht beeinflusst.

Probleme können auch auftreten, wenn Tasks dynamisch generiert werden, zum Beispiel wenn ein Task eine Reihe neuer Tasks erstellt, die wiederum selbst neue Tasks produzieren. Diese quantitative Explosion würde sehr schnell den gesamten vorhandenen Speicher eines Heaps oder Pools belegen. Echtzeit-Betriebssysteme könn-ten künftig davor schützen, indem sie den vorhandenen Speicher verwalten. Wenn beispielsweise ein Task zwei neue Tasks generiert, hätten die drei Tasks zusammen dasselbe gesamte Speicher-Allokierungs-Budget wie der ursprüngliche Task. Vielleicht erhält dazu jeder der neuen Tasks ein Drittel des Speicher-Budgets der ursprünglichen Task und gleichzeitig würde das Speicher-Budget des ursprünglichen Tasks auf ein Drittel seines ursprünglichen Wertes gekürzt. Auf diese Weise haben andere Tasks nicht weniger Speicher zur Verfügung.

In der nahen Zukunft werden wir also eine Vielzahl an Änderungen in den Basisdiensten von Echtzeit-Betriebssystemen erleben. Vielleicht können wir uns auf der Embedded Systems Conference 2010 treffen, um zu sehen, wie viele der Vorhersagen eingetroffen sind.

*David Kalinsky hat seine eigene Trainingsakademie für Embedded Systems Software Design und Entwicklung. Kontakt: info @ kalinskyassociates.com.

Kommentar zu diesem Artikel abgeben

Schreiben Sie uns hier Ihre Meinung ...
(nicht registrierter User)

Kommentar abschicken

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 197696 / Embedded Software Entwicklungswerkzeuge)

Embedded Software Engineering Report abonnieren

4 mal jährlich: Die kostenlose Pflichtlektüre für Embedded­-Software- und Systems-Entwickler, von Analyse bis Wartung und Betrieb

* Ich bin mit der Verarbeitung und Nutzung meiner Daten gemäß Einwilligungserklärung und AGB einverstanden.
Spamschutz:
Bitte geben Sie das Ergebnis der Rechenaufgabe (Addition) ein.