# Ćwiczenia 10, grupa śr. 10-12, 10 maja 2023

###### tags: `SYK23` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | | | | | | | | | |
Mikołaj Dworszczak | | | | | | | | | |
Kacper Jóźwiak | X | X | X | X | X | X | | X | |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Konrad Kowalczyk | X | X | X | X | X | X | X | X | |
Oskar Kropielnicki | X | X | X |==X==| | X | | X | |
Anna Krysta | X | X | X | X | X | X | X | X | X |
Jakub Krzyżowski | X | X | X | X |==X==| X | | X | |
Oskar Kubkowski | X | X | ==X== | X | X | X | | X | |
Mateusz Mazur | X | X | X | X | X | X | | | |
Barbara Moczulska | X | X | X | X | X | | | | |
Kacper Sojda | X | X | X | X | X | X | | | |
Marta Strzelec | X | X | X | X | | X | | X | |
Mikołaj Swoboda | X | X | X | X | X | | | X | |
Filip Szczepański | X | X | X | X | X | X | | X | |
Julian Włodarek | X | X | X | X | X | X | | X | |
Beata Łakoma | x | x | x | x | x | x | | x | |
Michał Łukasik | X | X | X | | X | X | | X | |
:::

Tu można zadeklarować zadanie 8 z listy 9:
-Anna Krysta
-
-

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Michał Łukasik
:::


Najstarsze bity zmieniają się znacznie rzadziej od młodszych bitów adresu, np. iterując po tablicy.
Korzystając ze środkowych bitów adresu podobne adresy mają takie same lub podobne tagi, ale różne zbiory i offsety.

Korzystając z najstarszych bitów podobne adresy mają takie same lub podobne zbiory oraz różne tagi i offsety.
Ponieważ podczas iteracji po tablicy często powtarzały by się zbiory, lecz z różnymi tagami, to następowało by więcej kolizji i zastąpień.


## Zadanie 2
:::success
Autor: Marta Strzelec
:::


Rozważmy 5-bitowe adresy o następującym formacie:

**Pamięć z mapowaniem bezpośrednim** : tag - 2 bity, index - 2 bity, offset - 1 bit
W takim formacie mamy cztery zbiory po jednym bloku.

| tag | index | offset | hit |
| ---- | ----- | ------ | --- |
| 00 | 00 | 0 | compulsory miss |
| 00 | 10 | 0 | compulsory miss |
| 01 | 10 | 0 | conflict miss |
| 00 | 00 | 0 | hit |

**Pamięć dwudrożna używająca LRU jako polityki wymiany:** tag - 3 bity; index - 1 bit; offset - 1 bit
W takim formacie mamy 2 zbiory po 2 bloki.

| tag | index | offset | hit |
| --- | ----- | ------ | ---- |
| 000 | 0 | 0 | compulsory miss |
| 001 | 0 | 0 | compulsory miss |
| 011 | 0 | 0 | conflict miss |
| 000 | 0 | 0 | conflict miss --> pierwszy wpis zostal usuniety |

## Zadanie 3
:::success
Autor: Oskar Kubkowski
:::
### a)


### b)


### c)


## Zadanie 4
:::success
Autor: Oskar Kropielnicki
:::


$4\text{KiB} = 2^{12}\text{B} \implies$ 12 bitów na VPO/PPO.
Adresy są 16-bitowe, więc 4 ($= 16 - 12$) bity przeznaczane są na VPN.
TLB jest w pełni asocjacyjna, więc jest tylko jeden zbiór, więc indeks zbioru nie musi być przechowywany w VPN, więc wszystkie 4 bity przeznaczane są na znacznik.

:::spoiler ciąg dostępów do pamięci
T
:::

:::spoiler początkowy stan TLB
| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
| 1 | 11 | 0 | 12 |
| 1 | 7 | 1 | 4 |
| 1 | 3 | 2 | 6 |
| 0 | 4 | 3 | 9 |
:::

:::spoiler początkowy stan tablicy stron
| VPN | Valid? | PPN |
|-----|--------|------|
| 0 | 1 | 5 |
| 1 | 0 | dysk |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 0 | dysk |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::
<br>

<style>
.c {
font-family: monospace;
font-size: 1.2em;
}
</style>

:::spoiler 4669 - page fault
<span class="c">4669~(10)~ = ++0001++ 0010 0011 1101~(2)~</span>

Znacznik = 1.
Szukamy go w TLB... brak. Szukamy go w tablicy stron... `Valid?` = 0, brak, błąd strony.

page fault - błąd strony

Ponieważ nie znaleźliśmy szukanej strony w TLB i tablicy stron, dobrze by było pobrać ją z dysku oraz umieścić w TLB i tablicy.

#### TLB

Wyrzucamy z TLB:
* dowolną krotkę, w której `Valid?` = 0, lub
* krotkę, która była najdawniej używana (LRU = 0).
W jej miejsce wstawiamy nową - ze znacznikiem, którego nie znaleźliśmy, i z PPN takim, żeby, zgodnie z treścią zadania, był większy od największego numeru ramki (PPN) istniejącego w tablicy stron. Nowa krotka jest ==zaznaczona==.

Ramka
~ [the smallest fixed-length contiguous block of physical memory into which memory pages are mapped by the operating system](https://en.wikipedia.org/wiki/Page_(computer_memory)) (najmniejszy ciągły blok fizycznej pamięci, na którą strony są mapowane).

Do tego zmniejszamy LRU pozostałych krotek o 1. Jeśli LRU = 0, to zostawiamy 0.

| Valid? | Tag | LRU | PPN |
|--------|-------|-------|--------|
| 1 | 11 | 0 | 12 |
| 1 | 7 | 1 | 4 |
| 1 | 3 | 2 | 6 |
| ==1== | ==1== | ==3== | ==13== |

#### Tablica stron

Tablicę stron aktualizujemy podobnie; krotkę z odpowiednim VPN już mamy, więc zmieniamy tylko PPN i `Valid?`.

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | ==1== | ==13== |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 0 | dysk |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 2227 - page hit
<span class="c">2227~(10)~ = ++0000++ 1000 1011 0011~(2)~</span>

Znacznik = 0.
Szukamy go w TLB... brak. Szukamy go w tablicy stron... `Valid?` = 1, jest; PPN = 5; $█▬█\ \ █\ \ ▀█▀$.

#### TLB

W TLB zastępujemy najdawniej używaną krotkę i aktualizujemy LRU dla pozostałych.

| Valid? | Tag | LRU | PPN |
|--------|-------|-------|--------|
| 1 | ==0== | ==3== | ==5== |
| 1 | 7 | 0 | 4 |
| 1 | 3 | 1 | 6 |
| 1 | 1 | 2 | 13 |

#### Tablica stron

Tablica stron w tym przypadku pozostaje bez zmian.

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 0 | dysk |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 13916 - TLB hit
<span class="c">13916~(10)~ = ++0011++ 0110 0101 1100~(2)~</span>

Znacznik = 3.
Szukamy go w TLB... jest. Nie musimy szukać go w tablicy stron; PPN = 6; $█▬█\ \ █\ \ ▀█▀$.

#### TLB

W tym przypadku tylko aktualizujemy LRU wszystkich krotek.

| Valid? | Tag | LRU | PPN |
|--------|-------|-------|--------|
| 1 | 0 | 2 | 5 |
| 1 | 7 | 0 | 4 |
| 1 | 3 | 3 | 6 |
| 1 | 1 | 1 | 13 |

#### Tablica stron

Tablica stron również w tym przypadku pozostaje bez zmian.

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 0 | dysk |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 34587 - page fault
<span class="c">34587~(10)~ = ++1000++ 0111 0001 1011~(2)~</span>

Znacznik = 8.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... brak.

#### TLB

| Valid? | Tag | LRU | PPN |
|--------|-------|-------|--------|
| 1 | 0 | 1 | 5 |
| 1 | ==8== | ==3== | ==14== |
| 1 | 3 | 2 | 6 |
| 1 | 1 | 0 | 13 |

#### Tablica stron

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 1 | 14 |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 48870 - page hit
<span class="c">48870~(10)~ = ++1011++ 1110 1110 0110~(2)~</span>

Znacznik = 11.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... jest.

#### TLB

| Valid? | Tag | LRU | PPN |
|--------|--------|-------|--------|
| 1 | 0 | 0 | 5 |
| 1 | 8 | 2 | 14 |
| 1 | 3 | 1 | 6 |
| 1 | ==11== | ==3== | ==12== |

#### Tablica stron

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 1 | 14 |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 12608 - TLB hit
<span class="c">12608~(10)~ = ++0011++ 0001 0100 0000~(2)~</span>

Znacznik = 3.
Szukamy go w TLB... jest.

#### TLB

| Valid? | Tag | LRU | PPN |
|--------|--------|-------|--------|
| 1 | 0 | 0 | 5 |
| 1 | 8 | 1 | 14 |
| 1 | 3 | 3 | 6 |
| 1 | 11 | 2 | 12 |

#### Tablica stron

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 1 | 14 |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

:::spoiler 49225 - page fault²
<span class="c">49225~(10)~ = ++1100++ 0000 0100 1001~(2)~</span>

Znacznik = 12.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... brak^2^.
Nawet na dysku go nie ma. :flushed:

#### Ostateczny stan TLB

| Valid? | Tag | LRU | PPN |
|--------|--------|-------|--------|
| 1 | 0 | 0 | 5 |
| 1 | 8 | 1 | 14 |
| 1 | 3 | 3 | 6 |
| 1 | 11 | 2 | 12 |

#### Ostateczny stan tablicy stron

| VPN | Valid? | PPN |
|-----|--------|--------|
| 0 | 1 | 5 |
| 1 | 1 | 13 |
| 2 | 0 | dysk |
| 3 | 1 | 6 |
| 4 | 1 | 9 |
| 5 | 1 | 11 |
| 6 | 0 | dysk |
| 7 | 1 | 4 |
| 8 | 1 | 14 |
| 9 | 0 | dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |
:::

## Zadanie 5
:::success
Autor: Jakub Krzyżowski
:::
Mamy:
4 KiB ($2^{12}$ B) page size - rozmiar strony,
32-bit address space - $2^{32}$ adresów wirtualnych,
4 B PTE (Page Table Entry) - wpis tablicy stron

(a)
$2^{32} / 2^{12} = 2^{20}$ stron
$2^{20} * 2^2 = 2^{22}$ B = 4 MiB

(b)
Katalog tablicy stron: $2^{10} * 2^2B = 2^{12}B$

$1 GiB = 2^{30}B$
A więc najmniej będziemy potrzebować $2^{30} / 2^{12} = 2^{18}$ stron.
A zatem najmniejsza liczba wpisów jaką będziemy potrzebować w tablicy stron 2-go poziomu to: $2^{18}$, więc minimalny rozmiar tablicy 2-go poziomu to $2^{18} * 2^2B$.
Więc minimalny rozmiar dwupoziomowej tablicy stron dla tego procesu wyniesie:
$2^{10} * 2^2B + 2^{18} * 2^2B = (2^{10} + 2^{18}) * 2^2 = (1 + 2^8) * 2^{10} * 2^2B \approx 2^{20}B = 1 MiB$

Tablica stron przybierze maksymalny rozmiar kiedy proces będzie używał całej przestrzeni adresowej: $2^{32}B$
Wtedy będziemy mieć $2^{32}/2^{12} = 2^{10}$ stron, a więc wpisów w tablicy stron 2-go poziomu będzie też $2^{10}$.
Więc maksymalny rozmiar tablicy stron dla tego procesu wyniesie:
$2^{10} * 2^2B + 2^{20} * 2^2B = (2^{10} + 2^{20}) * 2^2 = (1 + 2^{10}) * 2^{10} * 2^2B \approx 2^{22}B = 4 MiB$

## Zadanie 6
:::success
Autor: Filip Szczepański
:::

Zbiór roboczy to zbiór aktualnie aktywnych stron w pamięci wirtualnej wykorzystywanych przez proces.

TLB zawiera 64 wpisy, po 4 wpisy na zbiór, czyli 64/4 = 16 zbiorów.

Przestrzeń adresowa 2^48B

1) wielkość strony 4KiB

Optymistycznie: Czyli wykorzystujemy całe TLB (64 wpisy)
64 * 4KiB = 256KiB

Pesymistycznie: (4 wpisy)
4 * 4KiB = 16KiB

2) wielkość strony 4MiB

Optymistycznie:(64 wpisy)
256MiB

Pesymistycznie:(4 wpisy)
16MiB

## Zadanie 7
:::success
Autor: Konrad Kowalczyk
:::


Procesory w architekturze x86-64 używają czteropoziomowej tablicy stron, gdzie tablice wyższych poziomów zawierają wpisy przekierowujące do tablic niższych poziomów. Używane są 48-bitowe adresy wirtualne z 36-bitowym VPN i 12-bitowym VPO.
VPO jest bez żadnych przekształceń przesyłany jako PPO, tymczasem VPN jest najpierw dzielony na 32-bitowe TLBT i 4-bitowe TLBI i przesyłane jako adres do czterodrożnego TLB z 16 zbiorami.
Jeśli nie uda się wydobyć żądanego adresu z TLB, VPN jest dzielony na 4 części po 9 bitów. Każda z tych części oznacza offset na kolejnych poziomach tablicy stron. Tymczasem adresy kolejnych tablic są przechowywane we wpisach tablic wyższych poziomów, tzn. wpis w tablicy poziomu 1 zawiera adres do odpowiedniej tablicy poziomu 2 itd. Szukany wpis w tablicy poziomu pierwszego jest ustalany przez specjalny rejestr CR3, którego wartość jest częścią instrukcji aktualnie wykonywanego procesu.


Wpisy w tablicach poziomu 1, 2 oraz 3 są w tym samym formacie:

| Pole | Opis |
| :---: | :---: |
| P | określa czy pole adresowe zawiera adres do następnego poziomu tablicy |
| R/W | określa czy strony dostępne z tego adresu (tzn. strony w całym regionie obejmowanym przez ten poziom tablicy) są dostępne tylko do odczytu czy do odczytu i zapisu |
| U/S | określa czy dostęp do stron w całym regionie obejmowanym przez ten poziom tablicy mają programy użytkownika czy też dostęp ma jedynie jądro systemu |
| WT | określa czy strony w całym regionie obejmowanym przez ten poziom tablicy używają polityki zapisu write-back czy write-through |
| CD | określa czy strony w całym regionie obejmowanym przez ten poziom tablicy mają być sprawdzane czy też należy od razu odwołać się do pamięci głównej |
| A | specjalny bit referencji, ustawiany za każdym razem gdy proces uzyskuje dostęp do strony, używany do określania, które tablice stron powinne zostać wyrzucone w przypadku chybienia |
| PS | określa czy rozmiar pojedynczej strony wynosi 4 KB czy 4 MB (określony tylko dla tablicy poziomu 1) |
| G | określa czy strona powinna zostać wyrzucona z TLB w przypadku zmiany obecnego zadania w procesie |
| Page table physical base addr | Adres do odpowiedniej tablicy niższego poziomu |
| XD | określa czy ze stron w całym regionie obejmowanym przez ten poziom tablicy można odczytać instrukcje dla procesów |

Wpisy w tablicach poziomu 4 (pola o nazwach takich samych jak w tablicach wyższych poziomów pełnią takie same funkcje):

| Pole | Opis |
| :---: | :---: |
| D | tzw. dirty bit, określa czy strona została zmodyfikowana i czy musi zostać zmodyfikowana w pamięci głównej przed jej usunięciem w pamięci podręcznej |

Przewagą tablicy czteropoziomowej nad jednopoziomową jest duża oszczędność pamięci. Jeśli adres w tablicy wyższego poziomu nie jest określony, to nie ma konieczności rezerwowania pamięci dla tablic niższych poziomów.

## Zadanie 8
:::success
Autor: Beata Łakoma
:::


wcześniej
va->pa - weź set - znajdz tag
optymalizacja:
Set można pobrać równolegle z translacją adresu, kiedy vpo jest takie samo jak ppo. Taka optymalizacja nie jest możliwa gdy ppo>vpo.

## Zadanie 9
:::success
Autor: Anna Krysta
:::