Der Scheduler

Die Aufgabe des Schedulers

Ein typischer Desktop hat einige hundert Tasks, aber nur eine Handvoll CPU-Kerne. Die meisten Tasks schlafen zwar und warten auf Ereignisse (Kapitel 5), doch sobald mehrere gleichzeitig rechnen wollen, muss jemand entscheiden: Wer darf jetzt auf welche CPU, und wie lange? Das ist die Aufgabe des Schedulers.

Dabei stehen mehrere Ziele im Widerspruch zueinander:

• Durchsatz: möglichst viel Arbeit pro Zeit erledigen, also selten wechseln, weil jeder Kontextwechsel kostet.
• Latenz: auf Ereignisse schnell reagieren, etwa auf einen Tastendruck oder ein ankommendes Paket. Das erfordert häufiges Wechseln.
• Fairness: Gleichberechtigte Tasks bekommen gleich viel Rechenzeit, und niemand verhungert.
• Vorhersagbarkeit: Echtzeit-Anwendungen müssen garantierte Fristen einhalten.
• Energieeffizienz und Skalierbarkeit: CPUs sollen schlafen dürfen, wenn wenig zu tun ist, und auch auf Systemen mit hunderten Kernen soll der Scheduler effizient bleiben.

Der Linux-Scheduler löst das nicht mit einem einzigen Algorithmus, sondern mit mehreren Scheduling-Klassen, die jeweils einen Teil dieser Ziele verfolgen.

Scheduling-Klassen und Policies

Jeder Task gehört über seine Policy zu genau einer Klasse. Die Klassen sind streng nach Priorität geordnet:

Die Policy eines Tasks setzt man mit sched_setscheduler() bzw. sched_setattr() oder auf der Kommandozeile mit chrt:

Intern ist jede Klasse eine struct sched_class, im Grunde eine Tabelle von Funktionszeigern: enqueue_task, dequeue_task, pick_next_task, task_tick und weitere. Der Kern des Schedulers in kernel/sched/core.c↗ ruft nur diese Funktionen auf und weiß nichts über die Algorithmen der einzelnen Klassen.

Prioritäten und nice-Werte

Ein Begriff verwirrt anfangs fast alle: Priorität. Linux kennt mehrere Skalen, die intern auf eine gemeinsame Skala von 0 bis 139 abgebildet werden:

Für normale Tasks ist der nice-Wertnice-WertZahl von −20 bis 19, die die Priorität eines normalen Tasks beeinflusst. Höhere Werte bedeuten „netter zu anderen“, also weniger CPU-Anteil. Jede Stufe ändert den Anteil um etwa 10 %. maßgeblich (−20 bis 19, Standard 0). Er bestimmt nicht die Reihenfolge, sondern das Gewicht eines Tasks und damit seinen Anteil an der CPU-Zeit. Die Gewichte stehen in der Tabelle sched_prio_to_weight in kernel/sched/core.c↗. nice 0 entspricht dem Gewicht 1024, und jede Stufe ändert das Gewicht um den Faktor 1,25:

Die Faustregel: Eine nice-Stufe entspricht etwa 10 % CPU-Anteil. Konkurrieren zwei Tasks mit nice 0 und nice 1, bekommt der erste 1024 / (1024 + 820) ≈ 55 %, der zweite 45 %. Der Abstand ist relativ: nice 0 gegen nice 5 verhält sich genauso wie nice 10 gegen nice 15.

Normale Benutzer dürfen den nice-Wert nur erhöhen (sich selbst „netter“ machen). Zum Senken unter 0 braucht man Root-Rechte bzw. die Capability CAP_SYS_NICE.

Faires Scheduling: die virtuelle Laufzeit

Wie verteilt man CPU-Zeit fair nach Gewichten? Die Idee stammt vom Completely Fair Scheduler (CFS), der von 2007 (Linux 2.6.23) bis 2023 der Standard war. Jeder Task führt eine virtuelle Laufzeit vruntime. Läuft er real Δt lang, wächst sie um

Δvruntime = Δt × 1024 / Gewicht

Ein Task mit nice 0 (Gewicht 1024) altert also in Echtzeit. Ein Task mit doppeltem Gewicht altert halb so schnell, einer mit halbem Gewicht doppelt so schnell. Der Scheduler versucht, die virtuellen Laufzeiten aller Tasks gleich zu halten: Er wählt immer den Task, der „am weitesten zurückliegt“. Wer schwerer ist, darf dadurch real länger rechnen, bis er aufgeholt hat.

Probiere es aus. Mit zwei Tasks nice 0 und einem nice 5 verteilt sich die Zeit auf etwa 43 %, 43 % und 14 %:

EEVDF: der aktuelle Algorithmus

Seit Linux 6.6 verwendet die faire Klasse den Algorithmus EEVDFEEVDFEarliest Eligible Virtual Deadline First: seit Linux 6.6 der Algorithmus für normale Tasks. Unter den Tasks, die noch CPU-Zeit „gut haben“, läuft der mit der frühesten virtuellen Deadline. (Earliest Eligible Virtual Deadline First). Er beruht auf einer wissenschaftlichen Arbeit von 1995 und behält die virtuelle Laufzeit bei, trifft die Auswahl aber nach einer genaueren Regel:

1. Anspruch (Lag): Für jeden Task wird berechnet, wie viel Rechenzeit er im Vergleich zu einer ideal fairen Verteilung zu wenig oder zu viel bekommen hat. Ein Task ist berechtigt (eligible), wenn er nicht im Plus ist, seine vruntime also nicht über dem gewichteten Durchschnitt liegt.
2. Virtuelle Deadline: Jeder Task fordert eine Zeitscheibe an (Standard: base_slice, 0,7 ms, auf Rechnern mit vielen CPUs bis zu viermal so viel). Daraus ergibt sich eine virtuelle Deadline: deadline = vruntime + slice × 1024 / Gewicht.
3. Auswahl: Unter allen berechtigten Tasks läuft der mit der frühesten virtuellen Deadline.

Der Vorteil gegenüber CFS: Tasks, die kurze Zeitscheiben anfordern, bekommen frühere Deadlines und kommen schneller dran. Langfristig erhalten sie trotzdem nicht mehr als ihren fairen Anteil. Latenz und Anteil lassen sich so getrennt steuern. CFS brauchte dafür zahlreiche Heuristiken, die EEVDF überflüssig macht.

Wann der Scheduler entscheidet

Der Scheduler ist kein eigener Prozess. Er besteht aus der Funktion __schedule↗, die zu bestimmten Zeitpunkten aufgerufen wird:

1. Freiwillig, wenn ein Task blockiert, etwa auf I/O, eine Sperre oder sleep(). Er ruft dann selbst schedule() auf.
2. Beim Beenden eines Tasks.
3. Bei Verdrängung (PreemptionVerdrängung (Preemption)Der Scheduler entzieht einem laufenden Task die CPU, ohne dass dieser sie freiwillig abgibt, etwa weil ein wichtigerer Task lauffähig geworden ist.): Der Kernel stellt fest, dass ein anderer Task jetzt Vorrang haben sollte, und setzt beim laufenden Task das Flag TIF_NEED_RESCHED. Das geschieht zum Beispiel
   • im Timer-Interrupt (sched_tick()), wenn die Zeitscheibe abgelaufen ist,
   • beim Aufwecken eines Tasks, der Vorrang hat, etwa eines Echtzeit-Tasks.

Das Flag allein wechselt noch nichts. Der eigentliche Wechsel passiert an der nächsten sicheren Stelle: spätestens bei der Rückkehr in den User Space, nach einem Interrupt oder an einer Stelle im Kernel, an der Verdrängung erlaubt ist.

Verdrängung im Kernel: Preemption-Modelle

Ob auch Kernel-Code mitten in der Ausführung verdrängt werden darf, ist eine Abwägung zwischen Durchsatz und Latenz. Linux bietet dafür mehrere Modelle, die sich bei vielen Distributionen beim Booten mit preempt= wählen lassen:

Abschnitte, die nicht unterbrochen werden dürfen, etwa solange ein Spinlock gehalten wird, schalten die Verdrängung vorübergehend ab (preempt_disable()). Mehr dazu in Kapitel 9.

Mehrere CPUs

Auf Mehrkernsystemen hat jede CPU ihre eigene Run-QueueRun-QueueWarteschlange der lauffähigen Tasks einer CPU (struct rq). Jede CPU hat ihre eigene. (struct rq). Eine einzige gemeinsame Warteschlange wäre ein Engpass, weil alle CPUs ständig um dieselbe Sperre konkurrieren würden:

Damit keine CPU überlastet ist, während eine andere sich langweilt, gleicht der Kernel die Last regelmäßig aus:

• Periodischer Lastausgleich: In festen Abständen prüft jede CPU, ob andere CPUs deutlich mehr zu tun haben, und zieht gegebenenfalls Tasks zu sich.
• Leerlauf-Ausgleich: Wird eine CPU untätig, sucht sie sofort nach Arbeit bei den Nachbarn.
• Platzierung beim Aufwachen: Ein aufwachender Task wird möglichst auf eine CPU gelegt, die gerade frei ist und deren Caches seine Daten vielleicht noch enthalten.

Dabei berücksichtigt der Scheduler die Topologie über Scheduling Domains. Ein Task zwischen zwei Hyperthreads desselben Kerns zu verschieben ist billig, weil sie sich die Caches teilen. Ein Wechsel auf einen anderen Prozessorsockel (NUMA-Knoten) ist teuer, weil der Arbeitsspeicher dann „weiter weg“ liegt. Auf Prozessoren mit unterschiedlich starken Kernen (z. B. ARM big.LITTLE oder Intels P- und E-Kerne) bezieht der Scheduler außerdem Leistung und Energieverbrauch der Kerne ein.

Mit der CPU-Affinität lässt sich festlegen, auf welchen CPUs ein Task laufen darf (sched_setaffinity(), Kommandozeile: taskset).

Echtzeit-Scheduling

Echtzeit bedeutet nicht „schnell“, sondern vorhersagbar: Eine Reaktion muss innerhalb einer garantierten Frist erfolgen. Dafür gibt es zwei Klassen:

SCHED_FIFO und SCHED_RR arbeiten mit festen Prioritäten von 1 bis 99. Ein lauffähiger Echtzeit-Task verdrängt sofort jeden normalen Task und jeden Echtzeit-Task niedrigerer Priorität. Unter Tasks gleicher Priorität läuft bei FIFO der erste so lange, bis er blockiert. Bei RR wechseln sie sich nach ihrer Zeitscheibe ab.

SCHED_DEADLINE beschreibt einen Task durch drei Werte: Er braucht Laufzeit R innerhalb jeder Periode P und muss jeweils bis zur Frist D fertig sein. Der Kernel nimmt einen solchen Task nur an, wenn die Summe der angeforderten Anteile R/P die CPU-Kapazität nicht übersteigt (Admission Control). Ausgewählt wird nach Earliest Deadline First. Damit lassen sich Garantien geben, die mit festen Prioritäten nicht möglich sind.

sched_ext: Scheduler als BPF-Programm

Seit Linux 6.12 kann man mit sched_ext eine komplette Scheduling-Strategie als BPF-Programm zur Laufzeit laden (Kapitel 16). Tasks mit der Policy SCHED_EXT werden dann von diesem Programm verteilt. Das ermöglicht schnelle Experimente mit neuen Algorithmen und Strategien, die auf eine bestimmte Arbeitslast zugeschnitten sind, etwa für Spiele oder große Rechenzentren. Stürzt der BPF-Scheduler ab oder verhält er sich falsch, schaltet der Kernel automatisch auf den normalen Scheduler zurück.

Selbst ausprobieren

# Policy und Priorität der eigenen Shell
chrt -p $$

# Policy (CLS), nice (NI) und Echtzeit-Priorität aller Prozesse
ps -eo pid,cls,ni,rtprio,comm | head -n 20

# Erlaubte Prioritätsbereiche je Policy
chrt -m

# Auf welchen CPUs darf die Shell laufen?
taskset -cp $$

# Scheduler-Statistik eines Prozesses (Laufzeit, Wartezeit, Kontextwechsel …)
head -n 25 /proc/$$/sched

# Basis-Zeitscheibe und Echtzeit-Reservierung
sudo cat /sys/kernel/debug/sched/base_slice_ns
cat /proc/sys/kernel/sched_rt_runtime_us /proc/sys/kernel/sched_rt_period_us

# Zwei Endlosschleifen auf dieselbe CPU 0 zwingen, eine davon mit nice 5
taskset -c 0 yes > /dev/null &
taskset -c 0 nice -n 5 yes > /dev/null &

# CPU-Anteile beobachten (Spalte %CPU), mit q beenden
top -p "$(pgrep -d, -x yes)"

# Aufräumen
pkill -x yes