Open Source im professionellen Einsatz
Linux-Magazin 02/2004
582

Die Entwicklungsziele für den Scheduler

In jedem Multitasking-Betriebssystem stellt der Scheduler die Basis für die virtuelle Nebenläufigkeit der Prozesse: Allein er wacht darüber, dass lauffähige Prozesse CPU-Zeit erhalten. Außerdem berechnet er Prozessprioritäten und Timeslices (Zeitscheiben). Die CPU(s) sollen optimal ausgenutzt werden: Solange es ablauffähige Prozesse gibt, soll ein Prozess der CPU zugeteilt sein.

Die Ziele, die sich die Entwickler um Ingo Molnar für den Scheduler von Kernel 2.6 gesetzt hatten, sind besonders ehrgeizig: Perfekte SMP-Skalierung, SMP-Affinität, geringe Latenz auch bei hoher Systemlast, faire Prioritätenverteilung und eine Komplexität der Ordnung O(1). Dabei gab es für die meisten Einsatzgebiete am Scheduler des Kernels 2.4 gar nicht nicht so viel auszusetzen. Nur bei SMP-Systemen mit mehr als vier CPUs und in Worst-Case-Situationen geriet das System aus den Fugen.

Kaum verwunderlich also, dass die Idee, den Scheduler tief greifend zu überarbeiten und vieles zu erneuern, zunächst bei Linus & Co. auf teils rauen Widerstand stieß. Letztlich konnte Ingo Molnar aber die Vorteile seines Konzepts verdeutlichen. Dass seine Überlegungen sinnvoll waren, spiegelt sich in den messbar positiven Eigenschaften des neuen Schedulers wider.

Alle Linux-Scheduler bisher besaßen eine Komplexität der Ordnung O( n): Die Kosten (also der Aufwand) für das Scheduling wuchsen linear mit der Anzahl n der lauffähigen Prozesse. Das Ziel des neuen Schedulers war, den Scheduling-Aufwand von der Anzahl der lauffähigen Prozesse abzukoppeln, was der Ordnung O(1) entspricht. Konkret: Der Scheduler benötigt für die Verwaltung von fünf lauffähigen Prozessen die gleiche Zeit wie für 500000. Das hieß aber, dass alle Scheduling-Algorithmen so umgeschrieben oder ersetzt werden mussten, dass sie der Ordnung O(1) genügen.

Fairplay: Prozessprioritäten

Seine Strategie bewirkt, dass der neue Scheduler interaktive Prozesse (wie Shells und Editoren) auch unter hoher Systemlast regelmäßig in den Zustand »TASK_RUNNING« versetzt und ablaufen lässt. Die Prozessprioritäten entscheiden, welchen lauffähigen Prozess die CPU beim nächsten Kontextwechsel zugeteilt bekommt - den mit der zum Zeitpunkt des Kontextwechsels höchsten Priorität. Das Besondere: Die Priorität eines Prozesses ändert sich dynamisch während seiner Laufzeit.

Alle lauffähigen Prozesse verwaltet der Scheduler in einer Run-Queue (pro CPU). Sie ist die zentrale Datenstruktur, auf der der Scheduler arbeitet. Neben Verweisen auf die gerade laufende Task, enthält sie Verweise zu den zwei Priority-Arrays »active« und »expired«. Listing 1 zeigt einen Ausschnitt der Struktur »runqueue«, Listing 2 die Struktur der Priority-Arrays.

Das »active«-Array listet alle lauffähigen Prozesse, deren Zeitscheibe noch nicht abgelaufen ist. Wenn die Zeitscheibe eines Prozesse abläuft, verschiebt der Scheduler den Eintrag vom »active«- in das zweite Array »expired«.

Listing 1: Struktur der Run-Queue

01 struct runqueue {
02       /* Spinlock um Run-Queue zu schützen */
03       spinlock_t lock;
04 
05       /* Zahl der lauffähigen Prozesse */
06       unsigned long nr_running;
07       /* Zahl der bisherigen Kontextwechsel */
08       unsigned long nr_switches;
09       /* Zeitstempel des Letzten Tauschs von active- und expired-Array */
10       unsigned long expired_timestamp;
11       /* Zahl der Prozess im Zustand TASK_UNINTERRUPTIBLE */
12       unsigned long nr_uninterruptible;
13 
14       /* Verweis auf Prozessdeskriptor des momentan ablaufenden Prozesses */
15       task_t *curr;
16       /* Verweis auf Prozessdeskriptor der Idle-Task */
17       task_t *idle;
18       /* Verweis auf Memory Map des zuletzt ablaufenden Prozesses */
19       struct mm_struct *prev_mm;
20 
21       /* Verweise auf active- und expired-Array */
22       prio_array_t *active, *expired;
23       /* Priority-Arrays */
24       prio_array_t  arrays[2];
25 
26       ...
27 }

Listing 2: Struktur der Priority-Arrays

struct prio_array {
        /* Zahl der Prozesse */
        int nr_active;
        /* Priorität-Bitmap */
        unsigned long bitmap[BITMAP_SIZE];
        /* Für jede Priorität eine Liste */
        /* der Prozesse mit entsprechender Priorität */
        struct list_head queue[MAX_PRIO];
};

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Kern-Technik

    Der Linux-Kernel hat auch die Aufgabe, die Prozesse und Threads möglichst gleichmäßig auf die vorhandenen CPU-Cores zu verteilen. Einige Funktionen des Scheduling-API helfen dem Anwendungsprogrammierer dabei, den Kernel entsprechend zu beeinflussen.

  • Prozessor-Schwinger

    Die meisten Programme zur Anzeige der CPU-Auslastung wie Top und Xosview bedienen sich aus dem »/proc«-Dateisystem des Linux-Kernels. Unter bestimmten Umständen liefert diese Schnittstelle jedoch unkorrekte Werte. Das beschriebene Patch behebt das Problem.

  • Kern-Technik

    Scheduling ist eine zentrale Aufgabe des Linux-Kernels, der sich dabei um größte Fairness bemüht. Wer aber glaubt, dass damit alle das Gleiche bekommen, der irrt.

  • Kern-Technik

    Scheduling ist eine zentrale Aufgabe des Linux-Kernels, der sich dabei um größte Fairness bemüht. Wer aber glaubt, dass damit alle das Gleiche bekommen, der irrt.

  • Kern-Technik

    Mit dem Anticipatory-IO-Scheduler greift der Linux-Kernel vorausschauend und damit recht effektiv auf Festplatten zu. Der brandneue CFQ-IO-Scheduler tritt als ambitionierter Konkurrent auf. Der Artikel erklärt die Arbeitsweise beider Zugriffsstrategien und zeigt, worin sie sich unterscheiden.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.