Lastverteilung

Der Scheduler sorgt durch Prozessmigration, also das Verschieben eines Jobs auf einen anderen Kern oder in eine andere Gruppe, innerhalb seiner Domain für eine ausbalancierte Lastverteilung. Multicore-Scheduling ist immer dann aktiv, wenn sich ein Job beendet, ein neuer Job gestartet wird, sich schlafen legt oder wenn ein starkes Ungleichgewicht bei der Auslastung der einzelnen Rechnerkerne festgestellt wird. Ob in letzterem Fall eine Prozessmigration Vorteile bringt, rechnet Linux in jedem Einzelfall aus, zudem kann der Sysadmin dies per Kommandozeilen-Option beeinflussen.

Fürs Singlecore-Scheduling hat Linux mit Kernel 2.6.23 ein erweiterbares Framework zur einfachen Implementierung von Scheduling-Algorithmen verpasst bekommen. Dieses Framework führt so genannte Scheduling-Klassen ein, die per implementiertem Algorithmus aus den zugeordneten Jobs den nächsten zu bearbeitenden auswählen. Liefert eine Klasse auf Nachfrage keinen Job, fragt der Scheduler bei der nächsten nach.

Im Standardkernel sind drei Klassen implementiert. Die Klasse »rt_sched_class« ist für Echtzeitprozesse zuständig. Der in dieser Klasse implementierte Algorithmus realisiert ein prioritätengesteuertes Scheduling. Besitzen mehrere Jobs die gleiche Priorität, wird entweder per FCFS (First Come First Served) oder per Zeitscheibenverfahren (Round Robin) ausgewählt. Insgesamt bietet Linux in dieser Klasse 99 Prioritätsebenen.

Normal gestartete Jobs sind der Klasse »fair_sched_class« zugeordnet, die den Completly Fair Scheduler (CFS) realisiert. Dieser Algorithmus sortiert lauffähige Rechenprozesse nicht mehr – wie in den ersten 2.6-Versionen – in Listen, sondern in Red-Black-Trees. Das ermöglicht ihm, mit wenig Rechenaufwand eine faire Verteilung der Rechenzeit vorzunehmen, die nicht mehr auf Heuristiken, sondern allein auf Mathematik beruht.

Im Userland sind dabei weiterhin Nice-Level (Kommando »nice« ) sichtbar, die schon die allerersten Unix-Systeme kannten und eine Priorisierung von Jobs im Bereich von -20 bis +19 ermöglichen. Das Kommando »ps -ce« stellt diese als Linux-Prioritäten von 0 bis 39 dar.

Die Echtzeitprioritäten (1 bis 99) werden bei dieser Ausgabe übrigens als Linux-Prioritäten 41 bis 139 ausgegeben, sodass zur Umrechnung von Linux-Priorität in eine Posix-Realzeitpriorität immer 40 zu subtrahieren ist (Abbildung 2). Die dritte Klasse heißt »idle_sched_class« und tritt nur in Aktion, wenn es keinen anderen lauffähigen Job gibt.

Abbildung 2: Aus logischer Sicht unterstützt Linux 140 Prioritätsebenen, die in einen Bereich für normale Jobs und in einen für Echtzeit-Tasks unterteilt sind. Die Posix-Spezifikation zählt dabei anders.

Bitte nicht stören!

Die Unterbrechbarkeit (Preemption) durch den Scheduler bezieht sich im Linux-Kernel auch auf Funktionen, die im Kernel- oder im Prozesskontext abgearbeitet werden (siehe Kasten "Unterbrechungsmodell"), also Systemcalls oder Kernelthreads. Klassischerweise bringt Linux einmal im Kernel begonnene Funktionen erst bis zum nächsten planmäßig unterbrechbaren Punkt aus, bevor es andere Funktionen auf Kernel- oder Prozessebene in Angriff nimmt. Das gilt auch für den Fall, dass – etwa per Hardware-Interrupt signalisiert – eine sehr wichtige Funktion abzuarbeiten ist.

In einem modernen Linux-Kernel ist das anders: Höher priorisierte Kernelfunktionen unterbrechen niedriger priorisierte. Dadurch reduzieren sich die Latenzzeiten deutlich. Einziger Nachteil: Auf Singlecore-Maschinen gibt es mehr kritische Abschnitte, die das Betriebssystem schützen muss.

Eine sinnvolle Ergänzung zur Kernel-Preemption sind Threaded Interrupts (Abbildung 3). Startet ein Kernel 3.0 mit der Option »threadirqs« , arbeitet das Betriebssystem die zentralen Teile der Interrupt-Serviceroutinen (ISRs) im Kernelkontext ab, also als Kernelthreads. Damit beeinflusst der Admin oder der Systemarchitekt die Priorisierung nicht nur der Interrupts untereinander, sondern sogar in Beziehung zu sonstigen Aufgaben.

Abbildung 3: Interrupt-Serviceroutinen und Soft-IRQs mutieren zu Threads, was sie unterbrechbar macht: Ein Echtzeitprozess, der auf der Userebene läuft, kann sie verdrängen.