Operációs rendszerek Memória menedzselés
A program • • • • • • • •
Memória, címtartomány fogalmak A címkötődés és címleképzés kérdései A tárcsere Memóriamenedzselési osztályok, valós MM Virtuális MM koncepció Lapozós rendszer Szegmentálós rendszer NT esettanulmány
Vadász
2
A memória (tár) • Erőforrás, amit – Igényelni (kérni, allokálni) kell (a processzek igénylik) – Védeni kell (ellenőrzött elérések legyenek)
• Címekkel rendelkező cellák (rekeszek: bájtok, szavak, rekordok) készlete, • Egy-egy cella elérése (load-store) a címére való hivatkozással történhet • A fizikai memória hierarchikus szintekbe szervezett: – Processzorbeli-processzor közeli gyorsítótár – Központi tár – Másodlagos tár Vadász
3
1
A címtartományok • Miután a memória címekkel rendelkező rekeszek készlete, fontos fogalom a címtartomány fogalom • A címtartomány a címek készlete (szemben a memóriával, ami rekeszek készlete) • A címtartomány modellje
• A memória modellje
0 1
0. cella 1. cella
n-1 n
n-1. cella n. cella Vadász
4
Logikai címtartományok • A processzekhez logikai címtartományok tartoznak (Logical Address Space) – Az ő szemszögükből nézve van saját processzoruk, – van saját (logikai) memóriájuk. – A processzekhez egy lineáris, folytonos címtartományt szoktunk képzelni.
• Már a logikai címtartományokat is érdemes szakaszolni: – címek a kódnak, – az adatoknak, – a vermeknek. Vadász
5
A fizikai címtartományok • A CPU a fizikai memóriából tud felhozni, letárolni • A fizikai memóriához fizikai címtartományok tartoznak (Physical Address Space) – A címsín szélességétől függ, mekkora a fizikai címtartomány – Elképzelhető, hogy lehetséges fizikai címhez nem kötődik fizikai memória cella (fizikai címtartomány szakaszokhoz nem tartozik memória)
Vadász
6
2
A címkötődés (Address Binding) • Adott egy cím. Vajon tartozik-e hozzá cella? Melyik? – Kötődés a fordítás során: abszolút cím a tárgymodulokban – Kötődés a link során: abszolút cím a végrehajtható (betölthető) programokban – Kötődés a betöltés (load) során: abszolút címek a processz kontextusban – Kötődés a futás során (dinamikus kötődés): logikai címek a kontextusban. • A logikai címek lehetnek relatív címek, vagy virtuális címek
• A logikai címek és a fizikai címek közötti megfeleltetés (átalakítás) a címleképzés (mapping). Vadász
7
A címleképzések • Vegyük észre, más-más a probléma (a címleképzés kiváltó oka) az alább esetekben: – Nagyobb a memória, mint a címtartomány (korai rendszerekben 16 bites címzésnél gond volt) (A eset) – A logikai címtartomány és a fizikai címtartomány nem esik egybe (B eset) – A memória kisebb, mint a címtartomány (C eset) – (Természetesen a B eset a másik kettővel együtt is felléphet.)
Vadász
8
A címleképzések 0
A
c
0 c n
B k
0 c
n
n q 0
C
0
c
h
n
n
Vadász
9
3
A tárcsere (Swapping) • Vegyük észre, a C esetben tárcserére van szükség (átfedés (overlay), virtuális memória). • Tárcserére akkor is szükség lehet, ha különböző processzek (rutinok) felváltva használják ugyanazt a fizikai memória részt. 0 c
0 c k
n
n
q
Vadász
10
A memóriamenedzselés feladatai • A memória allokálás • A címleképzés segítése – Ezt kiegészítve az esetleges tárcsere (swapping out – swapping in, paging out – paging in) segítése
Vadász
11
A memória allokálása • Mivel a memória erőforrás, igényelni kell • A processzek az igénylők (allokálók) – Ún. statikus allokálás: a processz születésekor, hogy a kontextusa számára legyen tárolási lehetőség – Ún. dinamikus allokálás: processz élete során bővíti a rendelkezésére álló memóriát
• Az allokálás (mind a statikus, mind a dinamikus) az MM alrendszer egyik fontos feladata
Vadász
12
4
A címleképzés • A mai rendszerekben a processzek kontextusában logikai címek vannak (többnyire virtuális címek) • A logikai cím fizikai címre való leképzését, közben a cím kötődés megoldását a MM alrendszer a hardver MMU egységével együtt oldja meg – A címleképzés – kötődés során gondoskodnak a védelemről – Szükség esetén a ki-be mozgatásról (tárcseréről)
Vadász
13
MM alrendszer osztályozások • A virtuális címzés koncepciójú MM-től (lásd később) megkülönböztetve, vannak valós címzésű rendszerek – Fix partíciós és változó partíciós rendszerek • Korai MM rendszerek, • Felvetett problémáik: címkötődés késleltetése (áthelyezés lehetősége), partíció kiválasztási stratégia (best-, worst-, next fit) címzés védelme. • Némely probléma ma is érdekes (lapozó eszköz foglaltság kezelés stb.)
– A program-fejlesztő rendszerek által biztosított átfedési (overlay) technika a valós címzésű rendszerekben is megengedte a fizika memóriánál nagyobb logikai memória (logikai címtartomány) használatát Vadász
14
A virtuális memória koncepció • Általános megoldást ajánl a címleképzés – kötődés problémára • Lényege: – A processzek (meglehetésen nagy) virtuális címtartományt használhatnak • Állhat több résztartományból (régióból, szakaszból)
– Az MM a virtuális címekhez virtuális rekeszeket biztosít (a processzek számára átlátszó módon) • A virtuális cellák tartalma másodlagos tárolón mindig megtalálható, szükség esetén a fizikai memóriában is
– Mikor a processz egy virtuális címre hivatkozik, nem kell törődnie a címleképzéssel, sem a kötődéssel, sem a tartalom behozatalával. Vadász
15
5
Virtuális címtartomány - memória • A lehetséges virtuális címtartományt a címzési mód határozza meg (pl. 32 bites címzéshez 4 Gbájt) • Egy processz virtuális címtartománya ennél valószínűleg kisebb • A lehetséges fizikai címtartomány a címsín szélesség adja, ez lehet nagy. • A fizikai memória (a használható fizikai címtartomány) – bár egyre nő a gazdagépek memóriája – ennél is kisebb. Kisebb az összes processz virtuális memóriájánál. Vadász
16
A címkötődés • A taszképítő (linker) a végrehajtható-betölthető programokba virtuális címeket épít • A processzek a kontextusukban a virtuális címeket használják • Dinamikus címleképzés van: Vaddress Dynamic_Map Raddress • Előfordulhat a leképzés során, hogy a leképzett cím nem érvényes (not valid): a virtuális cellához nincs fizikai cella kötve, az nincs a fizikai memóriában. – Ekkor ki-be mozgatás (tárcsere) szükséges Vadász
17
Lapozó rendszerek (Paging) • Lapozós rendszerekben fix méretű blokkokban történik a címleképzés • A virtuális címtartomány (vagy annak altartománya) fix méretű szakaszokra van osztva • A virtuális memória fix méretű blokkokra van osztva: ez a lap (page) • A fizikai memória ugyanolyan (fix) méretű lapkeretekre (page frame) van osztva. • Lapozós rendszerekben a folytonos virtuális címtartománynak nem feltétlenül folytonos fizikai címtartomány fog megfelelni, nem folytonos címtartományra is lehet a leképzést végezni Vadász
18
6
Lapozó rendszerek (Paging) • (Tegyük fel: egy processz V címtartománya egy régióba tartozik, ezen belül folyamatos (bájtban mérve: 0-n)) • Egy virtuális cím formája: v = (p, o) ahol: p: a lap címe, (értéke 0 - np közötti, ahol np megmondja, hány lapból áll a processz);
o:
eltolás a lapon belül.
(értéktartománya át kell fedje a lapot)
Vadász
19
Lapozó rendszerek (Paging) • Egy fizikai cím: ahol: f o
r = (f, o) a lapkeret címe, az eltolás (offset).
• Az o eltolás bitszélessége a lap/lapkeret mérettől függ. • A lap/lapkeret méret architektúra függő!
Vadász
20
A laptáblák (Page Map Table) • Minden (egy dimenziós címtartományú, egy régiós) processz számára biztosított egy laptábla. (Több régiós processz: régiónkénti laptábla!) • Ennek címe: egy regiszterben (több régiósnál regiszterekben). • A laptáblának annyi bejegyzése van, ahány lapból áll a processz (egy bejegyzést a p lapcím indexel).
Vadász
21
7
Egy laptábla bejegyzés • Egy bejegyzés tartalma: – védelmi és állapot (state) bitek: • védelmi maszk (rwx stb.); • érvényességi (valid/present-absent) bit; • módosítás (dirty bit) jelző;
– lapkeret cím, – leíró a másodlagos tárolóhoz (cím és típus) (lehet ez a lapkeret cím mezőben is).
Vadász
22
Memória allokálás során • Statikus allokálás: készül(nek) laptábla (laptáblák), a szükséges számú bejegyzéssel • A bejegyzések tartalma kitöltődik – a kernel címtartományhoz tartozó bejegyzésekhez még a lapkeret címek is beíródhatnak, – a védelmi bitek és a másodlagos tároló leírók is kitöltődhetnek (leírók az image fájlra vonatkozhatnak, sok bejegyzésben not valid jelzi, nincs lapkeret rendelve a laphoz).
• Dinamikus allokálás során a laptábla "kiegészül", új bejegyzésekkel bővül (a címtartomány nő).
Vadász
23
Címleképzés lapozós rendszerben Base Address of Page Table b
Virtuális cím p
o
Page Table +
p Fizikai cím b+p
f
+
f
o
Itt érthető meg a HW MMU szerepe! Az addíciók HW-esek kell legyenek! Vadász
24
8
A laphiba (Page Fault) • Dinamikus címleképzés során a valid/present-absent bit jelzi: nincs a laphoz lapkeret rendelve. • Klasszikus kivételes esemény (exeption condition). A kezelője (Page Fault Handler) működésbe lép. • Keres szabad lapkeretet, kilapoz, ha szükséges, belapozza a kérdéses lapot, majd visszatér. • Újra indulhat - most már sikeresen - a leképzés. • A laphiba egész “normális jelenség“. • A laphiba gyakoriság (Page Fault Rata) - jellemzője a processz életének. Vadász
25
Kérdések, megoldandó dolgok • • • •
Mekkora kell legyen a laptábla? Hogy lehetne csökkenteni méretét? Hogy lehetne a címleképzést tovább gyorsítani? Meghatározandó a – belapozási stratégia • mely lapokat, mennyit hozzunk be egyidejűleg?
– mennyiségi stratégia • egyidejűleg hány lapkerete legyen/lehet egy processznek?
– kilapozási stratégia • mely lapok legyenek esélyesek kilapozásra?
– elhelyezési stratégia • nem a fizikai memóriára, hanem a másodlagos tárolóra Vadász
26
Laptábla méret kezelés • Méretét meghatározza a processz bájtban mért címtartománya és a lapméret hányadosa: a lapban mért címtartomány. • Méretcsökkentés 1: lapméret növelése (HW korlát) • Méretkezelés: maga a laptábla is kilapozható. VAX/VMS megoldás. • Csökkentés 2.: többszintű laptáblák: Intel: 2 szintes, Sun SPARC, Alpha: 3 szint, AMD x64: 4 szint. • Csökkentés 3.: Hasításos laptábla. IA64 • Csökkentés 4.: invertált laptábla. HP, IBM System 38. Vadász
27
9
Többszintes laptáblák Virtuális cím p1 p2 o 10
10
Második szintű laptáblák 0 1 2 3
12
Első szintű laptábla
b
0 1 2 3
+
... 1023
...
0 1 2 3
p2
1023
f
... 1023 Vadász
28
Hasításos (hashed) •
Hash függvény: hasító, szétosztó függvény, különböző p, q stb. lapcímeket ugyanarra a hash címre képez
Virtuális cím
Fizikai cím
p
f
o
p
hash
f
o
q
r
Vadász
29
Invertált laptábla • Címzés bitszélesség növekedéssel nem tud versenyt tartani a laptábla méret csökkentés. • Invertált tábla: bejegyzések lapkeretenként. Tartalmuk: – védelmi, módosítási maszk; – processz azonosító (pid); – a processz lapja (p).
• Leképzéshez: megnézni, adott processz adott lapja leképzett-e. • Nem szekvenciális keresés: hash módszerek. • Az ilyen rendszerekben asszociatív tár is! Vadász
30
10
Címleképzés gyorsítás asszociatív tárral • Translation Lookaside Buffer a CPU-ban (TLB). Nem nagy méretű. • Ennek egy bejegyzése: szinte ami a PMT egy bejegyzése. • Párhuzamos keresés a TLB-ben: címleképzés igen gyors, ha van találat. • Ha nincs találat: indul a normál laptáblás leképzés. (Ez eredményezhet laphibát. ) • Az asszociatív tár tartalma frissítődik. • Pl.: MIPS R2000 stb. processzorai (SGI), Intel stb. Vadász
31
Belapozási algoritmusok • A processzek hivatkozási lánca (Reference String): lapok sorozata. Előre megmondani nehéz. • Lehetséges behozási stratégiák (fetch policies): – Igény szerinti (Demand Paging). Egyszerű. • laphiba esetén belapozzuk a kérdéses lapot • eleinte magas laphiba ráta, később remélhető az "egyensúly"
– Szükséges és még néhány ("szomszédos" lap) • a "lokalitás elve" érvényesülhet
– "Mohó" belapozás • a szükséges és "sok" további. Megjósolható?
Vadász
32
A mennyiségi stratégia • Ha nincs stratégia: remélik az egyensúlyt • A munkakészlet (Working Set) modell (Denis, 1970) – A processz munka-lapkészlete (munkahalmaz): egy időablakban a bennlévő lapjainak halmaza. – Nincs laphiba, ha minden lapja a “pillanatnyi” munkakészlethez tartozik. – A “pillanatnyi“ helyzet valójában: egy időablak a hivatkozási láncon. – A munkakészleten eredetileg lapkészletet értettek, ma már – a munkakészlet lapkeret készlet. – A munkakészletet a processz élete során "igazíthatjuk" (adjustment). Vadász
33
11
Globális - lokális stratégiák • A munkakészlet modellel kapcsolatban a kilapozási problémák előjönnek: amikor belapozandó egy processz egy lapja, kilapozásra – a processz munkakészletéből válasszunk? (Lokális) – Más processzek munkakészletéből is? (Globális)
• Lokális kilapozáshoz: a munkakészlet nagyságát dinamikusan változtatják (határok között), a laphiba rátától függően. • A processzek munkakészleteinek egyensúlyát remélik (ez a Balance Set).
Vadász
34
Kilapozási algoritmusok • Page Replacement Algorithms • Amik befolyásolhatnak: – – – – – –
a bekövetkező lapigény nem jósolható igazán; lapok belapozási ideje; lapok belapozási sorrendje; hivatkozások gyakorisága; Lapok nem írhatósága – írhatósága, módosították-e; magának az algoritmusnak a “költsége“.
Vadász
35
FIFO algoritmus • A belapozási sorrend a meghatározó: minél régebben lapoztak be egy lapot, annál esélyesebb a kilapozásra. • Nyilvántartás egy láncolt listán: elejéről lapoznak ki, belapozott lap a végére. • Anomália: a régen belapozott, de most is használt, a gyakran használt lapokra.
Vadász
36
12
Második esélyes FIFO • • • •
Körkörös láncolt listán a belapozott lapok. Laponként egy hivatkozás bit. “Óramutató“ mutatja a lista “elejét“. Kilapozáshoz: ha a “mutatott“ lap hivatkozás bitje bebillentett, akkor azt törlik, és a mutató tovább lép. Ha nem (nem volt hivatkozás rá), akkor kilapozzák. • Mire az óramutató körbejár, újra bebillenhet a hivatkozás bit: kap egy második esélyt a lap. Ha nem billen, menthetetlenül kilapozódik. • Belapozott lap felvevődik a körre. • Ilyen a mach default memóriamenedzsere. Vadász
37
NRU (LRU) algoritmusok • Not (Least) Recently Used • Lokalitás elvből: a mostanában nem használatos lapok esélyesek a kilapozásra. Az “idő“ számít. • Láncolt listás nyilvántartás költséges volna! • Az “utolsó 8 idő-intervallum históriája“: – referencia bájt léptetés jobbra intervallumonként, – hivatkozott lapnál 1, nem hivatkozottnál 0 lép be. – A referencia bájtok rendezésre adnak lehetőséget: kisebb a bájt a kilapozásra esélyes lapoknál.
Vadász
38
NFU (LFU) algoritmusok • Not (Least) Frequently Used • A hivatkozások gyakorisága számít, nem a hivatkozások ideje. • Anomália: régen nagy gyakorisági frekvenciával használt lapok kiszorítják az újakat. Időszerűség is figyelembe veendő. • Öregedés (aging) a számlálómezőre ezen javít. • Költséges a megvalósítás, főleg a rendezés.
Vadász
39
13
A szegmentálás • “Többdimenziós“ címtartományok: – – – – –
• • • •
a kódnak, az adat szekcióknak, a veremnek, az osztott kódnak, kernel régiónak stb.
A címleképzésben a blokkméret nem fix. A virtuális cím: v = (s,d) Processzenként szegmens tábla. Kevesebb bejegyzés. Ki-be söprés (swapping in-out), ha szükséges. Vadász
40
Szegmensenkénti címleképzés Base Address of Segment Table b
Virtuális cím s
d
Segment Map Table +
s
b+s
m a
l
s'
+
s s' d a l m
Fizikai cím s' d
szegmens szám szegmens cím diplacement (eltolás) cím a swap tárolón szegmens hossz státus (valid, rwx stb)
Vadász
41
A stratégiák • Allokációs stratégia – egyidejűleg szegmensnyit a fizikai memóriában
• Behozási stratégia – igény szerinti a szegmensre
• Kisöprési stratégia – LRU
• Elhelyezési stratégia – First vagy next fit
Vadász
42
14
Szegmensenkénti leképzés vagy lapozás: lehetőségek • Tiszta lapozó rendszerek (Pure Paging) • Tiszta szegmentáló rendszerek. • Szegmentáló és lapozó rendszerek. – – – –
Ekkor a “teljes“ kontextus ki-besöprődik, szegmensekre külön laptáblák, lapozás a szegmenseken belül. Ma ezek gyakoriak.
Vadász
43
A "swap" eszköz/fájl struktúra • A mai rendszerekben lehet – swap/paging device (a másodlagos tároló partíció), – swap/paging file (a másodlagos tároló a fájl), – mindkettőt úgy foghatjuk fel, hogy lapméretű blokkok sora.
• Akár szegmensenkénti leképzés, akár laponkénti leképzés van: swap/paging eszközről/fájlról beszélünk. • Ami érdekes lehet: hogy menedzselik a swap/paging eszközön a szabad területet. Vadász
44
Klasszikus Unix swap eszköz • Adott a swap partíció, 0-n unitok (blokkok) • Adott a szabad területek térképe (map, map-entries): in core (esetleg a 0-ik blokkon) – egy bejegyzés: addr+hossz pár, szabad területet jelez.
• Foglalás: first-fit startégiával, a szabad terület elejére, a bejegyzést "igazítja" (el is tünteheti) • Felszabadítás: szomszédos szabad területek összefűzésével – ha előtte + utána szabad: a 2 bejegyzésből 1-et csinál, – ha előtte vagy utána szabad: a bejegyzést igazítja
• Ne feledjük: csak az irható lapok/régiók számára foglanak helyet a swap eszközön/fájlon. Vadász
45
15
Linux swap eszköz • A swap eszköz elején 4086- bájt hosszú bit-térkép (4096-10: 'SWAP_SPACE' füzér). – Ebből: max 4086*8-1=32 687 lap menedzselhető egy eszközön. – Ez kicsi, ezért több swap eszköz lehet (ma max 8)
• Bebillentett bit kettős jelentése: – adott régió lapját ide lehet kilapozni, – újabb régió swap területe itt nem foglalható.
• Ne feledjük: csak az irható lapok/régiók számára foglanak helyet a swap eszközön/fájlon. Vadász
46
Az NT memóriamenedzselés • • • • • • • •
Virtuális, lapozós; Virtual Address Descriptor-okat (VAD) használ; TLB-t is használ; Kétszintes laptáblás (osztott memóriához + 1 szint); Lapkeret adatbázist is használ; Munkakészletet használ; Önálló taszk a kilapozó; Igény szerinti belapozós.
Vadász
47
Az NT MM virtuális • 32 bites címzés: 232 lineáris címtartomány (4GB) – A felső 2GB rendszer címtartomány, kernel módban látható (Pentium 1GB). – Az alsó 2GB taszkonként egyedi címtartomány (Pentium 3GB).
• Vannak lefoglalt V címtartomány szakaszok. – Statikus allokálás: mikor a taszk készül, akkor foglalják ezeket a szakaszokat. – Dinamikus allokálás (alloc, malloc, stack bővítés stb.)
Vadász
48
16
A Virtual Address Descriptorok • A VAD a lefoglalt címtartományok leíróit (kezdő-végcím, néhány további adat) tartalmazza, • bináris fa struktúrába rendezve (gyors keresés). • Hol van szerepe? – A címleképzés elején: először a VAD struktúrát nézik, lefoglalt címterületre történt-e a hivatkozás. – A memória allokálásnál: új VAD leírót kell felvenni + VM-t hozzárendelni az új címtartományhoz. Ez súgja a 2 szintet: • Először csak VAD leírót veszünk fel (alloc), • Amikor tényleg használni akarjuk az új mem-et (committing), elkészítjük a laptábla bejegyzéseket stb.
– Leképzett fájl (Mapped File) létrehozásánál (ld. később). – Nincs szerepe a lapozásnál (ez már nem a címtartomány síkja!) Vadász
49
A címleképzés • Miután a VAD-on túl vagyunk, indul a TLB vizsgálat. – TLB: kisméretű asszociatív tár, 2 oszloppal • • • • •
egyikben a VA felső 20bitje (párhuzamos keresés ebben), másikban a laptábla rekord (ld. később). Találat esetén nyerő az ügy! Ha nincs találat: indul a “szokásos“ laponkénti leképzés. Ha változás van a Page Dir-ben vagy Page Table-kban, a TLB frissül.
Vadász
50
Laponkénti leképzés • Lap (Page): – – – – –
a Virtual Address Space fix méretű része, a Virtual Memory fix méretű blokkja. Létezik (összetett) lapcím, létezik lapon belüli eltolás (offset), a kettő adja a VA-t.
• Lapkeret (Page-frame): – – – –
a RA-space fix méretű része, a RM fix méretű blokkja (belefér egy lap). Létezik lapkeret cím, a lapkeret cím és az eltolás (offset) adja a RA-t, Vadász
51
17
Az NT 32 bites virtuális címe 10 bit
10 bit
12 bit
Page Dir Index Page Table Index
Offset
A lapméret Az offset szélesség: 12 bit
Page Dir (Lapkatalógus)
Page Tables (Laptáblák)
212 = 4KB
A lapkatalógus méret (Taszkonként 1 db)
PD record
210 = 1024 bejegyzés Egy bejegyzése: 4 Byte PT record
Egy laptábla méret (Taszkonként szükséges számú laptábla van) 210 = 1024 bejegyzés Egy bejegyzése: 4 Byte Vadász
52
Egy laptábla bejegyzés tartalma • Státusz bitek (érvényes, nem érvényes, prototípus laptábla index jelzésére)
• Védelmi bitek – – – – – – –
Csak olvasható (read only) lap Teljes jogú (r/w) lap Csak futtatható (exec only) lap (spec. processzorhoz) Figyelt (guarded) lap (elérése kivételt generál) Tiltott lap (elérése kivételt generál) Zárolt lap (nem kilapozható) Módosításkor másolt (copy on write) lap (halogatott memória taktikához, ld. később)
• Címek Vadász
53
Laptábla bejegyzésben a címek • Lapkeret cím • Másodlagos tároló blokk cím • Prototípus laptábla index. Osztott memória-használathoz (akár klasszikus, akár leképzett fájl) további szint a prototípus laptábla. Miután ugyanazt a lapkeretet kell használni, nem indexelhetjük közvetlenül. Pl. ha kilapozzák, minden laptáblába be kellene írni, hogy érvénytelen, s ki tudja, hány taszk használja. Ilyenkor a prototípus laptáblában rögzítettek az védelmi bitek! Szerencsére mindez transzparens!
Vadász
54
18
Laponkénti leképzés • Nincs találat a TLB-ben: • Veszik a lapkatalógus címét (regiszterben), • hozzáadják a VA felső 10 bites indexét: ez bemutat a katalógusba. • Veszik ennek bejegyzését: ez egy laptábla cím. Hozzáadják a VA második 10 bites indexét: ez mutat egy laptábla rekordra. • Veszik a tábla rekordját: – a státusból eldől: laphiba van-e. Indulhat a kezelője, ezt segíti a másodlagos tároló cím a rekordban ... – Nincs laphiba: vehető a rekordból a keretcím (további szint a prototípus laptábla esetén). • Keretcím és a VA offsettje adja a RA-t. Vadász
55
Halogatott gazdálkodási taktika • Lehetnek módosításkor másolt lapbejegyzések. • Osztott memóriahasználat halogató taktikája megvalósítható. – PL. POSIX taszk-kreációban a gyermek kontextusa (kezdetben az adatok is) megosztódnak a szülőjével: a lapjaik ilyen lapbejegyzéseket kapnak. Legtöbbször a gyermek nem módosítja az adatokat sem. – Ha bármelyik (szülő, gyermek) mégis módosít, az ilyen lapokat az MM lemásolja új lapkeretbe, és a laptábla bejegyzéseket frissíti (a copy on write bejegyzést törli, a módosítónál az új lapkeret-hivatkozást jegyzi fel, a másiknál meghagyja a régit.)
Vadász
56
A leképzett fájl objektum • Különleges memóriaallokáció! • A fájl objektumot beillesztik a taszk címtartományába (VAD leíró készül, ez a címtartomány a nézet: view). • A címtartományhoz lapkatalógus bejegyzés(ek), laptábla(k) készülnek, címezhetők majd lapkeretek, amikre a be- és kilapozás a kérdéses fájlra történnek (és nem a Paging Filera). Mindezt az MM intézi majd. • Ezen a címtartományon (a view-on) a taszk úgy látja a fájlt, mintha teljes egészében a memóriában volna! • Több taszk leképezheti ugyanazt a fájlt: osztoznak rajta • A klasszikus osztott memória pedig a leképzett fájl speciális esete: a leképzett fájl ilyenkor a Paging File.
Vadász
57
19
A fizikai memória nyivántartása • Létezik lapkeret adatbázis (Page Frame Database), annyi bejegyzéssel, ahány lapkeret van. • Egy bejegyzés tartalma: – Érvényes (valid) keret: használatban van, benne egy lap. – Szabad (free) keret. Taszk exitjénél az MM a hozzá tartozó kereteket felszabadítja. – Nullázott (zeroed). Szabad és 0-kkal felülírt keretek. (A C2 biztonsági előírás követelménye). – Készenléti (standby) keret: már felszabadított, de még benne az érintetlenül hagyott adatok. Visszakérhetők belapozás nélkül, csak érvényesre kell állítani őket. Az átmeneti bit is bebillentett. – Módosított (modified) keret: írta a taszk, így ha ha lemond róla, elveszik tőle és ki akarják osztani másik taszknak, előtte ki kell írni! Az átmeneti bit (transition flag) is bebillentett. – Hibás (bad) keret: megbízhatatlanul működőre ráírja az MM. – Visszamutató a taszk laptábla bejegyzésére (ahol értelmes). Vadász
58
Keretállapotok és listák • Egy taszk egy laptábla bejegyzése nemcsak a lapkeretet címezi, hanem a lapkeret adatbázis bejegyzést is! Nemcsak érvényes, hanem módosított és készenléti lapkeretre is mutathat. • A visszamutató azért kell, mert ha az MM fel akar használni egy módosított vagy készenléti keretet, javítania kell a laptábla bejegyzést érvénytelenre. • Az MM a kölönböző állapotú kereteket 5 láncolt listán nyilvántartja! • Van szabad, készenléti, módosított, nullázott és hibás lista. • A nullázott, a szabad és a készenléti lista elemei az ún. felhasználható keretek.
Vadász
59
A módosított lapíró • A Modified Page Writer egy állandóan futó rendszertaszk. • Ha a felhasználható keretek száma egy határ alá esik, lemezre írja a módosított kereteket, és átteszi azokat a készenléti listára (növeli a felhasználható készletet).
A lapkeret-adatbázis védelme • Forgózárral (spinlock semaphor) védik. • Többprocesszoros rendszernél is csak egy taszkot szolgál ki a VMM, • sok processzornál sorbaállás van a VMM kezelőhöz. Ez a közös memória hátránya.
Vadász
60
20
Laphiba kezelés • Az érvénytelen laptábla bejegyzésig eljutott a címleképzés, bekövetkezett a laphiba. De ott van a másodlagos tároló cím: mit kellene belapozni. • A kezelő először a nullázott kereteket használná. • Ha nincs ilyen, akkor egy szabad keretet. • Ha ez sincs, akkor készenléti keretet. • Ha ez sincs: valamely keretet fel kell szabadítani. • Az NT lokális, legrégebben betöltött (NRU) algoritmust használ. • A felszabadított kereteket a handler nem lapozza ki, hanem a készenléti vagy módosított listára teszi! (Ezért akár rögtön vissza is kérhetők belapozás nélkül!) Vadász
61
Laphiba kezelés • A kezelő kilapozás helyett csak “listára tesz” Módosított sor
Készenléti sor
Szabad sor
Nullázott sor
Vadász
62
A taszkok munkakészlete • Minden taszk kap Working Set-et: ez lapkeret-készlet. • Előírt max-min értéke van a készletnek, taszkonként ez változik. • Ha a taszk eléri a max értékét, újabb memóriafoglalási kérelmek esetén „kilapoznak” a készletéből (akkor is, ha vannak szabad keretek: ne sajátítson ki sokat egy taszk!) • Automatikus munkakészlet szabályozás (Workig Set Trimming) folyik: – a taszkok laphiba rátájától függően csökkentik vagy növelik (utóbbit ha vannak szabad keretek) a munkakészletük max. méretét. – Bizonyos esetekben a min. értékeket is.
Vadász
63
21
Összefoglalva kilapozás • Ha a VMM úgy találja, indítja a módosított-lap író taszkot. Ez kilapoz, csökkenti a módosított- és növeli a készenléti listát. • Ha ez nem segít, nézi a taszkokat, és azok munkakészletét a min-re csökkenti. • Ha ez sem segít, valamennyi taszk munkakészletét, annak min értékét csökkenti. • Ha ez sem segít, akkor menjünk memóriát vásárolni! • Ha a memória krízis megszűnik, a laphiba rátától függően készletnövekedés is lehet: beállhat újra az egyensúly.
Vadász
64
A belapozás • Tulajdonképpen igény szerinti belapozás (Demand Paging) van, • de a szükséges lapot közrefogó néhány lapot is belapozzák (ha a munkakészlet megengedi). (Cachingnek nevezik)
Vadász
65
A védelem • Első szintje a VAD struktúrában: – a kernel és felhasználói címtartományok már itt szétválnak.
• A taszkok egymás felhasználói szintű címeiket azért nem érhetik el, mert saját laptábláik vannak. • A közös memória a prototípus laptáblák segítségével mégis megoldható. • Taszk saját memóriáját is védheti a laptábla védelmi bitjeivel.
Vadász
66
22
Megjegyzések még • A gyorsítótárak – – – –
Ma már két szintű (L1 és L2 Cache), külön ICache DCache. Szerencsénkre ez tisztán hardveres és transzparens ügy! Mindenestre ami Cache-ban van, az be is van lapozva!
Vadász
67
Most már értjük, hogy az NT memóriamenedzselés • • • • • • • •
Virtuális, lapozós; Virtual Address Descriptor-okat (VAD) használ; TLB-t is használ; Kétszintes laptáblás (osztott memóriához + 1 szint); Lapkeret adatbázist is használ; Munkakészletet használ; Önálló taszk a kilapozó; Igény szerinti belapozós.
Vadász
68
Operációs rendszerek Memória menedzselés Vége
23
