15. tétel Flashcards
(15 cards)
A tárkezelés korszerű módszerei
A teljesítményt egyik legjobban befolyásoló tényező a központi tár szervezése. A multiprogramozás és a programok méretének növekedése miatt a virtuális tárkezelés is szükséges. A címzési módok és a hardveres támogatás határozza meg, hogy egy operációs rendszer milyen tárkezelési sémát tud megvalósítani.
Tár hierarchia
Olyan hierarchikus rendszer, amely a leggyorsabb és legkisebb tároló kapacitású memóriától terjed a leglassabban betölthető és legnagyobb tároló kapacitású memóriáig.
1. CPU gyorsítótás
2. Operatív memória (RAM)
3. Háttértár
4. Egyéb külső tárak, I/O eszközök
Program-címek kötése és címleképezés
Logikai címtartománynak nevezzük a program saját címtartományát, melyet a program folytonosnak tekint (0-tól a program maximális címéig). Viszont a programok végrehajtása gyakorlatilag soha nem a nulladik fizikai címtől kezdve történik. A logikai és a fizikai címtartomány különbözik, a kettő között konverzió szükséges. Gyakran nem is folytonos a fizikai címtartomány.
Címleképezés: logikai (virtuális) címekhez tartozó fizikai címek meghatározása. A memóriamenedzsment egység (MMU) kezeli.
Logikai (virtuális) cím: az a memóriacím, amit a CPU generál.
Fizikai cím: a memória valós mérete.
A logikai és fizikai címek csak statikus címkötés esetén egyeznek meg, dinamikus címkötés esetén különböznek.
Címek kötésének lehetőségei:
* Statikus:
o Fordítás közben: a fordító a programhoz abszolút címeket rendel.
o Szerkesztés közben: a program több modulból áll, melyek hivatkoznak egymásra (logikai címek). A szerkesztő fizikailag egymás mögé helyezi a tárban és a logikai címeket fizikaivá alakítja.
o Betöltés közben: a fordítás eredményeképpen előállt áthelyezhető kód címhivatkozásait a betöltő program az aktuális címkiosztás szerint módosítja.
* Dinamikus:
o Futás közben: a program memóriaképe logikai címeket tartalmaz. A konkrét fizikai címet speciális hardver elemek csak az utasítás végrehajtásakor határozzák meg.
Dinamikus címleképezés módszerei
Két alapvető módszert különböztetünk meg dinamikus logikai-fizikai címleképezésnél:
* Bázis-relatív címzés: a program tetszőleges helyre betölthető. A bázisregisztert a betöltési kezdőcímre állítva a program végrehajtható.
* Utasításszámláló-relatív címzés: pozíció-független kód, csak pozíció-független virtuális címeket tartalmaz.
Egypartíciós rendszer
Az operációs rendszeren felüli folytonos címtartományt egy folyamat használja. A program az első szabad címre töltődik be. Ha az operációs rendszernek több tárra van szüksége, akkor azt vagy a program által nem használt területről lopja el, vagy a programot áthelyezi, ami hardver támogatás nélkül nehézkes. az operációs rendszer területének védelmére elegendő egy regiszter. Tárkezelő hardver figyeli, hogy minden hivatkozás a tárolt cím felett legyen. Rendszermódban ez a védelem kikapcsol és a teljes memória használható.
Többpartíciós rendszer
A multiprogramozás miatt egyszerre több folyamat tartózkodik a tárban. Erre lehetséges megoldások:
* Fix partíciós rendszerek: a korai rendszerekben az operációs rendszeren felüli tárterületet részekre osztották. A partíciók határa a rendszer futása alatt nem változhatott (rögzített partíciók). Ezek a rendszerek a tárterületet rosszul használják ki és a szervezés a tár belső tördelődéséhez vezet, melynek oka, hogy a folyamatok nem használják ki teljesen a rendelkezésükre álló területet.
- Változó méretű partíciós rendszerek: a partíció a program igényeinek megfelelő méretű. Nincs belső tördelődés, hiszen csak a szükséges memóriát kapják meg a folyamatok. A szabad terület viszont tördelődhet, melynek oka, hogy egy folyamat lefutásakor a használt memória felszabadul. Az operációs rendszer nyilvántartja ezeket a területeket, az egymás melletti szabad területeket pedig automatikusan összevonja. Sokszor ezek a területek nem szomszédosak, így a szabad memória kis részekre oszlik. Ezt nevezzük külső tördelődésnek.
Memória területek lefoglalása: stratégiák a külső tördelődés csökkentésére. Az operációs rendszer a szabad területek közül a következőképpen választhat:
* Legjobban megfelelő (best fit): a legkisebb, még elegendő méretű memóriát foglalja le.
* Első megfelelő (first fit): a kereséssel a tár elejétől indulunk, az első megfelelő méretűt lefoglaljuk.
* Következő megfelelő (next fit): a kereséssel az utoljára lefoglalt tartomány végéről indulunk, az első megfelelő méretűt lefoglaljuk.
* Legrosszabban illeszkedő (worst fit): a legnagyobb szabad területből foglaljuk le, abban bízva, hogy a nagy darabból fennmaradó terület más folyamat számára még elegendő lesz.
Tárcsere (swap)
Az operációs rendszer egy folyamat teljes tárterületét a háttértárra másolja, így szabadítva fel területeket más folyamatoknak. A preifériás átvitel miatt időigényes (több idő, mint egy környezetváltás). A háttértáron lévő változatlan tartományt már nem kell újra kiírni. felmerülő problémák lehetnek, hogy például melyik folyamatot tegyük ki, ha tárterületre van szükség, vagy melyik folyamatot hozzuk vissza, ha felszabadul tárterület. A felesleges pakolgatás kerülendő.
Szegmensszervezés
A program memóriája nem egybefüggő terület, önmagukban folytonos blokkok halmaza, amelyek tárbeli elhelyezkedése közömbös. A folyamat memóriája különböző méretű blokkokból (szegmensekből) áll. A szegmensek közötti kihasználatlan memóriaterületek miatt fellép a külső tördelődés veszélye.
A szegmens egy logikai egység. Ilyen például egy főprogram, eljárások, függvények, objektumok és változók.
Címtranszformáció: a virtuális címek <blokkcím, eltolás> alakúak. A transzformáció a blokktábla (szegmenstábla) segítségével történik. Minden folyamathoz külön blokktábla tartozik.
Védelem: minden szegmensre biztosítani kell, hogy a folyamat ne címezhessen ki belőle (az eltolás nem lehet nagyobb a szegmens méreténél). A szegmenstábla tartalmazza a szegmensek hosszát. A túlcímzést hardver figyeli és bekövetkeztekor megszakítást okoz.
Hozzáférés ellenőrzés: a folyamatoknak az egyes szegmensekhez különböző hozzáférési módokat engedélyezhetünk. Ez egyfajta védelmi mechanizmus. Ha valamelyik jogosultság megsérül, akkor az megszakítást okoz. Ilyen hozzáférési módok:
* Olvasási jog: a folyamat a szegmens területét olvashatja.
* Írási jog: a folyamat a szegmens területére írhat, az adatokat módosíthatja.
* Végrehajtási jog: a szegmensben gépi utasítások vannak, amelyeket a folyamat végrehajthat.
Osztott szegmenshasználat: több folyamat ugyanazt a szegmenst használja (közös utasítások és adatterület használata). A folyamatok szegmenstáblájában ugyanaz a fizikai szegmenscím szerepel (de a hozzáférési jogosultság lehet különböző).
Tárcsere: előfordulhat, hogy egy futó folyamatnak nincs minden szegmense a memóriában. A szegmenstábla minden szegmens mellett tartalmaz egy bitet, amely jelzi, hogy a szegmens a központi tárban van-e; ill. tartalmaz információt, hogy a háttértáron hol található az adott szegmens. Ha a folyamat egy háttértáron lévő szegmensre hivatkozik, akkor az megszakítást okoz, amit az operációs rendszernek kezelnie kell.
Lapszervezés
Lapszervezés esetén azonos méretű blokkokat (lap) használunk a külső tördelődés elkerülése érdekében. A belső tördelődés csökkentése miatt kis méretű lapokat használunk. A lap mérete gyakorlati szempontok miatt mindig 2 hatványa.
Címtranszformáció: a lapon belüli cím a fizikai cím kisebb helyiértékű bitjeit alkotja. Típusai:
* Közvetlen leképezés: a folyamathoz tartozó minden fizikai cím egy laptérkép táblában van. Kis lapméret miatt nagy méretű a tábla.
* Asszociatív leképezés: speciális gyors elérésű tár (asszociatív tár) segíti a címzést. A gyorsítótárban a várhatóan gyakran használt lapok címét tároljuk. A tár mérete itt sem elég nagy. A keresés párhuzamosan történik az összes tárolt logikai cím alapján. Találat esetén a találatnak megfelelő fizikai cím kerül a kimenetre.
* Kombinált technika: a fizikai lapcím keresése egyszerre kezdődik az asszociatív tárban és a direkt laptáblában. Ha az asszociatív tárban van találat, akkor a direkt keresés leáll. Környezetváltás esetén az asszociatív laptáblát is cserélni kell. Egy adott időszakban a teljes címtartomány kis része van kihasználva.
Védelem: lapon belüli túlcímzés ellen nem kell védekezni. Kivételt képez az utolsó lap, mert az nincs teljesen tele.
Hozzáférés ellenőrzés: a lapokhoz hozzáférést a túl nagy extra tárigény miatt (laponként legalább 3 bit) általában nem ellenőrzik.
Osztott laphasználat: hasonló az osztott szegmenshasználathoz. Több folyamat laptérkép táblája azonos fizikai címekre hivatkozhat. Mivel a lap mérete nem tükrözi a folyamatok logikai tárfelosztását, így a lapokon nem osztottan használható területek is lehetnek.
Tárcsere: itt is egy bit jelzi, hogy a memóriában van-e a lap vagy a háttértáron. Utóbbi esetben a tábla a háttértáron való elhelyezkedés információját is tárolja.
A virtuális tárkezelés alapjai
Olyan szervezési elvek, algoritmusok összessége, amelyek biztosítják, hogy a rendszer folyamatai logikai címtartományainak csak egy – a folyamat futásához szükséges – része legyen a központi tárban.
A virtuális tárkezelés szükségessége
A programok nem használják ki a teljes címtartományukat. Tartalmaznak ritkán használt kódrészleteket, a statikus adatszerkezetek általában túlméretezettek, a program futásához egy időben nem kell minden részlet, időben egymáshoz közeli utasítások és adatok általában a térben is egymáshoz közel helyezkednek el.
Nem célszerű az egész programot a tárban tartani. A programok méretét nem korlátozza a tár nagysága, a program nagyobb lehet, mint a ténylegesen meglévő memória mérete. A memóriában tartott folyamatok száma növelhető, a programok betöltéséhez és háttértárba mentéséhez kevesebb I/O művelet kell.
Alapvető kérdések a virtuális tárkezelésnél
- A betöltendő blokk (lap) kiválasztása:
o Igény szerinti lapozás:
▪ Előnye: egyszerű a lapot kiválasztani, a tárba csak a biztosan szükséges lapok kerülnek be.
▪ Hátránya: új lapokra való hivatkozás mindig laphibát okoz.
o Előre tekintő lapozás:
▪ Az operációs rendszer megpróbálja kitalálni, hogy a folyamatnak a jövőben melyik lapokra lesz szüksége és azokat szabad idejében betölti. Ha a jóslás gyors és pontos, akkor a futási sebesség jelentősen felgyorsul. Ha a döntés hibás, a felesleges lapok foglalják a tárat.
▪ A memória ára jelentősen csökken, így a mérete nő, a hibás döntés ára pedig egyre kisebb. - A behozott blokk a valós tárba hova kerüljön?
- Ha nincs hely, akkor melyik blokkot tegyük ki?
- Hogyan gazdálkodjunk a fizikai tárral, azaz egy folyamat számára hány lapot biztosítsunk?
Lapcsere stratégiák
A lapcsere akkor lenne optimális, ha azt a lapot választaná ki, amelyre legtovább nem lesz szükség. A lapcserét nagyban gyorsítja, ha a mentést csak akkor végezzük el, ha az a lap a betöltés óta módosult. A hardver minden lap mellett nyilvántartja, hogy a lapra írtak-e a betöltés óta.
Algoritmusok:
* Véletlen kiválasztás: egyszerű, buta algoritmus, csak elvi jelentőségű, gyakorlatban nem használják. Véletlenszerűen kiválaszt egy lapot, amit kitesz a háttértárra.
* Legrégebbi lap (FIFO): a tárban lévő legrégebbi lapot cseréli le, megvalósítása egy egyszerű FIFO listával történik. Hibája, hogy olyan lapot is kitesz, amit gyakran használnak.
* Újabb esély: a FIFO egy változata. Minden lap tartalmaz egy R hivatkozás bitet, ami kezdetben törölve van. A lapra hivatkozáskor R = 1. Ha a sor elején lévő lapon R = 0, akkor csere. Ha a sor elején lévő lapon R = 1, akkor az R bitet töröljük és a lapot a FIFO végére rakjuk. Így kiküszöböli a FIFO hibáját.
* Óra: az újabb esély algoritmus másik implementációja. a lapok körkörös láncban vannak felfűzve a betöltés sorrendjében. Lapcsere előtt az algoritmus megvizsgálja az R bitet. Ha 1-nek találja, akkor nem veszi ki a lapot, törli az R-t és a mutatót tovább lépteti.
* Legrégebben nem használt lap (LRU): azt a lapot választjuk, amelyre a leghosszabb ideje nem hivatkoztak. A múltbéli információk alapján próbál előre látni, az optimális algoritmust közelíteni.
* Legkevésbé / legritkábban használt lap (LFU): a leggyakrabban használt lapok a memóriában. Lap hivatkozásakor R = 1. Periodikusan minden lapnál egy számlálót növel, ha R = 1, majd törli az R-t. Lapcsere esetén a legkisebb számláló-értékű lapot dobja ki.
* mostanában nem használt lap: bevezet két új bitet: hivatkozott (R) és módosított (M) biteket. Az operációs rendszer időközben törli az R bitet, de az M bitet viszont őrzi. A módszer a legkisebb prioritásból választ véletlenszerűen. Négy prioritást különböztetünk meg:
1. Nem hivatkozott, nem módosult
2. Nem hivatkozott, módosult
3. Hivatkozott, nem módosult
4. Hivatkozott, módosult
Folyamatok lapigénye
Vergődés (thrashing): ha egy folyamat vagy rendszer több időt tölt lapozással, mint amennyit hasznosan dolgozik. Oka:
* Folyamat: kevés lap van a tárban, gyakran hivatkozik a háttértáron lévőkre.
* Rendszer: túl sok a folyamat, ezek egymás elől lopkodják el a lapokat, mindegyik folyamat vergődni kezd.
Vergődés elkerülése: a tárban lévő folyamatoknak biztosítani kell a futáshoz szükséges optimális számú lapot.
Lokalitás: a folyamatok egy időintervallumban csak címtartományuk szűk részét használják. Típusai:
* Időbeli: a hivatkozott címre a közeljövőben nagy valószínűséggel újra hivatkozni fog.
* Térbeli: hivatkozott címek egymás melletti címre történnek.
Munkahalmaz modell
a munkahalmaz az elmúlt ∆ időben (munkahalmaz ablak) hivatkozott lapok halmaza. A lokalitás miatt a folyamatnak nagy valószínűséggel ezekre a lapokra lesz szüksége a közeljövőben. A munkahalmaz mérete folyamatonként és időben is változik. Az operációs rendszer célja minden aktív folyamat számára biztosítani a munkahalmazt. A pontos méréshez bonyolult hardver kellene, ezért fix időintervallumonkénti mintavételezéssel oldják meg. Ha túl kicsi a munkahalmaz mérete, akkor nem tartalmazza az egész lokalitást. Ha túl nagy, akkor több lokalitást is tartalmaz feleslegesen.
Ha a munkahalmaz a memóriában van, akkor kicsi a laphibák gyakorisága. A munkahalmaz változásakor megnő a laphibák gyakorisága.
