# 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](./priklad-strankovani-2-level.png)

> - 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](./priklad-strankovani-3-level.png)

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