Algoritmy nahrazování stránek paměti
Z FAV wiki
(Rozdíly mezi verzemi)
(Založena nová stránka: · Pokud všechny rámce obsazené a nastane výpadek stránky, je nutné některou stránku vyhodit a rámec uvolnit · Vyhození - Pokud byla stránka modifikována, zap...) |
m (kategorizace) |
||
| (Nejsou zobrazeny 3 mezilehlé verze od 1 uživatele.) | |||
| Řádka 1: | Řádka 1: | ||
| − | + | == Relokace při zavedení do paměti == | |
| − | + | ||
| − | + | Program volá instrukci na adrese 66 ale sám v paměti běží až od adresy 1000. Tedy instrukce se nechází na adrese 1066. - Při zavedení programu do paměti provede Linker modifikaci, aby adresy souhlasily | |
| − | + | ||
| − | + | ||
| − | Algoritmus FIFO | + | == Mechanismus báze a limitu (Dynamická relokace) == |
| − | + | ||
| − | + | Jednotka správy paměti (MMU) mezi procesorem a pamětí obsahuje dva registry: | |
| − | Algoritmus MIN/OPT | + | * báze - počáteční adresa oblasti |
| − | + | * limit - velikost oblasti | |
| − | + | ||
| − | + | Dostává adresu od CPU a pževádí ji na adresu v paměti | |
| − | + | ||
| − | Algoritmus Least Recently Used | + | |
| + | |||
| + | == Pojmy == | ||
| + | * virtuální paměť - stránky (pages) stejné délky | ||
| + | * fyzická paměť - rámce (stejné délky) | ||
| + | * rámec může obsahovat právě jednu stránku | ||
| + | * na známém místě v paměti tabulka stránek, poskytuje mapování virtuálních stránek na rámce | ||
| + | |||
| + | |||
| + | |||
| + | == Výpadek stránky == | ||
| + | * Pokud všechny rámce obsazené a nastane výpadek stránky, je nutné některou stránku vyhodit a rámec uvolnit (dojde k přerušení, zavede se požadovaná stránka, program může pokračovat v běhu) | ||
| + | * Vyhození | ||
| + | ** Pokud byla stránka modifikována, zapíše se na disk | ||
| + | ** Pokud oproti kopii na disku nebyla modifikovaná, bude pouze uvolněna | ||
| + | * Otázka - kterou stránku vyhodit? | ||
| + | |||
| + | Tabulka stránek procesu - v MMU, obsahuje stránky daného procesu, mapuje číslo stránky na fyzickou adresu rámce, řeší realokaci a ochranu | ||
| + | |||
| + | |||
| + | == Algoritmus FIFO == | ||
| + | |||
| + | * Udržujeme seznam všech stránek v pořadí, ve kterém byly zavedeny | ||
| + | * Vyhazujeme nejstarší stránku (je možné, že se vyhodí stránka, která se bude brzy potřebovat) | ||
| + | |||
| + | |||
| + | |||
| + | == Algoritmus MIN/OPT == | ||
| + | |||
| + | * V paměti je množina stránek, každá stránka je označena počtem instrukcí, po který se k ní nebude přistupovat | ||
| + | * V okamžiku výpadku stránky se vybere stránka s nejvyšším označením | ||
| + | * Algoritmus je optimální, tj. vybere se stránka, která bude zapotřebí nejvzdáleněji v budoucnosti | ||
| + | * Není realizovatelný (neexistuje způsob, jakým by OS mohl zjistit, která stránka bude zapotřebí jako příští) | ||
| + | |||
| + | |||
| + | |||
| + | == Algoritmus Least Recently Used == | ||
| + | |||
nejdele nepouzita (pohled do minulosti) | nejdele nepouzita (pohled do minulosti) | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | Algoritmus Clock | + | * princip lokality |
| + | ** stranky pouzivane v poslednich instrukcich se budou pravdepodobne pouzivat i v nasledujicich | ||
| + | ** pokud se stranka dlouho nepouzivala, pravdepodobne nebude brzy zapotrebi | ||
| + | |||
| + | Vyhazovat zbozi, na kterem je v prodejne nejvice prachu = nejdele nebylo pozadovano | ||
| + | |||
| + | * Obtizna implementace | ||
| + | * sw reseni (neni pouzitelne) | ||
| + | ** seznam stranek v poradi referenci | ||
| + | ** vypadek - vyhozeni stranky ze zacatku seznamu | ||
| + | ** zpomaleni cca 10x, nutna podpora hw | ||
| + | * hw reseni - citac | ||
| + | ** MMU obsahuje citac (64bit), pri kazdem pristupu do pameti zvetsen | ||
| + | ** kazda polozka v tabulce stranek - pole pro ulozeni citace | ||
| + | ** odkaz do pameti | ||
| + | ** obsah citace se zapise do polozky pro odkazovanou stranku | ||
| + | ** vypadek stranky - vyhodí se stranka s nejnizsim cislem | ||
| + | |||
| + | Realizece čítače pomocí matice | ||
| + | |||
| + | |||
| + | == Algoritmus Not-Recently-Used == | ||
| + | |||
| + | * Bit R - nastaven na 1 při čtení nebo zápisu do stránky | ||
| + | * Bit M - nastaven na 1 při zápisu do stránky; označuje, že se stránka má při vyhození zapsat na disk | ||
| + | |||
| + | Na začátku mají všechny stránky R=0, M=0, bit R je OS nastavován periodicky na 0 | ||
| + | |||
| + | 4 kategorie: | ||
| + | * Třída 0: R=0, M=0 | ||
| + | * Třída 1: R=0, M=1 | ||
| + | * Třída 2: R=1, M=0 | ||
| + | * Třída 3: R=1, M=1 | ||
| + | |||
| + | Algoritmus vyhodí stránku z nejnižší neprázdné třídy, výběr mezi stránkami ve stejné třídě je náhodný | ||
| + | Jednoduchý, efektivně implementovatelný, ale nevýkonný | ||
| + | |||
| + | (R = referenced) | ||
| + | |||
| + | |||
| + | == Algoritmus Second Chance == | ||
| + | |||
| + | * Vychází z algoritmu FIFO | ||
| + | * Vyhledává nejstarší stránku, která nebyla referencována v poslední době | ||
| + | * Pokud byly všechny referencovány => FIFO | ||
| + | |||
| + | Snaží se zabranit vyhozeni casto pouzivane - dle bitu R nejstarsi stranky R = 0 ... stranka je nejstarsi, nepouzivana, vyhodime. Pokud R = 1 ... nastavme | ||
| + | R=0, presuneme na konec seznamu stranek (jako by byla nove zavedena) a vezmeme další v pořadí. | ||
| + | |||
| + | [[Soubor:Second-chance.jpg]] | ||
| + | |||
| + | |||
| + | == Algoritmus Clock == | ||
| + | |||
Optimalizace datovych struktur algoritmu Second Chance | Optimalizace datovych struktur algoritmu Second Chance | ||
| − | + | * Stranky udrzovany v kruhovem seznamu | |
| − | + | * Ukazatel na nejstarsi stranku { "rucicka hodin\ | |
| − | + | * Vypadek stranky { najit stranku k vyhozeni | |
| − | + | * Stranka kam ukazuje rucicka | |
| − | + | ** ma-li R=0, stranku vyhodime a rucicku posuneme o jednu pozici | |
| − | + | ** ma-li R=1, nastavime R na 0, rucicku posuneme o 1 pozici, opakovani,.. | |
| − | + | * Od SC se lisi pouze implementaci | |
| − | + | * Varianty Clock pouzivaji napr. BSD UNIX | |
| + | |||
| + | |||
| + | == Algoritmus Aging == | ||
| + | |||
| + | * Každá položka má pole „stáří“, na počátku = 0 | ||
| + | * Při každém přerušení časovače - posun pole „stáří“ o 1 bit vpravo, zleva se přidá hodnota bitu R, nastavení R na 0 | ||
| + | * Při výpadku stránky se vyhodí stránka, jejíž pole „stáří“ má nejnižší hodnotu | ||
| + | |||
| + | {{fav-kiv-bzinf}} | ||
| + | |||
| − | + | [[Kategorie:fav-kiv-bzinf]] | |
| − | + | ||
| − | + | ||
| − | + | ||
Aktuální verze z 20. 2. 2014, 06:48
Obsah |
[editovat] Relokace při zavedení do paměti
Program volá instrukci na adrese 66 ale sám v paměti běží až od adresy 1000. Tedy instrukce se nechází na adrese 1066. - Při zavedení programu do paměti provede Linker modifikaci, aby adresy souhlasily
[editovat] Mechanismus báze a limitu (Dynamická relokace)
Jednotka správy paměti (MMU) mezi procesorem a pamětí obsahuje dva registry:
- báze - počáteční adresa oblasti
- limit - velikost oblasti
Dostává adresu od CPU a pževádí ji na adresu v paměti
[editovat] Pojmy
- virtuální paměť - stránky (pages) stejné délky
- fyzická paměť - rámce (stejné délky)
- rámec může obsahovat právě jednu stránku
- na známém místě v paměti tabulka stránek, poskytuje mapování virtuálních stránek na rámce
[editovat] Výpadek stránky
- Pokud všechny rámce obsazené a nastane výpadek stránky, je nutné některou stránku vyhodit a rámec uvolnit (dojde k přerušení, zavede se požadovaná stránka, program může pokračovat v běhu)
- Vyhození
- Pokud byla stránka modifikována, zapíše se na disk
- Pokud oproti kopii na disku nebyla modifikovaná, bude pouze uvolněna
- Otázka - kterou stránku vyhodit?
Tabulka stránek procesu - v MMU, obsahuje stránky daného procesu, mapuje číslo stránky na fyzickou adresu rámce, řeší realokaci a ochranu
[editovat] Algoritmus FIFO
- Udržujeme seznam všech stránek v pořadí, ve kterém byly zavedeny
- Vyhazujeme nejstarší stránku (je možné, že se vyhodí stránka, která se bude brzy potřebovat)
[editovat] Algoritmus MIN/OPT
- V paměti je množina stránek, každá stránka je označena počtem instrukcí, po který se k ní nebude přistupovat
- V okamžiku výpadku stránky se vybere stránka s nejvyšším označením
- Algoritmus je optimální, tj. vybere se stránka, která bude zapotřebí nejvzdáleněji v budoucnosti
- Není realizovatelný (neexistuje způsob, jakým by OS mohl zjistit, která stránka bude zapotřebí jako příští)
[editovat] Algoritmus Least Recently Used
nejdele nepouzita (pohled do minulosti)
- princip lokality
- stranky pouzivane v poslednich instrukcich se budou pravdepodobne pouzivat i v nasledujicich
- pokud se stranka dlouho nepouzivala, pravdepodobne nebude brzy zapotrebi
Vyhazovat zbozi, na kterem je v prodejne nejvice prachu = nejdele nebylo pozadovano
- Obtizna implementace
- sw reseni (neni pouzitelne)
- seznam stranek v poradi referenci
- vypadek - vyhozeni stranky ze zacatku seznamu
- zpomaleni cca 10x, nutna podpora hw
- hw reseni - citac
- MMU obsahuje citac (64bit), pri kazdem pristupu do pameti zvetsen
- kazda polozka v tabulce stranek - pole pro ulozeni citace
- odkaz do pameti
- obsah citace se zapise do polozky pro odkazovanou stranku
- vypadek stranky - vyhodí se stranka s nejnizsim cislem
Realizece čítače pomocí matice
[editovat] Algoritmus Not-Recently-Used
- Bit R - nastaven na 1 při čtení nebo zápisu do stránky
- Bit M - nastaven na 1 při zápisu do stránky; označuje, že se stránka má při vyhození zapsat na disk
Na začátku mají všechny stránky R=0, M=0, bit R je OS nastavován periodicky na 0
4 kategorie:
- Třída 0: R=0, M=0
- Třída 1: R=0, M=1
- Třída 2: R=1, M=0
- Třída 3: R=1, M=1
Algoritmus vyhodí stránku z nejnižší neprázdné třídy, výběr mezi stránkami ve stejné třídě je náhodný Jednoduchý, efektivně implementovatelný, ale nevýkonný
(R = referenced)
[editovat] Algoritmus Second Chance
- Vychází z algoritmu FIFO
- Vyhledává nejstarší stránku, která nebyla referencována v poslední době
- Pokud byly všechny referencovány => FIFO
Snaží se zabranit vyhozeni casto pouzivane - dle bitu R nejstarsi stranky R = 0 ... stranka je nejstarsi, nepouzivana, vyhodime. Pokud R = 1 ... nastavme R=0, presuneme na konec seznamu stranek (jako by byla nove zavedena) a vezmeme další v pořadí.
[editovat] Algoritmus Clock
Optimalizace datovych struktur algoritmu Second Chance
- Stranky udrzovany v kruhovem seznamu
- Ukazatel na nejstarsi stranku { "rucicka hodin\
- Vypadek stranky { najit stranku k vyhozeni
- Stranka kam ukazuje rucicka
- ma-li R=0, stranku vyhodime a rucicku posuneme o jednu pozici
- ma-li R=1, nastavime R na 0, rucicku posuneme o 1 pozici, opakovani,..
- Od SC se lisi pouze implementaci
- Varianty Clock pouzivaji napr. BSD UNIX
[editovat] Algoritmus Aging
- Každá položka má pole „stáří“, na počátku = 0
- Při každém přerušení časovače - posun pole „stáří“ o 1 bit vpravo, zleva se přidá hodnota bitu R, nastavení R na 0
- Při výpadku stránky se vyhodí stránka, jejíž pole „stáří“ má nejnižší hodnotu
