A Linux processz ütemező III.

• 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.

Az új ütemező kielégíti ezeket az elvárásokat.

Futási sorok (runqueues)
-----------------------------

A processz ütemező egyik elemi adat struktúrája a futási sor (runqueue). A runqueue kernel/sched.c fileban van definiálva, mint ``struct runqueue''. A runqueue tulajdonképpen egy lista, a futtatandó processzek listája egy adott processzoron. Processzoronként egy (runqueue) van. Minden egyes futtatandó processz pontosan egy meghatározható runqueue-ban van. A runqueue továbbá per-processzor ütemezési információkat is tartalmaz. Következésképpen a runqueue egy processzoronkénti elsődleges ütemezési adat struktúra. A runqueue-kat egy csoport makrón keresztül lehet elérni. A cpu_rq(processor) makró például az megadott processzorral kapcsolatos runqueue-ra mutató pointerrel tér vissza. Hasonlóan a this_rq() makró az aktuális processzor runqueue-jával tér vissza. Végül a task_rq(task) makró azzal a pointerrel tér vissza amely arra a runqueue-ra mutat, amelyen az adott taszk várakozik.

Mielőtt a runqueue-t változtatnánk, azt zárolni (lock) kell. Mivel minden egyes processzornak saját runqueue-ja van, ritka eset az, hogy egy processzor zárolni szeretné egy másik processzor runqueue-ját (ennek ellenére megtörténhet, ahogy azt látni fogjuk). A runqueue zárolása lehetővé teszi a zárolónak (lock-holder), hogy olvassa vagy írja a runqueue elemeit (tagjait). A leggyakoribb eset a runqueue zárolására az, amikor azt a runqueue-t akarod zárolni, amelyen egy specifikus taszk fut. Ebben az esetben task_rq_lock() és a task_rq_unlock() függvények használatosak.

Hogy elkerüljük a deadlock helyzeteket, a töbszörös runqueue zárolásnál megfelelő sorrendben kell a runqueue-ket zárolni. Erre a double_rq_lock() és double_rq_unlock() függvények használhatóak.

Egy gyors példa arra, hogy miért fontos a runqueue-k zárolásának sorrendje. A forgó zár (spin lock) használatos arra, hogy meggátolja, hogy több taszk egy időben manipulálja ugyanazon runqueue-kat. Ezek úgy működnek, mint a kulcs az ajtóhoz. Az első taszk eléri az ajtót, elveszi a kulcsot, bemegy az ajtón, és bezárja maga mögött. Ha egy másik taszk is eléri az ajtót, és azt bezárva találja (mert egy másik taszk már benn van), akkor várakoznia kell addig, amíg az első taszk ki nem jön, és vissza nem hozza a kulcsot. Ezt a várakozást ``forgásnak'' (spinning) nevezzük, mert a taszk egy szoros ciklusban állandóan ellenőrzi, hogy szabad-e már az ajtó, azaz, hogy visszatért-e már a kulcs. Most tételezzük fel, hogy egy taszk zárolni akarja az első runqueue-t, majd utána a másodikat. Közben egy másik taszk zárolni akarja a második runqueue-t, majd utána zárolni szeretné az elsőt. Tegyük fel, hogy az első taszk sikeresen zárolta az első runqueue-t, miközben ezzel egy időben a második taszk szintén sikeresen zárolta a második runqueue-t. Most, az első taszk megpróbálja zárolni a második runqueue-t, a második taszk pedig az elsőt. Egyik taszk sem fog sikerrel járni, mert a másik taszk már tartja a zárat. Mindkét taszk a végteleségig fog várni arra, hogy a másik elengedje a runqueue-t, de ez nem fog bekövetkezni. Ellenben ha mindkét taszk azonos sorrendben alkalmazza a zárolást, akkor ez a helyzet nem következhet be.

Folytatása következik.

Az írás Robert M. Love hasonló című írásán alapul.

* O(1) (ejtsd: ordó 1) - Az algoritmusok hatékonyságának (komplexitásának) szemléltetésére bevezették az O (ordó) operátort. Nézzünk egy példát: képzeljünk el egy láncolt listát vagy egy közönséges tömböt, amelyben egységnyi elem van. Az adott elem megtalálásának ideje egyenesen arányos az elemek számával. Ha száz elemből egy másodperc alatt megtaláltuk a keresett elemet, akkor számíthatunk arra, hogy ezer elemnél kb. 10 másodpercig fog tartani a keresés. Az ilyen algoritmust nevezzük O(n)-nek (ejtsd: ordó n), amely az előbb említett egyenes vonalú viszonyt, azaz az elemek számával arányos végrehajtási időt jelenti. Minél több elem van, annál hosszabb ideig tart a végrehajtás. Példa az O(n) algoritmusra: lista/tömb végigolvasása, lista/tömb minimális/maximális elemének, elemek átlagának meghatározása, n!, fib(n) kiszámítása

Ezzel szemben az O(1) algoritmus esetén gyakorlatilag szinte konstans idő alatt, azaz elemszámtól függetlenül kb. ugyanannyi ideig tart a keresés. Ezért ezen esetben a keresési algoritmus O(1), azaz konstans. Példa az O(1) algoritmusra: egyszerű értékadás, írás-olvasás veremből.