Completely Fair Scheduler

Ez a Mű a Creative Commons Nevezd meg! - Ne add el! - Ne változtasd! 4.0 Nemzetközi Licenc feltételeinek megfelelően felhasználható.

A Linux 2.6-os kernelének ütemezője

Elvárások

Ideális multitaszkot támogató hardveren több processz képes egymás mellett futni egyidejűleg, azaz párhuzamosan. Ekkor a teljes processzor teljesítmény egyenletesen oszlik el az egyes processzek között, valamint egyiknek sem kell arra várnia, hogy CPU időt kaphasson. Valódi hardveren ez csak akkor valósítható meg, ha legalább ugyanannyi CPU van, mint processz, ám ez többnyire nem teljesül. Egy CPU-n mindig csak egy processz futhat. A multitaszk opererációs rendszerek ezért azt az illúziót keltik, mintha egyszerre futnának a programok, oly módon, hogy felváltva kapnak CPU időt, mégpedig olyan gyakori ez a váltás, hogy a processzek futása folyamatosnak tűnik. A cél az ideális hardver működésének a lehető legjobban való megközelítése. Törekedni kell a minél nagyobb fokú korrektségre, tehát egyik processz sem maradhat CPU idő nélkül hosszabb ideig indokolatlanul. Minél tovább kell várakoznia egy processznek, annál nagyobb az őt ért igazságtalanság mértéke. Fontos az is, hogy a döntéseket minél gyorsabban hozza meg az operációs rendszer. A bemutatásra kerülő ütemező ezen elvárásokat igyekszik teljesíteni.

A Teljesen Korrekt Ütemező elnevezésben a ,,teljesen” szó nem fedi a valóságot, valójában arra utal, hogy az egyes processzeket ért igazságtalanságokat képes alacsony szintre csökkenteni, de ennek ellenére nem éri el az ideális hardver szintjét. Az ismertetésre kerülő algoritmus és architektúra a magyar Molnár Ingo nevéhez fűződik.

Működés

Architektúra

A 2.6-os kerneltől kezdve az ütemező moduláris felépítésű: Különböző ütemezési osztályok léteznek prioritás szerint rendezve. Egy processz egy ütemezési osztályhoz tartozhat. Minden osztálynak nyújtania kell bizonyos szolgáltatásokat, mint a processzek futási sorba való beillesztését, kivételét, futásra való kiválasztását. Ezeket a szolgáltatásokat a fő ütemező hívja meg, de ez utóbbinak nem kell tudnia, hogy az egyes osztályok milyen algoritmussal végzik el a feladatukat. Jelenleg három ütemező osztályt tartalmaz a kernel: a valós idejű, a teljesen korrekt ütemezőt, valamint a batch feladatok osztályát. A valós idejű a fontosabb, tehát ha van futtatatható valós idejű processz, akkor az fog futni, egyébként a második ütemező jut szerephez, és az futtathat a saját normál processzei közül egyet. Amennyiben nincs semmi dolga a CPU-nak, csak akkor futhat az utolsó osztályba tartozó taszkok közül valamelyik, ezek nem szakíthatnak meg másokat, és a futásuk rögtön megáll, mihelyst el kell indítani egy fontosabb processzt. A későbbiekben ütemező alatt a második osztályt, azaz a teljesen korrekt ütemezőt értjük.

Adatszerkezet

Az ütemező az egyes CPU-khoz tartozó futó processzeket tartalmazó futási sorokat piros-fekete fával reprezentálja, mely csomópontjai az egyes taszkokat tartalmazzák. Ez egy bináris fa adatszerkezet, mely különlegessége, hogy kiegyensúlyozott, azaz n csomópont esetén a fa magassága legfeljebb 2*lg(n+1). Az egyes műveletek (beillesztés, törlés) O(lg n) időben végrehajthatóak, valamint a bal szélső, azaz a legkisebb kulccsal rendelkező elem lekérdezése O(1) komplexitású. Ez utóbbi nagyon fontos, hiszen a fa legbaloldalibb eleme által tárolt taszk lesz jogosult arra, hogy CPU időt kapjon, tehát maga a taszk kiválasztás gyorsan megoldható. Molnár Ingo mérései alapján a többi művelet O(lg n) komplexitása nem okoz számottevő lassulást még nagy processz mennyiség mellett sem.

Prioritások

A Linux az egyes processzeket megkülönbözteti azok fontossága szerint: A fontosabb, processzor igényesebb feladatoknak több, míg a kevésbé fontosaknak, több I/O műveletet használóknak kevesebb CPU időt biztosít. A fontosságot prioritás értékekkel adhatjuk meg. Ezen értékeket két fő tartományra oszthatjuk: valós idejűre, és a normálra. A valós idejű taszkok mindig előbb futnak, mint a másik csoportba tartozók, ezek ütemezésének feladatát a valós idejű ütemező modul látja el. A nem valós idejű taszkok prioritását a nice értékkel adhatjuk meg, amely egy -20 és 19 közötti szám. Az alacsonyabb érték magasabb, míg a magasabb alacsonyabb prioritást jelent. Az azonos prioritással rendelkező taszkok ugyanakkora időszeletet kapnak a futásra, azaz ez esetben round-robinhoz hasonló ütemezésről van szó. Természetesen a nagyobb prioritású taszkok több CPU időhöz jutnak. Alapértelmezetten egy taszk nice értéke 0, ám ezt az ütemező (vagy az adminisztrátor) megváltoztathatja: Amennyiben a processz túl sok időt tölt I/O műveletekkel, akkor csökkenti annak prioritását, és növeli, ha a nagyobb CPU használat a jellemzőbb. A kernel a processz prioritását átszámolja egy un. leterheltségi súly értékre. A 0 nice értékű processz súlya 1024. Amennyiben a nice érték 1-el nő, úgy a súly 0.8-szeresére változik, 1-el való csökkenés esetén pedig 1.25-el szorzódik. Tegyük fel, hogy van két (A és B) processzünk, 0 nice értékkel, ekkor mindkettő súlya 1024. Ekkor mindkét processz a teljes CPU idő 50%-át kapja meg, mivel 1024 / (1024 + 1024) = 0.5. Megnöveljük A processz nice értékét 1-el, az ő súlya 820 lesz. Ekkor A processz részesedése a teljes CPU időből: 820 / (1024 + 820) ≈ 0.45, míg B processzé 1024 / ( 1024 + 820) ≈ 0.55 lesz. Az egyes CPU-khoz tartozó futási soron belül nyomon követik a sorhoz tartozó processzek súlyainak összegét, így tudja a kernel, hogy melyik processzor mennyire van leterhelve, szükség esetén a jobban megterhelt CPU-tól egy vagy több processzt átköltöztet egy kevésbé leterheltre.

A taszkok elrendezése

A virtuális óra elve

A hagyományos ütemezési algoritmusok időszeleteket állapítanak meg az egyes processzek számára, és ezeket az időintervallumokat időnként valamilyen szabály alapján újraszámolják. A korrekt ütemezési módszerek nem használnak időszeleteket, ehelyett arra törekednek, hogy a rendszer működése minél jobban megközelítse az ideális hardver működését. Azaz N futó processz mindegyike a CPU teljesítmény 1/N-ed részét használja fel. Ily módon, ha mindegyik lefutásához t0 idő szükséges abban az esetben, ha csak 1 processz lenne, ám N lefutásához N * t0 idő kell. Valóságos hardveren ez úgy nézne ki elvileg, hogy egy adott időintervallumot elosztanak N részre, amiket sorra kiosztanak az egyes processzeknek, ekkor az eredmény ugyanaz, mint ideális esetben. Előfordulhat viszont, hogy az egyes processzek nem használják ki a teljes időszeletet, mivel például I/O műveletre várnak. Ekkor a processz alvó állapotba kerül, majd átadja a CPU-t egy másik számára. Ekkor azonban az egyik több CPU időhöz juthat, mint az alvó. Törekedni kell tehát arra, hogy az ilyen igazságtalanságokat kompenzáljuk, azaz ha az alvó processz felébredhet (például, megkapta az I/O választ, amire várt), akkor annyival több CPU időt kell biztosítani számára, hogy behozhassa a lemaradását, és így csökkentsük az igazságtalanság mértékét. Hagyományos esetben ezt a következő módon érik el: Egy N darab futtatható processzt tartalmazó futási sor rendelkezik egy virtuális órával. Ez az óra nem a valóságos időt méri, mivel itt az idő N-szer lassabban telik. Ekkor T idő eltelte után a virtuális óra értéke megadja, hogy az egyes processzek ideális esetben mennyi valóságos ideig futottak volna. Például egy 4 processzt tartalmazó futási sor virtuális órája 5 másodpercet mutat 20 valóságos másodperc eltelte után. Minden egyes processzhez tartozik egy várakozási idő érték is. Ez azt adja meg, hogy az egyes processz mennyi időt töltött eddig azzal, hogy a futásra várakozzon. Minél nagyobb ez az érték, annál inkább jogosult arra, hogy futhasson, tehát ez méri az egyes processzekkel szembeni igazságtalanságot. Amennyiben fut a processz, úgy a hozzá tartozó várakozási idő értéke csökken annyival, amennyi ideig fut. Az egyes processzekre a fenti értékekből kiszámítható egy kulcs, ami nem más, mint a várakozási időt kivonják a virtuális óra értékéből. E kulcs szerint rendezik az elemeket a futási sorban – balról jobbra növekvő sorrendben -, majd a legkisebb értékkel rendelkező processz megkapja a jogot a futásra. A futó processz várakozási idejének csökkentése tehát a balról jobbra eltolódást segíti elő a futási soron belül. Az ütemező algoritmus adott időközönként elindul - vagy a futó processz blokkolódik -, majd újraszámolja a kulcsokat, és ha kell, megszakítja az aktuális futását, és újat indít el.

Teljesen korrekt ütemezés a Linux esetében

Az aktuális (2.6-os) kernel a fenti virtuális óra elvét használja, ám ettől valamennyire eltérő módon. A korábban ismertetett módszer nem biztosítja a prioritások figyelembe vételét. A prioritások azt szabják meg, hogy az egyik processz több vagy kevesebb ideig futhat a többihez képest. Az ötlet a következő: Ha egy processz CPU időt kap, akkor amennyiben ő fontos, akkor az ő ideje lassabban járjon le, és így több időhöz jusson, ám ha kevésbé fontos, akkor az ő órája gyorsabb, tehát kevesebb ideig fog futni. A fent leírt módszerrel ellentétben itt minden processz rendelkezik egy vruntime nevű változóval, amely számolja, hogy mennyi virtuális ideig futott eddig a processz. Ez az érték csak tényleges futás esetén nő. 0 nice értékű processz vruntime értéke a valóságos időnek megfelelően növekszik. Ezt az értéket delta_exec időközönként frissítik. Magasabb nice esetén (tehát kevésbé fontos processzről van szó), vruntime gyorsabban nő, mégpedig a következő módon: NICE_0_LOAD értéke (1024) a 0 nice-hoz tartozó leterheltségi súly, ezt osztják a processz nice értékének megfelelő súllyal. Az így kapott hányadossal szorozzák delta_exec–et, majd ezzel az értékkel növelik vruntime–ot. Vegyünk egy processzt, amely nice értéke 1. Ekkor 1 valós másodperc alatt az ő vruntime értéke 1 * (1024 / 820) ≈ 1.25-el nő, tehát hamarabb fog lejárni az ő ideje, mint alacsonyabb nice értékű processzé. Szükség van még egy min_vruntime értékre is, ami a futási soron belül a legkisebb vruntime-al egyenlő. A processzekhez tartozó kulcs pedig a következő: vruntime – min_vruntime. Tehát ha egy processz fut, akkor növekszik az ő vruntime-ja, a többié viszont nem. Mivel min_vruntime monoton nő, ezért előbb-utóbb a futó processz kulcsa nagyobb lesz, mint a sorban a következőé, ezért átadja neki a CPU-t.

Csoportos ütemezés

Felmerülhet olyan igény is, hogy bizonyos processzeket csoportba rendeznek (például adott felhasználó programjai). Amennyiben több csoport van, akkor a fenti ütemezés először a csoportok között történik meg, azaz az ütemező először kiválaszt egy futtatásra jogosult csoportot, majd azon belül egy processzt. Az egyes csoportokat ugyanúgy korrekten igyekszik kezelni, mint a processzeket, tehát ha a csoportok egyenrangúak, akkor ha az egyikhez több processz tartozik, mint a másikhoz, akkor is ugyanannyi CPU időt kap mindkettő. Például, ha A felhasználónak 2, míg B-nek 48 processze van, akkor A és B is a CPU idő 50%-át kapja meg, nem pedig 4% és 96%-ot vagyis A nem kerülhet hátrányba B-vel szemben.

Irodalomjegyzék:

1. Wolfgang Mauerer: Professional Linux Kernel Architecture
2. Avinesh Kumar: Multiprocessing with the Completely Fair Scheduler
3. Linux-source-2.6.28 kernel dokumentáció
4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Algoritmusok