Completely Fair Scheduler

Der Completely Fair Scheduler (kurz CFS) ist ein Prozess-Scheduler in der Informatik. 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 jeder 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]

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]

Quellen

1. ↑ ^{a b} Ingo Molnár: This is the CFS scheduler., Stand 13. März 2008

Weblinks

• Ingo Molnár: This is the CFS scheduler.
• Thomas Gleixner: The Completly Fair Scheduler. Linuxfoundation Japan Symposium, Juli 2008. (Präsentationsfolien im PDF-Format)
• M. Tim Jones: Inside the Linux 2.6 Completely Fair Scheduler. In: IBM developerWorks, 15. Dezember 2009.