Scheduling im Kernel 2.6

O(1) Algorithmen

Die Komplexität von Algorithmen wird in der O-Notation angegeben, als mathematische Beschreibung der Laufzeit eines Algorithmus. Eine Komplexität von O(n) bezeichnet Algorithmen, deren Laufzeit linear von der Menge der Eingabedaten abhängt. Ein Algorithmus der Komplexität O(1) läuft in konstanter Laufzeit unabhängig von der Eingabemenge.
Beim Scheduler im Linux Kernel 2.4 war die Laufzeit des Schedulers abhängig von der Anzahl der wartenden Prozesse. So ist der Scheduler gerade dann langsamer geworden, wenn mehr Prozesse etwas von der kostbaren Rechenzeit benutzen wollten.
Der Scheduler im Linux Kernel 2.6 läuft dagegen nicht nur immer gleich lang, sondern auch noch schneller und effizienter.

Warteschlangen

Der Scheduler verwaltet für jeden Prozessor im System eine Warteschlange. In dieser Runqueue sind die Prozesse verlinkt, die auf Rechenzeit warten.
Eine Runqueue wiederum besteht aus zwei Prioritäts-Arrays, den wichtigsten Elementen einer Runqueue. In den Arrays sind für jede Priorität Zeiger auf verkettete Listen gespeichert. Jede dieser Listen wiederum enthält die laufwilligen Prozesse.
Zusätzlich sind in den Arrays noch Informationen über die Anzahl der wartenden Prozesse und eine Bitmap enthalten, die signalisiert welche der verketteten Listen Einträge enthält.
Die beiden Prioritäts-Arrays einer Runqueue sind deklariert als Active und Expired.

Der Scheduler sucht nun die nicht-leere Liste mit der höchsten Priorität im Active-Array und startet den Prozess am Anfang der entsprechenden verketteten Liste. Diese Auswahl und der Wechsel erfolgt,

Im letztgenannten Fall wird der Prozess in das expired-Array verschoben und dabei eine neue Zeitscheibe für seinen nächsten Durchlauf berechnet. Eine Ausnahme bilden hier interaktive Prozesse, die solange im active-Array neu einsortiert werden, bis alle CPU-Fresser abgearbeitet sind (siehe Latenz und Prioritäten).
Sobald alle vordefinierten Zeiten im active-Array verbraucht, werden die Zeiger von active und expired vertauscht und der Zyklus beginnt von Neuem.

Prioritäten

Bei Programmstart erhält jeder Prozess eine statische Prioriät auf einer negativen Skale von -19 bis 20. Default ist 0. Je niedriger der Wert, desto höher die statische Priorität.
Der Scheduler berechnet während der Laufzeit für jeden Prozess eine dynamische Priorität im Bereich von -5 bis 5, die zur statischen dazu addiert wird.
So können interaktive Prozesse (E/A-lastige) belohnt und CPU-Fresser bestraft werden.
Die Einordnung in diese beiden Kategorien erfolgt durch die mittlere Schlafzeit eines Prozesses. Die Zeit, die ein Prozess schlafend und wartend verbringt, wird als Indikator für die dynamische Priorität verwendet. Wartezeit wird bis zur maximalen mittleren Schlafzeit auf dieselbe addiert und Rechenzeit von ihr abgezogen. So ergibt sich eine Skala, die linear auf Bereich der dynamischen Priorität interpoliert werden kann.

Zeitscheiben

Für jeden Prozess wird individuell bestimmt, wieviel Rechenzeit er am Stück benutzen darf. Dieses Zeitkontigent oder Zeitscheibe wird nach jeden Ablauf neu berechnet und ist abhängig von der dynamischen Priorität.
Die Zeitscheibe kann zwischen 10 und 200ms lang sein und dauert im Mittel 100ms.
Prozesse mit hoher Priorität bekommen mehr Zeit und Prozesse mit niedriger Priorität weniger.
Wie bereits erwähnt, erhöhen längere Zeitscheiben die Effizienz des Gesamtsystems, weil der Scheduler weniger oft laufen muss und weniger Kontext-Wechsel durchgeführt werden müssen. Generell kürzere Zeiten würden die Latenz und Interaktivität verbessern, erzeugen aber mehr Overhead.
Die individuelle Berechnung ermöglicht einen guten Kompromiss zwischen diesen beiden Anforderungen.

Unterbrechen

Prozesse laufen nicht immer. Besonders interaktive Prozesse verbringen sehr viel Zeit mit Warten. Während sie auf ein Ereignis warten, dürfen sie nicht laufen oder verplant werden. Andernfalls müssten sie in einer Schleife prüfen, ob das Ereignis, auf das sie warten, eingetreten ist. Stattdessen werden sie in besonderen Warteschlangen geparkt, die einer Ereignisroutine zugeordnet sind.
Solche Ereignisse können in der Regel Antworten von externen Kanälen sein (ein Device sendet Interrupt und meldet so neue Daten), Nachrichten von anderen Prozessen oder die Systemclock sein.
Die entsprechende Ereignisroutine weckt dann die schlafenden Prozesse wieder auf und schiebt sie zurück in das Active-Array.
Durch diese Interrupts - Unterbrechungen - kann der Scheduler laufende Prozesse anhalten und die Prioritäten neu prüfen.

Zeit zählen

Per Interrupt von der uhr wird alle 10ms eine Funktion scheduler_tick() ausgeführt, die hauptsächlich das Zeitkontingent des aktuell laufenden Prozesse dekrementiert.
Sollte die Zeitscheibe dadurch verbraucht worden sein, wird

Prozessplanung

Die Hauptroutine schedule() wird ausgeführt,

Zu Beginn wird die preemption deaktiviert, also die Unterbrechbarkeit durch Interrupts. Dann werden Statistiken des abgelaufenen Prozesses berechnet (Laufzeit, schlafzeit, ...) und führt andere Aufräumarbeiten in den Listen aus.
Falls das Active-Array leer ist, wird jetzt auf das expired-Array umgeschaltet.
Sollte dadurch kein wartender Prozess gefunden werden, kann in den Runqueues anderer Prozessoren nachgesehen werden, ob einzelne Prozesse von dort übernommen werden können
Ist jetzt immer noch kein Prozess zur Ausführung bereit, wird der spezielle idle() Prozess ausgeführt bis zum nächsten Aufruf von schedule()
Es erfolgt ein Kontext-Wechsel zum neuen Prozess und die preemption wird wieder aktiviert.

Prozessoren planen

Normalerweise bleiben Prozesse auf ihrem Prozessor um Cache- und Speicherzugriffe zu optimieren. Sollte ein Prozessor jedoch sehr viel mehr zu tun haben, als andere Prozessoren im System, können diese einzelne Prozesse übernehmen. Ein Prozessor mit geringer Auslastung wird dabei immer versuchen Prozessoren mit höherer Auslastung zu entlasten, so können die Prozesse gleichmäßig verteilt werden.