# Ćwiczenia 11, grupa cz. 10-12, 16 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | X | | | | | | | |
Michał Chawar | X | X | | | | | | | |
Julia Cygan | X | X | | | | | | | |
Maciej Dengusiak | X | X | | | | | | | |
Patryk Flama | ==X== | X | X | | | | | | |
Szymon Fluder | X | X | X | X | X | | | | |
Aleksandra Jędrzejak | X | X | X | | | | | | |
Mikołaj Karapka | X | ==X== | X | X | X | | | | |
Viktoriia Kashpruk | X | X | X | ==X== | X | | | | |
Wiktor Małek | X | X | X | X | X | | | | |
Błażej Molik | X | X | X | | | | | | |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Lucjan Pucelak | X | X | | | | | | | |
Aleksandra Sęk | | | | | | | | | |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | X | X | X | | X | | | | |
Katarzyna Trzos | | | | | | | | | |
Piotr Warząchowski | X | X | | | | | | | |
Olga Zaborska | X | X | X | | | | | | |
:::

Poniżej można zadeklarować zadanie **9** z listy **10**

:::success
| | 10.9 |
| ----------------------:| -----|
Borys Adamiak | |
Michał Chawar | |
Julia Cygan | |
Maciej Dengusiak | |
Patryk Flama | |
Szymon Fluder | |
Aleksandra Jędrzejak | |
Mikołaj Karapka | |
Viktoriia Kashpruk | |
Wiktor Małek | |
Błażej Molik | |
Andrzej Morawski | |
Konrad Oleksy | |
Lucjan Pucelak | |
Aleksandra Sęk | |
Radosław Śliwiński | |
Piotr Traczyński | |
Katarzyna Trzos | |
Piotr Warząchowski | |
Olga Zaborska | |
:::

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

## Zadanie 1
:::success
Autor: Patryk Flama
:::

## Zadanie 2
:::success
Autor: Mikołaj Karapka
:::

### Rozważam adresowanie na 8 bitach

### Mapowanie bezpośrednie
| Adres | Tag | SS | BB | Hit? |
|----------|------|----|----|-----------------|
| 00000000 | 0000 | 00 | 00 | Compulsory miss |
| 00000001 | 0001 | 00 | 01 | Conflict miss |
| 00000010 | 0010 | 00 | 10 | Conflict miss |
| 00000000 | 0000 | 00 | 00 | Hit |

### Pamięć dwurożna
| Adres | Tag | S | BB | Hit? |
|----------|------|----|----|-----------------|
| 00000000 | 00000 | 0 | 00 | Compulsory miss |
| 00000001 | 00001 | 0 | 01 | Conflict miss |
| 00000010 | 00010 | 0 | 10 | Conflict miss |
| 00000000 | 00000| 0 | 00 | Miss |

## Zadanie 3
:::success
Autor: Piotr Traczyński
:::



- 0x027c -> 00 0010 0111 1100
TLBI = 01
TLBT = 00 0010
W TLB w pierwszym zbiorze o tagu 2 bit valid = 0.

Patrzymy w tablicy stron na VPN = 0x09 -> jest w pamięci operacyjnej PPN = 0x17 = 10001

Żeby uzyskać fizyczny adres musimy jeszcze dokleić offset z wirtualnego adresu więc ostatecznie uzyskujemy adres: 10001 111100

- 0x03a9 -> 00 0011 1010 1001
TLBI = 10
TLBT = 11

Nie ma wpisu w TLB

VPN = 0x0e -> PPN = 0x11 -> PA = 10001 1010 01

- 0x0040 -> 00 0000 0100 0000
TLBI = 01
TLBT = 0x00

Nie ma w TLB

VPN = 0x01

Mamy page fault-a.

## Zadanie 4
:::success
Autor: Viktoriia Kashpruk

Przypomnienie:

Dla danej strony o rozmiarze 4KiB, możemy wyrazić ten rozmiar jako $2^2 * 2^{10}$ bajtów, co daje łącznie $2^{12}$ bajtów. Zatem mamy 12 bitów na przesunięcie stron (VPO/PPO).

Adresy są 16-bitowe, co oznacza, że pozostałe 4 bity są przeznaczone na VPN.

Ponieważ TLB jest asocjacyjna, istnieje tylko jeden zestaw. W związku z tym indeks nie musi być przechowywany w VPN, co oznacza, że te 4 bity mogą być wykorzystane jako tag.
Przyjmujemy, że im mniejsza jest wartość LRU, tym starsze
**Przypadek 1.**
Jeśli nie znaleźliśmy szukanej strony w TLB, pobieramy ją z dysku, i umieszczamy ją w talbice stron i TLB.
TLB aktualizujemy w następujący sposób:
* usuwamy dowolną linię, która ma valid = 0, lub która ma najmniejsze LRU
* wstawiamy nową, z PPN większym od największego numeru ramki istniejącego w tablicy stron

#### Adres = $4669 = 0001 0010 0011 1101_2$
- **Tag**: 1
- **Typ zdarzenia**: Page fault
- **LRU**: 3
- **PPN**: 13

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

Tablica stron:
Dopisujemy wiersza z VPN, PPN, zmieniamy valid = 1
| 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 = $2227 = 0000 1000 1011 0011_2$
- **Tag**: 0
- **Typ zdarzenia**: page hit
- **LRU**: 2
- **PPN**: 5
Brak w TLB, ale jest w tablicy stron

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

Tablica stron bez zmian

#### Adres = $13916 = 0011 0110 0101 1100_2$
- **Tag**: 3
- **Typ zdarzenia**: Trafienie w TLB
- **LRU**: 2
- **PPN**: 6
Aktualizujemy LRU

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

Tablica stron bez zmian

#### Adres = $34587 = 1000 0111 0001 1011_2$
- **Tag**: 8
- **Typ zdarzenia**: page fault
- **LRU**: 1
- **PPN**: 14

**W TLB brak, w tablicy stron brak.**

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

#### Adres = $48870 = 1011 1110 1110 0110_2$
- **Tag**: 11
- **Typ zdarzenia**: Trafienie w tablicę stron
- **LRU**: 0
- **PPN**: 12

| Valid | Tag | LRU | PPN |
|-------|-----|-----|-----|
| 1 | 0 | 0 | 5 |
| 1 | 8 | 2 | 14 |
| 1 | 3 | 1 | 6 |
| 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 | 1 | 14 |
| 9 | 0 | Dysk |
| 10 | 1 | 3 |
| 11 | 1 | 12 |
| 12 | 0 | brak |

#### Adres = $12608 = 0011 0001 0100 0000_2$
- **Tag**: 3
- **Typ zdarzenia**: Trafienie w tablicę stron
- **LRU**: 3
- **PPN**: 6

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

#### Adres = $49225 = 1100 0000 0100 1001_2$
- **Tag**: 12
- **Typ zdarzenia**: page fault
- **LRU**: N/A
- **PPN**: N/A
Nie ma ani w TLB, a nie na dysku
:::

## Zadanie 5
:::success
Autor: Wiktor Małek


Strona ma 4KiB, czyli jak w poprzednim mamy 12 bitów na offsety.

32 bitowy adres space, 4KiB na stronę, czyli mamy total $2^{32}/(4*2^{10}) = 2^{20} = 1\space048\space576$ stron.

### a)
Page Table będzie miało 4MiB ponieważ, jedno PTE zajmuje 4 bajty, zatem skoro mamy $2^{20}$ stron do zapamiętania, to razem będzie nas to kosztować $2^{20} * 4$ B pamięci czyli 4 MB (1MiB to $2^{20}$)

### b)




Ponieważ tablica poziomu pierwszego ma $1024=2^{10}$ wpisów, to każda tablica drugiego poziomu będzie mieć $2^{20}/2^{10} = 2^{10} = 1024$ wpisów.

Nasz program ma 1GiB = $2^{30}$B czyli nasz program zajmie maksymalnie $2^{30}/2^{12} = 2^{18}$ stron.

#### Maksymalny
Maksymalny rozmiar tablicy stron uzyskamy, gdy będziemy musieli utrzymać jak najwięcej tabel poziomu drugiego, a tabel poziomu drugiego jest maksymalnie 1024(Bo każdy wiersz poziomu pierwszego, może przejść na maks. jedną tabelę poziomu drugiego), więc chcemy mieć po jednym wierszy w jak największej liczbie tabel poziomu drugiego.

Skoro mamy w naszym programie $2^{18}$ stron do zajęcia, to bierzemy jakieś $2^{10}$ stron pamięci naszego programu i umieszczamy je w pamięci wirtualnej tak, aby każda była w innej tabeli(to do czego się mapuje jedno PTE poziomu 1.) poziomu drugiego, pozostałe wiersze obojętnie, czyli zajmiemy na pewno wszystkie wiersze poziomu pierwszego, a gorzej się nei da.

#### Minimalny
Minimalny rozmiar tablicy będzie wtedy, gdy będziemy wypełniać kolejno/spójnie komórki pamięci wirtualnej.
Zajmiemy wtedy 1GiB/4MiB = $2^8$ = 256 wierszy pierwszego poziomu.

:::

## Zadanie 6
:::success
Autor: Patryk Flama
:::

> KiB - kibibajt
> MiB - mebibajt
* Wariant pesymistyczny:
Wszystkie strony mają taki sam index w TLB, wtedy dla > 4 stron mają miejsce same conflict missy
maksymalny rozmiar: 4 strony, 16 KiB
* Wariant optymistyczny:
TLB się zapełni zanim natrafimy na piątą stronę w tym samym zbiorze
64 strony, $64*4$Kib = 256 KiB
* Huge pages:
Wariant pesymistyczny:
wszystkie strony mają taki sam index TLB
4 strony, $4*4$MiB = 16 MiB
Wariant optymistyczny:
64 strony, $64*4$MiB = 256 MiB

## Zadanie 7
:::success
Autor: Szymon Fluder


### W jaki sposób tłumaczone są adresy wirtualne na fizyczne?

VPO = PPO, więc tutaj nic ciekawego się nie dzieje.

VPN ma 36 bitów; jak widać na obrazku tablica stron jest cztero poziomowa, zatem VPN jest dzielony na 4 fragmenty 9 bitowe, każdy fragment odpowiada offsetowi dla PTE w danym poziomie tablicy stron(która to linijka w danej tabeli).

CR3 widoczne po lewej na zdjęciu jest rejestrem zawierającym adres początku tablicy stron pierwszego poziomu; jest to część kontekstu procesu, która jest odtwarzana za każdym razem gdy zmieniamy proces.

### Format czteropoziomowej tablicy stron

#### Poziomy 1, 2, 3

Bity od 12 do 52 przechowują adres początku kolejnego poziomu tablicy stron.

Znaczenia pól:
- P: czy bity od 12 do 52 przechowują adres tablicy stron kolejnego poziomu.
- R/W: czy dla stron mamy read-only czy read-write (dla całego regionu obejmowanego z tego PTE)
- U/S: tryb user/supervisor(dla całego regionu obejmowanego z tego PTE)
- WT: określa polityke cache'u, write-through albo write-back (dla całego regionu obejmowanego z tego PTE)
- CD: czy strony są cacheowane czy ściągamy je od razu z pamięci(dla całego regionu obejmowanego z tego PTE)
- A: nie wiem
- PS: określa rozmiar strony
- XD: określa czy z regionów obejmowanych przez ten PTE można odczytywać instrukcje.

#### Poziom 4

Bity od 12 do 52 przechowują PPN.

Oznaczenia te same, oprócz tego, że mamy Dirty bit D, który mówi czy strona była modyfikowana i czy trzeba to zakutalizować w pamięci głównej przed usunięciem z podręcznej.

Mamy też bit G, którego definicja jest jasna na zdjęciu.

### Jaką przewagę ma taka tablica nad tablicą jednopoziomową?

Oszczędzamy pamięć(patrz zad.5), jesli PTE w tablicy danego poziomu jest NULL, to kolejne poziomy nie muszą istnieć.

:::

## Zadanie 8
:::success
Autor: Lucjan Pucelak
:::


(PIPT) Indeksowana fizycznie oznacza korzystanie z indeksu z adresu fizycznego (PA), natomiast znakowana fizycznie polega na używaniu tagu z adresu fizycznego.

(VIPT) Jeżeli w architekturze rozmiar VPO jest równy rozmiarowi PPO, możemy to wykorzystać do jednoczesnego wykonania dwóch zadań:

1. Obliczania CI oraz CO i pobierania odpowiedniego zestawu z pamięci cache.
2. Translacji VPN na PPN.

Po wykonaniu tych czynności, wystarczy porównać CT = PPN z tagami w zestawie.

## Zadanie 9
:::success
Autor: Wiktor Małek
:::



"Odwrócona" dlatego, że mamy tyle PTE ile stron fizycznych.

Skoro musimy zajrzeć do tablicy stron, to znaczy, że mieliśmy TLB miss.

Kroki translacji:
- funkcja haszująca bierze VPN i zwraca index do HPT, pod każdym indeksem HPT mieści się 8 PTE
(Tutaj jeśli więcej niż 8 VPN hashuje się pod jeden index to po prostu nie pamiętamy tych nadmiarowych)
- przeszukujemy całą grupę PTE
- jeśli ponownie mamy miss to możemy spojrzeć pod inny indeks znany poprzez "secondary hash value"(tak jest dane w książce)

Zalety:
- mniej odniesień do pamięci - w przypadku miss ładujemy 8 PTE.
- zaoszczędzamy pamięciowo na tym, że mamy tylko jedną tablicę stron.
Wady:
- W niefortunnym przypadku część VPN będzie się haszować pod index w HPT, który już ma 8 PTE.
- Konieczność sprawdzania całej grupy.