Algoritmy nahrazování stránek paměti - Historie editací

Acolade: kategorizace

2014-02-20T06:48:45Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:48
Řádka 1:		Řádka 1:
−
	== Relokace při zavedení do paměti ==		== Relokace při zavedení do paměti ==

Řádka 125:		Řádka 124:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+
		+
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Algoritmus Aging */

2011-08-30T07:35:51Z

Algoritmus Aging

← Starší verze		Verze z 30. 8. 2011, 07:35
Řádka 123:		Řádka 123:
	* 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 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		* Při výpadku stránky se vyhodí stránka, jejíž pole „stáří“ má nejnižší hodnotu
		+
		+	{{fav-kiv-bzinf}}

Tester: /* Algoritmus Not-Recently-Used */

2011-08-30T07:35:24Z

Algoritmus Not-Recently-Used

← Starší verze		Verze z 30. 8. 2011, 07:35
Řádka 76:		Řádka 76:
	== Algoritmus Not-Recently-Used ==		== Algoritmus Not-Recently-Used ==

−	· Bit R - nastaven na 1 při čtení nebo zápisu do stránky	+	* 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	+	* 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:	+	Na začátku mají všechny stránky R=0, M=0, bit R je OS nastavován periodicky na 0
−	Třída 0: R=0, M=0	+
−	Třída 1: R=0, M=1	+	4 kategorie:
−	Třída 2: R=1, M=0	+	* Třída 0: R=0, M=0
−	Třída 3: R=1, M=1	+	* Třída 1: R=0, 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ý	+	* Třída 2: R=1, M=0
−	· Jednoduchý, efektivně implementovatelný, ale nevýkonný	+	* Třída 3: R=1, M=1
−	Algoritmus Second Chance	+
−	· Vychází z algoritmu FIFO	+	Algoritmus vyhodí stránku z nejnižší neprázdné třídy, výběr mezi stránkami ve stejné třídě je náhodný
−	· Vyhledává nejstarší stránku, která nebyla referencována v poslední době	+	Jednoduchý, efektivně implementovatelný, ale nevýkonný
−	· Pokud byly všechny referencovány => FIFO	+
−	{ zabranit vyhozeni casto pouzivane	+	(R = referenced)
−	{ dle bitu R nejstarsi stranky R = 0 ... stranka je nejstarsi, nepouzivana { vyhodime R = 1 ... nastavme	+
−	R=0, presuneme na konec seznamu stranek (jako by byla nove zavedena)	+
		+	== 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 ==

−	~~Algoritmus Clock~~
	Optimalizace datovych struktur algoritmu Second Chance		Optimalizace datovych struktur algoritmu Second Chance
−	� Stranky udrzovany v kruhovem seznamu	+	* Stranky udrzovany v kruhovem seznamu
−	� Ukazatel na nejstarsi stranku { "rucicka hodin\	+	* Ukazatel na nejstarsi stranku { "rucicka hodin\
−	� Vypadek stranky { najit stranku k vyhozeni	+	* Vypadek stranky { najit stranku k vyhozeni
−	� Stranka kam ukazuje rucicka	+	* Stranka kam ukazuje rucicka
−	{ ma-li R=0, stranku vyhodime a rucicku posuneme o jednu pozici	+	** 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,..	+	** ma-li R=1, nastavime R na 0, rucicku posuneme o 1 pozici, opakovani,..
−	� Od SC se lisi pouze implementaci	+	* Od SC se lisi pouze implementaci
−	� Varianty Clock pouzivaji napr. BSD UNIX	+	* Varianty Clock pouzivaji napr. BSD UNIX
		+
		+
		+	== Algoritmus Aging ==

−	~~Algoritmus Aging~~	+	* Každá položka má pole „stáří“, na počátku = 0
−	· 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 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
−	· Při výpadku stránky se vyhodí stránka, jejíž pole „stáří“ má nejnižší hodnotu	+

Tester v 30. 8. 2011, 06:21

2011-08-30T06:21:32Z

← Starší verze		Verze z 30. 8. 2011, 06:21
Řádka 1:		Řádka 1:
−	· Pokud všechny rámce obsazené a nastane výpadek stránky, je nutné některou stránku vyhodit a rámec uvolnit	+
−	· Vyhození	+	== Relokace při zavedení do paměti ==
−	- Pokud byla stránka modifikována, zapíše se na disk	+
−	- Pokud oproti kopii na disku nebyla modifikovaná, bude pouze uvolněna	+	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
−	· Otázka - kterou stránku vyhodit?	+
−	Algoritmus FIFO	+
−	· Udržujeme seznam všech stránek v pořadí, ve kterém byly zavedeny	+	== Mechanismus báze a limitu (Dynamická relokace) ==
−	· Vyhazujeme nejstarší stránku (je možné, že se vyhodí stránka, která se bude brzy potřebovat)	+
−	Algoritmus MIN/OPT	+	Jednotka správy paměti (MMU) mezi procesorem a pamětí obsahuje dva registry:
−	· 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	+	* báze - počáteční adresa oblasti
−	· V okamžiku výpadku stránky se vybere stránka s nejvyšším označením	+	* limit - velikost oblasti
−	· 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í)	+	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)
−	� princip lokality	+
−	{ stranky pouzivane v poslednich instrukcich se budou pravdepodobne pouzivat i v nasledujicich	+	* princip lokality
−	{ pokud se stranka dlouho nepouzivala, pravdepodobne nebude brzy zapotrebi	+	** stranky pouzivane v poslednich instrukcich se budou pravdepodobne pouzivat i v nasledujicich
−	� Vyhazovat zbozi, na kterem je v prodejne nejvice prachu = nejdele nebylo pozadovano	+	** pokud se stranka dlouho nepouzivala, pravdepodobne nebude brzy zapotrebi
−	� Obtizna implementace	+
−	� sw reseni (neni pouzitelne)	+	Vyhazovat zbozi, na kterem je v prodejne nejvice prachu = nejdele nebylo pozadovano
−	{ seznam stranek v poradi referenci	+
−	{ vypadek { vyhozeni stranky ze zacatku seznamu	+	* Obtizna implementace
−	{ zpomaleni cca 10x, nutna podpora hw	+	* sw reseni (neni pouzitelne)
−	� hw reseni { citac	+	** seznam stranek v poradi referenci
−	� MMU obsahuje citac (64bit), pri kazdem pristupu do pameti zvetsen	+	** vypadek - vyhozeni stranky ze zacatku seznamu
−	� kazda polozka v tabulce stranek { pole pro ulozeni citace	+	** zpomaleni cca 10x, nutna podpora hw
−	� odkaz do pameti	+	* hw reseni - citac
−	{ obsah citace se zapise do polozky pro odkazovanou stranku	+	** MMU obsahuje citac (64bit), pri kazdem pristupu do pameti zvetsen
−	� vypadek stranky ~~{ vyhod��~~ se stranka s nejnizsim cislem	+	** kazda polozka v tabulce stranek - pole pro ulozeni citace
−	Algoritmus Not-Recently-Used	+	** 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 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		· 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

Tester: 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...

2011-08-08T15:24:53Z

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

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íše se na disk
- Pokud oproti kopii na disku nebyla modifikovaná, bude pouze uvolněna
· Otázka - kterou stránku vyhodit?
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)
� 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
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ý
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
{ zabranit vyhozeni casto pouzivane
{ dle bitu R nejstarsi stranky R = 0 ... stranka je nejstarsi, nepouzivana { vyhodime R = 1 ... nastavme
R=0, presuneme na konec seznamu stranek (jako by byla nove zavedena)

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

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