Completely Fair Scheduler

(zkracováno CFS, česky doslova Zcela férový plánovač) je jeden z plánovačů linuxového jádra, do kterého je začleněn od verze 2.6.23 vydané v říjnu 2007. Naprogramoval jej Ingo Molnár a inspiroval se přitom u konkurenčního plánovače australského programátora a lékaře Cona Kolivase. Na rozdíl od starších plánovačů, které měly fronty úloh, spravuje CFS všechny procesy v jediném červeno-černém stromě. Frekvenci přepínání lze nastavit na úrovni nanosekund a tím ovlivnit, zda je důležitější, aby systém rychle reagoval (typicky u stolních počítačů), nebo aby měl celkově co nejvyšší výkon (typicky u serverů).

Asymptotická časová složitost plánovacího algoritmu je O(log N), přičemž samotné naplánování sice probíhá v konstantním čase, ale znovuzařazení procesu do červeno-černého stromu vyžaduje O(log N) operací.

Reference

Kategorie:Jádro Linuxu Kategorie:Algoritmy plánování procesů