Lapozás (informatika)

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.

Lapozási stratégiák (lapcserélési algoritmusok)

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
• NRU

FIFO (First In First Out)

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 (Least Recently Used)

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 (Optimal)

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)

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)

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.