39 - Virtualizace paměti, stránkovací a nahrazovací algoritmy Flashcards
Organizace paměti - FAP, LAP a virtualizace
Fyzický adresový prostor (FAP) - adresace paměti přímým přístupem, pohled na paměť z pohledu procesoru
Logický adresový prostor (LAP) - paměť z pohledu procesu, která se liší od fyzického přístupu k paměti
Virtualizace - při běhu procesu nemusí být celý obsah adresového prostoru trvale v paměti (některé úseky logické paměti mohou být např. swapovány na disku (stránkování na disk))
Typy organizace paměti
Jeden úsek paměti - LAP=FAP
- jen jeden program v paměti
- OS má přidělenu část, zbytek jednomu programu (MS-DOS)
- Monoprogramování BEZ OCHRANY PAMĚTI - posléze zavedeny segmenty
Společný adresový prostor
- všechny programy mají společný adresový prostor mapovaný na fyzickou paměť, pouze jsou zavedeny na jiná místa.
- je potřeba dynamická realokace (při zavedení programu se adresy do paměti změní podle místa zavedení)
- ale jednoduchá správa a přidělování paměti.
- Ochrana paměti není implicitní (programy mohou i do paměti jiných programů), lze řešit:
- mezní registry
- chráněný režim OS (programy mají ale omezený LAP).
Oddělené adresové prostory
- každý program má k dispozici celý LAP, každý LAP mapován někam do FAP
- ochrana oddělením při mapování
- ale mapování složitější (podpora hardware - převod adres v každé instrukci)
Adresový prostor jádra
a) oddělený LAP jádra (volání jádra musí přepočítat adresy),
b) sdílený s procesem volajícím jádro (horní část LAP rezervovaná pro jádro, v uživ režimu nepřístupná)
Organizace paměti - Mapování LAP na FAP - ÚSEKY PEVNÉ VELIKOST + ÚSEKY PROMĚNNÉ VELIKOSTI
Úseky pevné velikosti
- FAP dělěn na úseky pevné velikosti, kam se programy musejí vlézt
- Programy pevnou velikost
- Programy jsou mapovány do vhodných volných úseků
- Fronty procesů čekajících na úsek
- Společné fronta - přidělen nejmenší postačující volný úsek
Interní fragmentace - nevyužitá část přiděleného úseku
Odkládání (swapping) - pozastavený proces může být dočasně odložen do odkládacího prostoru aby se úsek uvolnil
!!! Úseky proměnné velikosti !!!
- mění velikost úseků dynamicky dle požadavků (spojování sousedních volných nebo dělení při zavedení programu)
Externí fragmentace - volná paměť není souvislá
Strategie přidělování úseků
- First fit - první dostačující
- Next fit - první dostačující za místem posledního přidělení
- Best fit - nejmenší dostačující
- Worst fit - největší volný (menší ext. fragmentace, ale fragmentuje největší úseky - interní fragmentace)
Alokace úseků o velikosti 2^n
- používá malloc(), přiděluje nejmenší postačující úsek o velikosti 2^n
- seznamy volných úseků jednotlivých velikostí - přiděluje se první na seznamu
- pokud není dostupný volný úsek alokuje se blok K nových úseků
Buddy systém
- Linux - systémová paměť
- alokace úseků o velikosti 2^n + spojování úseků
- pokud není volný úsek - větší úsek se rozdělí na poloviny (vlastně takový strom, dělíme volný prostor na poloviny)
- při uvolnění se sousední bloky spojují
Organizace paměti - Mapování LAP na FAP - segmentace + stránkování
Segmentace
- přiděluje každému procesu úseky proměnné velikosti, které mají adresu báze + limit
- tabulka segmentů může být globální nebo pro každý proces zvlášť
- různá ochrana segmentů ale stále externí fragmentace
- LAP rozdělen do segmentů - úseků proměnné velikosti: kódový, datový a zásobník
- logická adresa = segment + offset v něm
- Tabulka segmentů obsahuje pro každý segment bázi a limit (kde začíná a jak je velký) (tabulka pro každý proces nebo globální)
- umožňuje ochranu segmentů (zabraňuje programu zapisovat do kódového segmentu)
- namísto 1 spojitého bloku paměti jsou programu přidělovány jednotlivé segmenty - zmírňuje externí fragmentaci, ale přetrvává
Stránkování
- dělí FAP na rámce stejné velikosti
- dělí LAP na stránky stejné velikosti
- velikost rámce = velikost stránky (obvykle 1kB až 16kB)
- Tabulka stránek pak určuje mapování stránek na rámce
- logická adresa - číslo stránky a offset
- Zamezuje externí fragmentaci (v LAP), interní fragmentace max o velikosti velikost stránky/2
- Ochrana musí být na úrovni stránek
Segmentace se stránkováním
- segmenty jsou stránkovány
segment báze + offset -> lineární adresa = číslo stránky + offset -> fyzická paměť
Stránkování
Tabulka stránek
-> zobrazuje LAP na FAP (pro každé číslo stránky obsahuje číslo rámce ve kterém je stránka umístěna)
Obsah tabulky stránek (i386)
- číslo rámce
- flagy zápisu, systémové stránky, označení dirty (stránka byla modifikována) a přítomnosti v paměti, …
Inverzní tabulka stránek
- indexuje podle rámců ne podle stránek
- mnohem jednodušší tabulka a malá režie, ale hledání je komplikované a sdílení paměti ještě více
- PowerPC, HP PA RISC
Rychlost stránkování
- překlad LAP a FAP se musí uskutečnit při každé instrukci adresující paměť (5-10ns asi 10% z času přístupu do paměti)
Translation Look-Aside Buffer (TLB) - stránkovací cache (cca 10x zrychlení)
= je vyrovnávací paměť v HW pro překlad adres
- poslední/nejčastjší překlady adres jsou uloženy v rychlé (SRAM) asociativní paměti (přístup je zredukován z 50ns na 5ns)
- Čím větší úspěšnost TLB, tím rychlejší průměrný přístup.
- Při přepnutí kontextu se TLB vyprázdní (u SPARC ne, přidává položkám i číslo procesu)
Velikost tabulky stránek -> pro 32bit adresu 1MB tabulka stránek
Víceúrovňová organizace stránek
- adresa stránky se dělí na indexy jednotlivých tabulek, položky tabulek pak vybírají bázi následující tabulky
(adresa = offset první tabulky (ta má bázi druhé) + offset druhé tabulky)
- (tj. tabulka tabulek stránek)
- Např. Intel - 2 úrovně (Page Directory a Page Table), AMD64 - 4 úrovně
Stránkování - Virtualizace + výpadek stránky
Výpadek stránky = pokud požadovaná stránka není v paměti (díky virtualizaci)
- výpadek stránky výrazně zpomaluje ->je nutné minimalizovat počet výpadků
Zpracování výpadku stránky
- Výběr volného rámce
- Pokud není žádný rámec volný, výběr stránky, která bude odstraněna – nahrazovací algoritmy
- Zavedení požadované stránky a nastavení tabulky stránek
- Restart instrukce, která způsobila výpadek
Swapping = Odkládání stránek na disk - umisťování vyřazených stránek na disk do swapu (swap se nemusí použít, ale pak nelze stránky vyřadit a dojde paměť). Thrashing = je stav, kdy počet výpadků překračuje přípustnou mez, většinu výkonu spotřebuje režie stránek (nejen algoritmus, ale i I/O swapu).
Stránkovací algoritmus = udává, kdy a kolik stránek se zavede z disku do paměti, které rámce se jim přiřadí a případně, které stránky mají být z paměti odstraněny.
- Snaha minimalizovat výpadky (nahrazením nepoužívaných apod.).
1) Výběr zaváděných stránek
Kdy:
- prefetchingem (dopředu)
- zavádění na žádost (při výpadku)
Počet zaváděných stránek:
- celý LAP (neefektivní)
- jediná stránka (neefektivní)
- stránky a okolí (předvídá přístup na sousední stránky)
2) Umísťování stránek - nemá vliv na výpadky, ale na rychlost odkládání (souvislý kus se odloží rychleji).
3) Nahrazovací algoritmy -
- určuje, které stránky vyřadit z paměti, snaha o minimalizaci následných výpadků. Problém je, že nezná následující sled stránek, takže pouze odhaduje z minulosti.
- S pevným počtem stránek v paměti
- OPT - Optimální - hypotetický, odstraňuje stránku která bude nejdéle nepoužita (čte budoucnost)
- LRU - Last Recently Used - odstraňuje nejdéle nepoužitou stránku, aproximuje OPT (zásobník použití, vyhazuje nejspoednější)
- NRU - Not Recently Used - odstraňuje v poslední době nepoužitou stránku (1-bitová aproximace LRU - při použití bit nastaven, bit vynulován po intervalu)
- LFU - Least frequently used - odstraňuje nejméně používanou stránku (může ale nahradit právě použitou), při rovnosti LRU
- FIFO - odstraňuje nedříve zavedenou stránku (nejdéle v paměti, ale mohla být také nejvíce používána)
- LIFO - odstraňuje nejpozději zavedenou stránku (nejpozději zavedná)
- Clock - cyklický ukazatel, prochází a testuje příznak použití, je li nastaven, vynuluje a jde dál, není-li - našel oběť
- Second-chance NRU - Clock + příznak modifikace (pokud nastaven, stránka se zapíše na disk, bit se vynuluje a jdeme dál)
- S proměnným počtem stránek v paměti
- VMIN - Optimální - hypotetický, v paměti se drží stránky které budou použité v zadaném časovém intervalu v budoucnosti
- WS - Working Set - v paměti se drží stránky použité v zadaném časovém intervalu - pracovní množina stránek (nepraktické - nutno často aktualizovat)
- Page Fault Frequency - takový balance s velikostí pracovní množiny
- pokud stránky vypadávají častěji než je velikost pracovní množiny, pracovní množinu zvětší
- pokud je interval mezi výpadky větší, jsou odebrány všechny stránky nepoužité od posledního výpadku - zmenšování pracovní množiny
