---
# System prepended metadata

title: 'Ćwiczenia 10, grupa śr. 17-19, 18. maja 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ćwiczenia 10, grupa śr. 17-19, 18. maja 2022

###### tags: `SYK21` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki        |       |     |     |     |     |     |     |     |     |
Kamila Brzozowska        |   X   |  X  |==X==|  X  |  X  |  X  |     |  X  |     |
Adam Ciężkowski          |   X   |  X   |  X   |  X  |  ==X==  |  X  |     | X   |     |
Natalia Czerep           |   X    |   X  |  X   |     |   X  |     |     |    X |   X  |
Jan Dalecki              |   X    |     |  X   |  X   |     |     |     |     |     |
Marko Golovko            |   X   |==X==|  X  |     |  X  |  X  |     |     |     |
Adam Górkiewicz          |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Piotr Gunia              |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Krzysztof Jadłowski      | X      |  X   |  X   |   X  |   X  |     |     |     |     |
Magdalena Jarecka        |  X     |     |     |  X   |  X   |     |     |     |     |
Mikołaj Jaszcza          |   X   |  X |  X  |  X  |  X  |    |     |     |     |
Monika Jędrzejkowska     |       |     |     |     |     |     |     |     |     |
Michał Kierul            |   X    |   X  |   X  |   X  |     |  X  |     |     |     |
Damian Lukas             |       |     |     |     |     |     |     |     |     |
Karol Ochman-Milarski    |       |     |     |     |     |     |     |     |     |
Piotr Piesiak            |       |     |     |     |     |     |     |     |     |
Damian Ratajski          |       |     |     |     |     |     |     |     |     |
Aleksandra Rozkrut       |   X   |==X==|  X  |  X  |  X  |  X  |     |     |     |
Marcin Sarnecki          |   X   |  X  |  X  |==X== |  X  |  X  |     |     |     |
Maria Szlasa             |       |     |  X  |  X  |  X  |     |     |     |     |
Mateusz Burdyna          | ==X== |  X  |  X  |  X  |  X  |     |     |  X  |     |
Magdalena Słonińska      |       |     |     |     |     |     |     |     |     |
Nikola Wrona             |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Marcin Wróbel            |   X   | X   |  X  |  X  |  X  |  X  |     |  X  |     |
:::





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

## Zadanie 1
:::success
Autor: Mateusz Burdyna
:::

![](https://i.imgur.com/FKKSXNH.png)

![](https://i.imgur.com/wylpfFN.png)

## Zadanie 2

:::success
Autor: Marko Golovko
:::

32-bitowe adresy 
Rozmiar bloku 32 bajty
32 wiersze ma pamięć

tag - 22 bity
index - 5 bitów
offset - 5 bitów

```
      tag                    index offset hit
      0000000000000000000000 00000 00010  cold
      0000000000000000000000 10000 00000  cold
      0000000000000000000001 10000 00000  replace
      0000000000000000000000 00000 00100  hit
```
* Pamięć dwudrożna używa LRU jako polityki wymiany
16 wiersze ma pamięć
tag - 22 bity
index - 4 bity
offset - 5 bitów
```
      tag                    index offset hit
      00000000000000000000000 0000 00010  cold
      00000000000000000000001 0000 00000  cold
      00000000000000000000011 0000 00000  replace
      00000000000000000000000 0000 00100  replace
```


:::danger
Autor: Krzysztof Jadłowski
:::




## Zadanie 3
:::success
Autor: Jan Dalecki
:::

TLB - Niewielka pamięć przechowująca niektóre wpisy tablicy stron, którą MMU może bezpośrednio używać bez konieczności pobierania wpisu z tablicy stron w pamięci operacyjnej.


0x027c = 10 | 01 | 111100
0x03a9 = 11 | 10 | 101001
0x0040 = 00 | 01 | 000000 


| Adres  | VPN | VPO  | TLBI | TLBT | PPN  | CO  | CI  |  CT  |
|:------:|:---:|:----:|:----:|:----:|:----:|:---:| --- |:----:|
| 0x027c | 0x9 | 0x3c | 0x1  | 0x2  | 0x17 | 0x0 | 0xf | 0x17 |
| 0x03a9 | 0xe | 0x29 | 0x2  | 0x3  | 0x11 | 0x1 | 0xa | 0x11 |
| 0x0040 | 0x1 | 0x0  | 0x1  | 0x0  |  --  | --  | --  |  --  |


## Zadanie 4
:::success
Autor: Marcin Sarnecki
:::
![](https://i.imgur.com/ub6UqiF.png)


4KiB = 4096B
$2^{12}=4096 \rightarrow$ VPO na 12 bitach, na największy adres potrzebujemy 16 bitów, więc VPN na 16 - 12 = 4 bitach


---

Krok 1:
| VPN  | VPO            | TLB hit? | Page hit? | 
| ---- | -------------- | -------- | --------- | 
| 0001 | 0010 0011 1101 | nie      | nie       | 

| Valid? | Tag | LRU | PPN |
| ------ | --- | --- | --- |
| 1      | 11  | 1   | 12  | // pozostałe postarzamy o 1
| 1      | 7   | 2   | 4   |
| 1      | 3   | 3   | 6   |
| 1      | 1   | 0   | 13  | // nadpisujemy najstarszy zapis

| VPN | Valid? | PPN                                           |
| --- | ------ | --------------------------------------------- |
| 0   | 1      | 5                                             |
| 1   | 1      | 13 (bo największą używaną poprzednio jest 12) |
| 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                                          |





---

Krok 2:
| VPN  | VPO            | TLB hit? | Page hit?  | 
| ---- | -------------- | -------- | ---------- | 
| 0000 | 1000 1011 0011 | nie      | tak        | 

| Valid? | Tag | LRU | PPN             |
| ------ | --- | --- |:--------------- |
| 1      | 11  | 2   | 12              |
| 1      | 7   | 3   | 4               |
| 1      | 0   | 0   | 5 (nadpisujemy) |
| 1      | 1   | 1   | 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   | 0      | dysk |
| 9   | 0      | dysk |
| 10  | 1      | 3    |
| 11  | 1      | 12   |
| 12  | 0      | brak |





---
Krok 3
| VPN  | VPO            | TLB hit? | Page hit?  | 
| ---- | -------------- | -------- | ---------- | 
| 0011 | 0110 0101 1100 | nie      | tak        | 

| Valid? | Tag | LRU | PPN |
| ------ | --- | --- |:--- |
| 1      | 11  | 3   | 12  |
| 1      | 3   | 0   | 6   |
| 1      | 0   | 1   | 5   |
| 1      | 1   | 2   | 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   | 0      | dysk |
| 9   | 0      | dysk |
| 10  | 1      | 3    |
| 11  | 1      | 12   |
| 12  | 0      | brak |



---
Krok 4
| VPN  | VPO            | TLB hit? | Page hit?  | 
| ---- | -------------- | -------- | ---------- | 
| 1000 | 0111 0001 1011 | nie      | nie        |

| 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  (wczytujemy) |
| 9   | 0      |       dysk       |
| 10  | 1      |        3         |
| 11  | 1      |        12        |
| 12  | 0      |       brak       |




---
Krok 5
| VPN  | VPO            | TLB hit? | Page hit?  |
| ---- | -------------- | -------- | ---------- | 
| 1011 | 1110 1110 0110 | nie      | tak        | 

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

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





---
Krok 6


| VPN  | VPO            | TLB hit? | Page hit?  | 
| ---- | -------------- | -------- | ---------- | 
| 0011 | 0001 0100 0000 | tak      | -----      | 

| Valid? | Tag |                LRU                 | PPN |
| ------ | --- |:----------------------------------:|:--- |
| 1      | 8   |                 2                  | 14  |
| 1      | 3   | 0  (zmieniam jego stan, bo używam) | 6   |
| 1      | 0   |                 3                  | 5   |
| 1      | 11  |                 1                  | 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 |




---
Krok 7

| VPN  | VPO            | TLB hit? | Page hit?  | 
| ---- | -------------- | -------- | ---------- | 
| 1100 | 0000 0100 1001 | nie      | nie        | 

| Valid? | Tag | LRU | PPN |
| ------ | --- | --- |:--- |
| 1      | 8   | 2   | 14  |
| 1      | 3   | 0   | 6   |
| 1      | 0   | 3   | 5   |
| 1      | 11  | 1   | 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 |





---

Wynik końcowy

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

| 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: Adam Ciężkowski
:::

![](https://i.imgur.com/iCLG4sx.png)

a) $2^{32} \cdot 2^{-12} \cdot 2 ^ 2 = 2^{22}$ (4MiB)
b) 
$1$ GiB = $2^{30}$ B
4 KiB = $2^{12}$ B
Potrzebujemy $2^{30} / 2^{12} = 2^{18}$ stron
Minimalny: $(2^{8} + 1) \cdot 2^{10} \cdot 2^{2} \approx 2^{20}$ (1MiB)
Maksymalny: $(2^{10} + 1) \cdot 2^{10} \cdot 2^{2} \approx 2^{22}$ (4MiB)


## Zadanie 6
:::success
Autor: Michał Kierul
:::
![](https://i.imgur.com/tPEJTUs.png)

Zbiór roboczy to zbiór aktualnie aktywnych stron w pamięci wirtualnej wykorzystywanych przez proces.
Czterodrożne TLB o 64 wpisach ma 16 setów po 4 wpisy. W optymistycznym przypadku wykorzystane są wszystkie 64 wpisy, czyli pamięć 4KiB * 64 = 256KiB.
W pesymistycznym wypadku wszystkie wykorzystywane strony mogą należeć do tego samego seta. Wtedy maksymalnie tych stron może być 4, więc pamięć 4KiB * 4 = 16KiB.

Dla dużych stron jest odpowiednio 256MiB i 16MiB.

## Zadanie 7
:::danger
Autor:
:::

## Zadanie 8
:::success
Autor: Marcin Wróbel
:::
![](https://i.imgur.com/jpZvVOG.png)

![](https://i.imgur.com/AAU6hdY.png)

Gdy w architekturze rozmiar **VPO** równy rozmiarowi **PPO**, możemy wykorzystać tę informację, do równoległego wykonania następujących **2** czynności:
- obliczenia **CI**, oraz **CO**, i pobraniania odpowiegniego set'u z cache
- przetłumaczenia **VPN** na **PPN**

Dzięki temu będziemy po wykonaniu powyższych zadań będziemy musieli tylko porównać
**CT** = **PPN** z tagami w setcie


## Zadanie 9
:::success
Autor: Natalia Czerep
:::

Źródło (oprócz książki):
https://web.eecs.umich.edu/~akamil/teaching/sp04/040104.pdf



Ogólne idee:

1) Zamiast jednego wpisu na każdą wirtualną stronę należącą do procesu, zawiera jeden wpis dla każdej strony fizycznej w pamięci głównej.

2) Kazdy proces ma tą samą page table

3) Page Table Entry jest indeksowane przez fizyczny nr strony a nie vpn 



**Wersja najprostsza:**

Skoro tabela jest współdzielona przez procesy , każdy wpis musi zawierać identyfikator procesu. A skoro fizyczne strony
są teraz mapowane na wirtualne, każdy wpis zawiera wirtualny numer strony zamiast fizycznego. Fizyczny
numer strony nie jest przechowywany, ponieważ odpowiada mu indeks w tabeli.
Aby przetłumaczyć wirtualny adres, porównuje się wirtualny numer strony i bieżący identyfikator procesu
dla każdego wpisu, przechodząc kolejno przez tablicę. Jeśli nie zostanie znalezione żadne dopasowanie, wystąpi błąd strony.

![](https://i.imgur.com/52EB66X.png)


**Wersje z haszowaniem:**

Hashed inverted page table  dodaje dodatkowy poziom przed rzeczywistą tabelą stron, nazywany hash anchor table.
Ta tabela jest co najmniej tak duża jak page table i odwzorowuje identyfikatory procesów i vpn na wpisy w tabeli. Ponieważ mogą wystąpić kolizje, tabela stron musi mieć tzw łańcuchy. Ponieważ każdy element w łańcuchu
musi mapować do tej samej części pamięci fizycznej, łańcuch może być
reprezentowany jako sekwencja wpisów w tablicy stron, przy czym każdy wpis wskazuje na następny wpis w łańcuchu.

Teraz, aby przetłumaczyć adres wirtualny, identyfikator procesu i numer strony wirtualnej są haszowane, aby uzyskać
wpis w hash anchor table. Idziemy dzięki wskaźnikowi do wpisu w page table. Identyfikator procesu
i vpn są porównywane z zapisanymi tam. Jeśli się nie zgadzają, proces jest powtarzany z dalszymi wpisami w łańcuchu aż do znalezienia dopasowania.

![](https://i.imgur.com/57H1URC.png)

![](https://i.imgur.com/p72XcIH.png)

