Přístup stránek/rámce

Teorie:

(Začátky teorie zde)

Optimální algoritmus:

  • Nahradí se stránka, která má čas příštího přístupu nejdelší (bude se k ní přistupovat nejdelší dobu)
  • Vlastnosti:
    • Lze dokázat, že tento algoritmus generuje min. počet výpadků stránek
    • Nelze použít v praxi protože neznáme budoucnost (můžeme ale použít pro porovnání kvality reálných algoritmů)

Příklad:

  • Ke stránkám se přistupovalo v pořadí: 2,3,2,1,5,2,4,5,3,2,5,2.
  • Fyzická paměť se skládá ze tří prázdných rámců a, b, c.
Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
Rámec a 2 2 2 4 2 2
Rámec b 3 3
Rámec c 1 5 5 5
Výpadek stránky X X X X X X

# Výpadků: 6.

Komentovaný postup:

Načteme (2) a (3) popořádku do rámců. Při dalším přístupu je (2) již v rámci a (nedošlo k výpadku).
(1) se načte do prázdné c. (5) - zde se koukneme do budoucnosti a vidíme, že (1) se nebude používat dále (ale (2) a (3) ano), tím pádem přepíšeme rámec c. (2) je načtená, zase nedojde k výpadku. (4) - zase se koukáme do budoucnosti, (2) se použije jako poslední, tedy přepíšeme a. atd.

Algoritmus NRU (Not recently used):

  • Většina systémů se stránováním si pro každou stránku pamatuje Reference bit a Modified bit.
  • Při načtení stránky do paměti jsou bity nastaveny na danou hodnotu
  • Tyto bity jsou nastavovány automaticky HW při každém přístupu ke stránce
    • Reference bit se nastaví, pokud se ke stránce přistupuje (read or write)
    • Modify bit se nastaví, pokud se změnil obsah stránky (write)
    • Abychom získali informaci, kdy se ke stránce přistupovalo, je nutné, aby OS periodicky resetoval Reference bit na 0
    • Na základě hodnot R/M bitů můžeme rozdělit stránky do 4 tříd:
      • Class 0: R=0; M=0
      • Class 1: R=0; M=1
      • Class 2: R=1; M=0
      • Class 3: R=1; M=1
    • Algoritmus NRU nahradí stránku z neprázdné třídy s nejnižším číslem

Příklad:

  • Pořadí... (viz tabulka), fyzická paměť: rámce a, b, c (prázdné).
  • OS resetujue R bit v časech , kde
    Jak se bude měnit obsazení rámců v průběhu času?
Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
R/W r r w r r r r r r w w r
time 1 4 9 10 15 17 20 21 22 25 27 30 31 32 37
Rámec a Stránka 2 2 2 2 2
Rámec a R 1 1 0 0 1 0 1 1
Rámec a M 0 1 1 1 1
Rámec b Stránka 3 5 4 3
Rámec b R 1 0 1 0 1 1 0
Rámec b M 0 0 0 0
Rámec c Stránka 1 5 5
Rámec c R 1 0 1 0 1
Rámec c M 0 0 1
Výpadek stránky X X X X X X X

# Výpadků: 7.

Komentovaný postup:

Prvně máme read na (2), použijeme rámec a dosteneme výpadek a nastavíme R=1,M=0.
Dále máme read na (3), použijeme b, apod.
Ještě jednou jsme dostali write na (2), tu máme již uloženou v a, přepíšeme M=1 a nedojde k výpadku.
Dojde k resetu všech R bitů na 0
Dostaneme read na (1), použijeme c.
Další je read na (5), a víme, že v a (R:0,M:1), b (R:0,M:0), c (R:1,M:0) -> použijeme b (pak bychom použili a, pak c).
Dojde k dalšímu resetu.
Dále read na (2), kterou máme uloženou v a. Nedojde k resetování Modify bitu na 0. Změní se hodnota R=1.
Read na (4) - vidíme, že v a (R:1,M:1), b (R:0,M:0), c (R:0,M:0) - postupujeme podle abecedy, takže použijeme b.
atd..

Algoritmus FIFO (First-In First-Out):

  • OS si udržuje seznam všech stránek, které se aktuálně nachází v hlavní paměti
  • V okamžiku, kdy se stránka nahraje do paměti, přidá se její záznam na konec seznamu
  • FIFO algoritmus ybere první stránku ze seznamu jako vhodného kandidáta pro náhradu
  • Nezohleďnuje, kdy se ke stránce přistupovalo, pouze kdy byla stránka nahrána do hlavní paměti relativně velký počet výpadků
Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
Rámec a 2 2 5 5 3
Rámec b 3 2 2 5
Rámec c 1 4 2
Začátek seznamu a a a a b c a a b b c a
Výpadek stránky X X X X X X X X X

(Pokud je více možností: volíme rámec ze začátku abecedy)

# Výpadků: 9.

Komentovaný postup:

Přiřadíme (2) do rámce a. Ve frontě máme (2) - ještě někde si pamatujeme, kam jsme uložili tu (2) - ale rozhodla jsem se, že zde to nebudu psát. Dostaneme výpadek
Přiřadíme (3) do rámce b. Ve frontě máme (3, 2), další výpadek
Dostaneme požadavek na (2), ten je již uložený v paměti.
Dále máme 1, ve frontě jsou tyto prvky (1, 3, 2).
Další stránkou je (5), ta se dostane na místo (2) - je poslední v seznamu, a nyní fronta bude vypadat takto: (5, 1, 3)
...

Algoritmus Clock:

  • Modifikace FIFO
  • Seznam stránek je implementovaný jako kruhová fronta
  • Na počátku ručička (ukazatel) ukazuje na první položku fronty
  • Pro každou stránku si pamatujeme její Reference bit.
    • Stránka se nahraje do paměti -> OS nastaví R bit = 1
    • Při každém R/W se stránce nastaví R bit = 1
  • Postup při hledání vhodné stránky pro náhradu:
  1. Pokud ručička ukazuje na stránku, kde R = 1, potom se nastaví R = 0 a ručička se posune na další položku ve frontě
  2. Krok 1. se bude opakovat dokud se nenajde stránka s R = 0. Tato stránka se nahradí a ručička se posune dál
Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
Rámec a, Stránka 2 2 5 5 3
Rámec a, R 1 1 1 1 1
Rámec b, Stránka 3 2 2 2
Rámec b, R 1 0 1 0 1 0 1
Rámec c, Stránka 1 4 5
Rámec c, R 1 0 1 0 1
Ručička ukazuje na a a a a b c a a b b a
Výpadek stránky X X X X X X X X

# Výpadků: 8.

Komentovaný postup:

Nahrajeme stránku (2) do paměti, R=1. Ručička ukazuje na a
Nahrajeme stránku (3) do paměti, R=1. Ručička bude stále ukazovat na a jelikož nehledáme náhradu pro stránku.
Pro (2) nemusíme nic dělat, je stále ještě nahraná v paměti. Nic se nemění.
Situace se opakuje s (1), R=1. Ručička stále ukazuje na a. (Ručička se ve fázi, kdy stále ještě máme v rámcích místo, nemění)
Chceme nahrát (5). Ručička ukazuje na a, kde R=1. Přepíšeme u a R=0, pokračujeme s b, kde taky nastavíme R=0, to samé uděláme i s c. Nakonec se dostaneme zpátky na a, kde R=0. Zde nahrajeme (5) s R=1. Ručička se posune na další rámec - b.
Zase chceme nahrát (2). Ručička ukazuje na b, kde R=0 -> Nahrazujeme. Ručička se posune na c.
Máme další kolizi, chceme nahrát (4), ale to není problém, protože R=1. Přepíšeme a ručička ukazuje na a.
atd.. (Jestliže dojde k nahrání té samé stránky, která je již uložená a R=0, tak se nic neposouvá, jenom se přenastaví R na 1)

Dodatek (není potřeba ke zkoušce) - existuje two-handed clock algoritmus (který už se používá v reálných OS). Víc v 9. přednášce z BI-OSY.

Algoritmus LRU (Least recently used):

  • vhodným kandidátem pro náhradu je stránka, ke které se nepřistupovalo nejdelší dobu
  • Dobra aproximace opt. algo/problematická implementace (např. HW čítač)
Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
Rámec a 2 2 2 3
Rámec b 3 5 5 5
Rámec c 1 4 2 2
Výpadek stránky X X X X X X X

# Výpadků: 7.

Nahrazujeme nejstarší stránku v tabulce

Příklad ze zkoušky:

V systému jsou k dispozici celkem 4 rámce, které pro přehlednost označíme a, b, c a d. Pro konfiguraci platí:

  • Na začátku jsou tyto rámce prázdné
  • Pokud algoritmus na náhradu stránek může umístit stránku do více rámců, vždy zvolí rámec, který je první v abecedě.
  • Pokud algoritmus periodicky modifikuje R bit, pak se tak děje v časech kde,
  • Pokud algoritmus periodicky modifikuje M bit, pak se tak děje v časech kde,
  • Ke stránkám se přistupuje v následujícím pořadí:
time 11 17 29 42 53 55 68 73 77 88 96 104 110 118
R/W r w w w w r r w r w r w r r
page# 2 0 3 3 9 2 5 1 1 5 3 9 8 9

Ke kolika výpakům stránky (page fault) by došlo, pokud by systém používal algoritmus LRU?

Jaké stránky budou v jednotlivých rámcích po posledním přístupu? Uveďte jako uspořádaný seznam čísel stránek nahraných v rámcích a, b, c a d (např. 70, 63, 85, 46).

Podstatné je zde pro nás jenom to číslo stránky, v tomto případě.

page# 2 0 3 3 9 2 5 1 1 5 3 9 8 9
a 2 2 9 9
b 0 5 5
c 3 3 1 1 8
d 9 3
Výpadek X X X X X X X X X

# Výpadků: 9, a=(9), b=(5), c=(8), d=(3).

Algoritmus Aging

  • softwarová simulace LRU algoritmu
  • pro každou stránku si systém pamatuje:
    • Reference bit (R/W)
    • n-bitový čítač C, který má všechny bity nastavené na 1 při načtení stránky do paměti
  • Systém periodicky pro každou stránku:
    1. posune obsah čítače C doprava o jeden bit
    2. nastaví hodnotu nejvýznamějšího bitu čítače C na hodnotu R bitu
    3. resetuje hodnotu R bitu na hodnotu 0
  • vhodným kanidátem pro náhradu bude stránka, jejíž čítač C má nejmenší hodnotu

Čítač C je reprezentován 3 bity

Číslo stránky 2 3 2 1 5 2 4 5 3 2 5 2
time 1 4 9 10 15 17 20 21 22 25 27 30 31 32 37
Rámec a Stránka 2 2 5 4 5 3
Rámec a R 1 1 0 1 0 1 1 1 0
Rámec a C 7 7 7 7 7 7 7 7 7
Rámec b Stránka 3 2 2 2
Rámec b R 1 0 0 1 0 1 1
Rámec b C 7 7 3 7 7 7 7
Rámec c Stránka 1 5
Rámec c R 1 0 0 1
Rámec c C 7 7 3 7
Výpadek stránky X X X X x X X X X

# Výpadků: 9.

"Cheat sheet":

  • Optimální algoritmus
    • Žádné bity navíc, jenom se koukáme do historie budoucnosti
  • NRU (not recently used)
    • Bity Reference a Modify, nahrazuje se podle tohohle schématu:
    1. R=0;M=0
    2. R=0;M=1
    3. R=1;M=0
    4. R=1;M=1
    • V času dochází k resetu bitu R
  • FIFO
    • Udržujeme si seznam/frontu, jestliže je fronta plná, tak nahrazujeme nejstarší prvek ve frontě
  • Clock
    • Máme ručičku ukazující na "konec" kruhové fronty, Reference bit
    • Při hledání místa na náhradu tak posouváme ručičku dál a nastavujeme R=0
  • LRU (least recently used)
    • Velmi jednoduše nahrazujeme nejstarší stránku v paměti
  • Aging
    • Máme čítač C a Reference bit (nastaven při R/W). OS v času nastavuje R=0 a posouvá C doprava (resp. dělí 2) a k nejvyššímu bitu se přičítá bývalá hodnota R.
    • Při nahrazování: nahrazujeme stránku s nejnižším čítačem. Když se načte nová stránka (ne ta, co byla v paměti), tak se čítač aktualizuje a nastaví se R=1. V případě staré stránky se jenom nastaví R=1 (a hodnota se pak přičte k C).