Linux als Echtzeitbetriebssystem

---

... [ Was bedeutet Echtzeit? ] ... [ Thema Echtzeit für Linux ] ... [ KURT als eine mögliche Lösung ] ...

---

Übersicht: Linux als Echtzeitbetriebssystem

• Probleme bei traditionellen Multitasking- Betriebssystemen
• Weshalb Scheduler- Unterstützung für Echtzeitprozesse wichtig ist
• Schedulingmechanismen und Event- Handling von Standard- Linux

Probleme bei traditionellen Multitasking- Betriebssystemen

• Swapping: Der relativ zum Speicherzugriff langsame Zugriff auf Festplatten (allgemeiner: I/O- Devices) sorgt dafür, dass Echtzeitprozesse, derren Speicherbereich ausgelagert wurde nicht zeitgerecht ausgeführt werden können.
• Malloc: Anforderung neuen Speichers kann dazu führen, dass der Swapping- Mechanismus angestoßen wird. Dadurch wird die Ausführungszeit von Prozessen verlängert. Es kann also keine Ausführungszeit garantiert werden.
• Kernelmode: Selbst Prozesse mit niedriger Priorität können alle anderen Prozesse blockieren durch Aufrufe von Programmcode, der im Kernelmode läuft.
  Problem des Kernelmode
  
• Interrupts: Werden durch Betriebssystem verwaltet und stehen dem Anwenderprogramm nicht direkt zu Verfügung. Insbesondere können sie über eine gewisse Zeit deaktiviert sein (maskable Interrupts).
• Zeitgranularität: Der Scheduler wird mit einem Basistakt betrieben (Linux: 10 Millisekunden). Nach Ablauf dieser Zeit wird ein Interrupt ausgelöst und die aufgerufene Routine entscheidet, welcher Prozess als nächstes abzuarbeiten ist. Die Granularität bestimmt also die Genauigkeit, mit der Prozesse gestartet werden können. Verfeinert man jedoch die Granularität, so erhöht sich auch der Overhead durch zahlreiche Scheduleraufrufe.
  feine Granularität
  
  
  grobe Granularität
  

---

Weshalb Scheduler- Unterstützung für Echtzeitprozesse wichtig ist

Ein großer Teil der Echtzeitanwendungen ist periodisch (z.B. Multimedia- Applikationen). Nun gibt es verschieden Ansätze ein Programm periodisch zu machen:
Wenn man über das Problem nachdenkt, kommt man bestimmt zunächst zu folgender Lösung, die auf einem Loop/Delay- Mechanismus beruht. Die meisten Betriebssysteme unterstützen die Unterbrechung eines Programms für eine gewisse Zeit (z.B. die sleep- Funktion aus UNIX). In dem folgenden Pseudocode stellt f irgendeine Funktion dar, die Daten verarbeitet.

1 get_time(t);
2 while (read(data) != EoF) {
3     f(data);
4     t = t + period;
5     get_time(t1);
6     delay(t-t1);
7 }

Damit ist zwar der Einfluß der Ausführungszeit auf die Operationen vermieden worden, aber in verdrängenden Multitasking- Betriebssystemen ist dieser Ansatz falsch, da die Anweisungen nicht automatisch Ausgeführt werden. Jede Verdrängung des Prozesses zwischen der Berechnung von t1 und der delay- Operation führt zwangläufig dazu, dass der berechnete Zeitraum für die Verzögerung falsch (zu groß) ist.
Durch die Benutzung einer Funktion (z.B. delay_until), die die Ausführung bis zu einem bestimmten Zeitpunkt anstatt für eine Zeitspanne unterbricht läßt sich dieses Problem lösen.

1 get_time(t);
2 while (read(data) != EoF) {
3     f(data);
4     t = t + period;
5     delay_until(t);
6 }

Auch wenn dadurch ein korrektes Timing gewärleistet ist, so muß der Anwendungsprogrammierer die Handhabung der Zeitinformationen leisten.
Durch Ansatz über perodische Prozesse trennt die funktionale und die zeitliche Spezifikation von der Ausführung des eigentlichen Programms. Hier ruft der Prozess eine Funktion schedule_me auf, um auf den Anfang der nächsten Periode zu warten.

1 p = create_new_process();
2 inform_scheduler(p, processing_time, period);
3 while (TRUE) {
4     schedule_me();
5     /* die eigentliche Berechnung */
6     f();
7 }

Die Funktion schedule_me könnte jetzt zwar wieder durch delay_until implementiert sein, aber der Programmierer muß sich keine Gedanken um die Berechnung der Zeiten machen, da dies durch das Betriebssystem übernommen wird. Der größte Nachteil an delay, delay-until und anderen Scheduling- Mustern auf Benutzerebene ist, dass Scheduler des Betriebssystems keinerlei Informationen das Timing (Perioden), die nachgefragten Resourcen, etc. bekommt. Somit kann nicht getestet werden, ob alle Anforderungen erfüllt werden können und es können Überlastungssituationen auftreten, die dazu führen, dass zeitliche QoS- Garantien nicht eingehalten werden können.


---

Schedulingmechanismen und Event Handling von Standard- Linux

Standard Linux nutzt einen modularen Ansatz, damit verschiedene Prozesse verschiedene Scheduling- Verfahren nutzen können. Unter Linux gibt es normalerweise drei Scheduling- Algorithmen:


1. SCHED_OTHER: Der normale Time-Sharing Scheduler.
2. SCHED_FIFO: Der first-in first-out, Soft- Real- Time Scheduler.
3. SCHED_RR: Der Round-robin, Soft- Real- Time Scheduler.

Der normale Time-Sharing Algorithmus sorgt dafür, dass jeder Prozess entsprechend seiner statischen Priorität einen gerechten Anteil an der CPU- Zeit erhält.
Prozesse, die FIFO oder RR verwenden, werden abgearbeitet bevor die SCHED_OTHER- Prozesse bearbeitet werden. Beim FIFO- Algorithmus werden die Echtzeitprozesse in der Reihenfolge ihres zeitlichen Eintritts abgearbeitet. Beim Round- Robin der erste aus einer Liste bearbeitet und am Ende der Liste wieder eingereiht, wenn er von dem nächsten verdrängt wird. (Ähnlich wie auch die Nichtechtzeitprozesse verarbeitet werden.)
Alle Prozesse werden unabhängig von dem verwendeten Scheduler in einer einzigen Warteschlage verwaltet, was die Zeit, in der der Scheduler darauf reagieren kann, wenn ein Echtzeit- Prozess ablaufen kann, mit beeinflußt.
Die Priorisierung der Prozesse wird durch die goodness- Funktion erreicht. Hier eine vereinfachte Version:

1 int goodness(struct task_struct *p, struct task_struct *prev)
2 {
3     if (p->policy != SCHED_OTHER)
4         return 1000 + p->rt_priority;
5     weigth = dynamic priority;
6     if (weight && (p == prev))
7         weigth +=1;
8     return weigth;
9 }

Soft- Realtime- Prozesse bekommen einen Wert von 1000 plus ihrer RT-Priorität. Andere Prozesse bekommen einen Wert, der auf ihrer aktuellen dynamischen Priorität basiert. Die dynamische Priorität liegt immer zwischen Null und der statischen Priorität und ändert sich über die Laufzeit des Prozesses. Der Prozess, der gerade läuft bekommt einen kleinen Vorteil, da kein Kontextwechsel nötwendig wäre, wenn weiterläuft.

In Standard- Linux ist der Timer- Chip so programmiert, dass er die CPU in festen Abständen unterbricht. Jedesmal wenn dies passiert aktualisiert Linux seine Software- Uhr und prüft, ob es Ereignisse gibt, die auszulösen sind.
Die Softwareuhr zählt die absolute Anzahl der Timer- Interrupts seit der Kernel gestartet wurde. Jeder Timer- Interrupt wird 'jiffy' genannt. Die Anzahl selbst wird in einer globalen Variablen mit dem Namen 'jiffies' gespeichert.
Dies bringt mit sich, dass ein 'jiffy' die kleinste Einheit ist, mit der Ereignisse ausgelöst werden können (die zeitliche Auflösung, Granularität des Kernels). Auf den meisten Plattformen ist dies bei Linux 10 Millisekunden.
Immer wenn eine Benachrichtigung benötigt wird, wird ein Timer- Datensatz generiert und in eine doppelt verkettete Liste nach aufsteigenden Auslösezeitpunkten eingefügt. Diese Datensätze haben folgende Struktur:

1 struct timer_list {
2     struct timer_list *next;
3     struct timer_list *prev;
4     unsigned long expires;
5     unsigned long data;
6     void (*function)(unsigned long);
7 }

Die next und prev Felder sorgen für die Verbindung der Liste. In expires steht, bei welchem jiffy das Ereignis ausgelöst werden soll. Die anderen Felder geben eine Funktion an, die aufgerufen wird, wenn das Ereignis ausgelöst wird und ein Argument, das an diese Funktion übergeben wird.
Immer wenn der Timer- Chip nun einen Interrupt auslöst wird die Interruptserviceroutine (ISR) aufgerufen. Vereinfacht sieht sie so aus:

1 void timer_interrupt()
2 {
3     jiffies++;
4     run_timer_list = 1;
5     do_other_stuff();
6 }

Wichtig ist, dass die ISR nicht direkt die Ereignisbehandlungsroutine aufruft, sondern nur das Flag run_timer_list setzt, das anzeigt, dass die Liste mit den Ereignissen geprüft werden muss. Wenn der Kernel nun die Kontroll an die Benutzerebene übergeben will, überprüft er vorher, ob dieses Flag gesetzt ist und ruft dann ggf. die Funktion run_timer_list auf, die alle Timer ausführt, die bis inklusive des aktuellen jiffy ausgelaufen sind (expires <= jiffies).

1 void run_timer_list()
2 {
3    while (timers in queue) {
4         if (timer->expires <= jiffies){
5             (*timer->function)(timer->data);
6             timer = timer->next;
7             detach timer from queue;
8         } else {
9             break;
10        }
11    }
12}

Durch dieses Vorgehen wird zwar die ISR schnell ausgeführt aber es entsteht auch eine Verzögerung zwischen dem Hardware- Timer- Interrupt und dem Zeitpunkt, an dem die Ereignisbehandlung aufgerufen wird. Beim Standard- Linux mag diese Verzögerung nicht so auffallen, aber wenn die zeitliche Granulatität erhöht wird, fällt sie stärker ins Gewicht.


---

... [ Was bedeutet Echtzeit? ] ... [ Thema Echtzeit für Linux ] ... [ Linux als Echtzeitbetriebssystem ] ... [ KURT als eine mögliche Lösung ] ...

---