Memóriagazdalkodas

Memóriagazdálkodás

Az op. rendszer része a memóriakezelő, amely a memóriagazdálkodást végzi.

Memóriakezelő algoritmusok két csoportja:

Végrehajtás közben mozgatják a programrészeket a memória és a lemez között. 919b16j (lapozás, szegmentálás)

Nem mozgatnak.

Egy program futtatása

Egyszerre csak egy programot futtat az op. rendszer a memóriát megosztva az op. rendszer és a program között.

Három fajtája:

Az utóbbi modell használatos az MS-DOS-ban az eszközmeghajtók a BIOS részei a ROM-ban találhatóak.

Multiprogramozás rögzített méretű partíciókkal

Több programot futtat egyszerre, melyeket a memóriában kezel. A memóriát 4 db partícióra osztja, melyek mérete lehet eltérő, de állandó. Az új programot abba a legkisebb partícióba rakja az op. rendszer, amelyikbe belefér. A partíció nem használt része elvész.

Ezt az OS/360 op. rendszer használta az IBM ***.

I.        Csere

A programokat mozgatja a memória és a lemez között, de az egész programot!

Példa:

A partíciók száma és mérete dinamikusan változik.

A,D,E,F ábráknál a lukakat memóriatömörítéssel be lehet foltozni. (ezt ritkán használják, mert időigényes)

Probléma, hogy a program adatszegmense változhat, így egy program memóriaigénye változhat a futás alatt.

Ilyen esetben:

Kirak pár programot a lemezre, hogy legyen hely az adatoknak

Ha van a program mellett egy kis hely, az adatot oda rakhatja.

A programot helyezi át egy nagyobb szabad területre.

Ha már túl nagy a program, akkor várakoztatja, vagy megszakíthatja.

A növekedést számításba veszi, és már az elején foglal helyet erre a célra.

Verem és adatszegmens lefoglalása

Verembe rakja a változókat és címeket, az adatokat pedig adatszegmensbe.

A memóriahasználat nyilvántartására két módszer van:

Bittérképpel

Láncolt listával

Bittérkép

A memóriát allokációs egységekre osztják, és minden egységhez tartozik egy bit, amely 1-es ha az egység foglalt, és 0 ha az egység szabad.

Fontos az allokációs egységek mérete, hiszen ha túl kicsik, akkor a bittérkép túl nagy lesz. Ha túl nagy akkor a programok miatt jelentős memória nem lesz használva, hiszen a program nem tölti ki az allokációs egységet, a bittérkép viszont foglaltságot jelez.

Probléma k allokációt igénylő program elhelyezése, ami k 0 bit keresése összefüggően a bittérképen. Ez viszont időigényes.

Memóriakezelés láncolt listával

A lista minden eleme tartalmazza a következőket:

Programot tartalmaz e a lista, vagy üres.

A kezdőcímet és a hosszt, valamint a következő listaelem címét.

Példa:

Ez a lista kezdőcím szerint növekvő sorrendbe van rendezve.

Ezen belül számos memóriafoglalási algoritmus ismert:

First Fit: az első megfelelő méretű lukat keresi meg

Best Fit: az egész listát végignézi, és a legkisebb lukat keresi meg.

Worst Fit: a legnagyobb méretű lukat keresi meg

Quiet Fit: a gyakran használt méretekhez külön listát társít, így könnyen elhelyezhető egy adott méretű program.

II.      Virtuális memória

Manapság a programok már nem férnek bele a memóriába. Az op. rendszer csak a program éppen használt részét tartja a memóriában. Multiprogramozás esetében is működik ez a módszer.

Lapozás

Virtuális memóriát fizikai memóriába képezik bele, ami kisebb, mint a virtuális memória.

MMU (Memory Management Unit) végzi a virtuális címek fizikaira képezését.

A virtuális címteret lapokra osztja, melynek képe a fizikai memóriában a lapkeret.

MOVE REG, 0 utasítás hatására a 0. lapon levő értéket veszi, ami a 2-es fizikai lapkeretre mutat. (0-ás lap 0-4 095-ig terjedő memóriatartományt öleli fel)

A 2-es lapkeret fizikai címe 8192-12 287-ig terjedő fizikai cím, tehát az MMU erre a címre képezi le ezt a tartományt.

A jelenlét/hiány bit jelzi, hogy az adott virtuális cím leképezhető e vagy sem. (ezt az ábra x-el jelzi, ha nem.)

Ha egy olyan laphivatkozás történik (MOV REG, 32 780), amely nem betölthető, akkor laphiba megszakítás keletkezik. Az op. rendszer vesz egy lapkeretet, kiírja a lemezre, beírja a helyére a hivatkozott lapot, frissíti a laptérképet, majd folytatja a program végrehajtását.

Laptábla:

Olyan függvény, ami a virtuális lapszámból visszaadja a lapkeret számát.

Ez rendszerint a memóriában található, de létezik többszintű laptábla, amelynek csak egy része található a memóriában.

Lapcserélési algoritmusok

Laphiba esetén el kell dönteni, hogy milyen lapok kerüljenek ki, és melyek kerüljenek be a fizikai memóriába.

Optimális lapcserélési algoritmus

Minden bent lévő laphoz hozzárendelünk egy számot, aszerint, hogy hány utasítás múlva lesz az első hivatkozás rájuk. Az a lap kerüljön ki, amelyik a legnagyobb számot birtokolja. Problémája ennek az algoritmusnak, hogy megvalósíthatatlan.

NRU algoritmus

Minden laphoz két állapotbitet rendelünk:

R (olvasáskor és íráskor 1-re állítódik)

M (csak íráskor lesz 1-re állítva)

Egy program elindításakor minden lapjának mindkét bitjét 0-ra állítja. Időnként (pl. megszakításonként) nullázzuk az R bitet azoknál, amelyekre nem történt hivatkozás az utóbbi időben.

Laphiba esetén R és M segítségével az op. rendszer 4 csoportot alkot:

R M

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

1. Nem hivatkozott, módosított 0 1

2. Hivatkozott, nem módosított 1 0

3. Hivatkozott, módosított 1 1

Az algoritmus a legkisebb sorszámú nem üres osztályból választ egy elemet véletlenszerűen, azt rakja ki.

FIFO algoritmus (First In First Out)

Legelőször berakott lapot rakja ki, mivel ez van a legrégebben a memóriájában. Ez az algoritmus nem igazán hatékony, ezért önmagában ritkán alkalmazzák.

Második lehetőség algoritmus

A legrégebbi lap R bitjét megvizsgáljuk, ha az 0, akkor kidobjuk, ha egy töröljük a bitet, és a lista végére rakjuk, és vesszük a következő lapot.

Óra lapcserélési algoritmus

Az óra mindig a legrégebbi lapra mutat. Ha laphiba történik, akkor megvizsgáljuk az R bitjét. Ha 0, akkor kidobjuk a lapot, ha 1, akkor nullázzuk az R bitjét. Ezután léptetjük az órát, amíg nem találunk olyan lapot, melynek az R bitje 0. ezt dobjuk ki, ide hozunk be új lapot és léptetjük az órát.

LRU algoritmus (Last Recent Used)

Amikor laphiba történik, akkor a legrégebben nem használt lapot dobjuk ki.

Megvalósítása igen drága: a lapokból láncolt listát készítünk, és egy hivatkozásnál frissítjük a láncot és a végén lesznek a legrégebben használt, az elején a legutoljára használt lapok. Megvalósítása inkább hardveresen történik.

Szoftveres megvalósításához minden laphoz rendelnek egy számlálót, ami kezdetben 0. minden óramegszakításnál a lap R bitjét hozzáadja a számlálóhoz. Laphiba esetén a legkisebb számlálójú lapot dobjuk ki.