Ich habe die letzten Monate damit verbracht, alle paar Wochen eine weitere Folge einer vierteiligen Serie darüber zu lesen, wie der Linux-Kernel entscheidet, welcher Task als Nächstes die CPU bekommt. Die ersten drei Teile erzählten eine befriedigende Geschichte: Der Scheduler erfindet eine fiktive Uhr, um etwas Unmessbares – Fairness – berechenbar zu machen, und er erfindet einen echten Vertrag, abgesichert durch ein Ablehnungsrecht, um etwas Unverbrüchliches – eine Garantie – durchsetzbar zu machen. Der vierte und letzte Teil nimmt einen Teil dieser Befriedigung wieder zurück. Er zeigt, was mit einer sauberen Garantie passiert, sobald man von ihr verlangt, gleichzeitig zwei Arten von Ressourcen abzudecken. Die Antwort lässt sich weiter verallgemeinern, als ich erwartet hatte.

Zwei Probleme, die sich ähneln – und es nicht sind

Jede moderne CPU ist eigentlich mehrere CPUs zugleich – Kerne, Sockel, Speicherknoten, verbunden durch Leitungen unterschiedlicher Länge und unterschiedlicher Kosten. Wenn Linux entscheidet, wann ein Task läuft, kann es sich auf echte Theorie stützen: EEVDF (Earliest Eligible Virtual Deadline First) löste ab Version 6.6 im Oktober 2023 den älteren Completely Fair Scheduler als Standardrichtlinie für gewöhnliche Tasks ab1 und reduziert Fairness auf einen einzigen Skalar – lag –, dessen Beschränktheit sich beweisen lässt. Darüber sitzt SCHED_DEADLINE, das aus Fairness einen echten Vertrag macht: Ein Task erklärt, wie viel Laufzeit er pro Periode benötigt, eine Zulassungsprüfung (admission control) addiert diese Erklärung zu denen aller anderen und lehnt die Anfrage ab, wenn die Summe 100 % der CPU überschreiten würde. Nur zugelassene Tasks erhalten eine mathematisch beschränkte Garantie darüber, wie spät sie höchstens laufen können (ihre „tardiness”)2.

Aber das Wann ist nur die halbe Aufgabe des Schedulers. Er muss auch entscheiden, wo – auf welchem Kern der Maschine ein Task tatsächlich läuft. Und diese Entscheidung, so stellt sich heraus, ist ein anderes Problem in denselben Kleidern.

Die Achse ohne Theorie

Die Zeitachse bekam etwa 300 Zeilen prinzipienbasierte Mathematik. Die Raumachse bekam etwas anderes: einen Stapel Heuristiken. Linux stellt die physische Maschine als einen Baum von „Scheduling-Domänen” dar – Hyperthread-Geschwister, dann Kerne auf demselben Die, dann Sockel, dann NUMA-Knoten – und durchläuft diesen Baum periodisch auf der Suche nach der ausgelastetsten Gruppe und der ausgelastetsten Warteschlange darin, um dann Arbeit in Richtung der freien Seite zu verschieben. Einen freien Kern schnell genug zu finden, damit es sich lohnt, braucht eigene Abkürzungen (Auslastungs-Vorprüfungen, die entscheiden, ob ein vollständiger Scan überhaupt sinnvoll ist), und diese Abkürzungen werden laufend nachgebessert. Es gibt kein vruntime für physische Distanz. Niemandem ist es bisher gelungen, eine einzige fiktive Zahl zu erfinden, die erfasst, „wie teuer es ist, diesen Task von diesem Kern zu jenem zu verschieben” – so wie lag erfasst, „wie viel CPU dieser Task im Verhältnis zu seinem Anteil erhalten hat”.

Das ist keine Nachlässigkeit. Eine Messstudie aus dem Jahr 2016, „The Linux Scheduler: A Decade of Wasted Cores”, zeigte, dass diese Heuristik-Schicht reale, reproduzierbare Fehler erzeugt: Kerne, die sekundenlang untätig herumstehen, während lauffähige Threads anderswo warten – in einem Fall, weil ein Fehler beim Aufbau der Scheduling-Gruppen dazu führte, dass dieselbe Menge von Kernen in zwei überlappenden Gruppen registriert wurde, sodass ein dort beim Start platzierter Task nie wieder herausbalanciert werden konnte. Die Studie berichtete von einer um ein Vielfaches verlangsamten Ausführung bei synchronisationslastigen wissenschaftlichen Workloads, einem zweistelligen prozentualen Anstieg der Latenz beim Kernel-Build und einem vergleichbaren Durchsatzverlust bei einer kommerziellen Datenbank – alles bedingt durch die Platzierung, nicht durch einen Fehler in der Fairness-Mathematik selbst3. In der Praxis greifen Betreiber nicht zu einem klügeren Scheduler, sondern zu taskset: Tasks werden von Hand an Kerne gepinnt, und man verzichtet damit ganz auf die automatische Entscheidung.

Wo der Vertrag bricht

Hier ändert sich etwas an dem, was ich selbst noch vor ein paar Wochen geschrieben hatte. Die Zulassungsgarantie von SCHED_DEADLINE – die Eigenschaft, die mich in einem früheren Beitrag dazu brachte, sie das stärkste Versprechen im ganzen Scheduler zu nennen, weil ein Task, der sich selbst an eine erklärte Bandbreite bindet, mehr Vertrauen genießt als einer, der nur eine hohe Priorität behauptet – gilt sich, wie sich zeigt, nur entlang der Zeitachse. Sobald man einen Task zusätzlich auf eine bestimmte Teilmenge von Kernen festlegt (CPU-Affinität), kann die Garantie brechen. Eine Studie aus dem Jahr 2021 stellte fest, dass SCHED_DEADLINE unter allgemeinen Affinitätsmasken seine tardiness-Schranke nicht zuverlässig einhält und dass eine allgemeine Behebung einen unpraktikablen internen Umbau erfordern würde; nur ein eingeschränkter Fall (semi-partitionierte Affinität) lässt sich mit vertretbarem Aufwand reparieren4. Der tiefere Grund ist kein Programmierfehler – Tasks gegen eine gemeinsame Ressource (die gesamte CPU-Zeit) zuzulassen ist eine einfache arithmetische Prüfung, aber sie gleichzeitig gegen CPU-Zeit und eine bestimmte Teilmenge erlaubter Kerne zuzulassen, wird zu einem Bin-Packing-Problem, und Bin-Packing ist im Allgemeinen NP-schwer. Bezeichnend ist, dass diese Lücke noch Jahre nach der ersten Implementierung der tardiness-Garantie vom Maintainer des Schedulers selbst als offenes Problem genannt wurde5.

Das Versprechen, das ich isoliert betrachtet für so vertrauenswürdig hielt – „ich werde genau so viel, genau so oft verbrauchen” – hört also in dem Moment, in dem eine zweite Achse (wo) mit der ersten (wann) mitfährt, still auf, ein Versprechen zu sein. An der Erklärung selbst hat sich nichts geändert. Geändert hat sich, wie viele unabhängige Dinge sie gleichzeitig garantieren soll.

Was sich verallgemeinern lässt

Ich glaube, hier steckt eine Behauptung, die es wert ist, klar ausgesprochen zu werden, denn sie scheint nicht kernelspezifisch zu sein: Die Stärke einer Garantie ist umgekehrt proportional zur Anzahl der unabhängig variierenden Ressourcen, die sie abdeckt. Ein Anbieter, der eine Antwortzeit verspricht, macht eine überprüfbare Aussage. Ein Anbieter, der eine Antwortzeit und ein festes Team und ein festes Budget und feste Arbeitszeiten verspricht, macht ab einem gewissen Punkt eine Aussage, deren innere Konsistenz zum Zeitpunkt der Zusage niemand mehr überprüfen kann – nicht weil er lügt, sondern weil das Prüfproblem selbst kombinatorisch schwieriger geworden ist. Das ist kein Argument gegen ehrgeizige Verträge. Es ist ein Argument dafür, zu bemerken, dass „wir versprechen alles” eine andere Art von Aussage ist als „wir versprechen dieses eine”, selbst wenn beides in bester Absicht gesagt wird.

Daneben steht eine zweite, engere Beobachtung. Die fiktive Uhr, die die Zeitachse handhabbar macht – vruntime, lag – funktioniert nur, weil CPU-Zeit von vornherein eine künstliche, menschengemachte Einheit ist; es gab nie einen „natürlichen” Weg, sie zu verbrauchen, also kostet es konzeptionell nichts, ein Buchhaltungssystem dafür zu erfinden. Physische Distanz zwischen Kernen ist anders. Cache-Sharing, Speicherlatenz und Leistungsdomänen sind Tatsachen über das Silizium, festgelegt, bevor überhaupt ein Scheduler auftaucht, um darüber zu verteilen. Eine Ressource, die bereits eine Form hat, lässt sich nicht durch die Erfindung einer Uhr überdecken – man kann nur Heuristiken bauen, die die Form respektieren, die man sich nicht ausgesucht hat. Ich weiß noch nicht, wie weit sich diese Unterscheidung – zuteilbar, weil willkürlich, versus zuteilbar trotz physischer Natur – außerhalb von Kerneln trägt, aber es fühlt sich nach der Art von Sache an, die überall dort auftauchen sollte, wo Menschen versuchen, etwas Knappes und halb Natürliches zu verteilen, wie Land, Funkspektrum oder Aufmerksamkeit.

Die Autoren der Serie beobachten derzeit sched_ext, einen Mechanismus, der Ende 2024 in den Kernel aufgenommen wurde und es erlaubt, benutzerdefinierte Scheduler als ladbare BPF-Programme laufen zu lassen, statt sie fest in den Kernel einzukompilieren6. Ich bin mir noch nicht sicher, ob das eine echte Antwort auf das Problem der Raumachse ist oder nur eine Möglichkeit, dieselben ungelösten Heuristiken an einen Ort zu verschieben, an dem sich leichter iterieren lässt. Das ist die offene Frage, mit der ich gerade sitze: Ist eine flexiblere Experimentierfläche echter Fortschritt bei einem schwierigen Problem, oder nur ein bequemerer Ort, es ungelöst zu lassen?

  1. Michael Larabel, „EEVDF Scheduler Merged For Linux 6.6”, Phoronix. Abgerufen am 2026-08-15. ↩

  2. „Deadline Task Scheduling”, The Linux Kernel documentation. Abgerufen am 2026-08-15. ↩

  3. Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova, „The Linux Scheduler: a Decade of Wasted Cores”, EuroSys 2016. Abgerufen am 2026-08-15. ↩

  4. „On the Defectiveness of SCHED_DEADLINE w.r.t. Tardiness and Affinities, and a Partial Fix”, RTNS 2021. Abgerufen am 2026-08-15. ↩

  5. „GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved”, ECRTS 2019 (mit Verweis auf die Aufnahme des Problems in Peter Zijlstras Liste offener Probleme in seiner ECRTS-2017-Keynote). Abgerufen am 2026-08-15. ↩

  6. „Sched_EXT With Linux 6.19 Improves Recovering For Misbehaving eBPF Schedulers”, Phoronix (Hintergrund zur Aufnahme von sched_ext als erweiterbare Scheduler-Klasse in den Kernel). Abgerufen am 2026-08-15. ↩