Lage des „Completely Fair Scheduler“ (eines Prozessplaners) in einer vereinfachten Struktur des Linux-Kernels.

Der Completely Fair Scheduler ( CFS ) war ein Prozess-Scheduler , der in die Linux- Kernel- Version 2.6.23 (Oktober 2007) integriert wurde . Er war der Standard-Scheduler für Aufgaben der SCHED_NORMALKlasse `Task` (d. h. Aufgaben ohne Echtzeit-Ausführungsbeschränkungen) und verwaltete die CPU- Ressourcenzuweisung für laufende Prozesse mit dem Ziel, die CPU-Auslastung insgesamt zu maximieren und gleichzeitig die interaktive Leistung zu optimieren.

Im Gegensatz zum vorherigen O(1)-Scheduler älterer Linux-2.6-Kernel, der Ausführungswarteschlangen aktiver und abgelaufener Tasks verwaltete und zwischen ihnen wechselte, basiert die CFS-Scheduler-Implementierung auf CPU-spezifischen Ausführungswarteschlangen. Deren Knoten sind zeitlich geordnete, planbare Einheiten, die mithilfe von Rot-Schwarz-Bäumen sortiert werden . CFS verwirft das alte Konzept fester Zeitschlitze pro Priorität und zielt stattdessen darauf ab, Tasks (oder besser: planbaren Einheiten) einen fairen Anteil der CPU-Zeit zuzuweisen. [ 1 ] [ 2 ]

Ab Linux-Kernel-Version 6.6 wurde er durch den EEVDF- Scheduler ersetzt. [ 3 ]

Algorithmus

Eine Aufgabe (d. h. ein Synonym für Thread) ist die kleinste Einheit, die Linux planen kann. Linux kann jedoch auch Gruppen von Threads, ganze Multithread-Prozesse und sogar alle Prozesse eines bestimmten Benutzers verwalten. Dieses Design führt zum Konzept der planbaren Entitäten, bei denen Aufgaben gruppiert und vom Scheduler als Ganzes verwaltet werden. Damit dieses Design funktioniert, task_structenthält jeder Aufgabendeskriptor ein Feld vom Typ `Task` sched_entity, das die Menge der Entitäten repräsentiert, zu denen die Aufgabe gehört.

Jede CPU-spezifische Run-Queue cfs_rqsortiert sched_entityStrukturen zeitlich geordnet in einen Rot-Schwarz-Baum (oder „rbtree“ in Linux-Sprache), wobei der Knoten ganz links von der Entität belegt ist, die den geringsten Anteil an Ausführungszeit erhalten hat (gespeichert im vruntimeFeld der Entität). Die Knoten sind nach der Prozessor- Ausführungszeit in Nanosekunden indiziert. [ 4 ]

Für jeden Prozess wird außerdem eine „ maximale Ausführungszeit “ berechnet, die die Zeit angibt, die der Prozess auf einem „idealen Prozessor“ voraussichtlich benötigt hätte. Dies ist die Zeit, die der Prozess auf seine Ausführung gewartet hat, geteilt durch die Gesamtzahl der Prozesse.

Wenn der Scheduler aufgerufen wird, um einen neuen Prozess auszuführen:

  1. Der am weitesten links stehende Knoten des Ablaufplanungsbaums wird ausgewählt (da er die geringste Ausführungszeit aufweist ) und zur Ausführung gesendet.
  2. Wenn der Prozess seine Ausführung erfolgreich abgeschlossen hat, wird er aus dem System und dem Ablaufplan entfernt.
  3. Wenn der Prozess seine maximale Ausführungszeit erreicht oder auf andere Weise gestoppt wird (freiwillig oder durch Interrupt), wird er basierend auf seiner neu verbrauchten Ausführungszeit wieder in den Ablaufplanbaum eingefügt .
  4. Anschließend wird der neue linke Knoten aus dem Baum ausgewählt, und der Vorgang wird wiederholt.

Wenn ein Prozess viel Zeit im Leerlauf verbringt, ist sein Zeitaufwand gering, und er erhält automatisch eine höhere Priorität, sobald er diese benötigt. Daher erhalten solche Aufgaben nicht weniger Prozessorzeit als Aufgaben, die ständig laufen.

Die Komplexität des Algorithmus zum Einfügen von Knoten in die cfs_rqAusführungswarteschlange des CFS-Schedulers beträgt O ( log N ), wobei N die Gesamtzahl der Entitäten ist. Die Auswahl der nächsten auszuführenden Entität erfolgt in konstanter Zeit, da der am weitesten links stehende Knoten stets im Cache gespeichert ist.

Geschichte

Die Arbeiten von Con Kolivas im Bereich Scheduling, insbesondere seine Implementierung von „ Fair Scheduling “ namens Rotating Staircase Deadline , inspirierten Ingo Molnár zur Entwicklung seines CFS-Schedulers als Ersatz für den früheren O(1)-Scheduler . Molnár würdigte Kolivas in seiner Ankündigung. [ 5 ] CFS ist eine Implementierung des gut erforschten, klassischen Scheduling-Algorithmus Weighted Fair Queuing . [ 6 ] Fair Queuing wurde ursprünglich für Paketnetzwerke entwickelt und zuvor unter dem Namen Stride Scheduling auch für CPU-Scheduling eingesetzt . CFS ist die erste Implementierung eines Fair-Queuing -Prozess-Schedulers, der in einem Allzweck-Betriebssystem weit verbreitet ist. [ 6 ]

Im November 2010 erhielt der Linux-Kernel für Version 2.6.38 einen Patch für den CFS-Scheduler, der die Nutzung auf Desktop- und Workstations optimiert. Der von Mike Galbraith auf Basis von Ideen von Linus Torvalds entwickelte Patch implementiert die sogenannte automatische Gruppierung, die die interaktive Desktop-Performance deutlich verbessert. [ 7 ] Der Algorithmus ordnet Elternprozesse und Kindprozesse derselben Aufgabengruppe zu. [ 8 ] (Aufgabengruppen sind an Sitzungen gebunden, die über den setsid()Systemaufruf erstellt werden. [ 9 ] ) Dadurch wurde das Problem langsamer Reaktionszeiten auf Mehrkern- und Mehrprozessorsystemen ( SMP ) behoben, wenn diese rechenintensive Aufgaben mit vielen Threads ausführten. Vereinfacht ausgedrückt: Mit diesem Patch kann man weiterhin Videos ansehen, E-Mails lesen und andere typische Desktop-Aktivitäten ruckelfrei ausführen, während beispielsweise der Linux-Kernel kompiliert oder Videos codiert werden.

Im Jahr 2016 wurde der Linux-Scheduler für eine bessere Multicore-Leistung gepatcht, basierend auf den Vorschlägen aus dem Artikel „The Linux Scheduler: A Decade of Wasted Cores“ [ 10 ] .

Im Jahr 2023 wurde ein neuer Scheduler auf Basis des Earlyly Eligible Virtual Deadline First Scheduling (EEVDF) vorbereitet, um CFS zu ersetzen. [ 11 ] Die Motivation bestand darin, die Notwendigkeit von CFS-„Latenzverbesserungs“-Patches zu beseitigen. [ 12 ]

Siehe auch

Referenzen

  1. ^ Love, Robert (2010). Linux Kernel Development (3. Aufl.). Vereinigte Staaten von Amerika: Addison Wesley. S.  41–61 . ISBN 9780672329463Die
  2. ^ „Linux: Der absolut faire Scheduler | KernelTrap“ . 19.04.2007. Archiviert vom Original am 19.04.2007 . Abgerufen am 16.05.2021 .
  3. ^ Corbet, Jonathan. „Completing the EEVDF scheduler“ . LWN.net . Abgerufen am 24.12.2025 .
  4. ^ „IBM Developer“ . developer.ibm.com . Abgerufen am 25. Mai 2024 .
  5. ^ Molnár, Ingo (2007-04-13). "[Patch] Modular Scheduler Core und Completely Fair Scheduler [CFS]" . linux-kernel (Mailingliste).
  6. Li , T.; Baumberger, D.; Hahn, S. (2009). „Effiziente und skalierbare faire Mehrprozessor-Planung mittels verteiltem gewichtetem Round-Robin-Verfahren“ ( PDF ) . ACM SIGPLAN Notices . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . doi : 10.1145/1594835.1504188 . 
  7. ^ Der etwa 200 Zeilen lange Linux-Kernel-Patch, der Wunder bewirkt
  8. ^ Galbraith, Mike (15.11.2010). "[RFC/RFT PATCH v3] Re: [RFC/RFT PATCH v3] sched: automatisierte Aufgabengruppen pro TTY [CFS]" . linux-kernel (Mailingliste).
  9. ^ Galbraith, Mike (2010-11-20). "[PATCH v4] sched: automatisierte Aufgabengruppen pro Sitzung" . linux-kernel (Mailingliste).
  10. ^ Lozi, Jean-Pierre; Lepers, Baptiste; Funston, Justin; Gaud, Fabien; Quema, Vivian; Fedorova, Alexandra. „Der Linux-Scheduler: Ein Jahrzehnt verschwendeter Kerne“ (PDF) . EuroSys 2016. doi : 10.1145/2901318.2901326 . Abgerufen am 15. Juni 2019 .
  11. ^ „EEVDF Scheduler möglicherweise bereit für die Veröffentlichung in Linux 6.6“ . www.phoronix.com . Abgerufen am 27.07.2023 .
  12. ^ „Ein EEVDF-CPU-Scheduler für Linux [LWN.net]“ . lwn.net . Abgerufen am 27.07.2023 .