Názor k článku Přidělování procesoru procesům a vláknům v Linuxu od Pavel Píša - Ingo Molnár napsal pro 2.6 O(1) scheduler, který má...

Ingo Molnár napsal pro 2.6 O(1) scheduler, který má sice optimální komplexitu, ale později se ukázalo, že je potřeba čas dělit spravedlivěji. Con Kolivas napsal cheduler založený přibližně na principech EDF http://en.wikipedia.org/wiki/Con_Kolivas , který zajišťuje spravedlivější dělění času, pokud procesy sice vytěžují CPU hodně, ale na určité krátké časové úseky jsou v jádře blokované. Ingo implemetaci kritikou potopil, ale uznal základ přístupu a navrhl vlastní CFQ (Completely Fair Scheduler). Ten je nyní součástí jádra. Jeho komplexita při začleňování do ready fronty je pro SCHED_OTHER přibližně O(log n) – je založen na RB-tree viz. http://en.wikipedia.org/wiki/Completely_Fair_Scheduler
Ani toto řešení není optimální a stále se provádějí postupná zlepšení. Pro real-time aplikace je snaha zavést na místo SCHED_FIFO SCHED_DEADLINE (EDF) http://www.gitorious.org/sched_deadline/pages/Home .
Co se týče rozdělení práce mezi CPU, tak jsou možné dva přístupy, společná fronta – optimální vytížení a přednosti priorit, avšak nutnost společného zámku (možná by šlo najít i nějaké block-less řešení, otázka je pak složitost). Změny ve sdílených řádkách paměti cache znamenají enormní overhead a ping-pong snoop protokolů (např MOESI http://en.wikipedia.org/wiki/MOESI_protocol pro AMD7).
Proto Linux používá na každém CPU lokální fronty a plánovač a s určitým intervalem nebo v idle provádí load balancing.
Odkazy jsem jen narychlo nahledal ve Wikipedii. Nejlepší je si projít přímo zdrojáky http://lxr.linux.no/#linux+v2.6.34/include/linux/sched.h a dále soubory sched*.[ch] z http://lxr.linux.no/#linux+v2.6.34/kernel/ .
Obecně je přínosné, že se někdo pokusil o zpracování tématu na Root, ale bylo by dobré přidat článek s aktuálnějším a preciznějším řešením současné situace.
Další zdroj, který sdružuje hodnotné informace je LWN. Projděte odkazy v sekci Scheduler http://lwn.net/Kernel/Index/
Jinak něco z práce mých kolegů na téma rozvrhování: http://frescor.org/ , http://frsh-forb.sourceforge.net/ .
Pavel Píša
http://cmp.felk.cvut.cz/~pisa/