Completely Fair Scheduler

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.[1] 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.[2] 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ů).[3]

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

  1. ANDREWS, Jeremy. Scheduler Fixes. KernelTrap [online]. 2007-10-12 [cit. 2010-12-8]. Dostupné v archivu pořízeném dne 2010-12-16. 
  2. ANDREWS, Jeremy. Linux: The Completely Fair Scheduler. KernelTrap [online]. 2007-4-18 [cit. 2010-12-8]. Dostupné v archivu pořízeném dne 2012-06-29. 
  3. OUTRATA, Jan. Co se děje v jádře - červen 2007. LinuxExpres [online]. 2007-8-21 [cit. 2010-12-8]. Dostupné online.