Der O(1)-Scheduler im Kernel 2.6

Die Erneuerung des Scheduler im Kernel 2.6 gehört zu den unauffälligen Maßnahmen - kein Programm kann dadurch auch nur eine Funktion mehr bieten. Trotzdem profitieren praktisch alle Anwender von der Generalüberholung: Die Embedded-Fraktion freut die Reaktionsfreudigkeit samt "weicher" Echtzeiteigenschaften, große Multiprozessorsysteme kommen dank viel besserer SMP-Skalierung des neuen Kernels unter Last richtig in Fahrt und die Besitzer normaler Desktop-PCs müssten mit Entzücken auf die zügige Benutzer-System-Interaktion reagieren.

Die Struktur, die Verwaltungsstrategien und die praktischen Vorteile des neuen Schedulers im Vergleich zu dem des Kernels 2.4 vermittelt der folgende Beitrag. Hinzu kommen einige Grundlagen der Prozessverwaltung, die dem Verstehen des Funktionsprinzips dienlich sind.

Prozessverwaltung

Linux verwaltet alle Prozessinformationen mit Hilfe einer doppelt verketteten Liste - der Taskliste. Die Listenelemente (siehe Abbildung 1) sind die Prozessdeskriptoren (»task_struct«) der Prozesse. Der Deskriptor hält alle Informationen seines Prozesses fest: Prozessidentifikator (PID), Adressraum, Prozessstatus, Priorität, Signalhandler et cetera - das »ps«-Kommando macht diese Informationen dem Benutzer zugänglich. Wer neugierig ist, kann die komplette Struktur »task_strut« im Kernel »include/ linux/sched.h« studieren.

Abbildung 1: Linux verwaltet Prozessinformationen mit einer doppelt verketteten Liste - der Taskliste.

Ein Verweis reicht auch

Im Vergleich zu Linux 2.4 speichert der Kernel 2.6 auf dem Kernelstack eines jeden Prozesses nicht mehr den kompletten Prozessdeskriptor, sondern eine Struktur (»thread_info«), die einen Verweis auf den eigentlichen Prozessdeskriptor der Taskliste beinhaltet. Den Prozessdeskriptor selbst erzeugt wie bisher der Slab-Allocator dynamisch.

Den Zustand eines Prozesses speichert die Variable »state« des Prozessdeskriptors. Der Scheduler kennt insgesamt fünf Zustände:

• »TASK_RUNNING« kennzeichnet den Prozess als lauffähig. Er muss auf kein Ereignis warten und kann daher vom Scheduler der CPU zugeordnet werden. Alle Prozesse im Zustand »TASK_RUNNING« zieht der Scheduler für die Ausführung in Betracht.
• Ein blockierter Prozess befindet sich im Zustand »TASK_INTERRUPTIBLE«, da er auf ein Ereignis wartet und vor dessen Eintreten nicht ablaufen kann. Ein Prozess im Zustand »TASK_INTERRUPTIBLE« wird über zwei unterschiedliche Wege in den Zustand »TASK_RUNNING« versetzt: Entweder tritt das Ereignis ein, auf das er gewartet hat, oder der Prozess wird durch ein Signal aufgeweckt.
• »TASK_UNINTERRUPTIBLE« gleicht dem Zustand »TASK_INTERRUPTIBLE«, mit dem Unterschied, dass ein Signal den Prozess nicht aufwecken kann. Der Zustand »TASK_UNINTERRUPTIBLE« wird nur verwendet, wenn zu erwarten ist, dass das Ereignis, auf das der Prozess wartet, zügig eintritt, oder wenn der Prozess ohne Unterbrechung warten soll.
• Wurde ein Prozess beendet, dessen Elternprozess noch nicht den Systemaufruf »wait4()« ausgeführt hat, verbleibt er im Zustand »TASK_ZOMBIE«. So kann auch nach dem Beenden eines Kindprozesses der Elternprozess noch auf seine Daten zugreifen. Nachdem der Elternprozess »wait4()« aufgerufen hat, wird der Kindprozess endgültig beendet, seine Datenstrukturen werden gelöscht. Endet ein Elternprozess vor seinen Kindprozessen, bekommt jedes Kind einen neuen Elternprozess zugeordnet. Dieser ist nunmehr dafür verantwortlich, »wait4()« aufzurufen, sobald der Kindprozess beendet wird. Ansonsten könnten die Kindprozesse den Zustand »TASK_ZOMBIE« nicht verlassen und würden als Leichen im Hauptspeicher zurückbleiben.
• Den Zustand »TASK_STOPPED« erreicht ein Prozess, wenn er beendet wurde und nicht weiter ausführbar ist. In diesen Zustand tritt der Prozess ein, sobald er eines der Signale »SIGSTOP«, »SIGTST«, »SIGTTIN« oder »SIGTTOU« erhält.

Abbildung 2 zeigt die Prozesszustände und ihre Übergänge.

Abbildung 2: Die möglichen Prozesszustände und ihre Übergänge.