Otázka č. 12 - Logický adresový prostor a využití rámců

Zadání: LAP procesu · kradení stránek · sdílená a dočasně sdílená paměť

• Navazuje na otázku č. 11 (Virtualizace paměti). Tam jsme si řekli jak se adresa přeloží, tady jde o to, co v LAP vlastně je a jak se hospodaří s rámci, kterých je vždycky výrazně méně než stránek.

LAP procesu

• Každý proces má svůj vlastní LAP, nezávislý na fyzické paměti (RAM).
• LAP je rozdělen na stránky, fyzická paměť na rámce. Stránka a rámec mají stejnou velikost (typicky 4 KiB), takže je jedno, do kterého rámce se stránka uloží.
• O překlad logické adresy na fyzickou se stará MMU (Memory Management Unit) pomocí tabulky stránek. Každý proces má vlastní tabulku, takže dva procesy můžou používat stejnou logickou adresu a přesto sahat do jiné fyzické paměti.

Dvě části LAP

1. Nepoužité adresy - nemají žádnou fyzickou reprezentaci (neexistují pro ně rámce). Tvoří většinu LAP a jsou „zadarmo“ - proto může být LAP mnohem větší než RAM.
2. Využitý prostor - skutečná data. Ta jsou uložená buď
   • v RAM (v přiděleném rámci), nebo
   • na disku ve SWAPu / stránkovacím souboru, pokud se na ně dlouho nesáhlo.

Výhody LAP

• Izolace procesů - proces se fyzicky nemůže dostat do paměti jiného procesu, protože ji nemá ve své tabulce stránek.
• Paměť větší, než je fyzicky dostupná - velikost LAP omezuje jen šířka adresy (32bit ≈ 4 GB, 64bit ≈ 16 EB), ne velikost RAM.
• Ochrana paměti - u každé stránky jsou přístupová práva (čtení / zápis / spouštění, uživatelský vs. privilegovaný režim).
• Odstranění vnější fragmentace - libovolný volný rámec se hodí pro libovolnou stránku, volná paměť tedy nemusí být souvislá. Zůstává jen vnitřní fragmentace (nevyužitý zbytek poslední stránky), v průměru půl stránky na region.

Struktura LAP procesu

LAP není beztvará plocha, dělí se na regiony (viz i otázka č. 10):

• Kódový region (CR, text) - strojový kód programu. Jen pro čtení a spouštění, proto se dá bez problémů sdílet.
• Datový region (DR) - statické a globální proměnné, čtení i zápis.
• Halda (heap) - dynamicky alokovaná paměť (malloc, new), roste k vyšším adresám.
• Zásobníkový region (SR, stack) - lokální proměnné, parametry a návratové adresy funkcí (LIFO), roste proti haldě.
• Sdílené knihovny - namapované do LAP, jejich kódové stránky ukazují u všech procesů na stejné rámce.
• Prostor jádra - jádro je namapováno do horní části LAP každého procesu, ale jeho stránky jsou privilegované. Díky tomu se při volání služby jádra nemusí přepínat tabulka stránek.

Tabulka stránek a TLB

• Položka tabulky je indexovaná číslem stránky a obsahuje číslo rámce a příznaky:
  • VF (validity flag) - má stránka přidělený rámec?
  • DF (dirty flag) - bylo do stránky zapsáno?
  • referenced / accessed bit - sáhlo se na stránku? (používá se při kradení)
  • přístupová práva a cache příznaky
• Tabulka pro celý 32bit LAP by měla přes milion položek, proto se používají víceúrovňové (hierarchické) tabulky - podtabulky pro nepoužité části LAP vůbec nemusí existovat. x86 má 2 úrovně, x86-64 obvykle 4.
• TLB (Translation Lookaside Buffer) - malá asociativní cache posledních překladů přímo v MMU. Bez ní by byl překlad neúnosně pomalý, protože každý překlad by znamenal několik přístupů do paměti. Úspěšnost bývá přes 99 % díky lokalitě odkazů.

Kradení stránek

• RAM je rozdělená na rámce, které se přidělují procesům. Rámců je vždycky míň než stránek.
• Když dojde volný rámec a je potřeba další, musí OS nějaký ukrást - vybrat oběť, uvolnit ji a přidělit tomu, kdo ji potřebuje.
• Před uvolněním:
  • čistá (clean) stránka (nenastavený DF) se rovnou zahodí - její obsah je pořád na disku (např. kód programu),
  • špinavá (dirty) stránka se musí nejdřív zapsat na disk. Proto DF existuje - šetří zápisy.
• Zápis dělá na pozadí démon (pageout, kswapd), aby při výpadku byl už nějaký volný rámec připravený.
• Některé rámce jsou zamčené (pinned) a ukrást se nesmí - kód jádra, buffery DMA, obsluhy přerušení.

Algoritmy pro výběr stránky ke kradení

Cílem je minimalizovat počet výpadků stránky.

• FIFO - první přišla, první jde ven. Jednoduché, ale hloupé - vyhodí i stránku, která se používá pořád. Trpí Béládyho anomálií: při zvětšení počtu rámců může počet výpadků paradoxně vzrůst.
• LRU (Least Recently Used) - vyhodí stránku, která se nejdéle nepoužila. Vychází z lokality odkazů a funguje velmi dobře, ale přesná implementace je pro hardware moc drahá (razítko při každém přístupu).
• Optimal Page Replacement (OPT, Bélády) - vyhodí stránku, která bude potřeba nejpozději. Neproveditelný, protože vyžaduje znalost budoucnosti. Slouží jen jako měřítko, se kterým se ostatní algoritmy porovnávají.
• Clock / Second Chance - vylepšené FIFO, praktická aproximace LRU. Stránky jsou v kruhovém seznamu, ukazatel se posouvá dokola. Má-li stránka nastavený referenced bit, bit se vynuluje a stránka dostane druhou šanci; pokud ho nastavený nemá, je ukradena. Tohle používají reálné OS.
• LFU / MFU - podle počtu použití. Používají se málo (LFU drží v paměti stránky, které byly kdysi hodně používané a dnes už nejsou potřeba).

Výpadek stránky (page fault)

Nastane, když proces přistoupí ke stránce, která není v RAM (nemá nastavený VF).

1. Vyvolá se přerušení (výjimka), které přeruší instrukci a předá řízení obslužné rutině jádra.
2. Rutina najde volný rámec, nebo ho podle výše uvedených algoritmů ukradne (a případně jeho obsah zapíše na disk).
3. Načte požadovanou stránku ze SWAPu / ze souboru do rámce.
4. Zapíše číslo rámce do tabulky stránek a zplatní stránku (nastaví VF).
5. Zopakuje přerušenou instrukci - napodruhé už výpadek nenastane.

Pokud stránka leží v nepoužité části LAP, jádro proces místo toho ukončí s výjimkou (typicky SIGSEGV, „segmentation fault“).

Thrashing

• Pracovní množina (working set) - stránky, se kterými proces v daném okamžiku opravdu pracuje.
• Když procesu nezbývá dost rámců na jeho pracovní množinu, jenom pořád dokola odkládá a znovu načítá stránky. Procesor se skoro nevyužívá, systém čeká na disk a zdánlivě „zamrzne“. Tomu se říká thrashing (zahlcení výpadky).
• Řešení: model pracovní množiny, řízení podle frekvence výpadků, odložení celého procesu (střednědobé plánování), nebo prostě víc RAM.

Sdílená a dočasně sdílená paměť

Sdílená paměť

• Více procesů má ve své tabulce stránek odkaz na stejný rámec. Fyzicky jde o tutéž paměť, každý proces ji ale může vidět na jiné logické adrese.
• Využití:
  • IPC (meziprocesová komunikace, viz otázka č. 15) - nejrychlejší způsob, protože po namapování už jádro do komunikace vůbec nezasahuje,
  • úspora paměti - sdílené knihovny jsou v RAM jen jednou, i když je používá padesát procesů; jeden proces data načte, ostatní je jen čtou.
• Je nutné zajistit konzistenci a synchronizaci (MUTEX, semafor - viz otázka č. 14), jinak vznikne souběh.

Dočasně sdílená paměť (Copy-on-Write)

• Stránka je sdílená jen do chvíle, než se ji někdo pokusí změnit.
• Rámce jsou označené jen pro čtení. Při zápisu se vyvolá výjimka, jádro rámec zkopíruje, dá zapisujícímu procesu vlastní kopii a teprve pak zápis provede.
• Typické použití je fork() - potomek nedostane kopii paměti rodiče, ale sdílí s ním rámce. Zkopírují se jen ty stránky, které se opravdu změní.
• Výhoda: velká úspora paměti a času (fork je díky tomu levný), protože většina stránek se nikdy nezmění.