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ó

3.4. Tárkezelés

3.4. Tárkezelés

A multiprogramozott rendszerekben a CPU-t több folyamat megosztottan használja. Ahhoz, hogy megfelelő működési sebességet tudjunk biztosítani, egyszerre több folyamatot is a központi tárban (main storage, memory) kell tartanunk, hiszen, mint korábban láttuk, a háttértárak elérési ideje – gyorsító tár alkalmazása ellenére is – sokkal nagyobb a főtárénál, így nagyon lassú lenne, ha környezetváltásnál a háttértárról kellene behozni, illetve a háttértárra kellene kivinni a folyamatokat. Vagyis a központi tár igen fontos erőforrás, melyért több folyamat verseng, és szervezése, kezelése az operációs rendszerek tervezését, megvalósítását és teljesítményét befolyásoló egyik legfontosabb tényező.

3.4.1. A főtár megosztása a folyamatok között

A korábban tárgyalt tárhierarchia és általános társzervezési elvek folytatásaként ebben a részben a „klasszikus” tárkezelés két legfontosabb kérdését, a program címeinek kötését és a tárallokációt vizsgáljuk meg részleteiben.

3.4.1.1. A program címeinek kötése

A CPU közvetlenül csak a központi tárhoz tud hozzáférni, így a folyamatok aktuálisan végrehajtandó utasításának és az operandusoknak az operatív tárban kell elhelyezkedniük. Ez azt jelenti, hogy a programokat, adatokat végrehajtás előtt a másodlagos (háttér) tárakból be kell tölteni a központi (fizikai) memória valamilyen címére.

Egy programhoz általában lineáris, folytonos címtartományt szoktunk képzelni, amely 0-tól kezdődően (a program eleje) a program maximális címéig terjed. Ezt hívjuk logikai címtartománynak (logical address space). A mai rendszerekben a programok végrehajtása gyakorlatilag soha nem a 0. címtől kezdve, azaz a logikaival egyező fizikai címtartományban (physical address space) történik. Egy program a megírása (ahol értelemszerűen a logikai címtartományban vagy szimbolikus elnevezésekben gondolkodunk) és a végrehajtása (itt viszont a konkrét fizikai szó vagy byte címekre van szükség) között különböző fázisokon mehet keresztül (fordítás, kapcsolatszerkesztés, betöltés stb.). Az egyes lépések alatt a címek különböző módon lehetnek reprezentálva.

Egy-egy program lefordításakor, szerkesztésekor a fordító és a kapcsolatszerkesztő program első menetben általában a logikai címtartományban ad értékeket a szimbolikus hivatkozásoknak. Ugyanakkor a végrehajtáshoz már a fizikai címekre van szükség. A logikai és fizikai címtartomány közötti megfeleltetés, leképezés (mapping) elvileg bármelyik lépés alatt elvégezhető, de valamikor biztosan meg kell tenni. Nézzük meg tehát, hogy mikor (a program előkészítésének melyik fázisában) milyen lehetőségeink vannak a leképezés elvégzésére (3.10. ábra).

3.10. ábra. ábra - Logikai-fizikai címtranszformáció a felhasználói programok többlépcsős feldolgozása során

Logikai-fizikai címtranszformáció a felhasználói programok többlépcsős feldolgozása során


Statikus logikai-fizikai címleképezés

A címkonverzió történhet fordítás közben (compile time). Ha ismeretesek a program fizikai címei, akkor a leképezés elvégezhető a fordítás alatt. Ha a későbbiek során a program (fizikai) kezdőcíme megváltozik, akkor azt újra le kell fordítani. Éppen ezért, ezt a megoldást – merevsége miatt – csak speciális esetekben, a ROM (Read Only Memory, csak olvasható tár) memóriába kerülő programok esetén használják, egyébként pedig nem a végleges fizikai cím, hanem logikai cím rendelődik a tárgykódban a hivatkozásokhoz.

A végleges fizikai címek kötésére a következő lehetőség szerkesztés közben adódik (link time). Szerkesztésre akkor van szükség, ha egy program több, egymástól függetlenül lefordított modulból áll, amelyek hivatkoznak más modulban definiált logikai címre. A kapcsolatszerkesztő (linker) program feladata a modulok közötti kereszthivatkozások feloldása, és a modulok egymás mögé helyezése. Ennek eredményeképpen a tárgykódban a logikai címek helyére fizikai címek helyettesítődhetnek, azonban az esetek többségében csak a modulok logikai címtartományainak egyesítése történik meg, és egy áthelyezhető kódot (relocatable code) kapunk eredményül.

Ha a végleges címkonverzió betöltés közben (load time) történik, akkor a korábban kapott áthelyezhető kód címhivatkozásait módosítja a betöltő program (loader) az aktuális címkiosztás szerint.

Az eddig felsorolt megoldások ún. statikus leképezést valósítanak meg, azaz a fizikai címek hozzárendelése a program élete során egyszer, végrehajtásuk előtt következik be, és az értékek többé nem változnak.

Dinamikus logikai-fizikai címleképezés

A tárgazdálkodás szempontjából igen előnyös lehet, ha a program módosítás nélkül futtatható tetszőleges szabad tárterületre töltve, és helye akár végrehajtás közben is megváltoztatható. Ilyenkor dinamikus címleképezésről és dinamikus áthelyezhetőségről beszélünk. Dinamikus címleképezésnél a program memóriaképe logikai címeket tartalmaz, és a konkrét fizikai cím-hozzárendelés csak az utasítás-végrehajtás során következik be (speciális hardverelemek segítségével).

A legegyszerűbb dinamikus címleképezést a bázisrelatív címzés valósítja meg. Ha a program valamennyi címhivatkozása bázisrelatív címzési módú, a program tetszőleges helyre betölthető, a bázisregisztert a betöltési kezdőcímre állítva a program végrehajtható (3.11.(a) ábra). Ekkor annak sincs akadálya, hogy a program végrehajtásának megszakadása után a teljes programot egy új kezdőcímre töltsük vissza, vagy másoljuk át, és így folytatódjék a végrehajtás.

A bázisrelatív címzéshez igen hasonló (akár annak alesetének is tekinthető) dinamikus címleképezési mód az utasításszámláló-relatív címzés, melynek eredményeképpen pozíciófüggetlen kódot (PIC: Position Independent Code) kapunk, amelyet ugyancsak végrehajthatunk tetszőleges címre töltve (3.11.(b) ábra).

3.11. ábra. ábra - Dinamikus címleképezési módok (a) bázisrelatív címzés (a – a program fizikai kezdőcíme, b – virtuális (logikai) cím, r – fizikai cím), (b) utasításszámláló relatív címzés

Dinamikus címleképezési módok (a) bázisrelatív címzés (a – a program fizikai kezdőcíme, b – virtuális (logikai) cím, r – fizikai cím), (b) utasításszámláló relatív címzés


Késleltetett betöltés

Jobb tárkihasználás érhető el késleltetett betöltés alkalmazásával, vagyis ha a programok indításakor nem a teljes programot, hanem csak egyes részeit töltjük a tárba, míg más részek futás közben, szükség esetén töltődnek be. Az ide sorolható módszerek az esetek többségében dinamikus címleképezést igényelnek.

Dinamikus betöltésnek (dynamic loading) hívjuk azt a módszert, ha a programhoz tartozó egyes eljárások – áthelyezhető formában – a háttértáron vannak, és csak a meghívásukkor töltődnek be. Ilyenkor a futás elindításakor csak a főprogram kerül a memóriába, majd egy-egy eljárás meghívásakor először azt kell ellenőrizni, hogy a meghívott eljárás a memóriában van-e. Ha nem, akkor egy speciális programrész betölti a kívánt rutint, majd átadja a vezérlést az eljárásnak (3.12.(a) ábra).

A módszer előnye, hogy a programok összméretüknél általában lényegesen kisebb tárterületet igényelnek, a ténylegesen meg nem hívott eljárások soha nem töltődnek be. (A program részei között sokszor találunk olyan eljárásokat – például hibakezelő rutinokat – melyekre csak ritkán van szükség, így felesleges azokat minden esetben betölteni a memóriába.)

A dinamikus betöltést a programozónak magának kell megszerveznie, a megvalósításhoz az operációs rendszer nem, legfeljebb a nyelvekhez tartozó fordító, szerkesztő és futtató programok adnak támogatást.

A késleltetett betöltés következő, az előbbi módszer módosított – az operációs rendszer által is támogatott – változata a dinamikus könyvtárbetöltés vagy dinamikus kapcsolatszerkesztés (dynamic linking). A programban használt rendszerkönyvtárak eljárásai helyett a szerkesztő csak egy csonkot (stub) tesz be a programba, mely valamilyen hivatkozást tartalmaz egy könyvtárra és ezen belül az adott eljárásra. A csonk első meghívásakor a rendszer a kívánt eljárást betölti a tárba, majd az eljárás fizikai kezdőcímét a hívó eljárásban szereplő logikai címhez rendeli. Az ezután következő hívások már a betöltött eljárást fogják – időveszteség nélkül – meghívni (3.12.(b) ábra). (A könyvtárakat természetesen pozíciófüggetlenül kell kódolni.)

A módszer előnye a csökkentett tárfelhasználáson kívül az is, hogy a könyvtárak módosítása (hibajavítás, újabb, javított változatra cserélés) esetén nem szükséges az összes, a módosított könyvtárat használó programot újrafordítani. Az azonban előfordulhat módosított könyvtárak esetén, hogy a memóriába ugyanannak az eljárásnak különböző verziói (egymástól eltérő példányai) töltődnek be, attól függően, hogy a futó folyamatok módosítás előtt vagy után hívták meg az eljárást. Működési problémát okozhat, ha a változtatások a korábbival inkompatíbilis új verziót eredményeznek.

A dinamikus kapcsolatszerkesztést alkalmazó korszerű rendszerek annyiban különböznek a fenti sémától, hogy a betöltött eljárások más folyamatok számára is rendelkezésre állnak, azaz a csonk első meghívásakor a rendszer figyelembe veszi azt is, ha más folyamat már meghívta az eljárást, és így a kívánt eljárás már a tárba töltődött. Ilyenkor ez a fizikai cím rendelődik a hívó eljárás logikai címéhez. A megoldás felveti az újrahívhatóság problémáját (amikor több folyamat egyidőben is végrehajthatja ugyanazt az eljárást), melyről a fejezetben később részletesebben is szó lesz.

A központi tár fizikai méreténél nagyobb méretű programok írását és futtatását teszi lehetővé az átfedő programrészek (overlay) technikája. A módszer kifejlesztésénél abból a felismerésből indultak ki, hogy a programoknak csak egy részét teszik ki azok a programrészek, illetve adatok, amelyekre a teljes futási idő alatt szükség van, így elegendő ezeket állandóan a memóriában tartani. A programok fennmaradó része pedig „szétvágható” olyan részekre, amelyek időben elkülönülten – azaz egyidőben csak az egyik – dolgoznak. Ezeket szükség esetén egyesével töltjük be, majd használatuk után újra a háttértárba menthetjük (ezt sok rendszer nem teszi meg), hogy a felszabaduló területre egy másik overlay részt tölthessünk (3.12.(c) ábra). (A módszer tehát tulajdonképpen annyiban különbözik a dinamikus betöltéstől, hogy itt a betöltött részek nem maradnak bent a memóriában állandó jelleggel a további futás idejére.)

Az átfedés számára fenntartott tárterület a legnagyobb programrészlet hosszával egyezik meg. Az overlay technika szempontjából az átfedő programrészek a háttértáron tartalmazhatnak abszolút címeket is (így a módszer nem igényel feltétlenül dinamikus címleképezést), hiszen ugyanarra az ismert kezdőcímre töltődnek be.

A dinamikus betöltéshez hasonlóan ez a módszer sem igényel különleges támogatást az operációs rendszertől. Egyszerű fájlrendszer alkalmazásával megoldható az átfedő programrészek memóriába olvasása, illetve háttértárra írása, azonban az overlay részek tervezése a program szerkezetének és futás közbeni viselkedésének alapos ismeretét igénylik a programozótól, ezért manapság ritkán használják, csak ott, ahol a fizikai memória mérete ezt szükségessé teszi, és más, korszerűbb automatikus módszerek (például virtuális tárkezelés) nem valósíthatók meg.

3.4.1.2. Társzervezési módszerek

A számítógépek történetének korai időszakában a memória viszonylag drága erőforrásnak számított. Ezért a rendszertervezők komoly erőfeszítéseket tettek a központi tár használatának optimalizálására. A mai tárak ára egyre alacsonyabb, ezért a „gazdaságos” tárkihasználás némileg mást jelent, mint korábban. (A „gazdaságosság” mögött húzódó költségfüggvényben a hangsúlyok eltolódtak a mai élet kihívásai által diktált követelmények – például felhasználói kényelem, nagy komplexitású, beágyazott rendszerek összetett feladatai, valósidejű működés – felé.)

Társzervezés alatt azt a módot értjük, ahogyan a központi tárat a felhasználók (folyamatok) között megosztjuk. Az „optimális” tárhasználatra való törekvés során felmerült kérdések közül az első megválaszolandó mindjárt az volt, hogy egyszerre csak egyetlen, vagy több felhasználó is használhassa-e a főmemóriát. Később az vetődött fel, hogy ha egy időben párhuzamosan több felhasználó között osztjuk meg a memóriát, akkor vajon mindegyikhez ugyanakkora területet rendeljünk-e, vagy különböző méretű részekre, partíciókra (partition) osszuk azt. És ezeknek a partícióknak a hossza állandó vagy pedig változó legyen-e? Eldöntendő az is, hogy a programok a (felhasználói) memórián belül bárhol, vagy csak bizonyos részeken futhatnak-e, továbbá, hogy a folyamatokhoz rendelt fizikai memória területnek egybefüggőnek kell-e lennie, vagy össze nem függő részekből is állhat.

3.12. ábra. ábra - Késleltetett betöltési módok (a) dinamikus betöltés (b) dinamikus könyvtárbetöltés (c) átfedő programrészek

Késleltetett betöltési módok (a) dinamikus betöltés (b) dinamikus könyvtárbetöltés (c) átfedő programrészek


A fenti kérdésekkel is érzékeltethető, egyre táguló lehetőségek a történeti fejlődés során nyíltak meg. Mindegyik változatra találhatunk működő rendszert, ezért ennek a pontnak további részében azt tekintjük át, hogy ezek mi­lyen sajátosságokkal rendelkeznek, és hogyan is lehet megvalósítani őket.

Egypartíciós rendszer

Az egypartíciós rendszereknél egyidőben egyszerre egyetlen folyamat használhatja a központi tárat, így az operációs rendszeren – és a speciális tárterületeken, mint például a megszakításvektorok, a periféria-címtartományok – felüli folytonos címtartományon teljes egészében ez a folyamat futhat.

A betöltő a program indításakor azt az első szabad címre hozza be. Ha a program futása során az operációs rendszernek több tárra van szüksége, akkor azt vagy a program által nem használt területről – a tár másik végéről – „lopja” el, vagy a programot kell áthelyezni, ami hardvertámogatás nélkül nehézkes.

Az operációs rendszer védelmére elegendő egyetlen regiszter, amely a program legkisebb címét tartalmazza. A folyamat futása közben – felhasználói módban – a tárkezelő hardver minden egyes kiadott memóriacímet összehasonlít a határregiszter értékével, és ellenőrzi, hogy minden hivatkozás a tárolt cím felett legyen. Rendszerhíváskor a processzor olyan működési módba kerül át (rendszer vagy kernel mód), ahol ez a védelem kikapcsol, és az operációs rendszer a teljes tárat eléri. A határregiszter értéke csak rendszermódban változtatható meg.

A folyamatok váltása a központi tár és a háttértár közötti a későbbiekben részletezett tárcsere (swapping) segítségével történhet.

3.13. ábra. ábra - Egypartíciós memória szervezés

Egypartíciós memória szervezés


Többpartíciós rendszer

Bár swapping segítségével egypartíciós rendszerekben is megvalósítható valamiféle multiprogramozás, azonban ez a mágneslemezes átvitel nagy időigénye miatt jelentősen megnöveli a környezetváltási időt, így legfeljebb a lemeznél még sokkal lassabb periferiális műveletek esetén, vagy a felhasználói esélyegyenlőség biztosítása érdekében volt érdemes átkapcsolni más folyamat végrehajtására. A hatékony multiprogramozás megkövetelte, hogy egy időben egyszerre több folyamat is a tárban tartózkodjék.

Multiprogramozás rögzített partíciókkal

A korai rendszerekben a felhasználói tárterületet olyan különböző méretű partíciókra osztották, melyek mérete a rendszer működése során nem változhatott (rögzített partíciók, fixed partition). A programok a méretüknek megfelelő partícióban futtathatók. Minden partícióban egyetlen folyamat tartózkodhat. Így a multiprogramozás fokát alapvetően a partíciók száma korlátozza.

Egy-egy folyamat befejeződése után az operációs rendszer egy következő folyamatot választ ki futásra a szabad partícióhoz, vagy az egyetlen közös várakozási sorból (ilyenkor nyilván figyelembe kell venni, hogy a programok csak a maximális memóriaigényüknek megfelelő méretű partícióban futtathatók), vagy pedig a már eleve ehhez a partícióhoz kötött várakozási sorból (ilyenkor a hosszú távú ütemező a belépő folyamatokat közvetlenül a különböző partíciókhoz tartozó várakozási sorokba sorolja) valamilyen – általában a legjobb illeszkedést kereső – stratégia szerint (3.14. ábra).

3.14. ábra. ábra - Többpartíciós memória szervezés

Többpartíciós memória szervezés


Ez a tárkezelési mód nagyon egyszerű, ugyanakkor nagyon merev, így végeredményben rossz tárkihasználást biztosít. A folyamatok nem használják ki teljesen a partícióban rendelkezésükre álló tárterületet, minden partícióban a benne futó folyamathoz rendelt, ám kihasználatlan memóriaterület, „lyuk” marad. Ezt hívjuk belső tördelődésnek (internal fragmentation).

Multiprogramozás változó méretű partíciókkal

Fejlettebb operációs rendszerekben a folyamatok – igényeiknek megfelelő – változó méretű partíciót (variable partition) kapnak. Így a partíciókon belül nincs kihasználatlan memóriaterület.

A belépő folyamatok számára az ütemező egy kellően nagy, folyamatos, szabad memóriaterületet keres, melyet két részre oszt. A szükséges nagyságú területet a folyamathoz rendeli, a maradék pedig továbbra is szabad marad. Ezzel sikerül kivédeni a belső tördelődést.

Változó méretű partíciók használata esetén a problémák akkor kezdődnek, amikor folyamatok befejezik a futásukat és az operációs rendszer felszabadítja az általuk foglalt területet. Így lyukak keletkeznek az allokált memória- részek között. Ezek ugyan hozzárendelhetők más folyamatokhoz, azonban szinte biztos, hogy előbb-utóbb a folyamatokhoz rendelt tárterületek között akkora szabad területek maradnak, melyek egyenként túl kicsik a folyamatok számára, és így kihasználatlanok maradnak. Ezt a jelenséget hívjuk külső tördelődésnek (external fregmentation).

A külső tördelődés, ha meghalad egy bizonyos mértéket, jelentősen késleltetheti újabb folyamat elindítását, mindamellett, hogy összességében elegendő szabad terület lenne ehhez. Azonban ezek a területek nem alkotnak folytonos címtartományt. Ezen segíthet a szabad helyek tömörítése (com­paction, garbage collection), azaz a tár egyik végére rendezése. Ilyenkor az operációs rendszer úgy helyezi át a partíciókat, hogy azok érintkezzenek egymással, és így összefüggő szabad területet kapjunk.

A módszer ugyan megoldja a problémát, azonban nagyon időigényes, hardver támogatást (dinamikus áthelyezhetőséget) igényel, megzavarhatja a rendszer működését (például egy interaktív rendszer válaszideje váratlanul jelentősen megnövekedhet), és a tárterületek mozgatásához az áthelyezési információkat meg kell őrizni.

Mindezek miatt nem egyértelmű, hogy érdemes-e alkalmazni. Összességében jobban járhatunk, ha ehelyett inkább várakozunk, amíg más futó folyamatok is befejeződnek, vagy pedig a tárterület lefoglalása során próbáljuk optimalizálni a kihasználást.

A külső tördelődés csökkentésére különböző stratégiákat dolgoztak ki a folyamatokhoz rendelendő tárterület kiválasztására. Az operációs rendszer a betöltendő program számára a szabad területek közül az alábbiak szerint választhat.

Az első megfelelő (first fit) algoritmus a tár elejéről indulva az első elegendően nagy területet foglalja le a folyamat számára. Az algoritmus igen gyors, eredményeképpen a memória mintegy 30%-a marad kihasználatlan. (Ezt hívják 50%-os szabálynak, mivel a folyamatok által lefoglalt területek összegének mintegy fele marad kihasználatlan.)

A következő megfelelő (next fit) algoritmus annyiban különbözik az előzőtől, hogy a keresést nem a tár elején, hanem az utoljára lefoglalt tartomány végétől kezdi. Hatásfoka hasonló az előzőéhez.

A legjobban megfelelő (best fit) algoritmus a legkisebb, még elegendő méretű területet foglalja le. A mögöttes filozófia szerint, minél kisebbek a megmaradó lyukak, összességében annál kevesebb lesz a kihasználatlan memóriaterület. A módszer az előzőeknél lassabb, és bár első pillanatra hihetetlennek tűnik, de némileg rosszabb memória kihasználást eredményez az előzőeknél.

A legrosszabban illeszkedő (worst fit) algoritmus az előzővel épp ellentétben, a legnagyobb szabad területből foglal, mert abban bízik, hogy a megmaradó „nagy” lyuk elegendően nagy lesz egy további folyamat számára. Szimulációs vizsgálatok alapján azt mondhatjuk, hogy ez a legrosszabb hatásfokú algoritmus (a memória terület kb. 50%-a marad kihasználatlan).

A statisztikai vizsgálatok eredményeképpen tehát megállapíthatjuk, hogy hatásfokát tekintve az első három algoritmus nagyjából azonos kihasználtságot eredményez. Figyelembe véve, hogy az első megfelelő algoritmus megvalósítása a legegyszerűbb és ez működik a leggyorsabban, mindenképpen ez tűnik a legjobbnak.

A többpartíciós rendszerek megjelenésével nemcsak az operációs rendszert, hanem más folyamatok tárterületét is védeni kell a hibás (vagy rosszindulatú) folyamatok működésének következményeitől. Ezért a védelem két határregisztert használ, amelyekbe a folyamat futásakor, a hozzá tartozó címtartomány határait tölthetjük. Az egyes címzéseknél a hardver a tartományból való kicímzést figyeli.

Tárcsere

A folyamatoknak a háttértárról a memóriába való bevitelét, illetve a memóriából a háttértárra való kivitelét a tárcsere (swapping) technika segítségével oldhatjuk meg. Ennek során az operációs rendszer egy-egy folyamat teljes tárterületét a háttértárra másolja, így szabadítva fel a területet más folyamatok számára. Ehhez természetesen az operációs rendszernek pontosan ismernie kell a folyamatok aktuális tárigényét.

A tárcsere a perifériás átvitel miatt időigényes – egyszerre nagy tárterületet kell mozgatni –, így jóval hosszabb időt vesz igénybe, mint egy szokásos környezetváltás. A tárcserével töltött idő jelentősen megnövelheti a futás idejét, ezért mindenképpen célszerű a tárcsere idejét viszonylag alacsonyan tartani az effektív futási időkhöz képest (például Round–Robin-ütemezést alkalmazó rendszer tervezésekor az időszelet hosszának megválasztásánál figyelembe kell venni a swapping idejét és arányát), valamint lehetőség szerint minimalizálni kell a tárcserék számát és optimalizálni magát a műveletet.

Az ütemezőnek célszerű a tárban levő futásra kész folyamatok közül – ha van ilyen – választani. A tárterület elmentésénél pedig figyelhetünk arra is, hogy egy változatlan, a háttértáron meglevő tartományt nem kell újra kiírni. További gyorsítást tesz lehetővé az átlapolt tárcsere (overlapped swapping), vagyis amikor az éppen futó folyamat végrehajtásával párhuzamosan történik egy másik folyamat kivitele, illetve egy harmadik behozatala (3.15. ábra).

3.15. ábra. ábra - Átlapolt tárcsere

Átlapolt tárcsere


Tárcserét korszerű rendszerek a várhatóan hosszabb ideig várakozni kényszerülő folyamatoknál, vagy a rendszer túlterheltségét (például feladatok, azonos igények torlódása) megelőzendő alkalmaznak. Tárcserére lehet szükség új folyamat létrehozása (fork) esetén (ha nincs elég hely a szülő és a gyerek számára), ha egy folyamat tárigénye – például a verem mérete – megnő, illetve ha egy másik – nagyobb prioritású – folyamatnak van szüksége a memóriaterületre.

Ha szükség van további memóriaterületre, akkor el kell dönteni, melyik folyamat legyen az áldozat. Ehhez figyelembe vehetjük a folyamatok állapotát, prioritását, futási, illetve várakozási idejét stb. Behozatalnál pedig azt kell megválaszolni, hogy a háttértáron levők közül mikor és kit hozzunk be, szintén a fenti szempontok esetleges figyelembevételével. Mindkét esetben figyelnünk kell azonban arra, hogy a folyamatokat feleslegesen ne pakolgassuk, valamint, hogy a választási algoritmus ne vezessen éhezésre.

Statikus logikai-fizikai címleképezésnél egy további megkötést jelent, hogy a háttértárra kivitt folyamatokat ugyanarra a memóriaterületre kell behozni, amelyet korábban elfoglaltak. Dinamikus – futás közbeni – címtranszformáció alkalmazása esetén a folyamatok minden további nélkül betölthetők az előzőtől eltérő memóriaterületre.

Az eddigi társzervezési megoldásoknál abból a feltételezésből indultunk ki, hogy a folyamatok fizikailag is folytonos memóriaterületet használnak. A korszerű tárkezelő hardverek azonban lehetővé teszik, hogy a folyamatok folytonos logikai címtartományának nemfolytonos fizikai címtartományt feleltessünk meg [ezt hívjuk mesterséges folytonosságnak (artificial conti­nuity)]. Ezzel megszüntethető a külső, és jelentősen csökkenthető a belső tördelődés.

A tárcserék ideje erősen függ az átvitt információ mennyiségétől, azaz az átvitt memóriaterület nagyságától. Ezért a tárcsere idő lecsökkentésének kézenfekvő módjaként kinálkozik, hogy ne a teljes folyamatokat, hanem csak egy részüket kelljen mozgatni a memória és a háttértár között. Ehhez az igazi segítséget azok a speciális hardverelemek jelentették, amelyek lehetővé tették, hogy a futó folyamatnak ne a teljes címtartománya, hanem annak csak egy része tartózkodjék a központi tárban. Ilyenkor előfordulhatnak olyan hivatkozások, amelyekhez nem tartozik érvényes fizikai cím, mivel a hivatkozott cím nincs a memóriában. Megfelelő hardver-szoftver összjáték esetén azonban a rendszer képes arra, hogy a felhasználó számára észrevétlenül a szükséges programrészletet a háttértárból a központi tárba töltse, és a korábbi hivatkozást – ezúttal már sikeresen – végrehajtsa.

A következő korszerű társzervezési módszerek közös jellemzője, hogy egyrészt mesterségesen folytonos címtartományt használnak (azaz a fizikai címtartomány általában több, egymástól elkülönült memóriablokkból áll), másrészt lehetőséget adnak arra, hogy a folyamatok tárterületének csak egy része tartózkodjék egyidőben a memóriában. A szabad tárterületek rugalmas felhasználhatósága érdekében ezek a módszerek futás közbeni címleképezést alkalmaznak.

A leképezéshez szükséges többletinformációk mennyiségének elviselhető szinten tartása céljából a gyakorlati címtranszformációk tartományonként megőrzik a megfeleltetés folytonosságát. Egy-egy összefüggő logikai címtartományt (blokk) egy-egy önmagában összefüggő, de tetszőleges fizikai címtartományra képeznek le.

A megfelelő sebességet hardver támogatás biztosítja. Minden egyes folyamathoz tartozik egy ún. blokktábla (block map table), amely a logikai cím–fizikai cím összerendeléseket tartalmazza (a folyamatonkénti külön blokktáblára azért van szükség, mert a folyamatok logikai címtartománya fedi egymást, de fizikai címtartományuk el kell különüljön). A logikai címek <b, d>, azaz <blokkcím, blokkon belüli eltolás (displacement)> formában adottak. A blokktábla minden egyes blokkhoz megadja a blokk fizikai kezdőcímét. A hardverrel támogatott címleképezés mindig egy meghatározott módon elérhető (aktuális) blokktábla használatával történik. A futó folyamathoz tartozó blokktáblát az operációs rendszer teszi aktuálissá környezetváltáskor. Szokásos megoldás, hogy a címképző egység egy mutatón (pointer) keresztül éri el a blokktáblát, mert ilyenkor az aktuálissá tétel igen gyors lehet, hiszen csak a mutató átállítását igényli.

Szegmensszervezés

A programozók a programjaikat nem egyetlen összefüggő, folyamatos logikai címtartománynak látják, hanem sokkal inkább úgy, mint több, különböző funkcionális részegység együttesét, amelyek egy-egy részfeladatot oldanak meg (például a főprogram, egy-egy eljárás, a verem stb.). A részegységek fizikai elhelyezkedése pedig közömbös a felhasználó számára.

A szegmensszervezés (segmentation) ezt a látásmódot tükrözi, a cím-transzformációnál a logikai szegmenseket (segment) felelteti meg egy-egy blokknak. Az értelemszerűen különböző hosszúságú blokkok önmagukban folytonos fizikai címtartományt foglalnak el, a címképzés a blokktáblás sémát követi (3.16. ábra). Belső tördelődés nem lép fel.

3.16. ábra. ábra - Címtranszformáció szegmensszervezés esetén

Címtranszformáció szegmensszervezés esetén


A blokktáblában a szegmensek hosszát is tárolni kell. Ezzel biztosítható, hogy a folyamat ne címezhessen ki a szegmensből. A címképző hardver a szegmens területén kívülre mutató túlcímzést figyeli, és ha ilyen előfordul, hibamegszakítást generál (segment overflow fault).

Ahhoz, hogy a szegmentált címzési mód segítse a szegmensenkénti tárcserét is, a blokktábla egy bitje (residency bit) azt mutatja, hogy a szegmens a memóriában van-e vagy sem. Ha olyan szegmensre történik hivatkozás, amelyik nincs a tárban, ennek a bitnek az állása alapján a címképző hardver hibamegszakítást generál (missing segment fault). Természetesen a tárcserék lebonyolításához tárolni kell azt az információt is, hogy a háttértáron hol található meg a szegmens.

A szegmensszervezés lehetőséget ad arra, hogy több folyamat egy-egy logikai szegmense ugyanarra a fizikai címtartományra legyen leképezve, vagyis, hogy a folyamatok közös eljárásai egyetlen példányban tárolódjanak a memóriában (osztott szegmenshasználat, segment sharing).

Szegmensszervezés esetén könnyen megvalósítható a hozzáférések szabályozása (access control). A folyamatoknak az egyes szegmensekhez különböző hozzáférési módokat engedélyezhetünk. Ezzel a folyamat tárterületét védhetjük saját működésének hibáitól, illetve osztott szegmenshasználat esetén a különböző folyamatoknak különböző hozzáférési jogosultságokat adhatunk. Szokásos hozzáférési jogok az olvasási jog (read access, ilyenkor a folyamat a szegmens területét olvashatja), írási jog (write access, a folyamat a szegmens területére írhat, az ott levő értékeket módosíthatja) és a végrehajtási jog (execute access, a szegmensben gépi utasítások vannak, amelyeket a folyamat végrehajthat). A módosítható adatterületek helyes osztott használatához a kölcsönös kizárást a folyamatoknak kell biztosítania, ehhez a hardver nem nyújt támogatást.

Lapszervezés

A szegmensszervezésnél használt változó méretű blokkok megoldást jelentenek a belső tördelődésre, azonban óhatatlanul fellép a külső tördelődés jelensége. Ez utóbbi megszüntetéséhez azonos, rögzített méretű blokkok és nekik megfelelő fizikai memória keretek (frame) használata szükséges (vagyis, hogy a folyamatok tárterületét ilyen egységekben allokáljuk). Az azonos méretű blokkokra a lap (page), az ennek megfelelő társzervezésre pedig a lapszervezés (paging) elnevezést használjuk. A külső tördelődés megszüntetésének ára a belső tördelődés megjelenése. A folyamatok utolsó lapja átlagosan csak félig lesz tele, a tördelődési veszteség tehát átlagosan folyamatonként fél lap. A lapméretet az egyes rendszerekben egymásnak ellentmondó szempontok mérlegelése alapján választják meg. A lapméret csökkentésével csökken a belső tördelődésből származó tárveszteség. Ugyanakkor nő a laptábla mérete, és az adategységre vonatkoztatott átlagos keresési (címzési, lappangási) idő növekedése miatt csökken a memória és a háttértér közötti adatátvitel sebessége (ugyanolyan adatmennyiséget több blokkban kell átvinni).

A lap mérete gyakorlati szempontok miatt mindig 2 hatványa (általában 512 és 16 K byte között), ugyanis ez esetben a címtranszformáció második részében (a blokkon belüli eltolás figyelembevételénél) nem szükséges összeadást végezni, hanem elegendő az eltolást egyszerűen a fizikai címben a kisebb helyiértékű bitek helyére másolni (3.17. ábra).

3.17. ábra. ábra - Címtranszformáció lapszervezés esetén

Címtranszformáció lapszervezés esetén


Közvetlen leképezés esetén a folyamathoz tartozó minden lap fizikai címe egy laptáblában van, és a transzformáció mindig innen veszi elő a fizikai lapcímet. Mivel a lapok mérete viszonylag kicsi a programok méretéhez képest, ezért a laptábla mérete meglehetősen nagy lehet, és így nehéz speciális, elkülönített, gyors hozzáférésű tárban tartani. Ha pedig a laptábla a memóriában helyezkedik el, akkor minden egyes laptábla hozzáférést igénylő címtranszformációt magában foglaló memóriaművelet két memória hozzáférést igényel, ami jelentős lassulást okoz.

A laptábla méretének csökkentésére a megoldást a többszintű laptábla alkalmazása kínálja. A modern rendszerek korábban elképzelhetetlen nagyságú logikai címtartomány használatát teszik lehetővé, amely azonban egyben hatalmas méretű laptáblák használatát is jelenti. Gondoljuk csak meg, hogy egy 32 bites logikai cím 4K (212) byte méretű lapok használata esetén 1 millió (220) laptábla bejegyzést jelenthet. Ez – bejegyzésenként 4 byte-tal számolva – önmagában 4Mbyte fizikai memóriát igényel. Ekkora méretű táblák memóriában tartása, ki- és bevitele semmiképpen sem célszerű. Ugyanakkor már utaltunk rá, hogy a folyamatok egy adott időintervallumban a teljes címtartományuknak nagy valószínűséggel csak egy-egy részét használják. Így, ha a laptáblát megfelelően osztjuk részekre, elegendő néhány rész-laptáblát a memóriában tartani.

A gyakorlatban – az effektív hozzáférési idő növekedése miatt – legfeljebb két, illetve háromszintű laptáblát szoktak használni. Kétszintű laptábla-szervezés esetén a címképzést a 3.18. ábra mutatja.

3.18. ábra. ábra - Címtranszformáció lapszervezés esetén kétszintű laptábla használatával

Címtranszformáció lapszervezés esetén kétszintű laptábla használatával


A hozzáférési idő problémájára a tipikus megoldást az asszociatív leképezés, azaz egy speciális szervezésű, gyors asszociatív tár (associative regis­ters, translation look-aside buffer) alkalmazása jelenti, ahol a folyamat bizonyos – gyakran vagy a közeljövőben várhatóan használt – lapjainak logikai és fizikai címei találhatók. Az asszociatív tár gyors hozzáférésű és egyetlen művelettel kiadja a bemenetére juttatott logikai címhez tartozó fizikai címet, tehát lényegében a laptábla gyorsító tárjaként funkcionál.

A sebességben megfelelő asszociatív tárak általában nem elegendően nagyok akár csak egyetlen folyamat teljes laptáblájának befogadására sem, így az asszociatív leképezés megvalósítására kombinált technikák alakultak ki. A fizikai lapcím keresése a logikai lapcím alapján egyidejűleg kezdődik mind az asszociatív tárban, mind pedig a direkt laptáblában (ami ilyenkor általában memóriában tárolt). Ha a keresett cím megvan az asszociatív tárban, ez igen gyorsan – gyakorlatilag még a direkt táblához forduló memóriaművelet megkezdése előtt – kiderül, és a direkt táblához fordulás leáll. Mivel az asszociatív tár csak a laptábla töredékét képes tárolni, tartalmát valamilyen stratégiával folyamatosan frissíteni kell, hogy a várható hivatkozások minél nagyobb valószínűséggel megtalálhatók legyenek benne. Később még részletesen elemezzük azt a megfigyelést, hogy azonos lapra általában több egymást követő hivatkozás történik rövid időn belül. Ezért, ha a hivatkozott lapcím nem található az asszociatív tárban, a direkt leképezés eredményeként kapott logikai-fizikai címpárt érdemes felvenni az asszociatív tárba valamelyik régen használt bejegyzés helyére. Környezetváltáskor az asszociatív tár tartalmát is cserélni kell, hiszen ugyanazon logikai címekhez most új fizikai címek fognak tartozni.

Mivel a programok futásuk egyes időszakaiban a teljes címtartományuknak csak kis részét használják, ezért az asszociatív tárak – kis méretük ellenére – általában 80–99% közötti találati arányt (hit ratio) tesznek lehetővé (találati aránynak nevezzük az asszociatív tárban megtalált hivatkozott lapok arányát).

Az egyszerűség kedvéért tegyük fel, hogy a memória hozzáférés ideje 100 nsec, az asszociatív tárban való keresés pedig 20 nsec-t igényel. Asszociatív tár használata nélkül a fizikai memóriacím elérése 200 nsec-t igényel (100 nsec laptábla hozzáférés + 100 nsec memóriakeret elérés). Asszociatív tárral, 90%-os találati arányt feltételezve, az effektív memória hozzáférési idő kb. 128 nsec [0,9*(20 nsec asszociatív tár elérés + 100 nsec memóriakeret elérés) + 0,1*(100 nsec laptábla hozzáférés + 100 nsec memóriakeret elérés)], az elvi 100 nsec helyett.

Az eddigi társzervezési módszerekkel ellentétben lapszervezés esetén az eltolás tekintetében nincs szükség túlcímzés elleni védelemre, hiszen minden kiadható cím lapon belül marad. Túlcímzés csak a lapcímben történhet, ami a laptábla méretének megfelelő határregiszter segítségével ellenőrizhető. A memóriavédelem az egyes fizikai memóriakeretekhez rendelt védelmi bitek segítségével történhet, amelyeket az elviselhető sebesség érdekében hardvernek kell ellenőriznie. A számítógépek többsége azonban nem tartalmazza ezt a hardvertámogatást.

A szegmensszervezéshez hasonlóan szükség van viszont egy olyan bitre (érvényességi, valid bit), amely azt mutatja, hogy a lap a memóriában van-e, és természetesen a háttértáron való elhelyezkedés információját is tárolni kell valahol.

A szegmensszervezésű rendszerekhez hasonlóan a lapszervezésű rendszereknél is nagy előny az osztott laphasználat lehetősége. Ilyenkor több folyamat hivatkozhat azonos fizikai lapokra, amelyeket az esetek nagy részében azonos logikai címen is látnak, de ez nem szükségszerű. Képzeljük, mekkora tárigény csökkenést jelent az, hogy a több felhasználó által használt programok kódrészének, illetve a könyvtári eljárásoknak – szövegszerkesztő, fordító, ablakozó, adatbáziskezelő stb. – csak egyetlen példányát kell a memóriában tartani. Ezek a lapok általában olyan eljárásokat tartalmaznak, amelyek kódja végrehajtás során sohasem változik, így több folyamat egyidőben is végrehajthatja ugyanazt az eljárást (újrahívható, reentrant code). Természetesen minden folyamatnak külön regiszter- és adatkészlete kell hogy legyen a változók számára. A védelemmel kapcsolatban korábban mondottakkal ellentétben az ilyen közösen használt lapoknál az operációs rendszer gondoskodik a „csak olvasható” jelleg biztosításáról.

Kombinált szegmens- és lapszervezés

A kombinált szervezés egyesíti mind a szegmens-, mind pedig a lapszervezés előnyeit. A logikai cím három komponensből (szegmenscím, lapcím, eltolás) áll. A lapszervezésből következően nincs külső tördelődés. A szegmens- szervezés miatt a feladat logikai szerkezete tükröződik a társzerkezetben és egyszerűbben megvalósítható az osztott használat. A belső tördelődési veszteség ezzel szemben szegmensenként jelentkezik.

A hozzáférési jogok ellenőrzése és az osztott tárhasználat a szegmensszervezésnek megfelelően történik. A címtranszformáció lényegében első szinten egy laptábla-címeket tartalmazó szegmenstábla, második szinten pedig szegmensenként egy-egy fizikai lapcímeket tartalmazó laptábla segítségével történik, az esetleges asszociatív tár pedig itt címhármasokat tárol, és szegmenscím, lapcím párossal kereshető.

3.4.2. Virtuális tárkezelés

Az előző részben különböző memóriakezelési stratégiákat vizsgáltunk. Mindegyik módszernek az volt az alapvető célja, hogy lehetőleg kellően sok folyamatot tudjunk a memóriában tartani egyszerre, és így megfelelő szintű mul­ti­programozást tudjunk biztosítani. Azonban a fenti technikák alapvetően megkövetelték, illetve törekedtek arra, hogy a programok végrehajtásuk előtt minél teljesebb terjedelmükben a memóriába kerüljenek. A késleltetett, illetve overlay betöltések, tárcserék, a felhasználók és a programfejlesztési segédeszközök szintjén tették lehetővé a tártakarékos futtatást, általános megoldást nem kínáltak.

Ezzel szemben a virtuális tárkezelés (virtual memory management) a lap-, illetve szegmensszervezésre épülően – olyan szervezési elvek és az operációs rendszer olyan algoritmusainak összességét takarja, mely megengedi és biztosítja, hogy a rendszer folyamataihoz tartozó logikai címtartományoknak csak egy – a folyamat futásához éppen szükséges – része legyen a központi tárban, de ennek ellenére bármelyik folyamat szabadon hivatkozhasson bármilyen, tartományában szereplő logikai címre.

3.4.2.1. A működés alapjai

A korábbi algoritmusok tárgyalása során láttuk, hogy nem kerülhető meg az, hogy a végrehajtandó utasítások a fizikai memóriában legyenek. Első megközelítésként a teljes logikai címtartományt a fizikai memóriába olvasták. Az átfedő programrészek alkalmazása és a dinamikus betöltés valamelyest lazított a fenti követelményen, azonban e technikák sok óvatosságot és erőfeszítést követeltek a programozótól. A virtuális tárkezelés ezzel szemben a programozó elől is rejtett megoldást kínál, amelyet az operációs rendszer nyújt, és amely teljes szabadságot biztosít akár a fizikai memória méretét sokszorosan meghaladó logikai (virtuális) címtartományok használatában.

A virtuális tárkezelés előzményeit tekintve különböző programok vizsgálata során bebizonyosodott, hogy nem szükséges, hogy a programok teljes logikai memóriaterülete a központi tárban legyen, mert a programok nem használják ki a teljes címtartományukat:

  • tartalmaznak ritkán futó kódrészleteket (például a hibakezelő rutinok),

  • a statikus adatszerkezetek általában túlméretezettek (például vektorok, tömbök, szimbólum táblák definiálásánál a ténylegesen szükségesnél sokkal nagyobb területeket foglalhatunk le),

  • a program különböző részei időben egymástól elkülönülten működhetnek (ezt már az overlay technika is kihasználta),

  • a programok az összetartozó részek címtartományát is időben egyenetlenül használják, azaz az időben egymáshoz közeli utasítások és adatok általában a térben is egymáshoz közel helyezkednek el (lokalitás).

A korábbi vizsgálatokból az is világossá vált, hogy nem is célszerű, hogy a programok teljes logikai memóriaterülete a központi tárban legyen, hiszen

  • ekkor a futtatható programok méretét nem korlátozza a központi memória nagysága, azaz a ténylegesen meglevő tárterületnél nagyobb tárigényű (hosszabb) programokat is futtathatunk,

  • az egyes folyamatok tárigényének csökkenésével a memóriában tartott folyamatok száma növelhető, azaz növelhető a multi­programo­zás foka, és ezzel javítható a CPU-kihasználtság és átbocsátóképesség anélkül, hogy a körülfordulási idő, vagy a válaszidő növekednék,

  • a programok betöltéséhez, illetve a folyamatok háttértárba mentéséhez kevesebb perifériás műveletre van szükség, azaz a betöltés/kivitel gyorsabb lesz.

Jól látható tehát, hogy mind a rendszer, mind pedig a felhasználó szempontjából előnyös, ha a folyamatok tárterületének csak egy részét tartjuk egyidejűleg a memóriában.

Amikor egy folyamat érvénytelen – azaz nem a valós memóriában levő – címre hivatkozik, a címképző hardver hibamegszakítást okoz, amelyet az operációs rendszer kezel, és behozza a háttértárról a szükséges blokkot. Ennek logikai lépései a következők:

  • Az operációs rendszer megszakítást kiszolgáló programrésze kapja meg a vezérlést, amely

    • elmenti a folyamat környezetét,

    • elágazik a megfelelő kiszolgáló rutinra,

    • eldönti, hogy a megszakítást programhiba (például kicímzés) vagy logikailag érvényes, de nem betöltött blokkra való hivatkozás okozta-e.

  • Ez utóbbi esetben

  • Az operációs rendszer behozza a kívánt blokkot a központi tárba:

    • a blokknak helyet keres a tárban; ha nincs szabad terület, fel kell sza­badítania egy megfelelő méretű címtartományt, ennek tartalmát esetleg a háttértárba mentve,

    • beolvassa a kívánt blokkot.

  • Az operációs rendszer átadja a vezérlést a folyamatnak, amely ismételten végrehajtja, vagy folytatja a megszakított utasítást.

A blokk behozatala természetesen nem a folyamat aktív várakozása mellett történik. A perifériás művelet(ek) miatt a blokk behozatal sok időt vesz igénybe (meg kell várni, amíg a perifériás eszköz felszabadul, ki kell várni az átvitelt előkészítő műveleteket, valamint át kell vinni egy blokkot a periféria és a tár között), ezért a központi egység jobb kihasználása érdekében a blokkhiba miatt megszakított folyamatot az operációs rendszer várakozó állapotba helyezi, és más, futásra kész folyamatot indít el. Amikor a kívánt tartomány bekerül a tárba (azaz a folyamat várakozási feltétele bekövetkezik), az igénylő folyamat futásra kész állapotú lesz, és átkerül a futásra kész sorba, ahol megvárja, amíg az ütemező újra elindítja. A folyamatot a 3.19. ábra szemlélteti.

3.19. ábra. ábra - Laphiba kezelésének folyamata

Laphiba kezelésének folyamata


A virtuális tárkezelés megvalósítása teljesen új feladatok elé állítja az operációs rendszert, amelynek megoldásához megfelelő hardver támogatás szükséges. Legelőször is biztosítani kell, hogy az érvénytelen címre való hivatkozás megszakítást okozzon. Ezenfelül a megszakított utasítások újraindíthatók, vagy folytathatók kell hogy legyenek. A folytathatóság megoldása ritkább, mert utasítások végrehajtása közben fennálló állapotot kellene elmenteni, ami meglehetősen bonyolulttá tenné a processzorokat. Az újraindíthatóság megoldása, bár első pillanatra talán triviálisnak tűnik, bizonyos típusú utasításoknál – például többcímű, blokkmozgató, autoinkremens, illetve autodekremens indirekt című utasítások – ugyancsak nem egyszerű feladat.

A virtuális tárkezelést az IBM/360 számítógépcsalád megjelenésével kezdték elterjedten alkalmazni, és elmondhatjuk, hogy ma már a fejlettebb mikroprocesszorok mindegyike használ valamilyen fajta virtuális tárkezelést. A korszerű hardverek szinte kivétel nélkül lap- vagy kombinált szervezésűek, ezért a virtuális tárkezelés is csaknem mindig lapok mozgatásán alapul, így a továbbiakban mi is lapszervezésű rendszerekkel foglalkozunk.

A virtuális tárkezelés lapcsere algoritmusait egyéb, a blokkokhoz tartozó – később részletesen tárgyalt – bitek is támogatják.

A különböző rendszerek minősítését alapvetően befolyásolja a működési sebességük. A folyamatok futásának sebességét pedig döntően a tárhoz férés effektív ideje határozza meg. Ez virtuális tárkezelés esetén a megfelelő előfordulási valószínűséggel súlyozott memória hozzáférés, illetve (laphiba esetén) lapbehozatali időből számítható. Ha p jelöli a laphiba előfordulás valószínűségét, akkor

Effektív hozzáférési idő = (1-p) * Memória hozzáférési idő + p * Laphiba idő.

A laphiba kiszolgálási ideje több, mint öt nagyságrenddel is nagyobb lehet a valós memória hozzáférési időnél (a lemezműveletek időigénye a mai rendszerekben is 10 msec körül van), ezért p-nek nagyon kicsinek (10-6–10-8) kell lennie ahhoz, hogy a folyamatok futása ne lassuljon le túlságosan.

A virtuális tárkezelés tárgyalásánál három alapvető kérdést kell megválaszolnunk:

  • Melyik lapot hozzuk be a tárba (betöltendő lap kiválasztása)?

  • Ha nincs szabad hely a memóriában, akkor melyik lapot cseréljük le (lapcsere, replacement strategy)?

  • Hogyan gazdálkodjunk a fizikai tárral, azaz melyik folyamat számára hány lapot biztosítsunk?

A továbbiakban e három kérdést vizsgáljuk meg kicsit részletesebben.

3.4.2.2. Betöltendő lap kiválasztása (fetch-strategy)

Alapvetően két stratégiát követhetünk.

Igény szerinti lapozás (demand paging) esetén csak a laphibánál hivatkozott lapot hozzuk be a tárba. A módszer előnye, hogy a betöltendő lap kiválasztása nagyon egyszerű, továbbá, hogy csak a biztosan szükséges lapok kerülnek be a tárba. Ugyanakkor az új lapokra való hivatkozás mindig laphibát okoz, ami lassítja a működést.

Előretekintő lapozásnál (anticipatory paging) ezzel szemben az operációs rendszer megpróbálja „kitalálni”, hogy a folyamatnak a közeljövőben mely lapokra lesz szüksége, és azokat szabad idejében – amikor a lapcseréhez használt háttértár szabad – betölti.

Ha a jóslás helyes volt, akkor az előre behozott lapok miatt jelentősen lecsökken a laphibák száma, és ezzel a folyamat futási sebessége nagyban felgyorsul. Ha a döntés hibás volt, akkor felesleges lapok foglalják el a tárat.

Mivel manapság a központi tár ára drasztikusan csökken és ezzel párhuzamosan mérete egyre nő, ezért az előretekintő lapozás egyre népszerűbb, hiszen a hibás döntés – azaz a felesleges tárfoglalás – „ára” egyre kisebb.

3.4.2.3. Lapcsere stratégia (replacement strategy)

Lapcsere esetén ki kell választani azt a lapot, amelyiket feláldozzuk az új lap betöltése érdekében. A lapcsere stratégiák alapvető célja az, hogy az optimális esetet közelítsék, azaz azt a lapot válasszák áldozatul, amelyikre a legkésőbb lesz szükség (vagy másképp fogalmazva legtovább nem lesz szükség).

A lapcsere általános esetben két lépésből áll: az áldozat kimentéséből és az új lap betöltéséből. Az algoritmusok hatékonyságát nagyban fokozhatja, ha a mentést – vagyis háttértárra írást – csak akkor végzik el, ha szükséges, vagyis ha a lap tartalma a betöltés óta módosult. Annak nyilvántartása, hogy egy lapra betöltése óta írtak-e, csak hardver támogatással valósítható meg hatékonyan. A támogatás lényege, hogy minden fizikai laphoz tartozik egy jelzőbit – a módosított bit (modified bit, dirty bit, M bit). Ezt a bitet a lap betöltésekor az operációs rendszer törli, a tárkezelő hardver pedig minden, a lapra író memóriaművelet végrehajtásakor beállítja. A bit a laptáblában is elhelyezhető.

Bizonyos algoritmusok igénylik a lapra történő hivatkozások figyelését is, ami ugyancsak hardver támogatással hatékony. A laptáblában erre a célra is fenntarthatunk egy bitet. Ezt a hivatkozott bitet (referenced bit, used bit, R bit) a címképző hardver állítja be minden esetben, amikor az adott lapon belüli címre történik hivatkozás. A bitet az operációs rendszer törli adott időnként, vagy eseményhez (például laphiba) kötötten.

Optimális (OPT: Optimal) algoritmus

Az algoritmus előrenéz és a lapok következő használatának idejét veszi figyelembe. Ennél az algoritmusnál a legkevesebb a laphibák száma. Sajnos azonban a megvalósítása nehézségekbe ütközik, mivel jövőbeni laphivatkozásokra vonatkozó információt igényel (a helyzet az SJF ütemező algoritmushoz hasonló). Az egzakt végrehajtás gyakorlatilag megoldhatatlan, a kódok valamiféle előreolvasását és szimulált végrehajtását igényelné az adatfüggő elágazások figyelembevételével, ami csaknem olyan bonyolult lenne, mint a program valódi végrehajtása. Így csak közelítő megoldásokkal találkozunk. Az optimális algoritmus szerepe pedig az, hogy összehasonlítási alapként szolgáljon egy-egy eset utólagos értékelésekor, amiből következtetéseket vonhatunk le arra nézve, hogy az alkalmazott algoritmus mennyire közelítette meg az optimumot.

Legrégebbi lap (FIFO) algoritmus

A FIFO-algoritmus úgy próbálja közelíteni az optimálist, hogy hátranéz és a behozatal idejét figyeli. Az algoritmus azt a lapot cseréli le, amelyik legrégebb óta a tárban van. Megvalósítása egy egyszerű FIFO-listával történhet. Hibája azonban, hogy azokat a lapokat is lecseréli, amelyeket a folyamatok gyakran használnak.

Ennél az algoritmusnál felléphet egy érdekes jelenség, amelyet Bélády-anomáliának hívunk. Eszerint – várakozásainkkal ellentétben – bizonyos esetekben, ha növeljük a folyamathoz tartozó fizikai memóriakeretek számát, akkor nem csökken, hanem éppen növekszik a laphiba gyakoriság. A 3.20. ábra mutat példát erre.

3.20. ábra. ábra - Bélády-anomália

Bélády-anomália


Újabb esély (SC: Second Chance) algoritmus

Az újabb esély algoritmus a FIFO olyan változatát valósítja meg, amely a sor elején levő lapot csak akkor cseréli le, ha nem hivatkoztak rá. Vagyis hátranéz és a használat tényét figyeli. Ha hivatkoztak a lapra, akkor a hivatkozott bitet törli és a lapot visszateszi a FIFO-lista végére, vagyis a lap kap egy újabb esélyt. Ezzel kiküszöböli a FIFO-algoritmus hibáját és a gyakran használt lapokat nem cseréli le. A hivatkozott bit tehát ebben a megoldásban azt jelzi, hogy a lapra történt-e hivatkozás azóta, mióta az operációs rendszer legutóbb megvizsgálta, mint lehetséges áldozatot.

Óra (Clock) algoritmus

Az óra algoritmus csak megvalósításában különbözik az újabb esély algoritmustól. A tárban levő lapok egy körkörös listára vannak felfűzve a betöltés sorrendjében, és egy mutató mutat a legrégebbi lapra. Lapcserénél a kijelölt lap kivitele előtt az algoritmus megvizsgálja az R bitet. Amennyiben egynek találja, úgy nem viszi ki ezt a lapot, hanem törli az R bitet, és a mu­tató eggyel előbbre lép. A lépések addig ismétlődnek, amíg az algoritmus egy kivihető lapot nem talál (azaz amelynél R=0).

Legrégebben nem használt (LRU: Least Recently Used) algoritmus

Az LRU-algoritmus azt a lapot választja áldozatul, amelyre a folyamatok leghosszabb ideje nem hivatkoztak. Ez az algoritmus közelíti legjobban az optimálist, mivel ugyan hátrafele néz, viszont a használat idejét veszi figyelembe (azaz a közelmúltból következtet a közeljövőre, ami a lokalitás miatt jó becslést adhat).

Ennél a jó teljesítménye miatt gyakran használni kívánt algoritmusnál gondot okoz, hogy „drága”. A használat ideje alapján történő sorbarendezés külön hardvertámogatást igényel, és az algoritmus futási ideje is magasabb az egyszerű algoritmusokénál. A megvalósításra több változatot is kidolgoztak.

  • Számlálóval. A lapra történő minden hivatkozásnál feljegyezzük annak időpontját (egy logikai óra, vagy számláló állását). Lapcserénél a tárolt időpontok közül a legrégebbit keresi ki az algoritmus. Ez a megvalósítás a lapkiválasztási időt is megnövelheti, hiszen a legkisebb idő megkeresése mellett minden memória hivatkozásnál egy extra memória írási ciklust jelenthet (az időpont tárolása).

  • Láncolt listával. A memóriában tárolt lapok egy láncolt listában vannak felfűzve, az újonnan behozott lapok a lista végére kerülnek, az algoritmus a lista elején álló lapot választja ki. Címhivatkozásnál a címzett lapot kivesszük a listából és a végére illesztjük.

  • Kétdimenziós tömbbel. Ennél a megvalósításnál a hardver egy n*n-es (n a lapok számát mutatja) mátrixot használ (inicializáláskor a mátrix a 0 mátrixszal egyezik meg). Az i. lapra történő hivatkozásnál a mátrix i. sorának minden bitjét egyre, majd az i. oszlop minden elemét nullára állítja. A legkisebb bináris értékű sor az LRU-laphoz tartozik.

A bonyolult megvalósítás miatt az LRU-algoritmus helyett sokszor annak – hardvertámogatást nem, vagy alig igénylő – közelítését szokták használni:

Legkevésbé használt (LFU: Least Frequently Used vagy NFU: Not Frequently Used) algoritmus

Ennél az algoritmusnál abból indulhatunk ki, hogy a közelmúltban gyakran használt lapokat a folyamatok a közeljövőben is használni fogják még, és ugyanígy, a közelmúltban ritkán, vagy nem használt lapokra a közeljövőben nem lesz szükség. Ilyenkor az operációs rendszer rendszeres időközönként végignézi a memóriában levő lapokat, és a hozzájuk rendelt számlálóhoz hozzáadja az R bit (0 vagy 1) értékét, és egyben törli az R biteket. Az algoritmus a legkisebb számláló értékkel rendelkező – vagyis a legritkábban használt – lapot választja ki kivitelre.

Hátrányt jelent, hogy az algoritmus „nem felejt”, vagyis az egykor gyakran használt lapok még sokáig a memóriában maradnak akkor is, ha már biztosan nem lesz rájuk hivatkozás (például többmenetes fordításnál az egyes menetekhez tarozó lapok). A problémán öregítéssel segíthetünk, például úgy, hogy az R bitet a legnagyobb helyiértékű bit helyére másoljuk, de előtte a számlálót jobbra léptetve csökkentjük a régebbi hivatkozások súlyát.

A módszer másik problémája, hogy a frissen betöltött (és így biztosan kis számláló értékű) lapokat is könnyen kiteheti újra a háttértárra. Ezért általában a frissen behozott lapokat az első használatig befagyasztjuk (page locking) a tárba.

Utóbbi időben nem használt (NRU: Not Recently Used) algoritmus

Az utolsó algoritmus, amelyet megemlítünk, az R (hivatkozott) és M (módosított) bitek használatán alapszik. A hivatkozottság egy idő elteltével elveszti a jelentőségét, ezért az operációs rendszer rendszeres időközönként törli az R bitet. Ugyanakkor az M bit értékét őrizni kell, hiszen törlése információ veszteséghez vezetne.

A két bit értéke alapján az algoritmus a lapokat négy csoportba osztja, és lapkivitelnél hátranézve és a használat idejét és módját is figyelembe véve, a lehető legkisebb prioritású csoportból választ véletlenszerűen.

Prioritás R bit M bit Megjegyzés

0 0 0 Nem hivatkozott, nem módosított

1 0 1 Nem hivatkozott, módosított

2 1 0 Hivatkozott, nem módosított

3 1 1 Hivatkozott, módosított

Az algoritmusok működhetnek úgy, hogy szükség esetén mindig a folyamat saját munkaterületén belül választanak ki lapot kivitelre – ilyenkor lokális lapcsere algoritmusról beszélünk, vagy pedig az egész memórián belül keresnek – globális lapcsere algoritmus esetén. Ez utóbbi stratégia sokkal alkalmasabb a terhelésingadozások kiegyenlítésére, azonban könnyen előfordulhat, hogy a „burjánzó” (sokfele hivatkozó) folyamatok kiszorítják a „kicsiket”.

Bármelyik algoritmus használata esetén gyorsíthatjuk a lapcserét, és az eszközök egyenletesebb terhelését érhetjük el, ha egy periodikusan felébresztett háttérfolyamat, a paging daemon a háttértár szabad idejében (henyélésekor) a módosított lapokat kimásolja, így ezek esetleges későbbi lecserélésekor azokat nagy valószínűséggel már nem kell újra kiírni.

Fenntarthatunk egy előrehozott, kisebb CPU-terhelés idején futtatott áldozatválasztással kialakított listát, amelyikről azonnal leemelhetünk egy lapot, ha cserére van szükség. Ha a listán lévő lapok száma csökken, újabb előzetes áldozatokat választhatunk. Fokozza a hatékonyságot, ha a paging daemon a szabad listára tett módosított lapokat írja ki először, illetve a listára eleve a kimentést követően kerülnek fel a lapok. Előfordulhat az is, hogy a szabad listára került lapok felülírása előtt újabb hivatkozás történik rájuk. Ezek a hivatkozások még megtalálják a lapokat, ilyenkor természetesen nem kell azokat újra behozni, csupán lekerülnek a szabad listáról.

3.4.2.4. Gazdálkodás a fizikai tárral

A folyamatok lapigénye

A fizikai tárgazdálkodás legalapvetőbb kérdése, hogy hány lapot adjunk az egyes folyamatoknak. A folyamatok szempontjából nézve az a jó, ha minél több lapjuk van a tárban, hiszen nagy valószínűséggel annál kevesebb laphibát okoznak. Túl kevés lap esetén állandóan laphiba lép fel. Ha a rendszerben átlagosan nem tud befejeződni egy laphiba kiszolgálása, mielőtt egy újabb laphiba fellép, a folyamatok felgyűlnek a mágneslemez várakozási sorában, és a CPU-nak nem lesz futtatható folyamata, CPU-tétlenség alakul ki. A rendszer teljesítménye leromlik. (Fennáll annak a veszélye is, hogy a hosszú távú ütemező ezt a B/K-intenzív folyamatok túlsúlyaként értékeli, és újabb folyamatokat enged be, ami természetesen tovább rontja a helyzetet.) A gyakori laphibák által okozott teljesítménycsökkenést vergődésnek (thrashing) nevezzük. A jelenséget jól szemlélteti a 3.21. ábra, amelyik a multiprogramozás fokának és a CPU-kihasználásnak az összefüggését mutatja virtuális tárkezelést alkalmazó rendszerek esetére.

3.21. ábra. ábra - A multiprogramozás hatása a CPU-kihasználtságra

A multiprogramozás hatása a CPU-kihasználtságra


A rendszer szempontjából nézve, ha egy folyamatnak sok lapot adunk, azt jelenti, hogy kevesebb folyamatot tudunk a tárban tartani, így alacsonyabb lesz a multiprogramozás foka és ezzel várhatóan a CPU-kihasználtság is. A görbe kezdeti szakaszán kevés folyamat van a rendszerben. Minél kevesebben vannak, annál nagyobb annak a valószínűsége, hogy mindegyikük várakozik, a CPU pedig tétlen. A folyamatok számának a növekedésével a CPU-kihasználás aszimptotikusan közelít az adminisztrációs (például környezetváltási) veszteségekkel csökkentett 100%-os maximumhoz. A folyamatok számának további növekedésekor azonban – mivel az egy folyamatra jutó tárterület csökken – belép a tárkezelés hatása és kialakul a vergődés, a CPU-kihasználás pedig a folyamatok számának további növelésével meredeken leesik. El kell kerülni, hogy a rendszerben ilyen üzemállapot alakulhasson ki, azonban az optimumot lehetőleg meg szeretnénk közelíteni. Fontos tehát, hogy meg tudjuk becsülni, milyen laphiba gyakoriság (PFF: Page Fault Frequency) mellett marad még a rendszer egyensúlyban.

Könnyen beláthatjuk, hogy a rendszer egészét tekintve a CPU akkor nem válik tétlenné, ha átlagosan egy laphiba kezelése közben nem következik be újabb laphiba (ha meggondoljuk, ugyanerre a következtetésre jutottunk az effektív memóriahozzáférési idő kiszámítása kapcsán).

A teljes rendszerre vonatkozó egyensúlyi feltételt vonatkoztathatjuk az egyes folyamatokra is, azaz előírhatjuk, hogy két laphiba közötti átlagos futási idejük haladja meg a laphiba átlagos kiszolgálási idejét. Ha ez minden folyamatra teljesül, akkor az egész rendszer is egyensúlyban lesz.

Visszatérve az eredeti kérdésre, célszerű tehát egy folyamatnak annyi lapot adni, amennyi szükséges az egyensúlyhoz, azaz ahány lapra hivatkozik a laphiba kiszolgálás átlagos ideje alatt (ugyanakkor nem sokkal többet, mert akkor leromlik a multiprogramozás foka). Ezt az értéket a munkahalmaz méretének (working-set size) nevezzük.

Munkahalmaz

Munkahalmaznak (working set, bizonyos irodalmakban működő lapkészlet) nevezzük egy folyamat azon lapjainak a halmazát, amelyre egy adott időintervallumban (munkahalmaz-ablak) – a hossza célszerűen a laphiba kiszolgálási idővel egyezik meg – hivatkozik. A munkahalmaz dinamikus fogalom, tehát időben változik, ami nemcsak a munkahalmazba tartozó lapok, hanem a munkahalmaz méretének a változását is jelenti az időtengely mentén. Pontos mérése, nyilvántartása igen nehézkes, ezért az esetek többségében csak becslésekre hagyatkozunk.

Lokalitás

A munkahalmaz becslésében nagy szerep jut a lokalitásnak (locality). A folyamatok statisztikailag megfigyelhető tulajdonsága, hogy egy időintervallumban a címtartományuknak csak egy szűk részét használják. Időbeni lokalitás alatt azt értjük, hogy egy hivatkozott címet a folyamat a közeljövőben várhatóan újra használni fog, míg a térbeli lokalitás fogalma azt takarja, hogy az időben egymáshoz közelálló hivatkozások nagy valószínűséggel egymáshoz közeli címekre történnek.

A munkahalmaz becslése során tehát kiindulhatunk abból, hogy a közelmúltra vonatkozó munkahalmaz nem fog lényegesen eltérni a közeljövőben szükséges munkahalmaztól (a korábban tárgyalt lapcsere stratégiák is mind ezen a felismerésen alapulnak). Ez nem jelenti azt, hogy a folyamatok munkahalmazának mérete egyes futási szakaszokban ne változhatna meg jelentősen.

A lokalitás hatással van arra is, hogy hogyan alakul a laphiba gyakoriság a folyamat teljes címtartományából a memóriába töltött hányad függvényében. A laphibák aránya nem lineáris függvénye lesz a memóriába töltött címtartomány arányának (mint ahogy véletlen hivatkozás esetén fennállna), hanem ennél kisebb értékeket kapunk (3.22. ábra).

3.22. ábra. ábra - A lokalitás hatása a laphiba gyakoriságra

A lokalitás hatása a laphiba gyakoriságra


Dinamikus lokális tárgazdálkodás

Az optimális rendszerműködéshez tehát el kell kerülni a vergődést, és törekedni kell arra, hogy a folyamatoknak a lokalitás alapján meghatározott mun­ka­halmaza futás közben a központi memóriában legyen. A folyamatokat úgy érdemes elindítani vagy felfüggesztés után újraindítani, hogy egyszerre több lapjukat – a várható munkahalmazt – behozzuk a tárba (másképp induláskor túl gyakori lenne a laphiba). (Előrelapozás, prepaging)

Az optimális (legmagasabb fokú) multiprogramozás eléréséhez a legtöbb rendszer lokális lapcsere algoritmust alkalmaz. Ugyanakkor a munkahalmaz tárban tartását – a laphiba gyakoriság mérésén alapuló – a folyamatokhoz tartozó memóriaterület méretének dinamikus változtatásával biztosítja.

A globális lapgazdálkodás (globális lapcsere algoritmusok) kedvezőtlen kölcsönhatást okozhatnának egymástól egyébként független folyamatok között. A statikus lokális tárgazdálkodás ezt megakadályozza, de nem tud alkalmazkodni a folyamatok futás közben változó lapigényéhez. A jó kompromisszumot dinamikus lokális gazdálkodás jelentheti, amelyik alkalmazkodni képes a folyamatok aktuális lapigényéhez.

A folyamatok aktuális lapigényének meghatározására az egyik megoldás a munkahalmaz (illetve méretének) mérése, azonban, mint korábban említettük, ez túl körülményes lenne. Ehelyett inkább a folyamatok laphiba gya­ko­riságát, illetve az ezzel egyenértékű laphibák között eltelt időt (interfault time) mérik, ami sokkal könnyebben megoldható.

Ha a laphiba gyakoriság meghalad egy felső határértéket, akkor az operációs rendszer a folyamathoz újabb lapot rendel, vagy pedig – amennyiben nincs több hozzárendelhető szabad memóriakeret, vagy memóriabővében lévő folyamat – a mul­ti­programozás fokának csökkentése mellett dönt, és felfüggeszti valamelyik folyamatot. Ha pedig a laphiba-gyakoriság alatta marad az alsó határértéknek, akkor elvesz a folyamattól egy lapot (3.23. ábra). Új folyamatot pedig csak akkor lehet elindítani, ha van „elegendő” szabad memóriakeret a számára.

3.23. ábra. ábra - Rendszeregyensúly biztosítása a laphiba-gyakoriság mérése alapján

Rendszeregyensúly biztosítása a laphiba-gyakoriság mérése alapján


3.4.2.5. Egyéb tényezők

Lapméret

A rendszer működésére közvetlen hatással van a lapok mérete is. Ezt általában a hardver köti meg, így az itt következőket inkább hardver, mint szoftver rendszerfejlesztők mérlegelik.

Nagyobb lapméretek alkalmazása esetén figyelembe kell venni, hogy kevesebb lappal, így kisebb laptáblával számolhatunk, a perifériás átvitel fajlagos ideje csökken (az átvitel idejének nagyobb részét az előkészítési idő teszi ki), a folyamatok munkahalmazának mérete nő, ugyanakkor nagyobb lesz a belső tördelődés.

Kisebb lapoknál éppen ellenkezőleg, jobban érvényesül a lokalitás (kisebb lesz a munkahalmaz), kisebb lesz a belső tördelődés, viszont a perifériás átvitel fajlagos ideje és a laptáblák mérete is megnő.

Lapok tárba fagyasztása

Az LFU lapcsere algoritmusnál már említettük a lapok tárba fagyasztásának lehetőségét. Erre kifejezetten szükség is van bizonyos esetekben. Például, elindított perifériás műveleteknél az átvitel befejeződéséig a kijelölt címtartományt a tárban kell tartani.

Program struktúra

A virtuális tárkezelés átlátszó, azaz működése el van rejtve a felhasználó elől. Ha azonban a tárkezelés működését és sajátságait – elsősorban a lo­ka­li­tás hatását – mérnöki szemmel vizsgáljuk, jól látható, hogy maga a programozó is sokat tehet a programok gyorsabb lefutásáért, a rendszer jó teljesítményéért. Csak néhányat említünk a jól alkalmazható „trükkök” közül.

Programíráskor

  • többdimenziós tömböket célszerű a tárbeli elhelyezkedésüknek megfelelően bejárni (például keresésnél),

  • a programokban célszerű kerülni a nagy ugrásokat,

  • az egyszerre használt változókat, az egymást hívó eljárásokat célszerű egymás mellé helyezni.

Fordításkor

  • az eljárásokat célszerű egymás mellé helyezni,

  • a kód- és adatterületeket célszerű szétválasztani (a kódterület nem vál­tozik, így lapcserénél nem kell kimenteni).

3.4.3. Fájlrendszerek

A klasszikus operációs rendszerek felhasználók által leginkább használt absztrakciója a fájl, állomány. Fájlnak a felhasználó, vagy a rendszer szempontjából összetartozó információk perzisztens, a létrehozó programot „túlélő” gyűjteményét nevezzük. A fájlokat a rendszer többnyire valamilyen hát­tér­táron tárolja, amely tartalmát megőrzi még akkor is, amikor a rendszer áramellátását kikapcsolták. Leggyakoribb a közvetlen hozzáférésű perifériás eszközök, mint például a mágneslemez használata, de főleg korábbi rendszerekben fel-feltűntek soros hozzáférésű tárolóeszközök is. Ma ezek az eszközök elsősorban a biztonsági másolatok és a nagyméretű, off-line adatraktárak tárolóiként használatosak.

Egy operációs rendszer általában nagy számú fájlt tárol, kezel. Ezeket egymástól meg kell különböztetni, el kell különíteni. Az egyes állományokat tipikusan egy hozzájuk rendelt név azonosítja, a nagy számú fájlt könnyebb kezelhetőség érdekében könyvtárakba csoportosítják. Az állományok az operációs rendszer felhasználói számára közös, logikai erőforráshalmazt képeznek, az ebből fakadó erőforrás-gazdálkodási feladatok, mint például a hozzáférések ütemezése, koordinálása, szabályozása, korlátozása is a fájlkezelő rendszerek feladata.

A fájlabsztrakció a rendszer használója, programozója számára kényelmes hozzáférést biztosít a fájl tartalmához, elrejtve a tárolás és kezelés konkrét részleteit. A fájlkezelő rendszer tipikusan a következő magas szintű feladatokat valósítja meg:

  • hozzáférést biztosít az állomány részeihez, megvalósítja az állományok tartalmának átvitelét a háttértár és a központi tár, illetve a hát­tértár és egyéb perifériák – például nyomtató – között,

  • műveleteket biztosít az egyes fájlokon, illetve a fájlokat összefoglaló könyvtárakon,

  • osztott hozzáférések esetén koordinálja, időzíti az egyes folyamatok fájlhasználatát,

  • szabályozza a felhasználóknak, vagy azok programjainak a fájlokhoz hoz­záférést, különválasztva kezeli az egyes felhasználók állományait és könyvtárait, megakadályozza, hogy a fájlokon illetéktelen felhasználók műveleteket végezhessenek, esetlegesen védi a fájlokban tárolt információkat az illetéktelen olvasások ellen, kódolva, titkosítva annak tartalmát,

  • gyakori a fájlokban tárolt információk sérülése, hardver- vagy kezelési hiba miatt bekövetkező elvesztése elleni védelem, a fájlok időszakonkénti megbízhatóbb háttértárra mentése is.

A fájlok kezelését különböző, a konkrét hardvertől egyre távolodó, a logikai szervezéshez egyre közeledő, egymásra épülő programrétegek valósítják meg.

A perifériás eszközhöz legközelebb az ún. készülékkezelő programok (device driver, meghajtó) állnak, amelyek közvetlenül a berendezéseket vezérlik. Ezen réteg feladata az adatok központi tár és a periféria közötti átvitelének kezdeményezése, vezérlése, lebonyolítása. A jelenlegi hardverrendszerekben tipikusan megszakításosan vezérelt perifériák megszakításai is ide futnak be.

A meghajtókra épül az elemi átviteli műveletek lebonyolítására szolgáló réteg. Itt történik meg a fájlok tartalmának a periféria által használt címzési rendszerre való leképzése, a periféria által megkövetelt, avagy csak a rendszer teljesítményét javító, az átvitelek számát csökkentő blokkok képzése. Mivel a háttértár elérése még a korszerű, nagy sebességű mágneslemezes tárak esetén is több nagyságrenddel lassabb, mint a központi tár elérése, e réteg gyakori feladata gyorsító tárak (cache) képzése, a gyakran használt blokkok központi tárból történő újrafelhasználásának megvalósítása is. Egyidejű hozzáférés kérelmek esetén a réteg sorba állíthatja a kéréseket, optimalizálva a fizikai erőforrás kihasználását.

Az elemi átvitelekre épül az állományszervezés rétege, amely nyilvántartja a háttértár szabad és lefoglalt területeit, gondoskodik az egyes fájlokhoz tartozó blokkok logikai összefűzéséről, a dinamikus helygazdálkodásról. Ide tartozik új fájlok létrehozásakor, vagy a fájlokban tárolt információ bővülésekor további szabad helyek lefoglalása, illetve állományok törlésekor a korábban lefoglalt területek felszabadítása. Tipikusan ez a réteg biztosít eljárásokat a rendszer programozói számára az állomány tartalmának eléréséhez, módosításához.

A logikai állományszervezés rétege ismeri és kezeli a nyilvántartásokat, az állomány neve alapján megtalálja annak helyét. Ide tartozik az állományok felhasználónkénti hozzáférésének szabályozása, de gyakran a konkurens elérések időbeli ütemezése, szinkronizálása is e réteg feladata.

Vizsgáljuk meg részletesebben az egyes rétegek megvalósításánál használt adatszerkezeteket, algoritmusokat. A készülékkezelők és az elemi átviteli műveletek rétegével itt nem foglalkozunk, azt a készülékkezelésről szóló fe­je­zet részletezi. Az állományok tárolására közvetlen hozzáférésű lemezegységet tételezünk fel.

3.4.3.1. Az állományok tárolása a lemezen

Az operációs rendszer a lemezterületet a hardverhez hasonlóan nagyobb egységekben, blokkokban kezeli. Ez az adatmozgatás, lefoglalás, felszabadítás alapegysége, ennél kisebb területekkel az operációs rendszer nem foglalkozik (néhány kivételtől eltekintve). Egy logikai – operációs rendszer által képzett – blokk tipikusan 1 vagy néhány hardverblokkot – szektort – tartalmaz. A blokkok méretének meghatározását szervezési, tárolási és hatékonysági szempontok befolyásolják. Minél nagyobb blokkokat használunk, annál kevesebb az egységnyi információ átviteléhez szükséges többlet művelet, viszont a nagy blokkokat ki nem töltő információ miatt feleslegesen foglalunk mind a háttértárban, mind a központi tárban területet, jelentős belső tördelődési veszteség lép fel.

A blokkok méretét gyakorta meghatározza az adatszerkezetekben a blokkokat azonosító címek számára fenntartott hely mérete. Főleg kisebb, kezdetlegesebb rendszerekben a blokkok címzésére viszonylag kevés helyet, mondjuk 16 bitet tartottak fenn. Eleinte a 16 biten ábrázolható különböző értékek bőven elegendőnek bizonyultak az összes, a lemezen előforduló fizikai szektor egyenkénti megcímzésére. Azonban a lemezegységek kapacitásának ugrásszerű növekedésével ez a 16 bit hamarosan kevésnek bizonyult, fizikai szektorokat össze kellett vonni az operációs rendszer által egyben kezelt logikai blokkokká, hiszen ezek száma nem haladhatta meg a 64 K-t. Ezért aztán a logikai blokkok mérete egyre növekedett, így gyakran előfordulhatott, hogy egy tipikusan néhány száz bájtból álló szöveges fájl a lemezen több megabájtnyi területet kényszerült elfoglalni. A csapdából természetesen egyszerűnek tűnik a kiút, nagyobb címtartományt kell fenntartani a blokkok számára. Ám ez nem csak a blokkok adminisztrációja számára fenntartott területeket növeli, elvéve a helyet az „értékes” adatoktól, de a háttértárak rohamos fejlődésével a ma még bőségesen elegendőnek tűnő címtartomány 1-2 éven belül szűknek bizonyulhat. Az egyes rendszerváltozatok kompatibilitásának fenntartása is nehezíti a probléma megoldását, hiszen a rendszer belső adatszerkezeteit érintő módosításokat nem könnyű zökkenőmentesen lebonyolítani. Másik lehetőség a háttértár particionálása, a fizikai­lag nagy számú blokkot tartalmazó lemezegységek logikailag kisebb egységekre, ún. kötetekre „darabolása”, ám a szétszabdalt tárterület kezelése is problémákat okoz.

A fájlszervezés rétegének a lemez minden egyes blokkját nyilván kell tartania, tudni kell, mely blokkok tartoznak az egyes fájlokhoz, melyek az éppen szabad, fel nem használt blokkok. Ismernie kell a különböző alacsony (például szabad területek), illetve magas szintű (például könyvtárak) nyilvántartások tárolására fenntartott blokkokat is, és gazdálkodnia kell velük.

Alacsony szinten kétfajta adatszerkezetet különíthetünk el, a lemez szabad blokkjainak, illetve az egyes fájlokhoz tartozó blokkoknak a leírását. Mivel mind információtartalmában, mind kezelésében más jellegű nyilvántartással van dolgunk, e célokra más és más adatszerkezetek honosodtak meg.

A szabad blokkok nyilvántartására a különböző adatszerkezetek használatosak:

  • Bittérképes ábrázolás. A lemez mindegyik logikai blokkjához egy bit­ben tárolható, hogy szabad-e. Ezekből a bitekből képzett vektort a lemez kijelölt helyén tároljuk. A bitvektoros szervezés esetén egymás melletti szabad blokkok kiválasztása nagyon egyszerű, de a vektor kezelése csak akkor hatékony, ha a teljes vektort a központi tárban tudjuk tartani.

  • Láncolt listás ábrázolás. A szabad blokkokból „lecsípett” bájtokban egy másik szabad blokk sorszámát, címét tárolhatjuk. Így a szabad blokkokat mintegy láncra fűzzük, csak a lánc elejét kell „kézben tartani” – egy jól definiált helyen tárolni –, innen kiindulva az összes szabad blokk elérhető. Mivel a szabad blokkban értékes információ nincs, ezért a le­csípett bájtok nem okoznak problémát. Az ábrázolás viszont nem hatékony, a lista bejárása lassú, mert több lemezműveletet igényel.

  • Szabad helyek csoportjainak listája. A fenti ábrázolás teljesítménye könnyen javítható. Ahelyett, hogy minden egyes blokkból csak egyetlen címnyi területet csippentenénk le, kihasználhatjuk a teljes blokkot arra, hogy más szabad blokkok címét tároljuk. Mivel a szabad blokkok száma dinamikusan változhat, az egyik címet a fenti láncolt lista képzésére használjuk, ám a többi n-1 címnyi terület 1-1 szabad blokkot jelöl ki.

  • Egybefüggő szabad területek nyilvántartása. A szabad blokkok egyesével történő tárolása helyett egy táblázatban az egymás mellett lévő szabad blokkokról az első sorszámát és a terület hosszát tároljuk. A módszer akkor előnyös, ha a szabad területek átla­gos hossza (jóval) nagyobb egy­nél, valamint ha az allokálásnál egymás melletti szabad területeket akarunk kiválasztani. Ha a táblázat elemei a kezdő blokk szerint rendezettek, az egymás melletti szabad területek összevonása egyszerű.

Az egyes állományokhoz tartozó blokkok tárolására, lefoglalására a következő általános megoldások alakultak ki:

  • Folytonos terület lefoglalása. A fájlhoz tartozó információt egymás melletti szabad blokkokban tároljuk. A rend­szernek csupán az első blokk sorszámát, valamint a blokkok számát kell tárolni az állományt leíró adatok között.

A módszer legnagyobb hátránya, hogy az esetek nagy többségében nem tudjuk előre, hány blokkra lesz szük­ségünk, így valami­lyen algoritmussal a szükséges blokkok számát becsülni kell. Ha ez nem bizonyul elégnek és a lefoglalt blokkokat követő területet már használják, akkor a foglalást végző eljárás hibajelzést ad vissza, vagy megpróbál nagyobb sza­bad területet keresni, és oda a már felhasznált blokkok tartalmát is át­másolni. Itt is felléphet a külső tördelődés problémája, azaz az összefüggő területek lefoglalása és felszabadítása esetén a szabad területek kis, nehezen használható részekre tördelődnek. Különböző allokációs algoritmusokkal (első illeszkedő, legjobban illeszkedő, legrosszabbul illeszkedő kiválasztása) küzdhetünk a tördelődés ellen, illetve időszakonként tömörítést hajthatunk végre, ami azonban meglehetősen időigényes és körülményes eljárás, ezért viszonylag ritkán használatos. A fájlkezelésben az allokációs algoritmusok kombinált használata is előfordul. Amíg a lemezen nagy szabad területek vannak, általában teljesül a worst-fit allokáció mögött álló feltételezés, azaz a maradék használható más célra, legyen hát minél nagyobb. Amikor a lemez foglaltsága növekszik, ez a feltételezés egyre kevésbé teljesül, gyakorlatilag nincs jelentősége, melyik területet allokáljuk (first-fit, next-fit). További telítődéskor már használhatatlan hulladékok keletkeznek, amelyeket minimalizálni érdemes (best-fit). Ha mindemellett még a lefoglalandó terület méretét is figyelembe vesszük, és az átlagos szabad területhossz és a foglalás aránya szerint választunk algoritmust, viszonylag kedvező kihasználást érhetünk el.

A folytonos terület foglalásának előnye, hogy a tárolt információnak mind soros, mind közvetlen elérése egyszerű, gyors. Napjaink rendszerében ez a tárolási forma általában akkor használt, ha előre tudjuk a szükséges blokkok számát, illetve igény az összes blokk egyidejű, gyors tárba, illetve tárból való mozgatása. Tipikus eset a virtuális tárkezelés esetén a tárcsere (swapping) megvalósítása.

  • Láncolt tárolás. A szükséges blokkokat egyesével allokáljuk, minden blokkban fenntartva egy helyet a következő blokk sorszámának. Általában a rendszer az ál­lományleíróban az első és esetleg az utolsó blokk sorszámát tárolja.

A tárolási mód nagy előnye, hogy ez egy dinamikus adatszerkezet, az állomány mérete szükség szerint tetszőlegesen növekedhet, határt csak a szabad blokkok száma szab. A fenti módszer külső tördelődéstől is mentes, a szabad területeket nem kell tömöríteni.

Hátrány, hogy a láncolt tárolás csak a tárolt információ soros elérést támogatja, a közvetlen eléréshez a listát az elejéről végig kell járni.

Külön problémát jelent, hogy a lánc szervezéséhez szükséges címet a blokkok hasznos területéből kell lecsípni. Így egy-egy blokk központi tárba másolásakor ezeket a darabokat ki kell hagyni. Ezen a problémán segít a láncolt tárolás egy változata, ahol a láncokat az állományoktól elkülönülten, egy fájl allokációs táblában (FAT) tároljuk. A táblában a lemez minden blokkjához tartozik egy bejegyzés (pointer), amelyik – amennyiben a blokk fájlhoz tartozik –- a fájl következő blokkjára mutat. Az egyes állományokhoz csak a lánc első blokkjának sorszámát kell tárolni az állományleíróban, a következő blokkok a FAT-ból megtalálhatók. Ezt az allokációs táblát egyidejűleg a szabad blokkok tárolására is fel lehet használni. A tárolt információ közvetlen elérése is egyszerűbb, nem kell az egyes blokkokat végigjárni, elég e FAT-ban „lépkedni”. A FAT, vagy annak jelentős része a tárban tartható, így ez a keresés gyors. A sérülékenység ellen a FAT kettőzött tárolásával védekezhetünk. Ezt a megoldást alkalmazzák az MS-DOS rendszerek.

  • Indexelt tárolás. Az indexelt ábrázolás alapötlete, hogy az állományhoz tartozó blokkokat leíró címeket külön adatterületre, az indextáblába gyűjtjük. Az ál­lományleíróban az index­táblát tartalmazó blokk(ok) címét kell tárolni.

A módszer előnyei, hogy a közvetlen hozzáférés megvalósítása egyszerű, hiszen az indextábla segít­ségével minden blokk közvetlenül megtalálható. Lehetőség van „lyukas” állományok tárolására, azaz olyan állományokra, amelyek nem minden blokkja tartalmaz információt. Ebben az ábrázolási formában a nem használt területekhez nem kell lemezblokkot lefoglalni, azok helyét az indextáblában üresen hagyjuk.

Hátránya, hogy a blokkok címeinek tárolásához akkor is legalább egy teljes (index)blokkot kell lefoglalni, ha az állomány csak kevés blokkot tartalmaz. A tárolási mód pazarló. Mivel az indextábla mérete előre nem ismert, ezért meg kell oldani, hogy a táblázat is dinamikusan növekedhessen, például az indexblokkokat láncba fűzzük, hasonlóan a szabad helyek csoportjainak tárolásához, vagy többszintű indextáblákat használunk.

  • Kombinált módszerek. Egyes rendszerek az állomány hozzáférési módja, vagy mérete függvényében más és más módszert alkalmazhatnak. Például kis állományokat folytonosan, míg nagyokat indexelten tárolhatunk. Vagy soros hozzáférés igénye esetén láncolt, közvetlen hozzáférés esetén összefüggő blokkok tárolását választhatjuk.

Mind a szabad blokkok, mind az állományok tárolásának fent említett mód­sze­rei többé-kevésbé érzékenyek a lemezen tárolt nyilvántartások, adatszerkezetek sérülésére. Például egy láncolt blokkos szabad hely nyilvántartásnál egy blokk sérülése a lánc megszakadásához vezethet, ezzel a lánc végén álló blokkok elvesznek a rendszer számára. Még nagyobb problémát jelenthet az egyes állományokhoz tartozó blokkok leírásának elvesztése, megsérülése.

Ezt a problémát az operációs rendszerek általában redundáns adatszerkezetekkel igyekeznek enyhíteni. Például használhatunk kétirányú láncokat, ha a lánc mindkét vége még megvan, egy-egy blokk kiesését könnyen elviselhetjük, mindkét irányból elindulva megkeressük a „szakadást” és összefűzzük a láncot.

A redundáns adatszerkezetek árát a csökkenő értékes tárolási kapacitással és a lassabb kezelő algoritmusokkal fizetjük meg. Egy rendszer tervezőjének gondosan mérlegelnie kell tehát az egyes tényezőket, például azt hogy a perifériás eszköz várhatóan milyen arányú meghibásodásokat produkál, mekkora katasztrófát okoz számunkra egyes szabad blokkok, vagy az állományok blokkjainak elvesztése. A sérülések hatásai kiküszöbölésének egyszerű eszköze a háttértár tartalmának rendszeres, gyakori mentése.

A fájlkezelő rendszernek – vagy az erre szorosan épülő segédprogramoknak – tipikus feladata a különböző lemezen tárolt nyilvántartások konzisztenciájának ellenőrzése, az esetleges sérülések kijavítása. A javítás ügyesen meg­vá­lasztott adatszerkezetek esetén, bonyolult – nagy lemezegységek esetén lassú – ellenőrző algoritmusokat használva gyakran automatikusan történhet, ám néha a rendszergazda kézi beavatkozására is szükség lehet. Legrosszabb esetben a rendszergazdának egyes blokkok tartalmát „szemrevételeznie” kell, megtippelni, hogy vajon ez szabad blokk lehetett-e, vagy valamelyik – és főleg melyik – állományhoz tartozhatott. Ez a tevékenység szöveges információk esetén még úgy-ahogy sikerrel kecsegtet, de „bináris” állományok esetén nagyon nehezen használható.

3.4.3.2. A fájlok szerkezete

Míg a fentiekben az állományok háttértáron lévő fizikai szerkezetével fog­lalkoztunk, most a felhasználó szempontjait tükröző belső szerkezetét taglaljuk.

A fájl legáltalánosabb esetben összetartozó bitek sorozatának tekinthető. Napjaink hardver architektúrái tipikusan a bájtot tekintik a tárolás alapegységének, így a fájlokat is felfoghatjuk mint összetartozó bájtsorozatot. Ha ritkán is, de azért találkozhatunk a bájthatárokat nem „tisztelő” – változó bithosszúságú – információtárolási móddal is.

Az így tárolt bit- vagy bájtsorozathoz a felhasználó saját szempontjai szerint szerkezetet, jelentést rendelhet. Ilyenkor az alapegységet általában mezőnek nevezzük, amely rendeltetése szerint egy-egy adott típusú, kódolású adatot tartalmaz. Az összetartozó mezőket gyakran rekordokba foglalhatjuk. Mind az egyes mezők, mind a rekordok tárolás szerint lehetnek kötött, vagy változó hosszúságúak. Ez utóbbi esetben gondoskodni kell az egyes mezők, rekordok határainak felismerhetőségéről, például tárolva a mező hosszát, vagy speciális végjellel jelezve az adategység végét.

Az egyes operációs rendszerek a felhasználói adatszerkezethez különbözőképpen viszonyulhatnak. A leggyakoribb, általános célú fájlrendszerek nem veszik figyelembe a jelentés szerinti adatcsoportosítást, számukra a fájl „csak” egy bájt-, esetleg ritkán bitfolyam. A rendszer csak ennek a folyamnak a manipulálásához ad közvetlen eljárásokat (például olvasd a következő n bájtot). Az állományokat kezelő felhasználói programoknak kell a megkapott bájtokhoz jelentést rendelni, elkülöníteni az egyes információ-darabkákat.

Célrendszerekben, vagy univerzális, adatbáziskezelést is integráló általános célú rendszerekben (ilyeneket különösen IBM-rendszereken találhatunk) megtalálható viszont a felhasználói adatszerkezetet figyelembe vevő, azt támogató szervezés is, ahol például létjogosultsága van az olvasd a következő rekordot vagy következő mezőt eljárásnak. Persze itt külön gondot jelent az egyes adatszerkezetek „megismertetése” a kezelő eljárásaival, gyakori, hogy új adatszerkezet, tárolási mód stb. esetén a fájlrendszer adatkezelő eljárásait is bővíteni kell.

Megjegyzendő, hogy még azon rendszerekben is, amelyek a felhasználók fájljait szerkezet nélküli bájtsorozatnak tekintik, vannak a rendszer által ismert és kezelt szerkezetű állományok. Például a futtatható programok kódját tartalmazó fájlok általában rendszerenként különböző, de kötött, szigorúan definiált szerkezettel rendelkeznek. Bár az operációs rendszer fájlkezelő alrendszere nem ismeri ezek szerkezetét, de az erre épülő betöltő program annál inkább ismeri és használja. Ugyancsak találunk a rendszerekben minimális támogatást egyszerű szövegfájlok, illetve parancsfájlok kezelésére.

3.4.3.3. Könyvtárak

A könyvtár állományok – esetleg más könyvtárak – gyűjteménye, a könyvtár tartalmát a hozzá tar­tozó nyilvántartás (katalógus, directory) írja le. A könyvtár és nyilvántartás fogalma a szakirodalomban gyakran keveredik.

Az egyes nyilvántartások állományonként egy ún. nyilvántartás bejegyzést tárolnak. A bejegyzések tartalmazzák az egyes állományok attribútumait.

Az állomány legfontosabb attribútuma az azonosítására szolgáló név. Ennek a névnek könyvtáranként egyedinek kell lennie. Míg egyes rendszerek a nevet csak egy karaktersorozatnak tekintik, addig mások a nevet részekre osztják, például névre, típusra (ún. kiterjesztésre), esetleg verziószámra. Ezeket a rendszer külön kezeli, például hivatkozhatunk az adott könyvtár összes adott típusú fájljára, vagy például az egyes fájlok legutolsó, legfrissebb tárolt verziójára.

A nyilvántartás bejegyzés tartalmazhat az állomány fizikai elhelyezkedésére vonatkozó információkat, mint például a hosszát, a hozzá tartozó blokkok leírását, a lehetséges hozzáférés módját. Gyakoriak a logikai attribútumok is, például az állomány típusa (belső szerkezete szerint), tulajdonosa, különböző időpont adatok – létrehozásának, utolsó hozzáférésének, módosításának dátuma, esetleg érvényességének ideje –, felhasználónkénti, vagy felhasználó-csoportonkénti hozzáférés, engedélyezett műveletek.

A nyilvántartás bejegyzéseket tárolhatjuk a lemez speciális, elkülönített területén, de speciális, kötött szerkezetű fájlokban is. Néha előfordul kombinált tárolási forma, például kötet nyilvántartásba kerül a köteten lévő összes fájlt leíró nyilvántartás bejegyzés fizikai, esetleg logikai attribútumai, míg a neve, a könyvtárak szervezésének leírása külön tárolódik.

Az aktuálisan használatban lévő fájlokról az operációs rendszer nemcsak a háttértáron, de a központi tárban is tárol információkat. Ezek a fenti attribútumok – egy része – mellett a nyitott fájlok kezeléséhez szükséges egyéb állapotinformációt is tartalmazzák. Ilyen lehet például soros hozzáférés esetén az aktuális pozíció az állományban, vagy a megengedett műveletek listája, de osztott, konkurens kezelés esetén a szinkronizációhoz szükséges in­for­mációk (például lock) is ide kerülnek.

A fájlkezelő rendszerek gyakorta szerveznek hierarchiákat az egyes könyvtárakból. A korai rendszerek például kétszintű hierarchiát használtak, a má­so­dik szinten felhasználóként külön könyvtárba foglalva az egyes fájlokat. Napjainkban elterjedtek a szabadabb, flexibilisebb szerkezetek, például a faszerkezetű könyvtárak, ahol az egyes könyvtárak nemcsak fájlokat, hanem alárendelt könyvtárakat is tartalmazhatnak. Legáltalánosabb a gráfszerű könyvtárszerkezet. Mivel tipikus probléma lehet egy körrel rendelkező gráfban a tárolt elemek bejárása, kilistázása, ezért a rendszerek igyekeznek biztosítani a körmentes gráfszerkezetet, esetleg kivételt téve a rendszergazdával.

3.4.3.4. Műveletek

A fájlkezelés modellszinten is megjelenő alapműveletein túl a megvalósítás további részműveleteket igényel. A fájlok nyilvántartásának megoldása az egyes rendszerekben igen különböző lehet, így a könyvtárakra vonatkozó műveletek is jelentősen különbözhetnek.

Jellegzetes műveletek a könyvtárakon:

  • Fájl attribútumainak módosítása. Az állományhoz tartozó egyes logikai információk az állományban tárolt infor­mációk mó­dosítása nélkül is megváltoztathatók.

  • Új könyvtár létrehozása

  • Könyvtár törlése. Könyvtár törlésekor eldöntendő, hogy mi történjék a tartalmával. Például egy könyvtár csak akkor törölhető, ha üres, nincsenek benne állományok vagy könyvtárak. Esetleg a törlés törli az összes benne lévő állományt, esetleg rekurzívan törli az összes benne foglalt könyvtárat is.

  • Keresés. A könyvtárakon végzett egyik leggyakoribb művelet, hogy egy névhez meg kell találni a hozzá tar­tozó állományt. Keresni lehet a hierarchikus könyvtár szerkezetben, de végezetül a keresés mindig az egy könyvtárban tárolt állományok között történik. A keresés sebessége jelentősen befolyásolhatja a fájlkezelő rendszer teljesítményét. Ezért különböző adatszerkezetekkel igyekeznek a keresést felgyorsítani. A könyvtár hierarchiában történő keresést gyakran hashtáblákkal gyorsítják, míg a nyilvántartás bejegyzések közötti keresést például rendezéssel vagy hashtáblákkal lehet gyorsítani.

3.4.3.5. Osztott fájlkezelés

A fájl lehet olyan erőforrás, amelyet egyidejűleg több folya­mat is használni akar. Amennyiben ezek a folyamatok csak olvassák, tartalma nem mó­dosul, így az állomány osz­tottan is használható. Ha azonban legalább egy folyamat írja az állományt, akkor mint minden erőforrást, ezt is kölcsönös kizárással védeni kell. Kérdés, hogy a kölcsönös kizárást mennyi ideig kell fenntartani.

Az osztott fájlkezelést szabályozhatjuk a teljes fájlra. Ilyenkor az állományt először megnyitó folyamat definiálhatja, hogy a későbbi megnyitási kérelmekből mit engedélyezhetünk: például kizárólagos használatot kérünk, azaz több megnyitást nem engedélyezünk. Esetleg megengedhető, hogy a többi folyamat az állományt csak olvassa; legáltalánosabb esetben pedig egy vagy több folyamat is megnyithatja írási joggal.

Ha az állományt legalább egy folyamat írhatja, a fájlkezelő rendszernek definiálni kell, hogy az olvasó folyamatok az állomány változását mikor veszik észre: azonnal, vagy csak azután, hogy az író folyamat lezárta az állományt, addig a régi tartalmat látják.

Az egész állományra vonatkozó kölcsönös kizárás néha túlzottan, meg­en­ged­­hetetlenül óvatos, hiszen egyéb folyamatok az állományhoz csak lezárása után férhetnének hozzá.

Amelyik folyamat az állományban összetartozó információt akar elérni – írni vagy olvasni –, akkor ez(eke)t, mint önálló erőforrásokat lefoglalja – illetve várakozik, amíg fel­szabadul(nak) –, majd az átvitel lezajlása után a lefoglalt rekor­do(ka)t felszabadítja. Ter­mészetesen akár több egyidejűleg írási joggal ren­delkező folyamat is létezhet, a köl­csönös kizárás csak egyes kijelölt rekordokra vonatkozik. Az állomány mó­dosítását a többi folyamat a módosított rekordok fel­szabadítása után azonnal látja.

Sajnos a kölcsönös kizárás miatt itt is felléphet a holtpont vagy a kiéheztetés veszélye.

3.4.3.6. A hozzáférés szabályozása

Mivel az operációs rendszer általában több felhasználó állományait tárolja, kezeli, fel­vetődik az az igény, hogy jogosulatlan felhasználók ne férhessenek hozzá minden állomány tar­talmához, illetve ne végezhessenek rajtuk bizonyos műveleteket.

A hozzáférési jogokat az állomány létrehozója vagy az állomány felett speciális jo­gokkal ren­delkező felhasználó definiálhatja. Megjegyzés: az állo­mányokat folyamatok hozzák létre, a „létrehozó” vagy az a felhasználó, aki a folyamatot elindította, vagy a folyamathoz tartozik egy fix fel­használó. A hozzáférési jogok általában az egyedi fájlokhoz, esetleg egész könyvtárakhoz tartoznak. Néha azonos fájlokat több néven, több hozzáférési úton is elérhetünk, ilyenkor a jogosultságokat rendelhetjük mind a konkrét fájlhoz, mind az elérési útvonalhoz. A jogosultságok azt szabályozzák, hogy a rendszer egyes felhasználói milyen műveletek elvégzésére jogosultak. Amennyiben a rendszernek túl sok felhasználója van, célszerű a jogosultságokat felhasználói csoportokhoz rendelni.

Fájlokhoz rendelhető tipikus jogosultságok: írás, olvasás, hozzáírás, végrehajtás, törlés, míg könyvtárakra vonatkozóan megengedhető módosítás, törlés, listázás, keresés, új állomány létrehozása.