Virtuális memória
1
Problémák • Lehet hogy a program nem fér be a memóriába • Mozgatás diszkre és vissza • A programok lokalitásának elve – A program rövid idő alatt csak kis részét használja a memóriának
• Biztonság – A program nem nyúlhat ki a partíciójából
• Kezdetben nem tudhatjuk mennyi memória kell – Dinamikus foglalás 2
Megoldás • A processzusok által látott memória terület különbözik a fizikailag létező memóriától • Követelmények – Minden program csak a saját memória területét látja, mintha az egész az övé volna – Bármely címre lehet hivatkozni a saját területen belül – A program ne vegyen észre semmit a megvalósításból – A virtuális memória elérésének hatékonysága ne legyen rosszabb mint a fizikai memóriához való hozzáférés hatékonysága 3
Lapozás (paging) • A virtuális és fizikai memóriát egyenlő darabokra osztjuk fel – Virtuális memóriában: lap (page) – Fizikai memóriában: lapkeret (frame)
• A keretek száma kisebb mint a lapoké • Egy lappal csak akkor tudunk dolgozni, ha keretbe helyezzük 4
Lapozás • 0-64K a virtuális címek • A gépnek csak 32K memóriája van • Csak a szükséges részek töltődnek be • 4K a lapméret • A valós rendszerekben a lapméret 512 byte, 1K, 4K (2 hatványa)
5
Lapozás • Vannak lapok melyek nincsennek a fizikai memóriában • Jelölés: jelenlét/hiány bit • Mi lesz ha olyan címre hivatkozunk, mely egy be nem töltött lapon van? MOV REG, 32780
6
Lapozás MOV REG, 32780 • Az MMU észleli a problémát és laphiba megszakítást generál az operációs rendszernek! • Az operációs rendszer egy lapkeretet kiír a lemezre • Betölti a kívánt lapot • Módosítja a laptérképet a szükséges módon • A megszakítást okozó utasítástól folytatja. 7
Lapozás • • • •
Nincs külső töredezettség Kicsi belső töredezettség Támogatja a megosztást Lehetővé teszi hogy a memória fizikai felépítésétől elvonatkoztassunk – A programozó csak a virtuális címmel foglalkozik
8
MMU CPU kártya CPU Memória MMU
• MMU
Lemez vezérlő
Adat sín
– Memory Management Unit – A virtuális címeket fizikai címekké alakítja 9
Címfordítás • CPU által generált cím: – Lapszám (p) • a laptábla indexe, amely a fizikai memória címet tartalmazza • ez a bázis cím
– Lap offszet (d) • a fizikai memória címmel kombinálva kapjuk a végleges címet
10
Címfordítás Szám Bit
p m-n
d n
2m címtartomány és 2n lapméret esetén Címtartomány: 216 = 65535
64K
Lapméret: 212 = 4096
4K
Lapok száma: 216-12 = 24 = 16
11
MMU működése Kimenő fizikai cím (24580)
• 16 db 4K lap esetén • 4 bit: lapszám (24 = 16) • 12 bit: offszet (eltolás), 212 = 4096 címet reprezentálhat • Ezért használunk 2 hatványa lapméretet
Virtuális lap számát a laptábla indexeként használjuk
12 bites eltolás közvetlenül másolódik
Lap tábla
Jelenlét bit
MMU Bejövő virtuális cím 12(8196)
MMU működése, másképpen
13
Laptábla • A laptábla célja hogy a lapokat lapkeretekre képezzük le • Lényegében egy függvény – argumentuma: a virtuális lapszám – eredmény: a lapkeret száma
• Két probléma: – A laptábla nagyon nagy lehet – A leképezés gyors legyen 14
A laptábla nagyon nagy lehet 2m címtartomány és 2n lapméret esetén Címtartomány: 232 = 4 294 967 296
4 GB
Lapméret: 212 = 4096
4 KB
Lapok száma: 232-12 = 24 = 1 048 576 Több mint 1 millió lap, melyekhez bejegyzés kell Minden processzusnak saját laptáblája van!! 64 bit esetén még több 15
A leképezés gyors legyen • Minden memóriahivatkozásnál végre kell hajtani a címfordítást • Egy utasítás több memóriahivatkozást is eredményezhet
16
Laptábla: Gyors hardware regiszterekből álló tömb • Amikor egy processzus elindul, a rendszer betölti a memóriából a processzus laptábláját a regiszterekbe – Előny • Legegyszerűbb • Leképezés alatt nem kell a memóriához fordulni
– Hátrány • Processzus váltásnál a laptábla regisztrekbe töltése csökkenti a teljesítményt 17
Teljes laptábla a memóriában • Egy regiszter mutat a laptáblára • Processzus váltásnál csak egy regisztert kell átírni • Hátrány – Minden utasításnál több memóriahivatkozás
18
Kétszintű laptábla 32 bites cím, két darab 10 bites mezőből és 12 bites offszetből áll.
Második szintű laptábla
Felső szintű laptábla
Jelenlét bit 0 lapok 19
Kétszintű laptábla, címfordítás
Felső szintű laptábla Második szintű laptábla
20
Laptábla bejegyzés Gyorsítótár Módosított Jelenlét/hiány bit letíltás Lapkeret száma Hivatkozott
Védelmi bitek
Módosított bit: ha írtunk a lapra értéke 1 lesz, ha értéke 0 nem kell kiírni a lemezre (dirty bit) Hivatkozott bit: ha olvastunk vagy írtunk értéke 1 lesz; segít ha egy lapot ki kell dobni, akkor a használtat nem választjuk 21
TLB • A laptáblákat a memóriában tartjuk – Sajnos nagyban befolyásolja a teljesítményt
• Hivatkozáslokalitás – A legtöbb hivatkozás a lapok egy kis számára vonatkozik
• Megoldás: – Hardware eszköz – Translation Lookaside Buffer (címfordítási gyorsítótár)
22
TLB • 8 - 64 bejegyzést tud tárolni • MMU először a TLB-ben keresi a lapot, egyidejűleg (párhuzamosan)! – Ha a művelet nem sérti a védelmet, azonnal kapjuk a lapkeret címet – Ha sérti, védelmi hiba
23
TLB • Lapszám nincs a TLB-ben – Laptáblából keresi ki a táblát – TLB-ből kidob egy bejegyzést • Módosított bitet vissza kell írni a laptáblába
– Betölti a TLB-be az új lapot • Minden adatot felül kell írni a TLB-ben
24
MMU működése TLB-vel
25
Szoftveres TLB • Modern rendszereknél a TLB feltöltése szintén az operációs rendszer része – SPARC MIPS, HP PA, Power PC
• Ha egy lap nincs a TLB-ben, TLB hiba generálódik és az operációs rendszer kapja meg a vezérlést • Nagyon kevés utasítással szabad végrehajtani! – TLB hiba gyakoribb mint lap hiba
• Sokféla módszerrel javítható a működése 26
Invertált laptáblák • 32 bites cím, 4KB lapok – Több mint 1 millió bejegyzés – Laptábla kb 4MB-os
• 64 bites cím, 4KB lapok – Több mint 1052 bejegyzés – Egy bejegyzés 8 byte – A laptábla kb. 30 millió GB!!!
27
Invertált laptáblák • A valós tár minden lapkeretéhez tartozik egy bejegyzés – 64 bites címtér, 4 KB lapméret, 256 MB RAM • Csak 65 536 bejegyzés kell
• Nehezebb a virtuálisról a fizikai címre való fordítás • pid processzus p lapja – pid nem használható indexként – Az (pid,p) párost kell megkeresni a laptáblában 28
Invertált laptáblák
Nem hatékony keresés, legrosszabb esetben O(n)
29
Invertált laptáblák • Itt is segíthet a TLB !!! Vagy • Keresésre használható hasító (hash) tábla – Egy bejegyzés egy láncolt listát tartalmaz kulcs ütközés megoldására
30
Valós rendszerek • • • • •
Pentium: 2 szintű laptábla Pentium 4: 3 szintű laptábla AMD64: 4 szintű laptábla UltraSPARC: 3 szintű laptábla IBM RS/6000, PowerPC: invertált laptábla
31
fork, Copy-On-Write, COW • fork: Processzus létrehozására használtuk – Lemásolta a processzust, majd rögtön felülírtuk (execve) • Nem hatékony
– Megoldás: • Processzus összes lapját olvashatóra állítjuk • Új processzus lapjait ugyanazokra a lapkeretekre képezzük, szintén csak olvashatóan • Ha valamelyik processzus írni próbál egyik lapjára, kivétel generálódik és ekkor másolunk 32
COW, C lap módosítása előtt Processzus 1
Fizikai memória
Processzus 2
A Lap B Lap C Lap
33
COW, C lap módosítása után Processzus 1
Fizikai memória
Processzus 2
A Lap B Lap C Lap C’ Lap
34
Laphiba • Igény szerinti lapozás (demand paging) – Egy lap csak akkor töltődik be amikor szükség van rá • • • •
A processzus nincs a memóriában Első utasítás, rögtön laphibát generál, és behozza a lapot Gyors további laphibák (verem, globális változók) Egy idő múlva minden szükséges lap a memóriában lesz
• Lap betöltés – Ha referencia mutat a lapra • Érvénytelen referencia >> abort • Nincs a memóriában >> betöltés 35
Laphiba, lemezre írás-beolvasás
36
Érvényes-érvénytelen bit • Minden laptábla bejegyzés tartalmaz egy bitet – v: memóriában – i: nincs a memóriában (érvénytelen, invalid) Keret #
érvényes - érvénytelen bit
v v v v i ….
Ha címfordítás során a bit „i” akkor laphiba generálódik
i i laptábla 37
Érvényes-érvénytelen bit
38
Laphiba, lépések 1.
Utasítás egy új lapra hivatkozik
2.
Megszakítás, operációs rendszer meghívódik
3.
Lap a lemezen
4.
Lap betöltése egy üres keretbe
5.
Laptábla beállítása •
6.
i-ről v-re
Utasítás ismételt végrehajtása !!!!!
39
Laphiba • Nincs üres lapkeret – Ki kell dobni egy lapot • Ha gyakran használt lapot dobunk ki, hamar vissza kell tölteni
– Melyiket dobjuk ki? – A megoldás mindig erőforrásigényes így minnél kevesebbszer szeretnénk végrehajtani
40
Lapcserélési algoritmusok • Sokféle eljárás létezik • A probléma felmerül a gyorsítótárak esetén is • A lehető legkevesebb laphibát akarunk
41
First-In-First-Out (FIFO) algoritmus 3 lapkeret esetén Kívánt lap: 1
2
3
4
1
2
5
1
2
3
4
5
1
1 2
1 2 3
4 2 3
4 1 3
4 1 2
5 1 2
5 1 2
5 1 2
5 3 2
5 3 4
5 3 4
9 laphiba laphiba generálódik 42
First-In-First-Out (FIFO) algoritmus 4 lapkeret esetén Kívánt lap: 1
2
3
4
1
2
5
1
2
3
4
5
1
1 2
1 2 3
1 2 3 4
1 2 3 4
1 2 3 4
5 2 3 4
5 1 3 4
5 1 2 4
5 1 2 3
4 1 2 3
4 5 2 3
10 laphiba 43
Belady anomáliája
Belady László, 1969: Korábban azt hitték, ha több a lapkeret akkor csökken vagy azonos számú lesz a laphiba Bár több a lapkeret, mégis több a laphiba
44
Optimális lapcserélési algoritmus • Egyszerű leírni, de lehetetlen megvalósítani • Azt a lapot cseréljük le, melyet a leghosszabb ideig nem használunk – Sajnos nem látunk a jövőbe – A laphiba idejében nem lehet megmondani, hogy mely lapokra lesz hivatkozás
• Szimulátorban első futtatás során nyomonkövetjük a hivatkozásokat • Második futásnál használható az optimális algoritmus 45
Optimális lapcserélési algoritmus 4 lapkeret esetén
„Jövőbe látás”
Kívánt lap: 1
2
3
4
1
2
5
1
2
3
4
5
1
1 2
1 2 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 5
1 2 3 5
1 2 3 5
1 2 3 5
4 2 3 5
4 2 3 5
6 laphiba 46
Not-Recently-Used (NRU) Gyorsítótár Módosított Jelenlét/hiány bit letíltás Lapkeret száma Hivatkozott
Védelmi bitek
Módosított bit: ha írtunk a lapra értéke 1 lesz, ha értéke 0 nem kell kiírni a lemezre (dirty bit) Hivatkozott bit: ha olvastunk vagy írtunk értéke 1 lesz; segít ha egy lapot ki kell dobni, akkor a használtat nem választjuk 47
Not-Recently-Used (NRU) • Amikor egy processzus elindul, mindkét bitet (módosított, hivatkozott bit) nullázzuk • Időnként (minden) órajelre nullázzuk a Hivatkozott bitet – Így megkülönböztetjük azokat a lapokat amelyekre nem hivatkoztunk az időben
48
Not-Recently-Used (NRU) • Négy csoportba sorolhatók a lapok – – – –
0. osztály: nem hivatkozott, nem módosított 1. osztály: nem hivatkozott, módosított 2. osztály: hivatkozott, nem módosított 3. osztály: hivatkozott, módosított
• Az algoritmus véletlenszerűen kiválaszt egy lapot a legkisebb sorszámú nemüres osztályból és ezt a lapot dobja ki a memóriából
49
Második lehetőség lapcserélési alg. • • • •
Second chance FIFO módosítása Ne dobjon ki gyakran használt lapot Ha a Hivatkozott bit – nulla: nem használtuk a lapot és eldobható – egy: töröljük a bitet és a lapot a lista végére tesszük, úgy kezeljük, mintha most jött volna be a memóriába
• Olyan lapot keresünk, amelyre nem volt hivatkozás az utolsó időintervallumban 50
Második lehetőség lapcserélési alg. • Ha mindegyikre volt hivatkozás, akkor FIFO-ként működik – Hiszen amikor a listán végigmentünk az első lapot nullás bittel kapjuk meg Elsőnek betöltött lap
Betöltési idő
Utoljára betöltött lap
A-t úgy kezeljük Mint egy újonnan Betöltött lapot 51
Óra lapcserélési algoritmus • A második lehetőség algoritmus folyamatosan mozgatja a lapokat a listában – Nem túl hatékony
• Hatékonyabb egy körkörös lista • A mutató mindig a legrégebbi lapra mutat
52
Óra lapcserélési algoritmus Laphiba esetén a mutatónál levő lapot vizsgáljuk: Hivatkozott bit értéke: 0: eldobjuk a lapot 1: nullázzuk a bitet és a következő lapra lépünk
53
Least-Recently-Used (LRU) • Optimális algoritmus közelítése – Az utoljára használt lapok valószínűleg újra kellenek
• Amikor laphiba történik akkor a legrégebben használt lapot dobjuk el • Nehezen megvalósítható – Egy láncolt listát készítünk a lapokból – A lista elején van a legutoljára használt lap, végén a legrégebben használt lap – A probléma, hogy a listát minden hivatkozásnál frissíteni kell 54
Least-Recently-Used (LRU) • Alternatív implementáció – Rendeljünk egy számlálót minden laphoz – Minden hivatkozásnál növeljük a számlálót – Laphiba esetén a legkisebb számlálóértékű lapot választjuk
55
LRU bitmátrix-al • n lapkeret a gépben • n x n mátrixot definiálunk (csupa nulla) • k-adik lapra hivatkozunk – k-adik sor csupa 1-es – k-adik oszlop csupa 0 lesz
• Legkisebb bináris értékű sor tartozik a legrégebben használt laphoz
56
LRU bitmátrix-al 0
1
2
3
2
1
0
3
2
3
57
Összefoglalva Algoritmus
Megjegyzés
Optimális
Nem valósítható meg, de tesztnek jó
FIFO
Fontos oldalakat is kicserélhet
Második esély
FIFO-nál sokkal jobb
Óra
Valóságos
LRU
Kiváló, de nehéz pontosan megvalosítani
NRU
Az LRU egy durva közelítése
58
Tervezési szempontok
59
Munkahalmaz • A processzus által használt lapok halmaza a munkahalmaz (working set) • Ha az egész munkahalmaz a memóriában van akkor a processzus laphiba nélkül fut • Ha nem fér el a memóriában akkor sok laphibát generál
60
Vergődés (thrashing) • CPU kihasználtsága növekszik a multiprogramozással – a processzusok számával
• Több processzus, kevesebb memória áll rendelkezésre • Egyes processzusok munkahalmaza nem fér be a memóriába – Növekvő laphiba
61
Vergődés (thrashing) • Egyre több processzusnak nincs elég memóriája – Csökken a CPU kihasználtsága – A rendszer I/O korlátozottá válik
• A processzusok nem „számítással” (hasznos tevékenységgel) hanem lapcserékkel van elfoglalva
62
Munkahalmaz modell • A vergődés elkerülése érdekében a sok lapozásos rendszer megpróbálja nyomon követni a processzusok munkahalmazát (working set) és a program indítása előtt betölteni • Denning, 1970
63
Globális-lokális lapcsere • Globális lapcsere – A processzus az összes lapkeretből választhat lapcsere esetén – Egy processzus elvehet lapkeretet egy másik processzustól
• Lokális lapcsere – A processzus csak a saját lapkeret választékából választhat
64
Globális-lokális lapcsere • Globális lapcsere jobban működik – A processzus munkahalmaz mérete a futás során változhat – Lokális lapcsere esetén, • ha nő a munkahalmaz vergődéshez vezet • ha csökken a munkahalmaz memóriát vesztegetünk
• A globális lapcsere algoritmusnak döntenie kell, hogy mennyi memóriát foglaljon a processzusnak 65
Foglalás • Minden processzusnak kell egy minimum mennyiségű lapkeret • Két foglalási stratégia – Fix méretű – Prioritásos
66
Fix méretű foglalás • Egyenlő méretű – Minden processzus ugyanannyi lapkeretet kap • 100 keret esetén, 5 processzus, 20 lapkeret mindegyik processzusnak
• Arányos méretű – A processzus méretének megfelelő számú lapot foglal
67
Prioritásos foglalás • Arányos méretű foglalás, de a prioritás alapján
68
Laphiba gyakorisági algoritmus • Page Fault Frequency, PFF • Megmondja, hogyan növeljük vagy csökkentsük a processzuslapok számát
Növelni kell a lapkeretek számát Csökkenteni kell a lapkeretek számát
Lapkeretek száma
69
Teherelosztás • A PFF használata mellett is előfordulhat vergődés – Néhány processzusnak kell lap – De nincs processzus ami fel tudna adni lapot
• Megoldás – Csökkentsük a memóriáért versenyző processzusok számát
70
Program szerkezet • int data [128,128]; • Minden sor egy lap – 1. program for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i][j] = 0;
128x128 =16385 laphiba – 2. program for (i = 0; i < 128; i++) for (j = 0; j <128; j++) data[i][j] = 0;
128 laphiba 71
I/O és lapozás • Néha szükség lehet arra, hogy ne engedjük egy lap eldobását, pl. I/O esetén • Rögzíteni kell a lapot
72
VM stratégia • A virtuális memória rendszer működése és hatékonysága sok tényezőtől függ – – – – – –
Laptábla kialakítása (több szintű, hasító táblás) Lapméret Lapcsere stratégia Betöltési stratégia Munkahalmaz mérete Globális-lokális foglalás
73
Lapméret • Általában választható érték • Kis lap méret – Előny • Kisebb belső töredezettség • Jobban használható különböző adatszerkezeteknél
– Hátrány • Egy processzusnak sok lap kell • Nagyobb laptábla
74
Lapméret
75
Betöltési stratégia • Meghatározza mikor töltsünk be egy lapot – Szüksége szerinti betöltés • Laphiba esetén
– Előtöltés • Javítja az I/O-t, nagyobb egységben olvasunk
76
Lapcsere stratégia • Azt a lapot kell eltávolítani, melynél a legvalószínűbb hogy a jövőben nem hivatkozunk rá • Korlátok: – Kernel kód – Kernel adatszerkezetek – I/O bufferek
77
Takarítási stratégia • Jó lenne ha mindig rendelkezésre állna néhány szabad lap • Paging daemon – Háttérben fut – Ha nincs elég szabad lap, akkor a lapcserélési algoritmus alapján kijelöl néhányat – Időzíti, hogy a lapokat kiírjuk a merev lemezre, így amikor laphiba van lesz szabad lap
78
