Der lange Weg zur Implementierung von „Lazy Preemption“ im Linux-CPU-Scheduler

• Der Linux-Kernel hat mehrere Preemption-Modi beibehalten, um zwischen Durchsatz und Reaktionszeit abzuwägen; mit einem neuen Patchset von Peter Zijlstra nimmt die Diskussion über Lazy Preemption (PREEMPT_LAZY) wieder Fahrt auf
• Die bestehenden Modi PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL und PREEMPT_RT unterscheiden sich darin, in welchem Umfang Preemption erlaubt ist. Je häufiger Preemption stattfindet, desto besser kann die Reaktionsfähigkeit werden, aber desto größer wird die Belastung für Durchsatz und Lock-Contention
• PREEMPT_LAZY markiert über das Flag TIF_NEED_RESCHED_LAZY, dass „Rescheduling nötig ist, aber nicht sofort“, und verzögert die meiste Preemption bis zum Timer-Tick
• Langfristig sollen die Nicht-Echtzeit-Preemption-Modi auf PREEMPT_LAZY und PREEMPT_FULL reduziert und die meisten cond_resched()-Aufrufe im Kernel entfernt werden
• Das aktuelle Patchset benötigt noch Stabilisierung, eine Überprüfung der Aufrufstellen und Performance-Tests; in ersten Tests lag der Durchsatz von PREEMPT_LAZY etwas unter dem von PREEMPT_VOLUNTARY

---

Bestehende Preemption-Modi im Linux-Kernel

• Der aktuelle Kernel bietet mehrere Preemption-Modi, die steuern, wann eine laufende Aufgabe von einer anderen Aufgabe verdrängt werden kann
  • PREEMPT_NONE: der einfachste Modus, der Preemption nur erlaubt, wenn die laufende Aufgabe ihre Time Slice vollständig verbraucht hat
  • PREEMPT_VOLUNTARY: ein Modus, der im Kernel viele Stellen ergänzt, an denen bei Bedarf Preemption stattfinden kann
  • PREEMPT_FULL: ein Modus, der Preemption an nahezu jeder Stelle erlaubt, außer in Bereichen, in denen der Kernel sie blockiert, etwa beim Halten eines Spinlocks
  • PREEMPT_RT: ein Modus, der Preemption vor fast allem priorisiert und auch den meisten Code, der Spinlocks hält, preemptierbar macht
• Ein höheres Preemption-Niveau kann schneller auf Ereignisse wie Mausbewegungen oder unmittelbar bevorstehende Anomaliesignale in einem Reaktor reagieren
• Häufigere Preemption kann jedoch den Gesamtdurchsatz lang laufender, CPU-intensiver Aufgaben senken und auch die Lock-Contention erhöhen
• Viele Distributionen bauen den Kernel mit dem Pseudomodus PREEMPT_DYNAMIC
  • Beim Booten kann einer der drei zuvor genannten Nicht-Echtzeit-Modi gewählt werden
  • Der Standardwert ist PREEMPT_VOLUNTARY
  • Auf Systemen mit gemountetem debugfs lässt sich der aktuelle Modus unter /sys/kernel/debug/sched/preempt prüfen

Warum cond_resched() nötig war

• PREEMPT_NONE und PREEMPT_VOLUNTARY erlauben während der Ausführung von Kernel-Code keine beliebige Preemption
• Wenn im Kernel lange Arbeiten am Stück ausgeführt werden, kann es selbst auf Systemen, bei denen minimale Latenz nicht oberste Priorität hat, zu übermäßigen Verzögerungen kommen
• Um das zu vermeiden, wurden an vielen Stellen in lang laufenden Schleifen cond_resched()-Aufrufe ergänzt
  • Jeder Aufruf ist ein zusätzlicher freiwilliger Preemption-Punkt
  • Er funktioniert auch im Modus PREEMPT_NONE
  • Im Kernel gibt es Hunderte solcher Aufrufe
• Dieser Ansatz ist eine Heuristik, die nur an den von Entwicklern eingefügten Stellen wirkt
  • Es kann unnötige Aufrufe geben
  • Es können Aufrufe an nötigen Stellen fehlen
  • Scheduling-Entscheidungen werden dadurch über den gesamten Kernel-Code verteilt

Kernverhalten von Lazy Preemption

• Wenn der Kernel entscheidet, ob die aktuelle Aufgabe preemptiert werden kann, betrachtet er mehrere Variablen gemeinsam
• Darunter ist TIF_NEED_RESCHED ein Flag, das anzeigt, dass eine Aufgabe mit höherer Priorität auf CPU-Zugriff wartet
  • Wenn eine Aufgabe mit hoher Priorität aufgeweckt wird, kann dieses Flag für die aktuell laufende Aufgabe gesetzt werden
  • Ohne dieses Flag muss der Kernel die aktuelle Aufgabe nicht preemptieren
• Der Kernel kann an mehreren Stellen TIF_NEED_RESCHED prüfen und die aktuelle Aufgabe preemptieren
  • Timer-Tick des Schedulers
  • Rückkehr in den Userspace nach einem Systemaufruf
  • Abschluss eines Interrupt-Handlers
  • cond_resched()-Aufruf
• Der Lazy-Preemption-Patch fügt das neue Flag TIF_NEED_RESCHED_LAZY hinzu
  • Es bedeutet, dass Rescheduling nötig ist, aber nicht unbedingt sofort ausgeführt werden muss
  • Im Modus PREEMPT_LAZY setzen die meisten Ereignisse statt TIF_NEED_RESCHED dieses neue Flag
• An Stellen, an denen der Kernel in den Userspace zurückkehrt, führt bereits das Setzen eines der beiden Flags zu einem Scheduler-Aufruf
• An freiwilligen Preemption-Punkten und auf Rückkehrpfaden von Interrupts wird nur TIF_NEED_RESCHED geprüft

Der Kompromiss von PREEMPT_LAZY

• Bei PREEMPT_LAZY preemptieren die meisten Ereignisse innerhalb des Kernels die aktuelle Aufgabe nicht sofort
• Stattdessen prüft der Timer-Tick-Handler, ob TIF_NEED_RESCHED_LAZY gesetzt ist
  • Falls es gesetzt ist, setzt er auch TIF_NEED_RESCHED
  • Dadurch kann die laufende Aufgabe preemptiert werden
• Eine Aufgabe läuft normalerweise fast so lange wie ihre Time Slice, sofern sie die CPU nicht freiwillig abgibt
  • Dieses Verhalten soll voraussichtlich zu gutem Durchsatz führen
• Durch diese Änderung kann auch PREEMPT_LAZY, ähnlich wie PREEMPT_FULL, mit nahezu immer aktivierter Kernel-Preemption laufen
  • Wenn der Preemption-Zähler es erlaubt, ist Preemption jederzeit möglich
  • Wenn keine anderen Bedingungen sie verhindern, kann auch lang laufender Kernel-Code preemptiert werden
• Wenn sofortige Preemption wirklich nötig ist, wird sie nicht verzögert
  • Wenn etwa infolge der Interrupt-Verarbeitung eine Echtzeitaufgabe lauffähig wird, wird TIF_NEED_RESCHED gesetzt
  • In diesem Fall kommt es fast sofort zur Preemption, ohne auf den Timer-Tick zu warten
• Wenn nur TIF_NEED_RESCHED_LAZY gesetzt ist, findet keine Preemption statt
  • Daher ist es bei einem PREEMPT_LAZY-Kernel deutlich unwahrscheinlicher als bei einem PREEMPT_FULL-Kernel, dass die laufende Aufgabe preemptiert wird

Was bis zur Entfernung von cond_resched() noch zu tun ist

• Langfristiges Ziel ist es, die Nicht-Echtzeit-Preemption-Modi auf zwei zu reduzieren
  • PREEMPT_LAZY
  • PREEMPT_FULL
• PREEMPT_LAZY soll die Position zwischen PREEMPT_NONE und PREEMPT_VOLUNTARY einnehmen und beide ersetzen
• Wenn Preemption nahezu überall möglich wird, sinkt der Bedarf, an bestimmten Stellen separat freiwillige Preemption-Punkte einzufügen
• Derzeit bleiben cond_resched()-Aufrufe bestehen
  • Sie sind nötig, solange PREEMPT_NONE und PREEMPT_VOLUNTARY existieren
  • Sie helfen auch dabei, während der Stabilisierung von Lazy Preemption Probleme zu vermeiden
• Im aktuellen Patchset prüft cond_resched() nur TIF_NEED_RESCHED
  • Dadurch können viele Situationen, die unter PREEMPT_VOLUNTARY oder PREEMPT_NONE sofort zu Preemption geführt hätten, verzögert werden
• Steve Rostedt fragte insbesondere, ob der Übergang leichter werden könnte, wenn cond_resched() unter PREEMPT_VOLUNTARY seine frühere Bedeutung behält
• Thomas Gleixner hält die Entscheidung, nur TIF_NEED_RESCHED zu prüfen, für richtig
  • Weil sie dazu zwingt, alle cond_resched()-Aufrufe zu überprüfen
  • Aufrufe, bei denen das Lazy-Bit nicht geprüft werden muss, können bei der Einführung von PREEMPT_LAZY entfernt werden
  • Aufrufe, bei denen das Lazy-Bit geprüft werden muss, müssen bestehen bleiben
• Gleixner erwartet, dass weniger als 5 % der cond_resched()-Aufrufe eine Prüfung von TIF_NEED_RESCHED_LAZY benötigen
• Bis der Übergang abgeschlossen ist, müssen Hunderte cond_resched()-Aufrufe überprüft und die meisten davon entfernt werden
• Ein separates Patchset von Ankur Arora behandelt einige der damit verbundenen Details
• Außerdem sind umfangreiche Performance-Tests nötig
  • In frühen Tests von Mike Galbraith lag der Durchsatz von Lazy Preemption etwas unter dem von PREEMPT_VOLUNTARY

Das endgültige Ziel

• Als Ergebnis der Arbeit an Lazy Preemption könnte der Kernel etwas kleiner und einfacher werden
• Ziel ist ein Kernel, der vorhersehbare Latenzen bietet, ohne Scheduler-bezogene Aufrufe über den gesamten Code zu verstreuen
• Der aktuelle Ansatz scheint eine bessere Lösung zu sein, aber bis dieser Zustand erreicht ist, wird noch Zeit vergehen

[GN⁺]

Hacker-News-Meinungen

• Sieht vielversprechend aus. Da es wie EEVDF in die Richtung geht, den aktuellen Zustand zu vereinfachen und zugleich zu verbessern, dürfte es schwer sein, etwas Besseres zu finden.

• Ich frage mich, warum die Preemption-Stufe kein globaler Modus ist, sondern nicht eher eine Eigenschaft eines bestimmten Events. Manche Events müssen mit geringerer Latenz verarbeitet werden als andere.

  • Um die Priorität eines Events zu bewerten, braucht man zunächst CPU-Zeit. Diese Bewertung ist erst möglich, nachdem der aktuell auf der CPU laufende Prozess unterbrochen wurde.
    Daher ist auch die höchste Priorität, die ein Event haben kann, dadurch begrenzt, wie kurz die Zeitscheibe sein kann, die ein Programm bekommt, bevor es einen Kontextwechsel durchläuft. Um auf jede Art von Event zuverlässig mit niedriger Latenz zu reagieren, müssen alle CPU-intensiven Programme immer die Performance-Kosten tragen, egal wie selten dieses Event ist.
  • Hier gibt es zwei Konzepte, die leicht zu verwechseln sind. Das eine ist der Zeitpunkt, zu dem ein Prozess preempted werden kann, das andere, ob er tatsächlich preempted wird.
    Potenzielle Preemption-Punkte sind eine Eigenschaft des Schedulers, und genau das wird hier als globaler Modus diskutiert. Mehr Preemption-Punkte erhöhen natürlich die Wahrscheinlichkeit, dass ein Prozess zu einem ungünstigen Zeitpunkt preempted wird, bieten aber zugleich mehr Gelegenheiten, Prioritäten korrekt zu berücksichtigen. Die Preemption-Stufe aus der Frage, also die Priorität, die der Scheduler vergibt, ist tatsächlich eine Eigenschaft des Prozesses und lässt sich auch konfigurieren. Auch der Standard-Scheduler von Linux gibt Prozessen mit höherer Priorität größere Zeitscheiben und versucht, andere Prozesse seltener für sie zu verdrängen.
  • Das im Artikel beschriebene PREEMPT_VOLUNTARY war bis zu einem gewissen Grad ein Versuch in diese Richtung und kann nun als auf dem Weg zur Abschaffung betrachtet werden.
  • Dieser Patch übernimmt in gewissem Maße genau diese Rolle. Laut https://lwn.net/ml/all/[e-mail]...:
    SCHED_IDLE, SCHED_BATCH und SCHED_NORMAL/OTHER verwenden verzögerte Preemption, während FIFO, RR und DEADLINE das bisherige Full-Verhalten nutzen.
  • Ein solches System dürfte dazu führen, dass Programme untereinander darum konkurrieren, wer sich selbst als wichtig deklariert und höhere Priorität verlangt. Realistisch betrachtet werden vor allem große Unternehmen das für eine „bessere“ User Experience ausnutzen.
    Deshalb ist es wichtig, die Zahl laufender Anwendungen zu minimieren oder kurze Momente, die die meisten Nutzer erleben, manuell zu steuern. CPU-intensive Aufgaben sind manchmal eher ein Hinweis auf schlechten Code als auf wirklich effiziente Ressourcennutzung. Bei Spielen muss Performance Vorrang haben, aber es braucht eine heikle Balance, damit das System fürs Multitasking nicht zum Stillstand gebracht wird. Jedenfalls ist das hier hauptsächlich für Idle-Aufgaben gedacht, daher scheint es keinen großen Bedarf zu geben, mehr zu automatisieren, als dem Nutzer einen einfachen Befehl zu geben, mit dem er in Skripten mehrere Verhaltensweisen umschalten kann.

• Es heißt: „Im aktuellen Kernel gibt es vier Modi, die steuern, wann eine Aufgabe zugunsten einer anderen preempted werden kann.“ Ich frage mich, ob sich das auf Kernel-Tasks bezieht oder auch User-Tasks einschließt.

  • Es geht um Kernel-Code. Userspace-Code ist immer preemptible.

• Im verlinkten Thread mit dem Patch konnte ich keine Zahlen finden. Ich hätte erwartet, dass es bereits zumindest erste Benchmarks gibt, die das praktische Potenzial dieser Änderung zeigen.

  • Das steht im vorletzten Absatz des Artikels.
    Dort heißt es, dass umfangreiche Performance-Tests nötig sind, dass Mike Galbraith mit ersten Arbeiten begonnen hat und dass seine Ergebnisse zeigen, dass der Durchsatz bei verzögerter Preemption etwas niedriger ist als bei PREEMPT_VOLUNTARY.
  • Ich frage mich, wie man so etwas benchmarken sollte. Lässt man mehrere Prozesse gleichzeitig laufen und sortiert nach der Gesamtlaufzeit, oder sollte man die Wartezeit einzelner Prozesse messen?

• Ich frage mich, wie stark der Scheduler mit dem restlichen Kernel-Code gekoppelt ist.
  Wenn man den Scheduler zum Beispiel für wissenschaftliche Rechenanwendungen, denen Preemption völlig egal ist, stark vereinfachen wollte: Wäre das auf saubere, modulare Weise möglich? Gäbe es überhaupt einen realen Vorteil?

  • Wenn man eine Menge von Prozessen mit möglichst wenig Preemption ausführen möchte, ist in einer HPC-Umgebung zum Beispiel der wirkungsvollste Weg, einige Cores als isolierte CPUs zu konfigurieren, neu zu booten und die Jobs dann mit taskset direkt darauf zu legen.
    Allerdings muss man die Jobs dann wirklich manuell CPUs zuweisen, und es passiert leicht, dass alle Jobs auf den falschen CPUs landen. Der Standardansatz besteht darin, Interrupt-Masks zu setzen, damit keine Interrupts auf die „Arbeits“-CPUs gehen, und cpusets zu verwenden, sodass nur bestimmte cgroups in einem gegebenen cpuset laufen.
  • Auf einem sauberen System mit kaum Daemons kommt man etwa zu 95 % dorthin, wenn man die Anwendung auf einen Betriebssystem-Thread pro CPU-Thread auslegt und per CPU-Affinität fixiert, damit sie nicht wandert.
    Da die Runqueue dann sehr kurz wird, ist der Einfluss dessen, was der Scheduler tut, ziemlich gering. Wenn die Anwendung nicht viel I/O macht, gibt es auch nicht viele Interrupts. Wenn man einen tickless Kernel verwenden kann — ich weiß nicht, ob das heute noch eine separate Option oder bereits Standard ist — kann es über lange Zeiträume hinweg fast keine Interrupts geben.
  • Als ich zuletzt nachgesehen habe, war er überraschend gut getrennt.
    Der Grund für eine starke Vereinfachung wäre allerdings eher, Bugs zu vermeiden; im Vergleich zu einem gut konfigurierten Standard-Scheduler gewinnt man nicht viel Performance. Es gibt viele Einstellungen, aber auch dort gab es nicht viele Bugs. Eine naive Vereinfachung führt meist eher zu Performance-Verlusten als zu Gewinnen. Wenn man ein nicht-interaktives System betreibt, ist die einfachste Änderung, das Zeitkontingent der Prozesse zu erhöhen.
  • Ich würde einfach RT Linux verwenden. Es hat einen eigenen primären Scheduler, während der Kernel-Scheduler als Idle-Task läuft, und Echtzeit-Tasks haben Priorität vor allem anderen.