Open Source im professionellen Einsatz
Linux-Magazin 05/2007

Kernel- und Treiberprogrammierung mit dem Kernel 2.6 - Folge 33

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.

1580

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.

Tabelle 1: Defaults
für Multiprozessor-Architekturen

 

SMT

SMP

Numa

SD_SIBLING_INIT()

SD_CPU_INIT()

SD_NODE_INIT()

SD_BALANCE_NEWIDLE

SD_BALANCE_NEWIDLE

SD_BALANCE_FORK

SD_BALANCE_EXEC

SD_BALANCE_EXEC

SD_BALANCE_EXEC

SD_WAKE_IDLE

-

SD_WAKE_BALANCE

SD_WAKE_AFFINE

SD_WAKE_AFFINE

-

SD_SHARE_CPU_POWER

SD_SHARE_PKG_RESOURCES

SD_SERIALIZE

Tabelle 2: Scheduler
Domain Flags

 

Symbol

Bedeutung

SD_WAKE_IDLE

Dieses Flag ist dann relevant, wenn der Kernel einen
schlafenden Rechenprozess aufweckt. Ist für die
zugehörige Scheduling Domain das Flag gesetzt, verschiebt der
Scheduler den aufgeweckten Prozess auf eine andere CPU innerhalb
der Domain, wenn diese idle ist.

SD_WAKE_AFFINE

Kommt zur Wirkung, wenn ein schlafender Rechenprozess
aufgeweckt wird. Wenn der geweckte Prozess cache-cold ist,
verschiebt der Kernel ihn auf die den Scheduler-Code
ausführende CPU, sonst verbleibt der Thread auf dem ihm bisher
zugeordneten Prozessor.

SD_WAKE_BALANCE

Dieses Flag ist dann relevant, wenn ein schlafender
Rechenprozess aufgeweckt wird. Der geweckte Rechenprozess wird dann
auf die aktuelle, also den Scheduler-Code ausführende CPU
verschoben, wenn diese idle ist.

SD_BALANCE_FORK

Das Flag wird bedeutsam, wenn ein Task den Systemcall
»fork« aufruft. In diesem Fall balanciert der Scheduler
die Rechenprozesse zwischen den nächsten Domains aus, die das
Flag gesetzt haben.

SD_BALANCE_EXEC

Beeinflusst den Scheduler, wenn ein Task den Systemcall
»exec« aufruft. Der Scheduler sucht die höchste
Ebene im Domain-Baum, die dieses Flag aktiviert hat. Danach sucht
er innerhalb dieser Domain die CPU, die am wenigsten Last aufweist,
und ordnet den Prozess dieser CPU zu.

SD_BALANCE_NEWIDLE

Das Flag ist relevant, wenn eine Run Queue leer ist (der
Prozessor ist idle). Wird eine Run Queue leer, sucht der Scheduler
die oberste Domain, die dieses Flag gesetzt hat. Innerhalb der
Domain wird die CPU gesucht, die die meiste Last fährt. Der
Scheduler verschiebt einen Rechenprozess von dieser CPU auf die
Idle-CPU (Heranholen von Rechenprozessen).

SD_SHARE_CPUPOWER

Dieses Flag ist typischerweise auf der SMT-Ebene gesetzt. Ist
die aktive CPU idle, findet eine Prozessmigration statt. Eine
Besonderheit: Verarbeitet der andere Kern des
Hyperthreading-Prozessors einen Rechenprozess mit höherer
Priorität, verzögert der Scheduler die Bearbeitung des
Rechenprozesses mit niedrigerer Priorität. Damit steht die
gesamte Rechenleistung uneingeschränkt dem Realzeit-Prozess
zur Verfügung.

SD_SHARE_PKG_RESOURCES

Typischerweise auf der SMP-Ebene gesetzt. Es dient allein dazu,
die Variable »cpu_power« zu initialisieren.

SD_SERIALIZE

Kommt normalerweise auf der Numa-Ebene zum Einsatz. Ist es
gesetzt, balanciert der Kernel zu einem Zeitpunkt immer nur eine
Domain per Zeitsteuerung (Soft-IRQ) aus.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 4 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

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

Deutschland

Ähnliche Artikel

  • Kernel 3.0

    Was steckt im Linux-Kernel 3.0? Ein Rundgang durch Taskverwaltung, Memory-Management und weitere wichtige Architekturmerkmale eines modernen Betriebssystemkerns.

  • Kern-Technik

    Nur ausgewiesene Echtzeitbetriebssysteme konnten bislang mit einem "Earliest Deadline First Task"-Scheduler protzen. Seit Kernel 3.14 steht das überlegene CPU-Zuteilungsverfahren auch Linux-Nutzern zur Verfügung. Gegenüber dem prioritätengesteuerten Verfahren hat es einige Vorteile.

  • Kern-Technik

    Der Kernel bietet auf Multicore-Maschinen eine ganze Reihe von Methoden an, um Prozesse auf CPUs zu verteilen. Für alle braucht er die Mithilfe des Admin. So gewappnet erfüllt Linux auch harte Echtzeitanforderungen - wenn die betroffenen Prozesse ausreichend CPU-Zeit bekommen.

  • 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.

comments powered by Disqus

Stellenmarkt

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