Zusammenfassung: Dieser Artikel behandelt das Konzept, die Typen und das Warteschlangenmodell der Aufgabenplanung in einem Betriebssystem und konzentriert sich auf die Analyse des Echtzeitkernels von VxWorks. Schlüsselwörter: Eingebettetes Echtzeitbetriebssystem (RTOS); VxWorks; Aufgabenplanung. Einleitung: VxWorks ist ein eingebettetes Echtzeitbetriebssystem von Wind River Systems, Inc. Seit seiner Einführung in den 1980er Jahren hat es sich aufgrund seiner hohen Leistung, Zuverlässigkeit und Echtzeitfähigkeit zu einem der herausragendsten Echtzeitbetriebssysteme entwickelt. Es erlangte insbesondere durch seinen erfolgreichen Einsatz in Hightech-Produkten wie Mars-Rovern und Patriot-Raketen Bekanntheit. Seit seinem Markteintritt in China im Jahr 1996 hat es sich innerhalb weniger Jahre zum bevorzugten Betriebssystem in eingebetteten Echtzeitanwendungen wie Landesverteidigung, Industrieautomation, Netzwerkkommunikation, Luft- und Raumfahrt, Medizintechnik, Statusüberwachung und Unterhaltungselektronik entwickelt. Eingebettete Echtzeitbetriebssysteme weisen spezifische Merkmale ihres Kernels auf. Dieser Artikel konzentriert sich auf die Analyse der Aufgabenplanung im Echtzeitkernel. 1. Das Konzept der Ablaufplanung: In einem Anwendungssoftwaresystem werden unabhängige und interagierende Programmeinheiten während ihrer Ausführung als Tasks bezeichnet. Auf einer einzelnen CPU erzeugt der Multitasking-Mechanismus die Illusion, dass mehrere Tasks gleichzeitig ausgeführt werden. Tatsächlich ordnet das System den Kernel anhand eines Multitasking-Scheduling-Algorithmus den Tasks zur Ausführung zu. Der Systemkernel plant die Ausführung der Tasks für einen festen Zeitraum, den sogenannten Zeitschlitz. Ablaufplanung bezeichnet die Zuweisung von Ressourcen und Zeit zu Tasks, um sicherzustellen, dass das System bestimmte Leistungsanforderungen erfüllt. Ziel des Scheduling-Algorithmus ist es, die Zeitvorgaben aller Tasks unter normalen Bedingungen bestmöglich einzuhalten und sicherzustellen, dass auch echtzeitkritische Tasks ihre Zeitvorgaben unter Spitzenlastbedingungen erfüllen. Da Zeitvorgaben das entscheidende Unterscheidungsmerkmal zwischen Echtzeit- und Nicht-Echtzeitsystemen sind, stellen Scheduling-Algorithmen ein grundlegendes Problem für Echtzeitsysteme dar. Die Leistung eines Echtzeitbetriebssystems, wie Durchsatz, Bearbeitungszeit, Pünktlichkeit und Vorhersagbarkeit, hängt maßgeblich von der Echtzeit-Ablaufplanung ab. 2. Arten der Ablaufplanung Obwohl die Ablaufplanung hauptsächlich der Zuweisung von Prozessoren dient, unterscheiden sich die in verschiedenen Betriebssystemen verwendeten Methoden grundlegend. Auch die dabei eingesetzten Algorithmen können variieren. Daher wird die Ablaufplanung häufig hierarchisch in High-Level-, Medium-Level- und Low-Level-Planung unterteilt. Die High-Level-Planung, auch bekannt als Langzeit- oder Job-Planung, bestimmt, welche Jobs in der Warteschlange auf dem Sekundärspeicher in den Arbeitsspeicher geladen werden sollen, erstellt Prozesse für diese, weist die notwendigen Ressourcen zu und reiht die neu erstellten Prozesse zur Ausführung in die Warteschlange ein. In Echtzeitsystemen werden Benutzereingaben über die Tastatur jedoch direkt in den Arbeitsspeicher geladen, um eine zeitnahe Reaktion zu gewährleisten. Daher benötigen Echtzeitsysteme in der Regel keine Job-Planung. Die Intermediate-Level-Planung, auch bekannt als Mid-Range-Planung, dient primär der Verbesserung der Speichernutzung und des Systemdurchsatzes. Sie verhindert, dass vorübergehend nicht ausführbare Prozesse wertvollen Speicherplatz belegen, und lädt sie stattdessen zum Warten auf den Sekundärspeicher; dieser Zustand wird als angehaltener Zustand bezeichnet. Sobald diese Prozesse wieder lauffähig sind und Speicherplatz verfügbar ist, lädt der Scheduler der mittleren Ebene diese bereiten Prozesse zurück in den Speicher, stellt sie auf Ausführungsbereitschaft und reiht sie in die Warteschlange ein, um auf die Prozessplanung zu warten. Die Prozessplanung auf niedriger Ebene bestimmt, welcher Prozess in der Warteschlange den Prozessor erhält, und weist ihm diesen dann zu. Die Prozessplanung ist die grundlegendste Art der Prozessplanung und muss von allen Betriebssystemen konfiguriert werden. Sie kann auf zwei Arten implementiert werden: 1) Nicht-präemptives Scheduling: Bei dieser Methode wird ein Prozess, sobald ihm ein Prozessor zugewiesen wurde, so lange ausgeführt, bis er abgeschlossen ist oder durch ein Ereignis blockiert wird. Erst dann wird der Prozessor einem anderen Prozess neu zugewiesen. Kein Prozess darf den zugewiesenen Prozessor verdrängen. Diese Methode ist offensichtlich ungeeignet für dringende Aufgaben und wird für Echtzeitsysteme nicht empfohlen. 2) Präemptives Scheduling: Diese Methode ermöglicht es dem Scheduler, einen aktuell laufenden Prozess anhand bestimmter Kriterien zu stoppen und den diesem Prozess zugewiesenen Prozessor einem anderen Prozess neu zuzuweisen. Die Prinzipien der Präemption umfassen: ① Zeitscheibenprinzip: Jeder Prozess wird gemäß einer Zeitscheibe ausgeführt. Nach Ablauf einer Zeitscheibe wird die Ausführung des Prozesses gestoppt und neu eingeplant. ② Prioritätsprinzip: Trifft ein neuer Prozess ein und hat er eine höhere Priorität als der aktuell laufende Prozess, wird dieser gestoppt und der Prozessor dem Prozess mit der höheren Priorität zugewiesen. Echtzeitsysteme verwenden in der Regel eine Scheduling-Strategie, die prioritätsbasiertes präemptives Scheduling, Round-Robin-Scheduling und Zwischenplanung kombiniert. Dadurch wird eine höhere Flexibilität bei minimaler Scheduling-Latenz erreicht. 3. Scheduling-Warteschlangenmodell 3.1 Scheduling-Warteschlangenmodell mit reiner Prozessplanung Bereite Prozesse werden in die Warteschlange gestellt und gemäß den Zeitscheiben im Round-Robin-Verfahren zur Ausführung eingeplant. Bei der Ausführung eines Prozesses können folgende drei Situationen eintreten: 1) Wird die Aufgabe innerhalb der Zeitscheibe abgeschlossen, gibt die Aufgabe den Prozessor frei und der Prozess wird beendet. 2) Wird die Aufgabe nicht innerhalb des Zeitfensters abgeschlossen, reiht das Betriebssystem den Prozess ans Ende der Warteschlange für bereite Prozesse ein, wo er auf die nächste Planungsrunde wartet. 3) Wird der Prozess während der Aufgabenausführung blockiert, reiht das Betriebssystem ihn in die Warteschlange für blockierte Prozesse ein. Siehe Abbildung 1. Abbildung 1: Planungswarteschlangenmodell mit reiner Prozessplanung. 3.2 Planungswarteschlangenmodell mit Zwischenplanung. In umfassenderen Betriebssystemen wird neben der Prozessplanung auch die Zwischenplanung eingeführt, um die Speichernutzung zu verbessern. Bei der Einführung der Zwischenplanung im Betriebssystem kann der Bereitschaftszustand eines Prozesses in „Speicherbereit“ (Prozess im Speicher verfügbar) und „Speicherbereit“ (Prozess im externen Speicher verfügbar) unterteilt werden; der Blockierungszustand wird in „Speicher blockiert“ und „Speicher blockiert“ unterteilt. Durch einen Aufruf kann der Zustand „Speicherbereit“ in „Speicherbereit“ und der Zustand „Speicher blockiert“ in „Speicher blockiert“ umgewandelt werden. Durch die Zwischenplanung kann der Zustand „externer Speicher bereit“ in den Zustand „Speicher bereit“ überführt werden. Dies ist in Abbildung 2 dargestellt. Abbildung 2: Warteschlangenmodell für die Prozessplanung mit Zwischenplanung. 4. Analyse der Wind-Planung im VxWorks-Echtzeitkernel. Der Standard-Planungsmechanismus des Wind-Kernels ist die prioritätsbasierte, präemptive Planung. Dabei weist das System dem Prozess mit der höchsten Priorität einen Prozessor zur Ausführung zu. Sobald ein Prozess mit höherer Priorität eintrifft, unterbricht der Prozessplaner die Ausführung des aktuellen Prozesses und weist den Prozessor dem Prozess mit der höheren Priorität zu. Bei mehreren Prozessen gleicher Priorität kommt ein Round-Robin-Verfahren mit Zeitschlitzen zum Einsatz. Dabei wird ein eintreffender Prozess am Ende der Round-Robin-Warteschlange platziert und wartet auf seinen zugewiesenen Zeitschlitz. Wird der Prozess nicht innerhalb seines Zeitschlitzes abgeschlossen, wartet er so lange auf seinen zugewiesenen Zeitschlitz, bis er beendet ist. 4.1 Prioritätsbasierte, präemptive Planung. Es wird prioritätsbasierte, präemptive Planung verwendet. Jeder Task im System hat eine Priorität von 0 bis 255. Sobald der Kernel erkennt, dass ein Task mit höherer Priorität in den Zustand „Bereit“ wechselt, speichert er den Kontext des aktuellen Tasks und ändert dessen Zustand in „Blockiert“. Gleichzeitig wechselt er zum Kontext des Tasks mit höherer Priorität für die Ausführung. Wie in Abbildung 3 dargestellt, wird der Task 1 mit niedriger Priorität vom Task 2 mit mittlerer Priorität und dieser wiederum vom Task 3 mit hoher Priorität verdrängt. Abbildung 3: Prioritätsbasierte präemptive Planung. 4.2 Round-Robin-Scheduling-Algorithmus. Beim Round-Robin-Scheduling-Algorithmus führt eine Gruppe bereiter Tasks mit derselben Priorität abwechselnd Zeitabschnitte einer festgelegten Länge aus. Dies dient der gleichmäßigen Verteilung der Prozessorressourcen. Ohne Round-Robin-Scheduling würde der erste Task, der in einer Gruppe von Tasks mit derselben Priorität den Prozessor belegt, nicht blockiert und diesen exklusiv nutzen. Sofern keine Blockierungen oder andere Probleme auftreten, behält die Aufgabe ihr Recht auf die Prozessornutzung. Wie in Abbildung 4 dargestellt, wird den Aufgaben 1, 2 und 3 mit gleicher Priorität ein vordefinierter Prozessorzeitabschnitt gleichmäßig zugeteilt. Abbildung 4: Round-Robin-Scheduling mit gleicher Priorität. 4.3 Kombination von prioritätsbasiertem präemptivem Scheduling mit Round-Robin-Scheduling. Manchmal kann prioritätsbasiertes präemptives Scheduling mit Round-Robin-Scheduling kombiniert werden. Wenn eine Gruppe von Aufgaben mit gleicher Priorität den Prozessor abwechselnd gleichmäßig nutzt, kann eine Aufgabe mit höherer Priorität die Gruppe unterbrechen, sobald sie bereit ist. Die Gruppe kann den Prozessor erst wieder gemeinsam nutzen, wenn die Ausführungsbedingungen erneut erfüllt sind. Wie in Abbildung 5 dargestellt, unterbricht Aufgabe 4 mit höherer Priorität den Prozessor, wenn die Aufgaben 1, 2 und 3 mit gleicher Priorität den Prozessor abwechselnd nutzen. Nachdem Aufgabe 4 ihre Ausführung abgeschlossen hat, teilt sich die Gruppe den Prozessor wieder. Abbildung 5 zeigt eine Kombination aus prioritätsbasierter präemptiver und Round-Robin-Planung. Für eine flexible Aufgabensteuerung bietet der Wind-Kernel zudem einen dynamischen Prioritätsmechanismus, der es ermöglicht, Aufgabenprioritäten während der Laufzeit dynamisch zu ändern. Gleichzeitig wird ein Prioritätsvererbungsmechanismus implementiert, um Prioritätsinversionen zu verhindern. Mithilfe von Mutex-Semaphoren kann verhindert werden, dass Aufgaben mit hoher Priorität unbegrenzt warten müssen, bis eine Aufgabe mit niedriger Priorität abgeschlossen ist. 5. Fazit: Die Kernel-Planung ist der Kern eines Echtzeitsystems; ihre Qualität beeinflusst direkt die Gesamtleistung des Systems. Die Analyse dieser Kernel-Planung ermöglicht ein tieferes Verständnis der einzigartigen Aspekte des Echtzeitbetriebssystem-Designs. Referenzen: [1] Kong Xiangying. Eingebettetes Echtzeitbetriebssystem VxWorks und seine Entwicklungsumgebung Tornado [M]. Peking: China Electric Power Press, 2001. [2] Raberros. μC/OS 2 II – Echtzeit-Eingebettetes Betriebssystem mit Open-Source-Code [M]. Peking: China Electric Power Press, 2001. [3] Guo Fengyi, Wang Qiping, Sun Hexu. Untersuchung der Materialerosion im Schaltbogen [J]. Journal of Liaoning University of Engineering and Technology, 1997, 16 (3): 374–379. [4] Zhang Jijun. Fuzzy-Hierarchieanalyse-Methode [J]. Fuzzy Systems and Mathematics, 2000, 14 (2): 15–18. [5] Wang Qi. Praktische Fuzzy-Mathematik [M]. Peking: Science and Technology Literature Press, 1991.