Memóriakezelés

Készült Knapp Gábor: Operációs rendszerek című könyve alapján.

Mind a processzoridő-, mind a memóriakezelés abból a tényből kell, hogy kiinduljon, hogy a futásra váró és a futó programok azt feltételezik, hogy egyedül ők vannak a világon, egyáltalán nem törődnek azzal, hogy van például operációs rendszer, illetve más folyamatok is futni merészelnek. A folyamatok általában azt is figyelmen kívül hagyják, hogy mennyi memória van a gépben valójában.

Pedig az erőforrások hatékony kihasználása, és a folyamatok közötti gyors átkapcsolás érdekében több folyamatnak kell egyidejűleg a memóriában tartózkodnia. Az operációs rendszer magjának (kernel), azon belül is a memória­ke­ze­lő­nek a feladata a memória elosztása a folyamatok között, a mindenkori állapot adminisztrálása és szükség esetén a háttértárak igénybevétele, mégpedig oly módon, hogy a folyamatok se egymást, se az operációs rendszert ne sérthessék meg.

---

Valóságos tárkezelés

A valóságos tár elnevezés a virtuális tártól való megkülönböztetést szolgálja. A kétféle módszer között a leg­lé­nye­ge­sebb eltérés az, hogy a valós tárkezelés esetében az éppen végrehajtott folyamathoz tartozó prog­ram­u­ta­sí­tá­sok­nak és adatoknak teljes egészében az operatív memóriában kell tartózkodniuk, míg virtuális tárkezelés esetén csak az éppen végrehajtás alatt álló rész van az operatív tárban, a program és az adatok többi része a háttértáron található.

Rögzített címzés

Amíg egy számítógépen csak egy felhasználó dolgozhatott és ő is csak egyetlen, viszonylag kicsi programot futtathatott, a memóriakezelés különösebb gondot nem okozott. Az operációs rendszer állandó területen, például a memória legelső, legkisebb című rekeszein helyezkedett el, a felhasználói program használhatta az operációs rendszer végétől egészen a legnagyobb címig az egész memóriát. A program változóinak, illetve vezérlésátadásainak címe így már fordítás közben meghatározható volt.

A tárvédelem is elég egyszerű ebben az esetben, mindössze azt kell figyelni, hogy egy adott, az ún. határregiszterben tárolt címnél kisebbet a felhasználói program ne érhessen el, mert az már az operációs rendszer fennhatósága. A felhasználói program az operációs rendszert rend-szerhívások által érte el. A rendszerhívás első dolga, hogy a processzort védett üzemmódba kapcsolja, így biztosítva az operációs rendszer számára az egész memória elérését. Természetesen a határregiszter tartalmának változtatása is szigorúan az operációs rendszer feladata volt.

Áthelyezhető címzés

Az első korlát, amibe a rögzített címzésű rendszerek beleütköztek, az volt, hogy az operációs rendszer mérete nem bizonyult állandónak. Ez önmagában még nem lett volna baj, de a programozók is hamar megelégelték, hogy egy-egy operációs rendszer módosítás után mindig módosítaniuk kellett programjaikat. Amikor azonban megjelentek az olyan operációs rendszerek, melyek tranziens résszel is rendelkeztek, azaz egyes részeik csak akkor töltődtek be a memóriába, ha szükség volt rájuk, a szorgalmas programozóknak is bealkonyult, hiszen a felhasználói program rendelkezésére álló memória címtartomány a program végrehajtása során is változhatott.

A megoldás viszonylag egyszerű volt. A programok fordításakor a fordítóprogram már nem közvetlen fizikai címeket generált, (azaz nem azt mondta meg például, hogy ugorj el a 2345H címre), hanem a program elejéhez képesti relatív címeket (tehát azt mondta meg például, hogy ugorj el a program elejéhez képesti 1234H címre). Ahhoz, hogy ezekből a relatív címekből fizikai címeket kapjunk, most már csak azt kellett tudni, hogy hol kezdődik a program a memóriában. Ha ezt tudjuk, akkor ehhez a kezdőcímhez hozzá kell adni a programban szereplő relatív vagy más néven logikai címet és megkapjuk a keresett memóriarekesz fizikai címét. Ennek a módszernek a támogatására találták ki az ún. bázisregisztert. Ez a regiszter tartalmazza a program kezdő- vagy más néven báziscímét. A processzor minden memória műveletnél automatikusan hozzáadja a bázisregiszter tartalmát az utasításban szereplő címhez és az így kapott összeg lesz az a fizikai memóriacím, amihez fordul. Már csak egy kérdés maradt hátra: ki határozza meg a program kezdőcímét? Természetesen, ez az operációs rendszer feladata, hiszen az operációs rendszer mindig tudja magáról, hogy éppen meddig ér és hol kezdődik a szabad hely a memóriában, így a felhasználói programot az első szabad címtől kezdve töltheti be, ezt a kezdőcím értéket pedig a program betöltésekor beírja a bázisregiszterbe.

Átlapoló (overlay) módszer

Az eddigiekben olyan kicsi programokról volt szó, amelyek teljes egészükben belefértek a memóriába. A programozók természetesen nem elégedtek meg ezzel, nem voltak hajlandók fejet hajtani a gyarló földi korlátok előtt, nagyobb programokra vágytak. Ezért azonban meg kellett dolgozniuk. Úgy kellett a feladatokat szervezni, hogy az olyan méretű blokkokból álljon, melyek külön-külön már elhelyezhetők. Ezzel az átlapoló technikával (overlay) elérhető volt, hogy a memóriában állandóan csak a programrészek közötti átkapcsolást végző modulnak kelljen tartózkodnia, a többiek közül hol az egyik, hol a másik rész került a memóriába, a többi a háttértáron várakozott.

Az ilyen programozáshoz az operációs rendszer semmiféle támogatást nem adott, mindenről a programozónak kellett gondoskodnia, de megérte: a program mérete meghaladhatta a memória méretét.

Még egy nagyon fontos és előremutató dolog történt. A háttértár, amely eddig csak a programok tárolására szolgált, először vesz részt a program futtatásában aktív szereplőként.

Tárcsere (swapping)

A következő kihívást az jelentette, amikor egy időben több felhasználó programjának futtatását kellett biztosítani, persze egymástól függetlenül. A feladat megoldásának legegyszerűbb és legősibb módja, ha minden felhasználó kap egy bizonyos időszeletet, majd ha az lejárt, az általa használt egész memóriaterületet az operációs rendszer a háttértárra másolja, és onnan betölti a következő felhasználóhoz tartozó memóriatartalmat. Így mindegyik felhasználó úgy dolgozhat, mintha az egész memória az övé lenne. A memóriatartomány ki-be másolását tár-cserének (swapping) hívjuk, a másolás eredményeképpen keletkező állományt cserefile-nak (swap file). A módszer nagy hátránya, hogy lassú, hiszen az időszelet lejártakor a teljes memóriaterületet a háttértárra kell másolni, illetve onnan betölteni, ami nagyon sokáig tart!

A processzor-ütemezéshez hasonlóan itt sem mindegy, hogy mekkora az a bizonyos időszelet, mert ha túl kicsi, akkor a másolgatásra fordítódik az idő legnagyobb része. Segíteni lehet a dolgon úgy, ha az operációs rendszer elég okos, és csak azokat a memóriarészeket mozgatja, amelyek változtak, de ennek menedzselése bonyolult.

A címzés és a tárvédelem szempontjából semmi lényeges változás nem történt, az operációs rendszernek sem az átlapoló, sem a tárcsere technika esetén nem kell többet tudnia, mint az áthelyezhető címzés esetén.

Állandó partíciók

Mi történik azonban, ha az éppen futó folyamat várakozni kényszerül, például felhasználói adatbevitelt vár? Tegyük félre, és hadd jöjjön a másik? A másik folyamathoz tartozó memóriaterület betöltése viszont időigényes, ki tudja, hogy megéri-e? Ha állandóan több folyamat tartózkodhatna a memóriában, egyszerű lenne a dolog, a várakozás idejére csak át kéne gyorsan kapcsolni a másikra, és az máris futhatna.

Ha a felhasználói folyamatok számára rendelkezésre álló memóriaterületet egymástól független részekre, partíciókra osztjuk, több program memóriában tartására is lehetőség nyílik. Egy-egy partíció úgy viselkedik az őt birtokló folyamat számára, mintha teljesen önálló memória lenne, a partíción belül lehetőség van az átlapoló vagy a tárcsere technika alkalmazására is.

Mekkora legyen azonban egy partíció? Ha túl kicsi, esetleg nem fér bele folyamat. Ha túl nagy, akkor – mivel a partíciót csak egy folyamat használhatja -, sok kihasználatlan üres hely marad a partíció területén belül. Ezt a jelenséget nevezzük belső elaprózódásnak (internal fragmentation). A gyakorlatban az a módszer terjedt el, hogy becslések és statisztikák alapján a memóriában több különböző méretű partíciót alakítottak ki.

A partíciókat alkalmazó rendszerekben az operációs rendszerekre már komoly feladat hárul. Ismerniük kell a partíciók méretét és annyi bázisregiszter-határregiszter párt kell számon tartaniuk és folyamatosan vizsgálniuk, ahány partíció van. A másik feladat a partíciók kijelölése a folyamatok számára. Bármilyen tudományosan történt is a partíciók méretének megválasztása, a folyamatok csak azért sem jönnek a megfelelő sorrendben. Az operációs rendszernek döntést kell hoznia, hogy a futásra váró programok közül melyik kapjon meg egy felszabaduló partíciót. Ha az első érkező kapja (FCFS – előbb jött előbb fut), akkor fennáll a veszélye annak, hogy kicsi program nagy partíciót foglal el, ami rossz tárkihasználást eredményez. A másik megvalósított stratégia szerint az operációs rendszer külön várakozási sort tart fenn a különböző memóriaigényű programoknak. Ez utóbbi esetén viszont például lehetséges, hogy a nagyobb partíció üresen áll, míg a kisebbért vérre menő küzdelem folyik. Az eredmény újra csak rossz memória kihasználás.

Rugalmas partíciók

Az állandó partíció mérethátrányait jórészt kiküszöböli, ha a partíciók számát és nagyságát nem rögzítjük szigorúan, azok rugalmasan alkalmazkodhatnak az aktuális feltételekhez. A teljesen szabadon kezelt méret és kezdőcím azonban túl bonyolult címszámítást igényelne, ezért a partícióméretet célszerű valamely kettő hatvány egész számú többszörösére választani. (pl. 2048) Az operációs rendszer ebben az esetben nyilvántartja a partíciók foglaltságát, és az érkező folyamatoknak a befejezett folyamatok után fennmaradó lyukakból választ helyet, persze, csak ha van olyan szabad terület, ahová az befér.

A rugalmas partíciók módszere (majdnem) kiküszöböli a belső elaprózódást. Egy kis maradék hely mindig lesz, hiszen a programok mérete nem pontosan egyezik meg a minimális partícióméret (a fenti példa szerint 2048 bájt) egész számú többszörösével. De könnyű belátni, hogy a fenti példában még a legrosszabb esetben is az egy folyamatra eső belső elaprózódás csak maximum 2047 Byte lehet, ami elhanyagolható).

„Cserében” viszont megjelenik egy új veszély. Ugyanis, ha egy folyamat befejeződik, akkor a helyére betöltendő új folyamat memóriaigénye nem biztos, hogy megegyezik az előzőével. Nyilvánvaló, hogy ha az új folyamat memóriaigénye nagyobb, mint a régié volt, akkor az ide nem tölthető be, viszont ha kisebb, akkor az új folyamat vége után marad egy kis szabad hely, amely viszont általában már túl kicsi, hogy oda más folyamatok beférjenek. Azaz előbb-utóbb a folyamatok által használt memóriaterületek között viszonylag kicsi, de összességében akár jelentős méretű lyukak alakulnak ki. Ezt hívjuk külső elaprózódásnak (external fragmentation). Könnyen előfordulhat ugyanis, hogy egy folyamat betöltéséhez lenne elég szabad hely, de nem folytonosan, hanem az egyes aktív partíciók között teljesen szétdarabolódva. Megoldást jelenthet, ha olykor egy tömörítő algoritmust futtatunk (garbage collection), mely a memóriában lévő folyamatokat folytonosan egymás után rendezi, természetesen úgy, hogy közben módosítja a hozzájuk rendelt bázis- és határregisztereket is. Bár egy jól átgondolt, a várakozó programok jellemzőit is figyelembe vevő algoritmus itt is csodát tehet, jelentősen lerövidítve a tárrendezéshez szükséges időt, de a tömörítő algoritmus mindig nagyon lelassítja a rendszer működését. Ez különösen interaktív rendszerek esetén nagy probléma: egy türelmetlen felhasználó esetleg a tömörítés alatt elkezdi nyomkodni a reset gombot…

Lapozás (paging)

Mi okozta az elaprózódást az állandó és a rugalmas partíciók használata esetén? Az, hogy a programjaink nem egyforma memóriaterületet igényeltek, viszont ragaszkodtunk ahhoz, hogy folytonosan helyezzük el őket a memóriában. Mivel azon nem tudunk változtatni, hogy a folyamataink különböző méretű memóriát igényelnek, próbáljunk meg segíteni úgy, hogy lemondunk arról, hogy a folyamataink folytonosan helyezkedjenek el a memóriában.

Osszuk fel a rendelkezésre álló operatív memória területet egyforma és viszonylag kisméretű egységekre, ún. lapokra! Egy folyamat memóriában való elhelyezésekor most már nem szükséges az, hogy akkora összefüggő szabad memóriaterület álljon rendelkezésre, amennyit a folyamat igényel, hanem elég az, hogy összességében legyen ennyi hely. A folyamat első néhány lapját elhelyezzük az első szabad helyen, a következő néhány lapot a másodikban, stb.

Igen ám, de felmerül egy új probléma. Mivel az egyes folyamatok most már nem folytonosan helyezkednek el, nem elég már csak azt megjegyezni, hogy hol kezdődnek és milyen hosszúak, hanem sajnos nyilván kell tartani, hogy az egyes részek hol helyezkednek el. Erre a célra szolgálnak a laptáblák. Az operációs rendszer minden egyes folyamat betöltésekor létrehoz a folyamat számára egy laptáblát, mely a logikai lapokhoz hozzárendeli a fizikai lapot. A következő ábrán az operatív memória 8 lap méretű és ebből pillanatnyilag a 0., az l., a 3. és a 6. lapot használják más folyamatok, míg a 2., a 4., az 5. és a 7. lap üres. Mivel összességében 4 üres lap van, betölthetünk egy olyan folyamatot, amely 4 lapot igényel. A folyamat első (0. sorszámú ) lapját töltsük be például az operatív memória 4. számú laphelyére, az 1. sorszámút az 5. üres helyre, a 2. sorszámút a 2-ra és végül az utolsó, 3. sorszámú lapot a 7. helyre. Ennek a nyilvántartásához létre kell hoznunk egy négysoros laptáblát, mely első sora azt mutatja, hogy a 0. sorszámú logikai lap a 4. sorszámú fizikai lap helyére került az operatív memóriában stb.

(Megjegyzés: Azt könnyű belátni, hogy igazából a laptábla első oszlopára nincs is szükség, hiszen a laptábla sorainak sorszáma egyértelműen utal a logikai lap sorszámára. Itt az ábrán ezt az első oszlopot csak a megértés elősegítésére tüntettük föl.)

Most már csak egy problémát kell megoldani. Ez pedig az, hogy hogyan találjuk meg a memóriában az egyes utasításokat és adatokat? Hiszen a fordítóprogramunk azt mondja, hogy például ugorjunk el a program elejéhez képesti 16. sorra. Igen ám, de hol van most a 16. sor, hiszen a folyamatunk nem folytonosan helyezkedik el a memóriában! Az egyszerűség kedvéért tételezzük föl, hogy minden lap 10 sorból áll, amelyeket 0 és 9 közötti számokkal látunk el. (Természetesen a valóságban egy lap mérete célszerűen nem a 10 valamelyik hatványával egyezik meg, hanem a 2-ével.) Ezek után könnyű kiszámolni, hogy a 16. logikai sor az 1-es számú logikai lapon helyezkedik el és azon belül ez a 6. számú sor. (Ezt úgy hívjuk, hogy a lapon belüli eltolás értéke 6.) Most már csak azt kell tudnunk, hogy hol van az operatív memóriában az 1. számú logikai lap. De hiszen éppen ezt mondja meg a laptábla 1. sora! Ha ránézünk a laptáblánkra, látható, hogy az 1. logikai lap az 5. fizikai lap helyén van az operatív memóriában és ezen belül keressük a 6. sort, vagyis a 16. logikai cím a valóságban az 56. fizikai címen található meg.

Nézzük meg általánosan, hogy lapozásnál hogyan történik a címszámítás!

A processzor által kiadott logikai címet formálisan két részre osztjuk. A cím első része adja meg a lapszámot, míg a második része a lapon belüli eltolást. Ezek után megnézzük a laptábla „lapszám”-adik sorát, és az ott található számérték megmutatja a lap fizikai kezdőcímét az operatív memóriában. Ehhez a számértékhez kell hozzáilleszteni (úgy mondjuk, hogy „hozzáadni”, holott ez nem összeadást, hanem hozzáillesztést jelent!) a lapon belüli eltolás értékét.

fizikai cím számítása

Nézzünk egy valóságos példát! Tegyük fel, hogy a logikai cím 16 bites, azaz 2¹⁶ = 65536 sort címezhetünk meg. Legyen egy lap mérete 2¹¹ = 2048 sor! Ebből kiszámítható, hogy 2¹⁶ / 2¹¹ = 2⁵ = 32 db lapunk van. Azaz a lapok kiválasztására 5, míg a lapon belüli sor kiválasztására (eltolás) 11 bit kell. Például így:
logikai cím: 00010 | 10110101110 → lapcím: 00010, eltolás: 10110101110

Tegyük fel, hogy a laptábla 00010 (=2) sorában az 10111 (=23) számérték található, azaz a keresett memóriahely fizikai címe: 10111 | 10110101110.
Lapozásnál a címszámítás látszólag egyszerű: a folyamat által kívánt logikai címnek azt a részét, amely a laptábla megfelelő rekeszére mutat, ki kell cserélni a laptábla megfelelő rekeszének tartalmára és már készen is áll a fizikai cím. De hol legyen a laptábla, és hány rekeszből álljon?

Adott lapméret esetén tudjuk ugyan a lapok, azaz a szükséges laptábla rekeszek számát, de a memória is (egyszerű bővítéssel), a lapméret is változhat (az operációs rendszer más beállításával), így tisztán hardver eszközökkel nehéz megoldani a címszámítást. A gyakorlatban az terjedt el, hogy egy-egy folyamat létrehozásakor az operációs rendszer megfelelően védett területen létrehozott a folyamat számára egy laptáblát a memóriában, és a laptábla címét a folyamat egyéb adataival együtt a folyamatleíró blokkban (PCB) tárolta. A címszámító hardver megkapja az éppen futó folyamat laptáblájának címét, ahhoz hozzáadja a logikai lapcímet, és az így keletkezett mutató által címzett rekeszből veszi ki a lap fizikai kezdőcímét. A dolog működik, de a folyamat minden egyes memóriához fordulása egy újabb memóriához fordulást igényel, tehát a memória elérés ideje megduplázódik. (Ezt az elrémítő hatást cím-számítást segítő asszociatív memória alkalmazásával kb. 10%-ra lehet csökkenteni. Lásd később, a virtuális tárkezelésnél!)

Láthatjuk, hogy a lapozás alkalmazásával a külső elaprózódást kiküszöböljük, a belső elaprózódás minimalizálását pedig az szolgálja, hogy a lapok viszonylag kicsik. (A folyamatok mérete általában nem egész számú többszöröse a lapméretnek, így folyamatonként átlagosan egy fél lapnyi terület üres marad.) A belső elaprózódás szempontjából az lenne az optimális, ha a lapméret 1 sor lenne, de akkor a laptábla mérete lenne nagyon nagy. E két szempont közötti kompromisszum eredménye az, hogy a gyakorlatban a lapméret 1-4 kB.

A lapozó technika amellett, hogy kiküszöböli az elaprózódást, mintegy melléktermékként egy további lehetőséggel kecsegtet, amelyet főképp régebbi, kis címzési kapacitású processzorok esetén lehet jól használni.

A processzor látszólagos címzési tartománya könnyedén megnövelhető, hiszen nem kell mást tenni, mint a laptábla szóhosszúságát megnövelni. Az egyszerre kiadható címek száma ugyan nem növekszik, de azok egy szélesebb tartományban helyezkedhetnek el. Például az előző, 16 bites címet alkalmazó példánkkal élve, eredetileg a megcímezhető memória mérete 2¹⁶ byte, azaz 64 kB lehetett. Ha minden 5 bites logikai lapcímhez 8 bites fizikai lapcímet rendelünk, (azaz a laptáblában nem ötbites, hanem nyolcbites számokat tárolunk), akkor 8-szor annyi, azaz 512 kB memória címezhető. Egy folyamat címtartománya ugyan nem haladhatja meg a 64 kB-ot, viszont egyszerre a memóriában lehet 8 ilyen folyamat!