Memóriakezelés (Memory management)

Nyíregyházi Főiskola Matematika és Informatika Intézete

05

Memóriakezelés (Memory management)  Háttér, alapok  Logikai és fizikai címtér  Valós címzésű menedzselés  Partíciók  Szabad/foglalt partíciók kezelése

Dr. Bajalinov Erik

Operációs rendszerek (PMB1206)

1


05

Háttér, alapok Az számítógép (processzor) kapacitásának jobb kihasználása megköveteli, hogy egyszerre több processzus osztozzon a memórián (shared memory). Egy program alapvetően valamilyen (bináris végrehajtható) fájl formában helyezkedik el a háttértárban. Végrehajtáshoz be kell tölteni a memóriába. Bár a gépek egyre nagyobb központi memóriával rendelkeznek, a memóriával mindenképp gazdálkodni kell mert az alkalmazások is és az operációs rendszer magja is egyre nagyobb memóriát igényelnek. Parkinson törvénye: "Programs expand to fill the memory aviable to hold them". Végrehajtás közben – a memóriakezelési stratégiától függően – többször mozoghat a memória és háttértár között. Memory – Cache (drága, kevés)+ RAM (kevésbé drága, több) + disk storage (olcsó, sok)

Dr. Bajalinov Erik


2


05

Input queue – a végrehajtásra kijelölt és evégett sorban álló programok együttese. A programkódhoz és a program változókhoz valamikor memória címeket kell rendelni (address binding). Ez történhet a betöltés előtt, közben, vagy akár utána is: Fordítási időben történő tárfoglalás (címkapcsolás). Betöltési (szerkesztési) időben történő tárfoglalás (címkapcsolás). Futási időben történő tárfoglalás (címkapcsolás). A memória (RAM) címekkel rendelkező rekeszek (bájtok, szavak) készlete. A memória celláknak van címe, a címek készlete a címtartomány (address space). Egy cím csakis egy címtartomány elemét veheti fel. Megkülönböztethetünk fizikai címtartományokat (physical address space) és logikai címtartományokat (logical address space). A fizikai (vagy valós) címtartományok elemei olyan címek, amik kiadhatók a buszra, a fizikai memóriacellák címei alkotják a készletet. Az instrukciókban szereplő címek készlete a logikai címtartomány.

Dr. Bajalinov Erik


3


05

Egy felhasználói program feldolgozásának lépései

Dr. Bajalinov Erik


4


05

A címkötődés (Address Binding) Programjaink több lépcsőn mennek át fejlesztésük során, ebből következően több címkötődési eset lehetséges. A lépcsők: a fordítás (compilation), a taszképítés (link), a betöltés (load) és a végrehajtás (run), bármelyikben történhet a címkötődés. • Kötődés a fordítás során: abszolút cím generálódik már a tárgymodulokban. Ha itt nincs kötődés, akkor a tárgymodulokban relatív címek generálódnak. • Kötődés a taszképítés során: abszolút címek generálódnak a végrehajtható modulokban (executable files), különben azokban relatív címek vannak. Ha relatív címek vannak, akkor a program áthelyezhető (relocatable). Egy fajta relatív cím a virtuális cím (lásd később).

Dr. Bajalinov Erik


5


05

• Kötődés a betöltés során: a végrehajtható programfájlban relokálható címek a betöltés során "átíródnak", és abszolút címekké válnak. Ha nincs kötődés a betöltés során, akkor a folyamat kódszegmensének címei még mindig relatív címek (pl. virtuális címek). • Kötődés a futás során, dinamikus a kötődés. A processz kódjában az instrukciók ún. logikai címeket tartalmaznak. A logikai cím lehet relatív cím, virtuális cím. A CPU tehát logikai címet kap feldolgozásra, ezeket átképzi fizikai címekké és ez adható ki a buszra. Az operációs rendszerek magjának fontos része a Memória Menedzselő Alrendszer (Memory Management System, Memory Management Unit), A memóriamenedzselő alrendszernek két nagyobb, jól megkülönböztethető feladatosztálya van:

Dr. Bajalinov Erik


6


05

 Az egyik a memória allokálás feladatköre. Ez lehet statikus (egy processz keletkezésekor címtartományt és memóriát kell biztosítani), vagy dinamikus (a processz futása során további memóriát igényel, ami természetesen címtartomány bővítéssel járhat). A memória allokálása a mai rendszerekben – kisöprési-kilapozási területek biztosításával és leképzési táblák létrehozásával (bővítésével) járnak.  A másik feladatkör a címleképzés (a címkötődés) segítése. Ez a feladatkör különösen a dinamikus címkötődéses rendszereknél – a mai virtuális címzésű rendszereknél feltétlenül fontos. A címleképzés a logikai (virtuális) cím “átalakítása” valós címmé, közben ki- és besöprési, ki- és belapozási alfeladatok merülhetnek fel. Különböző memóriamenedzselő sémák lehetségesek. Ezek együtt fejlődtek a hardver- és szoftver-fejlődéssel.

Dr. Bajalinov Erik


7


05

Memóriamenedzsment osztályok Több szempont szerint is osztályozhatunk. Egyik osztályozás szerint vannak olyan memóriamenedzselő rendszerek, melyek  mozgatják a processzek kontextusát (vagy annak egy részét) a fő memória és a másodlagos memória (HDD) között: ki-belapozó rendszerek; ki-besöprő rendszerek;  nem mozgatják a kontextusokat.

További osztályozás szerint lehetnek: 1. Valós címzésű rendszerek, ezen belül mono-programozású, multi-programozású rendszerek, ezen belül - fix partíciós, - változó partíciós rendszerek; 2. Virtuális címzésű rendszerek, ezen belül - lapozós (paging) rendszerek, - szegmens-leképző, ki-besöprő rendszerek,

- szegmentáló, ki-besöprő és ugyanakkor lapozó rendszerek. Dr. Bajalinov Erik


8


05

Nézzünk ezekre tipikus példákat, közben magyarázva a lényeget is.

Valós címzésű rendszerek

Mono-programozás. A legegyszerűbb séma. Egy időben egy processz (vagy folyamat, taszk, job) van a memóriában és az elfoglalhatja az operációs rendszer moduljai mellett (fölött, alatt, között) a teljes memóriát. A program fejlesztése során a fordító-taszképítő (compiler-linker) valós címeket generál, a cím és memóriakötődés történhet bármelyik fázisban. MS-DOS. A *.COM fájloknál a kötődés a betöltés során, a *.EXE fájloknál futás során történik.

Dr. Bajalinov Erik


9


05

Multi-programozás fix méretű partíciókkal (IBM OS/MFT). MFT – Multiprogramming with Fixed number of Tasks

Fix méretű partíciókban, szeparált input sorokkal ((a) ábra). A memóriának az operációs rendszer által el nem foglalt részét fix méretű részekre, partíciókra osztották. Mindegyik partíciónak saját input sora volt, a programokat (jobokat) az egyes partíciókba kellett fordítani-linkelni. A programozó tehát tudta, hogy milyen címen kezdődik és meddig tart egy-egy partíció, a compiler-linker csakis a partícióba tartozó címeket generál. Dr. Bajalinov Erik


10


05

Valós címzés fix partíciókkal, közös input sorral ((b) ábra).

A szeparált input sorokat használó rendszer hátránya volt, hogy maradhattak üres partíciók. Ezt lehetett elkerülni egyetlen közös input sor használatával. Bármelyik partíció kiürülve azonnal fogadhatta a következő munkát, ami még belefért. Problémák: Áthelyezés (relocation) – kellett automatizálni. Megoldás: A fordító-taszképítő (compiler-linker) eltolás címeket (offset) generált, melyek a program 0 kezdő címétől számítódtak.

Dr. Bajalinov Erik


11


05

A végleges címet előállíthatták ezek után két módon is: egyik szerint a program betöltése (load) során minden címet átírtak az eltolás értékhez hozzáadva a partíció kezdőcímét, így előálltak a betöltött programban a partícióhoz tartozó címek. Másik megoldás szerint - mikor is minden címzés egy szegmens-regiszter és egy eltolás értékből adódik -, a betöltés során nem változtatták meg a címeket, hanem a partíció kezdőcímét betöltötték a szegmens-regiszterbe. Futás során így is a partícióhoz tartozó címek keletkezhettek. Védelem (protection) – hogyan lehet ellenőrizni, hogy egy-egy program ki ne címezzen a partíciójából. A betöltés során a címeket átíró módszer esetén az átírással egyidőben lehetett ellenőrizni minden címzést. A szegmens-regiszteres címzéses megoldáshoz más ellenőrzés kellett. Kétféle ellenőrzési módszer is bevált. Egyik szerint a partíció-határok címeit regiszterekben tartva minden címzés ellenőrződött, vajon e két határ közé esik-e. Vegyük észre, hogy ez dinamikus jellegű, a gépi instrukciók végrehajtása közben történik az ellenőrzés. Másik megoldás szerint ilyen volt a híres IBM 360-as rendszer - a memória minden 2 blokkja kapott 4 bites védelmi kódot, ugyanakkor a PSW-ben (Program Status Word, 64 bites) is volt 4 bites védelmi kód (protection key).

Dr. Bajalinov Erik


12


05

PSW struktúra:

Protection key

Ha a címzés során e két kód nem egyezett, bekövetkezett a címzés védelem megsértése kivételes esemény.

Dr. Bajalinov Erik


13


05

Multi-programozás változó méretű partíciókkal (CDC Cyber supercomputer, MS-DOS). Control Data Corporation, 1970-1980.

Lényeg: a fordító-taszképítő valós, eltolás (offset) címeket generál (kötődés itt még nincs), a rendszer memóriáját azonban nem osztjuk fel előre partíciókra. Az input sorba került munkák a szabad területről, vagy a már korábban kialakult, a rendszer élete során dinamikusan változó méretű partíciókból igényelnek memória partíciókat. Vannak tehát "szabad" partíciók, és vannak foglaltak. Az ábrán A, B, C és D különböző méretű munkáknak megfelelően történik a memória partíciónálása (kötődés a betöltés vagy a futás során történhet). Dr. Bajalinov Erik


14


05

Problémák:  Relokáció (áthelyezés) és védelem (protection).  A munkák helyigényét előre meg kell mondani, hogy ellenőrizhető legyen, befér-e egy - egy nem használt "partícióba."  Valamilyen stratégia kell az elhelyezésre, ha több üres helyre is befér a munka.  Idővel szegmentálódik a memória. Szükség van az üres szomszédos szegmensek összevonására, időnként pedig az összes üres terület egyetlen területre való összevonására: a Memory Compression-ra. Az elhelyezés (relocation) stratégiák a következők lehetnek:  First Fit (Next Fit) stratégia.  Best Fit stratégia.  Worts Fit stratégia.

Dr. Bajalinov Erik


15


05

A best fit stratégia lényege: a soron következő munka abba a szabad memória partícióba kerül, amibe a legkisebb veszteséggel befér. Az elgondolás mögötte az, hogy így lesz a legkisebb a veszteség. Érdekes tapasztalat volt azonban, hogy az elgondolás nem ad jó eredményeket. Kikeresni a szabad területek láncolt listáján a „legjobban passzoló” területet idő-igényes, ugyanakkor a memória szegmentálódik, keletkeznek benne kisméretű szabad partíciók, amikbe később nem is lehet semmit tölteni, csakis memória összevonás (compression) után használhatók: éppen az ellenkezőjét érjük el, mint amit akartunk, lesz veszteség. A worst fit stratégia szerint szintén végig kell keresni az összes szabad területet, és abba kell betölteni a munkát, amiben a "legtágasabban" fér el. Időigényes ugyan a keresés, de kevésbé szegmentálódik a memória, nem lesznek nagyon kicsi üres szegmensek. Egész jó eredményeket szolgáltat a first fit, és még jobb a next fit stratégia: az első (vagy az előző alkalommal megkeresett partíciótól kezdve) szabad területre töltsük a munkát, amibe belefér. Elmarad az időigényes keresés és tapasztalatok szerint nem szegmentálódik túlságosan a memória. A stratégiák minősítése függ attól, hogy milyen módszerekkel tartják nyilván a memória foglaltságot. Elvileg ez lehet bit térképes, vagy láncolt listás. Az utóbbi volt az elterjedt. Dr. Bajalinov Erik


16


05

Partíciók kezelése - Bit-térképek (bit-maps), láncolt listák (linkes lists) Allocation unit

Foglalási egység (allocation unit) – néhány byte-tól néhány kilobyte-ig. „P”- process, „H”-hole (lyuk). (C) ábrán foglalt és szabad partíciók kezelése egy közös listában történik. Alternatíva: két külön lista – szabad és foglalt. Kiszabadult partíció kezelése költséges, viszont a folyamat indításához szükséges partíció megkeresése gyors. Dr. Bajalinov Erik


17


05

Általános esetben egy X folyamatnak két szomszédja van: A és B. Akkor a következő négy lehetséges szituáció fordulhat elő:

Memória kompresszió szükséges B, C, és D esetben

Dr. Bajalinov Erik


18


05

Példa

Dr. Bajalinov Erik


19

Memóriakezelés (Memory management)

Recommend Documents