Ugrás a tartalomhoz

Operációs rendszerek

Dr. Fazekas Gábor (2011)

Kempelen Farkas Hallgatói Információs Központ

Virtuális memóriakezelési stratégiák

Virtuális memóriakezelési stratégiák

  • Behozási stratégia (Fetch Policy)

    • – azt határozza meg, mikor és mennyi lapot kell a memóriába betölteni

    • – Demand paging esetén csak akkor töltünk be egy lapot a főmemóriába, ha hivatkozás történik rá

      • a processzus első indításakor sok laphiba történik

    • – Prepaging a szükségesnél több lapot hoz be

      • hatékonyabb olyan lapokat behozni, melyek a diszken szomszédosak egymással

  • Elhelyezési stratégia (Placement Policy)

    • – meghatározza, hogy a valós memória mely részére tegyen egy adott processzus darabot

    • – szegmentáció esetén:

      • best-fit, next-fit, first-fit, ...

    • – lapozás esetén:

      • megfontolás nélkül ...

Áthelyezési stratégia (Replacement policy)

  • Keretzárolás (Frame locking)

    • – ha a keret zárolva van, tartalmát nem lehet kicserélni

    • – pl: egy operációs rendszer kernele

    • – vezérlőrendszerek

    • – I/O pufferek

    • – minden keretnek megfelel egy „zárolva” bit (lock bit)

  • Lapcserélési algoritmusok

    • – optimális stratégia

      • azt a lapot dobjuk ki, melyre való hivatkozás a jövőben a legkésőbb történne

      • lehetetlen implementálni: nem ismerhetjük a jövő eseményeit...

    • – legrégebben használt (Least Recently Used - LRU)

      • laphiba esetén a legrégebben használt lapot dobjuk ki

      • a lokalitási elvből következik, hogy annak valószínűsége, hogy erre a lapra a közeljövőben szükségünk lesz, a lehető legkisebb

      • minden lapot meg kell címkézni az utolsó rá való hivatkozás idejével

      • ennek hatékony implementálása nem egyszerű feladat!

    • first-in, first-out (FIFO)

      • a processzushoz tartozó kereteket körkörös pufferként kezeljük

      • a lapokat körkörösen (round-robin) dobjuk ki

      • ezt a stratégiát a legegyszerűbb megvalósítani

      • a memóriában legrégebb óta tartózkodó lap kerül kidobásra

      • Probléma: előfordulhat, hogy ezekre a lapokra nagyon hamar szükség lesz újból (v.ö. ciklusmag)

    • – "óra algoritmus" (második esély algoritmus)

      • bevezetünk egy jelző bitet minden laphoz (use bit)

      • amikor a lap betöltődik a memóriába, a use bit 0 értéket kap

      • a lapra való hivatkozás után a use bit 1 értéket kap

      • amikor lapot kell cserélni, az első olyan lap lesz dobva, melynek use bit értéke 0

      • a kicserélésre való keresés során minden 1 értékű use bit értékét 0-ra állítjuk

    • – lap pufferelés (Page buffering)

      • a kidobott lapok a következő listák egyikébe kerülnek felvételre

        • – nem módosított lapok listája

        • – módosított lapok listája

    • – mostanában nem használt (Not Recently Used – NRU)

      • – hivatkozás bit (reference bit - R), módosított bit (modified bit - M)

      • – óramegszakítás: R bit törlése periodikusan

      • – véletlenszerűen veszünk ki egy lapot a legalacsonyabb nemüres osztályból:

        • 0. osztály: nem mostanában hivatkozott, nem módosított

        • 1. osztály: nem mostanában hivatkozott, módosított

        • 2. osztály: mostanában hivatkozott, nem módosított

        • 3. osztály: mostanában hivatkozott, módosított

    • – nem gyakran használt (Not Frequently Used - NFU)

      • – hivatkozás bit (R) és szoftveres számlálók

      • – óramegszakítás: periódikusan hozzáadni az R (0 vagy 1) bitet a számlálóhoz

      • – a számlálók jelzik, hogy egy lap milyen gyakran kerül hivatkozásra

      • – laphiba esetén a legkisebb számlálóval rendelkező lapot választjuk ki cserére

      • – NFU és aging együtt jobb megoldás!

Rezidens készlet (szet) felügyelet

  • Rezidens szet mérete

    • – Fix kiosztású

      • a processzusok fix számú lapot kapnak

      • amikor egy laphiba történik, ezen processzus egyik lapja lesz cserélve

    • – Változtatható kiosztású

      • a processzusokhoz rendlet lapok száma a processzus élete során változik

  • Változtatható kiosztású, globális

    • – a legegyszerűbb megvalósítani, így a legtöbb operációs rendszer adoptálta

    • – az operációs rendszer egy listát tart a szabad keretekről

    • – laphiba esetén szabad keretet adunk a processzus rezidens szetjének

    • – ha nincs szabad keret, egy másik processzustól cserél egyet

  • Változtatható kiosztású, lokális

    • – új processzus esetén a keretek lefoglalása az alkalmazás típusától illetve más kritériumoktól függ

    • – laphiba esetén az okozó processzus rezidens szetjéből választunk lapot

    • – kiosztás újraértékelése időről időre

Tisztítási stratégia

  • A tisztítási stratégia feladata annak eldöntése, mikor szükséges egy módosított lapot a másodlagos tárra menteni

  • Igényelt tisztítás (demand cleaning)

    • – egy lap csak akkor lesz kiírva, amikor kiválasztjuk cserére

  • Előtisztítás (precleaning)

    • – lapok kimentése még mielőtt lapkeretjeikre szükség lenne, a lapok kiírása kötegekben (batch) történik

  • A legjobb közelítés: page buffering

    • – a kicserélt lapokat két listában helyezzük el

      • módosított lapok és nem módosított lapok

    • – a módosított listában lévő lapokat periodikusan kiírjuk és a nem módosított lapok listájába tesszük

    • – a nem módosított lapok listájában levő lapok hivatkozásuk esetén újra visszanyerhetők, vagy véglegesen elvesznek (törlődnek) ha a lapkeretüket egy másik lap kapja meg

Betöltésvezérlés

  • Betöltésvezérlés:

    • meghatározza azon processzusok számát, melyek a főmemóriába kerülnek

    • ha túl kevés processzus, túl sok alkalommal lesz minden processzus blokkolt és túl sok idő fog elmenni cserével (swapping)

    • túl sok processzus vergődéshez vezethet

  • Processzus felfüggesztése:

    • legkisebb prioritású processzust

    • hibázó processzust

      • – ezen processzusnak nincs működő része a főmemóriában, így úgyis blokkolva van

    • utolsó aktivált processzust

    • a legkisebb rezidens szettel rendelkező processzust

      • – ezen processzus újratöltése igényli a jövőben a legkisebb erőfeszítést

    • legnagyobb processzust

      • – a legtöbb szabad keretet igényli

    • legnagyobb hátralevő végrehajtási idővel rendelkező processzust