kategória | ||||||||||
|
||||||||||
|
||
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 ***.
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.
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.
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.
Találat: 12392