A Linux processz ütemező

Mivel közeledik a 2.6-os Linux kernel első stabil kiadásának időpontja (talán már decemberben megjelenik a stabil 2.6.0), úgy gondoltam, hogy nézzük át az egyik legfontosabb ``alkatrészét'', amely Molnár Ingonak köszönhetően jelentős fejlődésen esett át a 2.5-ös fejlesztési periódus alatt.

Ütemezés

-----------

Az ütemező (scheduler) a kernel azon része, amely kiválasztja azt a processzt, amely következőként futhat. Az ütemezőt (vagy más néven processz ütemezőt) úgy is tekinthetjük, mint egy darab kódot, amely azért felel, hogy a processzor véges erőforrását felossza a rendszeren levő futtatandó processzek között. Az ütemező az alapja az olyan multitaszkos operációs rendszereknek, mint amilyen a Linux. A ütemező azzal, hogy helyes sorrendben kiválasztja azt, hogy melyik processz futhat egy másik után, nagy mértékben felelős a rendszer helyes kihasználtságáért. Ha munkáját helyesen teszi, akkor azt az benyomást keltheti a felhasználóban, hogy a processzek egy időben, párhuzamosan futnak. Pedig egy egyprocesszoros rendszer esetében egy időpillanatban mindig csak egy processz futhat.

Az ütemező mögött álló elgondolás egyszerű. A processzoridő legjobb kihasználása érdekében tételezzük fel, hogy vannak futtatandó processzek, és hogy egy processznek minden körülmények között futnia kell. Ha több processz van, mint amennyi processzor található a rendszerben, néhány processz nem fog mindig futni. Ezek a processzek futásra fognak várni. Azt a fontos döntést, hogy melyik processz futhat legközelebb a futtatandó processzek közül, az ütemezőnek kell meghoznia.

A multitaszkos operációs rendszereket két fő részre oszthatjuk: kooperatív multitaszkos vagy preemptív multitaszkos rendszerekre. A Linux, mint az összes Unix variáns, és a legtöbb modern operációs rendszer (igen a Windows is), preemptív multitaszkos rendszer. A preemptív multitaszking lényege, hogy az ütemező hozhat olyan döntést, hogy egy processz futását felfüggeszti, és helyette egy másik processz futását engedélyezi. Azt az eseményt, amikor egy processz nem önszántából mond le a futásáról, hanem az ütemező készteti arra, hogy szüneteltesse azt, preemptálásnak nevezzük. Azt az előre meghatározott időt, amennyit a processz azelőtt futhat, mielőtt a preemptálás bekövetkezik, időszeletnek (timeslice) hívjuk. Az időszelet tulajdonképpen nem más, mint a processzoridő azon szelete, amely az egyes processzekre jut. Az időszeletek kezelése teszi lehetővé az ütemezőnek, hogy a rendszer számára globális ütemezési döntéseket hozzon. Az ütemező feladatai közé tartozik az is, hogy megakadályozza, hogy egy processz egymagában kisajátítsa a rendszert. A Linux kernel ütemezője dinamikusan számolja ki az időszeletet. Ennek ellentéte a kooperatív multitaszking, amelyben a processz futása nem áll meg addig, amíg az önként le nem mond a futásról. Azt az eseményt amikor egy processz önként lemond a futásáról ``yielding''-nek nevezzük. Ennek az elgondolásnak számos hátulütője van: az ütemező nem hozhat olyan globális döntést, amely meghatározná, hogy az adott processz milyen hosszú ideig futhat. Ennek eredményeképpen egy processz akár hosszabb ideig is lefoglalhatja a processzort, és rosszabb esetben egy ``fennakadt'' processz az egész rendszert is magával ránthatja. Szerencsére az utóbbi évtizedben a legtöbb operációs rendszer tervezésekor figyelembe vették a preemptív multitaszking előnyeit, és a legtöbb rendszer már ennek szellemében íródott (a Mac OS 9 és korábbi verziói az egyetlenek, amelyek említésre méltó kivételek). Természetesen a Unix rendszerek a kezdetektől fogva preemptív multitaszking képességekkel rendelkeznek.

A 2.5-ös kernelsorozat fejlesztése alatt a Linux kernel ütemezője generáljavításon esett át. Az új ütemező - amelyet a benne használt algoritmus viselkedése miatt O(1) ütemezőnek hívnak - pótolja a korábbi kernelek ütemezőjének hiányosságait, erőteljes új funkciókat mutat fel és sokkal jobb teljesítményt ad.

Irányelv (policy)

------------------

A irányelv (policy) az ütemezőnek az a viselkedési formája, amely meghatározza, hogy mi mikor futhat. Az ütemező irányelve gyakran meghatározza az egész rendszer működésének milyenségét (vagy inkább minőségét?), és felelős a processzoridő optimális kihasználásáért. Szóval ez nagyon fontos.

I/O-függő vs. processzor-függő processzek

------------------------------------------------

A processzeket feloszthatjuk I/O függő és processzor függő processzekre. Az előbbit úgy jellemezhetjük, hogy az a processz I/O függő, amely sok időt tölt azzal, hogy I/O kérést küld vagy vár. Tehát az ilyen processz gyakran futtatható de csak rövid időre, mert az állandó I/O-ra várás ezt teszi lehetővé (az I/O-ra várás természetesen nem csak a diszkre várás lehet, hanem lehet mondjuk billenytű leütésre várakozás is). Ennek ellentéte a processzor függő processz, amely idejének nagy részét kód végrehajtással tölti. Ezek a processzek addig tudnak futni, amíg be nem következik a preemptálás, hiszen nem kell gyakran I/O-ra várniuk. Viszont a rendszer jó válaszadó képességével szemben támasztott igény azt követeli, hogy az ütemező a processzor függő processzeket ne futtassa gyakran. Az ütemező irányelv a processzor függő processzeknél afelé hajlik, hogy az ilyen processzeket inkább ritkábban, de hosszabb ideig futtassa. A Unix variánsokon az ütemező irányelvek határozottan az I/O függő processzeknek kedveznek.

Az ütemező irányelvnek két teljesen szembenálló célt kell igyekezni kielégíteni: gyors processz válaszadási időt (low latency) és nagy processz áteresztőképességet. Hogy az ütemezők kielégítsék ezeket a kívánalmakat, gyakran komplex algoritmusokat alkalmaznak, hogy meghatározzák melyik processz a legértékesebb, és mindezt úgy teszik, hogy közben ne veszélyeztessék a többi alacsonyabb prioritású processzeket. Az, hogy az I/O függő proesszeket favorizálja az ütemező, ahhoz vezet, hogy javul a processz válaszadási idő, mert az interaktív processzek I/O függők. A Linux azért, hogy jó interaktív válaszadó képességgel rendelkezzen, az I/O függő processzeket előnyben részesíti a processzor függő processzekkel szemben. Mindezt úgy teszi, hogy emellett nem hanyagolja el a processzor függő processzeket sem.

Processz prioritás

-------------------

Az ütemező algoritmusok gyakori típusa a prioritás-alapú ütemezés. Az ötlet az, hogy rangsoroljuk a processzeket értékük és processzor igényük szerint. Azok a processzek, amelyek nagyobb prioritást kapnak hamarabb futnak, mint az alacsonyabb prioritásúak, míg az egyenlő prioritású processzek az ún. round-robin (egyik a másik után, ismétlődően) ütemezésben részesülnek. Néhány rendszeren - köztük a Linuxon is - a nagyobb prioritással rendelkező processzek hosszabb időszeletet kapnak. Mind a felhasználó, mind a rendszer képes a processzek prioritását állítani annak érdekében, hogy megváltoztassák a rendszer ütemezési viselkedését.

Linux erre az ötletre épül, és emellett tartalmazza a dinamikus prioritás-alapú ütemezést is. Ez az elgondolás úgy működik, hogy van egy kezdeti alap prioritás, és az ütemezőnek engedélyezve van, hogy ezt a kezdeti alap prioritást növelje vagy csökkentse az éppen aktuális ütemezési céloknak megfelelően. Például, ha egy processz a legtöbb idejét azzal tölti, hogy I/O (input/output) adatra vár (I/O függő), akkor az a Linux rendszeren emelt prioritást fog kapni. Ezzel ellentétben az a processz, amely állandóan felhasználja az egész időszeletét (processzor függő), alacsonyabb dinamikus prioritást kap.

A Linux kernelben két elkülönített prioritási tartomány van. Az első a ``nice'' érték, amely egy szám, és –20-tól 19-ig vehet fel értéket. Az alapértelmezett érték 0. A nagyobb érték az alacsonyabb prioritást jelenti. Az alacsonyabb ``nice'' értékkel rendelkező processz (magasabb prioritású) előbb fog futni, mint a magasabb ``nice'' értékkel rendelkező (alacsonyabb prioritású) processz. A ``nice'' érték segít meghatározni azt is, hogy milyen hosszú időszeletet kapott egy processz. Az a processz, amelynek a ``nice'' értéke –20, kapja a maximális időszeletet, míg a 19-es ``nice'' értékkel rendelkező a minimum időszeletet. A ``nice'' értékek, mint standard prioritási tartományok, az összes Unix rendszeren használatosak.

A második tartomány a valós idejű prioritás. Ez alapértelmezetten egy 0-tól 99-ig terjedő tartomány. Az összes valós idejű processz magasabb prioritással rendelkezik, mint a normál processzek. A Linuxban implementált valós idejű prioritás megfelel a POSIX követelményeinek. Az legtöbb modern Unix rendszer rendelkezik hasonló sémával.

Folytatása következik.

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