Már van valami elképzelésünk egy operációs rendszer felépítéséről, már tudjuk körvonalakban, hogy mi is az a folyamat, és a múltkori alkalommal tettünk egy kisebb túrát az alapvető multiprogramozási problémák témakörében. Mert ugyebár nem adhatjuk alább manapság - mindenféle többfeladatos rendszerekre vannak kiéhezve a felhasználók és az alkalmazások. Viszont arról még nem esett túl sok szó, hogy a programokat-folyamatokat hol tároljuk, és tárolásuk - illetve ezzel kapcsolatban a hatékony végrehajtásuk - mennyire fontos és hogyan hat lényegében az egész operációs rendszer összteljesítményére.

Memória mindenhol

Mióta számítógép a számítógép, azóta fellelhető benne az operatív tár, vagy másik nevén a központi memória. Minden tevékenység, minden művelet alapja valahol valamiféle memória használata - legyen az akár a processzor magjában, vagy egy háttértár vezérlő elektronikájára integrálva. Nyugodtan kijelenthetem, hogy ha valaki operációs rendszert akar készíteni, akkor egyszerűen nem tudja megkerülni a memória kezelését (mint mondjuk a folyamatokét). Kötelező és egyben gyönyörű feladat, amelyet kár lenne elszalasztani. Maga a memória kezelése (memory management) elsőre nem hangzik túlságosan bonyolultnak, hiszen a fő cél a programok tárolása (kód, adat, verem) tárolása. Ezzel lényegében biztosítva van az, hogy a tárolt programok végrehajtódhassanak, egyik (memória)állapotból a másikba kerüljenek.

Ami sok esetben a további nehézségeket szüli a memória kezelése során, az az, hogy mostanság ugye nem elégszünk meg egyszerű rendszerekkel. Az egyik ok, amiért nem, hogy biztosítani tudjuk azt, hogy a rendszerünk működni fog, és az általa futtatott programok nem tudják befolyásolni (közvetlenül). Erre azért van szükség, mert az operációs rendszerrel tulajdonképpen egy háttérben meghúzódó kezelőrendszert alakítunk majd ki a tárban is, és ekkor el kell szigetelnünk egymástól ezeket a memóriaállapotokat. Hiszen az biztos nem vezetne kellemes eredményre, ha éppen megzavarnák egymást a folyamatok. Mert ugye korunk igénye a folyamatok párhuzamos működtetése. Bár tárgyaltuk már, hogy az időosztás miatt a valóságban gyakran nem futnak ténylegesen egyszerre, a memóriában ennek ellenére még lehetnek parallel módon jelen.

Az érem másik oldala pedig az, hogy a memória az lehető leggyorsabb tár, ami jelen pillanatban a rendelkezésünkre állhat. Pontosan ezért törekedni kell a lehető legjobb mértékű kihasználása, többek között azzal, hogy mindig csak annyi memóriát adunk a programok számára, amennyi feltétlenül szükséges - ez már egyből meghiúsulhat, mert egyrészt az ideális bájtszintű kezelés helyett majd nagyobb egységekben (sok esetben lapokban) fogjuk kezelni; a könnyebb adminisztrálhatóság miatt. De ugyan így probléma okoz az is, hogy a programok memóriaigénye időben nem állandó, és úgy egészében tekintve a memória foglaltságának szerkezete is gyorsan változik. Az előbbi (a nem bájtszintű kezelés) belső töredezettséget okoz, az utóbbi (a nem állandó foglalási szerkezet) pedig külső töredezettséget. A töredezettség itt arra utal, hogy a memória lassanként elaprózódik, és egy idő után képtelenek leszünk szükséges mennyiségűt "összefogni" belőle - hely pedig lenne! Ennek a lehetséges megoldását a cikk végén még megnézzük.

De a folyamatokon kívül a memóriában még megtalálhatjuk magát az operációs rendszer kellékeit is: a különböző adminisztrációs eszközöket (segédtáblázatok, állapotok) és a kernelt. Sok esetben be szoktak töltődni azok a könyvtárak (library) is, amelyek egy-egy programozási nyelv futtató rendszerét szolgálják ki, lehetővé téve ezzel többek között azt is, hogy bizonyos programrészleteket megosszanak egymással a folyamatok. Ekkor van lehetőség némi spórolásra is, mert egy ilyen közös programkódnak elegendő csupán egyszer betöltődnie a memóriába, függetlenül attól, hogy mennyi folyamat is kívánja használni annak szolgáltatásait. A könyvtárak használata újabb jó pontnak könyvelhető el a gazdaságosság melletti harcban, mert így rengeteget megspórolunk. A kernellel együtt az előbb felsorolt komponenseket is meg kell tudni védeni a folyamatoktól, mert enélkül a rendszerünk gyorsan halálra lenne ítélve.


Oszd meg és uralkodj!

Tehát, ahogy az előbb megkarcolgattam a memória szerepét, illene most valami képet is adni arról, hogy miképp határoljuk el a folyamatokat a memóriában. Ehhez alapértelmezett esetben a szeletelés (segmentation) eszközét kínálják fel a processzorok. Ez egy címzést jelentősen megkönnyítő mechanizmus, segítségével címtereket (address space) lehet létrehozni, tehát lényegében darabokra osztani a memóriát. Ebből következik, hogy minden folyamathoz rendelhetünk a rendszerben ilyen szeleteket (i386 architektúra esetén maximálisan 16384 darab, egyenként legfeljebb 4 GB-nyi méretű), illetve így ki tudjuk alakítani a védelem körvonalait. A szeletelés használatával az egyik oldalról megkönnyítjük a programegységek összeszerkesztését a fordítás során; a másikról pedig a memória egyes szeleteihez (korábban neveztem Memória Szeletnek :)) eltérő tulajdonosokat és tulajdonjogokat tudunk rendelni. Olyan ez, mintha a Föld teljes megművelhető területét felosztanánk parcellákra, és mindenkinek kiosztanék egy-egyet belőlük. Ehhez kell még hozzáképzelni azt, hogy cserébe megszabnám, hogy mit lehet tenni a földdarabbal - csak művelni, vagy csak legelőnek használni...

A szeletelés tehát azért jelent védelmet, mert a folyamatoknak kiosztott szeletek egymástól való elszigetelést biztosítanak - felfoghatjuk őket falaknak is, amelyek sok esetben megakadályozzák azt, hogy ha egy folyamat "felrobban" (mondjuk, illegális utasítást hajt végre, vagy őrülten elkezdi firkálni a memóriát), akkor ez semmilyen hatással nem lesz a vele parallel módon futó társaira. A címterek tehát mindig egy folyamatot foglalnak magukban, de például egyetlen címtérben futhat több szál is. Ezek a címterek képviselik azt az alapvető egységet, amikben a memóriát - mint erőforrást - kezelni tudjuk a programkód tekintetében. Mint tudjuk, a szálak képesek közösen birtokolni erőforrásokat - így tehát memóriaterületet is.


A falak

Az előbb felhúzott falakat tulajdonképpen a szeletekhez társított privilégium szintek (privilege level) adják. Az első cikkben említésre került annak idején a MULTICS védelmi gyűrűs megoldása, a rétegelt kernelek ismertetése során. Nos, itt is megtalálható ez az elgondolás, mivel ezek a privilégium szintek tulajdonképpen eme gyűrűk számát adják meg (ez i386 esetén 4 szintet takar, de bizonyos procik esetében csupán kettőt), amelyek közül a legalacsonyabb számú kap a legtöbb előjogot (privilégiumot), és ezen érték növekedésével fokozatosan csökkenthetőek a jogok.

Ezen kívül minden szeletnek tartoznak jogok (itt gondoljunk csak a parcellákra!) is: ezek a végrehajtás (eXecute), olvasás (Read) és az írás (Write). Segítségükkel meghatározhatjuk az adott szelet elérési lehetőségeit, mondjuk írásvédetté téve. Gyakran ez is hozzájárul ahhoz, hogy egy folyamat - még hiba esetén is - kultúráltan érjen véget. Minden szelet tartalma könnyedén címezhető ("sorszámozható"), mivel annak első bájtja a nulladik, és egészen így folytatható ez a határig. Ez nagyon hasznos tud lenni akkor, ha megalkotunk egy olyan konvenciót, hogy az alprogramok kódját külön szeletekbe rakjuk, és mindegyik végrehajtását az adott szelet elejéről kezdjük.

A gyűrűk közötti átjárást magasabb szintről alacsonyabb szintre kizárólag ellenőrzötten lehet megtenni, ún. kapuk (gate) segítségével. Eme kapuknak több fajtája is létezik, megkülönböztetve annak tükrében, hogy milyen típusú átjárásra ad lehetőséget, "vízumot". Léteznek például hívási kapuk (call gate), amely arra szolgálnak, hogy az egyszeri folyamat egyáltalán képes legyen elérni a rendszer funkcióit. Mondanom se kellene, hogy a memóriához való hozzáférés sem lehetséges a'la random, kíméletlenül kivétel (exception) keletkezik, ha nem jogosult területre teszi egy folyamat a mancsát.


Hogyan osszuk fel a memóriát?

A szeletelést nem tudjuk megkerülni, mert ha az i386 architektúrán védett módba kapcsolunk, akkor kapásból meg leszünk ajándékozva pár szeletkével. Másrészt nem is tudjuk kikapcsolni ezt az absztrakciót, mint mondjuk majd a lapozást (paging). Nem kell aggódnunk, ennek ellenére számos memóriamodell kialakítására adódik lehetőségünk, mert majd a kernel készítése során mi - a rendszer fejlesztői - fogunk dönteni arról, hogy mennyire kívánunk szöszmötölni a szeletekkel. Én azért elmondom, hogy sok esetben megéri, mert nem igényel nagyobb erőfeszítést a processzortól ennek a címzési módszernek a használata, és ráadásul segítségével a különböző programrészleteket könnyen áthelyezhetővé tudjuk tenni, meg tudjuk védeni - egyetlen folyamaton belül.

A legegyszerűbb stratégia a memória felosztására, hogy veszünk egy részt a kernelnek (kernel space), és egy külön címteret a összes többi programnak a rendszerben (user space). Értelemszerűen a kernel címtere lesz a legmagasabb privilégium szintű, és így ott zajlik az operációs rendszer élete. Azért kell így lennie, mert az operációs rendszernek teljes körű hozzáféréssel kell rendelkeznie a hardverhez - enélkül nem tudná a legfontosabb feladatát teljesíteni! Az általa menedzselt folyamatoknak viszont nem kell mindenről tudnia, nem kell mindent irányítani, és nem kell minden komolyan vennie :) Nos, ez egy kicsit politikai tartalmúra sikeredett, de talán látható: a rendszernek kell adjuk a hatalmat, és a bizalmat, hogy képes vele élni. Amúgy ennek a felépítésnek előnye, hogy meg lehet valósítani szinte minden processzoron, mert csupán két szintre van szüksége. Igaz, nem ad valami túlságosan nagy strukturáltságot, de ebből már ki lehet csikarni egy működő rendszert. Az ilyeneket gyakran "egy címteres operációs rendszereknek" (Single Address Space Operating System) is nevezik. Ekkor a folyamatok valójában szálak lesznek, és ezek osztoznak meg valahogy a user space-n (amelyet nyugodtan megtehetnek). Tipikusnak tekinthető a mikrokerneles rendszerek esetén, oka többnyire a környezetváltás költségének megtakarításában keresendő.

Ennél klasszikusabb az a megoldás, amikor a kerneltéren kívül még minden folyamat kap saját címteret, ezáltal teljes mértékben el is vannak zárva egymástól, mindenféle komolyabb kommunikációra csak a rendszer beavatkozásával kerülhet sor. Tulajdonképpen itt sincs szükség túl sok privilégium szintre, mert a folyamatokat tekinthetjük demokratikusnak, tehát azonos jogokkal rendelkezőnek. Ezt azért lehet cifrázni mind a négy szint kihasználásával, amikor is az eddig kimaradt szintekre még elhelyezzük a meghajtóprogramokat (később még lesz szó ezekről is), illetve a futtató rendszer(ek) alprogramjait. Ha mindehhez használunk lapozást, akkor tiszta szeletelésről beszélünk.


Ha kevés lenne a memória...

Jobban belegondolva - mondjuk, alapul véve egy mostani rendszerben virtuálisan egyszerre futtatott programok számát - gyakran kevésnek tűnhet az akár 128, 256 megabájtnyi memória. Ahogy fejlődtek a számítógépek - és így nőttek velük a hozzájuk kapcsolt operatív tárak is - a programok is igyekeztek ezzel lépést tartani. Nem hinném, hogy túloznék, ha azt mondanám, hogy inkább lépéselőnyben vannak, mert félelmetesen sok memóriát igényel például egy DTP (Desktop Publishing), vagy bármilyen tervezőrendszer (pl. AutoCAD) futtatása.

Szerencsére erre már elég korán gondoltak a számítógép-gyártók, mert erre a problémára megalkották a lapozás módszerét. Eleinte a MULTICS-ban találkozhattunk vele, de a kor igényei előtt meghajolva az Intel és a konkurensei is építettek egy ilyen opciót az i386-ba. Itt most nem szabad semmi eget rengetőre gondolni. A lényege csak annyi, hogy miközben a szeletek használatával virtuális címeket hoztunk létre, ezeket most nem közvetlenül fizikai címekre (physical address) képezzük le, hanem még beillesztünk egy újabb "címvariálási" folyamatot, a lineáris címeket (linear address). Úgy is összegezhetjük az eddigieket, hogy ha nem használunk lapozást, akkor minden virtuális cím egyben a valódi, létező memória egy-egy bájtját hivatkozza.

Azért a mikroszámítógépes hőskorban elterjedt volt még az "overlay technika" is, amelyet napjainkra már felváltott az operációs rendszer által ügyesen lekezelt lapozás. Ettől függetlenül pár szóban ismertetném ennek a lényegét is. Mint ahogy a neve is mutatja (overlay - átlapolás), a programozónak fel kellett osztani a programját darabokra, és azok a végrehajtás során cserélgették egymást a memóriában. A feladat nehézsége az volt, hogy azokat az alprogramokat és adatokat kellett egyetlen részbe pakolni, amelyekre az adott lap bennléte során feltétlenül szükség volt. Számos korai fejlesztői rendszer, például a Turbo Pascal is támogatta ezt a lehetőséget.


Egy egyszerű modell, amelyben az adott lineáris memóriát leképezzük a rendelkezésre álló fizikai memóriára. Látható, hogy a lapok száma jóval meghaladja a keretekét, és nem is található a meg az összes lap egyszerre.

A lapok és keretek

A lineáris címekre azért lesz szükségünk, hogy tudjunk csalni a rendelkezésre álló memóriát illetően. Ez a "csalás" annyiban áll, hogy a programok számára azt állítjuk, hogy rendelkezünk a processzor által címezhető összes 4 GB memóriával (ami a proci 32 bites címsínéből adódik); bátran lehet pakolni akárhova. Nyilván nem igen fogunk olyan 386-ost találni, amelyik valaha is találkozott 4 GB memóriával. Így valamit ki kellett eszelni arra is, hogy a valóságban hogyan képezzük le a lineáris címeket fizikai címekké.

Ennek alapvető eszköze a lapokra (page) bontás, amelyek méretét a processzor határozza meg. Típustól, gyártótól függően ez a méret 512 bájttól akár 64 kilobájtig terjedhet. Kedvenc mikroszámítógépeinkben ez általában 4 KB. Nem kell mást tennünk, csak a fizikai memóriában eme lapoknak megfeleltetni kereteket (frame), amelyek szám a lapokkal ellentétben már messze nem fedi le a címezhető négy gigát. Számuk a rendelkezésre álló memória mérete, osztva a lapmérettel. Ahogy nevük is sugallja ("keret"), arra használjuk fel őket a működés során, bennük lapokat tároljunk. Voltaképpen a lapok tárolása úgy néz ki, hogy a keretet szimbolizáló memóriaterületre az adott lap tartalmát helyezzük el. A kialakuló igényeknek megfelelően cserélgetjük (swap) ezen keretekben a lapokat.

Mivel egyértelműen kijelenthető, hogy a lapok száma az esetek igen nagy százalékában jóval meghaladja a rendelkezésre álló keretek számát, így felmerülhet a kérdés, hogy hol marad a többi lap. Ennek megválaszolása igen egyszerű: nem a memóriában :) Egy részük sokszor nem is létezik (invalid) - hiszen miért kezeljük azokat a lapokat, amelyek tartalma üres. Másik részük az operációs rendszer működése során egyáltalán nem fog módosulni, csupán pillanatnyilag van szükség rájuk, így igény szerint - egy másik lap kicserélésével - betölthetőek a háttértárról. A leghúzósabb eset az utolsó: amikor egy lap tartalma bekerül a fizikai memóriába, és a feldolgozás során módosul is. Ekkor nincs mese, a memóriából való kikerülése során el kell menteni a pontos tartalmat.


Módosított lapok tárhelye

Az utolsó esetben vagyunk igazán gondban, mert lejjebb kell adnunk a megszokott memória sebességét, és keresnünk kell egy olyan tárat, amely rendelkezik elegendő kapacitással az információk tárolására. Korlátozva nem vagyunk ennek megjelölésében, ám konvenciók itt is élnek; a módosított (dirty) lapok sok esetben winchesterre mentődnek, a "lapterületre" (swap space). Operációs rendszere válogatja, hogy ez most csak egy állomány a sok közül, vagy jobb esetben egy külön állományrendszer. Előfordulhat viszont az is, hogy történetesen a videokártya feles memóriájába pakoltatjuk a lapokat. (Például a Linux, az Xfree86 és az nVidia kártyák esetén. [0])

Remélhetőleg nem kell hangoztatnom, hogy hasznossági sorrendben hangzottak el a megoldások. De most ragadjunk le a másodiknál (külön állományrendszer). Ekkor az operációs rendszer ugyanis pontosan tudni fogja, hogy ez speciális adat, és nagyon fontos a tárolás sebessége (mind az írás, mind az olvasás szempontjából). Ennek még megvan az az előnye is, hogy az adott állományrendszert el lehet helyezni a háttértár olyan részére, amely mondjuk, a legkisebb elérési idővel rendelkezik; másfelől pedig fix pontot biztosít a winchesteren, ami óriási előny ahhoz képest, hogy egy állomány szinte mindig kiszámíthatatlan helyen jön létre az állományrendszerben. Vagy azt se felejtsük el, hogy nehéz karbantartani egy állományrendszert úgy, hogy nem tudunk benne - fizikailag - arrébb mozdítani egy nagy méretű állományt - mert az aktív használat alatt van. Lassan azért minden modern operációs rendszer kiheverte ezt a problémát, és panaszra okom sem lehet :)

Komoly kérdés szokott lenni, hogy mekkora méretűnek illik lenni a lapterületnek. Általában azt szokták javasolni, hogy a fizikai memória méretének kétszerese legyen, mert ekkor működnek optimálisan a lapcserélési algoritmusok. Szerintem ez nem okozhat nehézséget senki sem, mert manapság jóval olcsóbb egy léptékekkel nagyobb winchester. A fukar olvasóknak viszont megjegyzem, hogy legalább annyi helyet vágjanak le, mint amekkora a fizikai memória - a kikapcsolása viszont semmi esetre sem javasolt, bár lehetséges. (Vagy marad a videómemóriás trükk.)


Melyik lapot cseréljem... és melyikre? És hogyan?

Visszatérve a lapokra és a keretekre, fel kellene még oldanunk azt a problémakört is, amely arra vonatkozik, hogy mikor melyik lapok tartalmát érdemes a keretekben tartani. Az ésszerű válasz az lenne, hogy mindig azokét, amelyeket az adott pillanatban használjuk. Persze a helyzet korán sem ennyire egyszerű. A bonyodalom ott kezdődik, hogy ritkán lesz az operációs rendszerünk abban a szerencsés helyzetben, hogy képes az összes keretbe azokat a lapokat bepasszírozni, amiket használunk is. Gondoljunk csak arra, amikor két, vagy több gigászi memóriaéhségű folyamat váltogatja egymást a rendszerünkben. Ennek a háborúnak könnyen akár vergődés (thrashing) is lehet vége. Ez a kifejezés annyit takar, hogy a rendszer egy idő után nem lesz mással elfoglalva, mint a szükséges adatok ki- és belapozásával.

A lapcserélés alapját a laphiba (page fault) nevezetű kivétel képezi, amely akkor generálódik, ha ugyan érvényes, létező lineáris cím tartalmára vagyunk kíváncsiak, de az azt magában foglaló lap nem található egyetlen keretben sem. Ekkor nincs más teendőnk, mint keresni egy lapot, kivenni a keretéből, és behozni a helyére az igényelt kollégáját. Amint ez rendben lezajlott, a kivételt okozó programot újraindítjuk.


A laptáblák sötét mágiája

A lapok aktuális állapotát egy ún. laptáblázatban (page table) tárolhatjuk el, amely alapján a processzor könnyedén meg tudja állapítani, hogy el tudjuk-e érni az adott lapot, ha igen hol, esetleg milyen korlátozások mellett - a lapokra is vonatkoznak védelmi szabályok; értelemszerűen továbbgondolva a szeletek szabályait. Mivel elméleti szinten minden lapot nyilvántartunk benne, így ennek mérete igen termetes is lehet. Ezt úgy küszöbölték ki, hogy több szintre osztották a laptáblákat, és így kaptak a rendszerfejlesztők arra picike sanszot, hogy ne kelljen minden esetben ténylegesen az össze lap állapotát nyilvántartani. Persze, csak akkor tudunk ezzel élni, ha nem használjuk a teljes lineáris memóriát (tehát a 4 GB-ot).

Ezen túl az is elő szokott fordulni, hogy így vagy úgy (hardveresen vagy szoftveresen) tartozik a laptáblázathoz egy címfordítási gyorsítótár (Translation Lookaside Buffer - TLB), amely igyekszik a laptáblázatban történő, időigényes keresést leszűkíteni. Elsőre talán butaságnak hangzik, de ha csak elképzeljük, hogy milyen sok laphivatkozás történik egyetlen másodperc alatt, akkor be kell látnunk, hogy az itt nyert idő számottevő.

Léteznek még invertált laptáblák, amelyek az idő hívó szavára keltek életre. Az indokolt megalkotásukat, hogy a 64 bites architektúrák esetén bizonyos sokkal nagyobb laptáblázatokat kellene használni. Helyette megfordították ("invertálták") az információk tárolásának irányát, és így nem azt tároljuk ekkor, hogy melyik laphoz, melyik keret tartozik (ha tartozik egyáltalán), hanem azt, hogy melyik kerethez melyik lap tartozik. Ez érezhetően racionálisabb megoldás, mert így a laptábla mérete mindig a jelenlevő fizikai memória függvénye, nem pedig konstans érték. Bár kezelésük nehézkesebb, TLB használatával ezen is enyhíteni lehet.


Példaként álljon itt egy végletekig egyszerűsített indirekt laptáblázat. Az indirektsége abban rejlik, hogy az első szintű laptáblázat bejegyzései közvetlenül nem lapokra mutatnak, hanem további - kis méretű - laptáblákra; végezetül ezek lesznek azok, amelyek egy az egyben a lapokra fognak mutatni. A valóságban ennél azért bonyolultabb, de jól megfigyelhető az ábrán az indirektség.
Az etalon

Akkor most térjük át a lapcserelés algoritmusaira is. Az optimista matematikusok próbálkoztak számos megoldással, és sikerült is megalkotni a lehető legjobb lapcserélési algoritmust. A hiba ott leledzik, hogy leprogramozni még senkinek sem sikerült. Ennek oka az algoritmus intiutivitásában rejlik, mivel azt igényli, hogy a cserék során legyünk tudatában annak, hogy melyik lapot fogjuk a legkésőbb használni. Ez szinte majdnem lehetetlen előre megmondani; még talán úgy sem lehetne teljes biztonsággal megjósolni, ha lefuttatnánk előre az adott programokat. De egy jó matematikus sose dobja ki a szemétbe, amit már egyszer sikerült felfedeznie - a feljegyzésekben így azért maradt meg, mert remek mércének bizonyult egy-egy újabb algoritmus megalkotása, illetve annak tesztelése során. Ezért is nevezik az optimális lapcserélési algoritmusnak.

Szinte mindegyik algoritmus használ még a lapok esetén egy hivatkozási bejegyzést. Feladata az, hogy regisztrálja, hogy a legutóbbi csere óta hivatkoztak-e már arra a lapra. Sejthető, ha hivatkoztak, akkor arra a lapra még szükség van, nem lenne értelme kidobni a keretből - hiszen a következő körben esetleg újból vissza kellene hozni, ami már eleve többletmunkára ítélteti a rendszert.

FIFO

Szerintem a lehető legegyszerűbb, de egyben a legcsapnivalóbb algoritmus erre a problémára a FIFO (First-In, First-Out). Ennek az alapja valójában a sor (queue) adatszerkezet, és ennek feldolgozási módjára utal a fenti elnevezés. A sorok már szerepeltek az ütemezési algoritmusoknál, így itt is hasonlót kell elképzelnünk. A sor elejére mindig a legrégebben használt lap kerül, amelyet a lapcserélés során majd ki kell raknunk a fizikai memóriából. A sor végére kerül ezek után az újonnan behozott lap. Ezt jelenti a név is: az "elsőként érkezett elsőként távozik"; gondoljunk csak egy alagútra, ahol nem lehet előzni - mert mondjuk, csak egy haladási sáv van. Mindig az a jármű jön ki először belőle, amely elsőként is ment be.

A FIFO egyik alkalmazott javítása a második esély bevezetése. Ez nem több, mint egy szabály, amely arra vonatkozik, hogy miképp kerüljük el az esetlegesen kártékony hatást: ne dobjunk ki olyan lapot, amelyet gyakran használunk. Ehhez nem kell mást tennünk, csupán a kidobásra jelölt lap esetében meg kell vizsgálni, hogy hivatkoztak-e rá. Ha igen, akkor egyelőre megkíméljük ez életét (a hivatkozást jelző bitet töröljük), és keresünk egy másik potenciális áldozatot, a sorban lépésenként haladva. Ha minden lapra hivatkoztak, akkor megkapjuk az eredeti FIFO-t, ettől eltérő esetben csak jobbra számíthatunk.

A FIFO tuningolásának azonban van még egy másik alternatívája. Ezt az óra lapcserélési algoritmusának nevezik, mert ekkor a sort szépen megfogjuk mind a két végénél, és összegyúrjuk egy gyűrűvé. Nyilvánvalóan el fog tűnni mind az eleje, mind a vége - a kidobós szabályai úgy módosulnak, hogy az eddig a sor elejét címző mutató a legrégebben használt lapra mutat. Miután megtörtént a csere, ezt a mutatót léptetjük, egészen addig, amíg a korábbi módszerhez hasonlóan nem találunk egy olyat, amelyik hivatkozási bitje nulla.


Gyakoriságon alapuló algoritmusok

Alapozhatjuk a hivatkozás gyakoriságára is az algoritmusok működésének magját. Az egyik ilyen az NRU (Not Recently Used - mostanában nem használt), amely úgy épül fel, hogy a lapokat a módosítás és a hivatkozás bitjei szerint a következő csoportokba sorolja: nem hivatkozott, nem módosított; nem hivatkozott, módosított; hivatkozott, nem módosított; hivatkozott módosított. Úgy keletkezhet "nem hivatkozott, módosított" típusú lap, hogy adott időközönként a rendszer nemes egyszerűséggel nullázza a hivatkozást jelző bitet. Ebben az esetben nagyon egyszerű teendőnk van, mert mindig az első csoporttól elindulva megnézzük, hogy tartalmaz-e elemet, és azok közül véletlenszerűen kiválasztva kiteszünk egyet a memóriából.

Az NRU-n kívül a gyakoriságot tekinti működési elvének az LRU (Least Recently Used - legrégebben használt) algoritmus, amely a legrégebben használt lapot küldi száműzetésre. Az ötlet nagyon egyszerű és remekül közelíti az etalon algoritmusunkat. Sajnos, az implementálása nem a legkönnyebb, de megfelelő hardveres és szoftverek eszközök segítségével viszonylag kis többletköltség (overhead) mellett használhatóvá válik. Szoftveresen az öregítést alkalmazzák erre a célra, amely hasonlatos az ütemezés terén tárgyalt öregítéshez (aging). Ekkor a lapokhoz egy "digitális emlékezetet" reprezentáló bitvektort (bitekből álló tömböt) rendelünk, amely bitjeit adott időközönként elcsúsztatva adjuk az elévülés, a "felejtés" látszatát. Akkor fogunk továbbra is "emlékezni" egy lapra, ha a rá való hivatkozás által ennek a bitvektornak az elejére újra beíródik egy egyes bit.


További gondok

A lapcserélés természetesen csak az egyik gond a sok közül. Mellette még figyelmet kell szentelnünk arra is, hogy a lefoglalt memóriadarabok gyakran réseket hagynak egymás között. A rések eleinte nem léteznek, a memória használata során alakulnak ki, apránként. A keletkezésük oka igen könnyen leírható. Tegyük fel, hogy vannak folyamataink, amelyek szépen feltöltik a memóriát. Ha ezek közül az egyik befejezte működését, akkor annak helye felszabadul, és máris képez egy lyukat a memóriában. Ezt később feltölti egy másik folyamat, de mondjuk nem teljesen (ennek ugyebár igen nagy a valószínűsége). Ilyen manőverek segítéségével tehát felaprózódik a memória, és képtelenek leszünk egy újabb folyamatot fogadni, pedig ha összeadjuk a résekben elveszett bájtokat, azt kapjuk, hogy lenne rá hely.

Nem tudunk a legnagyobb rés méreténél nagyobb méretű szeletet kiosztani. Erre sokféleképpen reagáltak eme tudomány lelkes művelői, és kiagyalnak néhány elfogadható megoldást. Kezdhetjük ott, hogy ha nem tiszta szeletelést alkalmazunk (tehát lapozunk), akkor lehetőségünk van a lineáris címek azon módú kiosztására, hogy logikailag egymás után fűzzük az elkallódott memóriadarabkákat. Másik esetben egyszerűen kihasználjuk azt, hogy szeleteink vannak. Mivel azok könnyen áthelyezhetőek a memóriában (ld. nem sokkal ezelőtt), egy ilyen kellemetlen helyzet esetén tömörítjük a szeleteinket, gondosan egymás mögé rendezve.

Ha ezt túlságosan időpazarlónak találnánk, akkor azzal is lehet trükközni, hogy a lyukak között valamilyen algoritmus, szabály szerint választunk. Például az "első megfelelő méretű" (first fit) szelet keresése során mindig az első rést igyekezzük betölteni az újonnani memóriafoglaláskor. Ezt továbbfejlesztve alkalmazhatjuk a "következő megfelelő méretű" (next fit) szabályt is, ahol nem a memória elejétől keressük a nekünk jó lyukat, hanem, a legutóbbi foglalás helyétől. Ha van időnk keresni, akkor a "legjobb méretű" (best fit) algoritmust is használhatjuk, amikor is végignézetjük az összes lyukat, és azt használjuk fel, amely mérete közelít a lefoglalandóéhoz. Létezik még erre a mintára a "legrosszabb méretű" (worst fit) lyuk kiválasztása, mely lényéget tekintve az előbb ellentéte.


Felhasznált irodalom

A. S. Tanenbaum - A. S. Woodhull: Operációs rendszerek (második kiadás)
[0] Ranking Hostingów – Najlepsze Hostingi 2018 – Szukasz najlepszego raningu hostingów dostepnero na ry