---
# System prepended metadata

title: 'Ćwiczenia 11, grupa cz. 10-12, 16 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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			
:::
![image](https://hackmd.io/_uploads/rkM3UrGmA.png)
![image](https://hackmd.io/_uploads/BkH9sBMmR.png)
![image](https://hackmd.io/_uploads/Hyp9iSz7C.png)

## Zadanie 2
:::success 
Autor: Mikołaj Karapka			
:::
![image](https://hackmd.io/_uploads/By8cZS77A.png)
 
### 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			
:::

![image](https://hackmd.io/_uploads/SyV1XrXQ0.png)

![image](https://hackmd.io/_uploads/HkORGrmX0.png)

- 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	
![image](https://hackmd.io/_uploads/HkL3VImXR.png)

Przypomnienie:
![image](https://hackmd.io/_uploads/rkUTVL7mC.png)


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	

![zad_5_polecenie](https://hackmd.io/_uploads/BJIfXH7XC.jpg)

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)

![zad_5_paragraf](https://hackmd.io/_uploads/SktVXSQX0.jpg)

![zad_5_tabelka](https://hackmd.io/_uploads/rJtr7H7mC.jpg)

![zad_5_redukcja](https://hackmd.io/_uploads/BkWvQB7QC.jpg)

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	 		
:::
![image](https://hackmd.io/_uploads/BJkzAOhX0.png)
![image](https://hackmd.io/_uploads/rk54xY27A.png)


> 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
![image](https://hackmd.io/_uploads/rJu7UnjmA.png)

![zad_7_translacja](https://hackmd.io/_uploads/rymLLhiXA.jpg)

### 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
![zad_7_lvl_1_2_3](https://hackmd.io/_uploads/S1iDL3iXA.jpg)

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
![zad_7_lvl_4](https://hackmd.io/_uploads/r1ZYL3sQC.jpg)

Bity od 12 do 52 przechowują PPN.
![zad_7_page_replacement](https://hackmd.io/_uploads/SkDc82omR.jpg)

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

![Screenshot 2024-05-23 at 10.25.01](https://hackmd.io/_uploads/rkuF6dhmR.png)
![Screenshot 2024-05-23 at 09.05.31](https://hackmd.io/_uploads/HJtt6uh70.png)

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

![zad_9_polecenie](https://hackmd.io/_uploads/Sk8gCunmC.jpg)

![zad_9_table](https://hackmd.io/_uploads/HJUbAd37C.jpg)


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

