Jak na výpočet maximálního počtu výpadků stránek (= page faultů)

Pro řešení je třeba se opřít o jejich předpoklady:

A) stránkovací tabulka první úrovně je vždy v paměti (= the first level paging table is always in the memory)
- to znamená, že ji bereme jako už načtenou, do počtu page faultů se počítat nebude

B) OS používá velmi jednoduchý algoritmus, při každém výpadku stránky je schopen alokovat jen jeden rámec (= OS implements a very simple algorithm which allocates only one frame during each page failure)
- tzn používáme tzv. Demand Paging (= data když je čteme se nenačtou do paměti hned, ale po kouskách, jak k ním přistupujeme)
  - realně se nám to stane, když př. jsme alokovali velký kus paměti, a teď se po něm procházíme for loopem.

C) máme dostatečné množství volných rámců, nebude docházet k výměně stránek (= there are enough free frames, there will be no page replacement)
- to znamená, že systém má dost paměti, nebude potřebovat swapovat stránky na disk
  - v této úloze co se jednou do paměti načte, to tam fakt bude
    - to v kombinaci s B) znamená právě 1 page fault na každou L2, L3 tabulku, a pak na každý actual překlad adresy v L3 na adresu fyzického rámce (= frame)

Z výše uvedeného vychází, že buď si:

můžeme odsimulovat, jak se postupně ty L2, L3, překlady v L3 objevují
nebo si jen spočítat součet počtu:
- fyzických framů (= počet stránek, protože velikost stránky = velikost rámce)
- L3
- L2

Trojúrovňové tabulky

Při trojúrovňových tabulkách:

nejdřív si spočítáš nejhorší maximální počet stránek na ty data
pro tento počet stránek si spočítáš nejhorší maximální počet $L3$ tabulek
pro tento počet $L3$ tabulek spočítáš nejhorší maximální počet $L2$ tabulek

a sečteš, $L1$ tě nezajímá

Dvojúrovňové tabulky

nejdřív si spočítáš nejhorší maximální počet stránek na ty data
pro tento počet stránek si spočítáš nejhorší maximální počet $L2$ tabulek

a sečteš, $L1$ tě nezajímá

Co je nejhorší počet stránek?

Př. Mějme data délky 8, stránku velikosti 4. Optimálně 8 / 4 = 2 stránky. Nejhůř ale 3 stránky, když náš blok dat nezačíná na začátku stránky, př:

  4    4    4  
|    |    |    |
   \        /
    -------
       8

Tj 2 v 1. stránce, 4 v 2. stránce, 2 v 3. stránce.

Pro větší velikosti dat a stránek se hodí výpočet takto:

nejvyšší počet stránek, na které se ro rozleze = $\lceil \frac{\text{velikost dat}}{\text{velikost stránky}} \rceil + 1$

Má však jeden mezní případ, kdy jej použít nejde:

  4    4    4  
|    |    |    |
     |     |
     ------
       5

=> jednu stránku jsme zaplnili, a zbývá malý kousek velikosti 1 => ten už rozdělit na 2 části neumíme

=> takže tady vyjdou 2 stránky, kde by podle předchozího vzorce vyšly 3.

Analogicky pak budeme počítat i počty tabulek.

Dodatek, proč to vůbec můžeme takto dělat:

V zadání je, že blok dat je souvislý. To znamená, že ve stránkovací tabulce jdou záznamy na fyzické adresy rámců souvisle za sebou. Takže když dojde tabulka a data pokračují, tak pokračují na začátku další tabulky, opět souvisle.

Př. 1

příklad 1

nejdřív si spočítáš nejhorší maximální počet stránek na ty data

$7 \text{ MiB} = 7 \cdot 1024 \cdot 1024 \text{ B}$

$4 \text{ KiB} = 4 \cdot 1024 \text{ B}$

$\left\lceil \frac{7 \cdot 1024 \cdot 1024}{4 \cdot 1024} \right\rceil + 1 = 1793$

pro tento počet stránek si spočítáš nejhorší maximální počet $L2$ tabulek

$\left\lceil \frac{1793}{1024} \right\rceil + 1 = 2 +1 = 3$

Celkově tedy $1793 + 3 = 1796$ .

V zadání máme kopírování, tedy čtení a zápis. Takže výsledek vynásobíme $2$ .

$1796 \cdot 2 = 3592$ , nice, vyšlo

Př. 2

příklad 2

31 KiB, 2 KiB stránky, 3 úrovňové tabulky

nejdřív si spočítáš nejhorší maximální počet stránek na ty data

$\left\lceil \frac{31}{2} \right\rceil + 1 = 16 + 1 = 17$

pro tento počet stránek si spočítáš nejhorší maximální počet $L3$ tabulek

$\left\lceil \frac{17}{256} \right\rceil + 1 = 1 + 1 = 2$

pro tento počet $L3$ tabulek spočítáš nejhorší maximální počet $L2$ tabulek

$\left\lceil \frac{2}{256} \right\rceil + 1 = 1 + 1 = 2$

Celkem $17 + 2 + 2 = 21$ na čtení, ještě jednou tolik na zapisování, tj. $42$ , nice vyšlo