Software::Kernel
Forscher analysieren Durchsatzprobleme im Linux-Scheduler
Eine Gruppe von Forschern hat Fälle identifiziert, in denen der Scheduler im Linux-Kernel falsche Entscheidungen trifft und die CPUs nicht so gut auslastet, wie er könnte. Die Fehler scheinen jedoch nur auf Rechnern mit mehreren CPUs und jeweils mehreren Kernen pro CPU aufzutreten. Das Team hat für alle Probleme bereits simple und effektive Lösungen sowie neue Analysewerkzeuge entwickelt.
Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova
Scheduler-Problem: Geringe Auslastung von CPU 0 und 4
Die Forschergruppe wird ihre Ergebnisse auf der
Eurosys-Konferenz in London präsentieren, die vom 19. bis 21. April stattfindet. Vorab ist bereits die Ausarbeitung des Vortrags
als wissenschaftliche Arbeit (PDF) verfügbar. Kurz nach dem
Vortrag dürften auch die Kernel-Patches und Werkzeuge des Teams
auf Github publiziert werden.
Das Papier trägt den Titel »The Linux Scheduler: a Decade of Wasted Cores« und geht tief in die Details des Schedulers. Um es zu verstehen, ist es hilfreich, einen Überblick über die Funktionsweise und die Geschichte des Schedulers zu besitzen, den die Forscher auch gleich mitliefern. Demnach ist es das generelle Ziel des Schedulers, wie bei allen Timesharing-Betriebssystemen, jedem Thread die seiner Priorität entsprechende CPU-Zeit zukommen zu lassen und Verzögerungen zu vermeiden. Dieses Ziel kann durch Energiespar-Anforderungen und andere Nebenbedingungen modifiziert werden, doch im Bereich von Hochleistungsrechnern und großen Servern zählt nur der reine Durchsatz.
Wenn also mehr Threads bereit sind, als CPU-Kerne zur Verfügung stehen, müsste die Auslastung aller Kerne permanent bei 100% liegen und keiner dürfte ohne Arbeit sein. Wie sich nun zeigte, trifft das in der Praxis nicht immer zu. Es wurde beobachtet, dass beim Compilieren großer Projekte, wie dem Kernel selbst, oder beim Datenbank-Benchmark TPC-H einzelne Kerne für eine gewisse Zeit, teils mehrere Sekunden, keinen Thread zugeteilt bekamen. Mit den bisher vorhandenen Werkzeugen ließ sich das Problem nicht greifen, so dass im Zuge der Untersuchungen neue Werkzeuge zum Tracen und Visualisieren entwickelt wurden.
Im Jahr 2000 wurde das Scheduling als erledigtes Problem angesehen. Der Linux-Scheduler bestand aus einigen hundert Zeilen und tat, was er sollte. Doch dann explodierte die Zahl der CPUs und Kerne in Systemen und mit ihnen auch die Zahl der Threads, und neue Anforderungen wie Energieverwaltung und Control Groups kamen hinzu. In der Folge wurde der Scheduler »unglaublich komplex, ein wahres Monster«. Der ursprüngliche Scheduler konnte nicht auf eine große Zahl von Threads compilieren und wurde 2001 durch den O(1)-Scheduler ersetzt. Doch dieser konnte trotz einer Vielzahl von Heuristiken nicht alle Erwartungen erfüllen und wurde 2007 durch den Completey Fair Scheduler (CFS) abgelöst. Dieser berechnet den nächsten auszuführenden Thread nicht so effizient wie der O(1)-Scheduler, aber immer noch schnell genug (proportional zum Logarithmus der Threadanzahl).
Mit der stark gestiegenen Komplexität des Schedulers mussten sich zwangsläufig Fehler einschleichen. Fehler, die zwar nicht das System destabilisierten, aber die CPUs nicht optimal auslasteten. Insgesamt vier solche Fehler fand das Forscherteam.
Der erste Fehler (Group Imbalance) tritt auf, wenn beispielsweise eine Kernel-Compilierung und eine aufwendige Statistik-Berechnung mit zwei Prozessen, gleichzeitig laufen. Das Symptom ist, dass ein oder mehrere CPUs praktisch im Leerlauf sind. Die Forscher konnte die Ursache ermitteln und eine sehr simple Lösung entwickeln, die statt der mittleren Auslastung einer Scheduler-Gruppe (hier gleichzusetzen mit einer CPU) die minimale Last verwendet. Die Behebung dieses Fehlers kann einzelne Programme wie »lu« aus dem NAS-Benchmark bei 60 Threads um Faktor 13 beschleunigen, für andere Programme dürfte die Verbesserung systemabhängig um die 13 Prozent liegen.
Der zweite Fehler (The Scheduling Group Construction) tritt nur auf, wenn ein Programm mit taskset an bestimmte CPUs gebunden wird. Er kann dazu führen, dass alle Threads des Programms statt auf zwei nur auf einer CPU laufen, während die zweite sich langweilt. Auch hier gibt es eine einfache Korrektur, die die Scheduler-Gruppen anders initialisiert. Betroffene Programme laufen wie zu erwarten nach der Korrektur um Faktor 2 schneller. Solche, die viele Sperren setzen, wie das erwähnte »lu«, können um Faktor 27 zulegen.
Der dritte Fehler (Overload-on-Wakeup) ist, dass ein Thread, der aufgeweckt wird, immer auf derselben CPU verbleibt, selbst wenn diese bereits ausgelastet ist und andere CPUs nichts zu tun haben. Aus Scheduler-Sicht ist das Verhalten aber günstig, da die Daten des Threads möglicherweise noch im Cache liegen (der CPU-spezifisch ist). Die Entscheidung, auf eine andere CPU zu migrieren, ist nicht einfach, denn das lohnt sich nur, wenn ein dort ein Kern für ausreichend lange Zeit frei ist. Dem Scheduler fehlte bisher ein solches Kriterium, daher implementierten die Forscher eine simple Heuristik, die keine zusätzliche Zeit benötigt. Der TPC-H-Benchmark lief nach dieser Änderung auf dem Testsystem mit 64 Kernen (8 CPUs) um etwa 13% schneller.
Der vierte Fehler (Missing Scheduling Domains) tritt auf, wenn eine ganze CPU vom Administrator deaktiviert und später wieder aktiviert wird. Aufgrund einer fehlerhaften Neuberechnung der Scheduler-Gruppen werden neue Treads nur noch auf bestimmte Kerne verteilt, während der Rest der Kerne leerläuft. Auch hier konnten die Forscher das Problem beheben, denn es musste nur ein vergessener Funktionsaufruf hinzugefügt werden.
Es ist anzunehmen, dass die Patches zur Behebung der beschriebenen Fehler bereits in Kürze in den Kernel aufgenommen werden. Auch wenn einzelne Programme dadurch um ein Mehrfaches schneller werden können - wenn gleichzeitig viele andere Threads laufen -, ist im Schnitt eher mit einer Beschleunigung um 10 bis 20 Prozent zu rechnen. Alle Fehler scheinen nur auf Systemen mit mehreren Mehrkern-Prozessoren aufzutreten, so dass die Auswirkungen auf gewöhnliche Heim- und Unternehmensrechner unmerklich sein dürften. Da Linux jedoch nahezu ein Monopol auf Hochleistungs- und Superrechnern innehält, dürfte die Anwendergemeinschaft auf diesen Systemen die Patches freudig erwarten.
Zum Abschluss wagen die Forscher noch einen Blick in die Zukunft. Der ideale Scheduler ist ihrer Ansicht nach modular, um die Komplexität beherrschbar zu machen. Dabei übernimmt der eigentliche Scheduler die Verteilung der Treads auf die CPUs anhand einiger elementarer Kriterien. Diese Verteilung kann durch Module beeinflusst werden, die weitere Kriterien heranziehen. Was die beste Strategie ist, wenn verschiedene Module Entscheidungen vorschlagen, die unvereinbar sind, ist allerdings noch immer ein Gegenstand der Forschung.
){kind=small}
