O(1) ütemező
A HupWiki-ből...
A 2.6-os Linux kernel ütemezője a kernel/sched.c fájlban van definiálva. Az ütemező algoritmus és a hozzá kapcsolódó támogató kód nagymértékű átalakításon ment keresztül a 2.5-ös fejlesztői kernel készítésének korai szakaszában. Az átirat a magyar Molnár Ingo nevéhez fűződik. Az ütemező kód teljesen új lett, és nem hasonlít a korábbi kernelek ütemezőjéhez. Az ütemező tervezésekor az alábbi szempontok voltak a legfontosabbak:
- Teljesen O(1) formájú ütemezés. Az új ütemező minden egyes algoritmusa konstans idő alatt fut le, függetlenül a futó processzek számától, vagy bármilyen más inputtól.
- Tökéletes több processzoros (SMP) skálázhatóság. Mindegyik processzor saját, egyéni zárolással (locking) és futási sorral (runqueue) bír.
- Javított processzor (SMP) affinitás. Törekvés arra, hogy a processzeket lehetőleg mindig ugyanazon CPU-n futtassuk (ne legyen felesleges CPU-ról CPU-ra költözködés, ami overheaddel jár). Csak akkor migrálódjon egy taszk egy másik CPU-ra, ha elveszik az egyensúly a futási sorok (runqueue) mérete között. Ilyenkor szóba jöhet a terhelés-kiegyenlítés (load balancing).
- Nyújtson jó interaktív teljesítményt. Ha a rendszer terhelése számottevő, a rendszer akkor is reagáljon, és futtassa az interaktív taszkokat azonnal.
- Legyen igazságos. Egyik processz se találja magát indokolatlanul hosszú időn át időszelet nélkül. Ebből következik, hogy egyik processz sem kaphat igazságtalanul nagy mennyiségű időszeletet.
- Viselkedjen hasonlóan akkor is ha csak 1-2 futtatandó processz van, és akkor is, ha több processzoros környezetben mindegyik processzor számos processzel bír.
A 2.6-os Linux kernel a 2.6.23-as kiadással megválik az O(1) algoritmussal dolgozó processz ütemezőjétől és a szintén Molnár Ingo által fejlesztett Completely Fair Scheduler (CFS) névre hallgató ütemezőre vált.
Az új ütemező kielégíti ezeket az elvárásokat.
