Processzus. Operációs rendszerek MINB240. Memória gazdálkodás. Operációs rendszer néhány célja előadás Memóriakezelés

Processzus • Egy vagy több futtatható szál • Futáshoz szükséges erőforrások – Memória (RAM)

Operációs rendszerek

• Program kód (text) • Adat (data) • Különböző bufferek

MINB240 5-6-7. előadás

– Egyéb • Fájlok, disk hely, nyomtató, stb.

Memóriakezelés

Operációs rendszerek MINB240

1

Operációs rendszer néhány célja • • • •

2

Memória gazdálkodás

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

• 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

• 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 Operációs rendszerek MINB240


3

• Kezeli a memória hely átadást a memória és a diszk között Operációs rendszerek MINB240

4

Követelmények 1.

Követelmények 1.

• 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


5


Követelmények 2.

6

Követelmények 3.

• Védelem

• Megosztás

– 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


– Több processzus is el tudja érni ugyanazt a memória helyet

7


8

Követelmények 4.

Memória hierarchia

• 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ó)

Tipikus elérési idő < ns

– A program által igényelt memória nem biztos, hogy rendelkezésre áll – A programozó nem tudja, hogy mennyi hely fog rendelkezésre állni Operációs rendszerek MINB240

word

10 ms s

Mágneses diszk Mágneses szalag

9

Cache CPU Regiszter

10 ns

Regiszterek Cache Memória (RAM)

ns

• Fizikai szerkezet

Tipikus kapacitás 1 KB 1 MB 1 GB 100 GB GB, TB


10

Memória kezelő algoritmusok block

Cache

• 2 fő osztály

Memória

– Mozgatják a processzusokat a memória és a diszk között

• CPU és memória között – 1 és néhány ciklus – 1000 ciklus a RAM eléréshez

• Swapping, paging (lapozás)

– És amelyek nem

• Korábban elért adatot tartalmaz

• Egyszerű • PC nem használja, de telefonokban, PDA-ban használják

– Gyorsabb elérés, mint a memóriához való hozzáférés

• Hardware kezeli • Általában hierarchikus, on és off chip Operációs rendszerek MINB240

11


12

Kellenek-e a bonyolult algoritmusok?

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 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


13

Monoprogramozás

Operációs Rendszer, a RAM-ban

0

Régi nagyszámítógépes rendszerek, ma már ritka

Felhasználói program

Kézi számítógépek, beágyazott rendszerek Operációs rendszerek MINB240

MS-DOS 14

Megoldás

• Jó, ha

• Osszuk fel a memóriát, futtassunk több processzust

– csak egy processzust kell futtatni – a szükséges memória egyenlő a rendelkezésre álló memóriával

– Multiprogramozás, multitasking

• 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


15


16

Hogyan osszuk fel a memóriát?

Változó méretű, de rögzített partíciók

• 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) Operációs rendszerek MINB240

Processzus E

Processzus D

Processzus C

• 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

Processzus B

Processzus A 17

Változó méretű, de rögzített partíciók • Probléma


18

Változó méretű, de rögzített partíciók • Egy sor

– Bizonyos partíciókat egyáltalán nem használunk – Például:



• Akár kis processzus nagy partícióba

• kis processzusokat használunk, de csak nagy partíciók állnak rendelkezésre • hosszú lesz a várakozás


– Ha egy partíció kiürül, akkor az első processzus amelyik belefér betöltődik

– Növekszik a belső töredezettség (fragmented)

19


20

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


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

• 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épeknél • ma már nem használják Operációs rendszerek MINB240

21

Dinamikus méretű partíciók Operációs rendszer

8M


8M

Processzus 1 20M

56M



Dinamikus méretű partíciók 8M


Processzus 1 20M

Processzus 1

Processzus 2

14M

Processzus 2

22M

Processzus 3

8M 20M

Operációs rendszer Processzus 1

8M 20M

14M

14M

18M

Processzus 3 18M

36M

4M


22

23

4M


Operációs rendszer Processzus 1

8M 20M

Processzus 4 8M 6M Processzus 3 18M 4M

24

Dinamikus méretű partíciók

Töredezettség • Külső töredezettség


8M 20M


Processzus 5 14M 6M

Processzus 4

Processzus 3

8M

Processzus 4 8M

6M

6M

18M 4M

– 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ó

8M

Hova??? Processzus 5 14M

• Belső töredezettség – A lefoglalt memórián belüli részt vesztegetünk el

Processzus 3 18M 4M


25

Több probléma is van


26

Memóriakezelés láncolt listával

• 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

• 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

• Ha a processzus mellett van hely, nem gond • Elmozgathatja a processzust ahol van hely

• Így könnyebb összevonni a szomszédos lyukakat

• Melyik szabad helyhez rendelje a processzust? Cím Méret Mutató Operációs rendszerek MINB240

27

Cím Méret Mutató

Cím Méret Mutató


Cím Méret Mutató 28

Memóriafoglalási stratégiák


• First-fit

• Next-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

– 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

• Sok kihasználatlan lyuk a lista elején

– Több nagy blokkot hagy a memória végén


29



30


• 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 sok kicsi használhatatlan lyukakat képes csinálni

16 Mbyte foglalása esetén

first-fit best-fit

Utolsó foglalás

lefoglalt szabad next-fit


31

előtte


utána

32



• Worst-fit

• Előző négy algoritmus gyorsítható

– 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

– 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


33



34


• Quick-fit

• Összefoglalva

– 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

– First-fit és next-fit a legjobb módszerek, a többihez képest Ritkán használják ezeket manapság Helyette: Buddy rendszer


35


36

Buddy rendszer

Buddy rendszer

• Lefoglalandó memória mérete 2 többszöröse –

2x

• Kis külső töredezettséget eredményez • Belső töredezettsége viszont nagy lehet

2xmin-2xmax

• Dönteni kell – Felső határról: 2xmax (teljes mérete a memóriának) 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: 2xmin legkisebb lefoglalható egység Operációs rendszerek MINB240

• Kezdetben: teljes memória szabad • Foglaláskor: a rendszer fát épít fel, jelezve a memóriablokkok méretét • Felszabaduláskor: ha két egymás mellet lévő blokk felszabadul, akkor összevonja – magasabb szintre kerül 37

Buddy rendszer xmin=6

26=64K,

xmax=10


38

Buddy rendszer, fa szerkezet

210=1024K

1M memória áll rendelkezésre


39


40

Slab foglalási rendszer


• Solaris, Linux használja • Jeff Bonwick, SunOS • Alapötlet

• Cache lista: kétszer kapcsolt lista • Cache: három, kétszer kapcsolt lista

– 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 Operációs rendszerek MINB240

41


– 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


42

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 megfelelő méretű – Slab mérettel befolyásolható Operációs rendszerek MINB240

43


44

Memóriakezelés bittérképpel

Memóriakezelés bittérképpel

• Foglalt és szabad memóriát karban kell tartani

• Allokációs egység mérete fontos

– Láncolt lista – Bittérkép

– Allokációs egység kicsi >> nagy bittérkép – Allokációs egység nagy >> nagy lehet a belső töredezettség

• 0 : az egység szabad • 1 : az egység foglalt

• Á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


45

1 0

1 1 1

Memória tömörítés • Csökkenthető a külső töredezettség – Csak ha a processzusok áthelyezhetők – Általában hardveres támogatást igényel

1 Operációs 0 0 rendszerek 0 0MINB240 0 1 1 1 1 1

Relokáció • Logikai cím

Processzus E

Process Control Block

– A programon belüli hely

Processzus D Processzus E Processzus D Processzus B

46

Processzus B

• 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 Processzus A Operációs rendszerek MINB240

Processzus A 47


48

Relokáció

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 határ regiszter


49


Relokáció, futási időben

50

Relokáció

• 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

Relatív cím Process Control Block

Bázis regiszter

Program

+

Határ regiszter

<

Abszolút cím Adat

Verem


51

Megszakítás az op. rsz. -nek, címzési hiba Operációs rendszerek MINB240

52

Relokáció

Relokáció

• Bázis regiszter

• 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

– A processzus kezdő címe

• Határ regiszter – A processzus végének címe

• Amikor egy processzus betöltődik, a regiszterek megfelelő értéket kapnak


53

Relokáció

– Ha az érték nincs határon belül megszakítás generálódik, a hiba kezeléséhez


54

Védelem

• Hátrányok – A fizikai memória folyamatos kell legyen – A teljes processzusnak a memóriában kell lennie


55


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?

Overlay • Program rétegekre bontása • 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


57

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 Operációs rendszerek MINB240

59


58

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

Virtuális memória

– 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 Operációs rendszerek MINB240

61

Megoldás

62

Lapozás (paging)

• A processzusok által látott memória terület különbözik a fizikailag létező memóriától • Követelmények

• A virtuális és fizikai memóriát egyenlő darabokra osztjuk fel

– 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 Operációs rendszerek MINB240


63

– 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 Operációs rendszerek MINB240

64

MMU

Lapozás

CPU kártya

• 0-64K a virtuális címek

CPU Memória MMU

• A gépnek csak 32K memóriája van

Lemez vezérlő

• Csak a szükséges részek töltődnek be • 4K a lapméret sín

• MMU

• A valós rendszerekben a lapméret 512 byte, 1K, 4K (2 hatványa)

– Memory Management Unit – A virtuális címeket fizikai címekké alakítja Operációs rendszerek MINB240

MOV REG,0 65

66

Lapozás

Lapozás MOV REG, 32780

• Vannak lapok melyek nincsenek a fizikai memóriában

• Az MMU észleli a problémát és laphiba megszakítást generál az operációs rendszernek!

• Jelölés: jelenlét/hiány bit

• Az operációs rendszer egy lapkeretet kiír a lemezre

• Mi lesz ha olyan címre hivatkozunk, mely egy be nem töltött lapon van?

• Betölti a kívánt lapot • Módosítja a laptérképet a szükséges módon

MOV REG, 32780

• A megszakítást okozó utasítástól folytatja. 67

68

Lapozás • • • •

MMU CPU kártya

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

CPU

Lemez vezérlő

Memória MMU

– A programozó csak a virtuális címmel foglalkozik

sín

• MMU – Memory Management Unit – A virtuális címeket fizikai címekké alakítja


69


Címfordítás

70

Címfordítás

• CPU által generált cím:

Szám

– Lapszám (p) • a laptábla indexe, amely a fizikai memória címet tartalmazza • ez a bázis cím

Bit

p m-n

2m címtartomány és 2n lapméret esetén (m=16, n=12) Címtartomány: 216 = 65535

– Lap offszet (d) • a fizikai memória címmel kombinálva kapjuk a végleges címet

d n 64K

n = 12 bit m - n = 4bit Lapméret: 212 = 4096

4K

Lapok száma: 216-12 = 24 = 16 Operációs rendszerek MINB240

71


72

MMU működése

MMU működése, másképpen 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 12 bites eltolás közvetlenül másolódik

Lap tábla

• Ezért használunk 2 hatványa lapméretet

Virtuális lap számát a laptábla indexeként használjuk

Jelenlét bit

MMU Bejövő virtuális cím 73 (8196)

Laptábla


74

A laptábla nagyon nagy lehet

• A laptábla célja, hogy a lapokat lapkeretekre képezzük le • Lényegében egy függvény

2m címtartomány és 2n lapméret esetén

– argumentuma: a virtuális lapszám – eredmény: a lapkeret száma

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

• Két probléma:

Minden processzusnak saját laptáblája van!!

– A laptábla nagyon nagy lehet – A leképezés gyors legyen Operációs rendszerek MINB240

64 bit esetén még több 75


76

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

Laptábla: Gyors hadrware 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 regiszterekbe töltése csökkenti a teljesítményt Operációs rendszerek MINB240

77

Teljes laptábla a memóriában


78

Kétszintű laptábla

• Egy regiszter mutat a laptáblára • Processzus váltásnál csak egy regisztert kell átírni • Hátrány

Második szintű laptábla

32 bites cím, két darab 10 bites mezőből és 12 bites offszetből áll.

Felső szintű laptábla

– Minden utasításnál több memóriahivatkozás

lapok Operációs rendszerek MINB240

79

80

Kétszintű laptábla

Kétszintű laptábla, címfordítás


Pl.: Virtuális cím: 4206596 Ez az adatszegmens 12292-es bájtja.

Felső szintű laptábla

PT1 = 1; PT2 = 3; Offset = 4 Felső szintű laptábla

PT1 = 1 Æ 4-8MB címek


PT2 = 3 Æ 12-16MB címek Lapkeretszám megadható.

Jelenlét bit 0

Ha a lapkeret a memóriában van (jelenléti/hiány bit jelzi), akkor

lapok 81

PT2 + Offset = fizikai cím


Laptábla egy bejegyzése

TLB • A laptáblákat a memóriában tartjuk

Gyorsítótár Módosított Jelenlét/hiány bit letiltás

– Sajnos nagyban befolyásolja a teljesítményt

• Hivatkozáslokalitás

Lapkeret száma Hivatkozott

– A legtöbb hivatkozás a lapok egy kis számára vonatkozik

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 Operációs rendszerek MINB240

82

83

• Megoldás: – Hardware eszköz Translation Lookaside Buffer (címfordítási gyorsítótár vagy asszociatív memória) Operációs rendszerek MINB240

84

TLB

TLB

• MMU-ban található • 8 - 64 bejegyzést tud tárolni

• Lapszám nincs a TLB-ben

érvényesség, virtuális lapszám, módosítási bit, védelmi kód, valós lapkeret szám

• MMU először a TLB-ben keresi a lapot, egyidejűleg (párhuzamosan)!

– MMU a laptáblából keresi ki a lapot – 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

– Ha a művelet nem sérti a védelmet, azonnal kapjuk a lapkeret címet – Ha sérti, védelmi hiba

• Minden adatot felül kell írni a TLB-ben

85

MMU működése TLB-vel

86

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 a lap hiba

• Sokféle módszerrel javítható a működése Operációs rendszerek MINB240

87


88

Invertált laptáblák


• 32 bites cím, 4KB lapok Æ 232 /4.096=1.048.576 – Több mint 1 millió bejegyzés – Laptábla kb 4MB-os

• 64 bites cím, 4KB lapok Æ

264

• A valós tár minden lapkeretéhez tartozik egy bejegyzés (a virtuális címtér minden lapja helyett) – 64 bites címtér, 4 KB lapméret, 256 MB RAM • Csak 65 536 bejegyzés kell • Egy bejegyzés megadja: adott lapkeretet mely processzus mely lapja használja

/4.096

– Több mint 1052 bejegyzés – Egy bejegyzés 8 byte – A laptábla kb. 30 millió GB!!!

• 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

Æ megoldás: invertált laptábla Operációs rendszerek MINB240

89



90

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

Nem hatékony keresés, legrosszabb esetben O(n)

91


92

fork, Copy-On-Write, COW

COW, C lap módosítása előtt

• fork: Processzus létrehozására használtuk – Lemásolta a processzust, majd rögtön felülírtuk (execve)

Processzus 1

• Nem hatékony

Fizikai memória

Processzus 2

A Lap

– Megoldás:

B Lap

• 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 Operációs rendszerek MINB240

C Lap

93


COW, C lap módosítása után

94

Laphiba • Igény szerinti lapozás (demand paging)

Processzus 1

Fizikai memória

Processzus 2

A Lap B Lap

• • • •

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

C Lap

– Ha referencia mutat a lapra

C’ Lap


– Egy lap csak akkor töltődik be, amikor szükség van rá

• Érvénytelen referencia >> megszakítás (abort) • Nincs a memóriában >> betöltés (load) 95


96

Laphiba, lemezre írás-beolvasás

Érvényes-érvénytelen bit • Minden laptábla bejegyzés tartalmaz egy bitet – v: memóriában (érvényes, valid) – 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 Operációs rendszerek MINB240

97

Érvényes-érvénytelen bit


98

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.


99


i-ről v-re

Utasítás ismételt végrehajtása !!!!!

100

Laphiba

Lapcserélési algoritmusok

• Nincs üres lapkeret

• 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

– 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ás igényes, így minél kevesebbszer szeretnénk végrehajtani


101


102

First-In-First-Out (FIFO) algoritmus

First-In-First-Out (FIFO) algoritmus

3 lapkeret esetén

4 lapkeret esetén

Kívánt lap:

Kívánt lap:

1

2

3

4

1

2

5

1

2

3

4

5

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

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

9 laphiba

10 laphiba

laphiba generálódik Operációs rendszerek MINB240

103


104

Belady anomáliája

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

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

105

Optimális lapcserélési algoritmus 4 lapkeret esetén

• Szimulátorban első futtatás során nyomonkövetjük a hivatkozásokat • Második futásnál használható az optimális algoritmus 106

Not-Recently-Used (NRU) Gyorsítótár Módosított Jelenlét/hiány bit letiltás

„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

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) (M bit - modified 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 (R bit – referenced bit)

6 laphiba Operációs rendszerek MINB240


107


108

Not-Recently-Used (NRU)

Not-Recently-Used (NRU)

• Amikor egy processzus elindul, mindkét bitet (módosított, hivatkozott bit) nullázzuk • Időnként (pl. minden órajelre) nullázzuk a hivatkozott bitet

• Négy csoportba sorolhatók a lapok

– Így megkülönböztetjük azokat a lapokat, amelyekre nem hivatkoztunk az időben


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

109

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


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

– 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

Elsőnek betöltött lap

Betöltési idő

• Olyan lapot keresünk, amelyre nem volt hivatkozás az utolsó időintervallumban Operációs rendszerek MINB240

110

111


Utoljára betöltött lap

A-t úgy kezeljük mint egy újonnan 112 betöltött lapot

Óra lapcserélési algoritmus

Óra lapcserélési algoritmus

• A második lehetőség algoritmus folyamatosan mozgatja a lapokat a listában – Nem túl hatékony

Laphibakor: a mutatónál lévő lapot vizsgáljuk

• Hatékonyabb egy körkörös lista • A mutató mindig a legrégebbi lapra mutat

Döntés hivatkozott (R) bit alapján: ha R=0 : kidobjuk a lapot ha R=1 : R bitet nullázzuk, mutató a következő lapra lép

113

Least-Recently-Used (LRU)


114

Least-Recently-Used (LRU)

• Optimális algoritmus közelítése

• Alternatív implementáció

– 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ó

– Rendeljünk egy számlálót minden laphoz – Minden memóriahivatkozásnál növeljük a számlálót – Laphiba esetén a legkisebb számlálóértékű lap lesz a legrégebben használt – ezt a lapot választjuk

– 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 Operációs rendszerek MINB240

115


116

LRU bitmátrix-al

LRU bitmátrix-al Hivatkozási sor a lapokra: 0,1,2,3,2,1,0,3,2,3

• n lapkeret a gépben • n x n mátrixot definiálunk (csupa nulla) • k-adik lapra hivatkozunk

0

1

2

3

2

1

0

3

2

3

– 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


117


118

Munkahalmaz modell • 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

Tervezési szempontok


119


120

Vergődés (thrashing)

Vergődés (thrashing)

• CPU kihasználtsága növekszik a multiprogramozással

• 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 számával

• Több processzus, kevesebb memória áll rendelkezésre • Egyes processzusok munkahalmaza nem fér be a memóriába

• A rendszer nem „számítással” (hasznos tevékenységgel) hanem lapcserékkel van elfoglalva

– Növekvő laphiba


121

Munkahalmaz modell

122

Globális-lokális lapcsere

• A vergődés elkerülése érdekében a sok lapozásos rendszer megpróbálja nyomon követni a processzusok munkahalmazát és a program indítása előtt betölteni Æ előlapozás • P.J.Denning, 1970

• 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


123


124

Globális-lokális lapcsere

Foglalás

• Globális lapcsere jobban működik

• Minden processzusnak kell egy minimum mennyiségű lapkeret • Két foglalási stratégia

– A processzus munkahalmaz mérete a futás során változhat – Lokális lapcsere esetén,

– Fix méretű – Prioritásos

• 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 Operációs rendszerek MINB240

125

Fix méretű foglalás


126

Prioritásos foglalás

• Egyenlő méretű

• Arányos méretű foglalás, de a prioritás alapján

– 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


127


128

Laphiba gyakorisági algoritmus - PFF

Algoritmusok jósága

• Page Fault Frequency • Megmondja, hogyan növeljük vagy csökkentsük a processzuslapok számát • Nem adja meg, hogy laphiba esetén melyik lapot cserélje • Lefoglalt laphalmaz méretét szabályozza

• Laphibák aránya csökken, ha több lapkeretet foglalunk le Elfogadhatatlan nagy laphiba arány Æ Növelni kell a lapkeretek számát Processzusnak túl sok lapkerete van Æ Csökkenteni kell a lapkeretek számát

Lapkeretek száma Operációs rendszerek MINB240

129

Teherelosztás

Program szerkezet

• A PFF használata mellett is előfordulhat vergődés

• int data [128,128]; • Minden sor egy lap

– Néhány processzusnak kell lap – De nincs processzus ami fel tudna adni lapot

– 1. program for (j = 0; j < 128; j++) for (i = 0; i < 128; i++) data[i][j] = 0;

• Megoldás – Csökkentsük a memóriáért versenyző processzusok számát

128x128 =16385 laphiba – 2. program for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i][j] = 0;

128 laphiba Operációs rendszerek MINB240

131


132

I/O és lapozás

VM stratégia

• 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

133

Lapméret

• 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


134

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


135


136

Betöltési stratégia

Lapcsere stratégia

• Meghatározza mikor töltsünk be egy lapot

• Azt a lapot kell eltávolítani, melynél a legvalószínűbb, hogy a jövőben nem hivatkozunk rá • Korlátok:

– Szüksége szerinti betöltés • Laphiba esetén

– Előtöltés • Javítja az I/O-t, nagyobb egységben olvasunk


– Kernel kód – Kernel adatszerkezetek – I/O bufferek

137


138

Szegmentálás • Memória kezelési stratégia, mely a felhasználó nézőpontját támogatja • Például:

Szegmentálás

– – – –

Egy program szegmensekből áll Mindegyik szegmens külön címtér Egy eljárás nullás címen kezdődik Újrafordításnál nem kell változtatni

függvény

verem

sqrt

main

Különálló virtuális címterek Operációs rendszerek MINB240

139

140

Szegmentálás Programozói nézőpont

Szegmentálás • Szegmentált memória:

Memória

– Több lineáris címtérből álló virtuális memória

• Egy processzus különböző részei külön szegmensekben helyezhetők el • A részek külön-külön növekedhetnek, csökkenhetnek • A szegmensek különböző típusúak lehetnek • A szegmenseknek különböző lehet a védelme

1 1 4

2

3

2 3

4

– írható, olvasható, futtatható Operációs rendszerek MINB240

141

Szegmentált címzés

142

Tiszta szegmentálás

• A logikai cím két részből áll

• Lapok fix méretűek • Szegmensek nem fix méretűek

– Szegmens szám s – Offszet d



143


144

Tiszta szegmentálás

Összehasonlítás Lapozás

Szegmentálás

Nem

Igen

1

Sok

A teljes címtartomány meghaladhatja a fizikai címtartományt?

Igen

Igen

Meg lehet-e különböztetni és külön védeni a programot és adatot?

Nem

Igen

Nem

Igen

Nem

Igen

A programozó tudatában kell legyen a technikának? Hány lineáris címtartomány van?

Változó méretű adatok könnyebben kezelhetők?

Külső töredezettség alakul ki Megszüntethető tömörítéssel Operációs rendszerek MINB240

145

Összehasonlítás Miért találták ki a technikát?

Lapozás

Szegmentálás

Nagy lineáris memória területet kaphassunk, anélkül, hogy memóriát vennénk

A program el tudja különíteni a futtatható és adat részt logikailag különálló memória részre Támogassa a megosztást és védelmet


147

Függvények megosztása felhasználók között lehetséges?


146

Processzus. Operációs rendszerek MINB240. Memória gazdálkodás. Operációs rendszer néhány célja előadás Memóriakezelés

Recommend Documents