# Ćwiczenia 10, grupa cz. 14-16, 19. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | | | | | | | | | |
Dariusz Ciesielski | | | | | | | | | |
Dawid Dudek | ==X== | X | X | | X | | | | |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | X | X | X | X | X | X | | X | |
Adam Jarząbek | X | X | X | | | | | | |
Anna Karykowska | X | X | X | | X | X | | | |
Oleś Kulczewicz | | | | | | | | | |
Pola Marciniak | X | X | X | X | X | X | | | |
Mikołaj Mroziuk | X | X | X | X | X | X | X | X | |
Marcelina Oset | X | X | X | X | X | | | X | |
Natalia Piasta | X | X | X | X | X | X | | X | |
Krzysztof Piekarczyk | X | ==X== | X | X | X | X | | X | |
Marcin Płaza | X | X |X | | | | | | |
Paweł Richert | | ==X== | X | X | X | | | | |
Rafał Starypan | X | X | X | | X | | | | |
Dawid Strojek | X | X | X | | X | X | | | |
Mateusz Suszek | | | | | | | | | |
Wojciech Śniady | X | X | X | | X | X | | | |
Volha Tsekalo | X | X | X | | X | X | | | |
Yana Vashkevich | X | X | X | | X | X | | | |
Konrad Woźniak | X | ==X== | X | | X | X | | | |
Natalia Czerep | | | | | | | | | |
Joanna Stachowicz | X | X | ==X== | | X | X | | | |
:::

**Tu można dodeklarować zad. 9. z listy 9.:**
*
*
*

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

## Zadanie 1
:::success
Autor: Dawid Dudek
:::



Takie kodowanie pozwala na większe rozsianie danych po pamięci podręcznej. Poprzez umieszczenia indeksu - odpowiedzialnego za wybór zbioru - w środku, przy próbie dostępu do elementów o w miarę bliskich adresach np. elementy tabeli, będziemy zapisywać dane do różnych zbiorów. Pozwoli to zapobiec nadpisywaniu danych i tym samym chybień. Odwrotna reprezentacja w pierwszej kolejności zmieniałaby znacznik a tym samym korzystałaby z bardziej ograniczonego zakresu pamięci, co mogłoby doprowadzić do częstszych kolizji.

## Zadanie 2
:::success
Autor: Paweł Richert

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

:::

## Zadanie 3
:::success
Autor: Joanna Stachowicz




:::

## Zadanie 4
:::success
Autor: Marcelina Oset
:::



**tablica stron** -- tablica przetrzymywana w pamięci operacyjnej komputera, która ma w sobie informacje potrzebne do przetłumaczenia adresu wirtuanego danego procesu, na adres fizyczny. Każdy proces ma własną tablicę stron.
**TLB w pełni asocjacyjna** -- każdy adres może zostać zapamiętany w dowolnym bloku pamięci podręcznej; brak indeksów
**wtoczenie (ang. swap-in)** -- wczytanie wpisu w tablicy stron, którego nie było w pamięci głównej
**ramka (ang. page frame)** -- fragment pamięci fizycznej; "physical page"
**błąd strony** -- rodzaj błędu kiedy uruchomiony program uzyskuje dostęp do strony pamięci, która nie jest obecnie mapowana do wirtualnej przestrzeni adresowej procesu

Rozmiar strony: 4KiB = $4 * 2^{10}$ = $2^{12}$
Stąd wiemy, że przeznaczamy 12 bitów na offset (VPO). Pozostałe bity przeznaczamy na VPN. Skoro nie mamy bitów na indeks (bo TLB jest w pełni asocjacyjna), to bity przeznaczone na VPN są takie same jak dla tagu (TLBT).

1) $4669_{10} = 0001\ 0010\ 0011\ 1101_2$

VPO: $0010\ 0011\ 1101_2$ = 0x23d
VPN, TLBT: $0001_2$ = 0x1

W TLB nie ma takiego tagu.
W tablicy stron, dla VPN == 0x1, nie mamy przypisanego PPNu. Czyli mamy page fault.

W TLB tag 11 ma najmniejsze LRU, dlatego w tym miejscu wprowadzimy nową wartość. Wpisujemy tag 1, a LRU zmieniamy na 3 (bo to maksymalna wartość), z kolei pozostałe LRU w tablicy zmniejszamy o 1. PPN ustawiamy na 13, bo jest to następna wartość niewystępująca w tablicy stron.
Tak samo aktualizujemy tablicę stron, zmieniamy valid bit na 1 i PPN na 13.

TLB hit? **F**
page table hit? **F**
page fault? **T** (minor page fault)

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

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

2. $2227_{10} = 0000\ 1000\ 1011\ 0011_{2}$

VPO = $1000\ 1011\ 0011_{2}$ = 0x8B3
VPN, TLBT = $0_2$ = 0x0

W TLB nie ma tagu 0.
TLB hit? **F**
page hit? **T**
page fault? **F**

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

tablica stron się nie zmienia.

3) $13916_{10} = 0011\ 0110\ 0101\ 1100_{2}$

VPO = $0110\ 0101\ 1100_{2}$ = 0x65C
VPN, TLBT = 0x3

TLB hit? **T**

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

Znaleźliśmy tag 3 w TLB, więc zmieniamy mu LRU na maksymalne, a pozostałe zmniejszamy o 1.

4. $34587_{10} = 1000\ 0111\ 0001\ 1011_{2}$

VPO = $0111\ 0001\ 1011_{2}$ = 0x71B
VPN, TLBT = $1000_2$ = 0x8

TLB hit? **F**
page hit? **F**
page fault? **T** (minor page fault)

| Valid | Tag | LRU | PPN |
| ----- | ----- | --- | --- |
| 1 | 1 | **0** | 13 |
| 1 | 0 | **1** | 5 |
| 1 | 3 | **2** | 6 |
| 0 | **8** | **3** | **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 |

5. $48870_{10}$ = $1011\ 1110\ 1110\ 0110_2$

VPO = $1110\ 1110\ 0110$ = 0xEE6
VPN, TLBT = $1011_2$ = 0xB

TLB hit? **F**
page hit? **T**
page fault? **F**

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

6. $12608_{10} = 0011\ 0001\ 0100\ 0000_{2}$

VPO = $0001\ 0100\ 0000_{2}$ = 320
VPN, TLBT = $0011_2$ = 3

TLB hit? **T**

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

7. $49225_{10}$ = $1100\ 0000\ 0100\ 1001_2$

VPO = $0000\ 0100\ 1001_2$ = 73
VPN, TLBT = $1100$ = 12

TLB hit? **F**
page hit? **F**
page fault? **T** (major page fault)

## Zadanie 5
:::success
Autor: Konrad Woźniak
:::


## Zadanie 6
:::success
Autor: Anna Karykowska
:::


**Zbiór roboczy procesu** (ang. working-set) — zbiór stron, które zostały zaadresowane w ciągu ostatnich X odniesień do pamięci; aktualnie aktywne strony w pamięci wirtualnej

W zadaniu mamy czterodrożne TLB o 64 wpisach. Będzie ono miało po 4 wpisy w secie, czyli 16 setów.

$4 KiB = 2^{12}$
- optymistyczny przypadek
Wykorzystamy wszystkie 64 wpisy, czyli $4KiB * 64 = 256KiB$.

- pesymistyczny przypadek
Wszystkie odwołania będą do tego samego setu. Wtedy będziemy mieli $4KiB * 4 = 16KiB$.

Dla dużych stron będziemy mieli:
$4 MiB = 2^{22}$
optymistycznie: 256MiB
pesymistycznie: 16MiB

## Zadanie 7
:::success
Autor: Mikołaj Mroziuk
:::
### strony poziomu 1 - 3
| - | - |
| -------- | -------- |
| P | czy znajuje się następna strona w pamięci |
| R/W | dostęp read-only czy read-write|
| U/S | user / supervisor(kernel) - kto ma dostęp |
| WT | Write-through / write-back |
| CD | cache disable |
| A | Bit referencji (accessed) ustawiany przez MMU przy odczytach i zapisach, pomocny jest on w algorytmie zastępowania stron pamięci wirtualnej. |
| PS | page size - Bit mówiący o rozmiarze strony (zdefiniowany tylko dla poziomu pierwszego), jest to albo 4KiB, albo 4 MiB. |
| Base addr | Bazowy adres fizyczny strony (PPN). |
| XD | Bit określający, czy można wykonać dostęp do danej strony. Gdy jest on ustawiony, próba wykonania zawartości tej strony jako kodu zakończy się wygenerowaniem wyjątku. Mechanizm ten chroni aplikacje przed niektórymi wersjami ataku buffer overflow, nie pozwalając wykonać kodu z zablokowanej strony. Powinien on być ustawiony dla wszystkich stron procesu z wyjątkiem programu i bibliotek oraz świadomie dozwolonych przez program wyjątków. |

### strona poziomu 4

| - | - |
| -------- | -------- |
| D | bitem dirty, określającym czy wykonano zapis przez MMU |
| 7 | nieużywany, zawsze wyzerowany|


36-bitowy VPN jest dzielony na 9-bitowe części, każdy jest używany jako offset tabeli stron. rejestr CR3 zawiera fizyczny adres L1 pamięci. VPN 1 to offset L1 PTE, VPN 2 zawiera offset

MMU tłumacząc wirtualny adres aktualizuje dwa bity używane przez kernel’s page fault handler
* MMU ustawia bit A - (Bit referencji) za każdym razem gdy strona jest odwiedzona. bit przydaje się w algorytmie zamiany stron
* MMU ustawia bit D (dirty bit) - za każdym razem gdy zapisuje do strony. Służy do sprawdzania czy trzeba zapisać stronę przed nadpisaniem jej

## Zadanie 8
:::success
Autor: Przemysław Grochal
:::


Do odczytu wpisu z pamięci podręcznej potrzebujemy Cache Tag, Cache Index oraz Cache Offset.
Cache Index i Cache Offset pochodzą z PPO. Możemy zauważyć, że VPO jest równe PPO. Wartości CO i w szczególności CI moga zostać uzyskane przed dokonaniem translacji VPN->PPN.

Aby przyspieszyć proces, równolegle do translacji wysyłamy do pamięci podręcznej VPO. Używając CI możemy wyciągnąć wpis (lub w przypadku większej drożności: kilka tagów). Po zakończonej translacji możemy od razu przejść do sprawdzania tagu, oszczędzając czas na przeszukiwanie pamięci podręcznej.

## Zadanie 9
:::success
Autor:Przemysław Grochal
:::

Wpisy w odwróconej tabeli stron odpowiadają stronom pamięci fizycznej, nie wirtualnej. Z tego powodów, nie mogą być indeksowane za pomocą VPN. Aby dokonać translacji z VPN na PPN stosuje się funkcję hashującą.
Funkcja hashująca może zwrócić nam taką samą wartość dla różnych adresów. Zatem jednemu VPN może odpowiadać wiele wpisów. Potrzebny jest nam mechanizm kontroli konfliktów. W PowerPC funkcję tę pełni grupa 8 wpisów. Jeżeli więcej niż 8 wpisów dopasowuje się do naszego hasha, nadmiarowe wpisy po prostu pomijamy.
Ponieważ wpisy nie mają bezpośredniego związku z VPN i PPN, musza zawierać obie te informacje, co wpływa na rozmiar wpisów.
Po wyliczeniu hasha wczytujemy całą grupę i dokonujemy jej przeszukania w poszukiwaniu VPN. W przypadku chybienia, możemy wykonać drugie przeszukiwanie z inną funkcją hashującą.

Zalety:
* Kompaktowość całej tablicy. Dla klasycznej tablicy stron i 64-bitowej przestrzeni adresowej, tablica stron może być potencjalnie bardzo duża. Odwrócona tablica stron skaluje się z pamięcią fizyczną.

Wady:
* Duży rozmiar wspisów/grupy wpisów.
* Problemy ze współdzieleniem pamięci. Jeden VPN odpowiada dokładnie jednemu PPN.
* Potencjalnie skomplikowana implementacja (chociażby ze względu na funkcję hashującą).