39 - Virtualizace paměti, stránkovací a nahrazovací algoritmy Flashcards

1
Q

Organizace paměti - FAP, LAP a virtualizace

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Typy organizace paměti

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Organizace paměti - Mapování LAP na FAP - ÚSEKY PEVNÉ VELIKOST + ÚSEKY PROMĚNNÉ VELIKOSTI

A

Ú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í
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Organizace paměti - Mapování LAP na FAP - segmentace + stránkování

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Stránkování

A

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ě

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Stránkování - Virtualizace + výpadek stránky

A

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

  1. Výběr volného rámce
  2. Pokud není žádný rámec volný, výběr stránky, která bude odstraněna – nahrazovací algoritmy
  3. Zavedení požadované stránky a nastavení tabulky stránek
  4. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly