Linux 6.6 bringt neuen Scheduler

Inhaltsverzeichnis

Beim letzten Linux-Kernel-Release des Jahres stehen Performance und Optimierung im Vordergrund. Mit dem Austausch des Standard-Schedulers nach 15 Jahren packen die Kernel-Entwickler einen essenziellen Teil des Kernels an. Die Programmierer ringen sich durch, Hardware-Sicherheitsfeatures zu nutzen und steigern die asynchrone I/O beträchtlich. Bei den Dateisystemen gibt es Verbesserungen, aber auch wehmütiger Abschied gehört zum neuen Linux-Release.

Schichtwechsel beim Scheduler

Der Scheduler ist in Linux verantwortlich, Prozessen Rechenzeit zu gewähren. Er lässt sie nach bestimmten Regel auf den Prozessorkernen im Zeitscheibenverfahren alle mal zum Zuge kommen. Seit 2007 mit Kernel 2.6.23 nimmt diese Aufgabe in der Regel der "Completely Fair Scheduler" (CFS) wahr. Er löste damals den einfacheren und in die Jahre gekommenen ursprünglichen Scheduler ab. Parallel arbeiten die Entwickler an alternativen Schedulern, beispielsweise für Real-Time-Aufgaben.

Wie das "Fair" beim CFS schon andeutet, ist der bisherige Scheduler bestrebt, möglichst gerecht und ausgeglichen den Prozessen die vorhandenen CPU-Ressourcen zu überlassen. Er überwacht, wie viel Rechenzeit die jeweiligen Prozesse bereits erhalten haben und ist bestrebt, die Prozesse auszuführen, die bislang weniger CPU-Zeit erhielten.

Auch auf einem Linux-System sind nicht alle Prozesse gleich. Systemkritische Prozesse müssen trotz aller Fairness beim Verteilen der Taktzyklen bevorzugt werden. Das lässt sich Unix-typisch über den nice-Wert (von Englischen "Niceness", Nettigkeit) steuern, der Prozesse höher und niedriger priorisiert.

Neue Herausforderungen

CFS leistet noch immer im Gros der Anwendungsfälle gute Arbeit. Er ist aber nicht perfekt. Mit dem technischen Fortschritt ergeben sich neue Anforderungen. Ein Prozess sollte beispielsweise möglichst selten von einer CPU zur anderen wandern. Bei jedem CPU-Wechsel sind System-Caches als Zwischenschritt erneut zu bemühen. Um das Maximum aus den Caches zu ziehen, also optimal und effizient zu nutzen, sollten Prozesse möglichst lange auf einer CPU verbleiben. Dem entgegen steht das Bestreben, alle Prozessoren und Kerne auszulasten: Also lieber die CPU wechseln, bevor sich alles an einem Prozessor staut und sich andere langweilen.

Weitere Komplexität lauert in hybriden Systemen, bei denen unterschiedliche Prozessoren zum Einsatz kommen – etwa bei Großrechnern CPUs für spezielle Lasten wie Datenbanken und Java. Aber auch bei Hybrid-Core-Architekturen wie Alder Lake der 12. Generation ist das Thema relevant, bei denen Kerne für hohe Leistung (P-Cores, Performance Cores) neben Kernen für niedrigere Workloads (E-Cores, Efficient Cores) mit weniger Leistungsaufnahme koexistieren.

Moderne Scheduler sollten dabei aber auch das Power-Management im Blick haben. Das Ideal der perfekt ausgereizten Hardware bringt nichts, wenn dadurch beispielsweise der Akku des Notebooks in kürzester Zeit leer läuft.

Auch lässt sich dem CFS nicht mit auf den Weg geben, welche Anforderungen an die Reaktionszeit (Latenz, Latency) ein Prozess stellt. Der nice-Wert gibt zwar an, dass ein kritischer Prozess mit höherer Priorität mehr CPU-Zeit erhält. Er definiert jedoch nicht, wie schnell der Prozess diese CPU-Zeit auch erhält. Ein zeitkritischer Prozess mag wenig CPU-Zeit benötigen, aber benötigt diese sehr schnell. Mit dem nice-Wert des CFS ist das nicht abbildbar.

Mehr Fairness

Abhilfe soll nun der neu aufgenommene "Earliest Eligible Virtual Deadline First" (EEVDF) Scheduler schaffen. Im Grunde greift der Linux-Kernel an dieser Stelle eine Idee von 1995 der Forscher Ion Stoica und Hussein Abdel-Wahab der Old Dominion Univerity in Norfolk (Virginia) auf. Das Funktionsprinzip ist ähnlich zum Deadline-Scheduler, welcher ebenfalls im Linux-Kernel zur Verfügung steht. Anders als der bereits länger vorhandene Deadline-Scheduler ist der EEVDF kein Realtime-Scheduler. Er ist also nicht für den Betrieb von Echtzeitsystemen, sondern in der Tat für "normale" Systeme wie Desktops und Server vorgesehen.

Wie der CFS verteilt der neue Scheduler die Rechenzeit möglichst "fair" zwischen Prozessen. Alle erhalten den gleichen Anteil an zur Verfügung stehender CPU-Zeit. Über den nice-Wert lässt sich dieser Anteil zu Gunsten höher priorisierter Prozesse verschieben. Sie erhalten je nach Prioritätsunterschied zu den konkurrierenden Prozessen mehr Anteil an den verfügbaren Rechenkapazitäten. Bis hierhin unterscheiden sich CFS und EEVDF nicht.

Allerdings führt EEVDF im Gegensatz zu CFS darüber Buch, welche Prozesse tatsächlich die zustehende Rechenzeit erhalten haben. Denn ein errechneter (theoretischer) Anteil verschiebt sich Hardware-bedingt. Prozesse können somit retrospektiv praktisch mehr oder weniger ihrer zustehenden Rechenzeit erhalten haben. Das gleicht EEVDF aus, indem Prozesse, die zu wenig Ressourcen erhalten haben, in der nächsten Runde priorisiert werden und früher laufen dürfen. Prozesse mit anteilsmäßig zu viel Rechenzeit qualifizieren sich erst mal gar nicht fürs Ausführen in der nächsten Runde. Durch das Zurückstehen gleicht sich deren Wert für spätere Läufe wieder an.

Schneller zum Zug kommen

Durch das Schema hat jeder qualifizierte Prozess einen Wert erhalten, die "virtual deadline". Er setzt sich aus der vom Prozess ermittelten Laufzeit und seiner zustehenden Zeit zusammen. Je niedriger dieser Wert ist, desto früher muss und darf er laufen. Er landet weiter oben in der Warteschlange (Run-Queue).

Das Latenzproblem adressiert EEVDF nun mit einem sehr einfachen Trick. Der Scheduler führt einen zusätzlichen Wert zur Priorisierung ein; den "latency-nice". Je niedriger dieser Wert ist, desto dringlicher ist der Prozess auszuführen. Unkritische Prozesse erhalten einen hohen latency-nice-Wert.

Um nun die Reihenfolge in der Run-Queue anhand der Latenz zu priorisieren, addiert der Scheduler zur "virtual deadline" den latency-nice hinzu. Damit ändert sich die Reihenfolge in der Warteschlange zu Gunsten der kritischeren Prozesse. Das einfache Prinzip beruht auf zwei Fakten. Von zwei Prozessen mit gleicher "virtual deadline", aber unterschiedlichen latency-nice-Werten, wird der dringlichere mit niedrigerem latency-nice in Summe in der Warteschlange nach oben wandern. Er wird priorisiert. Die andere einfache Tatsache ist, dass kritische Prozesse tendenziell weniger Rechnenzeit erfordern. Sie haben ohnehin schon eine niedrigere "virtual deadline".

Der EEVDF kommt damit ohne Annahmen und Daumenregeln zurecht. Einfache Arithmetik auf Basis geschickt ermittelter praktischer Werte lässt ihn die Warteschlange füllen.