el-context-switching-fig4.jpg

Wie jedes andere Betriebssystem weist ein RTOS die verfügbare Verarbeitungszeit (CPU-Zeit) den verschiedenen Aufgaben zu (Tasks/Prozesse und Threads). Jedem Thread stellt es eine Laufzeitumgebung mit einem eigenen virtuellen Prozessor zur Verfügung (Multithreading), inklusive Registersatz, Programmzähler, Stackspeicher und Stackpointer. Obwohl zu jedem Zeitpunkt nur der jeweils ausgeführte Thread die physischen (reale vorhandenen) Prozessor-Ressourcen nutzt, arbeiten die einzelnen Threads so, als würden sie ihre eigenen privaten Ressourcen manipulieren, sie haben alle ihre eigenen Kontext.

Eckdaten

Embedded-Entwickler stehen oft vor der Frage, ob sie ihr System direkt programmieren und alle Aufgaben in einer großen Schleife abarbeiten, oder ob sie auf ein RTOS zurückgreifen, dessen Scheduler den Ablauf steuert. Dank prioritätsgesteuerter Präemption lässt sich die Reaktion des Systems exakt vorhersagen. Allerdings scheuen manche Designer den Overhead eines Echtzeit-Betriebssystems. Express Logic erklärt hier, welche Probleme auftreten können und erklärt, wie Preemption-Threshold-Scheduling den Overhead deutlich senken kann.

Um für die Echtzeitfähigkeit zu sorgen, kontrolliert das RTOS die Verarbeitung der Threads. Jedem Thread gibt der Entwickler eine Priorität und legt damit fest, welcher Thread zum Zuge kommt, wenn mehrere Threads zur Verarbeitung anstehen. Sobald ein Thread verarbeitungsbereit wird, dessen Priorität höher ist als die des gerade laufenden Threads, legt das RTOS den Kontext des laufenden Threads im Speicher ab und stellt stattdessen den Kontext des neuen Threads mit höherer Priorität wieder her. Dieser Thread-Austausch heißt Kontextwechsel.

Die Kontrolle behalten

Dank Echtzeit-Betriebssystemen muss sich die Applikationssoftware nicht um die Zuweisung des Prozessors kümmern. Damit ist es deutlich einfacher, das Laufzeitverhalten eines Embedded-Geräts vorherzusagen und genau einzustellen.

Um echtzeitfähig zu sein, muss sich ein RTOS um Präemption kümmern. Damit wechselt das RTOS umgehend auf einen höherprioren Thread, ohne dass es wartet bis sich der niederpriore Thread beendet. Für die Threads selbst ist dieser Vorgang transparent, sie müssen sich um nichts kümmern. Eine Betriebsumgebung ohne Präemption wäre im Prinzip nur eine Abwandlung der althergebrachten Polling-Schleifen einfacher Embedded-Produkte. Das präemptive Scheduling von Threads garantiert, dass kritische Threads sofort zum Zuge kommen und damit ihre Echtzeitvorgaben einhalten können.

Unter bestimmten Bedingungen kann das präemptive Scheduling allerdings einen erheblichen Kontextwechsel-Aufwand mit sich bringen. Damit vergeudet das RTOS Prozessorzyklen, und außerdem steht die Echtzeitfähigkeit des Systems auf dem Spiel.

Kontextwechsel und deren Folgen

Threads können vier verschiedene Zustände einnehmen: Im „Ready“-Zustand ist der Thread bereit zur Ausführung, führt aber momentan keine Befehle aus. Im Zustand „Running“ führt der Thread Anweisungen aus. Bei „Suspended“ wartet der Thread auf ein Ereignis, zum Beispiel auf eine Meldung in einer Warteschlange, auf einen Semaphor, das Ablaufen eines Timers oder ähnliches. Im Zustand „Terminated“ hat der Thread seine Verarbeitung beendet und steht nicht zur Verarbeitung an.

Der Entwickler weist den Threads Prioritäten zu, um ihre relative Bedeutung zu kennzeichnen und festzulegen, in welcher Reihenfolge die „Ready“-Threads Zugang zur CPU erhalten. Als Prioritäten dienen üblicherweise ganze Zahlen von 0 bis N, wobei die 0 je nach RTOS für die höchste oder die niedrigste Priorität steht. Die Priorität eines Threads kann sich dynamisch verändern, außerdem können mehrere Threads die gleiche Priorität haben.

Wenn ein Thread ausgeführt wird und ein anderer Thread mit höherer Priorität in den „Ready“-Zustand wechselt, unterbricht das RTOS den gerade laufenden Thread (dieser Vorgang heißt Präemption) und führt einen Kontextwechsel durch, um den Thread mit der höheren Priorität zu verarbeiten. Im Rahmen eines Kontextwechsels legt das RTOS den Kontext des bisher ausgeführten Threads auf seinen Stack. Anschließend ruft es den Kontext des neuen Threads ab und lädt die Register und den Programmzähler der CPU.

Tabelle 1: Je nach RTOS und Prozessor können Kontextwechsel zwischen 50 und 500 Zyklen dauern.

Tabelle 1: Je nach RTOS und Prozessor können Kontextwechsel zwischen 50 und 500 Zyklen dauern.Express Logic

Ein solcher Kontextwechsel ist ein recht komplexer Vorgang, der je nach RTOS und Prozessor zwischen 50 und 500 Zyklen beanspruchen kann (Tabelle 1). Dieser große Aufwand ist auch der Grund für die Sorgfalt, die bei Echtzeit-Betriebssystemen auf die Optimierung der Kontextwechsel sowie darauf verwendet wird, die Häufigkeit dieses Vorgangs zu minimieren. Diesem Ziel dient auch das Preemption-Threshold-Scheduling.

Scheduling und Schleifen

Auch Anwendungen, die zwar kein Echtzeit-Betriebssystem benötigen, aber aus mehreren Threads oder Tasks zusammengesetzt sind, benötigen eine Steuerung wann welcher Thread an der Reihe ist. Eine einfache sequenzielle Schleife kommt hierfür ebenso in Frage wie eine ausgefeiltere Variante (Big-Loop) mit einer Statusprüfung. Die Big-Loop startet nur diejenigen Funktionen, die tatsächlich etwas zu tun haben. Bei derartigen Schleifen handelt es sich bereits um eine Art Scheduler, obwohl sie ineffizient sind und es ihnen an Reaktionsschnelligkeit mangelt, speziell wenn die Zahl der Threads und Funktionen zunimmt. Ein RTOS-Scheduler behält dagegen stets den Überblick, welche Aktivität das System zum jeweiligen Zeitpunkt verarbeiten muss.

Bild 1: Der farbig hinterlegte Bereich zeigt, wie ein Interrupt zunächst die Präemption eines Threads mit der Priorität 1 auslöst, gefolgt von Threads mit den Prioritäten 4 und 8 bis hin zu einem Thread mit der Priorität 16.

Bild 1: Der farbig hinterlegte Bereich zeigt, wie ein Interrupt zunächst die Präemption eines Threads mit der Priorität 1 auslöst, gefolgt von Threads mit den Prioritäten 4 und 8 bis hin zu einem Thread mit der Priorität 16.Express Logic

Echtzeit-Scheduler sind in aller Regel präemptiv. Sie sorgen also stets dafür, dass der Thread mit der höchsten Priorität ausgeführt wird, während die übrigen warten müssen. RTOS-Scheduler können das zyklische Round-Robin-Scheduling nutzen, das große Ähnlichkeit mit dem eben erwähnten Big-Loop-Verfahren hat. Es handelt sich dabei um eine etwas weiter ausgearbeitete Form des Round-Robin-Schedulings, das den einzelnen Threads jeweils einen bestimmten Prozentsatz der CPU-Zeit zuweist, statt den einzelnen Threads die Erlaubnis zu erteilen, so lange zu laufen, bis sie beendet sind oder ihre Arbeit von selbst unterbrechen. Der RTOS-Scheduler führt Kontextwechsel nach Bedarf aus und gibt den Threads die Möglichkeit, in den Sleep-Status zu wechseln, die CPU-Nutzung abzutreten oder den Pool der auf die CPU wartenden Threads zu verlassen. Bild 1 zeigt ein Beispiel für die Thread-Präemption im Echtzeit-Betriebssystem Thread-X von Express Logic, dargestellt mit dem Analyse-Tool Trace-X.

Beim Multithreading nutzen mehrere Threads die CPU gemeinsam. Wenn ein Thread in einem solchen System in seinem Verarbeitungsfluss unterbrochen wird, verzichtet er auf ein Polling (Warteschleife, die fortlaufend prüft ob er mit der Verarbeitung fortfahren kann). Stattdessen überlässt der Thread die CPU den anderen Threads, die nicht auf etwas Bestimmtes warten müssen. Als Beispiel eignet sich ein einfaches System mit Thread_A und Thread_B. Wenn Thread_A während seines Betriebs eine E/A-Operation anstößt, deren Beendigung mehrere hundert Zyklen dauern kann, wartet er nicht in einer Schleife, sondern wird für die Dauer der E/A-Operation unterbrochen. Während dieser Zeit kann Thread_B die CPU nutzen. Hierfür ist ein Kontextwechsel der weiter oben beschriebenen Art erforderlich. Nach Abschluss der erwähnten E/A-Operation nimmt Thread_A die Arbeit wieder auf. Verglichen mit der Big-Loop-Methode und anderen nicht-präemptiven Scheduling-Verfahren sorgt das Multithreading für eine effizientere Nutzung der CPU-Ressourcen.

Anforderungen der Präemption

Eine Präemption kann entweder als Reaktion auf einen Interrupt, also eine Unterbrechung von außen erfolgen, oder vom gerade laufenden Thread selbst veranlasst werden. Das präemptive Scheduling in Echtzeitsystemen und RTOS-Produkten ermöglicht eine zügige Reaktion auf externe Ereignisse, wenn ein Thread auf ein solches Ereignis hin umgehend gestartet werden muss oder ein Thread bis zu einem bestimmten Zeitpunkt verarbeitet sein muss. Der maximalen Reaktionsgeschwindigkeit steht allerdings ein großer Verarbeitungsaufwand gegenüber, da es niemals ohne Kontextwechsel geht. Das Präemptions-Konzept ist aber auch mit Problemen behaftet:

  • Thread Starvation: Bei diesem Problem, das 1:1 übersetzt das Verhungern eines Threads bedeutet, gelangt ein Thread niemals zur Ausführung, weil die Verarbeitung eines Threads mit höherer Priorität nicht endet. Entwickler sollten deshalb die Situation vermeiden, dass ein Thread hoher Priorität in eine Endlosschleife gerät oder übermäßig viel CPU-Zeit beansprucht.
  • Overhead: In Situationen mit vielen Kontextwechseln kann sich der Verarbeitungsaufwand so aufsummieren, dass gravierende Auswirkungen auf die Performance entstehen.
  • Prioritätsinversion: Dieses Problem tritt auf, wenn ein Thread mit hoher Priorität auf eine gemeinsam genutzte Ressource wartet, die von einem niederprioren Thread beansprucht wird, der die Ressource aber nicht freigeben kann, weil er von einem Thread mit dazwischen liegender Priorität unterbrochen wird.

Bild 2: Während ein traditioneller prioritätsgesteuerter Scheduler jede Task sofort unterbricht, wenn eine höherpriore Aufgabe ansteht (links oben), vermeidet das Preemption-Threshold-Scheduling viele verzichtbare Kontextwechsel (rechts unten).

Bild 2: Während ein traditioneller prioritätsgesteuerter Scheduler jede Task sofort unterbricht, wenn eine höherpriore Aufgabe ansteht (links oben), vermeidet das Preemption-Threshold-Scheduling viele verzichtbare Kontextwechsel (rechts unten).Express Logic

Preemption-Threshold-Scheduling

Beim Preemption-Threshold-Scheduling (PTS) muss eine bestimmte Priorität überschritten sein, damit das RTOS einen Thread tatsächlich unterbricht (Bild 2). Das PTS-Verfahren verhindert einige Präemptionen, sodass einige Kontextwechsel nicht stattfinden und der Overhead entsprechend sinkt.

Normalerweise kann ein Thread von jedem Thread unterbrochen werden, dessen Priorität höher ist. Beim PTS-Verfahren dagegen ist die Präemption eines Threads nur möglich, wenn die Priorität des unterbrechenden Threads höher ist als die Preemption Threshold des gerade laufenden Threads. In einem vollständig präemptiven System ist der Preemption-Threshold-Wert identisch mit der Priorität des Threads. Setzt man den Preemption-Threshold-Wert dagegen höher an als die eigentliche Priorität des Threads, werden Präemptionen durch Threads, deren Priorität zwischen beiden Werten liegt, unterbunden.

Tabelle 2: Preemption-Threshold-Scheduling verhindert einige Präemptionen, wodurch einige Kontextwechsel unterbleiben und der Verarbeitungsaufwand sinkt.

Tabelle 2: Preemption-Threshold-Scheduling verhindert einige Präemptionen, wodurch einige Kontextwechsel unterbleiben und der Verarbeitungsaufwand sinkt.Express Logic

Tabelle 2 zeigt ein Beispiel. Hier könnte ein Thread mit der Priorität 20 normalerweise von einem Thread unterbrochen werden, dessen Prioritätswert 19, 18, 17, 16… lautet. Wäre aber der Preemption-Threshold des Threads auf 15 eingestellt, wäre eine Präemption nur durch Threads mit einer höheren Priorität als 15 (also einer niedrigeren Prioritätszahl) zulässig: Eine Präemption durch Threads mit den Prioritäten 19 bis 15 wäre ausgeschlossen, während sie bei Prioritäten von 14 und höher erlaubt wäre. Die Angabe eines Preemption-Thresholds ist optional und kann für alle Threads, bestimmte Threads oder keine Threads erfolgen. Ist kein Preemption-Threshold-Wert spezifiziert, können Präemptionen durch alle Threads mit höherer Priorität erfolgen. Ist dagegen ein Preemption-Threshold angegeben, sind Präemptionen nur durch Threads zulässig, deren Priorität höher ist als der angegebene Wert.

Weniger Aufwand

Ein vollständig präemptiver Scheduler verursacht einen erheblichen Verarbeitungsaufwand, der zu Lasten der Systemeffizienz geht. Im Gegensatz dazu kann das Preemption-Threshold-Scheduling die Zahl der Kontextwechsel verringern und die Voraussetzungen für mehr Performance schaffen.

Bill Lamie

ist CEO von Express Logic in San Diego, Kalifornien.

(lei)

Sie möchten gerne weiterlesen?