Memória kezelés
1
Programok, statikus linkelés • Rendszer könyvtár, mint bármelyik másik tárgykód (object file) • Előny – Egyszerű – Nincs verzió probléma, program és library illeszkedik
• Hátrány – Nagy bináris kód memóriában, merev lemezen – Minden programban saját library
2
Programok, dinamikus linkelés • Linkelés (kapcsolat) késleltve van a végrehajtásig • Minden könyvtár (library) rutinhoz csak egy betöltőt tartalmaz • Előny – Egy library a merev lemezen és a memóriában
• Hátrány – Verzió ütközés • Verzió számmal elég jól kezelhető UNIX alatt • „Windows DLL Hell” 3
Processzus • Egy vagy több futtatható szál • Futáshoz szükséges erőforrások – Memória (RAM) • Program kód (text) • Adat (data) • Különböző bufferek
– Egyéb • Fájlok, disk hely, nyomtató, stb.
4
Operációs rendszer néhány célja • • • •
Maximalizálja a CPU kihasználtságát Maximalizáljuk a memória kihasználtságát Minimalizáljuk a válaszidőt Fontos (prioritásos) processzusokat vegye előre
• Ellentmondó célok – Ha maximalizáljuk a CPU kihasználtságát (minnél több processzus futtatásával) növeljük a válaszidőt 5
Memória gazdálkodás • Memory management • Nyilvántartja hogy mely memória foglalt illetve szabad • Memóriát foglal a processzusok számára amikor szükséges – Felszabadítja a memóriát végül
• Kezeli a memória hely átadást a memória és a diszk között 6
Követelmények • Relokáció – A programozó nem tudja, hogy a processzus hol lesz a memóriában amikor végrehajtódik – Amíg egy processzus fut, lehet hogy áthelyeződik a diszkre – A memória referenciákat át kell alakítani a kódban
7
Követelmények
8
Követelmények • Védelem – Egy processzus ne érhesse el egy másik processzus adatait – Lehetetlen abszolút címet ellenőrizni, hiszen lehet hogy a processzus áthelyeződik – Futás közben kell ez a védelem
9
Követelmények • Megosztás – Több processzus is el tudja érni ugyanazt a memória helyet
10
Követelmények • Logikai szerkezet – A programokat modulokban írjuk – A modulokat függetlenül írhatjuk és fordíthatjuk – Különböző fokú védelemre lehet szükség (csak olvasható, csak futtatható)
• Fizikai szerkezet – A program által igényelt memória nem biztos hogy rendelkezésre áll – A programozó nem tudja hogy mennyi hely fog rendelkezésre állni 11
Memória hierarchia Tipikus elérési idő 1 nsec 2 nsec 10 nsec 10 msec 100 sec
Tipikus kapacitás Regiszterek Cache Memória (RAM) Mágneses diszk Mágneses szalag
< 1 KB 1 MB 512 MB 100 GB 100 MB
12
Cache CPU Regiszter
word
block
Cache
Memória
• CPU és memória között – 1 és néhány ciklus – 1000 ciklus a RAM eléréshez
• Korábban elért adatot tartalmaz – Gyorsabb elérés, mint a memórához való hozzáférés
• Hardware kezeli • Általában hierarchikus, on és off chip 13
Memória kezelő algoritmusok • 2 fő osztály – Mozgatják a processzusokat a memória és a diszk között • Swapping, paging (lapozás)
– És amelyek nem • Egyszerű • PC nem használja, de telefonokban, PDA-ban használják
14
Kellenek-e a bonyolult algoritmusok?
A memória növekedése nem ugyanolyan mint a processzoroké. Mindig lesz olyan alkalmazás, mely több memóriát igényel. Lásd multimédia
15
Monoprogramozás, csere és lapozás nélkül 0xFFF
Operációs Rendszer, a ROM-ban
Eszköz meghajtó, a ROM-ban
Felhasználói program Felhasználói program Operációs Rendszer, a RAM-ban Régi nagyszámítóges rendszerek, ma már ritka
Felhasználói program Operációs Rendszer, a RAM-ban
0 Kézi számítógépek, beágyazott rendszerek
MS-DOS 16
Monoprogramozás • OK, ha – csak egy processzust kell futtatni – a szükséges memória egyenlő a rendelkezésre álló memóriával
• Egyébként – Rossz CPU kihasználtság ha I/O-ra kell várni – Rossz memória kihasználtság ha különböző munkák vannak
17
Megoldás • Osszuk fel a memóriát futtassunk több processzust – Multiprogramozás, multitasking
18
Hogyan osszuk fel a memóriát? • Egyik megoldás: – Osszuk fel a memóriát egyenlő részekre, partíciókra – Ha egy processzus elfér akkor bármelyik részbe betölthető – Ha a teljes memóriánál kisebb de egy résznél nagyobb nem futhat – A kihasználatlan részeket elvesztegetjük • Belső töredezettség (fragmented)
Processzus E
Processzus D
Processzus C
Processzus B
Processzus A 19
Változó méretű, de rögzített partíciók • A memória partíciókhoz processzus sorok (queue) tartoznak • Egy processzus a legkisebb, de a processzusnál nagyobb méretű partícióba kerül
Operációs rendszer
20
Változó méretű, de rögzített partíciók • Probléma – Bizonyos partíciókat egyáltalán nem használunk – Például:
Operációs rendszer
• kis processzusokat használunk, de csak nagy partíciók állnak rendelkezésre • hosszú lesz a várakozás
21
Változó méretű, de rögzített partíciók • Egy sor – Ha egy partíció kiürül, akkor az első processzus amelyik belefér betöltődik
Operációs rendszer
• Akár kis processzus nagy partícióba
– Növekszik a belső töredezettség (fragmented)
22
Változó méretű, de rögzített partíciók • Másik stratégia – Az egész sorból kiválasztjuk azt a legnagyobb processzust amelyik belefér a partícióba
Operációs rendszer
• Hátrányosan kezeli a kis munkákat, pedig a kis munkák általában az interaktívak – Egy kis partíció az interaktív munkáknak – Egyetlen munka sem mellőzhető k-nál többször
• OS/360 IBM gépek, ma már nem használják 23
Dinamikus méretű partíciók • A partíciók változó méretűek • A processzus pontosan annyi memóriát kap amennyit igényel – Feltételezzük, hogy a processzus tudja mennyi kell
24
Dinamikus méretű partíciók Operációs rendszer
8M
Operációs rendszer
8M
Processzus 1 20M
56M
Operációs rendszer
8M
Processzus 1 20M
Processzus 2
14M
36M 22M
25
Dinamikus méretű partíciók Operációs rendszer Processzus 1
Processzus 2
8M 20M
Operációs rendszer Processzus 1
8M 20M
14M
14M
Processzus 3 18M
Processzus 3 18M
4M
4M
Operációs rendszer Processzus 1
8M 20M
Processzus 4 8M 6M Processzus 3 18M 4M
26
Dinamikus méretű partíciók Operációs rendszer
8M 20M
Operációs rendszer
8M
Processzus 5 14M 6M
Processzus 4
8M 6M
Processzus 3 18M 4M
Processzus 4 8M 6M
Hova??? Processzus 5 14M
Processzus 3 18M 4M
27
Töredezettség • Külső töredezettség – A lefoglalt memóriához képesti külső részeket vesztegetünk el – Összmemória lehet hogy elég, de szét van szórva – Memóriatömörítés használható
• Belső töredezettség – A lefoglalt memórián belüli részt vesztegetünk el
28
Több probléma is van • Egy processzusnak mennyi memóriát foglaljon? – Ha rögzített a méret, akkor nem gond – Mi van ha növekszik a memória igény • Ha a processzus mellett van hely, nem gond • Elmozgathatja a processzust ahol van hely
• Melyik szabad helyhez rendelje a processzust?
29
Memóriakezelés láncolt listával • Láncolt listába (linked list) fűzzük a szabad és foglalt memória szegmenseket – Egy elem: cím, méret – A címek növekvő sorrendjében • Így könnyebb összevonni a szomszédos lyukakat
Cím Méret Mutató
Cím Méret Mutató
Cím Méret Mutató
Cím Méret Mutató 30
Memóriafoglalási stratégiák • First-fit – Addig keres a szegmensek listájában, amíg meg nem találja az első megfelelő méretű lyukat – A leggyorsabb, a lehető legkevesebbet keres – Nagy a külső töredezettség • Sok kihasználatlan lyuk a lista elején
– Több nagy blokkot hagy a memória végén
31
Memóriafoglalási stratégiák • Next-fit – First-fit egy változata, de a keresés, az utoljára sikeresen lefoglalt helytől kezdődik – Bays bizonyította, hogy rosszabb teljesítményű, mint a first-fit
32
Memóriafoglalási stratégiák • Best-fit – Az egész listát végigkeresi és a legkisebb alkalmas lyukat választja – A first-fit és next-fit -nél több memóriát veszteget el, mivel kicsi használhatatlan lyukakat képes csinálni
33
Memóriafoglalási stratégiák 16 Mbyte foglalása esetén
first-fit best-fit
Utolsó foglalás
lefoglalt szabad next-fit
előtte
utána
34
Memóriafoglalási stratégiák • Worst-fit – Ha nem akarunk sok kis lyukat választhatjuk a legrosszabb, legnagyobb lyukat – Így a maradék lyuk is nagy lesz – Megmutatták, hogy az előzőeknél rosszabb
35
Memóriafoglalási stratégiák • Előző négy algoritmus gyorsítható – Ha külön listát tartunk fel a lyukaknak • Nem kell végigkeresni a processzusokat is • A probléma – A foglalásnál be kell illeszteni a listába – A felszabadításnál ki kell venni a listából
– A lyukak listája lehet nagyság szerint is rendezve • Ekkor a best-fit gyorsabb lesz
36
Memóriafoglalási stratégiák • Quick-fit – A leggyakrabban kért méretekhez külön lyuklistát készítünk – Gyorsan talál megfelelő lyukat – Nehéz ellenőrizni, hogy szomszédos lyukkal összevonható-e
37
Memóriafoglalási stratégiák • Összefoglalva – First-fit és next-fit a legjobb módszerek, a többihez képest – Ritkán használják ezeket manapság – Például a Buddy rendszert használják
38
Buddy rendszer • Lefoglalandó memória mérete 2 többszöröse – 2x
• Dönteni kell – Felső határról: pl 2000K memória esetén xmax=10, ekkor maximum 210=1024K memória foglalható egyszerre, a többi (976K) csak kis darabokban – Alsó határról: legkisebb lefoglalható egység
• Kis külső töredezettséget eredményez • Belső töredezettsége viszont nagy lehet 39
Buddy rendszer xmin=6
26=64K,
xmax=10
210=1024K
1M memória áll rendelkezésre
40
Buddy rendszer, fa szerkezet
41
Slab foglalási rendszer • Solaris, Linux használja • Jeff Bonwick, SunOS • Alapötlet – Elég sok memória kell bizonyos fix méretű adatokhoz (objektumokhoz) • File leírók, mutexek, szemaforok, stb
– Az objektum inicializálásához szükséges idő több mint a foglaláshoz vagy felszabadításhoz szükséges idő – Így a memóriát nem kell felszabadítani, hanem az inicializált formájában tartsuk meg 42
Slab foglalási rendszer • Cache lista: kétszer kapcsolt lista • Cache: három, kétszer kapcsolt lista – Teljesen foglalt „slab”-ek listája – Részben foglalt slab-ek listája – Üres slab-ek listája
• Slab: – folytonos memória darab – azonos méretű objektumok csoportja
43
Slab foglalási rendszer
44
Slab foglalási rendszer • Quick-fit -hez hasonló, mert azonos méretű objektumokat tartalmaz egy cache • Memória felszabadítás könnyű – Az üres slab listából lehet felszabadítani
• Memória foglalás könnyű – A slab-ben levő memóriát használjuk
• A külső töredezettség kicsi • Belső töredezettség minimális – Az objektum éppen megfellelő méretű – Slab mérettel befolyásolható 45
Memóriakezelés bittérképpel • Foglalt és szabad memóriát karban kell tartani – Láncolt lista – Bittérkép • 0 : az egység szabad • 1 : az egység foglalt
46
Memóriakezelés bittérképpel • Allokációs egység mérete fontos – Allokációs egység kicsi >> nagy bittérkép – Allokációs egység nagy >> nagy lehet a belső töredezettség
• Általában jól használható • A fő probléma a keresés – n darab összefüggő 0 bitet kell keresnie – Mivel átlóghat szóhatáron, nem egyszerű!!! – Például: ha 5 memória egység kell a processzusnak 1
0
1
1 1
1
0
0
0
0
0 1
1
1
1
1
47
Memória tömörítés • Csökkenthető a külső töredezettség – Csak ha a processzusok áthelyezhetők – Általában hardweres támogatást igényel
Processzus E
Processzus D Processzus E Processzus D Processzus B
Processzus B
Processzus A
Processzus A 48
Relokáció • Logikai cím
Process Control Block
– A programon belüli hely
• Amikor a program fut, egy valóságos fizikai cím kellene • A logikai címeket mikor rendeljük fizikai címhez?
Program
Adat
Verem
49
Relokáció • Utasítások és adatok a memóriához rendelése – Fordítási időben • Memória hely előre ismert, abszolút címet lehet generálni
– Betöltési időben • Áthelyezhető kód kell • A betöltő (loader) végzi a hozzárendelést
– Végrehajtási időben • Áthelyezhető kód, melynek futás közben is változhat a helye • Hardware támogatás kell, bázis és limit regiszter
50
Relokáció
51
Relokáció, futási időben • Amikor a program betöltődik meg kell határozni az aktuális (abszolút) memória címet • A diszkre kiírás és visszaolvasás (swap) miatt is megváltozhat a memória cím • Memória tömörítés is megváltoztathatja a memória címet
52
Relokáció Relatív cím Process Control Block
Bázis regiszter
Program
+
Határ regiszter
<
Abszolút cím Adat
Verem Megszakítás az op. rsz. -nek, címzési hiba
53
Relokáció • Bázis regiszter – A processzus kezdő címe
• Limit regiszter – A processzus végének címe
• Amikor egy processzus betöltődik, a regiszterek megfelelő értéket kapnak
54
Relokáció • A bázis regiszter értékét a relatív címhez adjuk hozzá, hogy egy abszolút memória címet kapjunk • Az eredmény címet összehasonlítjuk a limit regiszterrel – Ha az érték nincs határon belül megszakítás generálódik, a hiba kezeléséhez
55
Relokáció • Hátrányok – A fizikai memória folyamatos kell legyen – A teljes processzusnak a memóriában kell lennie
56
Eddig feltételeztük, hogy a processzus mérete kisebb mint a memória • Mi van ha nagyobb a program mint a memória?
57
Overlay • Csak azokat az utasításokat és adatokat tartjuk a memóriában melyekre szükség van • Felhasználó implementálja – Nincs szükség operációs rendszer támogatásra
• A program tervezése overlay-el nagyon komplex
58
Overlay, két fázisú fordító Szimbólum tábla Közös rutinok Overlay drive
Pass 1
Pass 2
59
Virtuális memória • Az egyszerű módszerekkel kapcsolatos problémák elkerülésére • Két stratégia – Lapozás (paging) – Szegmentálás (segmentation)
• A lapozás a domináns stratégia manapság • Hibrid rendszer is van 60
