Virtuální paměť
===============

* už před dlouhou dobou problém, že programy jsou větší než dostupná fyzická 
  paměť
 - 2 způsoby řešení:
  1. mechanismus překrývání (overlays)
  2. virtuální paměť.

1. překrývání (overlays):
.........................
* program rozdělen na části, například moduly
* nejjednodušší varianta: při startu spuštěna část 0, při svém
  skončení zavede část 1, ...
* problém - časté zavádění některých modulů, proto některé systémy
  složitější:
 - více překryvných modulů + data v paměti současně
 - moduly zaváděny podle potřeby, mechanismus odkládání (podobně jako
   u odkládání procesů)

* mechanismus zavádění zařizoval OS, ale rozdělení programů i dat na
  části programátor
 - vhodné rozdělení do modulů ovlivňuje výkonnsot, značná komplikace
 - pro každou úlohu nutné nové rozdělení
=> snaha "hodit to na počítač" (aby to zařídil) 

* některé systémy pokusy o automatickou segmentaci, nevede k cíli
* virtuální paměť (Fortheringham 1961) 

2. virtuální paměť
..................
* potřebujeme počítač s velmi rozsáhlým, prakticky téměř neomezeným
  adresovým prostorem
* kdybychom celý prostor realizovali skutečnou pamětí - neúměrně drahé
* chceme, aby ve skutečné paměti realizována pouze část adresového
  prostoru
* kterou část? - tu, kterou právě potřebujeme

Jako mnoho jiných technických objevů má i tato myšlenka své předchůdce
v historii. Podobný nápad ušetřil konšelům města Kocourkova spoustu
peněz za koberce, když se chystali uvítat ve městě krále. Neznámý
génius přišel tehdy na to, že k (virtuálnímu) pokrytí celé cesty od
městské brány až k radnici stačí všeho všudy dva (reálné) koberce. Když
král jeden z nich přejde, musí ho dva sluhové (sloužící coby operační
systém) přenést dopředu dříve, než král dojde na konec druhého. Potíže,
jak známo, vznikly jen z toho, že sluhové spěchali a podtrhli
královskému průvodu nohy.

* původně adresa = číslo paměťové buňky
 - paměť = souvislé pole adres, číslovaných od 0 např. do 65535
 - adresa moderních počítačů 32 (=> 4 GB) nebo 64 bitů (=> moc)

* je-li virtuální paměť, adresa neznamená přímo číslo paměťové buňky 
 => nutný mechanismus, jak rychle a jednoznačně zjistit:
   - zda je příslušná část virtuálního paměťového prostoru v daném
     okamžiku v paměti realizována
   - pokud ano, kde

* adresa: 
 - virtuální - adresuje virtuální paměťový prostor
 - fyzická 
* nutný mechanismus převodu virtuální adresy na fyzickou
* program používá (CPU generuje) virtuální adresy
* mezi procesorem a pamětí je koncepčně umístěna jednotka správy
  paměti (Memory Management Unit, MMU), která tyto převody provádí 
* původně samostatná jednotka, dnes součástí mikroprocesoru

       procesorová karta
,-------------------------------. fyzická
|/-----\ virtuální adr.  /-----\| adresa  +-------+
|| CPU |---------------->| MMU |==========| paměť |
|\-----/                 \-----/|         +-------+
`-------------------------------'

* jak převést virtuální adresu na fyzickou?
- převod musí být co nejrychlejší (provádí se při každém přístupu k
  paměti)
- proto se virtuální adresový prostor rozdělí na stránky (pages) pevné délky
- délka stránky mocnina 2 
- nejčastěji 4KB, běžně se používají od 512 B do 8 KB
- fyzická paměť rozdělena na části stejné délky - rámce (page frames,
  česky také stránkové rámy, regály - terminologie je i v angličtině
  nejednotná)
- rámec může obsahovat právě jednu stránku
- na známém místě v paměti je uložena mapa - tabulka stránek
- tabulka stránek poskytuje mapování virtuálních stránek na rámce

* mechanismus převodu:

      virtuální adresa .. VA
      fyzická adresa .... FA
      číslo stránky ..... str
      offset ............ offset
      číslo rámce ....... ramec

1. virtuální adresu rozdělíme na číslo stránky a offset:

      str = VA div 4096
   offset = VA mod 4096

2. číslo stránky převedeme na číslo rámce pomocí tabulky stránek:

   Například tabulka stránek může vypadat takto:

   tab_str[0] = 2
   tab_str[1] = 0
   tab_str[2] = -- (stránka není mapována)

   Je-li VA=3, pak:
      str    = 0
      offset = 3
      ramec  = tab_str[str] = tab_str[0] = 2

3. z čísla rámce a offsetu sestavíme fyzickou adresu:

   FA = ramec*4096 + offset = 2*4096 + 3 = 8195


* nechceme dělit, proto velikost stránky mocnina dvou - 2^12 = 4096 (4 KB)
- nejnižších 12 bitů virtuální adresy = relativní adresa od počátku
  stránky (offset)
- svrchní bity virtuální adresy = pořadové číslo stránky ve virtuálním
  adresovém prostoru => index do tabulky stránek
- offset není nutné transformovat, je i relativní adresou uvnitř rámce

            (12 bitů)
   3 = 0000 000000000011 = str=0, offset=3 
    -> 0010 000000000011 = ramec=2, offset=3 
   
* každá položka tabulky stránek:
  . příznak: je stránka mapována? (present/absent bit)
  . pořadové číslo rámce
- převod: podle čísla stránky MMU najde číslo rámce, to vyšle na
  sběrnici

Poznámka: 

tento výklad je poněkud zjednodušený:
1. tabulky stránek mohou být velkého rozsahu; např. adresa 32 bitů -> 
   1 mil. stránek, ne všechny obsazeny - různé optimalizace uložení
2. přístup musí být rychlý - přístup k paměti úzké místo
   není možné pokaždé přistupovat k paměti - různá HW řešení,
   například kopie části tabulky v MMU


* fyzická paměť není nic o rámcích, rozdělení jen v MMU

  Adresa 8192 = (2, 0) nelze! - není mapování

* není mapována - způsobí událost výpadek stránky
 - výpadek stránky způsobí výjimku, tu zachytí OS
 - OS iniciuje zavádění stránky a přepne na jiný program
 - po zavedení stránky OS vytvoří pro mapování
 - program může pokračovat
 => dva problémy: kam stránku zavést a odkud?

OS musí řešit:
- hospodaření s rámci fyzické paměti
- uložení stránek, které nejsou právě ve fyzické paměti

Algoritmy nahrazování stránek
-----------------------------

* 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 modifikována, jen se uvolní

* otázka - kterou stránku vyhodit?
 - např. náhodně - kdybychom vybrali užívanou stránku, musela by se
   zase brzy zavést, stojí čas
 - lepší vybrat takovou, která se dlouho nebude potřebovat
 - existuje mnoho teoretických i experimentálních studií o různých
   aspektech algoritmů pro nahrazování stránek; my zmíníme jen ty
   nejzajímavější

Algoritmus MIN/OPT - optimální nahrazování
..........................................

* algoritmus:
- 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 
  (např. p[0]=10, p[1]=100, p[3]=1000)
- 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

* jediný problém algoritmu je, že není realizovatelný
- neexistuje způsob, jakým by OS mohl zjistit, která stránka bude
  zapotřebí jako příští
- optimální algoritmus slouží pro srovnání s realizovatelnými algoritmy
- program poběží v simulátoru, uchovají se odkazy na stránky a z toho
  se spočte počet výpadků
- počet výpadků se srovná s počtem výpadků realizovatelného algoritmu
  (pokud je rozdíl 1%, není možné vylepšení o více než o 1%)

* relálně používané algoritmy:

Algoritmus Not-Recently-Used (NRU, NUR)
.......................................

* OS se snaží zjistit, které stránky se používají a vyhazovat nepoužívané
* systémy s VM poskytují HW podporu - většina počítačů s VM má s každou
  stránkou sdruženy dva stavové bity nastavované HW podle způsobu
  přístupu ke stránce
 - bit R - nastaven na 1 při čtení nebo zápisu do stránky (referenced)
 - bit M - nastaven na 1 při zápisu do stránky (modified); označuje, že
           se stránka má při vyhození zapsat na disk
 - po nastavení bitu zůstane na 1 dokud ho SW nenastaví zpět na 0

* algoritmus NRU:
 - na začátku mají všechny stránky nastaveny R=0, M=0
 - bit R je OS nastavován periodicky na 0 (např. při přerušení
   časovače) - tím se rozliší, které stránky byly referencovány 
   v poslední době
 - OS rozlišuje 4 kategorie stránek:

   třída 0: R=0, M=0
   třída 1: R=0, M=1  ;; vznikne z třídy 3 po tiku, který nastaví R=0
   třída 2: R=1, M=0
   třída 3: R=1, M=1 
 
 - algoritmus NRU vyhodí stránku z nejnižší neprázdné třídy, výběr nezi
   stránkami ve stejné třídě je náhodný

* algoritmus předpokládá, že je lepší vyhodit modifikovanou stránku
  která nebyla 1 tik použit než nemodifikovanou stránku, která se právě
  používá
   
* výhody:
 - jednoduchost, srozumitelnost
 - efektivně implementovatelný
 - přiměřená výkonnost

* pokud HW nemá bity R a M, můžou se simulovat následujícím způsobem:

- při startu procesu se všechny jeho stránky označí jako nepřítomné
  v paměti
- při odkazy na stránku nastane výpadek stránky - OS interně nastaví
  R=1 a nastaví mapování v režimu READ ONLY
- při pokusu o zápis do stránky výjimka - OS nastaví M=1 a změní režim
  přístupu do stránky na READ/WRITE.

Algoritmus First-In, First-Out (FIFO)
.....................................

Představme si samoobsluhu s plnými regály, která potřebuje zavést nový
výrobek (na který byla reklama v televizi). Plné regály => je třeba
vybrat výrobek k odstranění. Nejjednodušší algoritmus: vybrat ten,
který je nejstarší (předpoklad: je nejstarší, asi ho už nikdo nechce).
Analogicky:

* seznam všech stránek v pořadí, ve kterém byly zavedeny
* vyhazujeme nejstarší stránku (nejdéle zavedenou = první na seznamu)

To, že bylo zboží zavedeno nejdelší dobu neznamená, že už ho nikdo
nechce (sůl). Analogicky:

* často používané stránky mohou být v paměti dlouho => je možné, že se
  vyhodí stránka, která se bude brzy potřebovat
=> FIFO se zřídka používá v čisté podobě

Modifikace algoritmu FIFO (tj. už to není FIFO): Second Chance, Clock

Algoritmus Second Chance
........................

Obchod: V algoritmu FIFO jsme vyhazovali zboží, které bylo zavedeno
před nejdelší dobou (bez ohledu na to, jestli ho někdo chce nebo ne). 
Začneme evidovat, jestli zboží někdo v poslední době koupil.

* jak modifikovat FIFO, abychom zabránili vyhození často používané
  stránky?
* algoritmus (Second Chance - vyhledání stránky pro vyhození):
- podívat se na bit R nejstarší stránky
- pokud R=0, stránka je nejstarší a zároveň nepoužívaná => vyhodíme
- pokud R=1, nastavíme R na 0 a na konec seznamu stránek 
  (jako by byla nově zavedena)

Příklad:

 v paměti stránky A, B, C, D, výpadek v čase 10:
 
   R t (čas zavedení)   R t    R t    R t
 A 1 0 ................>0 10 . 0 10 . 0 10
 B 1 3 ................ 1 3 ..>0 10 . 0 10
 C 0 7 ................ 0 7 .. 0 7 ..>0 7 - vyhodíme
 D 1 8 ................ 1 8 .. 1 8 .. 1 8

 Nejstarší je 0 (přišla v čase 0); pokud by měla R=0, vyhodili bychom
 jí, ale nemá => nastavíme R na 0 a přesuneme na konec seznamu (resp.
 nastavíme čas zavedení na "nyní"=10).

* vyhledává nejstarší stránku, která nebyla referencována "v poslední
  době"
* pokud byly všechny referencovány, degeneruje na čisté FIFO:
 - postupně všem stránkám nastavíme bit R na 0 a přesuneme na konec
   seznamu
 - dostaneme se opět na stránku A, tentokrát má R=0 => vyhodíme jí
 => algoritmus končí nejvýše po $počet_stránek + 1$ krocích

Algoritmus Clock
................

* optimalizace algoritmu Second Chance:
 - stránky udržovány v kruhovém seznamu 
 - ukazatel na nejstarší stránku ("ručička hodin")

    K  L  A
  J         B
  I    *--> C
  H         D
    G  F  E

* výpadek stránky -> vyhledáváme stránku k vyhození
 - stránka kam ukazuje "ručička": 
  . má-li R=0, stránku vyhodíme a ručičku posuneme o 1 pozici
  . má-li R=1, nastavíme R na 0, ručičku posuneme o 1 pozici; opakujeme
    dokud nenalezneme stránku s R=0
* od algoritmu Second Chance se liší pouze implementací
* varianty algoritmu Clock používají např. systémy UNIX

Algoritmus Least Recently Used (LRU, LUR)
.........................................

Obchod: Vyhazovat zboží, na kterém je v prodejně nejvíce prachu =>
nejdéle nebylo požadováno.

* pozorování (vyplývá z principu lokality): 
 - stránky, které se používaly v posledních několika instrukcích se
   budou pravděpodobně používat i v následujících instrukcích
 - stránky, které se dlouho nepoužívaly se pravděpodobně nebudou v
   nejbližší době používat
=> dobré přiblížení se optimálnímu algoritmu: algoritmus LRU - vyhodit
   nejdéle nepoužívanou stránku

* obtížná implementace
* čistě v software? (není možné)
 - bylo by třeba udržovat seznam stránek v pořadí referencí
 - při přístupu ke stránce přesunout na konec seznamu
 - při výpadku vyhazujeme ze začátku seznamu
=> tohle by bylo třeba při každém odkazu na stránku, algoritmus LRU
   není SW realizovatelný z výkonnostních důvodů, je nutná podpora HW

1. implementace pomocí čítače
* MMU obsahuje čítač (64 bitů), který je automaticky zvětšen po každém
  přístupu do paměti
* každá položka v tabulce stránek má pole pro uložení obsahu čítače
* při každém odkazu do paměti se obsah čítače zapíše tabulky stránek
  - do položky pro odkazovanou stránku
* při výpadku stránky se vyhledá a vyhodí stránka, jejíž položka
  obsahuje nejnižší číslo == nejdéle nepoužitá stránka

2. implementace pomocí matice (uvádím spíše pro zajímavost)
* MMU udržuje matici $n*n$ bitů, kde $n$ je počet rámců
* na počátku všechny prvky matice nastaveny na 0
* při odkazu na $k$-tou stránku:
  . nejprve nastavit všechny bity $k$-tého řádku matice na 1
  . pak nastavit všechny bity $k$-tého sloupce na 0
* v každém okamžiku představuje řádek s nejnižší binární hodnotou 
  nejdéle nepoužitou stránku

Příklad:

reference v pořadí: 3 2 1 0

     0.1.2.3       0.1.2.3       0.1.2.3       0.1.2.3
  0. 0 0 0 0    0. 0 0 0 0    0. 0 0 0 0    0. 0 1 1 1
  1. 0 0 0 0    1. 0 0 0 0    1. 1 0 1 1    1. 0 0 1 1
  2. 0 0 0 0    2. 1 1 0 1    2. 1 0 0 1    2. 0 0 0 1
  3. 1 1 1 0    3. 1 1 0 0    3. 1 0 0 0    3. 0 0 0 0

Výhody:

* z časově založených algoritmů nejlepší

Nevýhody:

* při každém odkazu na stránku nutnost aktualizace záznamu (položky 
  v tabulace stránek nebo řádek & sloupec v matici) => zpomalení
  výpočtu (místo jednoho odkazu do paměti se provádějí dva)
=> LRU se pro stránkovanou virtuální paměť prakticky nepoužívá 
  (používá se v jiných případech, např. bloková cache pro soubory)

Softwarová aproximace LRU 
.........................

* algoritmus Aging:
* každá položka v tabulce stránek má pole "stáří" age, N bitů (např. N=8)
* na počátku age=0
* při každém přerušení časovače pro každou stránku:
 
    age := age shr 1;           { posun o 1 bit vpravo }
    age := age or (R shl N-1);  { zleva se přidá hodnota bitu R }
    R := 0;                     { nastavení R na 0 }
                                { R---->7->6->5->4->3->2->1->0 }

* při výpadku stránky se vyhodí stránka, jejíž pole age je má nejnižší
  hodnotu

Dva rozdíly od LRU:

* 2 pole age mohou mít stejnou hodnotu a nevíme která stránka byla
  odkazovaná dříve (u LRU to víme vždy) 
 - rozlišení je "hrubé" (= po ticích časovače)
* pole age se může snížit na 0 - nevíme, jestli stránka byla naposledy
  odkazovaná před 9 nebo před 1000 tiky časovače 
 - uchovává pouze omezenou historii
 - v praxi není problém: pokud je tik časovače po 20 ms a N=8, nebyla
   odkazována 160 ms => nejspíš není tak důležitá, můžeme jí vyhodit
* pokud se musíme rozhodovat mezi dvěma stránkami se stejnou hodnotou
  age, vybíráme náhodně

Poznámka: (algoritmus Not Frequently Used (NFU)):

* s každou stránkou čítač cnt
* při každém přerušení: cnt := cnt + R; R := 0
  => cnt udržuje informaci, jak často se ke stránce přistupovalo
* problém s NFU - nikdy nezapomíná
* příklad: 
 - 2 fáze programu: 1. fáze používá množinu stránek S, 
                    2. fáze používá množinu stránek T,
 - ve druhé fázi jsou často používané stránky z první fáze preferovány
   před stránkami aktuálně používanými
* výše uvedený algoritmus Aging přidává stárnutí informace 
  o používaných stránkách - stránky používané v současnosti mají
  přednost