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.

Külső hivatkozások

Személyes eszközök