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.

Entscheidend für die gute Skalierbarkeit eines Multicore-Systems ist die Verteilung der anstehenden Aufgaben auf die vorhandenen Prozessoren, das so genannte Load Balancing. Der von Linus Torvalds einst hierfür eingeführte große Kernel-Lock, der die Liste mit den lauffähigen Rechenprozessen (Run Queue) absichert, ist mit Kernel 2.6 einem ausgewachsenen und ausgefeilten Multi-CPU-Scheduling-Modell gewichen. Bei diesem Modell verwaltet nun jede CPU ihre eigene Run Queue über den O(1)-Scheduler (siehe Kasten “Ein-Prozessor-Scheduling”).

Stellt eine CPU eine signifikante Ungleichverteilung der Last zwischen sich selbst und einer anderen CPU fest, nimmt sie Rechenprozesse aus der Run Queue einer stark belasteten CPU und verschiebt sie in die eigene (siehe Abbildung 1). Dabei allein auf eine gleichmäßige Verteilung der vorhandenen Aufgaben zu achten, wäre kurzsichtig. Vielmehr muss der Scheduler auch die Leistungsverluste berücksichtigen, die beim Verschieben eines Thread von einem zum anderen Prozessor – der Prozessmigration – durch das unvermeidliche Flushen von Prozessor-Caches entstehen. Diese Leistungsverluste hängen stark von der verwendeten Multiprozessor-Architektur ab.

Abbildung 1: Jede CPU unterhält eine eigene Liste lauffähiger Rechenprozesse (Run Queues). Bei signifikant ungleicher Lastverteilung verschiebt der Scheduler Prozesse zwischen den Run Queues.

Ein-Prozessor-Scheduling

Die Auswahl des Rechenprozesses, der als nächster die (lokale) CPU zugeteilt bekommt, gestaltet Linux prioritätengesteuert. Die insgesamt 140 zur Verfügung stehenden Prioritäten sind in zwei Bereiche eingeteilt: In den Bereich der statischen und den Bereich der dynamischen Prioritäten. Der Unterschied: Der Scheduler erlaubt sich, die Priorität im dynamischen Bereich – von 100 bis 139 – schon mal zu verändern. Die Priorität eines Rechenprozesses im statischen Bereich – 0 bis 99 – modifiziert der Scheduler nicht. Diese Prioritäten sind für Aufgaben mit Echtzeit-Anforderungen vorgesehen, während normale Rechenprozesse typischerweise eine Priorität aus dem dynamischen Bereich erhalten. Für jede Priorität gibt es zwei Listen, in denen die rechenbereiten Tasks und Threads eingetragen sind, die Listen »active« und »expired«. Der Scheduler wählt den ersten Prozess mit höchster Priorität aus der Active-Liste. Hat sich der Prozess nach Ablauf eines Zeitintervalls (Zeitscheibe) nicht beendet oder schlafen gelegt, hängt er ihn an die Expired-Liste an, aus der der Multi-CPU-Scheduler übrigens mit Vorliebe die zu migrierenden Rechenprozesse entnimmt. Neben dem beschriebenen Round-Robin-Verfahren unterstützt Linux im Bereich der statischen Prioritäten (Echtzeit-Prioritäten) auch noch die Auswahl des nächsten Rechenprozesses nach dem Prinzip “Wer zuerst kommt, mahlt zuerst” (First Come First Serve). Abbildung 2: Der Kernel führt fürs Scheduling zwei Listen mit Prozessen, die mit normalen und Echtzeit-Prioritäten versehen sind.

Prozessoren-Zoo

Der geringste Aufwand fällt bei einer Hyperthreading-Architektur (Symmetric Hyperthreading, SMT) an. In diesen Fällen stehen aus Software-Sicht zwei unabhängige Prozessorkerne – sprich zwei logische Prozessoren – zur Verfügung. Da sich beide Kerne aber den Hauptspeicher und die Prozessor-Caches teilen, gibt es erhebliche Abhängigkeiten zwischen den logischen Prozessoren. Die Migration eines Thread von einem logischen Kern zu dem zugehörigen Gegenstück ist so zwar kaum mit Kosten verbunden. Allerdings ist bei dieser Architektur der Leistungsgewinn auch vergleichsweise klein.

Anders beim klassischen symmetrischen Multiprozessing (SMP), aufgebaut etwa aus aktuellen Multicore-Prozessoren wie Athlon-X2 und Core 2 Duo. Bei jedem Prozesswechsel sind auch die eventuell noch in der CPU befindlichen Prozessinformationen obsolet. Noch dicker kommt es auf Numa-Systemen, bei denen Prozessoren auf die ihnen zugewiesenen Speicherbereiche schneller zugreifen können als auf das von anderen CPUs verwaltete Memory. In der Realität kommen die verschiedenen Basisarchitekturen oft in Kombination vor. Ein Numa-System besteht beispielsweise aus mehreren Knoten (Nodes), wobei jeder Knoten aus mehreren Prozessoren aufgebaut ist (SMP). Auch Hyperthreading-CPUs sind dabei einsetzbar.

Scheduling Domains

Um mit den unterschiedlichen Multiprozessor-Architekturen zurechtzukommen, setzt Linux auf das Konzept der Scheduling Domains und der Scheduling-Gruppen. Eine Scheduling Domain besteht aus mehreren Scheduling-Gruppen. Eine Gruppe repräsentiert dabei entweder eine CPU oder eine untergeordnete Scheduling Domain. Ein Zwei-Prozessor-System beispielsweise modelliert Linux in einer Scheduling Domain mit zwei Gruppen: für jede CPU eine. Ein Rechner mit Hyperthreading-Prozessor wird übrigens ebenfalls auf eine Domain und zwei Gruppen abgebildet.

Ein heterogenes System dagegen besteht aus mehreren Domains, wobei die Scheduling-Gruppen der übergeordneten Container (Domains) nicht Prozessoren, sondern eben weitere Domains repräsentieren. Ein Beispiel für eine solche baumartige Topologie zeigt Abbildung 3.

Abbildung 3: Linux bildet eine Architektur mit zwei Hyperthreading-Prozessoren auf drei Scheduling-Domains ab: zwei Basis-Domains und die übergeordnete Level-1-Domain, die alle vier CPUs umfasst. Die Basis-Domains enthalten jeweils einen Prozessor mit zwei logischen Kernen.

Innerhalb der Scheduling Domain sorgt der Kernel für ausbalancierte Lastverteilung zwischen den Gruppen, das Verfahren hierzu ist konfigurierbar. So kann der Anwender beim Booten festlegen, ob beim Aufruf des Systemcalls »exec« oder »fork« ausbalanciert werden soll, ob dies beim Aufwecken eines schlafenden Thread geschieht oder nur, wenn die CPU leer läuft (siehe Tabelle 2).

Um auch einen rechenintensiven Prozess, der sich nicht schlafen legt und kein »exec« oder »fork« aufruft, lasttechnisch zu verteilen, ist für jede Scheduling Domain ein individuelles Intervall spezifizierbar, innerhalb dessen der Scheduler in jedem Fall neu ausbalanciert. Dies geschieht über den neuen Soft-IRQ »SCHED_SOFTIRQ« und die Funktion »run_rebalance_domain()«.

Linux unterscheidet prinzipiell drei Domain-Arten: SMT, SMP und Numa. Gleich beim Booten legt sich das System auf eine Domain-Topology fest. Identifiziert der Kernel eine Hyperthreading-CPU, ruft er zur Initialisierung der zugehörigen Domain das Makro »SD_SIBLING_INIT()« auf. Zur Initialisierung einer klassischen SMP-Domain dient »SD_CPU_INIT()«. Einen Numa-Node initialisiert »SD_NODE_INIT()«. Die Makros sind architekturspezifisch und finden sich zum Beispiel in »arch/i386/kernel/topology.h«. Die für die x86-Systeme verwendeten Default-Load-Balancing-Flags listet Tabelle 1 auf.

Grundsätzlich gilt: SMT-Domains balanciert der Kernel entsprechend den geringen Verlusten bei der Prozessmigration häufig aus, Numa-Domains dagegen eher selten. Zum Ausbalancieren ist es natürlich notwendig, die Last jeder Scheduling-Gruppe zu bestimmen. Hierfür skaliert der Kernel die Last »load« einer CPU mit Hilfe der für jede Scheduling-Gruppe vorhandenen Variablen »cpu_power«. Während eine Zwei-Prozessor-SMP-Scheduling-Gruppe eine »cpu_power« von 2 besitzt, kann ein Hyperthreading-Prozessor nur mit 1,1 aufwarten.

Kommt der Scheduler zu dem Schluss, dass eine Prozessmigration sinnvoll ist, aktiviert er den höchstprioren Kernelthread »migration/X«, der für jede CPU einmal im System vorhanden ist und die eigentliche Migration durchführt. Allerdings werden nur jene Rechenprozesse migriert, die gerade nicht aktiv sind und die nicht Cache-hot sind, von denen der Scheduler also annimmt, dass sich im CPU-Cache keine für die Weiterverarbeitung nützliche Information befindet. Sind diese Anforderungen erfüllt, verhindert die CPU-Affinität unter Umständen noch eine Prozessverschiebung. Jeder Rechenprozess kann nämlich für sich bestimmen, auf welchem Prozessor er ablaufen soll und damit auch, auf welchem eben nicht.

Die Systemcalls »sched_set_affinity()« und »sched_get_affinity()« lesen respektive verändern die CPU-Affinität. Damit lassen sich CPU-Blocker auf eine CPU festlegen und die Cache-Performance optimieren. Außerdem können die zu einer Gruppe gehörigen Threads fest einer CPU zugeordnet werden. Auch das führt, da sich die Threads ihre Daten im Datensegment und damit im CPU-Cache teilen, unter Umständen zu einer Performance-Steigerung.

Isolationshaft für Realzeit

Besonders sinnvoll ist das Setzen von CPU-Affinitäten im Umfeld von Realzeit-Applikationen. Der Kernel bietet nämlich mit der Bootoption

isolcpus=<CPU-Nummer>,...,<CPU-Nummer>

die Möglichkeit, einen oder mehrere Prozessoren vom Ausbalancieren auszunehmen. Der einzige Weg, einen Rechenprozess auf eine isolierte CPU zu verschieben respektive von dieser wegzunehmen, ist der Systemcall »sched_set_affinity()«. Wer also eine isolierte CPU für Realzeit-Applikationen reserviert, kann mit wesentlich deterministischerem Zeitverhalten rechnen.

Der Applikationscode in Listing 1 zeigt, wie man die Affinität auslesen, setzen und damit auch eine Prozessmigration erzwingen kann. Eine Beschreibung der verwendeten Makros und Funktionen gibt [2]. Dieser Code gehört aber nicht in ein Produktivsystem. Der Einfachheit halber geht er nämlich einige Kompromisse ein: Er ist auf Zwei-Prozessor-Maschinen angepasst. Außerdem benutzt er nicht den mit Kernel 2.6.19 eingeführten Systemcall »get_cpu()«, der die CPU bestimmt, auf der der aktuelle Prozess läuft. Da der Systemcall neu ist, fehlt er in der Standard-C-Bibliothek.

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <unistd.h>
04 #define __USE_GNU
05 #include <sched.h>
06 #include <errno.h>
07 
08 static unsigned int getcpu()
09 {
10     unsigned int i, cpuid;
11     FILE *fp;
12 
13     fp=fopen( "/proc/self/stat", "r" );
14     if( fp==NULL ) {
15         perror( "/proc/self/stat" );
16         exit( -1 );
17     }
18     fscanf( fp, "%*d %*s %*s" );
19     for( i=3; i<39; i++ ) // Das 39. Feld enthaelt die CPU-Id.
20         fscanf( fp, "%d", &cpuid );
21     return cpuid;
22 }
23 
24 static unsigned int getaffinity( cpu_set_t *mask )
25 {
26     CPU_ZERO( mask );
27     if( sched_getaffinity( getpid(), sizeof(*mask), mask) ) {
28         perror("sched_setaffinity");
29         exit( -2 );
30     }
31     return mask->__bits[0]; // XXX - quick hack
32 }
33 
34 int main( int argc, char **argv )
35 {
36     cpu_set_t mask;
37     int cpuid;
38 
39     cpuid = getcpu();
40     printf("Aktive CPU: %dn", cpuid );
41     printf("Affinity-Maske: 0x%xn", getaffinity( &mask ) );
42     CPU_CLR( cpuid, &mask ); // Aktuelle CPU ausschliessen.
43     printf("Setzen der Affinität auf: 0x%lxn", mask.__bits[0] );
44     if( sched_setaffinity( getpid(), sizeof(mask), &mask ) ) {
45         perror("sched_setaffinity"); // UP-System???
46     }
47     printf("Affinity-Maske: 0x%xn", getaffinity( &mask ) );
48     printf("Aktive CPU %dn", getcpu() );
49 
50     return 0;
51 }

Der universelle Funktionsaufruf »syscall()« hilft nur auf einer i386-Architektur weiter. Auf einer x86-64-Architektur ist »get_cpu()« als so genannter »vsyscall« realisiert, einem Systemcall, der allein im Userspace – ohne Übergang in die Kernelebene – abläuft. Vsyscalls setzen aber andere Aufrufmechanismen voraus.Der Beispielcode entnimmt deshalb die Information, auf welcher CPU der aktive Prozess läuft, der Proc-Datei »/proc/self/stat«. Die Information steht dort im 39. Feld, siehe Listing 1, Zeile 19.

Das Programm aus Listing 1 gibt die CPU aus, auf der es läuft. Danach erzwingt es eine Prozessmigration, indem es die aktuell genutzte CPU aus dem Bitfeld der affinen Prozessoren entfernt. Die erneute Ausgabe der CPU (Abbildung 4) bestätigt die Prozessverschiebung.

Abbildung 4: Mit Hilfe des Systemcalls »sched_setaffinity()« lässt sich eine Prozessmigration erzwingen.

Handarbeit hilft

Bleibt abschließend anzumerken, dass vielfältige Methoden – die zudem von Kernelversion zu Kernelversion verfeinert werden – für eine bessere Lastverteilung zwischen den Prozessoren sorgen. Insbesondere wer hohe Anforderungen an das Zeitverhalten von Prozessen stellt, kann mit Hilfe der CPU-Affinität den Scheduler auf den richtigen Weg bringen. (ofr)