Der Scheduler ist ein wesentlicher Bestandteil von Betriebssystemen. Er plant
und regelt die Abläufe in den Prozessoren in einem Computersystem. Dafür
muss er eine Menge von Prozessen und Resourcen verwalten und die evtl. wartenden
Prozesse fair und effizient auf die zur Verfügung stehenden Prozessoren
verteilen.
Diese Verwaltungstätigkeit selbst kostet Rechenzeit, die als Overhead ihren
Beitrag zur Gesamtleistung eines Systems liefert. Je kleiner dieser Overhead,
desto größer ist die Netto-Rechenzeit.
Die Komplexität von Algorithmen wird in der O-Notation angegeben, als mathematische Beschreibung der Laufzeit eines Algorithmus. Eine Komplexität von O(n) bezeichnet Algorithmen, deren Laufzeit linear von der Menge der Eingabedaten abhängt. Ein Algorithmus der Komplexität O(1) läuft in konstanter Laufzeit unabhängig von der Eingabemenge.
Im Folgenden wird beschrieben, wie der Scheduler im Linux-Kernel seit Version 2.6 arbeitet und warum diese Verwaltungstätigkeit in konstanter Zeit unabhängig von der Anzahl der wartenden Prozesse abläuft.