Ugrás a tartalomhoz

Operációs rendszerek mérnöki megközelítésben

Benyó Balázs, Fék Márk, Kiss István, Kóczy Annamária, Kondorosi Károly, Mészáros Tamás, Román Gyula, Szeberényi Imre, Sziray József

Panem Kiadó

6.4. Folyamatok kezelése és ütemezése

6.4. Folyamatok kezelése és ütemezése

Ebben az alfejezetben azokat az adatstruktúrákat és algoritmusokat mutatjuk be, amelyek a folyamatokkal és szálakkal kapcsolatosak a Windows NT 4.0-s operációs rendszerben.

6.4.1. A Windows NT folyamatmodellje

A folyamatok az NT-ben egy adott program kódját végrehajtó (egy vagy több) szálból, valamint a szálak által lefoglalt erőforrásokból állnak. Az NT folyamat modellje a következő dolgokat foglalja magába:

  • A végrehajtandó program kódját és adatait.

  • Saját virtuális memória címteret, amit a folyamat használhat.

  • Rendszererőforrásokat (szemaforokat, fájlokat stb.) amiket az operációs rendszer foglal a folyamat számára, amikor a folyamathoz tartozó szálak azokat megnyitják.

  • A folyamat egyedi azonosítóját (process ID, PID).

  • Legalább egy végrehajtható szálat.

A szál az az egység (entitás) az NT-ben, amit az ütemező kezel és végrehajtásra ütemez a CPU-hoz. A szálak a következő komponensekből állnak:

  • A szálat végrehajtó processzor regiszterei, melyek a processzor állapotát írják le.

  • Két veremtárat (stack). Egyet a kernel módban történő program-végrehajtáshoz, egyet a felhasználói módban történő program-végrehajtáshoz.

  • Kizárólagosan használható tárterületet a DLL-ek, run-time könyvtárak számára.

  • A szál egyedi azonosítóját (thread ID). (Megjegyzendő, hogy a thread ID és a process ID ugyanabból a névtérből kerül ki, így egy rendszerben sohasem lehet két egyező.)

A felsorolás első három elemét együttesen a szál környezeteként (thread context) emlegetjük.

Láthatjuk, hogy az egy folyamathoz tartozó szálak közös virtuális címtartományt használnak. Az egyes folyamatok viszont külön címtartományban futnak, csak osztott elérésű memória használata esetén lehet átfedés két folyamat által használt memóriaterület között.

A folyamatok illetve egészen pontosan a folyamatokat alkotó szálak által használni kívánt memóriaterületeket természetesen a rendszertől kérni kell, le kell foglalni azokat.

A memóriához hasonlóan a folyamatnak le kell foglalni a folyamat által használni kívánt erőforrásokat, amelyeket az NT objektumokként reprezentál. Minden ilyen objektumhoz a megnyitása után a folyamat a gyorsabb elérés érdekében egy ún. handle-t kap.

A rendszer erőforrásainak védelme, illetve az erőforrás használat szabályozása érdekében minden folyamat rendelkezik egy ún. elérési tokennel, mely tartalmazza a folyamat biztonsági azonosítóját, illetve a folyamat jogosultságainak leírását.

Az NT folyamatmodelljének vázlatos képét a 6.7. ábrán láthatjuk.

6.7. ábra. ábra - A Windows NT folyamatmodellje

A Windows NT folyamatmodellje


6.4.2. Folyamatok kezelése a Windows NT-ben

A Windows NT executive rétege a folyamatokhoz tartozó adatokat egy ún. folyamatblokkban (EPROCESS) tárolja. Minden folyamathoz hozzárendel az NT egy ilyen adatstruktúrát a folyamat indulásakor. A blokk a folyamat kísérő adatait tartalmazza, valamint egy sereg mutatót a kapcsolódó adatstruktúrákra. Például minden folyamaton belül van egy vagy több szál, ahol a szálakat ún. executive szálblokk (ETHREAD) ír le. Az EPROCESS blokk és a hozzá tartozó adatstruktúrák a rendszer címterében helyezkednek el. Kivétel ez alól a folyamat futási környezetét leíró ún. folyamatkörnyezeti blokk (PEB: Process Environment Block), amely a folyamat címterében található. Ennek oka, hogy ez az adatstruktúra olyan információt tartalmaz, amit a felhasználói módban futó kód is megváltoztathat.

Az EPROCESS blokkon felül a Win32 alrendszer folyamata is kezel egy folyamatleíró adatstruktúrát (W32PROCESS). Minden Win32 kódot végrehajtó folyamathoz tartozik egy-egy ilyen adatstruktúra.

A folyamatok és szálak adatstruktúrájának egyszerűsített vázlatát a 6.8. ábrán mutatjuk be.

6.8. ábra. ábra - Folyamatokhoz és szálakhoz tartozó adatstruktúra

Folyamatokhoz és szálakhoz tartozó adatstruktúra


Folyamat létrehozása (CreateProcess)

Egy Win32 folyamat akkor jön létre, amikor egy alkalmazás meghívja a Win32 CreateProcess függvényét. A létrehozás több fázisból áll, amelyeket az operációs rendszer három részlete valósít meg: a Win32 kliensoldali könyvtárából a KERNEL32.DLL, a Windows NT executive, valamint a Win32 alrendszer folyamat (CSRSS). Mivel a Windows NT több környezeti alrendszert kezel, emiatt egy Windows NT executive réteg processz objektumának kezelése (amit más alrendszerek is tudnak használni) szét van választva attól a tevékenységtől, ami a Win32 folyamat létrehozásával jár.

A következő felsorolás összefoglalja a Win32 CreateProcess hívásának főbb lépéseit:

  1. A processzen belül végrehajtandó image-fájl (.EXE) megnyitása.

  2. A Windows NT executive processz objektumának létrehozása.

  3. A kezdeti szál létrehozása.

  4. A Win32 értesítése az új processzről, azzal a céllal, hogy az felkészüljön az új processzre és szálra.

  5. A kezdeti szál végrehajtásának elindítása.

  6. Az újonan létrehozott processz és szál környezetben a címtér inicializálása (például a szükséges DLL-ek betöltése), majd a program végrehajtásának elkezdése.

A fenti lépések mindegyikére vonatkozóan az alábbi megjegyzések érvényesek:

  • Egyetlen CreateProcess híváshoz egynél több prioritási osztály specifikálható. A Windows NT a processzhez automatikusan a legalacsonyabb prioritási osztályt rendeli.

  • Ha nincs prioritási osztály specifikálva az új folyamathoz, a prioritási osztály a Normal besorolást kapja.

  • Minden ablakot egy desktophoz rendel a rendszer. (Desktopnak nevezi az NT a felhasználó által használható grafikus környezetet. Egy munkahelyen több desktopot is képes kezelni a rendszer.) Ha a Create­Processben nincs megadva, melyik desktopot használja a folyamat, ak­kor a folyamat automatikusan a hívó aktuális desktopjához rendelődik.

6.4.3. Szálak kezelése az NT-ben

A következőkben először a szálak struktúrájával foglalkozunk. A továbbiakban, hacsak másként nem említjük, az itt leírtak egyaránt érvényesek mind a normál felhasználói módú szálakra, mind pedig a kernel módú rendszerszálakra.

Az operációs rendszer szintjén egy Windows NT szálat egy ún. executive szál blokk (ETHREAD) reprezentál. A blokkot a 6.9. ábra mutatja be. Az ETHREAD blokk és azok az adatstruktúrák, melyekre az ETHREAD blokkban tárolt pointerek mutatnak, a rendszer címtartományában találhatók, a szál környezeti blokkjának kivételével, ami a folyamat címtartományában van. Az ETHREAD blokkon kívül, a Win32 alrendszer folyamata is kezel egy szálleíró adatstruktúrát minden egyes szálhoz, ami egy Win32-es folyamatban jött létre.

Az ábrán látható első mező a kernel szálblokk (KTHREAD). Ezt követi a szálazonosítási információ, a processzazonosítási információ, a saját processz­hez tartozó pointerrel, biztonsági információ az elérési tokenre mutató poin­ter formájában, a megszemélyesítési információ, és végül az LPC-üzenetekre, illetve a függőben levő B/K-kérésekre vonatkozó mezők. A KTHREAD blokk tartalmazza mindazokat az adatokat, amelyekre a kernelnek van szüksége a szálütemezés és a szinkronizáció végrehajtása érdekében.

6.9. ábra. ábra - Az executive szálblokk felépítése

Az executive szálblokk felépítése


Szál létrehozása (CreateThread)

Egy szál életciklusa akor veszi kezdetét, amikor egy program új szálat hoz létre. Az erre irányuló kérés eljut a Windows NT executive-hoz, ahol a pro­cesszkezelő (elnevezése: process dispatcher) helyet jelöl ki egy szálobjektum számára, majd a kernelt hívja, a kernel szálblokk kezdeti értékeinek beállítása végett. A következőkben végigvesszük azokat a lépéseket, amelyek a Win32 CreateThread függvénye szerint történnek a KERNEL32.DLL-ben, azzal a céllal, hogy egy Win32 szál jöjjön létre:

  1. A CreateThread egy felhasználói módú stacket hoz létre a szál részére, a folyamat címterében.

  2. A CreateThread beállítja a kezdeti értékeket a szál hardverkapcsolataihoz.

  3. Az NtCreateThread függvény hívására kerül sor, ami az executive szál objektumát hozza létre. Az ide tartozó lépések sorozata kernel módban hajtódik végre, a Windows NT executive-ján és kernelén belül.

  4. A CreateThread értesíti a Win32 alrendszert az új szálról, amire az alrendszer különböző beállításokat eszközöl az új szál részére.

  5. A szál összetett elérési címe (handle) és azonosítója (amik a 3. lépésben lettek generálva) visszaadódik a hívónak.

  6. A szál olyan állapotba került, hogy ütemezni lehet a végre­hajtását.

6.4.4. Szálak ütemezése

Ebben a részben az ütemezési elvekkel foglalkozunk. A Windows NT prioritáson alapuló, preemptív (kiszorító) ütemezési elvet valósít meg. Egy NT rendszerben mindig a legmagasabb prioritású futtatható szál fut, azzal a megkötéssel, hogy a futást azok a processzorok korlátozhatják, amelyeken a szál futása meg van engedve. Ezt a jelenséget processzor-affinitásnak nevezzük. Általában egy szál bármelyik rendelkezésre álló processzoron futhat, de a processzor-affinitás megváltoztatható a Win32 ütemezési függvényeinek felhasználásával.

6.4.4.1. A kvantum

Amikor egy szál futásra választódik ki, egy előre megszabott ideig fog futni. Ezt az időszeletet kvantumnak (quantum) nevezzük. Egy kvantum az az idő­tar­tam, amennyit egy szál futhat, mielőtt a Windows NT megszakítja a szálat azért, hogy kiderítse, nem vár-e futásra egy másik szál ugyanakkora prioritással, vagy pedig nincs-e szükség a megszakított szál prioritásának csökkentésére. A kvantumok értéke szálanként változhat. Ugyanakkor azonban az is lehetséges, hogy egy szál nem jut el a kvantumja végéig. Ez a szituáció a pre­emptív ütemezés következtében léphet fel: ha egy másik szál, nagyobb prioritással, futásra kész állapotba kerül, a futásban levő szál ki lesz szorítva a saját időszelete lejárta előtt. Ezenfelül még az is előfordulhat, hogy egy szál futásra lesz kiválasztva, és még azelőtt leállítódik, hogy elkezdené a kvantumját.

A Windows NT ütemezési funkcióit a kernel valósítja meg. Nincs azonban külön ütemező modul a kernelen belül, az ütemező rutinok kódja a kernel különböző helyein van szétosztva. Az ütemezést megvalósító rutinok összességét közös néven a kernel diszpécserének (dispatcher) nevezik. Egy szál ütemezése az IRQL 2-es szintjén fordul elő, és a következő események bármelyike elindíthatja:

  • Egy szál futásra kész állapotba kerül. Például egy újonnan kreált szál, vagy egy olyan, ami éppen felszabadult a várakozásból.

  • Egy szál futása leáll, mivel a kvantumja véget ért, illetve befejeződött a futás, vagy várakozási állapotba került a szál.

  • Egy szál pioritása megváltozik, vagy egy rendszerkiszolgálási hívás miatt, vagy mert maga a Windows NT változtatja meg a prioritási értéket.

  • Egy futásban levő szál processzor-affinitása megváltozik.

Az operációs rendszernek a fenti esetek mindegyikében el kell döntenie, melyik szál fog futásra következni. A futó szál váltásakor a rendszer környezetváltást hajt végre: elmenti az éppen futó szál környezetét és betölti a futásra kijelölt szál környezetét.

Az ütemezési döntések szigorúan a szálak alapján történnek, ami azt jelenti, hogy egyáltalán nem számít, hogy egy szál melyik processzhez tartozik. Ha például egy A processznek 10 futtatható szála van, egy B-nek pedig 2, és mindegyik szálnak ugyanaz a prioritása, akkor mindegyik szál a CPU-idő 12-ed részét kapja. Vagyis a Windows NT nem ad 50 százalék CPU-időt az A processznek, és 50 százalékot a B-nek.

A szálütemező algoritmusok szorosan kötődnek a prioritási szintekhez. A Windows NT 32 prioritási szintet használ, 0-tól 31-ig. Ezek felosztása a következő:

  • tizenhat valós idejű szint (16–31),

  • tizenöt változószint (1–15),

  • egy rendszerszint (0), ami le van foglalva minden NT-rendszerben egyedül létező ún. zérus oldal (zero page) szálának.

A szálakhoz rendelt kvantumok értékét a Windows NT a következő tényezők beszámításával határozza meg:

  • Minden szálnak van egy kijelölt kvantumértéke, ami nem időtartam, hanem egy egész szám, amit nevezzünk kvantum egységnek.

  • Határozatlan helyzetben a szálak a Windows NT Workstation-ön 6-tal indulnak, míg a Windows NT Serveren 36-tal. Az utóbbi érték azért nagyobb, hogy több idő jusson a kliensek beérkező kéréseinek biztonságos kiszolgálására.

  • Amikor az órajel ad megszakítást, akkor a szál kvantumából 3 levonódik. Ha az 0 vagy kevesebb lesz, lejár a kvantum, és új szál lesz futásra kiválasztva. Eszerint az NT Workstation-ön 2 óraintervallum, az NT Ser­ve­ren pedig 12 óraintervallum jut egy szál futására ilyenkor.

  • Az óraintervallumok hossza természetesen függ a hardver platformtól. Másrészről a megszakítások gyakoriságát a HAL működése szabja meg, nem pedig a kernel. Például, az Intel rendszerek óraimpulzusa 10 msec (486-os), illetve 15 msec (Pentium Pro), míg a DEC Alpha AXP rendszereké 7,8 msec.

6.4.4.2. Egy szál állapotai

A Windows NT operációs rendszerben egy szál futása során több végrehajtási állapoton megy keresztül. Ezek a lehetséges állapotok a következők:

  • Készenlét. A szál végrehajtásra kész állapotban van. A diszpécser csak az ebben az állapotban levő szálak halmazát veszi figyelembe a végrehajtás ütemezésekor.

  • Standby. Egy szál akkor van standby állapotban, ha a dispatcher kiválasztotta egy adott CPU-n futásra az éppen futó szálat követően. Egy processzorhoz csak egyetlen szál létezhet standby állapotban az operációs rendszeren belül.

  • Futás. Miután a diszpécser környezetváltást hajt végre, a futási jogot megkapó szál futási állapotba kerül és megindul a végrehajtása. A végrehajtás addig folytatódik, amíg a kernel ki nem szorítja a szálat egy nagyobb prioritású szál futása érdekében, vagy lejár a szál kvantuma, a szál befejeződik, vagy pedig saját magától a várakozási állapotba lép.

  • Várakozás. Egy szál több módon léphet be a várakozási állapotba: ön­kényesen várhat egy objektumra, hogy az szinkronizálja a végrehajtását, az operációs rendszer (a B/K-rendszer például) várakozhat a szál érdekében, vagy egy környezeti alrendszer irányítja a szálat önmaga felfüggesztésére. Amikor a szál várakozása véget ér, akkor a prioritástól függően a szál vagy azonnal elkezd futni, vagy visszakerülhet készenléti állapotba.

  • Átmenet. Egy szál az átmeneti állapotba lép át, ha készen áll a végrehajtásra, de az ő kernel stackje ki van mentve (page-elve) a memóriából. Miután a szál kernel stackje visszakerül a memóriába, a szál készenléti állapotba megy át.

  • Befejezett. Amikor egy szál végrehajtása véget ér, a szál a befejezett állapotba kerül. Ebben az állapotban a szál objektumának a törlése az objektumkezelőtől függ. Ha az executive-nak van pointere az objektumhoz, az executive inicializálva ismét fel tudja használni a szál objektumát.

Az állapotok közötti átmenet gráfját a 6.10. ábra mutatja be.

6.10. ábra. ábra - Egy szál állapotai a Windows NT-ben

Egy szál állapotai a Windows NT-ben


Multiprocesszoros környezetben a szálütemezés megoldása a CPU-k közötti munkamegosztás intenzív szervezését követeli meg. Mindent összevéve a Windows NT úgy jár el, hogy megkísérli a legmagasabb prioritású futtatható szálakat a szabadon lévő CPU-khoz ütemezni. Mindazonáltal több tényező befolyásolja annak megválasztását, hogy egy szál melyik CPU-n fusson. A kiválasztási algoritmus ismertetése előtt néhány fogalmat vezetünk be.

6.4.4.3. A processzoraffinitás

Minden egyes szál egy ún. affinitási maszkkal (affinity mask) rendelkezik, amely azokat a processzorokat adja meg, amelyeken a szál futása megengedett. A szál affinitási maszkja a processz affinitási maszkjából öröklődik. Alapesetben mindegyik processz, és ennek megfelelően mindegyik szál egy olyan affinitási maszkkal kezd, amely megegyezik a rendszer aktív procesz-szorainak a halmazával. Más szóval, mindegyik szál tud futni mindegyik processzoron. Ezt az állapotot két dolog képes megváltoztatni:

  • Egy hívás az alkalmazás felől, amely át tudja állítani a processzhez, illetve a szálhoz tartozó maszkokat: ez a SetProcessAffinityMask, illetve a SetThreadAffinityMask függvények hívása.

  • Az image-fejlécben specifikált affinitási maszk, amely a teljes image-re érvényes.

Mindegyik szálnak van két CPU-sorszáma, amik a kernel szálblokkban vannak tárolva:

  • ideális processzor, vagyis a kitüntetett processzor, amin a szálnak futni kell,

  • következő processzor, vagyis az a processzor, amelyik a szál következő futására lett kiválasztva (vagy amin az utoljára futott).

Az ideális processzor kiválasztása véletlenszerűen történik, amikor egy szál létrejön. Ehhez a processzblokkban egy számláló van fenntartva. Ez a számláló minden egyes szál létrehozásakor eggyel növekszik, ami által az új szálak ideális processzorai körben választódnak ki a rendelkezésre állókból. A Windows NT már nem változtatja meg az ideális processzort, miután a szál létrejött. A változtatásra csak az alkalmazásoknak van módjuk az olyan szálnál, ami a SetThreadIdealProcessor függvényt használja.

6.4.4.4. A processzor kiválasztása

Amikor egy szál futásra kész állapotba kerül, a Windows NT először egy tétlen processzorhoz próbálja a szálat ütemezni. Ha a tétlen processzorokból lehet választani, akkor előnyben részesül a szál ideális processzora, majd ezután jön a szál következő processzora. Ha ez sem áll rendelkezésre, akkor az utasításokat éppen végrehajtó processzor jön sorra. (Vagyis az, amelyiken az ütemezési kód fut.) Ha ezen CPU-k egyike sem tétlen, akkor az első ren­del­kezésre álló tétlen processzor lesz kiválasztva úgy, hogy a Windows NT végigellenőrzi a tétlen processzorok maszkját, növekvő CPU-sorszám szerint.

Ha pillanatnyilag mindegyik CPU foglalt, és egy szál futásra kész állapotba került, a Windows NT azt vizsgálja meg, hogy van-e olyan futásban vagy várakozásban levő szál, amit ki lehetne szorítani valamelyik CPU-n. A kiválasztás elve ilyenkor a következő.

Az első választás a szál ideális processzora, a második pedig a következő processzora. Ha egyik CPU sincs a szál affinitási maszkjában, akkor az első olyan aktív processzor lesz kiválasztva, amelyiken a szál futni tud.

Ha ez a processzor olyan, amin egy másik szál van legközelebb futásra jelölve (vagyis standby állapotban várakozik az ütemezésre), és annak a szálnak a prioritása kisebb, mint az indításra előkészített szálé, akkor az új szál kiszorítja a másikat a standby állapotból, és ő maga lesz a CPU következő szála. Ha ennél a CPU-nál nincsen következő szál futásra választva, akkor az NT megvizsgálja, hogy az éppen futó szál prioritása kisebb-e, mint az új szálé. Ha kisebb, a futásban levő szálat kiszorításra jelöli ki, és elhelyez a sorban egy processzormegszakítást arra, hogy a futó szál félrelökődjék az új szál javára.

Megjegyezzük, hogy a Windows NT nem vizsgálja az összes CPU-n a jelenlegi és a következő szálak prioritását, hanem csak azon az egy CPU-n teszi ezt, amit a fentiek szerint választott ki. Ha ezen a CPU-n nincsen kiszorítható szál, akkor az új szál bekerül a prioritási szintje szerinti készenléti sorba, ahol várakozni fog, amíg ütemezve nem lesz.

Mint látható volt az előbbiekben, multiprocesszoros környezetben a Windows NT nem mindig a legnagyobb prioritású szálat választja ki egy CPU-n való futtatásra. Így egy olyan szál, ami egy adott CPU-n éppen futó szálnál nagyobb prioritású, készenlétbe kerülhet, de nem biztos, hogy azonnal kiszorítja a futó szálat.