CFS:Völlig faire Prozessplanung in Linux

Linux verfolgt einen modularen Ansatz für die Prozessorplanung, da verschiedene Algorithmen verwendet werden können, um verschiedene Prozesstypen zu planen. Eine Scheduling-Klasse gibt an, welche Scheduling-Policy für welchen Prozesstyp gilt. Completely Fair Scheduling (CFS), das 2007 Teil des Linux 2.6.23-Kernels wurde, ist die Scheduling-Klasse für normale (im Gegensatz zu Echtzeit-)Prozessen und trägt daher den Namen SCHED_NORMAL .

CFS ist für die in einer Desktop-Umgebung typischen interaktiven Anwendungen ausgelegt, kann aber als SCHED_BATCH konfiguriert werden um die Batch-Workloads zu bevorzugen, die beispielsweise auf einem High-Volume-Webserver üblich sind. Auf jeden Fall bricht CFS dramatisch mit dem, was man „klassisches präemptives Scheduling“ nennen könnte. Auch der Anspruch „völlig fair“ ist mit einem technischen Auge zu sehen; andernfalls könnte die Behauptung wie eine leere Prahlerei erscheinen.

Lassen Sie uns in die Details eintauchen, was CFS von anderen Prozess-Schedulern unterscheidet – und sogar übertrifft. Beginnen wir mit einer kurzen Wiederholung einiger wichtiger Fachbegriffe.

Einige Kernkonzepte

Linux erbt die Unix-Ansicht eines Prozesses als Programm in Ausführung. Daher muss ein Prozess mit anderen Prozessen um gemeinsam genutzte Systemressourcen konkurrieren:Speicher um Anweisungen und Daten zu speichern, mindestens ein Auftragsverarbeiter um Anweisungen auszuführen, und E/A-Geräte mit der Außenwelt zu interagieren. Bei der Prozessplanung weist das Betriebssystem (OS) Aufgaben (z. B. das Knacken einiger Zahlen, das Kopieren einer Datei) Prozessoren zu – ein laufender Prozess führt dann die Aufgabe aus. Ein Prozess hat einen oder mehrere Ausführungsthreads , die Sequenzen von Anweisungen auf Maschinenebene sind. Einen Prozess zu planen bedeutet, einen seiner Threads auf einem Prozessor zu planen.

Das Linux-Terminal

• Die 7 besten Terminalemulatoren für Linux
• 10 Befehlszeilentools für die Datenanalyse unter Linux
• Jetzt herunterladen:SSH-Spickzettel
• Spickzettel für fortgeschrittene Linux-Befehle
• Linux-Befehlszeilen-Tutorials

In einem vereinfachenden Schritt verwandelt Linux die Prozessplanung in eine Thread-Planung, indem ein geplanter Prozess so behandelt wird, als wäre er Single-Threaded. Wenn ein Prozess mit N multithreaded ist Threads, dann N Planungsaktionen wären erforderlich, um die Threads abzudecken. Threads innerhalb eines Multithreading-Prozesses bleiben insofern verwandt, als sie Ressourcen wie den Speicheradressraum gemeinsam nutzen. Linux-Threads werden manchmal als Lightweight-Prozesse beschrieben, wobei lightweight unterstreicht die gemeinsame Nutzung von Ressourcen zwischen den Threads innerhalb eines Prozesses.

Obwohl sich ein Prozess in verschiedenen Zuständen befinden kann, sind zwei von besonderem Interesse beim Scheduling. A blockiert Der Prozess wartet auf den Abschluss eines Ereignisses, z. B. eines E/A-Ereignisses. Der Prozess kann die Ausführung erst wieder aufnehmen, nachdem das Ereignis abgeschlossen ist. Ein lauffähiges Prozess ist einer, der derzeit nicht blockiert ist.

Ein Prozess ist prozessorgebunden (auch bekannt als compute-bound ), wenn es im Gegensatz zu E/A-Ressourcen hauptsächlich Prozessor verbraucht und E/A-gebunden ist im gegenteiligen Fall; Daher ist ein prozessorgebundener Prozess meistens lauffähig, während ein I/O-gebundener Prozess meistens blockiert ist. Beispielsweise ist das Knacken von Zahlen prozessorgebunden, und der Zugriff auf Dateien ist E/A-gebunden. Obwohl ein vollständiger Prozess entweder als prozessorgebunden oder als E/A-gebunden charakterisiert werden kann, kann ein gegebener Prozess während verschiedener Phasen seiner Ausführung entweder das eine oder das andere sein. Interaktive Desktop-Anwendungen wie Browser sind in der Regel E/A-gebunden.

Ein guter Prozessplaner muss die Anforderungen von prozessorgebundenen und I/O-gebundenen Aufgaben ausgleichen, insbesondere in einem Betriebssystem wie Linux, das auf so vielen Hardwareplattformen gedeiht:Desktop-Maschinen, eingebettete Geräte, mobile Geräte, Server-Cluster, Supercomputer , und mehr.

Klassische präemptive Planung versus CFS

Unix hat die klassische präemptive Planung populär gemacht, die später von anderen Betriebssystemen wie VAX/VMS, Windows NT und Linux übernommen wurde. Im Mittelpunkt dieses Planungsmodells steht eine feste Zeitscheibe , die Zeitspanne (z. B. 50 ms), die eine Task einen Prozessor halten darf, bis sie zugunsten einer anderen Task vorgezogen wird. Wenn ein vorgezogener Prozess seine Arbeit nicht beendet hat, muss der Prozess neu geplant werden. Dieses Modell ist insofern leistungsfähig, als es Multitasking (Parallelität) durch Prozessor-Time-Sharing unterstützt, selbst auf den Single-CPU-Rechnern von gestern.

Das klassische Modell umfasst normalerweise mehrere Planungswarteschlangen, eine pro Prozesspriorität:Jeder Prozess in einer Warteschlange mit höherer Priorität wird vor jedem Prozess in einer Warteschlange mit niedrigerer Priorität geplant. Beispielsweise verwendet VAX/VMS 32 Prioritätswarteschlangen für die Planung.

CFS verzichtet auf feste Zeitscheiben und explizite Prioritäten. Die Zeitdauer für eine bestimmte Aufgabe auf einem Prozessor wird dynamisch berechnet, wenn sich der Planungskontext über die Lebensdauer des Systems ändert. Hier eine Skizze der motivierenden Ideen und technischen Details:

• Stellen Sie sich einen Prozessor P vor, der dahingehend idealisiert ist, dass er mehrere Aufgaben gleichzeitig ausführen kann . Beispielsweise können die Tasks T1 und T2 gleichzeitig auf P ausgeführt werden, wobei jeder 50 % der magischen Verarbeitungsleistung von P erhält. Diese Idealisierung beschreibt perfektes Multitasking , die CFS auf realen im Gegensatz zu idealisierten Prozessoren erreichen möchte. CFS wurde entwickelt, um perfektes Multitasking zu erreichen.

• Der CFS-Scheduler hat eine Ziellatenz , was die minimale Zeit ist – idealisiert auf eine unendlich kleine Dauer – die für jede lauffähige Aufgabe erforderlich ist, um den Prozessor mindestens einmal einzuschalten. Wenn eine solche Dauer unendlich klein sein könnte, dann hätte jede ausführbare Aufgabe den Prozessor während einer beliebigen gegebenen Zeitspanne eingeschaltet, wie klein sie auch sein mag (z. B. 10 ms, 5 ns usw.). Natürlich muss in der realen Welt eine idealisierte unendlich kleine Dauer angenähert werden, und die Standardannäherung beträgt 20 ms. Jede ausführbare Aufgabe erhält dann eine 1/N Slice der Ziellatenz, wobei N ist die Anzahl der Aufgaben. Wenn die Ziellatenz beispielsweise 20 ms beträgt und es vier konkurrierende Aufgaben gibt, erhält jede Aufgabe eine Zeitscheibe von 5 ms. Übrigens, wenn es während eines Scheduling-Ereignisses nur eine einzige Aufgabe gibt, erhält diese glückliche Aufgabe die gesamte Ziellatenz als Slice. Die Messe in CFS tritt im 1/N in den Vordergrund Slice, das jeder Aufgabe gegeben wird, die um einen Prozessor konkurriert.

• Das 1/N Slice ist tatsächlich ein Timeslice – aber kein festes, da ein solches Slice von N abhängt , die Anzahl der Tasks, die derzeit um den Prozessor konkurrieren. Das System ändert sich im Laufe der Zeit. Einige Prozesse werden beendet und neue werden erzeugt; lauffähige Prozesse blockieren und blockierte Prozesse werden lauffähig. Der Wert von N ist dynamisch und daher auch das 1/N Zeitscheibe, die für jede ausführbare Aufgabe berechnet wird, die um einen Prozessor konkurriert. Das traditionelle schöne -Wert wird verwendet, um das 1/N zu gewichten Slice:ein Nice mit niedriger Priorität Wert bedeutet, dass nur ein Bruchteil von 1/N Slice wird einer Aufgabe zugewiesen, wohingegen ein nice mit hoher Priorität Wert bedeutet, dass ein proportional größerer Bruchteil von 1/N Slice wird einer Aufgabe gegeben. Zusammenfassend schön Werte bestimmen nicht den Slice, sondern modifizieren nur die 1/N Slice, das Fairness zwischen den konkurrierenden Aufgaben darstellt.

• Dem Betriebssystem entsteht bei jedem Kontextwechsel Overhead tritt ein; das heißt, wenn ein Prozess zugunsten eines anderen vorgezogen wird. Damit dieser Overhead nicht übermäßig groß wird, gibt es eine Mindestzeit (bei einer typischen Einstellung von 1 ms bis 4 ms), die jeder geplante Prozess ausführen muss, bevor er unterbrochen wird. Dieses Minimum wird als minimale Granularität bezeichnet . Wenn viele Tasks (z. B. 20) um den Prozessor konkurrieren, kann die minimale Granularität (angenommen 4 ms) höher sein als das 1/N Slice (in diesem Fall 1 ms). Wenn sich herausstellt, dass die minimale Granularität größer als 1/N ist Slice ist das System überlastet, weil zu viele Aufgaben um den Prozessor konkurrieren – und die Fairness geht zu Ende.

• Wann liegt Vorkaufsrecht vor? CFS versucht, Kontextwechsel angesichts ihres Overheads zu minimieren:Die Zeit, die für einen Kontextwechsel aufgewendet wird, ist Zeit, die für andere Aufgaben nicht verfügbar ist. Dementsprechend läuft eine Aufgabe, sobald sie den Prozessor erhält, für ihr gesamtes gewichtetes 1/N Slice, bevor er zugunsten einer anderen Aufgabe vorgezogen wird. Angenommen, Aufgabe T1 ist für ihre gewichtete 1/N ausgeführt worden Slice, und die ausführbare Aufgabe T2 hat derzeit die niedrigste virtuelle Laufzeit (vruntime) unter den Aufgaben, die um den Prozessor konkurrieren. Die vruntime zeichnet in Nanosekunden auf, wie lange eine Aufgabe auf dem Prozessor ausgeführt wurde. In diesem Fall würde T1 zugunsten von T2 vorgezogen.

• Der Scheduler verfolgt die vruntime für alle Tasks, lauffähig und blockiert. Je niedriger die vruntime einer Aufgabe ist, desto mehr Zeit verdient die Aufgabe auf dem Prozessor. CFS verschiebt dementsprechend Aufgaben mit geringer V-Laufzeit an den Anfang der Scheduling-Linie. Einzelheiten werden noch bekannt gegeben, da die Linie ist als Baum implementiert, nicht als Liste.

• Wie oft sollte der CFS-Scheduler neu planen? Es gibt eine einfache Möglichkeit, den Einplanungszeitraum zu bestimmen . Angenommen, die Ziellatenz (TL) beträgt 20 ms und die Mindestgranularität (MG) 4 ms:

  TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

  In diesem Fall würden fünf oder weniger Aufgaben jeder Aufgabe erlauben, den Prozessor während der Ziellatenzzeit einzuschalten. Wenn die Aufgabennummer beispielsweise fünf ist, hat jede ausführbare Aufgabe ein 1/N Slice von 4 ms, was zufällig der minimalen Granularität entspricht; wenn die Aufgabennummer drei ist, erhält jede Aufgabe eine 1/N Scheibe von fast 7ms. In beiden Fällen würde der Planer in 20 ms neu planen, der Dauer der Ziellatenzzeit.

  Probleme treten auf, wenn die Anzahl der Aufgaben (z. B. 10) TL / MG überschreitet, da jetzt jede Aufgabe die Mindestzeit von 4 ms anstelle der berechneten 1/N erhalten muss Scheibe, die 2ms ist. In diesem Fall würde der Planer in 40 ms neu planen:

  (number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Linux-Scheduler, die älter als CFS sind, verwenden Heuristiken, um die faire Behandlung interaktiver Aufgaben in Bezug auf die Planung zu fördern. CFS verfolgt einen ganz anderen Ansatz, indem es die Vruntime-Fakten größtenteils für sich selbst sprechen lässt, was zufällig die Schläfer-Fairness unterstützt . Eine interaktive Aufgabe neigt naturgemäß dazu, in dem Sinne viel zu schlafen, dass sie auf Benutzereingaben wartet und so I/O-gebunden wird; Daher neigt eine solche Aufgabe dazu, eine relativ geringe Vruntime zu haben, wodurch die Aufgabe tendenziell an den Anfang der Planungslinie verschoben wird.

Sonderfunktionen

CFS unterstützt symmetrisches Multiprocessing (SMP), bei dem jeder Prozess (ob Kernel oder Benutzer) auf jedem Prozessor ausgeführt werden kann. Noch konfigurierbare Scheduling-Domains kann verwendet werden, um Prozessoren für den Lastausgleich oder sogar die Trennung zu gruppieren. Wenn mehrere Prozessoren dieselbe Scheduling-Policy teilen, dann ist ein Lastausgleich zwischen ihnen eine Option; Wenn ein bestimmter Prozessor eine andere Scheduling-Richtlinie als die anderen hat, dann würde dieser Prozessor in Bezug auf die Scheduling von den anderen getrennt werden.

Konfigurierbare Planungsgruppen sind ein weiteres CFS-Feature. Betrachten Sie als Beispiel den Nginx-Webserver, der auf meinem Desktop-Computer ausgeführt wird. Beim Start hat dieser Server einen Master-Prozess und vier Worker-Prozesse, die als HTTP-Request-Handler fungieren. Für jede HTTP-Anfrage ist der jeweilige Worker, der die Anfrage bearbeitet, irrelevant; Es kommt nur darauf an, dass die Anfrage rechtzeitig bearbeitet wird, und so stellen die vier Worker zusammen einen Pool bereit, aus dem ein Task-Handler gezogen werden kann, wenn Anfragen eingehen. Es erscheint daher fair, die vier Nginx-Worker eher als Gruppe zu behandeln als als Einzelpersonen für Planungszwecke, und eine Planungsgruppe kann genau dafür verwendet werden. Die vier Nginx-Worker könnten so konfiguriert werden, dass sie statt einzelner Vruntimes eine einzelne Vruntime unter sich haben. Die Konfiguration erfolgt auf traditionelle Linux-Weise über Dateien. Für die gemeinsame Nutzung von vruntime wird eine Datei mit dem Namen cpu .Freigaben , mit den Details, die durch vertraute Shell-Befehle gegeben werden, erstellt werden.

Wie bereits erwähnt, unterstützt Linux Scheduling-Klassen so dass verschiedene Planungsrichtlinien zusammen mit ihren Implementierungsalgorithmen auf derselben Plattform koexistieren können. Eine Scheduling-Klasse ist als Codemodul in C implementiert. CFS, die bisher beschriebene Scheduling-Klasse, ist SCHED_NORMAL . Es gibt auch Scheduling-Klassen speziell für Echtzeitaufgaben, SCHED_FIFO (first in, first out) und SCHED_RR (Round-Robin). Unter SCHED_FIFO , Aufgaben werden bis zum Abschluss ausgeführt; unter SCHED_RR , werden Tasks ausgeführt, bis sie eine feste Zeitscheibe erschöpft haben, und vorzeitig beendet werden.

CFS-Implementierung

CFS erfordert effiziente Datenstrukturen zum Verfolgen von Aufgabeninformationen und Hochleistungscode zum Generieren der Zeitpläne. Beginnen wir mit einem zentralen Terminierungsbegriff, der Runqueue . Dies ist eine Datenstruktur, die einen Zeitplan für geplante Aufgaben darstellt. Trotz des Namens muss die Runqueue nicht auf herkömmliche Weise als FIFO-Liste implementiert werden. CFS bricht mit der Tradition, indem es einen zeitgeordneten rot-schwarzen Baum als Runqueue verwendet. Die Datenstruktur ist für diesen Job gut geeignet, da es sich um einen selbstausgleichenden binären Suchbaum mit effizienter Einfügung handelt und entfernen Operationen, die in O(log N) ausgeführt werden Zeit, wobei N ist die Anzahl der Knoten im Baum. Außerdem ist ein Baum eine hervorragende Datenstruktur zum Organisieren von Entitäten in einer Hierarchie basierend auf einer bestimmten Eigenschaft, in diesem Fall einer vruntime.

In CFS stellen die internen Knoten des Baums zu planende Aufgaben dar, und der Baum als Ganzes stellt wie jede Runqueue eine Zeitleiste für die Aufgabenausführung dar. Rot-Schwarz-Bäume werden weit über die Planung hinaus verwendet; Beispielsweise verwendet Java diese Datenstruktur, um seine TreeMap zu implementieren .

Unter CFS hat jeder Prozessor eine spezifische Runqueue von Aufgaben, und keine Aufgabe tritt gleichzeitig in mehr als einer Runqueue auf. Jede Runqueue ist ein rot-schwarzer Baum. Die internen Knoten des Baums stellen Tasks oder Task-Gruppen dar, und diese Knoten werden durch ihre vruntime-Werte indiziert, sodass (im gesamten Baum oder in einem Teilbaum) die internen Knoten links niedrigere vruntime-Werte haben als die rechts:

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

Zusammenfassend befinden sich Tasks mit der niedrigsten vruntime – und daher dem größten Prozessorbedarf – irgendwo im linken Teilbaum; Tasks mit relativ hohen Vruntimes sammeln sich im rechten Teilbaum. Eine vorgezogene Aufgabe würde in den rechten Unterbaum gehen und so anderen Aufgaben die Möglichkeit geben, sich im Baum nach links zu bewegen. Ein Task mit der kleinsten Vruntime landet im äußersten linken (internen) Knoten des Baums, der somit der Anfang der Runqueue ist.

Der CFS-Scheduler hat eine Instanz, die C task_struct , um detaillierte Informationen zu jeder zu planenden Aufgabe zu verfolgen. Diese Struktur bettet eine sched_entity ein Struktur, die wiederum Scheduling-spezifische Informationen enthält, insbesondere die vruntime pro Task oder Task-Gruppe:

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

Der Rot-Schwarz-Baum wird in bekannter C-Manier implementiert, mit einer Prämie für Zeiger für die Effizienz. Ein cfs_rq Strukturinstanz bettet ein rb_root ein Feld namens tasks_timeline , der auf die Wurzel eines rot-schwarzen Baumes hinweist. Jeder der internen Knoten des Baums hat Zeiger auf den Eltern- und die zwei Kindknoten; die Blattknoten haben nil als ihren Wert.

CFS veranschaulicht, wie eine unkomplizierte Idee – jeder Aufgabe einen fairen Anteil an Prozessorressourcen zuzuweisen – auf unkomplizierte, aber hocheffiziente Weise implementiert werden kann. Es lohnt sich zu wiederholen, dass CFS eine faire und effiziente Planung ohne traditionelle Artefakte wie feste Zeitscheiben und explizite Aufgabenprioritäten erreicht. Das Streben nach noch besseren Terminplanern geht natürlich weiter; Im Moment ist CFS jedoch so gut wie es nur geht für allgemeines Prozessor-Scheduling.