Adatok a memóriában: címzés, allokálás

Folyamatkezelés, processzusok, folyamatok

Processzus: végrehajtás alatt álló program. A processzusnak bizonyos erőforrásokra (pl. CPU idő, memória, állományok, I/O berendezések) van szüksége, hogy a feladatát megoldhassa.

Egy végrehajtható programból, a hozzákapcsolódó adatokból és a végrehajtási környezetből tevődik össze (az összes információ, ami ahhoz szükséges, hogy az operációs rendszer kezelni tudja a processzust)

Az operációs rendszer az alábbi tevékenységekért felel a processzusok felügyeletével kapcsolatban:

processzus létrehozása és törlése

processzus felfüggesztése és újraindítása

eszközök biztosítása a processzusok szinkronizációjához és kommunikációjához

Memóriakezelés

A memóriakezelő feladata:

- folyamatok ne sértsék meg egymást – memóriaelosztás

- mindenkori helyzetadminisztrálás

- aktuális háttértárak igénybevétele

A memória legyen gyors, megfelelően nagy, olcsó, és kikapcsolás után is őrizze meg az adatokat.

Hierarchia (tároló hierarchia)

1. Kisméretű drága, gyors és felejtő – CACHE

2. Közepes méretű, felejtő, közepesen drága (pár MB) – RAM

3. Lassú, olcsó nem felejtő (pár GB) – WINCHESTER

A memória az egyik legfontosabb (és gyakran a legszükösebb) erőforrás, amivel egy operációs rendszernek gazdálkodnia kell; foleg a többfelhasználós rendszerekben, ahol gyakran olyan sok és nagy folyamat fut, hogy együtt nem férnek be egyszerre a memóriába.

Amíg a multiprogramozás nem jelent meg, addig az operációs rendszerben nem volt olyan nagy szükség a memóriakezelo részekre. A multiprogramozás megjelenésével azonban szükségessé vált a memóriának a futó folyamatok közötti valamilyen "igazságos" elosztására. A megoldást a virtuális memóriakezelés jelentette. Ez úgy muködik, hogy az operációs rendszer minden egyes folyamatnak ad a központi memóriából egy akkora részt, amelyben a folyamat még úgy ahogy muködik, és a folyamatnak csak azt a részét tartja a központi memóriában, amely éppen muködik. A folyamatnak azt a részét, amelyre nincs szükség (mert például már rég nem adódott rá a vezérlés, és feltételezhetjük, hogy rövid idon belül nem is fog végrehajtódni) ki kell rakni a háttértárra (a diszken az ún. lapozási területre). Ez a megoldás azért muködik, mert a programok legtöbbször egy eljáráson belül ciklusban dolgoznak, nem csinálnak gyakran nagy ugrásokat a program egyik végérol a másikra (ez a lokalitás elve).

A központi egység fel van szerelve egy úgynevezett memóriakezelo egységgel (MMU), amely figyeli, hogy olyan kódrészre kerül-e a vezérlés, amely nincs benn a központi memóriában (mert például a háttértárra van kirakva). Ha a memóriakezelo egység azt találja, hogy ez az eset áll fenn, akkor az operációs rendszert arra utasítja, hogy rakja ki a háttértárra a folyamatnak azt a részét, amely jelenleg a memóriában van, és azt a részt hozza be a helyére, amelyre ezután szükség lesz.
A virtuális memória kezelése leggyakrabban lapozással (paging) történik. Ekkor a virtuális memória (egy folyamat virtuális címtartománya, amit a CPU biztosít) fel lesz osztva egyenlo nagyságú részekre, ún. lapokra (pages) - a háttértár és a memória között legalább ennyi byteot fog az operációs rendszer átvinni (vagy ennek többszörösét). A fizikai memória pedig fel lesz osztva ugyanolyan méretu lapkeretekre (page frames). Ha mondjuk a virtuális címtartomány 128 KByte, és 64 KByte fizikai memória van a számítógépbe építve, akkor ez 32 lapot, és 16 lapkeretet jelent, ha a lapméret 4 KByte. Ha egy program végrehajt egy olyan (gépi kódú) utasítást, amely a memória valamelyik rekeszére hivatkozik (a hivatkozott memóriarekesz címét nevezikvirtuális címnek), akkor ezt a címet eloször a processzor átadja az MMU-nak, ami majd egy fizikai memóriabeli címet állít elo belole. E feladatának ellátásához az MMU tárol egy ún. laptáblát (vagy legalábbis valamilyen módon hozzáfér a laptáblához), amely a lapok és lapkeretek egymáshoz rendelését tartalmazza egy speciális ún. "érvényességi" bittel, ami minden egyes laphoz tárolva van, és a bit értéke azoknál a lapoknál 1, amelyekhez tartozik a fizikai memóriában lapkeret. Az MMU muködése során egy kapott virtuális címhez tartozó lapról megvizsgálja, hogy az "érvényességi" bitje 1-e. Ha igen, akkor a megadott laphoz tartozó lapkeret sorszámát visszaadja a CPU-nak (mondjuk ... ez történhet így is), és az a kívánt adatot a megfelelo (fizikai memória-) rekeszbol megszerzi (vagyis azt csinál vele, amit a gépi kódú programban a végrehajtott gépikódú utasításban megadtak). Mi történik akkor, ha az "érvényességi" bit 0? Ekkor egy ún. hardware-interrupt (megszakítás) keletkezik, amit laphibának (page faultnak) neveznek. Ekkor kerül végrehajtásra az operációs rendszer memóriakezelo része, ami egy másik "érvényes" (fizikai memóriabeli) lapnak az 1-es érvényességi bitjét 0-ra állítja, és a hozzá tartozó lapkeretet a diszkre menti (az ún. lapozási területre). A lapkeretet ezután beírja a laptáblába ahhoz a laphoz, amelyhez a laphiba során hozzá akartak férni, betölti a diszkrol (lapozási területrol) a megfelelo laphoz tartozó lapkeret tartalmát, a laphoz tartozó "érvényességi" bitet 1-re állítja, és az MMU ezután már laphiba nélkül el tudja végezni a címtranszformációt.

Több programnak szüksége lehet esetleg több virtuális címtartományra is. Sok CPU lehetoséget ad szegmentált memóriakezelésre, ami annyit jelent, hogy a program több ún. szegmensben is tárolhat adatokat, és mindegyik szegmenshez külön-külön laptábla tartozhat (mondjuk ... de ez nem mindig van így). Minden szegmensnek van egy dinamikusan változtatható mérete, ami az adott szegmensben megengedett legmagasabb sorszámú memóriarekeszt adja meg. Ilyen rendszerekben a memória címzésekor meg kell adni egy szegmens-sorszámot és az azon belüli virtuális címet is. Ilyen CPU-kon gyakori az is, hogy az operációs rendszer rövid idore nemcsak egy-egy lapot, hanem egy egész szegmenst visz ki a háttértárra - lényegében azt nevezik swappingnek.


Bevezető

Számítógépben található memória modul

A számítógép alaplapján található a memória. A központi feldolgozóegység direkt kapcsolatban áll a memóriával. A memóriában tartózkodnak az éppen futó programok, és a programhoz tartozó adatok. A számítógép memóriája byte-okból épül fel, melyek sorszámozva vannak 0-tól n-1-ig, ahol n a memória mérete. A mai számítógépek memóriái byte-szervezésűek, ami azt jelenti, hogy a legkisebb adatmennyiség amellyel dolgozhatunk 1 byte (8 bit).

Memória cím

A memória byte-jai be vannak sorszámozva, e sorszámokat a megfelelő byte-ok címeinek nevezzük. A memória címeket általában hexadecimálisan adják meg. Tehát, a memória minden byte-jának van egy címe, amit arra használhatunk fel, hogy tudjuk melyik byte-ról van szó. Illetve van tartalma, aktuális értéke, amely $0 és $FF közzé eshet.

Memória címzése

Ahhoz, hogy a memória byte-jait elérhessük, a memóriát címezni kell. A központi feldolgozóegység (processzor) a címet 16, 32, 64 biten tárolja. Hogy pontosan hány biten, az processzorra jellemző adat. Mivel 16 biten 216 különböző érték tárolható, ezért 16 bites, vagyis két byte-os címzés esetén csak 216 , azaz 65535 (64 KB) nagyságú lehetne a memóriánk - az ezen felüli byte-ok nem címezhetők. Ez rendkívül kevés, és a mai igényeknek nem felel meg. 32 bites címzés esetén 232 byte, azaz 4 GB a memóriakorlát. Ugyanennyi címbittel még nagyobb memória címezhető, ha a memóriát 2, 4, 8 stb. byte-os egységként kezeljük.

Redundancia

Ha a memóriát azonos méretű tárolórekeszek összességének vesszük, akkor szemelőt kell tartanunk azt is, hogy valamennyi tárolórekesz mellett van egy 9. bit is, amelyet ismertebb nevén paritásbit -nek is szokás nevezni. A paritásbit feladata, hogy felismerje az esetleges tárolási hibákat (redundancia). Értéke 0 vagy 1 lesz attól függően, hogy a rekeszbe történő íráskor páros vagy páratlan az egyesek száma. Ha a tárolórekesz kiolvasásakor nem felel meg az egyesek száma a paritásbit értékének, akkor a processzor memória hibát jelez.

Memória tartalma

A memória tartalma a program futása során állandóan változhat. A memóriának bármely byte-ját közvetlenül el tudjuk érni, oda eltárolhatunk adatot, és el is tudjuk olvasni annak tartalmát. Tároláskor természetesen a memória előző tartalma törlődik, olvasáskor viszont nem változik. A számítógép kikapcsolásakor a memória tartalma általában elvész.

Memóriák csoportosítása

A memóriákat fizikai szempontból két csoportra oszthatjuk.

RAM (Random Access Memory)
A központi feldolgozó egység a memória tetszőleges byte-jait azonos idő alatt éri el. Az ilyen elérésű memóriát véletlen elérésű memóriának nevezik.
Olvasható, írható és törölhető a tartalma.
Ahhoz, hogy az adatokat el tudja tárolni, külső tápfeszültségre van szüksége, vagyis a számítógép kikapcsolásakor a benne tárolt adatok elvesznek.
Operatív tár céljára használják. Egy program futása úgy történik, hogy a először a program betöltődik a RAM-ba, majd végrehajtódnak az utasítások.
A RAM gyorsabb mint a ROM.

ROM (Read Only Memory)
A memória, amelybe az adatok véglegesen be vannak égetve, a ROM. A számítógép vezérléséhez szükséges alapvető parancsokat tartalmazza.
Tartalma olvasható, de nem változtatható meg.
Programozása a gyártáskor történik.
Információ tartalmát a számítógép kikapcsolásakor is megőrzi.
Speciális fajtája a PROM , melyet a felhasználó egy speciális készülékkel programozhat, utána azonban a tartalma csak olvasható. Például az EPROM , mely ultraibolya fénnyel törölhető majd újraírható.

RAM-ok csoportosítása

DRAM (dinamikus RAM): olcsóbban gyártható, mivel a bitet a félvezető kapacitása tárolja, de a háttérben rendszeres időközönként végig kell címezni a sorokat, ellenkező esetben elvész a benne tárolt információ. Sorok és oszlopok: alacsony szinten a DRAM-ok nem egy skalár memóriacímmel címződnek, hanem sor és oszlop kijelöléssel. A sorkijelölés hatására kiolvasódik az egész sor és egyúttal vissza is íródik.
SRAM (statikus RAM): ebben már rendes D tároló cella lett kialakítva, ami duplá akkora gyártási költséget jelent. Azonban nem kell frissíteni az SRAM-ot, mert a cella mindkét állapotában stabilan megmarad, amíg tápfeszültséget kap. Általában ezért kisebb kapacitásúak (néhány 10 MB-os nagyságrendig maximum), azonban nagyon gyors működésűek és az üzemi állapotukat nem szakítja meg frissítési ciklus.

ROM-ok csoportosítása

PROM: egyszer programozható, üzem közben csak olvasható memória. Technológiailag általában vékony szilíciumszálakat égettek át a programozás során. Az üres memória minden bitjében ép volt ez a szál.
EPROM: elektromos árammal írható memória, törlése UV fénnyel történt.
EEPROM: elektromos árammal írható és elektromos árammal törölhető memória. UV fény és kvarcablak a tokozáson már nem kell.
FLASH ROM: az EEPROM cellájának írása nagyságrendileg 1 ms időt vesz igénybe, azaz nagyon lassú. Ezt feloldandó X oszlop hosszú (pl. 512 byte) sorokra osztották a memóriát a byte szervezés helyett. Így ha bele akarunk írni 2 kB-ot, az 4 ms alatt megtörténik, szemben a klasszikus EEPROM byte-os szervezésével, ahol 2000 ms alatt zajlott volna le. Amennyiben a példának bemutatott FLASH-ben 16 byte-ot akarnánk írni, akkor alacsony szinten kiolvasódik a teljes 512 byte, beleíródik a RAM-ba a megfelelő 16 byte és az új 512 byte-os tartalom íródik vissza a FLASH ROM sorába.
A gyakorlatban az EPROM írási sebessége is gyorsult, ám az igazi sebességnövekedést a FLASH-eknél még mindig azzal érik el, hogy a sorok hossza gyakran hosszabb, mint 512 byte, így az egyidejű párhuzamos írás okán adnak jobb sebességértéket.

Memória típusok használata

ROM típusú memóriák:
A BIOS-t tartalmazó memória a ROM-BIOS. Melynek feladata az egyes hardver elemek működésének irányítása. Ennek tartalmát a DOS a RAM-ba másolja.
Nagy felbontású VGA monitorok esetén, a vezérlőkártyán is találhatunk ROM-ot.
RAM típusú memóriák:
Operatív memória. Ennek első 640 KB-os részét, hagyományos memóriának, az 1 MB feletti részét pedig kiterjesztett memóriának (XMS) nevezzük. A DOS közvetlenül csak a hagyományos memóriát tudja kezelni.
CMOS-RAM. Olyan kis fogyasztású memória, amely külön akkumulátorról kapja az áramot, így a gép kikapcsolásakor sem veszíti el tartalmát. A számítógép konfigurációs beállításait őrzi.
CACHE-MEMORY. Kis kapacitású gyorsító memória.
Virtuális memória
A számítógépnek lehet úgynevezett virtuális memóriája. Itt tulajdonképpen arról van szó, hogy a gép - igazi memória hiányában - memóriának használja a merevlemez egy bizonyos meghatározott részét.

Az alapfogalmak összegyüjtése után egy részletesebb leírás

Valóságos tárkezelés

A valóságos tár kifejezés kis magyarázatra szorul. Nem minden tár valóságos? Természetesen az, de létezik a tárkezelésnek egy olyan - nemsokára ismertetendő - módszere is, melyet kidolgozói virtuális tárkezelésnek neveztek el. 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 leglényegesebb eltérés az, hogy a valós tárkezelés esetében az éppen végrehajtott folyamathoz tartozó programutasításoknak é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 rendszerhí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árcseré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 Byte - 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, úgynevezett 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 fel.)

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 fel, 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 ezt 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.

Lapcsere stratégiák

Az optimális stratégia (Optimal - OPT)

Az optimális stratégia szerint azt a lapot kell kicserélni, amelyikre a legtávolabbi jövőben lesz szükség, hiszen így a bent maradó lapokkal a lehető legtovább ki tudjuk elégíteni a lapok iránti igényeket laphiba nélkül.

Előbb jött - előbb megy (First In First Out - FIFO)

Mivel láttuk, hogy az optimális stratégia sajnos megvalósíthatatlan, próbáljunk meg kitalálni olyan algoritmust, amely megközelítőleg olyan hatékony, mint az optimális, de megvalósítható. Forduljunk megint a már jól ismert lokalitási elvhez. A lokalitási elv azt mondta ki, hogy ha a programunk egy adott pontján tartózkodunk, akkor valószínűleg viszonylag sokáig ennek egy szűk környezetében maradunk. „Lefordítva” ezt a lapozásra: valószínű, hogy a továbbiakban a mostanában behozott lapok kellenek, míg a régebben behozottak nem. Meg is van az alapötlet: tartsuk nyilván, hogy milyen sorrendben hoztuk be a lapokat, és lapcsere esetén a legrégebben behozottat cseréljük le.

Legrégebben használt (Last Recently Used - LRU)

Ezek után térjünk rá a már említett stratégia vizsgálatára. Vagyis azt tartsuk nyilván, hogy egy lapot mikor használtak, és azt a lapot cseréljük ki, amelyet a bent lévők közül a legrégebben használtunk utoljára. (Last Recently Used - LRU algoritmus.)

Ajánlott videó: