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ó

5.3. Belső szerkezet és működés

5.3. Belső szerkezet és működés

Az alábbi részek a UNIX-rendszer legfontosabb alrendszereit és funkcióit tárgyalják.

5.3.1. Szerkezet

Ebben a részben a UNIX-kernel felépítését tárgyaljuk. Röviden ismertetjük a hagyományos és a mai modern UNIX kernel réteg (illetve modul) szerkezetét és vázoljuk ezek fő feladatait.

A korai ’80-as évekig az eltérő UNIX-változatok ellenére a kernelek elég egységes képet mutattak. Egyetlen állományrendszer típust, egyetlen ütemezési politikát és egyetlen végrehajtható állomány formátumot támogattak (5.1. ábra).

5.1. ábra. ábra - A hagyományos UNIX-rendszerek belső szerkezete

A hagyományos UNIX-rendszerek belső szerkezete


Az 5.1. ábra jól mutatja a moduláris felépítést. Ebben a szerkezetben a rugalmasságot a blokkos és a karakteres berendezés kapcsolók biztosították. Ezek lehetővé tették, hogy a rendszerben eltérő típusú berendezéseket egy egységes interfészen keresztül lehessen elérni. A réteges szervezésben rejlő előnyöket már ekkor is hatékonyan kihasználták. Az egymásra épülő rétegek a közvetlen felettük lévő réteg szolgáltatásait egy jól definiált interfészen keresztül vehették igénybe. Sajnos a korai implementációkban a megvalósítás leegyszerűsítése érdekében ez alól akadt néhány kivétel, ami a későbbiekben meg is nehezítette a fejlesztők dolgát.

Mint azt a későbbiekben látni fogjuk, a ’80-as évek közepén egyre nagyobb teret nyerő elosztott állományrendszerek megkövetelték, hogy a UNIX adjon támogatást mind a lokális, mind pedig a távoli állományrendszerek kezeléséhez. Másrészt az osztott könyvtárak megjelenésével szükségessé vált több futtatható fájlformátum támogatása is, illetve speciális alkalmazások (mint például a korábban említett multimédiás alkalmazások) az ütemezéssel szemben is újfajta igényeket támasztottak. Ebből adódóan rugalmasabb ker­nel­szerkezet kialakítására volt szükség, ami több alrendszer, interfész laza, de szerves kapcsolatából épül fel. Az 5.2. ábra ezt az új szerkezetet mutatja. A külső lekerekített téglalapok interfészeket reprezentálnak, amiket számos eltérő módon lehet megvalósítani. Jól látható, hogy az egyes főbb funkciókhoz tartozik egy-egy interfész (de akár több is), amelyeken keresztül az adott funkciók többféle megvalósítását el lehet érni.

Erre talán az egyik legjobb példa az állományrendszer. Míg a korai UNIX-rendszerekben csak egyetlen állományrendszer állt rendelkezésre, a gyakorlati igények megkövetelték, hogy egyszerre több, akár eltérő típusú állományrendszerrel is dolgozni lehessen. Ennek eredményeképp előállt a vnode/vfs interfész, ami már absztrakt szinten kezeli az állományrendszert, lehetővé téve ezáltal eltérő állományrendszerek egységes kezelését. Az interfészből kiinduló nyíl a különféle implementációkat mutatja. Ebben a példában a hagyományos System V s5fs mellett található egy Berkeley FFS, egy elosztott NFS és RFS állományrendszer implementáció is. Az állományrendszerek részletes leírását és fejlődésüket az 5.3.6. alfejezet részletesen tárgyalja. A többi alrendszer esetén is hasonló igények merültek fel. Az 5.2. ábrán például a futtatható állományok kezeléséért felelős exec kapcsolóhoz (alrendszer) is a hagyományos a.out végrehajtható állomány formátum mellett más formátumok kezelését is lehetővé kell tenni.

5.2. ábra. ábra - A modern UNIX-ok egy lehetséges szerkezeti felépítése

A modern UNIX-ok egy lehetséges szerkezeti felépítése


A továbbiakban a UNIX főbb funkcióit, alrendszereit, és a hozzájuk kapcsolódó interfészeket tárgyaljuk.

5.3.2. Folyamatkezelés

Mint azt korábban láttuk, az operációs rendszer elsődleges feladata, hogy a felhasználói programoknak, alkalmazásoknak végrehajtási környezetet (execution environment) biztosítson. A UNIX végrehajtási környezet a folyamat (process) absztrakción alapszik. A hagyományos UNIX-rendszerekben a folyamat egyetlen utasítássorozatot hajt végre egy címtérben (address space). A modern UNIX-változatokban már egy folyamaton belül egyszerre több szálon futhat végrehajtás, több vezérlési pont található. A szálak (threads) vagy könnyűsúlyú folyamatok (lightweight processes) bevezetése bizonyos alkalmazásoknál jelentős hatékonyság növekedést eredményezett. A kliens-szerver architektúra szerver komponense hatékonyan kihasználja a szálak alkalmazásából adódó előnyöket.

Ebben a részben a UNIX hagyományos folyamatmodelljét ismertetjük. A UNIX modern folyamatmodelljének a részleteit az érdeklődő olvasó az irodalomjegyzékben felsorolt idevágó irodalmak tanulmányozásából részletesen megismerheti.

A UNIX-rendszer egy multiprogramozott környezet, a rendszerben egyszerre párhuzamosan több folyamat is aktív. Ezen folyamatok egy virtuális gépen (virtual machine) futnak, minden folyamat a B/K-műveletek és a készülékek vezérlésén kívül úgy érzékeli, mintha csak egyedül ő futna a gépen. A B/K-műveleteket és a készülék vezérlést az operációs rendszer végzi el a folyamat számára. A virtuális gép koncepciójának megfelelően minden folyamat rendelkezik egy regiszterkészlettel, ami a valós hardverregisztereknek felel meg. A rendszerben számos aktív folyamat található, viszont általában – az egyetlen CPU-nak megfelelően – csak egy hardverregiszter-készlet létezik. A kernel az aktív, futó folyamat regisztereit tartja a hardverregiszterekben, a többi folyamat regiszterkészletének tartalmát elmenti folyamatonkénti adatszerkezetekbe.

A kernel tehát az a speciális program, ami közvetlenül a hardveren fut, és a kernel valósítja meg több más rendszer szolgáltatással egyetemben a folyamat modellt.

5.3.2.1. Végrehajtási módok és környezetek

A UNIX futtatásához olyan hardverre van szükségünk, ami legalább két vég­re­hajtási módot (execution mode) biztosít: egy privilegizált kernel módot, és egy felhasználói (user) módot. A kernel a címtér egy részét védi felhasználói módú hozzáféréssel szemben, valamint bizonyos privilegizált utasítások csak kernel módban adhatók ki. Ezek tipikusan memóriakezelő, illetve B/K-kezelőutasítások.

Ma már szinte minden általános célú UNIX-változat alkalmaz virtuális me­mó­riakezelést (virtual memory). Ekkor a folyamatok a virtuális címtartományban adnak ki címeket és a rendszer címleképzési táblázatokkal futási időben köti ezekhez a virtuális címekhez a valós fizikai címeket. Minden folyamat virtuális címtartományának egy rögzített része a kernel fizikai címtartományára képződik le, ahol a kernel kódja és adatszerkezetei találhatók. Ezt a kernel területet (kernel area) csak kernel módban lehet elérni. A folyamatok közvetlenül nem, csak rendszerhívásokkal tudják elérni a kernelt.

Meg kell említeni két fontos folyamatonkénti adatszerkezetet, amiket bár a kernel kezel, gyakran a folyamat címterében implementálnak. Ezek az u-terület (u area) és a kernelverem (kernel stack). Az u-terület a kernel számára fontos információkat tárol a folyamatról, mint például a megnyitott állományok táblája, azonosítók, a regiszterek elmentett tartalma, ha a folyamat nem fut stb. Ezen információkat a későbbiekben részletesebben tárgyaljuk. Bár az u-terület a folyamat címterében található, ahhoz csak kernel módban lehet hozzáférni, annak tartalmát a folyamat maga önkényesen nem módosíthatja.

A végrehajtási környezet (execution context) a folyamat szempontjából nagy jelentőséggel bír. A kernel részek végrehajtódhatnak folyamat vagy kernel környezetben (process, kernel context). Folyamat környezetben a kernel az adott folyamat számára hajt végre valamilyen feladatot (például egy rendszerhívás során). Ekkor a kernel hozzáfér a folyamat címteréhez, u-területéhez és a kernel verméhez. Sőt, a kernel folyamat környezetben blokkolhatja is az aktuális folyamatot, ha a végrehajtás során valamilyen erőforrásra vagy eseményre kell várakoznia.

A kernelnek bizonyos rendszer szintű feladatokat is végre kell hajtania, amiket nem kifejezetten egy adott folyamat számára hajt végre, ezeket rendszerkörnyezetben hajtja végre. Tipikus rendszerkörnyezetben végrehajtott feladatok a külső megszakítások kezelése, a prioritások újraszámítása stb. Rendszerkörnyezetben a kernel nem fér hozzá közvetlenül az aktuális folyamat címteréhez, u-területéhez vagy kernel verméhez. Meg kell jegyezni, hogy bizonyos speciális indirekt leképzések segítségével a kernel ekkor is elérheti az aktuális folyamat címterét. Rendszerkörnyezetben a kernel nem blokkolódhat, mert ekkor ezzel egy „ártatlan” folyamatot blokkolna. Az 5.3. ábrában a mód és a környezet tengelyek négy negyedre osztják az ábrát. Az egyes negyedekbe beírtuk az adott állapotban elvégezhető műveleteket.

5.3. ábra. ábra - Végrehajtási mód és környezet

Végrehajtási mód és környezet


5.3.2.2. A folyamat absztrakció – a folyamatok állapotai és az állapotátmeneti gráf

A folyamatokat gyakran úgy definiálják, hogy „A folyamat egy végrehajtás alatt álló program.” A UNIX-rendszerrel kapcsolatban talán szerencsésebb, ha úgy fogalmazunk, hogy a folyamat egy olyan entitás, ami egyrészt futtat egy programot, másrészt biztosítja a futáshoz szükséges végrehajtási környezetet.

A UNIX folyamatai jól definiált hierarchiát alkotnak. Minden folyamatnak pontosan egy szülője (parent) van (aki mint azt majd a későbbiekben látjuk, fork rendszerhívással hozza létre gyermekét), és egy vagy több gyermek folyamata (child process) lehet. A folyamat hierarchia tetején az init folyamat helyezkedik el. Az init folyamat az első létrehozott felhasználói folyamat, a rendszer indulásakor jön létre. Minden felhasználói folyamat az init folyamat leszármazottja. Néhány rendszer folyamat, mint például a swapper és a pagedaemon (a háttértár kezelésével kapcsolatos folyamatok), szintén a rendszer indulásakor jön létre és nem az init folyamat leszármazottja. Ha egy folyamat befejeződésekor még léteznek aktív gyermek folyamatai, akkor azok árvákká (orphan) válnak és azokat az init folyamat örökli.

A UNIX folyamatai minden időpillanatban egy jól definiált állapotban találhatók. Ezeket az állapotokat és a közöttük lehetséges állapotátmeneteket egy állapotátmeneti gráffal lehet szemléletesen ábrázolni. Az 5.4. ábra ezt a gráfot mutatja.

5.4. ábra. ábra - A folyamatok állapotátmeneti gráfja

A folyamatok állapotátmeneti gráfja


Mint azt korábban láttuk, új folyamatot a fork rendszerhívással lehet létrehozni, amelynek hatására a folyamat kezdeti állapotba kerül. Itt végrehajtódnak a legfontosabb inicializálások, majd a fork lefutása után a folyamat készen áll a futásra, már csak a processzorra van szüksége. Ezt az állapotot jelöli a futásra kész (ready) állapot. Innen az ütemezés hatására egy környezetváltással (context switch) (swtch rendszerhívás) kernel fut (kernel running) állapotba kerül. Egy frissen létrejött folyamat a rendszerhívás befejeződése után átlép user fut (user running) állapotba. Egy user módban futó folyamat egy rendszerhívás vagy egy megszakítás hatására léphet át kernel fut állapotba, ahonnan a rendszerhívásból vagy a megszakításból való visszatérés után léphet vissza a user fut állapotba. Az 5.4. ábrán a további állapotátmenetek: amikor egy folyamat befejezi futását és végrehajtja az exit rendszerhívást, átlép zombi (zombie) állapotba. A zombi állapotban a folyamat már felszabadította a foglalt memóriát, lezárta az állományokat, minden erőforrását visszaadta a rendszernek, csak a proc struktúráját tartja fogva, amiben visszatérési és statisztikai információkat tárol a szülő számára. A szülő wait rendszerhívásának hatására a folyamat véglegesen kilép az állapot átmenet gráfból, felszabadul a proc struktúra is, a folyamat teljesen megszűnik létezni.

Amikor egy folyamatnak valamilyen erőforrásra kell várakoznia, akkor kiad egy sleep rendszerhívást és alvó állapotba megy. Az alvó állapotból a várt esemény bekövetkezése által kiváltott wakeup rendszerhívás hatására a folyamat átlép a futásra kész állapotba és várja, hogy az ütemező ismét futásra ütemezze. Az 5.4. ábra alján a bekeretezett két állapotot először a 4BSD vezette be, majd később a SVR4 is átvette. Egy alvó folyamat egy stop jelzés hatására átlép a felfüggesztve alszik (stopped + asleep) állapotba. (A stop jelzés különlegessége, hogy azt a rendszer a többi jelzéssel ellentétben azonnal kezeli. A jelzések kezelésével részletesebben az 5.3.4. rész foglalkozik.) Ebből az állapotból a continue jelzés hatására a folyamat visszalép az alvó állapotba. Ha a felfüggesztve alszik állapotban következik be egy wakeup rendszerhívás, akkor a folyamat átlép a felfüggesztve futásra kész állapotba, ahonnan egy continue jelzés hatására kerül át a futásra kész állapotba.

5.3.2.3. Folyamatok környezete (kontextus)

Mint azt korábban láttuk, a folyamat absztrakció egy végrehajtási környezetet biztosít. Ennek a környezetnek tartalmaznia kell a folyamatok leírásához szükséges összes információt. Ezek az alábbi főbb részekből állnak:

  • felhasználói (user) címtér,

  • vezérlési információk:

    • u-terület,

    • proc struktúra (folyamattábla bejegyzés),

  • hitelesítők (credentials), többek között a felhasználó és csoport azonosítók),

  • környezetváltozók,

  • hardverkontextus (program számláló, veremmutató, a processzor állapota, memóriakezelő, regiszterek, lebegőpontos egység regiszterei stb.).

A hardver regiszterei mindig a végrehajtás alatt álló aktuális folyamat környezetét tárolják. Környezetváltáskor ezen regiszterek tartalmát az operációs rendszer elmenti az aktuális folyamat u-területére. Az ütemező által kiválasztott új folyamat környezetét a kernel betölti a regiszterekbe, és az új folyamat folytathatja a futását.

A továbbiakban fontosságuk miatt részletesebben ismertetjük a hitelesítőket és megadjuk az u-területen és a proc struktúrában tárolt főbb információkat.

Hitelesítők (credentials)

A UNIX-rendszerben minden felhasználót egy egyedi azonosító, a felhasz­ná­ló­azonosító (UID) azonosít. Ezen felül minden felhasználó egy vagy több csoportba tartozik, amiket szintén egyedi azonosítók, a csoportazonosítók (GID) azonosítanak. Minden rendszerben van egy kitüntetett felhasználó, a superuser, aki kitüntetett jogosultságokkal rendelkezik a rendszerben. A su­per­user UID-je 0, GID-je 1. Meg kell jegyezni, hogy a modern UNIX-rendsze­rek fejlett biztonsági megoldásokat nyújtanak, ahol a privilégiumokat összefogva kezelő superuser absztrakció helyett műveletenkénti privilégiumkezelés valósul meg.

Az azonosítókból minden folyamat egy párral rendelkezik: a valódi (real) és az effektív (effective) azonosítókkal. Az effektív azonosítók (UID, GID) az állománykezelésben, míg a valódi azonosítók a jelzések kezelésében töltenek be meghatározó szerepet. Az operációs rendszer ki is használja ezt a kettősséget. Amikor egy folyamat az exec rendszerhívással futtat egy programot, aminek a suid bitje be van állítva, akkor a kernel a folyamat effektív UID-jét átállítja a végrehajtható állomány tulajdonosának az azonosítójára. Hasonlóan, ha a program sgid bitje be van állítva, akkor a kernel a folyamat effektív GID-jét átállítja a végrehajtható állomány tulajdonosának az azonosítójára. Ezen a mechanizmuson keresztül a UNIX különleges jogosultságokat tud biztosítani a felhasználóknak bizonyos feladatok végrehajtásához. A mechanizmus alkalmazásának egy gyakran idézett példája a passwd program, amivel a felhasználó megváltoztathatja a jelszavát. A jelszó egy, a rendszer tulajdonában lévő jelszó-adatbázisban található, amit a felhasználók közvetlenül nem módosíthatnak. A passwd program tulajdonosa a superuser és a suid bitje be van állítva. Így amikor a felhasználó a programot futtatja, hogy megváltoztassa a jelszavát, akkor állománykezelés szempontjából superuseri jogosultságokat kap, így elvégezheti a megfelelő módosítást.

Ezenfelül még a setuid és a setgid rendszerhívásokkal lehet az azonosítókat módosítani. A felhasználók ezekkel a rendszerhívásokkal az effektív azonosítóikat visszaállíthatják a valódi azonosítóikra, míg a superuser mind az effektív, mind pedig a valós azonosítókat megváltoztathatja.

Az u-terület és a proc struktúra

A folyamatokhoz kapcsolódó vezérlési információkat két folyamatonkénti adatszerkezet az u-terület és a proc struktúra tárolja. Korábbi implementációkban a kernel egy rögzített méretű proc struktúrákból álló tömböt, egy úgynevezett folyamattáblát (process table) tartalmazott. A folyamattábla mérete meghatározta a rendszerben az egyidejűleg létező folyamatok maximális számát. A későbbi implementációk ezt a merev szerkezetet leváltották egy dinamikus allokációs sémával: a kernel szükség esetén újabb proc struktúrákat tud allokálni. Egy nagyon lényeges különbség van a proc struktúra és az u-terület között: míg a proc struktúra rendszerterületen található, addig az u-terület a folyamat címterének része (bár a kernel felügyelete alatt áll). Ebből adódóan a kernel az összes (nem csak a futó) folyamat proc struktúrájához hozzáfér, míg csak a futó folyamat u-területét éri el (indirekt mechanizmusokon keresztül elérheti a többi folyamat u-területét is, azonban ez lassabb hozzáférést biztosít). Ebből adódóan a UNIX-rendszerek evolúciója során hatékonysági okok miatt bizonyos korábban az u-területen tárolt (többek között az ütemezéssel és a jelzéskezeléssel kapcsolatos) információkat áthelyeztek a proc struktúrába. Az alábbiakban megadjuk az u-területen és a proc struktúrában tárolt leglényegesebb információkat.

Az u-területen tárolt főbb információk

  • PCB (Process Control Block) ® hardverkörnyezet,

  • mutató a folyamattábla bejegyzésre (proc struktúrára),

  • valós és effektív UID, GID,

  • argumentumok, visszaadott értékek, hibaérték az aktuális rendszerhívásból,

  • jelzéskezelők,

  • program-fejlécinformációk (kód-, adat- és veremméret stb.),

  • folyamatonkénti állományleíró tábla (nyitott állományokról),

  • mutató az aktuális könyvtár és a vezérlő terminál v-node-jára,

  • CPU használati statisztikák, diszkkvóta, erőforrás-korlátok,

  • folyamat kernelverme.

A proc struktúrában tárolt főbb információk

  • PID, PGID, SID (munkamenet-azonosító),

  • kernel címleképzési térkép az u-területhez,

  • az aktuális folyamatállapot,

  • mutatók az ütemezési (alvás esetén az alvó) sorokba,

  • ütemezési prioritás és információk,

  • jelzéssel kapcsolatos információk (például maszk),

  • memóriakezelési információk,

  • mutatók az aktív, szabad, illetve zombi folyamat sorokra,

  • egyéb jelzőbitek,

  • hash mutatók,

  • hierarchiainformációk (folyamatok közötti kapcsolatról).

5.3.2.4. Folyamatok létrehozása

A UNIX-ban új folyamatok létrehozására a fork rendszerhívás szolgál. A létrejött folyamat majdnem teljes mása a szülő folyamatnak, csak a megkülönböztetésükhöz szükséges adatokban (folyamat azonosító) térnek el. A fork rendszerhívás az alábbi főbb feladatokat hajtja végre:

  • háttértár (swap) területfoglalás a folyamat számára,

  • PID generálás a gyermekfolyamat számára,

  • proc struktúra foglalás és inicializálás,

  • címleképzés táblák allokálása,

  • u-terület frissítése, hogy az már az új címleképzési táblát tükrözze,

  • osztottan használt kódtartomány megfelelő kezelése,

  • szülő verem- és adattartományainak duplikálása,

  • referenciák begyűjtése osztottan használt erőforrásokra (nyitott állományok stb.),

  • hardver kontextus inicializálása szülőtől másolva,

  • a folyamat futásra késszé tétele, illetve a megfelelő ütemezési sorba helyezése,

  • a gyermeknek 0, a szülőnek a gyermek PID-jének, mint visszatérési értéknek a visszaadása.

5.3.2.5. Folyamatok befejezése (terminálás)

Egy folyamat kétféle okból fejeződhet be (terminálódhat). Ha elvégezte a feladatát, működését normál módon fejezte be. Ekkor a folyamat maga adja ki az exit rendszerhívást, ami az exit() függvényt meghíva terminálja a folyamatot. Egy folyamat egy jelzés hatására is befejezheti a futását. Az ilyen „rendellenes” terminálás során az operációs rendszer hívja meg az exit() függvényt a folyamat megszüntetése céljából. Az alábbiakban vázlatosan ismertetjük az exit() függvény által elvégzendő feladatokat.

  • a jelzések „kikapcsolása”,

  • a nyitott állományok lezárása,

  • a text állomány és más erőforrások, mint például az aktuális könyvtár felszabadítása,

  • a megfelelő információk beírása a statisztika naplóba (log),

  • az erőforrás használati statisztikák és a kilépési státus elmentése a proc struktúrába,

  • átlépés zombi állapotba és a folyamat a zombi listára kerül,

  • amennyiben a folyamatnak még léteznek élő gyermekei, azokat az init folyamat örökli,

  • a címtér, a foglalt területek, táblák, címtérképek, a háttértár (swap) terület felszabadítása,

  • SIGCHLD jelzés küldés a szülőnek (amely általában figyelmen kívül hagyja azt),

  • a szülő felébresztése, amennyiben az alszik,

  • swtch() rendszerhívással átütemezés kezdeményezése.

Ezek után a folyamat már csak egy folyamattábla-bejegyzést foglal. Ezt a folyamat állapotot nevezik zombi állapotnak. A szülő feladata, hogy a statisztikai információk begyűjtése után ezt a fennmaradó memóriadarabot felszabadítsa. Tipikusan a szülő wait() rendszerhívással megvárhatja a gyermek terminálását és felszabadíthatja ezt az utolsó erőforrást is.

5.3.3. Ütemezés

A CPU-ütemező, illetve az ütemezési algoritmus minden multiprog­ra­mo­zott operációs rendszer lelke. A rendszer teljesítménye, illetve a hardver ki­­hasz­náltsága szempontjából az egyik legfontosabb, ha nem a legfontosabb tényező a megfelelően kiválasztott és a körültekintően paraméterezett ütemezési algoritmus.

Ebben a részben ismertetjük a tradicionálisnak tekintett UNIX ütemezési algoritmust, amit az SVR3, illetve 3.1BSD UNIX-rendszerek alkalmaztak. Az ismertetetésre kerülő ütemezési algoritmust a UNIX-rendszerekben használt ütemezés tipikus példájának tekinthetjük, annak ellenére, hogy a ma hasz­nált UNIX-rendszerek az algoritmus valamilyen továbbfejlesztett változatát használják.

Mint látni fogjuk, a UNIX-ban használt ütemezés meglehetősen összetett. Az ismertetésre kerülő ütemezési algoritmus kiválasztásával az volt a célunk, hogy a UNIX-rendszerek ütemezőiben használt minél több ötletet bemutathassunk.

5.3.3.1. Az ütemezési algoritmussal szemben támasztott követelmények

A UNIX-rendszert elsősorban többfelhasználós, interaktív és batch programokat egyaránt futtató felhasználói környezetre tervezték. Az ütemezési algoritmussal szemben támasztott követelményeket a következőkben foglalhatjuk össze:

  • alacsony válaszidő biztosítása az interaktív folyamatok támogatásának érdekében,

  • nagy átbocsátó képesség biztosítása,

  • az alacsony prioritású, háttérben futó folyamatok éhezésének elkerülése.

A fenti követelményeket még kiegészíthetjük az ütemezőkkel szemben támasztott általános kritériumokkal:

  • a rendszer terhelését figyelembe vevő ütemezés, mely a terhelés növekedésével nem hirtelen omlik össze, hanem lehetőséget ad beavatkozásra,

  • a felhasználónak legyen lehetősége a folyamatok futási esélyeinek befolyásolására.

A UNIX ütemezési algoritmusa a fenti követelmények megvalósítása jegyében született, azonban néhány ponton a fenti követelmények egymásnak ellentmondó igényeket képviselnek, így – mint látni fogjuk – az algoritmus nem mindegyik követelményt elégíti ki maradéktalanul.

5.3.3.2. A UNIX-ütemezés rövid jellemzése

A UNIX ütemezése prioritásos. A rendszer minden egyes folyamathoz hozzárendel egy, az időben dinamikusan változó prioritást. Az ütemezés felhasználói, illetve kernel módban eltér egymástól:

  • A felhasználói módban futó folyamatok ütemezése: preemptív ütemezés, időosztásos, időben változó prioritású folyamatok, azonos prioritású folyamatok esetén körforgásos (Round–Robin), FCFS (First Come First Served: érkezési sorrend szerinti kiszolgálás).

  • A kernel módban futó folyamatok ütemezése: nem preemptív ütemezés, rögzített prioritású folyamatok.

A kernel módban az ütemezés szigorúan nem preemptív. Kernel kódot végrehajtó folyamatot (például rendszerhívás, megszakítás-kezelés) nem lehet kényszeríteni, hogy lemondjon a CPU használatról egy nagyobb prioritású folyamat javára. Újraütemezés akkor következik be, amikor a folyamat önként lemond a futás jogáról (sleep rendszerhívást hajt végre), illetve, amikor a folyamat visszatér kernel módból felhasználói módba.

Megjegyzendő, hogy a kernel kód újrahívható, vagyis egyszerre több példányban is végrehajtódhat. (Például, ha egy kernel módban futó folyamat lemond a futás jogáról, vagyis egy sleep rendszerhívást hajt végre, más folyamat rendszerhívása miatt ugyanaz a kernel eljárás újra elindulhat.)

Annak oka, hogy a kernel futása során az ütemezés nem preemptív, egyszerűen az, hogy az operációs rendszer számos olyan adatszerkezetet használ, amit nem lehet egy lépésben megváltoztatni. Ha egy ilyen adatszerkezet változtatása közben vennék el a futás jogát egy kernel módban futó folyamattól, az nem konzisztens állapotban hagyná az operációs rendszer adatszerkezeteit, vagy pedig tele kellene tűzdelni szinkronizációs műveletekkel a kölcsönös kizárás biztosítása érdekében.

Egy ilyen szituációt szemléltet az 5.5. ábra, ami egy kétirányban láncolt lista listaelemének lefűzését mutatja. Tegyük fel például, hogy a kernel a szabad memórialapok láncolt listájából szeretne egy elemet kivenni. A probléma abból adódik, hogy a listaelemet nem lehet egy lépésben lefűzni a láncból. A lefűzési lépések köztes állapotát (amikor a második elem lefűzése közben az egyik irány mutatói már megváltoztak) illusztrálja az 5.6. ábra. Ha a folyamattól el lehetne venni a vezérlést miközben az a listán dolgozik, a következő folyamat a lista végéről keresve eggyel kevesebb memórialapot látna, mint elölről indulva, vagyis a kernel adatai nem lennének konzisztens állapotban.

5.5. ábra. ábra - Láncolt lista egy közbülső elem lefűzése előtt

Láncolt lista egy közbülső elem lefűzése előtt


5.6. ábra. ábra - Láncolt lista egy közbülső elem lefűzése közben

Láncolt lista egy közbülső elem lefűzése közben


5.3.3.3. Folyamatok ütemezési prioritása

A UNIX-ban a folyamatok prioritását 0-127 közötti egész számok jelölik. (Némelyik UNIX-változatban ettől eltérő prioritási tartományt használnak.) A nullás prioritás jelöli a legnagyobb prioritást, vagyis a kisebb prioritási érték nagyobb prioritáshoz tartozik.

A rendszer a felhasználói és a kernel módban futó folyamatok prioritását eltérő módon kezeli. A prioritási értékeket két prioritási tartományra osztja amint azt a következő, 5.7. ábra mutatja. Az 50 fölötti prioritási értékeket felhasználói módban futó folyamatokhoz rendeli a rendszer, míg az 50 alatti prioritások kernel módú folyamatokhoz tartoznak.

5.8.ábra. táblázat - Az óramegszakításhoz kötődő ütemezési tevékenységek

0

Legnagyobb prioritás

} KERNEL-prioritások

·

 

·

 

·

 

49

 

50

 

} FELHASZNÁLÓI prioritások

·

 

·

 

·

 

127

Legkisebb prioritás


Prioritás meghatározása kernel módban

A kernel módban futó folyamat prioritása statikus, nem függ attól, hogy a folyamat mennyit használta a CPU-t, vagyis mennyi ideig futott. A prioritás attól függ, hogy a folyamat milyen ok miatt hajtott végre sleep rendszerhívást, vagyis, hogy milyen eseményre várakozik. Emiatt a kernel prioritást szokták alvási prioritásnak is nevezni.

Jogos a kérdés, hogy mi alapján határozza meg a rendszer annak a kernel módban futó folyamatnak a prioritását, amelyik nem hajtott még végre sleep rendszerhívást mióta kernel módba került. A válasz nagyon egyszerű. A rendszer a folyamatok prioritását az ütemezés, vagyis az ütemező folyamat futása alkalmával vizsgálja. Mivel kernel módban a UNIX nem preemptív, ütemezésre csak akkor kerülhet sor, ha a futó folyamat végrehajt egy sleep rendszerhívást. A sleep rendszerhívás végrehajtása után viszont meghatározható a kernel módú prioritás.

Vizsgáljuk meg egy kicsit részletesebben is a kernel prioritás generálását. Hogyan kerülhet egy folyamat kernel módba? Két lehetőség van: vagy rendszerhívást hajt végre (vagyis implicit módon egy trap utasítást), vagy külső megszakítás kiszolgálása történik.

Ha rendszerhívás történik, a kernel módú futást felhasználói módú futás előzte meg, amikor is a folyamat prioritása adott. Ezt az értéket – mint majd látni fogjuk – a rendszer későbbi használatra elmenti. Ebben a pillanatban a folyamat kernel módú prioritása – mint láttuk – elvileg nem határozható meg, de ez nem okoz problémát.

Megszakítás esetén a rendszer nem ütemezi át a folyamatokat, a megszakítási rutin az éppen futó folyamat környezetében hajtódik végre. A megszakítási rutint az operációs rendszer úgy tekinti, mintha az éppen futó (vagyis a megszakított) folyamat futna tovább. (Ennek következtében minden megszakítási rutin által felhasznált idő a megszakított folyamat időkvótáját terheli.) Ütemezésre csak a megszakítás kiszolgálása után kerülhet sor, hiszen a megszakítási rutin kernel módban hajtódik végre. Ha a megszakított folyamat eredetileg is kernel módban futott, a rendszer nem tér vissza felhasználói módba, vagyis az ütemezőnek megint csak nincs lehetősége futni. Ha a megszakított folyamat felhasználói módban futott, akkor a visszatérés után a megszakított folyamat felhasználói módú prioritása él tovább. Láthatjuk tehát, hogy megszakítás kiszolgálása esetén, bár kernel módú futás történik, a rendszernek nincs szüksége kernel módú prioritás számolására. (Megjegyezzük, hogy az ütemezés kritikus szakaszaiban, amikor például éppen nincs futásra kijelölt folyamat és a környezet is indefinit, a megszakítások tiltva vannak.)

Folyamatok prioritásának meghatározása felhasználói módban

Felhasználói módban a prioritást egy adott pillanatban két dolog határozza meg:

  • a felhasználó által adott külső prioritás (nice szám, kedvezési szám),

  • a folyamat korábbi CPU használata.

A nice szám a felhasználó által meghatározható érték, amivel kifejezheti, hogy mennyire fontos az általa indított folyamat. Minél kisebb egy folyamat nice száma, annál fontosabb a folyamat, vagyis annál nagyobb lesz a prioritása a futás során.

A prioritás számításához a UNIX a következő négy paramétert használja:

  • p_pri: aktuális ütemezési prioritás,

  • p_usrpri: felhasználói módban érvényes prioritás,

  • p_cpu: a CPU használat mértékére vonatkozó szám,

  • p_nice: a felhasználó által futás elején adott nice szám.

Az operációs rendszer a fenti paramétereket minden folyamat esetén külön-külön számon tartja.

Az ütemező a p_pri paraméterben tárolja a folyamat aktuális prioritását, tehát ez alapján választja ki, hogy melyik folyamatot ütemezze futásra. Amikor a folyamat felhasználói módban fut, akkor a p_pri megegyezik a p_usrprivel. Kernel módba váltásnál a p_pri paraméter megkapja a kernel módban érvényes prioritás értékét, míg a p_usrpri értéke nem változik, sőt a rendszer továbbra is karbantartja a p_usrpri értékét az ütemezési algoritmus szerint. Amikor visszatér felhasználói módba, a rendszer a p_pri értékét a p_usrpriből frissíti.

Amikor egy folyamat felébred egy sleep hívás után, akkor a kernel módú prioritása lesz érvényes, ami, mint láttuk, mindig magasabb, mint a felhasználói módú folyamatok prioritása. A rendszer így biztosítja a kernel módú folyamatok preferenciáját.

A p_cpu paraméter a folyamat CPU használatára jellemző érték. A folyamat p_cpu paramétere a folyamat indításakor nulla értékre áll. A folyamatok p_cpu értékének módosításai az óra-megszakításhoz kapcsolódnak a következők szerint (5.8. ábra):

  • p_cput minden óramegszakítás alkalmával emeli a kiszolgáló rutin a futó folyamatnál:

p_cpu := p_cpu +1,

  • ha több azonos felhasználói prioritású folyamat van a rendszerben az aktuálisan legmagasabb prioritási szinten, minden tizedik megszakításnál lefut a Round–Robin-algoritmus, vagyis az ütemező az azonos prioritású folyamatok között forgatja a végrehajtás jogát,

  • minden századik megszakításnál az ütemező újraszámolja minden folyamat felhasználói prioritását a következő három lépésben:

    – korrekciós faktor (KF) számítása:

    KF: = 2*futásra kész folyamatok száma/(2* futásra kész folyamatok száma+1)

    – minden folyamat CPU használatára jellemző változó kiszámítása:

p_cpu = p_cpu * KF

– felhasználói prioritás kiszámolása:

p_usrpri = P_USER+p_cpu/4+2*p_nice,

ahol P_USER egy alkalmas konstans.

A fenti képletben szereplő P_USER egy konstans. Arra szolgál, hogy a p_usrpri változó, vagyis a folyamat felhasználói prioritása, ne hagyja el a felhasználói prioritási tartományt. (A P_USER értéke a legkisebb felhasználói prioritás értékével egyezik meg, vagyis példánkban P_USER = 50.)

5.10.ábra. táblázat - Ütemezési példa

 

Futó folyamat

Minden folyamat

Minden óramegszakítás

p_cpu := p_cpu +1

Megvizsgálja, van-e a futónál magasabb prioritású folyamat. Ha van, újraütemez.

Minden 10. óramegszakítás

Round-Robin algoritmus: ha több azonos prioritás-osztályú folyamat van a legmagasabb prioritású pozícióban, 10 óra-megszakításonként váltja a futó folyamatot

Minden 100. óramegszakítás

 

korrekciós faktor számítása

p_cpu = p_cpu * KF

p_usrpri = P_USER+p_cpu/4+2*p_nice


A KF korrekciós faktor számításával a rendszer terhelését igyekszik figyelembe venni az ütemező. Ha megvizsgáljuk a korrekciós faktor viselkedését, láthatjuk, hogy a korrekciós faktor értéke annál inkább egyhez tart, minél több futásra kész folyamat volt a rendszerben az elmúlt ütemezési periódusban (elmúlt 100 óramegszakítás ideje alatt), vagyis minél nagyobb volt a rendszer terheltsége: 1 futásra kész folyamatnál ez a szám 2/3; 2 folyamatnál 4/5, 10 folyamatnál 10/11 stb. Megjegyezzük, hogy számos UNIX-rendszer a korrekciós faktor értékét konstansnak (1) veszi.

Nagyon fontos kiemelni, hogy az ütemezési algoritmus, illetve a hozzá kötődő tevékenységek nem közvetlenül a megszakítási rutinban hajtódnak végre, hiszen ekkor feleslegesen hosszú időt töltene a rendszer a megszakítás kiszolgálásával. Az ütemezéshez kötődő rutinokat – hasonlóan más ciklikusan végrehajtandó rendszerfeladatokhoz – a call-out mechanizmus segítségével hajtja végre a rendszer. Erről a későbbiekben még részletesen szó lesz.

Másik ide tartozó megjegyzés, hogy a fent említett, óra-megszakításokhoz kötődő három tevékenység gyakorisága változhat az egyes UNIX-rendszerekben. A fent szereplő 10-es, illetve 100-as számok tipikus értékek.

5.3.3.4. Környezetváltás ütemezéskor

Az ütemezési algoritmus ismeretében tanulságos végignézni, hogy milyen esetekben történik környezetváltás a UNIX-ban, vagyis milyen események hatására kerül át a CPU-használat joga – az ütemező közreműködésével – az egyik folyamattól a másik folyamathoz. Környezetváltás a következő esetekben történik:

  • Nem preemptív ütemezés

    – Egy folyamatnak várnia kell valamilyen eseményre (sleep rendszerhívást hajt végre).

    Egy folyamat befejeződik (exit rendszerhívást hajt végre).

  • Preemptív ütemezés

    A 100-adik óraciklusban a prioritások újraszámításakor az egyik folyamat prioritása nagyobb lesz, mint a futó folyamat prioritása. Ekkor prioritásvizsgálat után új folyamatot futtat a rendszer, tehát környezetváltás szükséges.

    A 10-edik óraciklus esetén a Round–Robin-algoritmus egy másik, azonos prioritású folyamatot választ futásra.

    Egy futó folyamat, vagy megszakítási rutin működésének eredményeképpen felébred (ready to run állapotba jut) egy, az aktuálisan futónál magasabb prioritású, eddig várakozó folyamat.

5.3.3.5. Adatszerkezetek a folyamatok prioritásának tárolására

Az időben változó prioritások tárolására a rendszer dinamikus adatszerkezetet használ. Az azonos prioritású, futásra kész folyamatok láncolt listán tárolódnak. Az adott prioritású folyamatok keresésének megkönnyítése érdekében a listafejeket egy hashtáblázatban tárolja a UNIX. Egy listafejhez négy egymás után következő prioritásértékkel rendelkező folyamat tartozik. A hashtáblás ábrázolást mutatja be az 5.9. ábra.

5.9. ábra. ábra - A folyamatok prioritásának tárolása

A folyamatok prioritásának tárolása


A fenti megoldás nemcsak azért előnyös, mert csökkenti a hashtábla bejegyzéseinek számát, hanem lehetővé teszi adott prioritású folyamatok létezésének ellenőrzését is. A rendszer minden sorhoz hozzárendel egy jelzőbitet. A jelzőbit értéke mutatja, hogy az adott sorban létezik-e futásra kész folyamat. Ezeket a biteket a listába történő beszúrás, illetve lefűzés alkalmával frissíti a rendszer. Az ellenőrzés gyorsítása azért fontos, mert nagy gyakorisággal (minden óramegszakítás esetén) lefut, tehát ennek a tevékenységnek az ideje a rendszer teljesítményét nagymértékben befolyásolja.

A négy prioritási szint egyetlen hashtábla-bejegyzésbe történő összevonása azért előnyös, mert így pontosan 32 jelzőbit lesz, amit egy memóriaszóba összevonva egyszerű kezelni a 32 bites rendszerekben. (A jelzőbiteket tartalmazó változó neve: whichqs.)

5.3.3.6. Példa az ütemezés számolására

A következőkben egy konkrét példán keresztül mutatjuk be a prioritás számolását. Legyen a korrekciós tényező értéke 1/2, és ne változzon az ütemezés alatt. (Ez egyébként több UNIX-rendszerben is hasonlóan van.)

Tekintsünk el a Round–Robin-algoritmus használatától. Válasszuk a nice számot minden folyamatnál 0-nak.

Esetünkben tehát az ütemező algoritmus tevékenységei:

  • minden óra-megszakításnál emeli a futó folyamat p_cpu értékét:

p_cpu := p_cpu +1

  • minden 100-adik óra-megszakításnál újraszámolja minden folyamat felhasználói prioritását a következő két lépésben:

    kiszámítja a minden folyamat CPU használatára jellemző változó, (p_cpu) értékét:

p_cpu = p_cpu * KF = p_cpu * 1

kiszámítja a felhasználói prioritás értékét:

p_usrpri = P_USER+p_cpu/4+2*p_nice = 50 + p_cpu/4

Minden folyamatnak négy, ütemezésnél használt paraméterét (p_pri, p_usrpri, p_cpu, p_nice) tartja számon a rendszer, azonban esetünkben csak kettő (p_pri, p_cpu) érdekes, mivel a p_nice szám zéró, a p_pri értéke pedig megegyezik a p_usrpri értékével, hiszen csak felhasználói módú futásról van szó. A számításokat az 5.10. ábrán látható táblázatban foglaltuk össze.

Láthatjuk, hogy mindegyik folyamat futási lehetőséghez jutott a vizsgált periódus alatt. A várakozó folyamatok prioritása a várakozási idő növekedésével folyamatosan növekedett, míg el nem érték a lehető legmagasabb prioritási szintet. A futó folyamat prioritása a futási idővel arányosan csökent. Az ütemező így előzi meg a folyamatok éheztetését.

5.3.3.7. A UNIX-ütemezés értékelése

A UNIX ütemezése viszonylag jó rendszerkihasználást és jó áteresztőképességet biztosít a felhasználók számára átlagos, vagyis nem szélsőséges rendszerterhelés esetén. Az utóbbi években azonban a felhasználók igényei megemelkedtek az ütemezővel szemben, nem utolsósorban azért, mert meg­jelentek a UNIX-nál nagyobb hatékonyságot és több lehetőséget biztosító rendszerek.

5.13.ábra. táblázat - Jelzések

A

B

C

 

p_pri

p_cpu

p_pri

p_cpu

p_pri

p_cpu

Lépés

Futó folyamat

50

0

50

0

50

0

1

A

50

1

50

0

50

0

2

A

A

50

99

50

0

50

0

99

A

50+50/4

63

100/2

50

50

0

50

0

100

A

63

50

50

1

50

0

101

B

….

B

63

50

50

99

50

0

199

B

50+25/4

56

50/2

25

50+50/4

63

100/2

50

50

0

200

B

56

25

63

50

50

1

201

C

….

C

56

25

63

50

50

100

299

C

50+13/4

53

25/2

13

50+25/4

56

50/2

25

50+50/4

63

100/2

50

300

C


Az ütemezés értékelésénél így elsősorban az algoritmus negatívumait emeljük ki:

  • Nem méretezhető megfelelően. Az alkalmazott algoritmus a folyamatok számának emelkedése esetén nem tud rugalmasan alkalmazkodni, vagyis változni a terhelés növekedésével. A korrekciós faktor használata nem elég hatékony eszköz.

  • Az algoritmussal nem lehet meghatározott CPU-időt allokálni egy adott folyamat, illetve a folyamatok egy csoportja számára, vagyis nem lehet a CPU-t adott esetben „kiosztani”.

  • Nem lehet a folyamatok fix válaszidejét garantálni. Bár az algoritmus igyekszik minél alacsonyabb válaszidőt biztosítani, de nagy rendszerterhelés esetén ez limit nélkül megnőhet, vagyis nem lehet garantált válaszidőről beszélni. Emiatt a UNIX-ütemezést nem lehet valósidejű (real-time) rendszerben alkalmazni. Ezt a hiányosságot számos rendszerben (SVR4, Digital UNIX stb.) megpróbálták kiküszöbölni.

  • Az előző hiányossággal rokon probléma, de érdemes külön is kiemelni, hogy ha egy kernel rutin sokáig fut, az feltartja az egész rendszert, mi­vel a kernel nem preemptív.

  • A felhasználó a folyamatainak prioritását nem tudja megfelelő módon befolyásolni. A gyakorlatban a nice szám nem elég hatásos eszköz erre a célra.

5.3.3.8. Call-out

A call-out mechanizmus arra szolgál, hogy egy adott tevékenységet (függvényt) a kernel egy későbbi időpontban hajtson végre (hívjon meg). A call-out függvények adott időben történő meghívását a timeout rendszerhívással lehet megadni, illetve az untimeout rendszerhívással lehet törölni.

Fontos megjegyezni, hogy a call-out függvények rendszerkörnyezetben fut­nak, így nem aludhatnak, illetve nem érhetik el a folyamatok környezetét.

A call-out függvények periodikusan ismétlődő feladatok (tipikusan kernel-funkciók) végrehajtására használhatók, például:

  • hálózati csomagok ismételt elküldésére,

  • ütemezési és memóriakezelő függvények hívására,

  • készülékek monitorozására (nehogy megszakítások maszkolása miatt el­vesszünk bemeneti adatokat),

  • olyan készülékek lekérdezésére, amelyek nem megszakításkéréssel mű­ködnek.

A call-out-ok meghívását az óra-megszakítás végzi, azonban mivel a call-out függvények kernel rutinok, futásuk alatt a megszakítások fogadása nem lehet letiltva, hiszen ekkor hosszú ideig nem fogadná a rendszer az óramegszakításnál alacsonyabb prioritású megszakításokat. Emiatt a megsza­kí­tás­ke­zelő nem közvetlenül hívja meg a call-out függvényeket, hanem csak ellenőrzi, hogy elérkezett-e az ideje valamelyik call-out függvény meghívásának. Ha igen, beállít egy erre a célra rendszeresített jelzőbitet. A kernel ezt a jelzőbitet minden esetben ellenőrzi, amikor a megszakítások befejezése után visszatér a megszakított tevékenységéhez, vagyis feloldaná a legkisebb prioritású megszakítás tiltását. Így biztosított, hogy a kernel a call-out-okat a lehető leghamarabb, de az összes megszakítás kiszolgálása után meghívja.

A call-out függvények meghívásának adminisztrálására a rendszer különböző adatszerkezeteket használhat. Mindegyik adatszerkezet dinamikus, hiszen a call-out függvények száma futás közben változik, és nem lehet tudni, hány call-out függvény lesz egy adott rendszerben. Az adatszerkezetek meg­választásakor ismét az óra-megszakításkor végrehajtandó műveletek gyorsítása a cél. Két call-out listakezelési megoldást ismertetünk:

  • a láncolt listás és

  • az időkerekes

Call-out függvények láncolt listás ábrázolása

Ebben az esetben a call-out függvények listája egy rendezett lista, amely a call-out függvényeket „tüzelési sorrendben” (meghívási sorrendben) tartalmazza. Az időt a rendszer óra-megszakításokban számolja. Ezt az időegységet hívjuk tikknek.

A listaelemekben a láncolt listás tárolás esetén relatív időpontok vannak tárolva. A rendszer az egyes függvények meghívásának idejét az előző elem tüzelési idejéhez képest relatív számként tárolja, vagyis a rendszernek a lista előző eleméhez képest az adott listaelemben tárolt számú tikkel később kell aktiválni a listaelemben megnevezett függvényt.

A kernel minden egyes óramegszakítás esetén eggyel csökkenti az első listaelem időpont-számlálóját, és amikor az eléri a 0-át, akkor aktivizálja az első listaelemben tárolt függvényt, illetve mögötte az összes 0 időt tartalmazó elemet.

A megoldás előnye az egyszerű kezelhetőség, viszont hátránya, hogy a lis­ta igen hosszú lehet, ami időigényessé teheti a lista kezelését, például a listába való beszúrást (5.11.ábra).

5.11. ábra. ábra - Call-out függvények láncolt listás ábrázolása

Call-out függvények láncolt listás ábrázolása


Call-out függvények tárolása időkerékkel

Az időkerekes ábrázolás esetén a rendszer lényegében felszabdalja a listát nagyjából egyenlő részlistákra. A listaelemekben az abszolút meghívási idő van tárolva tikkekben mérve. A függvények meghívási ideje alapján egy hashtáblát készít a rendszer. Ha mondjuk egy 10 elemű hashtábla van használatban, akkor az első listában azok a call-out függvények lesznek, amelyek meghívási ideje 10-zel osztva 1-et ad maradékul. Így átlagosan egy lista hossza az előző tárolási móddal összevetve a tizedére csökken. Az egyes listák rendezettek, az elsőként meghívandó függvény áll a lista első helyén. Az időkerekes ábrázolást láthatjuk az 5.12 ábrán.

5.12. ábra. ábra - Call-out függvények időkerekes ábrázolása

Call-out függvények időkerekes ábrázolása


Az időkerék kezelése a következő módon történik: A rendszer megvizsgálja, hogy melyik részlistában tárolódnak az adott időpillanathoz tartozó call-out függvények. (Megnézi, 10-zel osztva mennyi maradékot ad az aktuális óra tikk-sorszáma.) Összehasonlítja az első listaelem tüzelési idejét az aktuális idővel. Ha a két érték megegyezik, meghívja a hozzá tartozó rutint, majd a lista esetleges további, azonos tüzelési idejű függvényeit. Ha a tüzelési idő nagyobb, nem tesz semmit. A nevét a módszer onnan kapta, hogy a hash­táb­lán a rendszer ellenőrzéskor körbe-körbe jár.

5.3.4. Szinkronizáció

A szinkronizáció (syncronization) egy folyamat végrehajtásának olyan időbeli korlá­tozása, ahol ez egy másik folyamat futásától, esetleg egy külső ese­mény bekövetkezésétől függ. Alapeseteit a korábbiakban tárgyaltuk.

A UNIX operációs rendszer alatt a szinkronizáció legegyszerűbb eszközei a jelzések (signals).

5.3.4.1. UNIX-jelzések

A jelzések elsődleges célja a UNIX-rendszerekben az, hogy a folyamatok kü­lönböző (rendszer- vagy alkalmazás szintű) események bekövetkezéséről értesüljenek. A jelzések részletes működése és rendszer szintű megvalósítása az egyes UNIX-változatokban lényeges eltéréseket mutat. Az eredeti System V jelzés implementáció alapvetően megbízhatatlan és hibás volt. A BSD UNIX-variációk ezért egy robusztusabb, megbízhatóbb jelzésmechanizmust dolgoztak ki, amely azonban nem kompatíbilis a System V jelzésekkel. Ezt a problémát a POSIX.1-szabvány (IEEE 90) próbálta meg feloldani egy szabványos interfész definiálásával. A System V Release 4 (SVR4) UNIX-variáns már ennek megfelelően, a BSD-jelzések bizonyos tulajdonságait is ötvözve tartalmazza a jelzéskezelést. A mai modern UNIX-rendszerek (So­laris, AIX, HP-UX, Digital UNIX stb.) a POSIX.1 szabványnak megfelelő jelzéskezelő rendszert tartalmaznak.

A UNIX-jelzések arra kínálnak módot, hogy események egy meghatározott halmazának bekövetkezése esetén a futó folyamat egy eljárása meghívásra kerüljön. Az eseményeket egész számokkal reprezentálják a rendszerek, és szimbolikus konstansokkal hivatkoznak rájuk. Az eredeti System V megvalósítás 15 jelzést tartalmazott, a mai rendszerek általában 31 jelzéssel dolgoznak.

Az 5.13. ábra néhány tipikus jelzést ismertet.

A jelzésrendszerben két lépés különíthető el: a jelzések keletkezése és kezelése. A következőkben ezeket a lépéseket ismertetjük.

5.14.ábra. táblázat - Tipikus UNIX-jelzések és értelmezésük

A jelzés

Leírása

SIGABRT

A folyamat megszakítása

SIGTERM

A folyamat leállítása

SIGSEGV

Szegmentációs hiba

SIGALRM

Valósidejű órariasztás

SIGBUS

Buszhiba

SIGPIPE

Olvasó nélküli csôvezetékbe írás


5.3.4.2. Jelzések keltése

Sokféle esemény válthat ki jelzéseket a futó folyamat környezetében: a futó folyamat maga, más folyamatok, az operációs rendszer, külső események, megszakítások. A jelzések forrásai a következő főbb kategóriákba csoportosíthatók.

  • Kivételek (exception). A kivételek (például illegális utasítás végrehajtásának kísérlete) bekövetkezése esetén a kernel értesíti a folyamatot egy jelzés elküldésével.

  • Más folyamatok. Egy folyamat jelzést küldhet egy más folyamat, vagy folyamatok csoportja számára az erre szolgáló rendszerhívások (kill(), illetve sigsend()) segítségével. A folyamat önmaga számára is küldhet jelzést.

  • Terminálmegszakítások. A terminál bizonyos karaktereinek (mint például a CTRL+C) leütése a terminálhoz csatlakozó, előtérben futó folyamat számára jelzést generál.

  • Munkamenet-kezelés (job control). Az ilyen képességgel rendelkező parancsértelmezők (shellek) az előtérben, illetve háttérben futó folyamatokat jelzések segítségével manipulálják, illetve a kernel egy folyamat megszűnése esetén ilyen jelzéssel értesíti a szülő folyamatát.

  • Kvótajelzések. Amikor egy folyamat eléri a számára rendelkezésre bocsátott CPU-használat vagy fájlméret határait, a kernel jelzést küld számára.

  • Értesítések. Egy folyamat bizonyos események (például egy periféria készen áll az adatátvitelre) bekövetkezéséről értesítést kérhet a ker­neltől.

  • Riasztások. Egy folyamat beállíthat riasztást egy adott időhosszra, amely letelte után, a kernel jelzést küld a folyamat számára.

5.3.4.3. Jelzések kezelése

Egy folyamat számára a hozzá beérkező jelzések aszinkron események, azaz futása során bármikor beérkezhetnek. A jelzés létrejötte után a második fázis a folyamatok értesítése és a jelzések kezelése. A jelzés akkor számít kézbesítettnek, ha az a folyamat, amelynek a jelzés szól, tudomásul veszi a megérkezését, és normális futását megszakítva valamilyen meghatározott akciót hajt végre.

Minden jelzéshez tartozik egy alapértelmezett akció (default action), amit a kernel hajt végre, amennyiben a folyamat nem határozott meg más akciót. Öt lehetséges alapértelmezett akció létezik.

  • Megszakítás (abortálás). A folyamat megszakítását eredményezi egy futási lenyomat (core dump) generálása után. A lenyomat egy core nevű fájlban keletkezik a folyamat aktuális könyvtárában. Tartalmazza a folyamathoz tartozó tárterület tartalmát (memóriakép) és a processzor regisztereinek pillanatnyi értékét (regiszterkép). Ez a lenyomat felhasználható a későbbiekben a megszakítási helyzet analízisére.

  • Kilépés. A program leállítása core fájl generálása nélkül.

  • Figyelmen kívül hagyás (ignore). A jelzést figyelmen kívül hagyja a kernel (folyamat).

  • Felfüggesztés. A folyamat felfüggesztődik.

  • Folytatás. A folyamat folytatódik, ha fel volt függesztve, egyébként figyelmen kívül hagyja a jelzést.

Az 5.14. ábra a korábbiban felsorolt jelzésekre adja meg az alapértelmezett akciókat.

A jelzés

Leírása

Alapértelmezett akció

SIGABRT

A folyamat megszakítása

megszakítás

SIGTERM

A folyamat leállítása

kilépés

SIGSEGV

Szegmentációs hiba

megszakítás

SIGALRM

Valósidejű órariasztás

kilépés

SIGBUS

Buszhiba

megszakítás

SIGPIPE

Olvasó nélküli csővezetékbe írás

kilépés

A folyamatok futásuk során bármikor felülírhatják ezeket az alapértelmezett akciókat a jelzések többségére. Az így meghatározott akció lehet a jelzés figyelmen kívül hagyása, vagy egy, a folyamat által meghatározott, ún. jelzéskezelő (handler) eljárás meghívása. A folyamat bármikor visszaállíthatja a jelzéshez tartozó alapértelmezett akciót is. Bizonyos jelzések esetében, mint például a SIGKILL vagy a SIGSTOP az alapértelmezett akciók felülírása nem lehetséges.

Fontos megjegyezni, hogy a jelzésekhez tartozó akciók a címzett folyamat környezetében hajtódnak végre, azaz csak akkor, ha a hozzájuk tartozó folyamatok futó állapotba kerülnek. Bizonyos esetekben ez lényeges késleltetést okozhat a jelzések kezelésében.

A jelzést fogadó folyamat tudomására akkor jut egy jelzés érkezése, ha a kernel meghívja az erre a célra szolgáló issig() rendszerhívást. Ez a következő esetekben fordul elő:

  • visszatéréskor felhasználói futási szintre egy rendszerhívásból vagy meg­szakításból,

  • egy megszakítható eseményre történő várakozás előtt, és

  • közvetlenül egy nem megszakítható eseményre történő várakozás után.

Látható, hogy a jelzések kezelése szempontjából a folyamat várakozó (alvó) állapotai közül a nem megszakítható eseményre várakozás különleges jelentőséggel bír. Az ilyen típusú várakozás esetén a kernel a jelzést várakozó állapotban tartja mindaddig, míg a folyamat vissza nem tér (fel nem ébred) ebből az állapotából. Megszakítható várakozások (mint például a terminál bevitelre történő várakozás) esetén a kernel a jelzése beérkezésének hatására a folyamatot felébreszti.

Ha az issig() hívás IGAZ értékkel tér vissza, a kernel a psig() hívás segítségével kezeli a jelzést. A psig() vagy végrehajtja a kernel által meghatározott alapértelmezett akciót, vagy a sendsig() hívás segítségével meghívja a folyamatkezelő függvényét. A kezelő függvény meghívása előtt a folyamat kilép a kernel futási módból. A psig() a verem és a folyamat kontextusának manipulálásával arról is gondoskodik, hogy a folyamat a jelzés kezelése után normálisan folytatható legyen.

5.3.4.4. Megbízhatatlan jelzések

Az eredeti Ssytem V jelzésrendszer több hibát is tartalmaz, ezért megbízhatatlan jelzővel illetik. Egyik tipikus problémája, hogy a kernel a jelzés kezelésekor minden alkalommal visszaállítja az alapértelmezett akciót, így a folyamat jelzéskezelő eljárásának gondoskodnia kell az egyedi kezelés ismételt beállításáról. Ez versenyhelyzetet teremt a jelzések keletkezése és az egyedi akciók beállítása között, ami egy-egy jelzés esetében könnyen az alapértelmezett akció végrehajtását eredményezheti.

Egy másik tipikus probléma a jelzéseket leíró tábla elhelyezéséből adódik. A táblát a kernel ugyanis a folyamathoz kötött u-területen tárolja, amihez csak az aktuális folyamatnál fér hozzá. Ily módon egy nem megszakítható várakozásban lévő folyamat esetén a kernel nem tudja eldönteni, hogy a folyamat maga kezeli-e a jelzést, vagy az alapértelmezett akciót kell végrehajtania. Ez csak a folyamat felébresztése után derülhet ki.

Végezetül hiányzott a jelzések kézbesítésének átmeneti blokkolása, illetve az olyan munkamenetek kezelése, ahol folyamatok csoportosan kezelhetőek a terminál-hozzáférés során.

5.3.4.5. Megbízható jelzések

Az előbbi problémákra a BSD 4.2-es verziója egy új jelzésrendszer bevezetésével hozott megoldást, illetve az AT&T SVR3 verziójában található megbízható jelzések is ebben az irányban változtak. A két megoldás ugyanakkor nem volt kompatíbilis, mindkettő más és más rendszerhívások bevezetésével orvosolta a problémákat.

A POSIX.1 szabvány teremtett rendet egy egységes interfész bevezetésével, melynek implementációs részleteit nem rögzítették, így mindkét UNIX-variáns beépíthette. Az SVR4 UNIX egy új, POSIX.1-nek megfelelő rendszert tartalmazott, amely kompatíbilis volt a korábbi BSD és SVR3 verziókkal is.

A megbízható jelzéskezelő rendszerek mindegyike a következő közös szolgáltatásokat nyújtja:

  • Perzisztens kezelők (persistent handlers). A jelzéskezelő eljárás végrehajtásának beállítása a jelzés kezelése után is megmarad, így nincs szük­ség újbóli beállítására.

  • Maszkolás (masking). Egy jelzés átmenetileg maszkolható, avagy blokkolható. Az ilyen jelzések keletkezését a kernel megjegyzi, de nem érte­síti a hozzájuk rendelt folyamatokat. Ez lehetővé teszi a folyamatok kri­tikus részeinek védelmét a jelzések megszakításaival szemben.

  • Alvó folyamatok (sleeping processes). A folyamatokhoz tartozó jelzéseket leíró információk egy része akkor is látható a kernel számára, ha a folyamat éppen nem fut (az u-terület helyett a proc-területen tárolódik), ily módon a kernel a folyamat felébresztése nélkül ellenőrizheti, hogy az megadott-e egyedi akciót, vagy az alapértelmezett jelzéskezelő akciót kell végrehajtani.

  • Felszabadítás és várakozás (unblock and wait). A megbízható jelzések mechanizmusa egy speciális rendszerhívás (sigpause()) segítségével képes megoldani azt, hogy egy folyamat felszabadítsa a blokkolt jelzést, majd azonnal várakozó állapotba kerüljön a jelzés megérkezéséig.

5.3.4.6. Az SVR3 implementáció

Az AT&T által kidolgozott implementáció minden lényeges tulajdonsággal rendelkezett a megbízható jelzéskezelés kidolgozásához, azonban megvalósításának voltak sajátos hátrányai. Legfontosabb hiányossága, hogy egyszerre nem képes több jelzést blokkolni, így nehéz több jelzést is kezelő kritikus régiók megírása (ahol a folyamatot nem szakíthatják félbe jelzések). Az SVR3-ból hiányzott a munkafolyamat-kezelés is. Mindezeket a hiányosságokat a 4BSD rendszere pótolta.

5.3.4.7. BSD jelzésmenedzsment

A 4.2BSD volt az első megbízható jelzésrendszerrel ellátott UNIX-variáns. A rendszerhívások többsége tartalmaz egy jelzésmaszk paramétert, így egy hívás egyszerre több jelzésen is végrehajthat egy művelet. A jelzéseket blokkoló sigsetmask() függvényhívásnak egyszerre több jelzést is megadhatunk.

A jelzések kezelésére szolgáló eljárásokhoz megadásukkor jelzésmaszkot rendelhetünk, így végrehajtásukkor a kernel gondoskodik a maszkolt jelzések helyes és automatikus beállításáról. Ily módon egy jelzés második példányát a rendszer nem fogja kezelni addig, míg az első kezelését be nem fejezte.

A BSD implementáció további újdonsága, hogy a jelzéseket különálló vermet használva is kezelheti a folyamat. Így lehetővé válik például a verem túlcsordulását jelző jelzés kezelése is.

Ez az implementáció további jelzéseket is bevezetett, elsősorban a munkafolyamat-kezelés területén. A munkafolyamat összefüggő folyamatok olyan csoportja, amelyek általában egy csővezetéket formálva helyezkednek el (standard be-, illetve kimeneteiket összekötve). Egy terminálhoz tartozó több folyamat esetén csak egy rendelkezhet a terminál írásának és olvasásának jogával (előtérben futó folyamat), a többiek a háttérben futnak. A háttérben futó folyamatok jelzéseket kapnak, amikor megpróbálják elérni a terminált, és általában felfüggesztődnek. A felhasználó parancsértelmezője jelzések küldésével képes a folyamatokat előtérbe vagy háttérbe helyezni, felfüggeszteni és továbbindítani a futásukat.

Végezetül a 4BSD UNIX képes a jelzések által félbeszakított, hosszú ideig futó rendszerhívások automatikus újrahívására. Ilyen rendszerhívások lehetnek a karakteres eszközök írás és olvasás műveletei, a hálózati kapcsolatokat és csővezetékeket kezelő műveletek és a várakozás jellegűek (például wait(), waitpid(), és ioctl()). Amikor egy ilyen hívást félbeszakít egy jelzés, a jelzés lekezelését követően a rendszerhívás automatikusan újra meghívódik (enélkül EINTR hibával térne vissza).

A BSD jelzésinterfész hatékony és flexibilis. Legfontosabb hátránya, hogy nem kompatíbilis az eredeti AT&T interfésszel. Ez azt eredményezte, hogy a szoftvergyártók maguk kezdtek olyan közös interfészeket kifejleszteni, amelyek mindkét (BSD, SysV) UNIX-variánssal használhatóak. Ezt a problémát oldotta meg az egységes POSIX.1 jelzésinterfész, amelyet az SVR4 (System V Release 4) vezetett be.

5.3.4.8. Az SVR4 jelzések

A UNIX Systems Laboratories UNIX SVR4.2 Operációs rendszer API Interfésze által bevezetett jelzéskezelő rendszerhívások a BSD és korábbi SVR3 variánsok és a nem megbízható jelzések teljes halmazát lefedik. A régi signal(), sigset(), sighold(), sigelse(), sigignore() és sigpause() rendszerhívások mellett új, a BSD javított jelzéskezelését megvalósító rendszerhívásokat vezettek be. A jelzésekkel kapcsolatos állapotinformációk kezelését a BSD megoldásnál látható módon oldották meg, kisebb változó- és függvénynév módosításokkal.

A kernel a folyamatok felébresztése nélkül képes ellenőrizni, hogy azok foglalkoznak-e a jelzéssel. Ha igen, akkor egy bitsorozat (p_cursig) megfelelő elemét bebillentve a kernel jelzi a folyamat számára a jelzés megérkezését. (Ily módon egy jelzésből egyszerre maximum egy kezeletlen lehet.) Ha a folyamat megszakítható várakozásban van és a jelzés nem blokkolt, akkor a kernel felébreszti a folyamatot.

A folyamat a BSD-megoldásnál megismert issig() rendszerhívással ellenőrzi a jelzések meglétét (a p_cursig bitjeinek tesztjével). A kernel itt is a psig() rendszerhívással kezdeményezi a jelzések kezelését.

5.3.4.9. Kivételkezelés

Kivételen azt értjük, amikor egy program egy nem megszokott szituációval, tipikusan valamilyen hibával találja magát szemben. Ezek valamilyen hardver eszköz (többnyire a processzor) által generált megszakítások, mint például a hibás címzés, nullával való osztás stb. Ez általában hibamegszakítást okoz, amelynek kiszolgálásakor a kernel jelzések segítségével értesíti a programot a bekövetkezett kivételről.

A jelzés típusa a kivétel természetétől függ. Például egy hibás címzés SIGSEGV (szegmentációs hiba) jelzést eredményez. Amennyiben a folyamat meghatározott egy kezelő függvényt a jelzéshez, úgy a kernel azt hívja meg. (Ezt a mechanizmust használják a nyomkövetők is a program futásának befolyásolására).

A UNIX kivételkezelésnek – többek között – két nagy hátránya van:

  • a kivételkezelés a kivétellel megegyező kontextusban fut; a kernel ugyan átadja a kivétel bekövetkezésekor aktuális kontextus bizonyos ré­szét a kivételkezelőnek, de ennek pontos tartalma UNIX-implementációnként változhat,

  • a jelzéseket alapvetően egyszálú folyamatok számára találták ki; többszálú végrehajtást is támogató UNIX-variánsok (például Solaris 7) csak körülményesen alkalmazhatják a jelzéseket.

5.3.4.10. Folyamatcsoportok és terminálkezelés

A UNIX a korábban említett folyamatcsoportokat használja a terminál hozzáférés és a felhasználói viszony kezelésére. (Felhasználói viszonyon azt értjük, amikor a felhasználó interaktív kapcsolatot létesít az operációs rendszerrel.) Minden folyamathoz tartozik egy folyamatcsoport azonosító (process group ID), melyet a kernel a folyamatok teljes csoportjára vonatkozó akciók végrehajtásában használ fel. A csoportoknak lehet egy csoportvezetője, mely­nek processzazonosítója (PID) megegyezik a folyamatcsoport azonosítóval. Normális esetben a folyamatok szülőjüktől öröklik csoportazonosítójukat.

Az egy csoportba tartozó folyamatokhoz egy vezérlő terminál tartozik, általában a felhasználó belépésének terminálja, ahonnan a folyamatokat elindította. Ehhez a terminálhoz egy speciális eszköz, a /dev/tty rendelődik (az eszköz neve kiegészülhet a terminált azonosító jellel, például /dev/tty01).

A munkamenet-kezelés az a mechanizmus, mely egy folyamatcsoport futását felfüggesztheti, vagy továbbengedheti, és meghatározza a csoport kapcsolatát a terminálhoz. Munkamenet-kezelésre alkalmas shellek, mint például a csh vagy ksh speciális vezérlő karaktereket (például CTRL+Z) és parancsokat (például fg és bg) használnak ezen szolgáltatások elérésére.

A kezdeti System V implementációk a folyamatcsoportokat általában a felhasználókhoz kötött folyamatok reprezentálására használták, és nem tartalmaztak munkamenet-kezelést. A 4BSD minden parancssorhoz új folyamatcsoportot vezetett be, így megjelent a munkamenet fogalma. Az SVR4 vezette be az egységes, felhasználói belépési viszonyon és munkameneten alapuló folyamatcsoport-kezelést.

Az SVR4 (illetve a 4.4BSD) egy új viszony objektum (session object) bevezetésével írja le a felhasználói kapcsolatot a folyamatokhoz. A folyamatok egyaránt tartozhatnak viszonyhoz és folyamatcsoporthoz. A viszonyok leírására egy új azonosítót (SID – session id) használ a rendszer. A viszony objektum a felhasználóhoz és a vezérlő terminálhoz rögzített. A viszony kapcsolatban levő folyamatok vezetője (session leader) jogosult egyedül a vezérlő terminál lefoglalására, vagy felszabadítására.

Amikor a felhasználó belép a rendszerbe, a termináljához rendelt első folyamat a setsid() rendszerhívás segítségével létrehoz egy új viszony csoportot, mely egyben folyamatcsoport is lesz. A felhasználó által elindított további folyamatok ehhez a viszony csoporthoz fognak tartozni, viszont újabb, az elsőtől független folyamatcsoportot is alakíthatnak. Így egyetlen belépéshez több folyamatcsoport is tartozhat. Ezen csoportok egyike az előtérben futó csoport (foreground group), amely kizárólagos hozzáféréssel rendelkezik a terminálhoz. Amennyiben a háttérben futó folyamatok hozzá akarnak férni a terminálhoz, egy speciális jelzés értesíti őket arról, hogy ezt nem tehetik meg, mivel a háttérben futnak.

A viszony csoporton belül a folyamatok megváltoztathatják aktuális folyamatcsoportjukat, de más viszonyhoz tartozó folyamatcsoportba nem léphetnek át. Erre csak egy mód van: a folyamat maga alapít egy új viszony csoportot, teljesen szakítva az előzővel.

5.3.5. Folyamatok közötti kommunikáció (interprocess communication)

Bizonyos programozási környezetekben gyakran együttműködő folyamatok csoportját használhatjuk egymással összefüggő feladatok megoldására. A folyamatok között információáramlásra van szükség. Az informá­ciócsere alapvetően két módon valósulhat meg:

  • közösen használt tárterületen, vagy

  • kommunikációs csatornán keresztül.

Ebben a részben azzal foglalkozunk részletesebben, hogy a UNIX-rendszer milyen eszközöket nyújt a második eset, azaz a folyamatok üzenetváltásos együttműködésének megszervezéséhez.

A UNIX operációs rendszer többféle IPC-mechanizmust kínál. Ezek a következők: jelzések (signals), csővezetékek (pipes) és folyamat-nyomkövetés (process tracing). Bizonyos UNIX-variánsok ezen kívül rendelkeznek az osztott memória (shared memory), szemaforok (semaphores) és üzenetsorok (message queues) lehetőségeivel is. A következőkben röviden áttekintjük ezen eszközöket.

5.3.5.1. Jelzések

A jelzések elsődleges célja a folyamatok értesítése aszinkron módon bekövetkező eseményekről. Bár eredetileg hibák jelzésére szolgáltak, egyszerű folyamatok közötti kommunikációt is lehetővé tesznek. A modern UNIX-rendszerek 31 jelzést alkalmaznak, melyek közül kettő, a SIGUSR1 és SIGUSR2 az alkalmazások számára fenntartott. Egy folyamat jelzést küldhet egy vagy több másik számára rendszerhívások (kill()) segítségével. A jelzésekkel részletesebben az 5.3.4. részben foglalkoztunk.

5.3.5.2. Csővezetékek

A csővezeték (pipe) tradicionálisan egy egyirányú, FIFO jellegű, nem strukturált, változó méretű adatokat közvetítő adatfolyam. A csővezeték írói adatokat helyeznek a csőbe, olvasói kiolvassák azokat. A kiolvasott adatok eltűnnek a csőből. Egy üres csőből olvasni kívánó folyamat megáll addig, míg adat nem érkezik a csőbe. Hasonlóképpen, egy tele csőbe írni akaró folyamat is megáll, amíg a csőből egy adat nem távozik.

A pipe() rendszerhívással hozható létre egy cső. A rendszerhívás két fájl-leíróval tér vissza, a csővezeték írására és olvasására való leírókkal. A leírókat felhasználva a csővezetéket a fájlkezelésben használható read() és write() rendszerhívásokkal olvashatjuk, illetve írhatjuk. Ezeket a leírókat a folyamatból létrejött gyermekek öröklik, megosztva ezzel a fájl használatát. Ily módon egy csővezetéknek több írója és olvasója lehet. Egy adott folyamat önmaga is lehet egyszerre író és olvasó is. A csővezetéket azonban általában két folyamat közötti egyirányú kommunikációra használják, amikor pontosan egy írója és egy olvasója van. Ilyen csővezetéket a felhasználók a parancsértelmezőben is létrehozhatnak a csővezeték jel ( '|' ) segítségével. A jel bal oldalán szereplő folyamat a cső írója, a jobb oldali pedig az olvasója lesz. A parancsértelmező gondoskodik a csővezeték létrehozásáról a folyamatok indítása során.

A csővezetékek legfontosabb hátrányai a következők:

  • mivel nincs rögzített adatméret és -struktúra, a vevőnek nincs tudomása arról, hogy hol vannak az adatok határai,

  • amennyiben több olvasó is van, úgy az író nem tudja kiválasztani, hogy melyik olvasónak küldi az üzenetet, és

  • mivel az olvasás kiveszi az adatot a csővezetékből, nincs lehetőség több címzetthez is eljuttatni az adatot.

A System V rendszerekben létezik egy speciális csővezeték, az elnevezett csővezeték (named pipe). Ez létrehozási módjában és használatában is különbözik az eddig megismertektől, bár lényegében ugyanazt a célt szolgálja. A felhasználó a fájlrendszerben létrehoz egy FIFO elvű speciális fájlt egy speciális parancs segítségével (mknod). A FIFO-t a folyamatok a fájlokhoz hasonlóan nyithatják meg és használhatják. Viselkedését tekintve az elnevezett csővezeték nem különbözik a korábban megismert, névtelen csővezetéktől. Lényeges különbség, hogy a FIFO a folyamatoktól függetlenül létezik, az írók és olvasók megszűnésével nem törlődik. Ez a megoldás több előnyt is jelent a korábbi csővezetékekkel szemben: a FIFO-kat egymástól független folyamatok is használhatják (csak a nevet kell ismerniük), az adat megmarad még akkor is, ha az összes hozzáférő folyamat megszűnik. Hátrány azonban, hogy kevésbé biztonságosak (csak a fájlrendszerben alkalmazott biztonsági mechanizmusok vonatkoznak rájuk), valamint könnyen előfordulhat, hogy senki sem törli őket, és feleslegesen foglalnak erőforrásokat. A névtelen csővezetékeket egyszerűbb létrehozni és kevesebb erőforrást kötnek le.

Az SVR4 kétirányú csővezetéket is implementál. A pipe() rendszerhívás itt is két leíróval tér vissza, azonban mindkettő használható írásra és olvasásra is. Valójában két független csővezeték keletkezik (fd[2]), melyeknél a kernel oldja meg a leírók egymáshoz rendelését. Mindkét csővezetékhez egy-egy leírót rendel a kernel, így megvalósítva a kétirányú adatforgalmat. Az fd[0]-ba írt adat az fd[1]-ből olvasható ki, míg az fd[1]-be írt adat az fd[0]-ból olvasható. A kétirányú csővezeték hasznos eszköz, mivel az alkalmazások többségénél kétirányú adatforgalmat szeretnénk kiépíteni.

5.3.5.3. Folyamat-nyomkövetés

Ezt a lehetőséget elsősorban a nyomkövető programok használják. A ptrace() rendszerhívás segítségével egy folyamat befolyásolhatja a gyermeke futását. A következő főbb feladatok oldhatóak meg a rendszerhívás segítségével:

  • adat olvasása és írása a gyermek címtartományában,

  • adat olvasása és írása a gyermek u-területén,

  • a gyermek folyamat általános célú regisztereinek írása és olvasása,

  • adott jelzések „elkapása”, aminek során a kernel a gyermeket felfüggeszti és értesíti a szülőt a jelzésről,

  • megfigyelési pontok (watchpoints) beállítása és törlése a gyermek címtartományában,

  • a leállított gyermek folyamat futásának folytatása,

  • a gyermek futásának folytatása egy utasítás végrehajtására,

  • a gyermek futásának leállítása,

  • a gyermek engedélyezheti a szülő számára a nyomkövetést.

A nyomkövető tipikusan gyermek folyamataként hozza létre a követendő programot, amely a ptrace() rendszerhívás segítségével engedélyezi a nyomkövetést. A szülő ezek után a wait() rendszerhívással várakozik a gyermekkel kapcsolatos eseményekre. A hívás visszatérési értéke ad információt arra nézve, hogy aktuálisan milyen esemény következett be. Ezek után a szülő a ptrace() rendszerhívással befolyásolja a gyermeket, majd ismét várakozni kezd.

Bár a ptrace() alapvetően lehetővé tette nyomkövető programok létrehozását, rendelkezik fontos korlátokkal és hátrányokkal:

  • A nyomkövető kizárólag a közvetlen gyermekeit tudja nyomon követni, az általuk létrehozott gyermekeket már nem.

  • A rendszer nem hatékony, rengeteg környezetváltást igényel. A ptrace() hívással kiadott utasítások ugyanis nem közvetlenül érik el a gyermeket, hanem a kernel segítségével egy környezetváltás után.

  • A nyomkövető már futó folyamatokat nem követhet, mivel a gyermeknek előbb engedélyeznie kell a nyomkövetést.

  • setuid jelzéssel ellátott programok nyomkövetése általában tiltott, mivel súlyos biztonsági problémákat vetne fel (a címterület módosításával a program működése lényegesen befolyásolható, például ha a gyermek egy másik folyamatot indít, a nyomkövető megváltoztathatja a program nevét).

A mai modern UNIX-rendszerek új módszereket kínálnak a nyomkövetés megoldására a /proc fájlrendszeren keresztül. Ez a rendszer a felsorolt hiányosságok nagy részét megoldja, így a korszerű nyomkövető programok a ptrace() interfész helyett ezt használják.

5.3.5.4. System V IPC

A következő kommunikációs eszközöket (szemaforok, üzenetsorok, osztott memória) összefoglaló néven csak System V IPC-ként szokás említeni. Eredetileg a SYSV UNIX-variánsokban tranzakciófeldolgozásra kifejlesztett eszközök mára részeivé váltak minden korszerű UNIX-rendszernek. Ezen eszközök (IPC-erőforrások) használata és programozói interfésze lényeges közös elemeket tartalmaz.

Minden IPC-erőforrás rendelkezik a következő azonosítókkal:

  • kulcs (key) – a felhasználó által meghatározott egész szám, mely az erőforrás egy példányát azonosítja,

  • létrehozó (creator) – az erőforrás létrehozójának felhasználói és csoportazonosítói (UID, GID),

  • tulajdonos (owner) – az erőforrás tulajdonosának felhasználói és csoportazonosítói (UID, GID),

  • hozzáférési jogok (permissions) – a fájlrendszerhez hasonlatos olvasási/írási/végrehajtási jogok a tulajdonos, csoportja és mások számára.

Minden erőforrásnak van létrehozó (shmget(), semget(), msgget()) és vezérlő rendszerhívása (shmctl(), semctl(), msgctl()). A létrehozáskor a kulcs megadása mellett a létrehozási opciókat, illetve egyéb, az adott erőforrásra jellemző paramétereket adhatunk meg. A létrehozó függvények az erőforrás elérésére alkalmas leírót adnak vissza (shmid, semid és msgid). A vezérlő függvényeknek átadott parancsok segítségével befolyásolhatjuk az erőforrás működését. Ezek egyike a megszüntető parancs (IPC_RMID) is. A megszüntetés nélkül a kernel folyamatosan fenntartja az erőforrásokat, még akkor is, ha minden kezelő folyamatuk megszűnt. Ennek megvalósítása érdekében a kernel egy elkülönített, a folyamatoktól független területen tartja fent az erőforrásokat és a kezelésükhöz szükséges adminisztrációs táblákat. Ez a terület korlátos méretű, általában kernel-paraméterként méretezhető. Bizonyos alkalmazások (például adatbázis kezelők) megkövetelhetik az operációs rendszer alapértelmezett területméretének növelését.

5.3.5.5. Szemaforok

A SYSV IPC szemaforok az általános szemafor mechanizmusát és operációit (P() és V()) valósítják meg. A megvalósítás némiképp bonyolultabb, körültekintőbb használatot igényel, de összetettebb megoldások is kialakíthatóak segítségével.

A szemaforokat a semget() rendszerhívással hozhatjuk létre:

semid = semget(key, count, flag);

A kernel a megadott kulccsal (key) count darab szemafort hoz létre. Létrehozásuk után a semop() rendszerhívás segítségével használhatjuk őket.

status = semop(semid, semops, nsemops);

Az nsemops méretű semops tömb sembuf típusú elemei tartalmazzák a szemaforon végrehajtandó utasításokat. A sembuf struktúra a következő:

struct sembuf {

unsigned short sem_num;

short sem_op;

short sem_flg;

};

A sem_num jelöl ki egy szemafort a létrehozottak tömbjéből, a sem_op által meghatározott művelet pedig a következő lehet:

  • sem_op > 0 esetén sem_op értéke hozzáadódik a szemafor értékéhez,

  • sem_op = 0 esetén a kernel blokkolja a folyamatot mindaddig, míg a szemafor értéke nulla nem lesz,

  • sem_op < 0 esetén a kernel blokkolja a folyamatot, míg a szemafor értéke nagyobb vagy egyenlő lesz, mint a sem_op abszolút értéke. Ha ez bekövetkezik, akkor ezzel az értékkel csökkenti a szemafor értékét és továbbengedi a folyamatot.

Látható, hogy egyetlen semop() hívás több szemaforon többféle művelet végrehajtását is jelentheti. A kernel garantálja azt, hogy a műveletek végrehajtásáig (vagy a folyamat blokkolásáig) más műveleteket ezen a halmazon nem kezd el végrehajtani (a szemafor műveletek kizárólagosak). Ha bármelyik művelet blokkolja a folyamatot, akkor a kernel visszaállítja az esetlegesen módosított szemaforok értékét a semop() hívás előtti értékekre. A flag paraméter beállításával (IPC_NOWAIT) blokkolás helyett hibaüzenettel való visszatérés is választható. Másrészt a SEM_UNDO flag beállítása esetén a kernel megjegyzi a folyamat által végrehajtott műveleteket, és azokat automatikusan visszaállítja, ha a folyamat kilép. Ez a módszer használható fel olyan holtpont helyzetek kezelésére, amikor a szemafort tartó folyamat kilépése miatt a szemaforra várakozók örökre leállnának a P() műveletben.

A System V szemaforimplementáció legnagyobb problémája, hogy a szemaforok létrehozása és inicializálása nem atomi művelet. A két rendszerhívás (semget() és semctl()) között más folyamatok is hozzáláthatnak ugyanazon szemafor létrehozásához. A másik probléma a SYSV IPC általános vonása: a szemaforok törlésük nélkül a hozzájuk tartozó folyamatok megszűnése után is létezni fognak, feleslegesen foglalva a rendszer erőforrásait.

5.3.5.6. Üzenetsorok

Az üzenetsor egy olyan leíró, mely üzenetek láncolt listájára mutat. Minden egyes üzenet egy típusjelző után egy adatterületet tartalmaz. A felhasználói folyamat az msgget() rendszerhívással hozhat létre egy üzenetsort, melyet aztán az msgsnd() és msgrcv() rendszerhívásokkal írhat és olvashat a read() és write() rendszerhívásokhoz hasonlóan.

Az üzenetsorok a csővezetékekhez hasonlatosan FIFO működésűek, azaz a kernel nyilvántartja az üzenetek érkezési sorrendjét, és a legelőször érkezett üzenetet adja vissza az első olvasási kérésre. Két lényeges különbség van a csővezetékekhez képest. Az üzenetek típusjelzője felhasználható szűrőként az olvasáskor bizonyos típusú üzenetek kiválasztására, azaz ilyenkor az elsőként érkezett, megegyező típusú üzenettel tér vissza az msgrcv() hívás. Ez a mechanizmus felhasználható például üzenetprioritási rendszer meg­valósítására.

A másik különbség az üzenetsorok azon tulajdonsága, hogy az adatokat nem formázatlan folyamként, hanem elkülönülő üzenetekben továbbítják, ami az adatok pontosabb feldolgozását teszi lehetővé, mivel az üzenetek belsejében a tartalmi feldolgozást segítő típusazonosítókat lehet elhelyezni.

Az üzenetsorok jól használhatóak kisméretű adatcsomagok küldésére, de kevéssé alkalmasak nagy mennyiségű adat átvitelére. A kernel belső adat­buffereket használ az üzenetek tárolására a kiolvasásig. Az üzenet beérkezésekor a kernel a küldő adatterületéről átmásolja az üzenetet a belső tárolóba, majd a kiolvasáskor tovább másolja a fogadó adatterületére. Ily módon egyazon adatcsomagot kétszer kell mozgatni, ami nagy mennyiségű adat esetén költséges megoldás. Az üzenetsorok másik hátránya, hogy nem nevezhető meg címzett az üzenetekhez. Bármilyen, megfelelő jogosultságokkal rendelkező folyamat kiolvashatja az üzeneteket. Ennek megfelelően a kooperációban részt vevő feleknek meg kell egyezniük valamilyen saját címzési protokollban, amit a kernel semmilyen eszközzel nem támogat.

5.3.5.7. Osztott memória

Az osztott memória a központi tár egy olyan régiója, melyet egyszerre több folyamat is használhat. A folyamatok ezen tartományt bármilyen virtuális címhez hozzárendelhetik saját címtartományukban. A hozzárendelés után a memória a folyamat saját memóriájával teljesen megegyező módon – rendszerhívások nélkül – használható. Ezért az osztott memória a leggyorsabb kommunikációs forma azonos gépen futó folyamatok között. A memória létrehozója a kulcs megadása mellett meghatározhatja a memória méretét:

shmid = shmget(key, size, flag);

Már létező osztott memóriaterülethez az shmat() rendszerhívással lehet virtuális címet rendelni, illetve az shmdt() hívással lehet a hozzárendelést megszüntetni:

addr = shmat(shmid, shmaddr, shmflag);

shmdt(shmaddr);

A memória teljes megszüntetéséhez az shmctl() rendszerhívással ki kell adni az IPC_RMID parancsot. Ez azonban nem jár a memória azonnali megszüntetésével, csak megjelöli azt. A tényleges megszüntetés akkor következik be, amikor minden, a memóriához kapcsolódott folyamat lekapcsolódik róla. A törlésre megjelölt memóriához azonban új folyamatok már nem kapcsolódhatnak. Törlés nélkül a memória a folyamatok megszűnése után is megmarad, megőrizve minden adatot, amit a folyamatok ott elhelyeztek. Ily módon lehetővé válik például a folyamatok két futása közötti adatátmentés.

Az osztott memória rendkívül gyors és egyszerűen megvalósítható módszer az azonos gépen futó folyamatok közötti adatcserére. Legnagyobb hátránya, hogy semmilyen szinkronizációs mechanizmus nem kapcsolódik hozzá, így az adatok módosítása konkurens lehet. Még önálló adatstruktúrák módosításán belül is lehetséges a párhuzamosság, ami teljesen inkonzisztens adatokat eredményez. Ezért az osztott memóriát használó folyamatoknak egymás között meg kell oldaniuk a konzisztens módosítás rendszerét (például szemaforok segítségével).

5.3.5.8. Hálózati kommunikáció – socket programozás

A számítástechnikában a gépeket összekapcsoló hálózat megjelenése egy új fejezetet nyitott. A soros vonali terminál illesztés (dialup) továbbfejlődése gépek közötti pont-pont adatkapcsolat kialakítását tette lehetővé. Megjelent a kliens-szerver modell, mely szolgáltatásalapon különítette el a felhasználót (kliens) és a szolgáltatót (szerver).

A UNIX operációs rendszerben alapvetően a TCP/IP protokollcsaládra alapuló kommunikációs eszközöket fejlesztettek ki a különböző gépeken futó folyamatok közötti kommunikáció megoldására.

A különböző gépeken futó alkalmazások közötti adatátvitel programozói interfésze nagyon hasonlatos az eddigiekben megismertekhez. A hálózati kommunikációs csatorna leírója az ún. socket, egy absztrakt objektum, ami felhasználható üzenetek küldésére és fogadására. A socket programozói interfész nemcsak hálózati, hanem gépen belüli IPC megvalósítására is alkalmas.

A socket (és az adatforgalom) alapvetően két típusú lehet (zárójelben az IP fölötti réteg protokolljának rövidítése olvasható):

  • folyam (stream) (TCP): megbízható, sorrendhelyes, kétirányú kapcsolat

  • üzenetszórás (datagram) (UDP): kapcsolatmentes csomagküldés, ahol a sorrend és a megérkezés nem garantált.

Amikor egy folyamat egy socket hívást hajt végre, a kernel ezen alacsony szintű adatátviteli protokollokat hívja meg az üzenetek átvitelére. A protokollhoz tartozó átviteli függvényeket egy táblából választja ki a kernel, és elküldi hozzájuk az adatokat. A magasabb szintű kommunikációs rétegek az alacsonyabb szintűekkel közös adatstruktúrákon keresztül cserélik ki az adatokat.

A socket hívások a hívó folyamat környezetében hajtódnak végre. Ily mó­don minden hiba szinkron módon jelentkezhet a hívónál.

A socket hívások megvalósítására az ún. socklib felhasználói szintű könyvtárat lehet használni. Ez a legtöbb UNIX-variánsban elérhető.

A socket létrehozása

A hálózati programozás legkényesebb (legnehezebben megérthető) része a socket létrehozásával, illetve konfigurálásával kapcsolatos. Ellentétben a fájlműveletek egyszerű open() rendszerhívásával, itt több rendszerhívást is használni kell, valamint a kitöltendő adatstruktúrák is bonyolultabbak. A socket a következő rendszerhívással hozható létre:

int socket(int domain, int type, int protokol);

ahol a domain esetünkben az AF_INET (más domainek is léteznek, mivel a socket nem csak hálózati kommunikációra használható), a típus stream vagy datagram (SOCK_STREAM, vagy SOCK_DGRAM), a protokoll praktikusan 0 (akkor más, ha a típuson és domainen belül többféle protokoll is létezik). A visszatérési érték a socket-leíró, vagy hibajelzés. Ez azonban önmagában nem elegendő adatok küldéséhez.

A socket kötése

A socket létrehozása csak a névtérben történik meg a socket() rendszerhívással. A socket a következő rendszerhívással köthető a lokális gépen egy porthoz:

int bind(int sockfd, const struct sockaddr *addr, int addrlen);

Ezt tipikusan a szerver alkalmazásokban használjuk. Az így kötött portra kapcsolódhatnak a kliens alkalmazások a következő rendszerhívással:

int connect(int sockfd, const struct sockaddr *addr, int addrlen);

A connect() segítségével a socket egy tényleges adatúthoz köthető, azaz egy másik gépen futó alkalmazásig (a másik gép adott portjáig) vezető hálózati kapcsolatot hozunk létre. Ez a hívás egyrészt felépíti az adatutat, másrészt hozzárendel egy helyi portot, amihez köti a socketet. Első ránézésre nincs különbség az előző bind()-hez képest, azonban a cím (addr) struktúra kitöltése különböző a két esetben. A cím kitöltéséhez egy struktúrát használunk:

struct sockaddr {

short int sin_family; /* Address family, esetünkben AF_INET */

char sa_data[14]; /* 14 bájtos protokoll cím */

}

Ez túl általános, ezért az AF_INET domainre készült egy jobb struktúra is:

struct sockaddr_in {

short int sin_family; /* AF_INET */

unsigned short int sin_port; /* portszám */

struct in_addr sin_addr; /* IP cím */

unsigned char sin_zero[8]; /* feltöltés sockaddr méretűre */

};

Ez a struktúra méretében megegyezik az előzővel (fontos a sin_zero feltöltése nullával), ezért használható helyette, csak a függvények hívásakor kell típuskonverziót végezni. Fontos megjegyezni, hogy a sin_port és a sin_addr hálózati bájtsorrendet követ (network byte order), tehát erre a formára kell hozni. Erre (illetve a visszaalakításra) a következö függvények valók: htons(), htonl(), ntohs() és ntohl(), ahol az első betű a forrás (n: network, h: host), a negyedik betű a cél, míg az utolsó a típus (l: long, s: short). A kommunikáció során az adatokat is célszerű ilyen bájtsorrendben küldeni, mivel így kikerülhetők a különböző architektúrák eltérő ábrázolási sorrendjéből fakadó problémák.

A fenti struktúrában szereplő in_addr kifejtése a következő:

struct in_addr {

unsigned long s_addr; /* 4 bájtos cím */

}

például:

struct in_addr server_addr =

inet_addr(„152.66.82.1”); /* hálózati bájt sorrenddel tér vissza */

A név szerinti címek leírására a következő struktúra, illetve kezelésükre a következő függvények használhatók:

/* FONTOS! Minden adat hálózati bájtsorrendben adott */

struct hostent {

char *h_name; /* elsődleges név */

char **aliases; /* alternatív nevek */

int h_addrtype; /* esetünkben AF_INET */

int h_length; /* a cím hossza bájtokban */

char **h_addr_list; /* a gép címei, nullával végződik */

}

#define h_addr h_addr_list[0]

/* a gép elsődleges címe */

/* A címek lekérdezése név alapján: */

struct hostent *gethostbyname(const char *hostname);

A socket használata

A szerverek a bind() hívás után bejövő adatokra várakoznak. Mielőtt ezt megtennék, egy rendszerhívással konfigurálják a várakozási sor hosszát:

int listen(int sockfd, int backlog); /* backlog: a sor hossza */

int accept(int sockfd, void *addr, int *addrlen);

Az operációs rendszer a portra beérkező kapcsolatokat egy sorban helyezi el, aminek hosszát határozza meg a backlog paraméter. A szerver az accept() rendszerhívással a sor elején álló kérést fogadja, az addr struktúrában megkapva annak paramétereit. A következő accept() a sorban következő kéréssel fog foglalkozni. Az accept visszatérési értéke egy új socketleíró, mely a klienshez létrejött kapcsolatban használható adatküldésre és fogadásra:

int send(int sockfd, const void *msg, int len, int flags);

int recv(int sockfd, void *buf, int len, unsigned int flags);

/* Mint minden fájlleíróra, itt is használható a read() és a write() */

Mindkét rendszerhívás az elküldött, illetve fogadott bájtok számával tér vissza, amely küldésnél kevesebb is lehet, mint az előírt.

A socket lezárása

A socket a shutdown() és a fájl műveleteknél megszokott close() rendszerhívásokkal zárható le. Az előbbinek paraméterként megadható, hogy a kétirányú adatforgalomból melyik irányt zárja le.

Tipikus szerver- és kliens-alkalmazás

Egy tipikus szerver-alkalmazás szerkezete UNIX alatt:

servsock = socket();

bind(servsock, ...);

listen(servsock, ...);

while (1) {

newsock=accept(servsock, ...);

if (fork()==0) { /* a gyerek kiszolgálja a kérést */

if (send(new_fd, „Hello, world!\n”, 14, 0) == -1)

perror(„send”);

close(new_fd);

exit(0);

} /* a gyerek vege */

close(new_fd); /* a szülőnek nem kell */

} /* while() */

A kliens programjának szerkezete:

#define SERVERPORT 1201

srvent = gethostbyname(server_hostname);

sockfd = socket();

srv_addr.sin_family = AF_INET;

srv_addr.sin_port = htons(SERVERPORT);

srv_addr.sin_addr = *((struct in_addr *)srvent->h_addr);

bzero(&(srv_addr.sin_zero), 8);

connect(sockfd, (struct sockaddr *)&srv_addr, sizeof(struct sockaddr))

numbytes = recv(sockfd, buf, MAXDATASIZE, 0)

buf[numbytes] = ‘\0’;

printf(„Received: %s”,buf);

...

close(sockfd);

Megjegyzések

Az itt ismertetett rendszerhívások nemcsak UNIX, hanem más operációs rendszer alatt is így használhatóak (könnyen írható olyan forráskód, mely UNIX, DOS, Windows, OS/2 alatt is lefordul). Legnagyobb különbség az egyéb rendszerhívásokban van, például új folyamatot másképp kell Windows és UNIX alatt indítani (de még a UNIX-verziók között is lehet választási lehetőség). Windows, OS/2, illetve újabb UNIX-verziók (például Solaris 2) esetén már használhatunk szálakat (thread) is (például a fent bemutatott tipikus szerverben a kérés kiszolgálására), míg régebbi UNIX-ok (például SunOS) esetén csak folyamatokban (process) gondolkozhatunk.

5.3.6. Állományrendszer implementációk

A mai modern UNIX-rendszerek számos különböző típusú állományrendszert támogatnak. Ezek két nagy csoportra oszthatók: lokális és távoli állományrendszerek. Az előbbi a rendszerhez közvetlenül csatlakoztatott berendezéseken tárolja az adatokat, míg az utóbbi lehetőséget nyújt a felhasználónak, hogy távoli gépeken elhelyezkedő állományokhoz férjen hozzá. A legtöbb modern UNIX-rendszerben megtalálható két általános célú állományrendszer a System V állományrendszer (s5fs) és a Berkeley Fast File System (FFS). Az s5fs az eredeti UNIX-állományrendszer. A System V rendszerek mindegyike és a kereskedelmi rendszerek nagy része is támogatja ezt az állományrendszert. Az FFS-t a 4.2 BSD vezette be, jobb hatékonyságú, robusztusabb és több funkcionalitást biztosít korábbi társánál. Kiváló tulajdonságai miatt széles körben elterjedt a kereskedelmi változatokban, sőt a SVR4-be is bekerült.

A korai UNIX-rendszerek egyetlenegy típusú állományrendszer kezelésére voltak képesek, így a rendszerek fejlesztői választásra kényszerültek. Mint azt majd a későbbiekben látni fogjuk, a Sun Microsystems által kidolgozott vnode/vfs interfész lehetővé tette több állományrendszer egyidejű alkalmazását is.

A következőkben először részletesen ismertetjük a s5fs felépítését, annak lemez szervezését és az alkalmazott adatszerkezeteket, majd rámutatunk azokra a hiányosságokra, amik elvezettek az FFS és a vnode/vfs interfész kidolgozásához. Ez a tárgyalásmód egyrészt segít megérteni az állományrendszerek általános felépítését és funkcióit, másrészt szépen mutatja a mérnöki fejlesztés, problémamegoldás logikus lépéseit.

5.3.6.1. A System V állományrendszer

Az állományrendszer felépítése

A Unix más operációs rendszerekhez hasonlóan logikai szinten, nem pedig diszk szinten kezeli az állományrendszert. A kernel logikai blokkokban szervezi az állományrendszert, egy blokk lehetséges mérete: 512*2k byte, ahol a k kitevő tipikus értékei a 0–5 tartományba esnek, megválasztásánál az alábbi szempontokat szokás figyelembe venni:

  • minél nagyobb a blokkméret, annál hatékonyabb az adathozzáférés, kisebb az adategységre jutó keresési időveszteség, nagyobb az átvitel sávszélessége,

  • minél kisebb a blokkméret, annál kisebb a tördelődés.

A kezdeti s5fs implementációban 512, majd a későbbiekben 1Kb-os blokkméretet alkalmaztak.

Az állományrendszer logikai szerkezete

A továbbiakban részletesen tárgyaljuk a s5fs lemezen található adatszerkezeteit. A lemezt az állományrendszer négy logikailag eltérő feladatot ellátó részre osztja:

boot blokk szuper blokk inode lista adat blokkok

Az egyes részek feladatai az alábbiak:

I. boot blokk – A rendszer elindulásához szükséges információkat tartalmazza. (Bár csak egyetlen állományrendszernél van szükség a boot blokk­ra, minden állományrendszer tartalmazza, legfeljebb üres).

II. szuperblokk – Az állományrendszerről tartalmaz a rendszer működéséhez szükséges metaadatokat, az állományrendszer állapotát írja le. Az itt tárolt információkat a későbbiekben részletezzük.

III. inode lista – Minden állományhoz pontosan egy inode tartozik, ezek alapján lehet az állományokra hivatkozni. A lista méretét a rendszergazda adja meg, meghatározva ezzel az állományrendszerben a maximális állományszámot. Az inode-ok és a lista szerkezetét a későbbiekben részletesen tárgyaljuk.

IV. adat blokkok – Ezek szolgálnak a fizikai adattárolásra.

A következőkben tekintsük át az egyes elemeket egy kicsit részletesebben.

A szuperblokk szerkezete

A szuperblokk az állományrendszer egészéről tartalmaz fontos információ­kat, ún. metaadatokat. A szuperblokkban tárolt legfontosabb információk:

  • az állományrendszer mérete,

  • a szabad blokkok száma,

  • a szabad blokkok listája,

  • a következő szabad blokk indexe,

  • az inode lista mérete,

  • a szabad inode-ok száma,

  • inode lista (tömb),

  • a következő szabad inode indexe,

  • lock mezők (inode, blokklista),

  • módosítás jelzőbit.

A továbbiakban a szuperblokk két legfontosabb adatszerkezetének, a szuperblokkon belül tárolt inode listának és a szabad blokkok listájának a felépítését és kezelését ismertetjük.

Az inode lista

Mint azt már korábban láttuk, az állományrendszer a szuperblokk után egy lineáris listában tárolja az inode-okat. Az inode tartalmaz egy típus mezőt, amely értéke 0 ha az inode szabad, vagyis felhasználható. Így a kernel viszonylag könnyen kereshet szabad inode-okat. Azonban az állományrendszerben gyakori esemény, hogy új inode-ra van szükség, hisz minden megnyitott állományhoz hozzá kell rendelni egyet, így a fenti megoldás nem elég hatékony. Ezért a szuperblokk tartalmaz egy fix méretű tömböt (szuperblokk inode lista), amelyet gyorsítótárként (cache) használ a szabad inode-ok sorszámainak tárolására. Minden egyes elem egy szabad inode sorszámát tárolja. Ha a rendszernek szabad inode-ra van szüksége (például fájl létrehozása), keresés helyett kiveszi a tömbben tárolt utolsó elemet. A tömb kezelését egy index nyilvántartása segíti. Ez megmutatja, hogy hány felhasználható elem (szabad inode sorszám) van még a tömbben, illetve éppen az utolsó felhasználható elemre mutat. Az 5.15. ábra felső részén az index a 44. elemre mutat, vagyis a 44. elem tartalmazza a legközelebb felhasználandó inode indexét. Ez a példában a 23-as. Amennyiben a kernel felhasznál egy inode-ot, akkor az indexet eggyel csökkenti (lásd az 5.15. ábra alsó részét).

Amikor kiürül a szuperblokk inode listája, a kernel elkezdi vizsgálni az (igazi) inode listát, szabad inode-okat keres, és hátulról kezdve teljesen feltölti a szuperblokkon belüli inode listát. Az utolsó megtalált szabad inode sorszám kerül a tömb első helyére. Ezt megjegyzett inode-nak is nevezik. Ennek nagy hatékonyság-növelő szerepe van, mert a kernel a legközelebbi feltöltéskor ettől a sorszámtól kezdődően kezdi el keresni a szabad inode-okat. Amikor a kernel felszabadít egy inode-ot, akkor megnézi, hogy van-e szabad hely a tömbben. Amennyiben igen, egyszerűen beteszi a sorszámot a tömb első szabad helyére, és eggyel növeli az indexet. Amennyiben a tömb tele van, megnézi, hogy a megjegyzett inode sorszáma kisebb-e, mint a felszabadítandó inode-é. Amennyiben kisebb, akkor a felszabadított inode-ot az algoritmus meg fogja találni a diszken, hiszen az a megjegyzett inode után következik, így nincs további teendő. Amennyiben a felszabadított inode sorszáma kisebb, mint a megjegyzetté, akkor annak helyére írja – ez lesz tehát a megjegyzett inode –, így biztosítva, hogy a kernel valóban a legkisebb sorszámú szabad inode-tól kezdje majd a következő keresést.

5.15. ábra. ábra - A szuperblokkban tárolt inode lista

A szuperblokkban tárolt inode lista


A szabad lemezblokkok listája

Mint azt korábban láttuk, az inode-ról egyértelműen el lehet dönteni, hogy szabad-e: amennyiben a típus mező értéke 0, akkor szabad, ellenkező esetben foglalt. Sajnos a lemezblokkok (adatblokkok) esetében pusztán azok tartalmának vizsgálatával nem lehet eldönteni, hogy szabadok-e, vagy használatban vannak, ezért a szabad lemezblokkokat adminisztrálni kell, azokat külön kell kezelni. Ennek érdekében a szuperblokk tartalmaz egy szabad blokklistát, amelynek a szervezése az alábbi.

A lista rögzített méretű, és a szabad blokkok sorszámait tartalmazza. Az első (a felhasználás sorrendjében utolsó) elem pedig egy olyan blokk sorszáma, amelyik szintén szabad blokkok sorszámait tartalmazza. (Tegyük fel, hogy egy blokk mérete 1 K, és a sorszámok 4 byte-osak. Így egy blokkban 1024/4 = 256 szabad blokk sorszámát lehet tárolni.)

Például a szuperblokkban tárolt szabad blokkok listájának egy lehetséges állapota:

A szuperblokkban lévő szabad blokkok listája

105

108

115

211

   

A 105-ös blokk tartalma

214

206

203

217

   

A 214-es blokk tartalma

313

315

317

321

   

Ezen lista kezelése hasonló a szabad szuperblokk inode lista kezeléséhez: egy index segítségével a kernel mindig nyilvántartja, hogy hányadik elem tartalmazza a következő szabad blokk sorszámát. Amennyiben szabad blokkra van szükség, a kernel visszaadja az első szabad blokk sorszámot. Ameny-nyiben felszabadul egy blokk, akkor a sorszámát a kernel beírja az első szabad helyre. Amennyiben nincs szabad hely már a listán, akkor a lista tartalmát bemásolja a felszabadított blokkba, és a visszaadandó blokk sorszámát beírja a lista utolsó helyére. Így a szabad blokkok listája egy újabb blokknyi (256) index hellyel bővül. Amennyiben a szuperblokkban tárolt szabad blokkok listája már csak egy elemet tartalmaz, akkor ez olyan blokkra mutat, amelyik újabb szabad blokkok sorszámait tartalmazza. Ha most újabb szabad blokkra van szükség, először a kernel a maradék egyetlen sorszám által mutatott blokk tartalmát (újabb szabad blokkok sorszámai) bemásolja a szuperblokk szabad blokk listájába (ekkor a blokk valóban szabaddá vált), majd visszaadja a sorszámot.

Lássunk egy példát!

A szuperblokkban tárolt szabad blokkok listája már csak egyetlen sorszámot tartalmaz, a 105-öst (amely újabb 256 szabad blokk sorszámait tartalmazza).

A szuperblokkban lévő szabad blokkok listája

105

   

   

A 105-ös blokk tartalma

214

206

203

217

   

Tegyük fel, hogy ekkor a kernel felszabadítja a 934-es blokkot és visszateszi a szabad blokkok listájára.

A szuperblokkban lévő szabad blokkok listája

105

934

  

   

A 105-ös blokk tartalma

214

206

203

217

   

Tegyük fel, hogy ezek után szükség van egy szabad blokkra. A kernel visszaadja a 934-es blokkot. Ezután újabb blokkra van szükség. Ekkor a kernel a 105-ös blokk tartalmát bemásolja a szuperblokk szabad blokk listájába, majd visszaadja a 105-ös blokkot.

A szuperblokkban lévő szabad blokkok listája

214

206

203

217

   

A 214-es blokk tartalma

5.16.ábra. táblázat - A példa állomány lemezblokkjainak elhelyezkedése

 

315

317

321

   

Az eddigiek során számos alkalommal hivatkoztunk már az inode-okra, vázlatosan ismertettük a rendeltetését, azonban még nem adtuk meg a belső szerkezetét, a benne tárolt információkat. A UNIX-állományrendszerben be­töl­tött központi szerepe miatt az alábbiakban részletesen ismertetjük az inode felépítését.

Az inode

Az inode a fizikai állományhoz tartozó azonosító. Az állományrendszer minden egyes állományához pontosan egy inode tartozik. Az állományrendszerben az inode-ok diszken találhatók, azonban a gyorsabb működés érdekében a kernel cache-eli azokat a memóriában. A diszken tárolt inode számos, az állományhoz kapcsolódó információt tárol:

  • tulajdonosazonosító (UID, GID),

  • állomány típusa – reguláris, könyvtár, FIFO, karakteres vagy blokkos berendezés,

  • állomány-hozzáférési jogosultságok (tulajdonos, csoport, illetve a világ számára, olvasási, írási, illetve végrehajtási jogok),

  • időcímkék:

    • az utolsó állományhozzáférés ideje,

    • az utolsó állománymódosítás ideje,

    • az utolsó attribútum módosítás ideje (inode módosítás),

  • linkek száma (hány könyvtári bejegyzés hivatkozik az adott fizikai állo­mányra),

  • címtábla (mutatók adatblokkokra – 10 db direkt, 1 db indirekt, 1 db kétszeres indirekt és 1 db háromszoros indirekt mutató),

  • állományméret.

A kernel a memóriában cache-eli az inode-okat (ezeket in-core inode-oknak is nevezzük). Ezek egy kicsit más felépítésűek, mint a diszken tárolt másolatuk. Tartalmazzák a diszken tárolt inode összes információját, azonban néhány további információval ki vannak egészítve:

  • az in-core inode státusa

    • zárolt (locked),

    • folyamat vár rá,

    • eltér a diszken lévő változattól

    • attribútum írás következtében,

    • adat írás következtében,

  • az állomány mount pont, vagyis az adott pontra egy másik állományrendszer csatlakozik,

  • az állományt tartalmazó állományrendszer logikai berendezés azonosítója,

  • az inode sorszáma (a diszken az inode-ok az inode listában sorszámuk által meghatározott, rögzített helyen találhatóak, nincs szükség a sorszám tárolására),

  • mutatók más in-core inode-okra (hash sorok, szabad lista),

  • hivatkozásszámláló (hány példányban van nyitva az állomány).

A hivatkozásszámláló fontos szerepet játszik a memóriabeli inode-ok kezelésében. Mivel a számláló megmutatja, hogy az adott állomány hány példányban van nyitva, így amíg az nagyobb nullánál, addig az inode aktív, használatban van. Amennyiben a számláló értéke nulla, akkor az inode inaktív, éppen senki sem használja, így az a szabad listára kerülhet, ahonnan majd a kernel újra allokálhatja, és esetleg már egy másik állományhoz rendelheti.

Reguláris állományok szerkezete

A UNIX-rendszer az indexelt allokáció egy speciális formáját alkalmazza a fájlokhoz tartozó adatblokkok lefoglalásakor. Az indexelt allokáció lehetővé teszi az adatterület blokkonkénti lefoglalását. Így a fájl egyes adatblokkjai a lemez tetszőleges blokkjában tárolhatók. A fájlhoz tartozó adatok elhelyezkedését az inode-ban található címtábla (13 mutató) írja le.

Tegyük fel, hogy a rendszer diszk blokkjai 1 K-sak, és 4 byte-on lehet a blokkokat címezni. Az inode címtáblájának első 10 mutatója egy-egy 1 K-s diszk blokkra mutat. Ezek a direkt elérésű blokkok. A következő mutató egy olyan diszk blokkra mutat, amely további mutatókat tárol, most már adatokat tartalmazó blokkokra. Mivel egy blokkba 256 mutató fér el, így a fenti egyszeres indirekt címzéssel további 256 K adatot lehet megcímezni. A következő mutató kétszeres indirekt mutató, vagyis egy olyan blokkra mutat, amely 256 mutatót tartalmaz, amelyek mindegyike egy-egy további indirekt blokkra mutat. Vagyis most hivatkozáskor az első két lépésben indirekt blokkokat kapunk, és csak a harmadik lépésben jutunk el az adatokhoz. Ezzel a módszerrel 64 M adatot lehet megcímezni. A következő, egyben utolsó mutató egy háromszoros indirekt mutató, vagyis még a harmadik hivatkozás is 256 mutatót tartalmazó indirekt blokkra mutat, és onnan egy újabb referenciával juthatunk el az adatokhoz. Ezzel a módszerrel 16 G adatot lehet címezni. Tehát a fent vázolt struktúrával összesen:

10 db direkt blokk 10 K

1 db egyszeres indirekt blokk 256 K

1 db kétszeres indirekt blokk 64 M

1 db háromszoros indirekt blokk 16 G

adatot lehet tárolni. A valóságban persze ennél kevesebbet, mert az inode állományhossz mezője is 4 byte, a méretet byte egységben tárolják, így ez 4 G-ra korlátozza a maximális állományméretet.

A jobb érthetőség érdekében tekintsünk két példát: (a blokkméret továbbra is 1 Kb és a blokkokat 4 byte-on címezzük, így egy blokkban 256 blokkcím tárolható. A példához használt állomány lemezblokkjait az 5.16. ábra mutatja.)

1. példa

Tegyük fel, hogy egy fájl 9500-adik byte-ját akarjuk olvasni, amihez a kernelnek meg kell találni az ehhez tartozó blokk címet.

A 9500-adik byte a 9. direkt blokkban van (9*1024 = 9216), ott pedig a 284-edik (a blokkokat 0-tól kezdődően sorszámozzuk). A példában az inode 9. direkt blokkra mutató pointer a 3361. lemezblokkra mutat, vagyis a 3361. blokk 284. byte-ja a keresett adat.

2. példa (5.16. ábra)

Tegyük fel, hogy a 355 000-es byte-ot akarjuk olvasni. Ehhez kétszeres indirekt blokkot kell használni, mert a 10 direkt és az egyszeres indirekt blokkal 10*1024 + 256*1024 = 272384 byte-ot lehet elérni. Innen számítva a 82616. byte-ot keressük. Az a kétszeres indirekt blokk első (0-ás indexű) mutatója által kijelölt egyszeres indirekt blokkban van, méghozzá annak 80. elemében (80*1024 = 81920). Az így kijelölt blokk 696. byte-ja a keresett adatelem. A fenti példa esetén a kétszeres indirekt blokk pointere a 7147. diszk blokkra mutat, annak az első pointere a 2456. blokkra, ami tartalmazza 80. elemként a keresett adatokat tartalmazó blokk címét, a 3121-et. Ezen a blokkon belül a 696. byte-ot kerestük.

5.19.ábra. táblázat - /etc könyvtár egy lehetséges tartalma

4016

       

2328

       

45344

       

0

       

0

       

12121

       

0

       

1004

       

118

 

3361-es

     

3361

——>

blokk

     

322

       

7147

——>

2456

——>

    

333

       
   

80.

3121

———>

3121-es

 
      

blokk

 

A fenti séma problémája, hogy az indirekciók időigényesek, nagy fájlok esetén lassul az adatelérés. A bevezetés időszakára jellemző statisztika szerint azonban az állományok kb. 85%-a kisebb 8 K-nál (így elférnek a direkt blokkokban), és ezen állományok kb. 48%-a kisebb 1 K-nál! Ebből következik, hogy indirekt elérésre ritkán van szükség, így az effektív adathozzáférés gyors. Nagy fájlok esetén pedig egyrészt a felhasználók is türelmesebben viselik a hosszabb keresési időket, másrészt a rendszerek egyéb megoldásokat is alkalmaznak a gyorsítás érdekében (például buffer-cache).

Az állománykezelés logikai sémája és adatszerkezetei

A UNIX a fájlkezelés multiprogramozott rendszerekben felmerülő kérdéseire a következő választ adja:

  • A folyamatoknak csak megnyitáskor kell névvel hivakozniuk egy fájl­ra. A megnyitás egy számot (logikai perifériaszám) ad vissza a folyamatnak, a további műveletekben (read, write) ezzel hivatkozhat a fájlra.

  • Egy folyamat többször is megnyithat egy fájlt, minden megnyitáskor önálló logikai periféria jön létre, amelyek azonban külön-külön fájlmutatóval ugyan, de ugyanazt a fizikai fájlt jelentik. Így egy folyamat különböző logikai perifériaként ugyannak a fájlnak különböző részeit használhatja különböző fájlmutatókkal.

  • Több folyamat megnyithatja és használhatja ugyanazt a fájlt párhuzamosan, a read és write rendszerhívások atomicitása teljesül, azonban hosszabb távú szinkronizáció megoldása külön műveleteket igényel.

  • A gyermek folyamatok öröklik a szülők logikai perifériáit. Ha a gyermek és a szülő ugyanazt a logikai perifériát használja, a gyermek és a szülő fájlműveletei a CPU-ütemezéstől függő sorrendben írják, vagy olvassák a fájlt ugyanazon fájlmutató használatával.

A s5fs állományrendszerben a logikai állománykezelés három szintre tagozódik, amelyekhez egy-egy fontos adatszerkezet tartozik. Az alábbiakban az egyes lépcsőkhöz tartozó adatszerkezeteket (folyamatonkénti állományleíró tábla, globális állománytábla, és inode tábla) és a hozzáférésben betöltött funkciójukat ismertetjük.

Folyamatonkénti állományleíró tábla

Minden egyes folyamathoz tartozik egy állománytábla. Mint azt a neve is mutatja, ez egy folyamathoz tartozó adatszerkezet. A tábla egy bejegyzése egy logikai perifériának felel meg. A folyamatok állománytáblájuk bejegyzéseinek indexeit használják a logikai periféria azonosítására. Ebben a táblában minden, a folyamat által elérhető, megnyitott állományhoz legalább egy mutató tartozik. A mutató a globális állománytábla megfelelő elemére mutat.

Globális állománytábla

Minden egyes open rendszerhívás hatására létrejön egy bejegyzés (struktúra) a globális állománytáblában, amely az adott állománynévhez rendelődik, tartalmazza a megnyitás módját, jogosultságokat, egy fájlmutatót, hogy hol tartunk az állományban az olvasással/írással, illetve egy hivatkozásszámlálót, amely megmondja, hogy hány folyamatonkénti állományleíró tábla bejegyzés mutat rá. (A globális állománytáblában egy állománynévhez több bejegyzés is tartozhat, itt a bejegyzések munkamenetet tárolnak.) A globális állománytábla használata az állományok osztott használatát teszi lehetővé.

Inode tábla (in-core inode tábla)

Minden egyes megnyitott állományhoz tartozik egy inode a memóriában, tartalmaz egy hivatkozásszámlálót, hogy az adott nevű fizikai állományt hány példányban használják, vagyis hány globális állománytábla bejegyzés mutat rá.

A folyamatonkénti állományleíró tábla első három eleme (0, 1, 2) a standard input-, a standard output-, illetve a standard error logikai perifériákat jelöli. Ezeket a folyamatok indulásukkor megnyitva kapják.

A UNIX-ban az állományok megnyitására az open rendszerhívás szolgál. Ennek alakja:

fd = open(path, flag, mode);

Kötelezően meg kell adni a megnyitandó állomány elérési útját (path) és a megnyitás módját. A rendszerhívás egy egész számot (fd) ad vissza, ami tulajdonképp nem más, mint egy index a folyamatonkénti állományleíró táblába.

Az alábbi példában megnyitunk három állományt, majd az egyik állományleírót megkettőzzük. Az 5.17. ábra mutatja, hogy a rendszerhívások hatására milyen bejegyzések jelennek meg a fent ismertetett három adatszerkezetben. Az ábrán a nyilak mutatókat jelölnek.

fd1 = open(„/etc/group”, O_RDONLY);

fd2 = open(„readme”, O_RDWR);

fd3 = open(„/etc/group”, O_WRONLY);

fd4 = dup(fd2);

Az 5.17. ábrán jól látszik, hogy minden egyes open rendszerhívás hatására a globális állománytáblában létrejön az adott állománymegnyitáshoz tartozó bejegyzés. A jelölt számok hivatkozásszámlálók, megadják, hogy a folyamatonkénti állományleíró táblák hány bejegyzése mutat az adott elemre. Bár a jobb áttekinthetőség érdekében az ábrán nem tüntettük fel, a globális állománytábla bejegyzései tárolják az állományból/ba történő olvasás/írás pillanatnyi pozícióját (fájlmutató), vagyis egy indexet, hogy hol tart az adott művelet az állományban.

5.17. ábra. ábra - Az open és dup rendszerhívások hatása az állománykezeléssel kapcsolatos adatszerkezetekre

Az open és dup rendszerhívások hatása az állománykezeléssel kapcsolatos adatszerkezetekre


Az open rendszerhívás végrehajtásakor bejegyződik egy mutató a folyamatonkénti állományleíró táblába is, ami az adott állománymegnyitáshoz tartozó globális állománytábla bejegyzésre mutat. A dup rendszerhívás a paraméterül kapott állományleírót megduplázza és beírja a folyamatonkénti állományleíró tábla első szabad helyére. (Ezt a standard bemenet és kimenet átirányítására hatékonyan ki lehet használni.) Az ábrán jól látszik, hogy a dup rendszerhívás hatására egy újabb mutató mutat a globális állománytábla readme állományhoz tartozó bejegyzésére (ezt a hivatkozásszámláló is jelzi). Míg a globális állománytábla munkameneteket reprezentál, addig az inode tábla magukat az állományokat. Ebből adódóan minden egyes állományhoz és nem pedig az állomány megnyitásokhoz tartozik egy-egy bejegyzés. A fenti példa állománymegnyitásai így két új bejegyzést hoznak csak létre az inode táblában, hisz két megnyitás ugyanarra a fizikai állományra vonatkozik (ami persze két különböző munkamenetet jelent). A hivatkozásszámláló az egyes inode tábla bejegyzésekre mutató globális állománytábla bejegyzések számát mutatja.

Állományok és könyvtárak

Az állomány logikailag egy adattároló egység. A felhasználónak lehetősége van a fájl adatainak mind szekvenciális (sequential), mind pedig címzett elérésére (véletlen – random access), a kernel segítségével számos műveletet végezhet a fájlokon. Fontos megjegyezni, hogy a kernel nem értelmezi az állományban tárolt adatokat, nem feltételez semmilyen magasabb rendű struktúrát, egyszerűen byte-ok folyamának tekinti a fájlt. (Amennyiben szükség van valamilyen magasabb rendű szerkezetre – például rekordra – azt az alkalmazásoknak kell kezelni.)

A UNIX a felhasználó szemszögéből tekintve az állományokat egy hierarchikus fa struktúrájú névtérbe rendezi (5.18. ábra).

5.18. ábra. ábra - A UNIX-állományrendszer könyvtárstruktúrája

A UNIX-állományrendszer könyvtárstruktúrája


A nevek a / és a NULL karakter kivételével tetszőleges ASCII-karaktert tar­tal­mazhatnak. A gyökér (root) könyvtárat a „/” név jelöli. A hierarchikus névtérből adódóan egy könyvtáron belül egyedi állományneveknek kell szerepelni, más könyvtárban azonban szerepelhet egy állomány azonos névvel (ekkor az egyediséget az eltérő elérési út biztosítja).

A UNIX támogatja az aktuális könyvtár fogalmát, amelyhez képest relatív elérési utat is lehet használni. Az aktuális könyvtárat a chdir rendszerhívással lehet megváltoztatni.

Egy állományhoz tartozó könyvtár bejegyzést az állományra mutató hard linknek vagy egyszerűen csak linknek nevezünk. Minden állományra több link is mutathat, akár más-más könyvtárakból is. Ebből adódóan a UNIX-ban egy állomány nem egyetlen adott névhez kötődik, nincs egyedi neve. A név nem az állomány attribútuma, van azonban egy ún. link számláló minden egyes állományhoz, amely megadja, hogy hány néven lehet hivatkozni az adott állományra. (Ez az inode-ban tárolt hivatkozásszámláló megmutatja, hogy hány könyvtári bejegyzés mutat a fájlra.) Egy állomány addig létezik, amíg a link számlálója nagyobb nullánál. Amikor a számláló nullává válik, az állomány már elérhetetlen, így az általa használt diszk terület felszabadítható. Az állomány bármelyik linken keresztül teljesen egyenrangúan érhető el.

A s5fs könyvtárszerkezete

A Unix alatt a könyvtárak is állományok, de speciális szerkezettel bírnak. Minden egyes könyvtár tartalmaz két különleges bejegyzést: a . és a .. bejegyzéseket az aktuális könyvtárhoz, illetve a szülőkönyvtárhoz. A s5fs könyvtárak szerkezete a következő: minden bejegyzés tartalmaz egy 2 byte-os inode számot, amely az adott nevű állomány inode-ját adja meg, illetve egy 14 karakterből álló állománynevet. Így minden egyes bejegyzés 16 byte-ot foglal. Például a /etc könyvtár tartalmazhatja az 5.19. ábra szerinti adatokat.

Relatív byte-cím

inode száma (2 byte)

Állománynév (14 byte)

0

83

.

16

2

..

32

1798

group

48

1276

networks

Ezek után egy adott nevű állományhoz tartozó inode megkeresése elég egyszerű művelet: a kernel az adott könyvtárban végez egy lineáris keresést a név alapján, és a hozzá tartozó inode-ot a megfelelő könyvtár bejegyzésből ki tudja olvasni.

Az s5fs értékelése

Az s5fs-t az egyszerű felépítése emeli ki a többi állományrendszer közül. Ez az egyszerűség nagyon előnyös az érthetőség, áttekinthetőség és megvalósítás szempontjából, azonban a megbízhatóság, teljesítmény és funkcionalitás területén kívánnivalókat hagy maga után. A megbízhatósági problémák elsődleges forrása a szuperblokk kezelésével kapcsolatos. A szuperblokk az állományrendszer szempontjából életbevágóan fontos információkat, mint például a szabad blokkok listája, a szabad inode-ok száma, tartalmaz. A s5fs-ben minden egyes állományrendszer csak egyetlen példányban tartalmazza a szuperblokkot. Ebből adódóan ha a szuperblokk megsérül, a teljes állományrendszer használhatatlanná válhat.

A teljesítmény problémák is több okra vezethetők vissza. Az s5fs együtt kezeli az inode-okat, azokat az állományrendszer elején tárolja, majd utána következnek az adatblokkok. Ebből adódóan egy állomány hozzáférés esetén először be kell olvasni az inode-ot, majd utána a fizikailag távol elhelyezkedhető adatblokkot. Ez gyakran jelentős fejmozgásokat igényelhet, ami lassítja az adathozzáférést. Másrészt az inode-ok kiosztása is véletlenszerű, nem követi az esetlegesen meglévő logikai állománycsoportokat (például azonos könyvtárban lévő állományok). Nemcsak az inode-ok kiosztása véletlenszerű, hanem az adatblokkoké is. Bár kezdetben a szabad blokkok rendezetten tárolódnak, a folyamatos használat (foglalás, felszabadítás) hatására ez a rendezettség megszűnik. Egy állomány logikailag szomszédos blokkjai véletlenszerűen, akár távoli sávokon is elhelyezkedhetnek, aminek hatására a szekvenciális hozzáférés lelassulhat. A lemez blokkok mérete is problémát jelent. A korai, SVR2 rendszerekben 512 byte-os blokkokat használtak. Ennek hatására a belső tördelődést alacsony szinten lehetett tartani (átlagosan a blokkméret fele), ennek ára viszont, hogy egy lemezhozzáféréssel kevesebb adatot lehet beolvasni. A SVR3-tól kezdődően 1 K-s blokkokat használtak, ami javította az adatátvitelt, de növelte a tördelődést. Ez a probléma egy rugalmasabb allokációs módszer igényét vetette fel.

Végezetül a s5fs néhány funkcionalitásbeli problémával is küszködik. Ezek közül talán a legjelentősebb korlátozás az állománynevek 14 karakteres maximális hossza. A korai időkben ez minden bizonnyal elegendő volt, azonban manapság felettébb rontja a rendszer kereskedelmi értékét, hisz a mai felhasználók már egyre inkább megszokták, hogy hosszú, beszédes neveket adjanak az állományaiknak. Másrészt számos alkalmazás, mint például a fordítók, szövegfeldolgozók munkájuk során új kiterjesztéseket, tagokat fűznek a feldolgozandó állomány nevéhez. Ebben az esetben a 14 karakteres állományhossz megkeseríti az ilyen alkalmazás íróinak az életét.

Mint azt korábban láttuk, a könyvtárszerkezetben minden állományhoz egy 16 byte-os bejegyzés tartozik. Ebből 14 byte az állomány neve (innen a 14 ka­rakteres maximális állománynév korlátozás) és a maradék két byte azonosítja az állományhoz tartozó inode-ot. Ebből viszont következik, hogy egy állományrendszerben maximum 16 biten megkülönböztethető, vagyis 65 535 inode – vagyis állomány lehet. Ez a mai alkalmazások tükrében megengedhetetlen korlátozásnak tűnik.

Ezek a problémák motiválták a Berkeley Fast File System állományrendszer kidolgozását. Az alábbiakban vázlatosan kitérünk a fenti problémák megoldására.

5.3.6.2. A Berkeley FFS állományrendszer

Az FFS az s5fs számos hiányosságát próbálta meg orvosolni. A s5fs minden funkcionalitását megtartotta, a kernel adatszerkezetek nagy része, illetve a rendszerhívások kezelési algoritmusa is változatlan maradt. A legjelentősebb átalakítást a lemez használatában, a lemezen lévő adatszerkezeteken és a szabad blokk allokáción hajtották végre.

Az FFS-nél a korábban látott partíció csoportosítás mellett bevezették a cilinder csoportokat (cylinder groups), ami valahány folytonos cilindert tartalmazott. Ezzel a kiegészítő szervezéssel lehetővé vált, hogy a Unix az egymáshoz tartozó adatokat egy cilinder csoporton tárolja, miáltal minimalizálni lehet a fejmozgást. (Az adatátvitel szempontjából a legjelentősebb időköltsége a fejmozgatásnak van.)

Ez a kiegészítés újabb metaadatok megjelenését vonta maga után, amiket cilinder csoportonként a csoport elején tárolnak. A s5fs megbízhatósági problémája elsősorban abból fakadt, hogy az állományrendszer egészéről életbevágóan fontos információkat tároló szuperblokk csak egy példányban, a boot blokk után került tárolásra. Az FFS-nél a szuperblokkról minden egyes cilinder csoport tartalmaz egy másolatot. Ezek a másolatok úgy vannak elhelyezve a cilinder csoportokban, hogy egyetlen sáv, cilinder vagy lemez sem tartalmazza az összes másolatot, így mechanikai sérülésekkel szemben is kellő védelmet biztosít.

Mint azt már láttuk, a blokkméret meghatározásakor ellentmondó szempontokat kell figyelembe venni. Minél nagyobb blokkokat használunk, annál jobb az adatátviteli sebesség, viszont annál nagyobb a belső tördelődés. Az FFS ezt a problémát töredékek (fragment) alkalmazásával próbálja orvosolni. Egy állomány minden blokkja azonos méretű (a minimális blokkméret 4 kB), azonban az utolsó blokk tartalmazhat egy vagy több, külön címezhető és allokálható folyamatos töredékblokkot. Meg kell jegyezni, hogy a töredékblokkok maximális száma az állományrendszer létrehozásakor kerül rögzítésre: 1, 2, 4 vagy 8 lehet. Ezzel a struktúrával 4k-s blokkokat és 8 töredékblokkot alkalmazva 512 byte-os alsó határt lehet elérni, ami megegyezik a szektormérettel. A nagyobb blokkméret alkalmazásának egy járulékos előnye, hogy 232 byte (4 GB) méretű állományokat is két indirekciós szinten lehet címezni. Az FFS általában ebből kifolyólag nem is alkalmazza a háromszoros indirekt blokkokat.

A lemezblokk töredékek használatára érvényes néhány korlátozás. Egy állományblokknak egyetlen lemezblokkban kell lennie. Szomszédos lemezblokkok összefüggő töredékei nem vonhatók össze. Továbbá, ha egy állomány utolsó blokkja több töredéket is tartalmaz, ezen töredékeknek összefüggőeknek kell lenniük és azonos lemezblokkon kell elhelyezkedniük. Ezen adatszerkezet csökkenti a lemez tördelődését, használatához azonban módosítani kell a szabad lemezblokkok nyilvántartását: a listát le kell cserélni az összes töredékblokkot nyilvántartó bittérképre. A többlet adminisztráció mellett bizonyos esetekben adatok átmásolására is szükség van. Amikor például egy olyan állományt próbálunk meg növelni, amelynek utolsó blokkja egyetlen töredéket foglal el, és ugyanazon blokk többi töredéke más állományokhoz tartozik, akkor először allokálni kell egy új blokkot, ami több szabad töredéket tartalmaz, majd a töredéket át kell másolni. Lassan, kis lépésekben bővülő állomány esetén számos ilyen másolásra lehet szükség. Ebből adódóan a jobb hatékonyság érdekében az alkalmazások, amikor csak lehetséges, teljes blokkokat kell hogy az állományba írjanak.

Lemezblokk allokációs politika

Az FFS lemezblokk allokációs politikájának célja, hogy az egymáshoz kap­csolódó információkat egy helyen tárolja, és a szekvenciális hozzáférésre opti­malizálja az allokációt. A s5fs-nél láttuk, hogy listában tárolja a szabad blokkokat és inode-okat. Bár kezdetben ezek lemezelfordulás szempontjából opti­ma­lizáltak voltak, a használat során teljesen véletlenszerűvé válnak, gyakorlatilag az operációs rendszernek semmilyen befolyása sincs az allokálandó adatblokk vagy inode elhelyezkedésére. Ezzel szemben az FFS itt is a cilindercsoportokat alkalmazza. Az alábbiakban a teljesség igénye nélkül felsorolunk néhány szempontot, amit az FFS az allokáció során figyelembe vesz.

  • Az FFS az egy könyvtárban lévő állományok inode-ját megkísérli ugyanarra a cilindercsoportra helyezni. Ennek ésszerű magyarázata, hogy számos parancs, mint például az ls is, gyors egymásutánban olvassa a könyvtár inode-jait, így ha azok egy cilindercsoporton helyezkednek el, a fejmozgások csökkenthetők.

  • Minden új könyvtárat más cilindercsoportra helyez, hogy az adatokat egyenletesen terítse szét a lemezen.

  • Egy állományhoz tartozó adatblokkokat megpróbálja ugyanarra a ci­lin­dercsoportra helyezni, ahol az állomány inode-ja is található, hisz tipikusan az inode-ot és az adatokat együtt használja.

  • A nagy állományokat „szétkeni” a cilindercsoportokon. Amikor az állo­mányméret eléri a 48 kB-ot, új cilindercsoportra lép, majd 1 MB után újra stb. Ezzel meg tudja akadályozni, hogy egy óriási állomány feltöltse a tel­jes cilindercsoportot. A 48 Kb-os határ a direkt blokkokon tárolható méretet jelöli (az FFS-nél 12 db direkt blokk található az inode-ban), így a direkt blokkokban tárolt adatok azonos cilindercsoportra kerülnek az inode-dal.

  • Az egymást követő blokkokat – amennyiben az lehetséges – lemezelfordulás szerint optimálisan allokálja.

Funkcionális bővítések a s5fs-hez képest

Hosszú állománynevek

Mint azt láttuk, a 16 bájtos könyvtár bejegyzés miatt a s5fs-nél a maximális állománynév 14 karakter lehetett. Ez a mai alkalmazásoknál elég húsbavágó korlátozást jelent, így az FFS megalkotói egy eltérő könyvtárszerkezetet dolgoztak ki, ami feloldja ezt a korlátozást. A könyvtárbejegyzés egy rögzített és egy változó részből áll. A rögzített rész tartalmazza az inode számát, az allokált területet, illetve, hogy ebből a területből maga az állománynév mennyit foglal le. A rögzített részt követi a változó hosszúságú rész, ami a null karakterrel lezárt állománynevet tartalmazza, négy byte-os margóra igazítva. (5.20. ábra). Ebben az esetben a maximális állománynév hossz 255 karakter. Egy probléma merül fel ezzel a szerkezettel kapcsolatban: mit kell tenni, ha egy könyvtárbejegyzést törlünk? Ekkor a rendszer a törölt bejegyzés területét hozzáolvasztja az előző bejegyzés területéhez, a változást feltüntetve az allokált terület nagyságában (5.20. ábra jobb oldala).

Egyéb bővítések

Az FFS vezette be a szimbolikus link fogalmát. A szimbolikus linkek kiküszöbölik a hard linkek számos korlátját. A szimbolikus link tulajdonképpen egy olyan speciális állomány, ami egy másik állományra, az ún. célállományra mutat. A szimbolikus linket az inode típus mezője alapján lehet felismerni, és tulajdonképpen csak a célállomány elérési útját tartalmazza.

5.20. ábra. ábra - Az FFS könyvtárszerkezete

Az FFS könyvtárszerkezete


Továbbá az FFS bevezette a kvóta mechanizmust, amivel korlátozni lehet az egyes felhasználók rendelkezésére álló állományrendszer erőforrásokat.

Az FFS teljesítménye

Az FFS teljesítménye jelentősen túlszárnyalja a s5fs teljesítményét. Mérések szerint a s5fs olvasás esetén a megközelítőleg 30 Kb/s-os átbocsátóképességét (1 Kb-os blokkok használata mellett) az FFS megközelítőleg 220 Kb/s-ra javította (4 Kb-os blokkokat és 1 Kb-os töredékblokkokat alkalmazva). A CPU-kihasználtság is jelentősen növekedett: a s5fs körülbelüli 1%-os kihasználtságát sikerült majd megnégyszerezni. Írás esetén az eltérés nem ennyire domináns, de ott is jelentős. (A megadott adatok VAX/750 hardveren elvégzett mérésekből származnak.)

5.3.6.3. Az állományrendszerek megvalósításának újabb megközelítése

A korai UNIX-rendszerek azt a filozófiát követték, hogy egy rendszerben csak egyetlen állományrendszer létezik. Ebben a megközelítésben az állományok leírására elégséges volt az inode absztrakció. Hamar felismerték azonban, hogy ez a korlátozás indokolatlan, több állományrendszer (beleértve a több típust is) számos előnnyel kecsegtet. A megvalósításához azonban már nem elegendők az inode-ok. Az új leíró adatszerkezet a virtuális csomópont (vnode) és a virtuális állományrendszer (vfs).

Az új absztrakció bevezetésének célja, hogy

  • egyszerre támogasson több állományrendszert (UNIX, nem UNIX),

  • különböző diszk partíciók tartalmazhassanak különböző állományrendszert, viszont csatlakoztatás (mount) esetén egységes „képet” kell hogy mutassanak,

  • támogassa a hálózaton történő állományok osztott használatát,

  • modulárisan bővíthető legyen.

Az absztrakciót tulajdonképpen két adatszerkezet a vnode és a vfs, illetve azok kezelési módja valósítja meg. Először vizsgáljuk meg az inode szerepét átvevő vnode-ot. Az 5.21. ábra mutatja a vnode szerkezetét. Mint az az ábrán jól látható, az adatszerkezet három részre tagolódik: az adatmezőkre, a virtuális függvényekre valamint a segédrutinokra, és makrókra. Az adat­mezők egyes elemei töltik be az inode megfelelő funkcióinak a szerepét: megjelenik a típusmező (v_type), ami a vnode által leírt állomány típusát adja meg, található itt hivatkozásszámláló (v_count), mount információ (v_vfs­mountedhere) stb. Ezenfelül megtalálható itt két mutató (v_data, v_op), amelyek implementációfüggő valódi, a virtuális csomópont által elfedett adatszerkezetekre mutatnak, amelyekre a konkrét állományrendszerek kezeléséhez, karbantartásához van szükség. A v_data mező s5fs esetén pontosan egy inode-ra mutat. A v_op mező által mutatott táblában pedig a valódi adatszerkezeteken az absztrakt állományműveleteket konkrétan végrehajtó függvények címei találhatók.

5.21. ábra. ábra - A vnode szerkezete

A vnode szerkezete


A vnode-ban megtalálható virtuális függvények szerepe, hogy az állományműveleteket konkrét állományrendszer implementációtól függetlenül ki lehessen adni és majd a vnode kezelő mechanizmusa gondoskodik róla, hogy az adott absztrakt műveletet megvalósító konkrét, az adott állományrendszerhez tartozó állományművelet hajtódjon végre. Ehhez a vnode absztrakció definiál egy művelethalmazt (állomány megnyitás, olvasás, írás stb.) amit minden konkrét állományrendszer implementációban meg kell valósítani. Így egy indexelési és mutató indirekción keresztül el lehet jutni a konkrét műveletet megvalósító függvényhez.

A vnode használatával a korábban látott kettős indirekció (folyamatonkénti állományleíró tábla, globális állománytábla bejegyzés, inode tábla bejegyzés) egy újabb elemmel bővül (5.22. ábra).

5.22. ábra. ábra - A vnode-ot is tartalmazó állományrendszer hozzáférés logikai sémája

A vnode-ot is tartalmazó állományrendszer hozzáférés logikai sémája


A virtuális állományrendszer megvalósításához egy, a vnode-hoz hasonló adatszerkezetet, a vfs-t használják. Ennek felhasználásával több eltérő típusú állományrendszert egységesen lehet kezelni az alábbi módon (5.23. ábra).

Az 5.23. ábrán jól látszik, hogy van egy root állományrendszer, amire a többi állományrendszert csatlakoztatni lehet (fel lehet mount-olni). A rendszer minden egyes állományrendszer típushoz tartalmaz egy vfs struktúrát, ami tárolja az állományrendszerhez kapcsolódó, az állományrendszer kezeléséhez elengedhetetlen információkat. Továbbá minden egyes olyan virtuális csomópontban (vnode), amely egyben egy állományrendszer gyökér csomópontja, a VROOT jelzőbit be van billentve.

5.23. ábra. ábra - Több állományrendszer használata vfs-sel

Több állományrendszer használata vfs-sel


5.3.6.4. Speciális állományrendszerek

Az s5fs és az FFS állományrendszer a UNIX általános célú lokális állományrendszerei. Amennyiben az állományrendszernek távoli hozzáférést is támogatnia kell, akkor a kialakítását ezekhez az igényekhez kell alakítani. A távoli állományrendszerekkel a 4.4.2. rész foglalkozik.

A továbbiakban vázlatosan ismertetünk néhány speciális állományrendszert, amelyek egy-egy adott speciális igényt szolgálnak ki, a felépítésük ezekhez az igényekhez alkalmazkodott.

Ideiglenes állományrendszer

Számos program – főként a fordítóprogramok és az ablakkezelők – nagyon kiterjedten használ ideiglenes állományokat (temporary files) közbülső eredményeik, állapotuk tárolására. Ezekre az állományokra az alkalmazás befejeződése után már nincs szükség, nem kell túlélniük egy rendszer összeomlást. Ezen állományok létrehozásának, hozzáférésének és törlésének a használatukból adódóan gyorsnak kell lennie. Már a korai rendszerekben is a ker­nel az ideiglenes állományok helyett a memóriában található blokk buffer cache-be írt, így késleltetve a valódi állományba írást. Ezzel a hozzáférés jelentősen gyorsult, azonban az állomány létrehozása és törlése a többszöri szinkron lemezhozzáférés miatt még mindig felettébb lassúnak számított.

Ezt a problémát a RAM-diszkek alkalmazásával küszöbölték ki. Mivel ekkor az adatok a fizikai memóriában kerültek tárolásra, így a hozzáférések jelentősen felgyorsultak. A RAM-diszk nagy sebessége azonban nem igazán tudja kompenzálni azt a kellemetlen tulajdonságát, hogy nagyon pazarlóan bánik a globális erőforrásokkal, vagyis elsősorban a memóriával. A rendszer működése során változóak az igények az ideiglenes állományrendszerrel szem­ben, sajnos azonban a RAM-diszk számára fenntartott memóriát a rendszer külön kezeli, így azt kisebb igények esetén sem lehet más célra felhasználni.

A Memória Állományrendszer (Memory File System – mfs) ezt a problémát próbálta orvosolni. Az állományrendszert egy folyamat, méghozzá az állományrendszert csatlakoztató (mount-oló) folyamat virtuális címtartományában építették fel. Mivel az állományrendszer egy folyamat virtuális címtartományában van, így a standard memóriakezelő mechanizmusokkal éppúgy ki lehet lapozni háttértárra, mint bármilyen más adatot. Mivel ebben a megvalósításban egy külön folyamat kezelt minden B/K-műveletet, így mindig két környezetváltásra van szükség.

Ezzel szemben a teljesen kernelben megvalósított, elterjedten használt tmpfs nem használ külön B/K-szervert, így elkerüli a felesleges környezetváltásokat. Mivel a metaadatokat nem kilapozható memóriában tárolja, így számos memória-memória másolást és néhány lemezműveletet is el lehet kerülni. Ezenfelül, mivel támogatja a memória leképzést, így gyorsan és közvetlenül is hozzá lehet férni az állomány adatokhoz.

A specfs állományrendszer a felhasználók számára láthatatlan módon egységes interfészt biztosít a készülék állományokhoz, ami jelentősen megkönnyíti a készülékek kezelését.

A /proc állományrendszer

A /proc állományrendszer elegáns és hatékony interfészt biztosít minden fo­lyamat címteréhez. Eredetileg a hibakeresés támogatására dolgozták ki (hogy leváltsa a kényelmetlenül használható ptrace funkciót), azonban egy általános interfésszé nőtte ki magát a folyamat modellhez. A megközelítés nagy előnye, hogy a standard állományrendszer interfész segítségével a felhasználók folyamatok címteréből olvashatnak és módosíthatják azt.

A jogosultságokat a közönséges állományoknál megszokott jogosultságkezelési mechanizmussal lehet szabályozni. Az állományrendszer bevezetésekor minden egyes folyamathoz egy-egy bejegyzés tartozott a /proc könyvtárban. A bejegyzések nevei megegyeztek a folyamatazonosítókkal. A későbbiek folyamán finomították a modellt és minden folyamatot egy könyvtár jelölt a /proc könyvtárban, aminek a neve továbbra is a folyamat azonosítója maradt. A könyvtáron belül a logikailag eltérő funkciókhoz egy-egy külön állomány jelent meg, mint például a folyamat állapotát, a virtuális címtérképét, jelzés információkat stb. leíró állományok.

A Processzor állományrendszer

A processzor állományrendszert a többprocesszoros környezet és az ezekhez alkalmazkodó operációs rendszerek hívták életre. Az állományrendszer egy interfészt biztosít egy többprocesszoros számítógép egyes processzo­rai­hoz. A /system/processor könyvtárra mount-olódik fel és a rendszer minden pro­cesszorához tartalmaz egy állományt. Az állomány a processzorral kapcsolatos legfontosabb információkat tartalmazza, mint például a CPU típusa, a CPU sebessége, a cache mérete, a hozzá kapcsolódó speciális berendezések stb.

5.3.6.5. Modern állományrendszerek

Az operációs rendszerek tervezésekor figyelembe veszik a hardver adottságokat, maximálisan megpróbálják kiaknázni a bennük rejlő lehetőségeket, illetve a fejlesztés során hozott döntések magukon viselik az adottságok hatását. A UNIX kialakulásakor a tervezési döntéseket erősen befolyásolta, hogy a korai ’80-as években viszonylag kis memóriára, lassú processzorra és relatíve gyors lemezegységekre kellett alapozni a tervezést. Időközben a hardverfejlesztés eltérő léptékben haladt előre, a memória mérete jelentősen megnőtt, a CPU sebessége közel három, míg a memória mérete közel két nagyságrenddel megnövekedett, ezzel szemben bár mérete jelentősen nőtt, a lemezegység sebessége alig duplázódott meg. Ebből adódóan a UNIX belső szerkezete szempontjából megváltozott hardverfeltételek miatt számos tervezési döntés elvesztette létjogosultságát, azokat az új feltételeknek megfelelően újra át kellett gondolni.

A lemezegység sebességének lassú növekedése elsősorban az állományrendszert érinti hátrányosan. A hagyományos állományrendszereket a mai számítógépeken használva erősen B/K-korlátozott rendszerek jönnek létre, ami gátolja a jelentős CPU-sebességnövekedés kiaknázását.

A sebesség problémák kiküszöbölésére számos modern állományrendszer alkalmazza az ún. naplózási (journaling vagy log) technikát. A megközelítés lényege, hogy minden állományrendszer változást a rendszer egy csak hozzáfűzhető állományba naplóz, vagyis az egész állományrendszer tulajdonképpen egy hatalmas napló állomány. A naplót a rendszer szekvenciálisan írja, nagy darabokban, ami jelentősen javítja a lemezkihasználtságot és a teljesítményt. Továbbá egy rendszer összeomlás után a napló állománynak csak a végét kell vizsgálni, ami a felépülést jelentősen felgyorsíthatja.

Egy naplózó állományrendszer tervezésénél is számos döntést kell meghozni. Ezek közül az alábbiakban a teljesség igénye nélkül vázoljuk a legfontosabbakat:

  • mit írjunk a napló állományba, műveletek vagy értékek,

  • kiegészítő állományrendszerként alkalmazzuk, vagy cseréljük le a korábbi állományrendszert,

  • a változtatásokat újra lejátszva (REDO) vagy a legutóbbi változtatásokat visszavonva (UNDO), állítsuk vissza a korábbi értékeket,

  • milyen szemétgyűjtési stratégiát alkalmazzunk,

  • hogyan alkalmazzuk a csoportvéglegesítést,

  • hogyan keressük vissza az adatokat.

A hely szűke miatt itt nem tárgyaljuk részletesen az implementációt, csak felhívjuk a figyelmet a naplóalapú állományrendszer alkalmazásának néhány nyilvánvaló előnyös tulajdonságára, illetve a megoldandó problémákra.

Az előnyök eléggé szembeötlők. Mivel mindig a napló állomány végére írunk, így az írás mindig szekvenciális és nincs szükség fejmozgatásra. A naplóba írás során egyszerre mindig nagy mennyiségű adatot írunk, tipikusan egy egész sávot, ebből adódóan nem kell elfordulás alapján optimalizálni, illetve a lemezegység teljes sávszélességét ki lehet használni. Egy művelet minden adat összetevőjét (metaadatot és valódi adatot) össze lehet fogni egyetlen atomikusan végrehajtott írásba, ami jelentősen növelheti az állományrendszer megbízhatóságát. Az írás tehát nem okoz problémát.

Viszont a rendszer hatékonysága szempontjából nagy gondot kell fektetni az adat visszakeresés problémájára. Az adatokat a hagyományos módszerrel (állandó helyen tárolt szuperblokk, inode stb.) már nem lehet kezelni, a napló állományban keresést kell végrehajtani. Ezt a keresést jelentősen támogatja a memóriában történő cache-elés, ami a mai memóriaméretek mel­lett nem jelent problémát. Ettől függetlenül az állomány szerkezetének támo­gatni kell a napló állományban történő keresést, mert enélkül a rendszer használati értéke jelentősen csökken.

Számos napló alapú rendszert dolgoztak ki, mint például a 4.4BSD napló­alapú állományrendszere, metaadat naplózó rendszerek, az Episode állomány­rendszer. Ezeket részletesen az irodalomjegyzékben felsorolt források tárgyalják.

5.3.7. Teljes folyamatok háttértárra írása (swapping)

A korai UNIX-rendszerekben a virtuális memóriakezelést teljes folyamatok háttértárra írásával oldották meg (swapping rendszerek). Ennek történeti okai vannak: az első UNIX-rendszerek PDP-11-en futottak, ahol a folyamatokra 64 K-s memóriakorlát volt kiszabva. Ilyen kisméretű folyamatokat viszonylag gyorsan ki lehetett írni háttértárra. Nagy folyamatok esetén (manapság egy-egy folyamat virtuális memóriaméretére nincs elvi korlátozás, gyakoriak a több Mbyte-os folyamatok) a háttértárra írás időigényes, így ön­ma­gában, egyedüli módszerként nem használatos, azt egy igény szerinti la­po­zási technikával ötvözve alkalmazzák.

Bár a teljes folyamatok háttértárra írása (tárcsere) veszített a jelentőségéből, a modern rendszerek is alkalmazzák, hogy gyorsan orvosolják a leterhelt rendszereknél gyakran jelentkező erőforrás szűke okozta hatékonysági problémákat.

A továbbiakban áttekintjük, hogy a tárcsere rendszer megvalósítása milyen feladatokat ró az operációs rendszerre, és hogy ezeket a feladatokat ho­gyan oldják meg.

A swapping rendszerekben három, logikailag elkülönülő feladatot kell meg­oldani:

  • a háttértár szervezését (swap device),

  • folyamatok háttértárra írását,

  • folyamatok háttértárról memóriába történő beolvasását.

A továbbiakban ezeket a feladatokat tárgyaljuk.

5.3.7.1. A háttértár szervezése

A háttértár (swap device) egy blokkos eszköz, általában merevlemez. Ellentétben a Unix állományrendszerrel (amely egy lépésben egy blokkot foglal le), a háttértárra íráskor a rendszer a folyamatoknak összefüggő blokkcsoportot foglal. Ez persze a rendelkezésre álló terület tördelődéséhez (fragmen­tation) vezet, de ebben az esetben ez nem jelent olyan nagy problémát, mert a hát­tértáron a folyamatok csak ideiglenesen tartózkodnak, onnan időről időre be­kerülnek a memóriába, és ekkor a háttértáron használt terület felszabadul. A tördelődésnél fontosabb, kritikus probléma a háttértárra írás sebessége. Folyamatok háttértárra írása és onnan történő beolvasása nagyon gyakori esemény volt a korai rendszerek működése során, így a műveletek sebessége valóban létfontosságú volt. Az is maradt mindmáig, mert a gyakoriság ugyan csökkent, de a processzor és a háttértár közötti sebességkülönbség jelentősen növekedett.

A rendszer a háttértáron rendelkezésre álló szabad területeket egy memóriában tárolt táblával (ún. map-pal) tartja nyilván. A map szerkezete egyszerű: a bejegyzések (cím, szabad blokkok száma) alakú rendezett párok. Itt a cím a háttértár blokk relatív címe a swapping területen (a logikai swap device-on – a számozás 1-gyel kezdődik). A táblát a rendszer mindig a lehető legtömörebben tartja, felesleges bejegyzést nem tartalmaz. Például, feltételezve egy 100 000 blokkot tartalmazó háttértárat, azt a pillanatot, amikor a tel­jes háttértár üres, vagyis minden blokk szabad, az alább látható map írja le.

5.26.ábra. táblázat - A laptábla-bejegyzés által tárolt információk. A bejegyzést a folyamat virtuális címei címzik. Jelölések: Age – öregítés bit(ek), C/W – copy-on-write bit, Mod – módosítás bit, Ref – hivatkozás bit, Val – érvényességi bit,

Szabad terület kezdőcíme

Az összefüggő szabad terület mérete (blokkokban)

1

100000


A map egy dinamikusan bővülő, illetve szűkülő szerkezet, vagyis működés közben a táblába új sorok szúródnak be, illetve sorok törlődnek. Mivel a gyorsaság a legfontosabb tervezési szempont a háttértár kezelésében, ezért a foglalási stratégia is ezt tükrözi: a stratégia first-fit, vagyis az első megfelelő méretű területet használja fel a rendszer. A map struktúráját végiggondolva jól látható, hogy az a first-fit stratégiát támogatja.

5.3.7.2. A háttértár-foglalási és -felszabadítási algoritmus

A háttértár foglalása és felszabadítása során a kernel megpróbálja a map-ot a lehető legtömörebben tartani. Foglaláskor, ha egy teljes map bejegyzést foglalunk, akkor a kernel törli a bejegyzést (nem hagy meg 0 méretű bejegyzést). Felszabadításkor a kernel megvizsgálja, hogy a felszabadított terület pontosan beilleszkedik-e két map bejegyzés közé. Amennyiben igen, akkor a nagyobb indexű bejegyzést törli, és az alacsonyabb indexű bejegyzés által megadott szabad blokkok számát úgy módosítja, hogy az lefedje a kisebb indexű bejegyzés, a felszabadított terület és a nagyobb indexű bejegyzés szabad blokkjait. Amennyiben a felszabadított terület nem tölt ki teljesen egy „lyukat” a map táblában, a kernel megvizsgálja, hogy a felszabadított terület illeszkedik-e valamelyik korábbi bejegyzéshez (egy korábbi map bejegyzéshez a felszabadított terület alulról vagy felülről illeszkedhet). Amennyiben igen, módosítja a már meglévő bejegyzést. Amennyiben a felszabadított terület egyetlen bejegyzéshez sem illeszkedik, akkor a kernel új bejegyzést hoz létre.

A korai UNIX-rendszerekben csak egy háttértár volt, manapság már a kernel több swap berendezést is használhat. Ezeket a rendszer konfigurálásakor a rendszergazda adja meg. Amennyiben több swap berendezés is van, a kernel azokat round–robin-stratégiával használja.

5.3.7.3. Folyamatok háttértárra írása

Az operációs rendszer működése során négy esetben lehet szükség folyamatok háttértárra írására:

  1. a kernel fork rendszerhívást hajt végre – új folyamatot hoz létre, és nincs elég memória,

  2. a kernel (s)brk rendszerhívást hajt végre – vagyis memória tartományt bővít,

  3. a verem dinamikusan bővül,

  4. a kernel átütemez (korábban háttértárra írt folyamatnak kell a hely).

Tárcserénél (1–3) a kernel zárolja az érintett folyamatokat, hogy a swapper (0-ás folyamat) menet közben háttértárra ne írja. A memória objektumok éppúgy, mint az állománykezeléshez tartozó adatszerkezetek, hivatkozásszámlálóval rendelkeznek, ami megmondja, hogy egy adott időpontban az objektumot hányan használják. Amikor a swapper egy tartományt háttértárra akar írni, csökkenti eggyel a tartomány hivatkozás számlálóját, és ha az 0-ra csökken, ki is írja. Itt gondoljunk az osztottan használt tartományokra (shared memory regions), ahol egy tartományt egyszerre több folyamat is használ. Ekkor a tartomány hivatkozásszámlálója a tartományt használó folyamatok számával egyezik meg. Amikor a swapper úgy dönt, hogy egy folyamatot háttértárra ír, a folyamat azon tartományait, amelyeket más folyamat is használ, nem szabadíthatja fel! Amikor a kernel egy tartományt kiír a háttértárra, akkor a tartomány háttértáron elfoglalt címét beírja a tartománytáblába (region table).

A folyamatok virtuális címtartománya „hézagos”, ritka, vagyis a folyamatok általában nem használják a teljes virtuális címtartományukat. A kód-, adat- és veremtartományok általában nem összefüggők (már csak azért sem, hogy azok dinamikusan növekedhessenek). Ebből adódóan a swapper nem írja ki a folyamat teljes virtuális címtartományát a háttértárra, hisz az felesleges és pazarló lenne, hanem csak a valójában használt (fizikai címmel rendelkező) címtartományokat menti el (5.24. ábra).

Az 5.24. ábrán jól látszik, hogy a folyamatban csak hat laphoz tartozik fizikai memória, így a háttértárra csak ez a hat lap íródik ki. A tartománytáblában tárolódnak a virtuális címek az egyes tartományokhoz, így amikor a folyamat visszatöltődik a memóriába, bár a fizikai címek megváltozhatnak, a virtuális címek (vagyis a folyamat memóriaképe) nem változnak (az 5.24. ábra jobb oldala).

5.24. ábra. ábra - Folymat háttértárra írása és visszatöltése

Folymat háttértárra írása és visszatöltése


Háttértárra írás fork rendszerhívás esetén

A fork rendszerhíváskor két helyzet állhat elő:

  • van memória a gyermek folyamat létrehozásához (ekkor nem kell semmit sem háttértárra írni),

  • nincs elég memória a gyermek folyamat létrehozásához.

A második esetben a swapper kiírja háttértárra a szülő memóriaképét (ez lesz majd a gyermek memóriaképe), de a hozzá tartozó fizikai memóriát nem szabadítja fel, a szülő a memóriában marad. Ezek után a swapper futásra késszé teszi a gyermeket a háttértáron. Mivel a háttértáron lévő futásra kész folyamatokat előbb-utóbb a swapper betölti, így a gyermek folyamat is bekerül majd a memóriába. Majd az ütemező valamikor futásra ütemezi, amikor majd befejeződik a gyermekben is a fork hívás, majd a gyermek folyamat user módba vált.

Tartománynövelés

Ez az eset akkor áll elő, amikor egy memóriában lévő folyamat valamelyik tar­­tományának a méretét szeretné növelni, de nem áll rendelkezésre fizikai me­mória. Leggyakoribb eset, hogy a verem méretét szeretné növelni a ker­nel. A tartományok méretének növelését az (s)brk rendszerhívásokkal lehet meg­tenni. (A brk hívás adott memóriacímre állítja az adott tartományhoz tartozó legmagasabb memóriacímet, míg az sbrk adott mérettel bővíti a tartományt.) Amennyiben a rendszerhívás idején rendelkezésre áll a kívánt memória, a rendszerhívás lefut, lefoglalva a megfelelő méretű memóriát. Amennyiben nincs elég memória, a kernel a virtuális címtartományban elvégzi a címleképezést, de nem foglal az új memóriaterülethez fizikai memóriát, hanem a folyamatot kiírja a háttértárra és futásra késszé teszi. (A háttértáron megjelenik a memórianövelés előtti memóriakép, valamint a lefoglalt új memóriatartomány is, amelyet a kernel a háttértáron kinulláz – lásd az 5.25. ábrát.) Amikor legközelebb a swapper betölti a folyamatot, a kernel az új virtuális címtartományhoz is allokál fizikai memóriát, így a folyamat „meg­nö­vekedett” memóriával fut tovább. (A folyamat nem veszi észre, hogy futása megszakadt, és háttértáron töltött valamennyi időt – ez ütemezés miatt is előfordulhatott volna.)

5.25. ábra. ábra - Tartománybővítés háttértárra írással

Tartománybővítés háttértárra írással


Folyamatok betöltése

A swapper folyamat mindig kernel módban fut, nem ad ki rendszerhívásokat, hanem közvetlenül meghívja a kernel rutinokat. Végtelen ciklusban dol­gozik, folyamatokat próbál meg memóriába tölteni, illetve memóriából háttértárra írni. Amikor nem tud mit csinálni, alszik. A swapper nem kitüntetett folyamat, ugyanúgy fut, mint bármely más folyamat, csak magasabb a prioritása.

A swapper működési fázisai

  • ha nincs a háttértáron futásra kész folyamat, a swapper alszik,

  • ha van, de a rendszerben nincs memória, megpróbál folyamat(okat) háttértárra írni és kezdi elölről a futásra kész folyamatok keresését a háttértáron.

Itt fontos megjegyezni, hogy a swapper zombi folyamatot sohasem ír ki háttértárra, hiszen a zombi folyamatok csak folyamattábla bejegyzést foglalnak, fizikai memóriát nem.

5.3.7.4. A háttértárra írás, illetve a háttértárról való beolvasás szabályai

A swapper néhány egyszerű szabályt alkalmaz annak eldöntésére, hogy mely folyamatok alkalmasak háttértárra történő kiírásra, illetve háttértárból történő beolvasásra. Ezen szabályok a következők:

  • a folyamat memóriába tölthető, ha már legalább 2 másodpercet háttértáron töltött,

  • a folyamat háttértárra írható, ha már legalább 2 másodpercet memóriában töltött.

Az óra minden másodpercben felébreszti a swappert. Mivel a swapper nagy prioritású folyamat, minden másodpercben fut is. Fontos tulajdonsága a háttértárba író algoritmusnak, hogy amikor egy folyamat sleep rendszerhívást ad ki, akkor az algoritmus elölről indul, hiszen valószínűleg érdemesebb az épp „elalvó” folyamatot a háttértárra írni.

5.3.7.5. A háttértárra kiírandó folyamat kiválasztásával kapcsolatos problémák

A folyamatokat a swapper azért írja ki háttértárra, hogy helyet csináljon a betöltendő folyamatoknak. A folyamatok kiválasztásakor azonban az aláb­bia­kat figyelembe kell venni:

  • Lehet, hogy a kiírt folyamat kicsi, továbbra sem lesz elég hely a memóriában ahhoz, hogy egy másik folyamatot betöltsön a swapper (például ha kiír egy 2 K-s folyamatot, az nem fog elég helyet biztosítani egy 1 M-es folyamatnak). Erre a problémára megoldást jelenthet, ha a swapper folyamatcsoportokat ír ki háttértárra, amelyeknek összes memóriafoglalása már elég lesz a betöltendő folyamat számára.

  • Ha a swapper azért alszik, mert nem volt elég memória, akkor ébredéskor újra kezdi az egész algoritmust. Ebből fakadóan egy korábban várakozó folyamat lehet hogy ismét nem jut be a memóriába, mert időközben egy másik folyamatot fontosabb lett betölteni.

  • Amennyiben egy futásra kész folyamatot ír ki, előfordulhat, hogy az a folyamat még nem is futott (prioritás, nice).

Egy érdekes elvi problémára fel kell itt figyelni: szerencsétlen körülmények között holtpont is kialakulhat. Ennek feltételei:

  • nincs hely a háttértáron,

  • a memóriában minden folyamat alszik,

  • minden futásra kész folyamat a háttértáron van,

  • nincs elég hely a memóriában, hogy a swapper a háttértárból egy futásra kész folyamatot memóriába töltsön.

Szerencsére, ezen állapot kialakulásának kicsi az esélye.

5.3.8. Igény szerinti lapozás

Az operációs rendszer egyik elsődleges feladata, hogy a rendszer memória erőforrásait hatékonyan kezelje. Ezen feladat ellátására az operációs rendszerben a memóriakezelő rendszer egy alrendszert alkot. A memóriakezelő rendszerrel szemben természetes elvárás, hogy

  • segítségével a fizikai memória méreténél nagyobb programokat lehessen futtatni,

  • csak részben memóriában lévő programok is futtathatók legyenek,

  • a multiprogramozásból adódóan támogatnia kell, hogy egyszerre több program is a memóriában lehessen,

  • támogassa áthelyezhető programok kezelését,

  • a memóriakezelés legyen gépfüggetlen,

  • vegye le a programozó válláról a memória allokációs és menedzselési terheket,

  • tegye lehetővé az osztott memória használatot.

Ezen feladatok megoldásához egy magas szintű absztrakcióra van szükség: a virtuális memóriakezelésre (virtual memory). A virtuális memória használata feltételezi, hogy a címtér (address space) a fizikai memóriától független erőforrás. Mérések azt mutatják, hogy a memóriakezeléssel kapcsolatos tevékenységek jelentős CPU-időt emésztenek fel – terhelt rendszeren megközelíti a 10%-ot.

A UNIX, mint azt korábban láttuk, kezdetben csak a folyamatok háttértárra írását (swapping) biztosította. A modern operációs rendszereknek ennél ha­té­konyabb eszközökre is szükségük van. A ’80-as évek közepére már minden UNIX-változat az igény szerinti lapozást használta, mint elsődleges virtuális memóriakezelő technikát. A legújabb rendszerek már előretekintő lapozási technikákat (anticipatory paging) is alkalmaznak, amivel a rendszer olyan lapokat is behoz a fizikai memóriába, amikről úgy hiszi, hogy majd a közeljövőben szüksége lesz rá.

Mivel a 3.4.2. rész már részletesen tárgyalta a virtuális memóriakezelés elvi alapjait, ismertetve a szükséges hardver és szoftver feltételeket, így ebben a fejezetben már nem térünk ki ennek részleteire, hanem a UNIX azon adatszerkezeteit és használatukat ismertetjük, amelyek az igény szerinti lapozás megvalósításához szükségesek. Fogalmi tisztasága miatt a következőkben a SVR3 adatszerkezeteit ismertetjük. A legújabb UNIX-rendszerek már egy új, memóriába ágyazott állományokon alapuló virtuális memóriakezelő alrendszert alkalmaznak, azonban azok kialakítására nagy hatással volt a SVR3. A tárgyalás végén felhívjuk az olvasó figyelmét a hatékonysági problémákra, és rámutatunk, hogy a későbbi virtuális memóriakezelő alrendszerek hogyan orvosolták ezeket a problémákat.

5.3.8.1. A virtuális memóriakezelést támogató adatszerkezetek

A UNIX az alábbi fontosabb adatszerkezeteket használja memóriakezeléshez:

  • pfdata (page frame data table). Ez az adatszerkezet a fizikai lapok állapotát írja le. A tartalmazott információkat alább ismertetjük. A rendszer induláskor foglal helyet számára, statikus adatszerkezet.

  • laptábla-bejegyzés (page table entry). Egyrészt tartalmazza a virtuális-fizikai címleképzést, másrészt a memóriakezelő funkciók megvalósításához elengedhetetlen jelzőbiteket tárol.

  • diszkblokk leíró (disk block descriptor). A virtuális memória lapjaihoz tartozó háttértár címeket (a lap háttértáron tárolt másolatának a helyét) adja meg egyéb fontos információkkal együtt.

  • háttértár használat tábla (swap use table). A háttértár használatát adminisztrálja.

A továbbiakban a fenti adatszerkezeteket és használatukat ismertetjük.

A pfdata adatszerkezet

A pfdata a fizikai lapokat írja le, az alábbi információkat tartalmazza:

  • a lap állapota (háttértáron, végrehajtható állományban található, DMA van folyamatban a lapra, a lap kiadható),

  • hivatkozásszámláló: a lapra hivatkozó folyamatok száma (ez megegyezik az érvényes laptábla hivatkozások számával). Ezen mező támogatja a fizikai memória osztott használatát, illetve a kernel ez alapján tudja eldönteni, hogy egy adott lapot újra ki lehet-e adni,

  • a lapra éppen melyik háttértár blokk van betöltve: a háttértár logikai címe, az azon belüli blokkcím (ez utóbbi jelentőségét a későbbiekben részletesen tárgyaljuk),

  • mutatók pfdata bejegyzésekre (szabad lista, hashtábla).

A pfdata bejegyzések a háttértár blokk cím szerint hashsorokba vannak rendezve (amennyiben több háttértár is van a rendszerben, akkor a hash­kulcs­ban szerepel a háttértár logikai címe is). Ezáltal gyorsan meg lehet találni a blokk cím alapján egy adott háttértár blokkhoz tartozó lapot a memóriában. Ez javítja a hatékonyságot, ugyanis, ha egy olyan lapra van szükség, ami már bent van a memóriában, akkor azt nem kell ismét betölteni, meg lehet takarítani egy lemezműveletet. Ezenfelül a szabad memórialapok egy szabad listára is fel vannak fűzve. Amennyiben az operációs rendszer lapot akar foglalni, ezen szabad lista elejéről foglal. Az lenne az ideális, ha a szabad lista elején olyan lapok lennének, amelyekre már soha sem lesz szükség a későbbiekben, vagyis ezeknek a lapoknak meg kellene előzni azokat a lapokat, amelyekre esetleg a későbbiekben szükség lehet. Ha nincsenek ilyen lapok, akkor a lokalitás elvéből adódóan a legrégebben használt (least recently used) lapokat lenne célszerű felhasználni, azokat lenne célszerű a szabad lista elején tárolni.

Ezzel kapcsolatban felmerül egy gyakorlati probléma: a legrégebben használt sorrend fenntartásához minden egyes laphivatkozás után újra kellene rendezni a listát, aminek időköltsége nem megengedhető. Ezért egy ésszerű kompromisszummal a legrégebben használt stratégia helyett a régen használt (not recently used) stratégiát alkalmazzák. Ehhez egy hivatkozásbitet rendelnek minden egyes laphoz, ami az adott lapra történő hivatkozáskor beállítódik, illetve adott időközönként törlődik. Bár ez a stratégia nem optimális, garantálja, hogy csak olyan lapok kerüljenek újra kiadásra, amiket az elmúlt időszakban nem használtak. A későbbiekben ismertetjük, hogy ezt a technikát szimulált hivatkozásbit bevezetésével hogyan lehet megvalósítani olyan architektúrán, ami hardverből nem támogatja a hivatkozásbitet.

Laptábla bejegyzés

Minden egyes folyamathoz tartozik legalább egy laptábla (page table), aminek a bejegyzései a folyamat címterét képezik le a fizikai memória címeire, illetve további memóriakezeléssel kapcsolatos információkat tárolnak. A laptábla elemei magától értetődően tartalmazzák a fizikai memóriacímeket és a hozzáférési jogosultság biteket. Az igény szerinti lapozás támogatására azonban még az alábbi biteket is nyilván kell tartani (5.26. ábra).

  • érvényességi (valid),

  • hivatkozás (reference),

  • módosítás (modify, dirty),

  • másolás írás esetén (copy on write – C/W),

  • öregítés (age),

  • védelem (protection).

Protection – védelmi bitek. táblázat - all

Lap fizikai címe

Age

C/W

Nod

Ref

Val

Protection


A hivatkozás- és módosításbiteket általában a hardver állítja. Léteznek olyan hardverek is, amelyek ezt nem teszik meg. A hivatkozásbit szoftver szimulációját majd a későbbiekben tárgyaljuk. Az érvényes, C/W és az öregí­tés­­biteket a kernel kezeli.

Diszk blokk leíró és a háttértár használat tábla

A diszk blokk leíró (disk block descriptor) a virtuális memória lapjaihoz tartozó háttértár címeket adja meg. Ehhez tartalmazza a háttértár logikai címét, a lap háttértáron elfoglalt helyét, illetve megadja a lap típusát, vagyis, hogy milyen módon lehet a tárolt másolatot (backing store) elérni (5.27. ábra). A lap lehet a háttértáron (swap), lehet a memóriában, illetve lehet fill-on-demand típusú, vagyis ha szükség van a lapra, akkor azt egy adott tartalommal fel kell tölteni. Ennek két típusa ismeretes. Fill-from-text esetén a betöltendő tárolt másolat egy végrehajtható állományban található. Az ilyen típusú lapok általában kódot vagy inicializált adatot tartalmaznak. Zero-fill esetén nincs tárolt másolat, a kernel a lapot kinullázza, vagyis nullával tölti fel. Az ilyen típusú lapok általában nem inicializált adatot tartalmaznak. A kinullázással a kernel biztosítja, hogy a nem inicializált változók kezdeti értéke nulla legyen.

5.27.ábra. táblázat - A diszk blokk leíró által tárolt információk. A bejegyzést a folyamat virtuális címei címzik

Háttértár logikai címe

Blokk sorszám

Típus (swap, file, ZF, FT)


A háttértár használati tábla a háttértár használatát adminisztrálja. Ez az adatszerkezet is tartalmaz egy hivatkozásszámlálót, ami a pfdata hivatkozásszámlálójához hasonló szerepet tölt be. Amikor a kernel fizikai lapot allokál a háttértáron tárolt laphoz (vagyis amikor a lap betöltődik a fizikai memóriába), a laphoz tartozó pfdata hivatkozásszámláló értékét a háttértár használati tábla hivatkozásszámlálójának az értékére állítja, így a konzisztencia biztosítható.

5.3.8.2. A virtuális memóriakezelést támogató adatszerkezetek használata

A SVR3 a memóriakezeléshez a tartomány (region) modellt alkalmazta. Ennek lényege, hogy a lapszervezésű memóriát nagyobb logikai egységenként, tartományonként kezelte. Egy-egy tartományt rendeltek a folyamatok kód, adat és verem területéhez, illetve egyéb logikai egységeihez. A tartományok a memóriahasználat logikai szerkezetét tükrözik. Az 5.28. ábra a tartományok és a laptábla-bejegyzések, illetve diszkblokk leírók viszonyát mutatja.

5.28. ábra. ábra - A tartománymodell és a virtuális memóriakezelést támogató adatszerkezetek kapcsolata

A tartománymodell és a virtuális memóriakezelést támogató adatszerkezetek kapcsolata


Az ábrán jól látszik, hogy minden tartományhoz tartozik egy laptábla, illetve, hogy a laptáblabejegyzéseket és a diszkblokk leírókat a kernel együtt kezeli (mindkettőt a folyamat virtuális címeivel címzi), azok akár egyetlen adatszerkezetet is alkothatnának, azonban eltérő funkcionalitásuk miatt és az áttekinthetőség kedvéért célszerű azokat külön adatszerkezetbe foglalni.

A virtuális memóriakezelést támogató adatszerkezetek közötti kapcsolat

A korábbi bekezdésekben ismertetett adatszerkezetek között számos kereszthivatkozás található, ami megkönnyíti az operációs rendszer hatékony működését. Az 5.29. ábra ezeket a kapcsolatokat mutatja. A jobb áttekinthetőség érdekében az ábra egyetlen laptáblabejegyzést és a hozzá kapcsolódó adatelemeket mutatja.

Mint az az 5.29. ábrán jól látszik, mind a laptáblabejegyzést, mind pedig a diszkblokk leírót a folyamat virtuális lapcímével címzik. A laptábla­be­jegy­zésben tárolt fizikai lapcím egyrészt kapcsolatot teremt magával a fizikai lappal, másrészt az adott laphoz tartozó pfdata bejegyzéssel is (a példában ez a 711-es lapkeret). A 711-es lapkeretet (fizikai memórialapot) leíró pfdata bejegyzés természetesen szintén hivatkozik magára a 711-es lapkeretre. Továbbá ugyanezen bejegyzés hivatkozik arra a háttértár blokkra, amely tárolja a virtuális lap tartalmát (ebben az esetben az 1. háttértár 2343-as blokkjára). Ugyanerre a blokkra hivatkozik a diszkblokk leíró és a háttértár használati tábla megfelelő bejegyzése is. Első látásra ez a redundancia tékozlónak tűnhet, azonban egy példa hamarosan rávilágít, hogy ezen adatszerkezetek segítségével bizonyos esetekben jelentős hatékonyság növekedést lehet elérni.

5.29. ábra. ábra - A virtuális memóriakezelést támogató adatszerkezetek kereszthivatkozásai

A virtuális memóriakezelést támogató adatszerkezetek kereszthivatkozásai


A „laplopó” folyamat

A „laplopó” folyamat (vagy pagedaemon) kernel szintű folyamat, inicializáláskor jön létre. Akkor aktivizálódik, amikor a rendelkezésre álló szabad lapok száma egy alsó határ alá csökken, és addig fut, amíg a szabad lapok száma újra egy felső határ fölé nem ér. Erre a két határra azért van szükség, hogy elkerülje a rendszer a vergődést (thrashing).

A lapoknak két állapota lehetséges:

  • a lapot még nem lehet kiírni háttértárra, öregszik (ez tulajdonképpen több állapotot takar, és implementáció függő, hogy a laplopó egy la­pot hányszor vizsgál meg kiírás előtt). A laplopó minden egyes vizsgálatnál törli a referenciabitet és öregít,

  • a lap kiírható, újra kiadható.

A lapok nem feltétlenül arányosan vannak elosztva a folyamatok között. Egy fontos szabályt mindig betart a laplopó: használatban lévő lapot nem lop el.

Amikor a laplopó úgy dönt, hogy kiír egy lapot, három eset lehetséges:

  • nincs másolat a háttértáron ® a lapot kiírásra ütemezi,

  • van másolat, nincs módosítás ® laptábla bejegyzés valid bitjét törli, csökkenti eggyel a pfdata hivatkozásszámlálóját, és a lapot a szabad listára teszi,

  • van másolat, és a memóriakép módosult ® kiírásra ütemezi a lapot, és az éppen használt háttértár helyet felszabadítja (blokkos kiírás).

A háttértár tördelődése jelentős lehet, mert bár a kiírás blokkos, de a felszabadítás, illetve a beolvasás laponkénti. Amikor a kernel kiírja a lapot, törli az érvényességi bitet, és a pfdata hivatkozásszámlálóját eggyel csökkenti. Amennyiben a hivatkozásszámláló 0 lett, akkor a lapot a szabad lista végére teszi.

5.3.8.3. Laphibák

Mint azt korábban láttuk, a címtranszformáció során a memóriakezelő egység a virtuális címet szétbontja egy virtuális lapcímre és egy lapon belüli eltolásra. A virtuális lapcím alapján megkeresi a laphoz tartozó laptábla bejegyzést, amiből kiolvassa a laphoz tartozó fizikai lapcímet. A fizikai lapcímhez hozzáilleszti a lapon belüli eltolást és így előáll a teljes fizikai cím. A címleképzés a következő okok miatt hiúsulhat meg.

  • Túlcímzés hiba (bounds error). A kiadott cím kívül esik az adott folyamat által kiadható érvényes címtartományon, ebből adódóan a címhez nem tartozik laptábla bejegyzés.

  • Érvényességi hiba (validity fault). A laphoz tartozik laptábla bejegyzés, azonban a hozzá tartozó érvényességi bit törölve van, ami általában azt jelenti, hogy a laphoz nem tartozik fizikai memórialap. Mint azt majd a későbbiekben látni fogjuk, a szoftverből szimulált referenciabit esetén az érvényességi bitet a rendszer felhasználja a szimulációhoz, és a lap akkor is érvényes lehet, ha az érvényességi bitje ki van törölve.

  • Védelmi hiba (protection fault). A lap nem engedi meg a kiadott művelet igényelte hozzáférést (például egy csak olvasható lapot nem lehet írni, vagy a felhasználó nem férhet hozzá a kernel lapokhoz). A copy-on-write technikánál is ezt a mechanizmust használja a kernel.

A fent ismertetett hibák minden esetben kivételt (exception) okoznak, amit egy kivételkezelő rutin kezel le. Ezeket a kivételeket általánosan laphibának nevezik. A kivételkezelő megkapja paraméterként a hibát kiváltó virtuális lapcímet, illetve a hiba típusát is (védelmi vagy érvényességi hiba – a határhiba is érvényességi hibát okoz). A kivételkezelő a hiba típusától függően megpróbálja a megfelelő lapot behozni a memóriába vagy egy jelzés elküldésével értesíti a folyamatot. A hibakezelők általában nem kerülnek alvó állapotba, kivéve ezen hibák kezelőit. Ezek aludhatnak, de ezek adott folyamathoz tartoznak. Továbbá a hiba kezelése alatt a tartományt zárolni kell, hogy a laplopó nehogy ellopjon lapokat a tartományból.

5.3.8.4. A laptábla-bejegyzés, a diszk blokk leíró és a pfdata együttes használata

A továbbiakban szemléletes példákon keresztül bemutatjuk a laptábla-bejegyzés, a diszkblokk leíró és a pfdata együttes használatát.

Mint azt korábban láttuk, az igény szerinti lapozás kihasználja, hogy az érvénytelen lapra történő hivatkozás laphibát okoz. A kivételkezelő, ha már tudomást szerzett róla, hogy a hiba azt jelzi, hogy egy lapot a memóriába kell tölteni, akkor a legfontosabb feladata, hogy a lapot megkeresse és betöltse.

A hibát okozó lap az alábbi állapotban lehet:

  1. háttértáron, de nincs memóriában,

  2. a szabad listán a memóriában,

  3. végrehajtható állományban,

  4. zero fill.

Az 5.30. ábra ezekre az esetekre mutat egy-egy példát.

5.30. ábra. ábra - A laphibát okozó lap állapotai

A laphibát okozó lap állapotai


1. eset: A lap a háttértáron van, de nincs a memóriában

Az 5.30. ábrán, az 1. esettel jelölt sorban látható, hogy a kérdéses lap nincs memóriában (az érvényességi bit törölve van, a lap invalid), és a háttértáron a 813-as blokkon található (a Diszk bejegyzés jelöli). A pfdata adatszerkezet diszkblokk oszlopát végigkeresve a 813-as blokkal, látjuk, hogy az nem szerepel, vagyis a szabad listán sincs sehol. A pfdata adatszerkezetből az is kiolvasható, hogy a 1036-os fizikai lap, ami korábban a 813-as háttértár blokk tartalmát tárolta, jelenleg a 387-es háttértár blokk tartalmát tárolja. A laphiba kezelő ekkor lapot allokál a 66K virtuális lapnak, megkapja az 1676-os fizikai lapot, és a 813-as blokk tartalma ide töltődik be. Az 5.31. ábra az ez utáni adatszerkezeteket mutatja.

5.31. ábra. ábra - A módosult adatszerkezetek a lap allokálás után

A módosult adatszerkezetek a lap allokálás után


2. eset: A lap a szabad listán, a memóriában található

Az 5.30. ábrán, a 2. esettel jelölt sorban látható, hogy a 64 K-s virtuális című lap még a szabad listán megtalálható a memóriában. Ezt a kernel a következőképpen találja meg: a lap a diszken a 1336-os blokkban található. Ez alapján a blokk alapján keres a pfdata adatszerkezet diszkblokk oszlopában, és megtalálja, hogy az ehhez a blokkhoz tartozó lap az 1611-es fizikai lapban található. A hivatkozásszámláló 0-ás értéke jelöli, hogy a lapot jelenleg senki sem használja, az valóban a szabad listán található. Ekkor a hivatkozásszámlálót eggyel növeli a kernel, és ezt a lapcímet beírja a laptábla bejegyzésbe. Ez után a 64 K-s virtuális lap bejegyzése az 5.32. ábra szerint alakul:

5.32. ábra. ábra - A módosult adatszerkezetek a lap szabad listán történő megtalálása után

A módosult adatszerkezetek a lap szabad listán történő megtalálása után


3. eset: A lap egy végrehajtható állományban található

Az 5.31. ábrán, a 3. esettel jelölt sorban látható, hogy a lap egy végrehajtható állomány adott blokkjában található (erre a hely oszlop File bejegyzése utal). A példában az 1 K virtuális címhez tartozó lap tartalma egy végrehajtható állomány 3. logikai blokkja. Az állomány megnyitásakor a kernel végez egy kis adat-előkészítést: az állományhoz tartozó inode-ba a végrehajtható állomány logikai blokkjaihoz tartozó fizikai blokkcímeket írja be sorfolytonosan, így a logikai blokk cím rögtön indexként használható.

4. eset: A laphoz nem tartozik tárolt másolat, azt fizikai memória allokálásakor ki kell nullázni

Az 5.30. ábrán, a 4. esettel jelölt sorban látható, hogy a lap zero-fill, vagyis nem inicializált adatot tartalmaz (erre a hely oszlop ZF bejegyzése utal). Ekkor a kernel amikor fizikai memórialapot allokál, azt kinullázza, ezzel biztosítva, hogy a nem inicializált változók nulla kezdeti értékkel rendelkezzenek.

5.3.8.5. A copy-on-write technika és használata

Mint azt a folyamatkezeléssel kapcsolatban láttuk, a UNIX-ban új folyamatot a fork rendszerhívással lehet létrehozni. A rendszerhívás hatására a létrejövő gyermek folyamat memóriaképe megegyezik a szülő memóriaképével. A korai rendszerekben a folyamat létrehozásával automatikusan allokáltak memóriát a gyermek folyamat számára. Ez nagyon rossz memóriagazdálkodást eredményezett, hisz nagyon gyakran a gyermek folyamat ugyanazt a kódot futtatja, mint a szülője, és a gyermek folyamat gyakran memóriamódosítás nélkül fejeződik be. Ilyenkor felesleges külön memóriát allokálni a gyermek számára.

A probléma kezelésére kidolgozták a copy-on-write technikát. A módszer során, ha egy folyamat gyermek folyamatot hoz létre, a kernel először csak a mutatókat kezeli. Először csak az osztottan kezelt tartományok hivatkozás- számlálóját növeli. A privát tartományokra új tartománytábla bejegyzés készül, illetve a kernel új laptáblákat foglal. Ezek után a kernel végigmegy a szülő lapjain. Ha a lap érvényes, akkor a pfdata hivatkozásszámlálóját eggyel megnöveli (ezzel jelzi, hogy a fizikai lapot külön tartományok használják). Amennyiben a lap háttértáron van, akkor a háttértár használat tábla hivatkozásszámlálóját növeli eggyel. Továbbá a folyamatok laptábla bejegyzéseiben a hozzáférési jogosultságot csak olvasási jogosultságra állítja (W: 0) és bebillenti a C/W (copy-on-write) bitet, jelezve, hogy a copy-on-write technikát alkalmazza. Ha a szülő vagy a gyermeke megpróbálja írni a közösen használt lapok valamelyikét, akkor az írás védelmi laphibát (protection fault) okoz. A laphibakezelő megvizsgálja a C/W-bit állapotát. Ha a bit nincs beállítva, akkor valóban jogosulatlan műveletet próbáltak meg végrehajtani, ellenkező esetben viszont a kernel tudomást szerez róla, hogy most már nem lehet tovább elodázni a fizikai memóriafoglalást, a laphibát okozó folyamat számára lapot kell foglalni, és a foglalás tényét be kell jegyezni a laptáblába, illetve a korábbi leképzésben szereplő fizikai laphoz tartozó pfdata adatszerkezetben csökkenteni kell a hivatkozásszámlálót.

5.33. ábra. ábra - Egyszerű példa a copy-on-write technika alkalmazására. Az (a) ábra azt az állapotot mutatja, amikor az A folyamat és két gyermeke osztoznak egy lapon, míg a (b) ábrán már az egyik gyermek (B) írás miatt külön lapot használ

Egyszerű példa a copy-on-write technika alkalmazására. Az (a) ábra azt az állapotot mutatja, amikor az A folyamat és két gyermeke osztoznak egy lapon, míg a (b) ábrán már az egyik gyermek (B) írás miatt külön lapot használ


Az 5.33.(a) ábra egy ilyen helyzetet mutat be. Az A folyamat két gyermek folyamatot hozott létre, B-t és C-t. A három folyamat közösen használja az 543-as fizikai lapot. Az ábrán a jobb áttekinthetőség érdekében laptábla bejegyzés és a pfdata adatszerkezetnek csak a releváns komponenseit tüntettük fel, illetve csak egyetlen lapot, az éppen írt lapot ragadtuk ki. Az 5.33.(a) ábrán jól látszik, hogy mindhárom folyamat az 543-as lapot használja, amit a pfdata hivatkozásszámlálójának 3-as értéke is jól mutat.

Ekkor a B folyamat írni próbál a mutatott lapra. A folyamat védelmi laphibát okoz (W: 0 volt). A laphibakezelő látja, hogy az adott laptábla bejegyzés C/W-bitje be van állítva, így fizikai memória lapot kell allokálnia a B folyamat számára. Az 5.33.(b) ábra ezt az állapotot mutatja. Jól látszik, hogy a hiba kezelése során a B folyamathoz egy új lap (746) allokálódott, amelynek a hivatkozásszámlálója 1, hisz csak a B folyamat hivatkozik rá, míg az 543-as lap hivatkozásszámlálója eggyel csökkent, mert a B folyamat már nem rá hivatkozik. Amennyiben a C/W-bit be van billentve, de a hivatkozásszámláló már csak 1, akkor a kernel nem allokál újabb lapot, hanem az eredetiben törli a C/W-bitet, és engedi a folyamatnak a lap írását.

5.3.8.6. Hivatkozás bit szimulálása szoftverből

Néhány számítógép architektúra, mint például a VAX-11 vagy a MIPS R3000, nem nyújt hardver támogatást a hivatkozás (reference) bit használatához. Ekkor annak funkcióját egy szimulált szoftver hivatkozás bit veheti át. Ezt egy egyszerű mechanizmussal lehet biztosítani: be lehet vezetni egy ún. szoftver érvényességi (valid) bitet, ami a memórialap valódi érvényességi információját hordozza. Nevezzük az eredeti érvényességi bitet megkülönböztetésül hardver érvényességi bitnek, ezt a hardver teszteli, és érvénytelen állapota okozza a laphibát. A szoftver hivatkozás bitet most a kernel kezeli, ez tölti be a szokásos hivatkozás bit szerepét, a szoftver érvényességi bitet ugyancsak a kernel állítja. Induljunk onnan, hogy a lap érvényes, a hardver érvényességi bit be van billentve. Amikor adott időközönként a kernel (vagy a laplopó folyamat) törli a (most szoftver) hivatkozás bitet, vele együtt a hardver érvényességi bitet is törli, és a szoftver érvényességi bitet bebillenti, jelezve, hogy a lap valójában érvényes. (5.34.(a) ábra.) Ezek után, amikor hivatkozunk a lapra, az laphibát okoz, hiszen a hardver érvényességi bit ki van törölve. A laphiba kezelő megnézi, hogy valóban érvénytelen-e a lap. Látja azonban, hogy a szoftver érvényességi bit be van állítva, vagyis a lap érvényes, így most hivatkozás történt egy érvényes lapra. Ekkor a kernel beállítja mind a szoftver hivatkozás bitet, mind a hardver érvényességi bitet. (5.34.(b) ábra.) Ezzel a rendszer információt szerzett arról, hogy a lapot nem „túl régen” használták, és az érvényesség is helyreállt, a közeli jövőben történő hivatkozás már nem okoz laphibát. Amikor a laplopó folyamat végigvizsgálja a lapokat a memóriában, nem választ hivatkozott lapot, de törli a hivatkozás bitet és most vele együtt a hardver érvényességi bitet is. Amennyiben a lapra történik újabb hivatkozás, a fentiek szerint a szoftver hivatkozás bit beáll, és a lap „friss”-nek fog tűnni, amennyiben nem, a laplopó legközelebb elveheti a lapot. Természetesen amikor a lap valóban érvénytelenné válik, mind a hardver, mind a szoftver érvényességi bitet törölni kell.

5.34. ábra. ábra - A hardver, szoftver érvényességi és a szoftverből szimulált hivatkozás bit állapota (a) memóriahivatkozás előtt, (b) memóriahivatkozás után

A hardver, szoftver érvényességi és a szoftverből szimulált hivatkozás bit állapota (a) memóriahivatkozás előtt, (b) memóriahivatkozás után


5.3.8.7. A 4.3 BSD virtuális memóriakezelése

A 4.3 BSD virtuális memóriakezelő sok szempontból hasonlít a SVR3 vir­tuá­lis memóriakezelő alrendszerre, hasonló adatszerkezeteket használ, azonban a terminológia kissé eltérő. A 4.3 BSD-ben a fizikai memóriát egy ún. memória térkép (core map), a virtuális memóriát laptáblák, míg a háttértárat a diszk térképek (diszk map) írják le. A fizikai memória a használat szempontjából három részre oszlik. Az alsó memóriaterületeken helyezkedik a nem lapozott memória pool, ami tipikusan kernel kódot és a kernel statikusan allo­kál­ható adatszerkezeteit tartalmazza, középen helyezkedik el a lapozott me­­mó­ria pool, amit általános célra, a felhasználók folyamatai és a kernel dinamikus adatszerkezetei használnak (ez teszi ki a fizikai memória jelentős részét) és a fizikai memória felső címtartományában található a hiba buffer, amit a rendszerhívások során generált hibaüzenetek tárolására tartanak fenn.

Mint azt láttuk, a SVR3 implementáció a nem memória rezidens lapokról egy külön adatszerkezetben, a diszkblokk leíróban tárol információkat. Ez a megoldás jelentős redundanciát tartalmaz, és többletmemóriát igényel. A 4.3 BSD ezt a problémát úgy oldotta meg, hogy kihasználta, hogy a védelmi és érvényességi biteken kívül a többi bitmezőt a hardver nem vizsgálja, ha az érvényességi bit nincs beállítva. Mivel a nem memória rezidens lapok esetén az érvényességi bit törölt állapotú, így ezek a mezők más olyan információ tárolására használhatók fel, amik nyilvántartják ezen lapok helyét. Erre egy tipikus példa, hogy egy fill-on-demand lap esetén, ha azt egy végrehajtható állományból kell betölteni, akkor mivel ilyenkor az érvényességi bit törölt állapotú, és így a memóriakezelő tudja, hogy a fizikai lapkeret címét leíró mezőben más információ jelenik meg. Ebben az esetben egy biten jelezni lehet, hogy a fill-on-demand lap végrehajtható állományból töltendő vagy ki kell nullázni, és ha végrehajtható állományból töltendő, akkor a lapkeret címe helyett a végrehajtható állomány állományrendszerben elfoglalt megfelelő blokkcímét lehet ezen a helyen tárolni. Ez jelentős memória megtakarítást eredményezett a SVR3 implementációhoz képest.

A legújabb UNIX-rendszerek már egy új, memóriába ágyazott állományokon alapuló virtuális memóriakezelő alrendszert alkalmaznak, ami kialakulásában magán viseli az elődök fejlesztési tapasztalatait, azonban egy jelentősen eltérő struktúrát vezet be. Ennek tárgyalása meghaladja ezen könyv kereteit. Az irodalomjegyzék bőséges forrást tartalmaz, ami alapján az érdeklődő olvasó elmélyülhet a témában.