Fakulta informačních technologií Božetěchova 2, BRNO 26. dubna 2011

´ pameti ˇ Sprava

´ s Vojnar Tomaˇ

[email protected]

Vysoke´ uˇcen´ı technicke´ v Brneˇ Fakulta informaˇcn´ıch technologi´ı ˇ Boˇzetechova 2, 612 66 BRNO 26. dubna 2011

´ Operaˇcn´ı systemy

´ pameti ˇ Sprava

ˇ – Aby program mohl být proveden, mus´ı nad n´ım být vytvoˇren proces, mus´ı mu být pˇridelen procesor ˇ ˇ ’ (a pˇr´ıpadneˇ dalˇs´ı zdroje). např. I/O zdroje a mus´ı mu být pˇridelena pamet – Rozliˇsujeme: ´ ı adresový prostor, se kterým pracuje procesor pˇri • logicky´ adresovy´ prostor (LAP): virtualn´ ´ en´ ˇ ı kodu ´ ´ provad (kaˇzdý proces i jadro maj´ı svuj), ˚ ˇ (spoleˇcný pro vˇsechny • fyzicky´ adresovy´ prostor (FAP): adresový prostor fyzických adres pameti ´ procesy i jadro).


´ pameti ˇ Sprava

1

– MMU (Memory Management Unit) = HW jednotka pro pˇreklad logických adres na fyzicke´ (dnes ´ cˇ ipu procesoru): souˇcast

CPU

Logical Address

MMU

Physical Address

Memory

TLB

interrupt Data

datová sběrnice

´ ıch registru˚ a pˇr´ıpadeˇ i hlavn´ı pameti ˇ systemu; ´ – MMU vyuˇz´ıva´ specialn´ pro urychlen´ı pˇrekladu muˇ ˚ ze ´ ˇ (napˇr. TLB). obsahuje informace potřebné pro překlad adres obsahovat ruzn ı pameti ˚ e´ vyrovnavac´


´ pameti ˇ Sprava

2

ˇ ´ ı pameti ˇ Pˇridelov an´

´ re setkat s pˇridelov ˇ an´ ´ ım FAP pro – Na nejniˇzsˇ ´ı urovni z hlediska bl´ızkosti HW se muˇ ´ ˚ zeme v jadˇ ´ ı do LAP, ktere´ je konzistentn´ı se zpusobem ´ HW zamapovan´ pˇrekladu LAP na FAP, jenˇz je podporovan ˚ ´ ´ daneho výpoˇcetn´ıho systemu:

• spojite´ bloky (contiguous memory allocation), • segmenty, ´ • stranky, ´ • kombinace výsˇ e uvedeneho. ˇ an´ ´ ı LAP pro konkretn´ ´ ı potˇreby uˇzivatelských procesu˚ – Na vyˇssˇ ´ı urovni se pak pouˇz´ıva´ pˇridelov ´ ´ ´ ˇ znou potˇrebu v jadˇ ´ re ( kmalloc, ( malloc, ... – implementovano mimo reˇzim jadra) i pro beˇ ˇ ych usek ´ u˚ FAP. vmalloc, ...), a to v ramci bloku˚ LAP jiˇz zamapovaných do pˇridelen´ ´


´ pameti ˇ Sprava

3

Contiguous Memory Allocation

ˇ any ´ spojite´ bloky pameti ˇ urˇcite´ velikosti. – Procesum ˚ jsou pˇridelov – Snadna´ implementace (jak v HW, tak obsluha v OS):

kde se blok přidělené paměti nachází ve fyzické paměti

velikost bloku přidělené paměti

proces se snaží přistoupit mimo jemu přidělenou paměť


´ pameti ˇ Sprava

4

ˇ (FAP): – Významneˇ se projevuje extern´ı fragmentace pameti ˇ an´ ´ ım a uvolnov ˇ an´ ´ ım pameti ˇ vznika´ posloupnost obsazených a neobsazených usek • pˇridelov u˚ ´ ˇ ruzn ´ protoˇze je nespojite, ´ pameti ıc´ı, zˇ e volne´ m´ısto muˇ ˚ e´ velikosti zpusobuj´ ˚ ˚ ze být nevyuˇzitelne, ˇ (pˇriˇcemˇz je tˇreba brat ´ do uvahy • minimalizace pomoc´ı ruzn´ take´ reˇzii ˚ ych strategi´ı alokace pameti ´ ˇ an´ ´ ım) – mimo first fit lze uˇz´ıt napˇr. best fit, worst fit, binary buddy, ..., spojenou s daným pˇridelov ´ se zvetˇ ˇ sovan´ ´ ım pˇridelen ˇ eho ´ • problem prostoru, ˇ (nakladn ´ ´ • dynamicka´ reorganizace pameti e!).

worst fit - přidělí nejméně odpovídající volný blok best fit - přidělí nejvhodnější blok binary buddy - přiděluje paměť po mocninách 2

ˇ nutno odkladat ´ ˇ ’ procesu: muˇ ´ pomale. ´ na disk veˇskerou pamet – Pˇri nedostatku pameti ˚ ze být zbyteˇcne, ´ ´ pameti. ˇ nen´ı moˇzne´ sd´ılet cˇ asti – Nen´ı moˇzne´ jemneˇ ˇr´ıdit pˇr´ıstupova´ prava, ´ popisuj´ıc´ıch obsazen´ı pameti ˇ je pak ale nutne´ – Nemus´ı zpusobit intern´ı fragmentaci, ve strukturach ˚ ˇ ı evidence pˇridelen ˇ e/voln ´ ˇ a odstranen´ ˇ ı moˇznosti pracovat s upln´ e´ pameti ´ ymi adresami. Pro usnadnen´ ˇ ´ vzniku velmi malých neobsazených usek u˚ se muˇ v nasobc´ ıch urˇcitých bloku, ı ´ ˚ ze pˇridelovat ˚ coˇz zpusob´ ˚ ˇ an´ ´ ı pameti). ˇ intern´ı fragmentaci (toleruje se, vznika´ i u ostatn´ıch mechanismu˚ pˇridelov


´ pameti ˇ Sprava

5

ˇ Segmentace pameti ˇ ˇ pˇrekladaˇcem – LAP rozdelen na kolekci segmentu. ˚ Ruzn ˚ e´ segmenty mohou být pˇrideleny ´ ´ ´ ´ ´ cˇ astem dat, zasobn´ ıku, ...). (programatorem) jednotlivým cˇ astem procesu (napˇr. proceduram, ´ ´ a´ ze jmena ´ – Kaˇzdý segment ma´ jmeno (ˇc´ıslo) a velikost; logicka´ adresa sestav segmentu a posunu ˇ v nem:

logická adresa se zkládá z čísla segmentu a posuvu v rámci segmentu (velikost požadované paměti)

+ další řídící přáznaky

podle indexu segementu se vyhledá odpovídající záznam v tabulce segmentů, pokud proces přistupuje mimo přidělenou oblast, dojde k chybě


´ pameti ˇ Sprava

6

ˇ (segmenty jen pro cˇ ten´ı, – Segmenty mohou být vyuˇzity jako jednotka ochrany a/nebo sd´ılen´ı pameti sd´ılene´ segmenty, ...).

´ pomern ˇ eˇ jednoducha. ´ – Implementace je stale

ˇ ’ pˇridelov ˇ ana ´ ˇ ı dopadu˚ extern´ı fragmentace a jemnejˇ ˇ s´ı odklad ´ an´ ´ ı neˇz – Pamet po segmentech; zm´ırnen´ ˇ an´ ´ ı jedine´ oblasti – ale problem ´ pˇretrvav ´ a. ´ u pˇridelov

– Segmentace je viditelna´ procesu: komplikace pˇri pˇrekladu (tvorbeˇ programu), ˚ moˇznost chyb.


´ pameti ˇ Sprava

7

´ ´ ı Strankov an´ ˇ ´ – LAP rozdelen na jednotky pevne´ velikosti: stranky (pages). ˇ ´ – FAP rozdelen na jednotky stejne´ velikosti: ramce (frames).

– Vlastnosti: ˇ ’ pˇridelov ˇ ana ´ ´ ıch, • pamet po ramc´

• neviditelne´ pro uˇzivatelske´ procesy, ´ problemy ´ • minimalizovany s extern´ı fragmentac´ı,

paměť je rozdělena na stránky, každá je buď volná nebo obsazená, pokud

– nevznika´ nevyuˇzitelný volný prostor, není místo na souvislé uložení, stránky se rozprostřou ˇ (vetˇ ˇ s´ı poˇcet koliz´ı v ruzn´ ´ – moˇzne´ sn´ızˇ en´ı rychlosti pˇr´ıstupu do pameti ıch ˚ ych vyrovnavac´ ˇ ´ se strukturami popisuj´ıc´ımi aktualn´ ´ ı obsah pameti), ˇ pametech) a alokace/dealokace (delˇs´ı prace ´ u: ˇ ˇ ’ pokud moˇzno po spojitých posloupnostech ramc – proto v praxi je snaha pˇridelovat pamet ˚ napˇr. pomoc´ı algoritmu binary buddy“, ” ´ en´ ˇ ı – tzv. NX bit) a/nebo sd´ılen´ı, lze nastavit • jemna´ jednotka ochrany (r/rw, user/system, moˇznost provad ´ an´ ´ ı po strank ´ ach, ´ • jemna´ kontrola odklad

zabezpečení pro každou stránku

ˇ s´ı implementace, vetˇ ˇ s´ı reˇzie, • sloˇzitejˇ

• intern´ı fragmentace.


´ pameti ˇ Sprava

8

ˇ ych) tabulek stranek, ´ – V nejjednoduˇssˇ ´ım pˇr´ıpadeˇ tzv. jednoduchých (ˇci jednourov OS udrˇzuje ´ nov´ ´ ´ ´ informaci o volnych ´ ramc´ ıch a pro kaˇzdý proces (a jadro) tabulku stranek (page table): logická adresa se skládá z čísla stránky a posuvu v rámci stránky každý proces má svou tabulku stránek (uložena v RAM) v MMU je uložen začátek tabulky stránek pro daný proces (registr CR3) pro číslo logické stránky se nalezene odpovídající číslo fyzické stránky a v ní se použije stejný posun jako v logické adrese


´ pameti ˇ Sprava

9

´ ´ ı logických stranek ´ – Tabulka stranek obsahuje popis mapovan´ do FAP a pˇr´ıznaky modifikace, ´ (r/rw, user/system, moˇznost provad ´ en´ ˇ ı), pˇr´ıznak globality (neodstranov ˇ ano ´ pˇr´ıstupu, pˇr´ıstupova´ prava pokud je položka sdílená, ponechá ji v cache automaticky z TLB pˇri pˇrepnut´ı kontextu), ...

ˇ specialn´ ´ ı registr MMU (CR3 u x86) obsahuje ´ ´ v hlavn´ı pameti; – Tabulky stranek jsou udrˇzovany ´ ´ ´ ı proces. adresu zaˇcatku tabulky stranek pro aktualn´ ˇ vyˇzaduje (u jednoduche´ tabulky stranek) ´ – Kaˇzdý odkaz na data/instrukce v pameti dva pˇr´ıstupy do ˇ do tabulky stranek ´ pameti: a na vlastn´ı data/instrukci.

´ ˇ TLB (Translation Look-aside – Urychlen´ı pomoc´ı rychle´ hardwarove´ asociativn´ı vyrovnavac´ ı pameti Buffer ).


´ pameti ˇ Sprava 10

´ ´ ˇ – TLB obsahuje dvojice (ˇc´ıslo stranky,ˇ c´ıslo ramce) + nekter e´ z pˇr´ıznaku˚ spojených s daným ´ en´ ˇ ı, pˇr´ıznak modifikace, pˇr´ıp. dalˇs´ı). ´ ım v tabulkach ´ stranek ´ mapovan´ (pˇr´ıstupova´ opravn ´ ´ – POZOR! V TLB nejsou cele´ stranky cˇ i ramce! ´ a´ paralelneˇ na zaklad ´ ´ ´ – TLB se prohledav eˇ cˇ ´ısla stranky, a to bud’ plneˇ (viz obrazek n´ızˇ e), nebo ´ cneˇ (dojde k indexaci skupiny bunek ˇ TLB dle cˇ asti ´ cˇ ´ısla stranky ´ ´ ı– cˇ asteˇ a pak k paraleln´ımu dohledan´ ´ ´ ´ napˇr. by mohly být uˇzity 2 bity z cˇ ´ısla stranky k rozliˇsen´ı 4 mnoˇzin dvojic stranek prohledavan´ ych jiˇz ´ ˇ tak, jak je znazorn eno n´ızˇ e).

TLB miss - pokud TLB neobsahuje záznam pro danou stránku, pokračuje se podle běžného postupu



– POZOR! K TLB miss muˇ ˚ ze doj´ıt jak pˇri cˇ ten´ı instrukce, tak pˇri cˇ ten´ı jejich operandu, ˚ a to u instrukce i ´ ´ operandu˚ i v´ıcenasobn eˇ (nezarovnana´ instrukce, nezarovnana´ data, data delˇs´ı neˇz jedna stranka). – Po TLB miss: ´ • U HW ˇr´ızených TLB HW automaticky hleda´ v tabulce stranek. ´ ´ • U SW ˇr´ızených TLB (napˇr. MIPS, SPARC) mus´ı v tabulce stranek hledat jadro a patˇriˇcneˇ upravit obsah TLB. ´ st’ pro stranky ´ ´ a data a/nebo hierarchie v´ıce ˇ obsahuj´ıc´ı kod – Nekdy muˇ ˚ ze být pouˇzito v´ıce TLB: zvlaˇ urovn´ ı TLB (ruzn ´ ˚ a´ rychlost, kapacita, cena, spotˇreba). – Pˇri pˇrepnut´ı kontextu nutno obsah TLB invalidovat. Optimalizace: ´ ıch stranek ´ ´ stn´ım pˇr´ıznakem v tabulce stranek ´ oznaˇcených zvlaˇ a TLB cˇ i • pouˇzit´ı globaln´

neodstraňují se z TLB

´ • spojen´ı zaznamu v TLB s identifikac´ı procesu (ASID, PCID, ...). ˇ eˇ obsahu tabulek stranek. ´ ˇ e´ zaznamy ´ – Invalidace TLB nutna´ samoˇrejmeˇ i po zmen Muˇ ˚ ze-li ovlivnen pouˇz´ıvat v´ıce procesoru, ˚ nutno invalidovat TLB na vˇsech procesorech. je třeba vymazat TLB ˇ ´ ´ provad ´ en ˇ e´ – Nekter e´ procesory mohou dopˇredu nahravat do TLB pˇreklad pro odhadovane´ dale instrukce. ´ Operaˇcn´ı systemy


´ ı na usp ˇ snosti TLB: ´ ´ ı velmi silneˇ zavis´ – Efektivnost strankov an´ ´ eˇ

• Efektivn´ı pˇr´ıstupova´ doba: (τ + ε)α + (2τ + ε)(1 − α), kde – τ: vybavovac´ı doba RAM – ε: vybavovac´ı doba TLB ˇ ˇ sných vyhledan´ ´ ı v TLB (TLB hit ratio) – α: pravdepodobnost usp ´ eˇ

při čtení programu by se za sebou měly nacházet odkazy do stejné stránky, pokud se bude neustále přeskakovat ze stránky na stránku, bude se přepisovat TLB -> častý TLB miss -> TLB nevyužita

ˇ e´ zpomalen´ı o 22%. • Napˇr. pro τ = 100ns, ε = 20ns a α = 0.98 dostaneme prum ˚ ern ´ ı na lokaliteˇ odkazu˚ programu. • TLB hit ratio významneˇ zavis´

vlastnost programu, která udává míru toho, kolik různých shluků adres v paměti odpovídajích různým stránkám v dané chvíli program používá...pokud program používá příliš mnoho stránek, dochází k výpadkům z paměti TLB

´ – Výsˇ e uvedený vztah je sestaven za pˇredpokladu, zˇ e po TLB miss a pˇrekladu pˇres tabulky stranek se z´ıskana´ adresa ihned pouˇzije. V praxi se cˇ asto z´ıskaný pˇreklad nejprve vloˇz´ı do TLB a pak se opakuje ´ vztahu nutno pˇri TLB miss pˇripoˇc´ıst dalˇs´ı pˇr´ıstup do TLB pˇreklad pˇres TLB – pak je ve výsˇ e uvedenem a take´ cˇ as pro upravu TLB. ´ – Lokalita odkazu˚ = vlastnost programu – m´ıra toho, kolik ruzn´ ˚ ych shluku˚ adres (odpov´ıdaj´ıc´ıch ´ em ´ cˇ asovem ´ useku. ´ v ruzn´ ´ ach) ´ typicky adresam bude proces potˇrebovat v kratk ´ ˚ ych strank



Pˇr´ıklad: ´ an´ ´ ı matic po ˇradc´ ´ ıch je – Pˇri uklad

for (j = 0; j < MAX; j++) for (i = 0; i < MAX; i++) A[i,j] = 0; ´ eˇ výhodne´ neˇz mnohem men

for (i = 0; i < MAX; i++) for (j = 0; j < MAX; j++) A[i,j] = 0; ˇ pˇri virtualizaci pameti ˇ a odklad ´ an´ ´ ı stranek ´ – Rozd´ıl se projev´ı jeˇsteˇ výrazneji na disk.



´ Implementace tabulek stranek

´ ´ e. ´ – Tabulky stranek mohou být znaˇcneˇ rozsahl

´ se strankami ´ ´ poloˇzek (pˇresneˇ – Pro 32b system o velikosti 4KiB (212 ) muˇ ˚ ze m´ıt tabulka v´ıce neˇz milion ´ poloˇzka tabulky stranek ´ 232/212 = 220 = 1048576 poloˇzek). Ma-li 4B, dostaneme 4MiB na tabulku ´ stranek pro kaˇzdý proces, coˇz je pˇr´ıliˇs na spojitou alokaci (pro 100 procesu˚ 400MiB jen pro tabulky ´ stranek!). ´ ´ exponencialn ´ eˇ roste. – Pro 64b systemy problem



´ ´ ´ ´ – Hierarchicke´ tabulky stranek: tabulka stranek je sama strankov ana, vznikaj´ı tabulky tabulek ´ ´ zpomaluje pˇr´ıstup). stranek, ... (coˇz ovˇsem dale ˇ a´ tabulka stranek ´ – Pˇr´ıklad: dvouurov procesoru˚ i386+ ´ nov Logical address 22 21

31

10 bits horních 10 bitů je index do tabulky tabulek stránek, tam se nalezne odkaz na dílčí tabulku stránek, v níž se podle indexu (prostředních 10 bitů) nalezne odkaz na číslo stránky

12 11

10 bits

odkaz do tabulek tabulek stránek

0

12 bits

odkaz do tabulek stránek

page tables

posuv ve stránce

page directory

index lze přepínat mezi 4KiB a 4MiB velikostmi stránek přepnutím 1 bitu v adresáři tabulek stránek. pak se použije pouza jedna úroveň stránek -> prostřední část adresy pak také tvoří posuv

index

Physical address page number

12 11

0

12 bits offset

´ adresaˇ ´ re stranek ´ ´ ´ ı. T´ımto – Pˇr´ıznak v poloˇzkach urˇcuje, zda je pouˇzita i niˇzsˇ ´ı urove nˇ strankov an´ ´ ´ zpusobem je moˇzno pracovat se strankami o velikosti 4 KiB (212 B) a 4 MiB (222 B). ˚ ´ Operaˇcn´ı systemy


ˇ a´ tabulka stranek ´ – 4-urov na x86-64: ´ nov

´ tabulek PDPE a PDE urˇcuje, zda je pouˇzita i niˇzsˇ ´ı urove ´ ´ ı. T´ımto – Pˇr´ıznak v poloˇzkach nˇ strankov an´ ´ ´ ˇ zpusobem je moˇzno pracovat se strankami o velikosti 4 KiB (212 B), 2 MiB (221 B) a u nekter´ ych ˚ procesoru˚ i 1 GiB (230 B). ´ Operaˇcn´ı systemy


´ – Hashovane´ tabulky stranek:

každý proces má svou hashovací tabulku

číslo logické stránky se zahashuje, podle něj se v tabulce stránek nalezne odpovídající zřetězený seznam, který obsahuje číslo stránky a číslo rámce (v ideálním případě je tento seznam pouze s jedním prvkem), najdu v zřetězeném seznamu číslo dané stránky a jeho odpovídající rámec



´ ıc´ı pro kaˇzdý ramec, ´ ˇ ´ – Invertovana´ tabulka stranek: jedina´ tabulka udavaj´ který proces ma´ do nej ´ kterou stranku. ´ do jednoho rámce může přistupovat více procesů, je proto nutné každý proces identifikovat namapovanu pomocí PID a pamatovat si, kterou jeho stránku mapuje do daného rámce

´ ım napˇr. PowerPC a 64b UltraSparc firmy Sun. – Pouˇz´ıva´ v kombinaci s hashovan´ ´ pameti ˇ (odklad ´ an´ ´ ı na disk apod.) vede dale ´ i klasicke´ tabulky stranek. ´ – OS si pro potˇreby spravy ´ Problematicka´ je implementace sd´ılen´ı stranek.

je nutné postupně procházet invertovanou tabulku stránek, na každém řádku hledáme, zda obsahuje číslo logické stránky a číslo aktuálního procesu, pokud ano, zjistíme index řádku -> číslo rámce

položky indexovány číslem rámce



ˇ Virtualizace pameti virtualizace = technologie, která umožňuje oddělit vazbu mezi obsazenou částí logického adresového prostoru procesu a obsazenou částí paměti. umožňuje ukládat obsazené části logické paměti na disk

ˇ – Vyuˇzitý adresový prostor procesu nemus´ı být celý ve fyzicke´ pameti. – Vyuˇz´ıva´ se prostor na disku.

– Virtualizace pomoc´ı: ´ ´ ı na zˇ adost ´ • strankov an´ (demand paging) ´ ı na zˇ adost ´ • segmentovan´ (demand segmenting)



´ ´ ı na zˇ adost ´ Strankov an´

´ ´ eny ˇ do pameti ˇ jen tehdy, jsou-li zapotˇreb´ı. – Stranky jsou zavad ˇ rychlejˇs´ı odklad ´ an´ ´ ı na disk a zavad ´ en´ ˇ ı do pameti ˇ (nen´ı zapotˇreb´ı odloˇzit – Menˇs´ı spotˇreba pameti, ´ celý vyuˇzitý adresový prostor procesu). nebo zavest

´ ´ je zapotˇreb´ı tehdy, dojde-li k odkazu na ni. V tabulce stranek je pˇr´ıznak, zda pˇr´ısluˇsne´ – Stranka ´ ˇ ´ ´ strance je pˇridelen ramec. Pokud ne, dojde k výpadku stranky (page fault).



´ Obsluha vypadku ´ stranky ´ ´ ıc´ı, zˇ e nelze pˇrevest ´ adresu (nen´ı definovano ´ – Výpadek stranky je pˇreruˇsen´ı od MMU udavaj´ ´ ı v tabulce stranek). ´ mapovan´ ˇ y adresový prostor, dojde – Pokud pˇr´ıcˇ inou výpadku nen´ı to, zˇ e se odkazujeme mimo pˇridelen´ ´ ´ ´ k obsluze výpadku stranky takto (pouze zakladn´ ı ilustrace, bl´ızˇ e viz nasleduj´ ıc´ı slajd):

ke slovu se dostane jádro, zjistí důvod výpadku, pokud je to dáno tím, že se proces pokoušel přistoupit do paměti, která mu nebyla alokována, typicky dojde ke zrušení procesu pokud proces přistupuje do alokované paměti, která však ještě nebyla vytvořena nebo byla odložena, je nutné vytvořit nový rámec, načíst data z dsku, upraví se tabulka stránek, znova se provede instrukce, která selhala



ˇ vypada´ typicka´ obsluha výpadku stranky ´ – Podrobneji takto: ˇ y adresový prostor. 1. Kontrola, zda se proces neodkazuje mimo pˇridelen´ ´ 2. Alokace ramce: ´ ˇ y volný je, • pouˇzijeme volný ramec, pokud nejak´ • pokud nen´ı, ´ ˇ ym ramcem ´ – vybereme vhodnou stranku s pˇridelen´ (victim page), ´ ´ pˇr´ıznak modifikace v tabulce stranek), ´ – stranku odloˇz´ıme na swap (je-li to nutne: ˇ y ramec. ´ – pouˇzijeme uvolnen´ ´ ´ ´ 3. Inicializace stranky po alokaci zavisl a´ na pˇredchoz´ım stavu stranky: ´ • prvn´ı odkaz na stranku: ´ naˇcten´ı z programu, kod: inicializovana´ data: naˇcten´ı z programu, ´ ı (nelze ponechat puvodn´ vˇse ostatn´ı: vynulovan´ ı obsah – bezpeˇcnost), ˚ ´ ˇ • stranka byla v minulosti uvolnena z FAP: ´ znovu naˇcte z programu (jen pokud nelze pˇrepisovat kodov ´ ´ kod: e´ stranky), ´ z co kod, ´ konstantn´ı data: toteˇ ´ ´ ˇ do FAP. ostatn´ı: pokud byla modifikovana, je stranka ve swapu a mus´ı se naˇc´ıst zpet ´ ´ ´ ı zpˇr´ıstupnovan ˇ ´ ˇ y ramec. ´ tabulky stranek: namapovan´ e´ stranky na pˇridelen´ 4. Uprava ´ ı instrukce, ktera´ výpadek zpusobila 5. Proces je pˇripraven k opakovan´ (je ve stavu pˇripravený“). ˚ ”



´ ´ ı na zˇ adost ´ Vykonnost ´ strankov an´ ˇ (1 − p)T + pD, kde – Efektivn´ı doba pˇr´ıstupu do pameti: ˇ ´ • p: page fault rate = pravdepodobnost výpadku stranky,

• T : doba pˇr´ıstupu bez výpadku, • D: doba pˇr´ıstupu s výpadkem.

– Vzhledem k tomu, zˇ e T << D, mus´ı být p co nejmenˇs´ı: ˇ a jemu pˇrimeˇ ˇ rený poˇcet procesu˚ (s ohledem na jejich pamet ˇ ’ove´ naroky), ´ • dostatek pameti ˇ zavad ´ en´ ˇ ych a odkladan´ ´ ´ • vhodný výber ych stranek,

• lokalita odkazu˚ v procesech.



ˇ vypadk Pocet ´ u˚

´ s kaˇzdým z jejich operandu, – K výpadkum ˚ muˇ ˚ ze doj´ıt jak pˇri cˇ ten´ı instrukce, tak pˇri praci ˚ a to ´ ˇ ´ e. u instrukce i u kaˇzdeho z operandu˚ i v´ıcenasobn ´ – V´ıcenasobn e´ výpadky mohou být zpusobeny: ˚ ´ ım instrukce, • nezarovnan´ ´ ım dat, • nezarovnan´

delší než 1 stránka

´ • daty delˇs´ımi neˇz jedna stranka, ´ ´ na stejne´ urovni • výpadky tabulek stranek ruzn´ ı – a to i v´ıcekrat hierarchických tabulek ˚ ych urovn´ ´ ´ ´ ´ ´ ıc´ı se na stejne´ urovni. stranek pˇri dotazech na ruzn nachazej´ ˚ e´ d´ılˇc´ı tabulky stranek ´ ´ tabulek stranek ´ ´ ena ˇ ´ ´ – Obvykle alesponˇ cˇ ast je chran pˇred výpadkem stranek (zejmena se to týka´ ´ ˇ mj. proto, aby bylo moˇzno u hierarchických tabulek stranek d´ılˇc´ı tabulky nejvyˇssˇ ´ı urovn e) ´ ´ obsluˇzit výpadky stranek. ´ ı poˇcet výpadku˚ stranek ´ ´ ´ – Pˇr´ıklad: Jaký je maximaln´ v systemu se strankami o velikosti 4 KiB, ˇ ´ ´ en ˇ a´ proti výpadku, 4-urov tabulkou stranek, u ktere´ pouze d´ılˇc´ı tabulka nejvyˇssˇ ´ı urovn eˇ je chran ´ novou ´ ˇ ´ ´ en´ ˇ ı pˇredem nenaˇctene´ instrukce o delce 4 B, ktera´ pˇresouva´ 8 KiB z jedne´ adresy pameti pˇri provad na jinou?



´ an´ ´ ı stranek ´ Odklad ´ ´ – K odloˇzen´ı stranky muˇ Muˇ ˚ ze doj´ıt pˇri výpadku stranky. ˚ ze být provedeno odloˇzen´ı: ´ ´ ´ ı – tj. v ramci • lokaln´ procesu, u ktereho doˇslo k výpadku ´ u˚ pro pouˇzit´ı procesy, – je zapotˇreb´ı vhodný algoritmus alokace ramc ´ ´ ´ ı – tj. bez ohledu na to, kteremu • globaln´ procesu patˇr´ı ktera´ stranka.

´ udrˇzovan ´ urˇcitý poˇcet volných ramc ´ u: – Typicky je ale neustale ˚ ´ u˚ klesne pod urˇcitou mez, aktivuje se • Pokud poˇcet volných ramc ˇ stranek“), ´ ˇ z´ı tak dlouho, dokud neuvoln´ı dostateˇcný poˇcet stranek ´ page daemon ( zlodej který beˇ ” ˇ ’ uvolnuje ˇ ´ ´ a´ prostor k behu ˇ (pˇr´ıp. pamet po cˇ astech a dav ostatn´ım procesum). ˚ ´ ´ ´ u. • Pˇri výpadku stranky se pak pouˇzije ramec z mnoˇziny volných ramc ˚ ˇ e´ stranky ´ ˇ ı a zjist´ı-li se, zˇ e byla • Lze doplnit heuristikou, kdy cˇ erstveˇ uvolnen se okamˇziteˇ nepˇridel´ ´ ´ a´ obet ˇ ’, lze je snadno vratit ´ pˇr´ısluˇsnemu procesu k pouˇzit´ı. zvolena nespravn



ˇ odkladan ´ ´ Algoritmy vyb ´ eru ych ´ stranek – FIFO:

udržuje seznam stránek ve frontě, odstraňuje stránky ze začátku fronty, nové stránky k uvolnění jsou na konec fronty

• Jednoducha´ implementace. ´ cˇ asto pouˇz´ıvanou stranku. ´ • Muˇ ˚ ze odstranit starou“, ale stale ” ´ ı. • Trp´ı tzv. Beladyho anomali´

správně by při větším množství volných rámců mělo docházet k méně výpadkům, u tohoto algoritmu však může nastat i opačná situace

ˇ ım uvolnen ˇ eho ´ ´ ´ u, ˇ ım • Lze uˇz´ıt v kombinac´ı s pˇrem´ısten´ ramce do mnoˇziny volných ramc ˚ pˇridelen´ ´ ´ ´ ˇ prav ´ eˇ uvolnen´ ˇ y ramec ´ ´ ´ výpadku jineho volneho ramce a moˇznost´ı ihned z´ıskat zpet pˇri nasledn em ´ a´ obet ˇ ’“. signalizuj´ıc´ım, zˇ e byla zvolena nespravn ” ´ Operaˇcn´ı systemy


– LRU (Least Recently Used): ´ a´ nejdele ´ nepouˇzitou stranku. ´ • Odklad ´ ´ ıho algoritmu (tj. algoritmu, který by znal budoucnost • Velmi dobra´ aproximace hypotetickeho idealn´ ´ eˇ odloˇzit tak, aby poˇcet výpadku˚ byl a podle budouc´ıch poˇzadavku˚ rozhodoval, co aktualn ´ ı). v budoucnu minimaln´ ˇ ´ ı problemy ´ ´ ymi poli, spolu se snahou takove´ – Nekdy se uvad´ s cyklickými pruchody rozsahl´ ˚ ´ st’ napˇr. strategi´ı odstranen´ ˇ ı naposledy pouˇzite´ stranky ´ pˇr´ıstupy detekovat a ˇreˇsit zvlaˇ (most recently used – MRU). ´ ı stranek ´ • Problematicka´ implementace vyˇzaduj´ıc´ı výraznou HW podporu (oznaˇcovan´ cˇ asovým ´ ı zasobn´ ´ ´ raz´ıtkem posledn´ıho pˇr´ıstupu, udrˇzovan´ ıku stranek, jehoˇz vrcholem je naposledy pouˇzita´ ´ stranka).

• Pouˇz´ıvaj´ı se aproximace LRU.



ˇ ıho bitu stranek ´ – Aproximace LRU pomoc´ı omezene´ historie referencn´ (page aging): ´ ´ pˇr´ıstupu, • Referenˇc´ı bit stranky je HW nastaven pˇri kaˇzdem ´ ´ • jadro si vede omezenou historii tohoto bitu pro jednotlive´ stranky,

• periodicky posouva´ obsah historie doprava, ˇ s´ı pozici uloˇz´ı aktualn´ ´ ı hodnotu referenˇcn´ıho bitu a vynuluje ho, • na nejlevejˇ ˇ ’ je vybrana ´ ´ • obet jako stranka s nejniˇzsˇ ´ı cˇ ´ıselnou hodnotou historie. ´ ame-li ´ ´ ´ – Uklad 4 bity historie a mame stranky s histori´ı 0110 a 1100, odstran´ıme prvn´ı z nich ˇ s´ı bit je posledn´ı reference). (nejlevejˇ



ˇ – Aproximace LRU algoritmem druhe´ sance: ´ ´ seznamu, postupujeme a nulujeme referenˇcn´ı bit, odstran´ıme prvn´ı stranku, ´ • Stranky v kruhovem ´ ktera´ jiˇz nulový referenˇcn´ı bit ma. ˇ ´ z oznaˇcovaný jako tzv. clock algorithm). • Casto pouˇz´ıvaný algoritmus (teˇ



ˇ – Modifikace algoritmu druhe´ sance: ˇ ı nemodifikovaných stranek ´ ˇ ı (modifikovane´ se zap´ısˇ ´ı na disk a dostanou • upˇrednostnen´ jako obet´ dalˇs´ı sˇ anci), ´ ıc´ı frontou s urˇcitým rozestupem – jeden nuluje referenˇcn´ı bit, druhý • dva ukazatele prochazej´ ˇ ˇ (tzv. double-handed clock algorithm), odstranuje obeti

• Linux: ˇ a´ dvakrat ´ behem ˇ ´ ´ jedne´ periody – fronty aktivn´ıch“ a neaktivn´ıch“ stranek: stranka zpˇr´ıstupnen ” ” ´ ı referenˇcn´ıch bitu˚ a odklad ´ an´ ´ ı neaktivn´ıch stranek ´ nulovan´ se pˇresouva´ do fronty aktivn´ıch ´ ˇ ˇ stranek, z aktivn´ı fronty se odstranuje do neaktivn´ı, z neaktivn´ı se pak vyb´ıraj´ı obeti, ´ se snaˇz´ı nejprve odkladat ´ ´ ´ ˇ pˇri urˇcitem ´ – system stranky pouˇzite´ pro ruzn ı pameti; ˚ e´ vyrovnavac´ ´ ˇ an´ ´ ı jejich stranek: ´ ´ ı procesy poˇctu stranek namapovaných procesy pˇrejde na odstranov prochaz´ ´ ´ stn´ıch seznamu), snaˇz´ı se odstranit vˇzdy alesponˇ urˇcitý poˇcet a jejich stranky (propojene´ ve zvlaˇ ´ ˇ ´ ´ stranek z procesu, neodstranuje stranky z aktivn´ıho seznamu (nebo alesponˇ referencovane), ´ ı odklad ´ an´ ´ ı po urˇcitých poˇctech projdených a odloˇzených stranek, ´ – provad´ agresivita se zvyˇsuje ˇ s rostouc´ım nedostatkem pameti, ´ ´ ˇ ˇ – tzv. swap token“: stranky procesu, kteremu je tato znaˇcka udelena, jsou pˇreskoˇceny pˇri výberu ” ˇ ı, obet´ ´ nedostatku pameti ˇ ukonˇcuje nekter ˇ – pˇri kritickem e´ procesy.



´ ´ Alokace ramc u˚ procesum ˚ (resp. jadru) ˇ an´ ´ ı ramc ´ u˚ procesum ´ ´ ´ ım výberu ˇ obet´ ˇ ı, kde ˇr´ıd´ı – Pˇridelov je významne´ zejmena pˇri lokaln´ ˚ (resp. jadru) při malém počtu dostupných rámců nemá ˇ ı mnoˇziny ramc ´ u, ´ ´ ı lokaln´ ´ ı výmeny. ˇ pˇridelen´ kterých se pak provad´ ˚ v ramci obětování příliš velký efekt

´ ıho výberu ˇ lze pouˇz´ıt pro ˇr´ızen´ı výberu ˇ obet´ ˇ ı. – U globaln´ ˇ ´ ı poˇcet ramc ´ u˚ pro proveden´ı jedne´ instrukce: jinak dojde – Je tˇreba m´ıt vˇzdy pˇridelen minimaln´ ´ ˇ an´ ´ ı stranek ´ k nekoneˇcnemu vymeˇ nov potˇrebných k proveden´ı instrukce. ´ se uˇz´ıvaj´ı ruzn ´ u˚ pro procesy (resp. jadro): ´ – Dale ˚ e´ heuristiky pro urˇcen´ı poˇctu ramc ´ ern ˇ eˇ k velikosti programu, priorite, ˇ objemu fyzicke´ pameti, ˇ ... • Um ´ ´ ´ ´ • Na zaklad eˇ pracovn´ı mnoˇziny stranek, tj. mnoˇziny stranek pouˇzitých procesem (resp. jadrem) za urˇcitou dobu (aproximace s pomoc´ı referenˇcn´ıho bitu). ´ ´ ı frekvence vypadk • Pˇr´ımo na zaklad eˇ sledovan´ ´ u˚ v jednotlivých procesech.



ˇ an´ ´ ı ramc ´ u˚ s vyuˇzit´ım pracovn´ı mnoˇziny a kombinace lokaln´ ´ ı a globaln´ ´ ı výmeny ˇ pouˇz´ıvaj´ı – Pˇridelov ˇ s´ı systemy ´ novejˇ Windows: ´ ´ ı a maximaln´ ´ ı poˇcet ramc ´ u˚ (meze velikosti pracovn´ı mnoˇziny), • Procesy a jadro maj´ı jistý minimaln´ ˇ se jim ramce ´ ´ ı aˇz po dasaˇzen´ı maxima (pˇr´ıp. se povol´ı i – pˇri dostatku pameti pˇri potˇrebeˇ pˇridavaj´ ˇ sen´ı maxima), zvetˇ ˇ se uplatn´ı lokaln´ ´ ı výmena, ˇ – pˇri dosaˇzen´ı maxima, nen´ı-li nadbytek pameti, ´ nedostatku volných ramc ´ u˚ se do vytvoˇren´ı patˇriˇcne´ zasoby ´ ´ u˚ system ´ – pˇri výraznem volných ramc ˇ odeb´ırat procesum snaˇz´ı (s agresivitou rostouc´ı s rostouc´ım nedostatkem pameti) ˚ urˇcitý poˇcet ´ ´ ´ a´ jim dalˇs´ı v posledn´ı dobeˇ nepouˇzitých stranek (u pouˇzitých stranek nuluje referenˇcn´ı bit a dav sˇ anci). ˇ obet´ ˇ ı dav ´ a´ pˇrednost vetˇ ˇ s´ım procesum ˇ z´ıc´ım men ´ eˇ cˇ asto; vyhýba´ se procesum, • Pˇri výberu ktere´ ˚ beˇ ˚ ˇ z´ı na popˇred´ı. zpusobily v posledn´ı dobeˇ mnoho výpadku˚ a procesu, který beˇ ˚ ˇ v ramci ´ ´ ´ • Obeti v posledn´ı dobeˇ nepouˇzitých stranek vyb´ıra´ na zaklad eˇ omezene´ historie pˇr´ıstupu. ˚ ´ cn´ı meze pracovn´ıch mnoˇzin odvozuje pˇri startu systemu ´ ˇ • Poˇcateˇ z velikosti fyzicke´ pameti. ˇ k jinemu ´ ˇ aby bylo moˇzno korigovat chyby pˇri ˇ se snaˇz´ı nepˇridelit pouˇzit´ı okamˇzite, • Vybrane´ obeti ˇ ı. volbeˇ obet´ ˇ odklad ´ an´ ´ ım (swapovan´ ´ ım) celých procesu˚ (vyb´ıra´ dlouho • Uvedený mechanismus je doplnen neaktivn´ı procesy).



Thrashing ˇ odstranovan´ ˇ ´ – I pˇri rozumne´ volbeˇ výberu ych stranek muˇ ˚ ze nastat tzv. thrashing: Proces (v horˇs´ım ´ ´ ı v´ıce cˇ asu nahradou ´ ´ pˇr´ıpadeˇ system) strav´ stranek neˇz uˇziteˇcným výpoˇctem.

´ znem ´ nedostatku pameti ˇ swapper pozastav´ı nekter ˇ ˇ ’. – Pˇri vaˇ e´ procesy a odloˇz´ı veˇskerou jejich pamet ˇ – Jinou moˇznost´ı je ukonˇcen´ı nekter´ ych procesu. ˚



´ Poznamky ´ et ˇ do systemu ´ ´ ´ – Prepaging: snaha zavad v´ıce stranek souˇcasneˇ (zejmena pˇri startu procesu cˇ i po ´ ı, ale i za beˇ ˇ zne´ cˇ innosti s ohledem na pˇredpokladanou ´ odswapovan´ lokalitu odkazu). ˚ načte z disku větší blok dat "do zásoby", může se však stát, že se načtou nepotřebná data

´ ı stranek: ´ – Zamykan´ ˇ • zabranuje odloˇzen´ı,

• uˇz´ıva´ se napˇr. – – – –

´ u stranek, do nichˇz prob´ıha´ I/O, ´ ı) tabulek stranek, ´ u (ˇcast´ ˇ ´ ´ u (nekter´ ych) stranek jadra, ´ ´ ı uˇzivatele (k jeho vyjadˇ ´ ren´ı slouˇz´ı v POSIXu – v ramci pˇrednastavených limitu˚ a na pˇran´ ´ en´ ˇ ı – volan´ ´ ı mlock()): citliva´ data, (soft) real-time procesy. opravn



´ Sd´ılen´ı stranek stránky, které se nacházejí v LAP různých procesů, jsou namapovány na stejný rámec fyzické paměti

´ ´ ı umoˇznuje ˇ ˇ – Strankov an´ jemnou kontrolu sd´ılen´ı pameti.

´ – Sd´ılen´ı stranek: ´ programu˚ (procesy ˇr´ızene´ stejným programem, sd´ılene´ knihovny), • kod

• konstantn´ı data nebo doposud nemodifikovana´ data u kopi´ı procesu˚ (technologie copy-on-write), • mechanismus IPC, ˇ ’oveˇ mapovaných souboru. • sd´ılen´ı pamet ˚



Sd´ılene´ knihovny

´ který je v dane´ verzi v FAP (a na disku) maximaln ´ eˇ jednou a – Sd´ılene´ knihovny ( .dll, .so): kod, muˇ ˚ ze být sd´ılen v´ıce procesy (procesy nemus´ı být ˇr´ızeny stejným programem). ´ • Výhody: menˇs´ı programy – lepˇs´ı vyuˇzit´ı FAP i diskoveho prostoru, moˇznost aktualizovat knihovny. ´ programu˚ na dalˇs´ıch souborech a verz´ıch knihoven, moˇzný pomalejˇs´ı start • Nevýhody: zavislost programu (je nutne´ dynamicky sestavit; na druhou stanu se ale zase muˇ ˚ ze uˇsetˇrit d´ıky nutnosti ´ et ˇ jiˇz zavedene´ stranky). ´ nezavad



Copy-on-Write

ˇ ı procesu pomoc´ı – Pˇri spuˇsten´

ˇ procesu. fork se nevytvoˇr´ı kopie veˇskere´ pameti

´ ´ – Vytvoˇr´ı se pouze tabulky stranek a stranky se poznaˇc´ı jako copy-on-write. ´ ´ – K vytvoˇren´ı fyzicke´ kopie stranky dojde aˇz pˇri pokusu o zapis jedn´ım z procesu. ˚

´ – Poznamka:


ˇ ’ je skuteˇcneˇ sd´ılena. vfork jako alternativa k fork s copy-on-write: pamet


ˇ ’ (shared memory) Sd´ılena´ pamet

´ stejne´ fyzicke´ stranky ´ – Forma IPC: V´ıce procesu˚ ma´ mapovany do LAP. –

shmget, shmat, shmctl, shmdt

Pˇr´ıklad: GIMP plugin



ˇ ’oveˇ mapovane´ soubory Pamet ´ do stranek ´ ˇ – Bloky souboru˚ jsou mapovany v pameti. ´ ´ ım na zˇ adost ´ ´ ach ´ do pameti ˇ a dale ´ muˇ ´ se – Soubory jsou strankov an´ naˇcteny po strank ˚ ze být prace ´ ˇ nam´ısto pouˇzit´ı read()/ write(). soubory realizovana standardn´ım pˇr´ıstupem do pameti ˇ r´ı se reˇzie se systemov´ ´ ´ ım, kop´ırovan´ ´ ı do bufferu a pak do pameti. ˇ Umoˇznuje ˇ – Setˇ ym volan´ sd´ılený pˇr´ıstup k souborum. ˚

´ ı – Dostupne´ prostˇrednictv´ım volan´ ´ Operaˇcn´ı systemy

mmap(). ´ pameti ˇ Sprava 40

ˇ ’ove´ regiony Pamet ˇ ’ove´ regiony jsou jednotkou vyˇssˇ ´ıho strukturovan´ ´ ı pameti ˇ v Unixu (pouˇz´ıvaj´ı se i dalˇs´ı: napˇr. – Pamet uzly - úsek paměti, ke kterému různé procesory přistupují různě ´ v Linuxu tzv. uzly a zony).

zóny - používají se pro odlišení části paměťového prostoru, se kterým pracuje HW nebo jádro

´ ı pameti ˇ pouˇzite´ za urˇcitým uˇ – Jedna´ se o spojite´ oblasti virtualn´ ´ celem (data – staticka´ inicializovana´ ´ zasobn´ ´ ´ eˇ mapovane´ pamet ˇ ’i – data, staticka´ neinicializovana´ data, hromada; kod; ık; useky individualn ´ ˇ ’, pamet ˇ ’oveˇ mapovane´ soubory, anonymn´ı mapovan´ ´ ı). sd´ılena´ pamet

´ ıc´ı pozici regionu v LAP procesu, pˇr´ıstupova´ – Kaˇzdý proces muˇ ˚ ze m´ıt tabulku regionu˚ procesu udavaj´ ´ ´ k regionu a odkazuj´ıc´ı na systemovou tabulku regionu˚ s dalˇs´ımi informacemi o reginu, sd´ılenými prava mezi procesy – pˇr´ıpadneˇ ma´ kaˇzdý proces vˇsechny potˇrebne´ udaje pˇr´ımo ve sve´ tabulce regionu. ´ ˚ ´ ´ – V systemov e´ tabulce regionu˚ je uvedena velikost regionu, typ, i-uzel souboru pˇr´ıpadneˇ mapovaneho do regionu apod.

´ muˇ ´ et ˇ nad regionem jako celkem nekter ˇ ˇ sovan´ ´ ı/zmenˇsovan´ ´ ı (u – System e´ operace: zvetˇ ˚ ze provad ´ ´ ı, mapovan´ ´ ı do pameti ˇ aj. datoveho regionu) brk, swapovan´



´ Rozloˇzen´ı adresoveho prostoru procesu v Linuxu (i386) pro 32b instalace

(Anatomy of a Program in Memory, G. Duarte)

adresový prostor jádra

zásobník pro aktivační záznamy vyvolávaných funkcí

část adresového prostoru používaná pro anonymně mapované úseky paměti či paměťově mapované soubory část LAP, se kterou proces může pracovat

region pro dynamickou alokaci

neinicializovaná statická data

statická data (globální inicializované proměnné) kód, který řídí proces



Fakulta informačních technologií Božetěchova 2, BRNO 26. dubna 2011

Recommend Documents