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

Symmetric Multi Processing: Skalierung und Affinität

Das Load-Balancing bis zum Kernel 2.4 funktioniert so: Bei jedem Kontextwechsel prüfte der Kernel, ob der neu zugeordnete Prozess nicht besser auf einer anderen CPU laufen sollte, und verschiebt ihn gegebenenfalls. Der Nachteil: Ein Kontextwechsel auf einer CPU beeinträchtigt die anderen CPUs, was sich auf die Performance niederschlägt. Auch neigt der alte Scheduler auf Multiprozessorsystemen dazu, Prozesse unnötig zwischen CPUs hin und her zu schieben (Process Bouncing).

Der neue Scheduler verhindert dies und sorgt dafür, dass Prozesse von der ihnen zugewiesenen CPU "angezogen" werden. Seine neuen Datenstrukturen und die Operatoren für deren Bearbeitung sind auf gute SMP-Skalierbarkeit für Systeme mit vielen CPUs getrimmt (siehe Kasten "Benchmarking"). Jede CPU verwaltet eine eigene Run-Queue. Zudem betreffen die Locking-Mechanismen nur die für den Prozess relevante CPU.

Benchmarking

Spätestens seit Galilei ("Alles messen, was zu messen ist, und messbar machen, was noch nicht messbar ist") hat die Quantifizierung Konjunktur. Aber selbst ohne wissenschaftshistorisches Fundament ist der praktische Leistungsvergleich der Scheduler von Kernel 2.4 und 2.6 interessant. Um deren Performance, den Overhead und die Skalierbarkeit zu testen, eignet sich das Messprogramm Hackbench[3] von Rusty Russell.

Interprozess-Kommunikation als Maßstab

Der Benchmark startet gruppenweise Client- und Serverprozesse, die über Sockets Nachrichten austauschen. Beim den hier vorgestellten Testergebnissen[4] bestand jede Gruppe aus je 25 Clients und 25 Servern. Jeder Client schickte an jeden der 25 Server-Sockets 100 Nachrichten. Hackbench misst die für die Ausführung benötigte Zeit. Jeder Testlauf wurde viermal wiederholt und der Mittelwert als Resultat festgehalten.

Linux 2.6 erläuft sich einen großen Vorsprung

Für den ersten Benchmark (siehe Abbildung 5) kam ein System mit einer CPU (Intel Pentium III, 1 GHz) und 512 MByte RAM zum Einsatz. Auf dem Rechner liegen die Zeitwerte für den Testlauf mit 25 Prozessen bei Linux 2.4 und 2.6 noch nahe beieinander. Bei 100 Prozessen - was der typischen Prozesszahl eines Desktopsystems nahe kommt - hat Linux 2.6 mit 17,86 Sekunden bereits einen weiten Vorsprung vor 2.4 mit 37,63 Sekunden.

Die beiden anderen Diagramme fassen die Ergebnisse der Testläufe auf vier verschiedenen Systemen zusammen:

  • 1 CPU: Pentium III 1 GHz, 512 MByte RAM
  • 2 CPU: Pentium III 850 MHz, 1 GByte RAM
  • 4 CPU: Pentium III 700 MHz, 4 GByte RAM
  • 8 CPU: Pentium III 700 MHz, 8 GByte RAM

Die Abbildung 6 zeigt die Werte für Kernel 2.4 und Abbildung 7 für 2.6. Es ist schön deutlich zu sehen, dass Linux 2.6 bei steigender Prozesszahl auf allen vier Systemen ungleich besser skaliert als der alte Kernel.

Ab 150 Prozessen ist der Kernel 2.4 auf Zwei- und Acht-Prozessor-Systemen nahezu gleich schnell. Linux 2.6 skaliert dagegen bei steigender Prozesszahl in erwartetem Maß - auch auf dem Acht-Prozessor-System.

Abbildung 5: Benötigte Zeit zur Interprozess- Kommunikation in Abhängigkeit von der Anzahl beteiligter Prozesse auf einem Singleprozessor-System mit Kernel 2.4 und 2.6. (Quelle: [4])

Abbildung 6: Benötigte Zeit zur Interprozess- Kommunikation in Abhängigkeit von der Anzahl beteiligter Prozesse auf Systemen mit ein, zwei, vier und acht CPUs mit Kernel 2.4.

Abbildung 7: Benötigte Zeit zur Interprozess- Kommunikation in Abhängigkeit von der Anzahl beteiligter Prozesse auf Systemen mit ein, zwei, vier und acht CPUs mit Kernel 2.6.

Dafür, dass die Run-Queues nicht entarten, sorgt die Funktion »load_balance()«. Sie hält die Anzahl der Prozesse pro CPU etwa im Gleichgewicht und wird immer dann aufgerufen, wenn die Run-Queue eines Prozessors leer ist. Außerdem bedient ein Timer zyklisch die Funktion: Wenn das System gerade idle ist, ruft er »load_balance()« je Millisekunde auf, unter Last alle 200 Millisekunden.

»load_balance()« arbeitet für jede Run-Queue getrennt. Als Erstes lockt der Scheduler die aktuelle Run-Queue, was Veränderungen an ihr durch konkurrierende Zugriffe während des Load-Balancing verhindert. Mit der Funktion »find _busiest_queue()« sucht der Scheduler unter den Run-Queues der anderen CPUs jene mit den meisten Prozessen. Hat keine der Queues mindestens 25 Prozent mehr Prozesse zu erledigen als die aktuelle, beendet sich »load_balance()« und nimmt somit sinnvollerweise keinen Ausgleich zwischen den Run-Queues vor.

Andernfalls liefert »find_busiest_queue()« die Run-Queue mit den meisten Prozessen zurück und »load_balance()« entscheidet, ob aus ihrem »active«- oder »expired«-Array Prozesse entnommen werden. Die gewählten Prozesse verschiebt der Scheduler später in die Run-Queue der aktuellen CPU. »load_balance()« entnimmt Prozesse bevorzugt dem »expired«-Array, da sie wahrscheinlich seit längerer Zeit nicht mehr gelaufen sind und sich deshalb nicht im Cache einer CPU befinden. Nur wenn »expired« leer ist, kommen Prozesse aus dem »active«-Array zum Zuge.

Aus dem gewählten Array wird über das Prioritäts-Bitmap die Liste der Prozesse mit höchster Priorität ausgewählt. Dann wird aus dieser Liste jener Prozess gelöst, der sich weder im Cache der CPU befindet noch zum Zeitpunkt des Load-Balancing schläft und auch durch SMP-Affinität nicht daran gehindert wird, die CPU zu wechseln. Dieser Vorgang wird so lange wiederholt, bis die »runqueues« bis auf das 25-Prozent-Limit ausgeglichen sind. Solange die Run-Queues aber nicht entarten, hat »load_balance()« keinen Anlass dafür, Prozesse zwischen den CPUs zu transferieren.

Als Sonderfall ist es möglich, explizit festzulegen, dass ein Prozess nur auf bestimmten Prozessoren läuft (Hard Affinity) und vom Load-Balancing ausgeschlossen wird. Das passiert über die Bitmaske »cpus_allowed« im Prozessdeskriptor, jedes Bit entspricht einer CPU im System. Die Initialisierung setzt zunächst immer alle Bits auf eins und der Prozess darf auf jeder CPU laufen. Mit der Funktion »sched_affinity()« ist die Bitmaske jetzt beliebig manipulierbar - mindestens ein Bit muss aber gesetzt bleiben. Anschließend verschmäht der Prozess garantiert alle CPUs, deren »cpus_allowed«-Flag nicht gesetzt ist.

Prozess-Preemption und Kontextwechsel

Alle blockierten Prozesse - sie warten ohne Schuld des Schedulers auf ein Ereignis - werden in den so genannten Wait-Queues verwaltet. Prozesse, die von »TASK_RUNNING« in den Zustand »TASK_INTERRUPTIBLE« oder »TASK_ UNINTERRUPTIBLE« wechseln, gelangen in diese Warteschlange. Anschließend ruft der Kernel »schedule()« auf, damit ein anderer Prozess die CPU erhält.

Sobald das Ereignis eintritt, auf das der Prozess in einer Wait-Queue wartet, wird er aufgeweckt, wechselt seinen Zustand in »TASK_RUNNING« zurück, verlässt die Wait-Queue und betritt die Run-Queue. Falls der aufgewachte Prozess eine höhere Priorität besitzt als der gerade ablaufende, unterbricht der Scheduler den aktuell laufenden Prozess zugunsten des eben aufgewachten.

Den Kontextwechsel löst die erwähnte Funktion »schedule()« aus. Der Kernel erfährt über das Flag »need_resched«, wann er »schedule()« aufrufen muss. »need_resched« ist als Nachricht realisiert, die an den Kernel geschickt wird, sobald das Flag gesetzt ist. Das macht die Funktion »scheduler_tick()«, sobald die aktuelle Zeitscheibe abläuft. Zum anderen setzt die Funktion »try_to_ wakeup()« das Flag, sollte ein schlafender Prozess in den Zustand »TASK_ RUNNING« wechseln, der eine höhere Priorität als der zurzeit ablaufende Prozess besitzt.

Den eigentliche Wechsel zwischen zwei Prozessen realisiert die durch »schedule()« aufgerufene Funktion »switch_ context()«. Der Kontextwechsel ist in zwei Schritte gegliedert: »switch_ mm()« tauscht zunächst den virtuelle Adressraum des alten Prozesses gegen den des neuen. Anschließend sichert »switch_to()« den Zustand (Stack, Register) des bisher laufenden Prozesses und lädt den Zustand des neuen.

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.