Lapcserélő algoritmusok

NRU
- Minden laphoz R (hivatkozott) és M (módosított) bitek tartoznak.
- Adott időközönként nullázzuk az R bitet.
- 4 osztály:
  1. nem R, nem M
  2. nem R, M
  3. R, nem M
  4. R, M
- A legkisebb sorszámú nemüres osztályból választjuk ki véletlenszerűen az eldobandó lapot.

FIFO
- A lapok egy listában vannak. A lista elején a legkorábban, végén a legutóbb betett lap.
- Laphibánál a lista elején lévőt dobjuk el, és végéhez fűzzük az újat.

Second chance
- A lapok láncolt listába fűzve, mint a FIFO-nál.
- Ha az első (legkorábban betett) lap R bitje 0, kidobjuk.
- Ha az R bit 1, a lapot a lista végére tesszük és töröljük az R bitjét.

Clock (nincs megvalósítva)
- A lapok körkörös listában vannak.
- A mutató (az óráé) a legrégebben betett lapra mutat, laphibánál ezt a lapot vizsgáljuk.
- Ha az R bit 0, kidobjuk, ha nem, nullázzuk és léptetjük a mutatót.
- WSclock
  - Ha az R bit 0, de a lap benne van a munkahalmazban, nem dobjuk el.

LRU
- Láncolt lista: elején a legrégebben, végén a legutóbb használt lap.
- Minden memóriahivatkozásnál (!) a hivatkozott lapot a lista végére kell fűzni.
- Laphiba esetén a legelső lapot dobjuk ki.
- NFU
  - Minden laphoz tartozik egy számláló.
  - Adott időközönként megnézzük a memóriában lévő lapokat és minden lap R bitjét hozzáadjuk a számlálójához.
  - A legkisebb számlálójú lapot dobjuk el.
- Aging
  - Mint az előző, de:
  - Először a számlálót 1 bittel jobbra toljuk, majd R-t nem a jobb, hanem a baloldali bithez adjuk hozzá.

Random
- Arra szerintem tökéletes, hogy a többivel összehasonlítsuk. Egyes források szerint nem is a “leghatékonytalanabb” bizonyos adatszerkezeteknél.

LRU-2/LRU-K, ARC, CAR (nincsenek megvalósítva)
- Ezek további elég hatékony algoritmusok. Tulajdonképpen rendre az LRU, LRU és a Clock továbbfejlesztett változatai, valamint az ARC és a CAR is rokonok, tehát összehasonlitási célokból tökéletesen helytállnak.
- Források:

Provide feedback