2010/2011 ZS
P i i počítačů Principy čít čů
PAMĚŤOVÝ SUBSYSTÉM z pohledu OS
2010/2011 ZS
Správa paměti • OS je správcem prostředků, tedy i paměti – přidělování procesům – zajištění ochrany systému i procesů – zajištění požadavků aniž by došlo k zablokování
2010/2011 ZS
Hierarchie pamětí mikropočítače
vnějšíí
vnnitřní
registry vyrovnávací á í paměť hlavní paměť odkládací (sekundární) paměť archivní hi í paměť ěť
procesor L1 L2 cache L1,L2 h „RAM“ pevnýý disk di k CD, DVD, pásek
2010/2011 ZS
PŘIDĚLOVÁNÍ PAMĚTI • (spojité - nespojité) • Přidělování v jednouživatelských OS:
2010/2011 ZS
Přidělování v prostředí více procesů • Problém relokace a ochrany • Základní metodiky rozdělení paměti – pevné oddíly • •
paměť rozdělena na oddíly specifické velikosti, procesy ve frontách podle požadované velikosti
– volné oddíly •
procesy dostávají paměť podle potřeby
2010/2011 ZS
Relokace • Při psaní programu nejsou známy absolutní adresy, přiřazují se „později“: – Při překladu • je-li známo absolutní umístění
– Při zavádění • OS rozhodne o umístění • kód se generuje s relokacemi + relativním adresováním
– Za běhu • proces se může za běhu „stěhovat“
2010/2011 ZS
Řízení paměti • Bitová mapa – Bloky stejné délky, „paragrafy“
• Spojový seznam – Bloky různých délek – Je třeba řešit: • •
který blok spojování volných bloků
2010/2011 ZS
Strategie přidělování • • • •
First Fit Next Fit Best Fit Worst Fit 6 4
5
3
10
20
2010/2011 ZS
Virtuální paměť • Oddělení adresového prostoru procesu od adresového prostoru fyzické paměti • Transparentní (z hlediska procesu) převod mezi adresami
2010/2011 ZS
Virtuální paměť • Ochrana • • • •
Cena Snížení nebezpečí uváznutí S íž á fragmentace Snížená f t Pohodlí – flat address space – stejný svět – rozšíření / zmenšení prostoru
2010/2011 ZS
Virtuální paměť • Klíč – převod virtuálních adres na fyzické (parciální zobrazení) • 2 základní metody: – stránkování – segmentace
2010/2011 ZS
Stránkování f i ká paměť fyzická ěť
rámec á 0 rámec 1 ... rámec N-1
správce á
představa ř d procesu
stránka tá k 0 ... stránka i ... stránka M-1
2010/2011 ZS
Stránkování • Virtuální adresový prostor rozdělen na bloky stejné velikosti – stránky (pages) • Fyzický adresový prostor rozdělen na bloky stejné velikosti jako stránky – rámce (frames)
2010/2011 ZS
Pohled uživatele vs realita • Pohled uživatele: – spojitý adresový prostor
• Skutečnost: – stránky „rozházeny“ po hlavní i sekundární paměti, některé ěkt é chybějí h bějí zcela… l
• stránkování je neviditelné pro proces/uživatele!
2010/2011 ZS
• Adresa ve virtuálním prostoru vyjádřena jako dvojice [p,d] [p d] • Mechanismus stránkování převede číslo stránky á k p na odpovídající d íd jí í čí číslo l rámce á p’’ (lze-li to) – mapování. • Adresa ve fyzickém prostoru je pak vyjádřena dvojicí [p [p’,d] d] • Neexistuje-li mapování, dojde k výpadku stránky (page fault)
2010/2011 ZS
Překlad adres • Překlad zajišťuje hardware (procesor/MMU) • Mapování definuje operační systém • Stránkovací tabulky – Struktury potřebné k zajištění mapování – adresa rámce pro danou stránku – příznaky (platnost, přístup, …)
2010/2011 ZS
Překlad adresy u stránkování page number
page offset
virtuální adresa (lineární )
stránkovací tabulka
fyzická adresa fy
příznaky
rámec
2010/2011 ZS
Problémy stránkování • interní fragmentace • velikost stránkovacích tabulek 32b adresy → 4GB, 4GB stránky 4kB ⇒ stránkovací tabulka má 1M položek
• rychlost hl přístupu ří do d stránkovacích á k í h tabulek b l k instrukce s paměťovými operandy...
2010/2011 ZS
Výběr velikosti stránky • Malé stránky malá lokalita referencí (typ. < 256) + menší fragmentace - velké stránkovací tabulky
• Velké V lké stránky á k + malé stránkovací tabulky + lépe vyhovuje I/O - vetší fragmentace
2010/2011 ZS
Reálný příklad (4MB stránky)
2010/2011 ZS
Úpravy • Víceúrovňové stránkování řeší problém velikosti tabulek
• TLB / Asociativní paměť řeší problém rychlosti přístupu
• Nulaúrovňové stránkování nejsou stránkovací tabulky, pouze asociativní paměť
• Inverzní I í stránkovací á k í tabulky b lk organizace g nad rámci, nikoli stránkami
2010/2011 ZS
Reálný příklad (4kB stránky) tá k ) - víceúrovňové stránkování
2010/2011 ZS
TLB • lokalita chování programů • asociativní paměť Platné
Stránka
Dirty y
Ochrana
Rámec
1
125
1
RW
654
1
44
0
RW
132
1
485
1
RW
12
1
55
0
RX
142
1
111
0
RX
54
1
108
1
RW
54
1
88
0
RX
543
0
2010/2011 ZS
Inverzní stránkovací tabulky • FAP menší než VAP • 64-bitové CPU – IA-64
VA
p
f
d
hash f fn
hash table
p f
d
FA
2010/2011 ZS
Záznam stránkovací tabulky
2010/2011 ZS
Výpadek stránky Chybí převod VA→FA, tedy nelze přistoupit k datům, tedy nelze vykonat instrukci Ö výjimka: • uložit kontext (stav CPU) • zjistit VA • zkontrolovat platnost adresy a oprávnění přístupu • nalézt lé t rámec á pro mapování á í • zrušit aktuální mapování rámce (a příp. uložit!) • načíst stránku do rámce • zavést mapování • obnovit kontext
2010/2011 ZS
Algoritmy výměny stránek Replacement policy • • • • • • • •
Optimální stránka Random Working set FIFO – First in, first out LRU – Least Recently Used NRU – Not N tR Recently tl Used U d NFU – Not Frequently q y Used CLOCK – Hodinový algoritmus
2010/2011 ZS
Optimální stránka • Vybrána bude stránka, na kterou přistoupíme za nejdelší dobu – nelze obecně implementovat
Random • Stránka bude vybrána y zcela náhodně
2010/2011 ZS
Working Set Model • Proces může být v RAM tehdy a jen tehdy, pokud všechny jím používané stránky mohou být g ) v RAM ((“all or nothing”) – používané znamená přístup v rozsahu okna přístupů
• St Stránkovací á k í algoritmus l it vyhazuje h j jen j stránky, tá k které nejsou ve Working Set – problém je jeho udržování
2010/2011 ZS
FIFO • klasická fronta: nahrazení stránky, která byla v paměti nejdéle – odstraňuje i často používané stránky – zajímavost: „Beladyova anomálie“: zvýšení počtu rámců může vést i ke zvýšení počtu výpadků
2010/2011 ZS
Beladyova anomálie
2010/2011 ZS
FIFO s druhou šancí • úprava FIFO zavedením „druhé šance“ – pokud A=1, zařadím na konec fronty – nevykazuje anomálii
2010/2011 ZS
NRU – Not Recently Used • Příznaky Accessed, Dirty (nastavuje HW, nuluje OS)
• Algoritmus: periodické nulování A při výpadku volím náhodně ze tříd v pořadí A-D: 0-0, 0-1, 1-0, 1-1 (tj. z nejnižší neprázdné třídy)
2010/2011 ZS
LRU – Least Recently Used • dlouho nepoužívané stránky asi nebudu potřebovat, naopak nedávno používané asi ano • seznam, seznam který je při každém přístupu upravován • HW realizace: – 64b čítač, který CPU při přístupu uloží do PTE, vybírá se nejnižší – matice n×n, při přístupu do rámce k nastavíme k-tý řádek na 1 a k-týý sloupec p na 0 – vybírá se řádek s nejméně jedničkami
2010/2011 ZS
NFU – Not Frequently Used • SW řešení LRU • Čítač u stránek: – periodicky přičítáme A – vybíráme stránku s nejnižší hodnotou čítače
• Problém – nezapomíná a znevýhodňuje mladé • Úprava – stárnutí (aging): – posunu doprava, přičtu doleva
2010/2011 ZS
CLOCK – Hodinový algoritmus • • • • •
“Second chance” Stránky jsou zařazeny v kruhovém seznamu Nastavování A Při výpadku: Je-li A=0, vyměním, je-li A=1, A=1 nastavím A=0 a posunu se
2010/2011 ZS
Mapovací strategie • Lokální – každý proces má svou množinu rámců, ve které pprovádí mapování p ((viz Working g set))
• Globální – všechny š h procesy sdílí dílí všechny š h rámce á
2010/2011 ZS
Implementační problémy • znovuspuštění vs. dopracování instrukce • sdílení stránek • odstranění položky v TLB při změně mapování
2010/2011 ZS
Segmentace f i ká paměť fyzická ěť
segment g M
správce á
představa ř d procesu
segment 0
segment i segment i ... segment 0
segmentt M-1
2010/2011 ZS
Segmentace • Segment – nezávislý adresový prostor 0..limit • Organizace podle potřeb a struktury programu – kód, kód data data, zásobníky zásobníky, …
• Segmenty různé a měnitelné velikosti • Umístění segmentu v paměti je pro proces neviditelné (jako u stránkování) • Výpadky segmentů obdobně jako u stránkování
2010/2011 ZS
Překlad adresy u segmentace segment number
segment offset
virtuální adresa (logická)
tabulka segmentů
+
příznaky
adr. začátku segmentu
fyzická adresa (lineární )
2010/2011 ZS
2010/2011 ZS
Problémy segmentace • Při výpadku je nutné vyměnit celý segment – a segment může být velký
• Segment nemůže být větší než FAP • Dynamická alokace → externí fragmentace „checkerboarding“ – ale lze jje sesypat yp
2010/2011 ZS
příklad kombinace segmentace a stránkování Logická adresa (Logical address) Jednotka řízení paměti ((MMU - memoryy management unit)
46
Segmentace Lineární adresa (Linear address) 32
Stránkování Fyzická adresa ((Physical ys c address) dd ess) 32 (32-36)
2010/2011 ZS
Možný překlad adresy segment number
page number
tabulka segmentů
virtuální adresa page offset
stránkovací tabulka(y)
+
fyzická adresa
2010/2011 ZS
Možný překlad adresy segment number
page number
tabulka segmentů
virtuální adresa page offset
stránkovací tabulka(y)
+
fyzická adresa
2010/2011 ZS
Segmented paging Rozdělení (segmenting) stránkovací tabulky + sdílení kódu + zmenšení nároků na stránkovací tabulku - větší komplexita, overhead - stránkovací tá k í tabulky t b lk stále tál musíí být spojité jité - každý ý přístup p p do paměti p znamená 2 vyhledání y
2010/2011 ZS
Srovnání Segmentace • programátor musí vědět g • externí fragmentace • separátní ochrana • sdílený kód, kód separátní kompilace
Stránkování • programátor nemusí vědět g • interní fragmentace
