Completely Fair Scheduler

aus Wikipedia, der freien Enzyklopädie

Gesichtet

Dies ist die letzte gesichtete Version, (zeige alle), freigegeben am 14. Mai 2008.

Status

gesichtet

In der Informatik ist der Completely Fair Scheduler, kurz CFS, ein Prozess-Scheduler. Solche Scheduler werden verwendet, um die Priorität von Programmabläufen auf Kernelebene von Betriebssystemen zu verwalten. CFS wurde von Ingo Molnár entwickelt und ersetzte mit der Linux Kernelversion 2.6.23 im Oktober 2007 den zuvor implementierten O(1)-Scheduler.

Der CFS garantiert eine faire Aufteilung der Prozessorzeit. Er verzichtet im Gegensatz zum O(1)-Scheduler auf Heuristiken und Statistiken. Im Idealfall läuft beim CFS jede Task quasiparallel in gleicher Geschwindigkeit. Der CFS kennt keine Runqueue, keine Timeslices und kein Array-Switching, weil es kein expired-Array gibt. Stattdessen ist jedem Prozess ein wait_runtime-Wert zugeordnet, der auf Nanosekunden genau bestimmt ist, und eine Aussage darüber macht, wie lange der Prozess auf seine Ausführung wartet. Derjenige Prozess mit höchster wait_runtime wird gewählt. Als Struktur wird dafür ein nach der wait_runtime sortierter Rot-Schwarz-Baum verwendet.^[1]

[Bearbeiten] Erweiterungen im 2.6.24er-Kernel

Mit dem 2.6.24er-Kernel unterstützt der CFS Task Groups. Dies bedeutet, dass mehrere Tasks zu Gruppen zusammengefasst werden und dadurch ein faires Scheduling zwischen den Gruppen stattfindet. Das kann sinnvoll sein, wenn mehrere User an einem System arbeiten. Folgendes Szenario soll den Sachverhalt einmal verdeutlichen: Benutzer A hat zwei Prozesse am Laufen, Benutzer B dagegen einen. Alle drei Prozesse haben die gleiche Priorität. Der alte Scheduler würde dem Benutzer A zwei Drittel und Benutzer B ein Drittel der CPU-Laufzeit zuteilen. Der CFS teilt dagegen beiden Usern 50% der Rechenzeit zu.^[1]