# Ćwiczenia 11, grupa cz. 16-18, 9 maja 2024

###### tags: `SYK24` `ć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!**

**UWAGA: Zgodnie z zapowiedzią dzisiaj deklarujecie zadania 1 -- 5**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak | X | X | X | | | | | | |
Bartosz Borecki | X | X | X | | | | | | |
Karol Burczyk | X | X | | | | | | | |
Yelyzaveta Ilman | X | X | X | | | | | | |
Antoni Kamiński | X | X | X | | | | | | |
Jan Kamyk | X | X | X | | | | | | |
Bartosz Kruszewski | X | X |==X==| | | | | | |
Hanna Laszkiewicz | ==X== | X | X | | | | | | |
Kaja Matuszewska | X | X | X | | | | | | |
Dominik Muc | | | | | | | | | |
Krzysztof Ostrowski | | | | | | | | | |
Franciszek Przeliorz | X |==X==| X | | | | | | |
Yaryna Rachkevych | X | X | | | | | | | |
Mikołaj Kalitka | X | X | X | | | | | | |
Piotr Thamm | | | | | | | | | |
Taras Tsehenko | | | | | | | | | |
Wiktor Małek | | | | | | | | | |
Piotr Salamon | X | X | X | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Hanna Laszkiewicz

:::

## Zadanie 2
:::success
Autor: Franciszek Przeliorz

### Rozważmy przypadek:
* **MM rozmiar**: $32 = 2^5B$
* **Cashe rozmiar**: $16 = 2^4B$
* **Blok rozmiar**: $2 = 2^1B$

---

### Pamięć z mapowaniem bezpośrednim

- **offset**: $1$ bit
- **index**: $2$ bity
- **tag**: $2$ bity

$4$ zbiory po $1$ blok

| 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 z LRU

- **offset**: $1$ bit
- **index**: $1$ bity
- **tag**: $3$ bity

$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 |
:::

## Zadanie 3
:::success
Autor: Bartosz Kruszewski
:::


#### Pojęcia

- **translacja adresów**: proces tłumaczenia adresów wirtualnych na fizyczne
- **TLB (Translation lookaside buffer)**: pamieć pomocnicza do obługi pamięci wirtualnej (działa jak cache dla MMU)
- **tablica stron**: pamięć przechowująca informacje o adresach fizycznych poprzednio wczytanych do pamięci operacyjnej lub jeszcze znajdujących się na dysku

#### Znaczenie adresu wirtualnego

- **TLBI (TLB index)**: indeks zbioru w TLB
- **TLBT (TLB tag)**: tag bloku w **TLB**
- **VPO (Virtual Page Offset)**: przesunięcie strony w pamięci wirtualnej
- **VPN (Virtual Page Number)**: numer strony w pamięci wirtualnej (pokrywa się z **TLBI** oraz **TLBT**)

#### Znaczenie adresu fizycznego

- **CT (Cache Tag)**
- **CI (Cache Index)**
- **CO (Cache Offset)**
- **PPN (Physical Page Number)**:
numer strony w pamięci fizycznej (pokrywa się z **CI** oraz **CO**)
- **PPO (Physical Page Offset)**: przesunięcie strony w pamięci fizycznej (jest takie same jak **VPO**)

#### Translacja adresu

1. sprawdzamy, czy **TLBI** oraz **TLBT** są w **TLB** oraz czy są *Valid*
2. jezeli tak to odczytujemy **PPN** z **TLB**
3. jezeli nie to szukamy **PPN** w tablicy stron za pomoca **VPN**
4. przepisujemy **VPO** do **PPO**
5. Odczytujemy **CT**, **CI**, **CO**

#### Adres 1

$0x027c = 00001001111100$
$TLBT = 000010 = 0x02$
$TLBI = 01 = 0x01$
$VPN = 00001001 = 0x09$
$VPO = 111100 = 0x3c$

Wartość w **TLB** nie jest *Valid*, wiec szukamy za pomoca **VPN**.

$PPN = 0x17 = 010111$

Adres po translacji: **010111 111100**
$CT = 010111 = 0x17$
$CI = 1111 = 0x0f$
$CO = 00 = 0x00$

#### Adres 2

$0x03a9 = 00001110101001$
$TLBT = 000011 = 0x03$
$TLBI = 10 = 0x03$
$VPN = 00001110 = 0x0e$
$VPO = 101001 = 0x29$

Wartość w **TLB** jest *Valid*, wiec odczytujemy **PPN**.

$PPN = 0x0D = 001101$

Adres po translacji: **001101 101001**
$CT = 001101 = 0x0D$
$CI = 1010 = 0x0a$
$CO = 01 = 0x01$

#### Adres 3

$0x0040 = 00000001000000$
$TLBT = 000000 = 0x00$
$TLBI = 01 = 0x01$
$VPN = 00000001 = 0x01$
$VPO = 000000 = 0x00$

Nie ma tego tagu w **TLB**, więc szukamy za pomocą **VPN**.

Pod ustalonym **VPN** nie ma wartości w **tablicy stron**, więc mamy chybienie.

## Zadanie 4
:::success
Autor: Hanna Laszkiewicz

Przypomnienie z ostatnich ćwiczeń:


TLB jest w pełni asocjacyjne - nie mamy zbiorów, czyli nie mamy też TLBI. Całość bitów przeznaczonych na VPN odwzorowuje TLBT.

Strony mają po 4 KiB, czyli offset ma wielkość $log_2(4096) = 12$. Mamy zatem 12 bitów na VPO, a pozostałe bity przeznaczamy na VPN.

Przyjmijmy, że długość adresu to długość jego zapisu binarnego, wtedy wystarczy 16 bitów do zapisu adresu (zapis binarny największego adresu mieści się na 16 bitach). Na TLB przeznaczymy zatem 16 - 12 = 4 bity.

Tam gdzie adresu nie ma w TLB, a w tablicy stron nie jest valid lub nie ma go tam, otrzymujemy błąd.

Adres 1.:
4669 = 0001 001000111101
TLBT = VPN = 1
Nie ma go w TLB, ani nie jest Valid w tablicy stron.

Robimy wpis do tablicy stron (VPN: 1, valid: 1, PPN: 13), oraz wpis do TLB (Valid: 1, Tag: 1, LRU: 0, PPN: 13).

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

| 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 |

Adres 2.:
2227 = 0000 100010110011
TLBT = VPN = 0
Nie ma go w tablicy TLB, ale jest w tablicy stron z PPN = 5. Robimy wpis do TLB (valid: 1, tag 0, PPN: 5).

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

| 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 |

Adres 3.:
13916 = 0011 011001011100
TLBT = VPN = 3
Nie ma go w TLB ale jest w tablicy stron z PPN = 6. Robimy wpis do TLB.

| Valid? | Tag | LRU | PPN |
|:------:|:---:|:---:|:---:|
| 1 | 3 | 0 | 6 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 2 | 13 |
| 1 | 11 | 3 | 12 |

| 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 |

Adres 4 .:
34587 = 1000 011100011011
TLBT = VPN = 8
Nie ma go w TLB, nie jest Valid w tablicy stron. Mamy błąd. Robimy wpis do TLB i tablicy stron.

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

| 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 |

Adres 5.:
48870 = 1011 111011100110
TLBT = VPN = 11
Nie ma go w TLB, ale jest w tablicy stron z PPN = 12. Robimy wpis do TLB.

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

| 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 |

Adres 6.:
12608 = 0011 000101000000
TLBT = VPN = 3
Jest w TLB (zmienia się tylko kolejność w TLB).

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

| 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 |

Adres 7.:
49225 = 1100 000001001001
TLBT = VPN = 12
Nie ma go w TLB ani w tablicy stron. Otrzymujemy błąd.

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

| 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: Piotr Salamon

a) Adres wirtualny ma 32-bity, zatem mamy 2^32 możliwych adresów.
Rozmiar strony ma 4KiB, 1 KiB = 1024 bajty, czyli 2^12 bajtów.

Skoro chcemy poznać liczbę stron to liczbę możliwości / rozmiar strony:
2^32 / 2^12 = 2^20.

Teraz jeśli rozmiar wpisu tablicy stron zajmuje 4 bajty, to rozmiar całej tablicy:
2^20 * 2^2B = 2^22B, czyli 4MiB.

b) Katalog tablicy stron (tablica stron pierwszego poziomu) ma 1024 wpisy,
Czyli 2^10 * 2^2 B (rozmiar wpisu) = 2^12 B.

Minimalny rozmiar tablicy stron:
Proces używa 1GiB swojej przestrzeni adresowej, czyli 2^30 B, zatem będziemy potrzebować 2^30 B / 2^12 B = 2^18 stron.
W takim razie najmniejsza liczba wpisów, jaka może być nam potrzebna w tablicy stron drugiego poziomu to 2^18 stron, a jeden wpis to 2^2B, czyli w sumie
2^18 * 2^2B = 2^20 B.
Podsumowując, minimalny rozmiar tablicy dwupoziomowej jest równy:
2^12 B + 2^20 B = 1052672 B, czyli blisko 1MiB.
(pierwszy poziom) + (drugi poziom)
(1 mebibajt = 1 048 576 bajtów)

Maksymalny rozmiar tablicy stron:
Kiedy proces będzie używał całej swojej przestrzeni adresowej, czyli 2^32B.
(2^10 wpisów w pierwszej, dla każdego 2^10 w poziomie drugim, i każdy wskazuje na 2^12B ramkę, czyli 2^10 * 2^10 * 2^2^12B = 2^32B)
Wtedy mamy 2^32 B/2^12 B = 2^20 stron.
W takim razie liczba wpisów, jaka będzie nam potrzebna w tablicy stron drugiego poziomu to 2^20 stron, a jeden wpis to 2^2B, czyli w sumie
2^20*2^2B = 2^22B.
Podsumowując, maksymalny rozmiar tablicy dwupoziomowej jest równy:
2^12 B + 2^22 B = 4198400 B, czyli blisko 4MiB.
(pierwszy poziom) + (drugi poziom)

:::

## Zadanie 6
:::success
Autor: Bartosz Kruszewski
:::

#### Zbiór roboczy

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

#### Obliczenia

TLB zawiera $64$ wpisy, ma $4$ wpisy na zbiór (bo jest czterodrożne), czyli ma $64 / 4 = 16$ zbiorów.

Możemy zakładać różne warianty trafień w TLB:

- **optymistyczny**: trafiamy ciągle w ten sam zbiór (wykorzytujemy tylko jeden zbiór, czyli 4 wpisy)
- **pesymistyczny**: trafiamy za każdym razem w różne wpisy (wykorzystujemy całe TLB, czyli 64 wpisy)

Warianty rozpatruje pod względem wykorzystania pamięci. Jeśli chodzi o efektywność działania procesu to nazwy **optymistyczny** i **pesymistyczny** będą na odwrót.

#### Oszacowania dla stron o wielkości 4KiB

Optymistycznie: $4 * 4KiB = 16KiB$
Pesymistycznie: $64 * 4KiB = 256KiB$

#### Oszacowania dla stron o wielkości 4MiB

Optymistycznie: $4 * 4MiB = 16MiB$
Pesymistycznie: $64 * 4MiB = 256MiB$

#### Przestrzeń adresowa

Przestrzeń adresowa ma wielkość $2^{48}B = 2^{18}GiB$, także na pewno pokryje wszystkie adresy.

## Zadanie 7
::: success
Autor: Antoni Kamiński
:::


VPN k - zawiera offset w tablicy k-tego poziomu

bity pomocnicze:

| Indeks bitu | Nazwa | Znaczenie 1-3 | Znaczenie 4 |
| ----------- | ---------------- | --------------------------------------------------------------------------------------------------------- | --------------------------------------------------------- |
| 0 | Present | 1 jeżeli istnieje tablica dziecko | - |
| 1 | Read/Write | 1 jeżeli dany adres mozna nadpisywać | - |
| 2 | User/Supervisor | Tryb dostepu do pamieci: użytkownika(1)/nadzorcy(0) | - |
| 3 | PageWriteThrough | WriteThrough(1)/WriteBack(0) | - |
| 4 | PageCacheDisable | (1)Strona może być cachowana/(0) nie | - |
| 5 | Reference | Ustawiany na 1 przez MMU w momencie zapisu/odczytu strony | - |
| 6 | Dirty | brak | (1)Ustawiany na 1 przez MMU w momencie modyfikacji strony |
| 7 | PageSize | **tylko dla 1-poziomu**(1)Nie wskazuje na tablice kolejnego poziomu, tylko na *large table* rozmiaru 4MiB | brak |
| 8 | Global | (1)Wszystkie procesy mogą używać tej strony/(0)Strona jest prywatna dla swojego procesu | - |
| 63 | XD | (1)Można z tej strony pobierać instrukcje do wykonania przez procesor | - |
| 12-52 | - | Wskazuje na początek tablicy następnego poziomu | Wskazuje na początek szukanej strony |

## Zadanie 8
:::success
Autor: Yelyzaveta Ilman
:::
### **Schemat VIPT: Równoległy Dostęp do TLB i Pamięci Podręcznej**

W schemacie **VIPT** (Virtually-Indexed, Physically-Tagged), aby **zrównoleglić** dostęp do **TLB** (Translation Lookaside Buffer) i **pamięci podręcznej**, stosujemy taki mechanizm:

### Indeksowanie Wirtualne
- Proces żąda dostępu do strony pamięci, korzystając z *adresu wirtualnego*.
- Z adresu wirtualnego mamy *indeks* pamięci podręcznej.
- Indeks używany jest do odnalezienia *setu w pamięci* podręcznej.

==**W tym samym czasie:**==

### Równoległa Translacja Adresów
- rozpoczynamy translację adresu wirtualnego na adres fizyczny (przy użyciu TLB)

### Znajdowanie Zestawu
- po zidentyfikowaniu setu w pamięci podręcznej na podstawie indeksu z adresu wirtualnego, czekamy na *zakończenie translacji adresu*.

### Tagowanie Fizyczne
- kiedy translacja adresu zakończy się, używamy uzyskanego *adresu fizycznego* do odczytania odpowiedniego *tagu*.
- wyszukujemy linię w znalezionym zestawie, która ma potrzebny tag

### Fakty
- *te same bity* adresu wirtualnego i fizycznego są używane *do określenia indeksu pamięci podręcznej*. Dzięki temu możemy zacząć proces przeszukiwania pamięci podręcznej *równocześnie* z translacją adresu.
- indeksowanie wirtualne pozwala na szybszy dostęp do pamięci podręcznej, bo nie musimy czekać na zakończenie translacji adresu, aby określić, który set w pamięci podręcznej nam pasuje.
- adres fizyczny jest używany do finalnego porównania tagów *dopiero po translacji*, co zapewnia *poprawność danych*.

## Zadanie 9
:::success
Autor: Bartosz Kruszewski
:::


#### Założenia

- indeksowanie, za pomocą stron pamięci fizycznej zamiast wirtualnej
- procesy współdzielą tablicę stron (wpisy mają identyfikatory procesu)

#### Translacja adresów

1. Hashowanie adresu przez funkcję hashującą (może być skomplikowana).
2. Wyszukiwanie hasha w tablicy hashy (zawiera wszystkie możliwe hashe odpowiadające pamięci, do jednego hasha może być przydzielone łacuchowo max 8 wpisów)
3. Wyszkujemy numer strony w pamięci spośród trafionych wpisów

#### Zalety

- skalowanie liniowe wraz z pamięcią fizyczną.
- mniej odwołań do pamięci

#### Wady

- duże rozmiary wpisów
- gorsze współdzielenie pamięci
- uzależnienie od funkcji hashującej