Algoritmy nahrazování stránek paměti

Obsah 1 Relokace při zavedení do paměti 2 Mechanismus báze a limitu (Dynamická relokace) 3 Pojmy 4 Výpadek stránky 5 Algoritmus FIFO 6 Algoritmus MIN/OPT 7 Algoritmus Least Recently Used 8 Algoritmus Not-Recently-Used

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

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

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)

• 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ý 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