Lapozás (informatika)

A Wikipédiából, a szabad enciklopédiából

Az operációs rendszerek témakörében a lapozás (paging) egy virtuális memóriát használó memóriakezelő módszer, melyet használva a számítógép az elsődleges memória adatait tárolja el a másodlagos memóriában (többnyire merevlemez), majd szükség esetén ezt visszaolvassa.

A logikai címtartományt azonos méretű egységekre bontjuk, ezeket hívjuk lapnak. Az ennek megfelelő egység a fizikai memóriában a lapkeret. A lapok és a lapkeret mérete mindig megegyező.

A lapozás fogalma a virtuális memória fogalmával szorosan összefügg, a virtuális címeket az MMU (Memory Management Unit) képezi le fizikai címekre. Ha egy program olyan lapra hivatkozik, ami nincs benne a memóriában, akkor laphiba történik, és az MMU egy megszakítással (interrupt) jelez az operációs rendszernek.[1]

Lapozási stratégiák (lapcserélési algoritmusok)[1][szerkesztés]

Az elsődleges memóriába csak korlátozott mennyiségű lapok férnek bele. Ha egy program olyan lapra hivatkozik, ami nincs benne a memóriában, akkor laphiba történik. A lapozási stratégiák célja, hogy a laphibák száma minimális legyen.

A lapozási stratégiák fajtái:

  • FIFO
  • LRU
  • OPT
  • SC
  • NUR

FIFO (First In First Out)[szerkesztés]

Előbb jött, előbb megy elv. Az operációs rendszer a lapokat bejövetelük szerinti sorrendben egy listában tárolja el. Laphiba esetén a hiányzó lapot a rendszer a lista végére szúrja be.

A lista elejére tehát a legrégebbi lap kerül, ami még belefér a memóriába, a legvégére pedig a legújabb lap kerül. Ha az erre a célra lefoglalt memória betelt, akkor új lap beszúrása esetén a lista elején lévő lap kiesik.

LRU (Last Recently Used)[szerkesztés]

Legutoljára használt algoritmus. A memóriában tárolt lapokat a FIFO-hoz hasonlóan egy listában tároljuk el. A lista végére kerül a legutoljára használt lap, a elejére pedig a legrégebben használt. Ennek megfelelően laphiba esetén az új lapot a rendszer a lista végére szúrja be.

Ez az algoritmus azon a megfigyelésen alapszik, hogy a legutóbb használt lapokra valószínűleg még szükség lesz. Az algoritmus hátránya az, hogy a listát minden egyes memóriahivatkozás után frissíteni kell.

OPT (Opitma)[szerkesztés]

Elméleti megoldás, gyakorlatban nem lehet megvalósítani. Feltételezi hogy tudjuk hogy a jövőben melyik lapra lesz legkésőbb szükségünk, és annak a helyére ír.

SC (Second Chance)[szerkesztés]

a FIFO elvet használjuk, azzal a kiegészítéssel, hogy bevezetünk egy hivatkozásbitet amely arra utal, hogy ezt a lapot mikor használtuk. Tulajdonképpen nem első kiválasztásnál cseréljük le a lapot hanem csak a másodiknál.

NRU (Not Recently Used)[szerkesztés]

Az operációs rendszer minden laphoz rendel két állapotbitet: Az R bit (hivatkozott bit) minden írás vagy olvasás esetén 1-re állítódik, az M bit (módosított bit) csak írás hatására lesz 1. Ezeket a biteket a számítógép minden hivatkozás után hardveresen frissíti.

A állapotbitek alapján a lapokat négy osztályra oszthatjuk:

  1. nem hivatkozott, nem módosított
  2. nem hivatkozott, módosított.
  3. hivatkozott, nem módosított.
  4. hivatkozott, módosított.

Az NRU a fönti csoportokból a legkisebb sorszámú osztályból véletlenszerűen kiválasztva dob ki egy lapot, ha laphiba esetén a memória tele van.

A "nem hivatkozott, módosított" osztály akkor fordulhat elő, ha óramegszakítás történt. Ekkor ugyanis az R bit nullázódik, de az M bit nem.

  1. ^ a b Andrew S. Tanenbaum: Operációs rendszerek