# Lista 14 (17.06.2021), grupa pwit

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

Tabelka zawiera tylko osoby zapisane do grupy.

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec | | | | | | | | |
|Kacper Bajkiewicz | | | | | | | | |
|Bartłomiej Hildebrandt| X | X | | | | | | |
|Dominik Komła | | | | | | | | |
|Aleksandra Kosińska | X | X | | | X | | X | |
|Oleś Kulczewicz | X | X | | | | | | |
|Damian Lukas | | | | | | | | |
|Michał Mikołajczyk | | | | | | | | |
|Mateusz Opala | | | | | | | | |
|Łukasz Orawiec | X | X | | | | | X | |
|Szymon Pielat | X | X | | | | | | |
|Łukasz Pluta | X | X | | | X | X | X | X |
|Kamil Puchacz | | | | | | | | |
|Magdalena Rzepka | X | X | X | | X | | | |
|Cezary Stajszczyk | X | X | | | X | | X | |
|Jakub Szajner | | | | | | | | |
|Bartosz Troszka | | | | | | | | |
|Miłosz Urbanik | X | X | | | | | | |
:::

## Zadanie 1
:::info
Autor: Bartłomiej Hildebrandt
:::

> Niech system posługuje się 32-bitowymi adresami wirtualnymi, rozmiar strony ma 4KiB, a rozmiar wpisu tablicy stron zajmuje 4 bajty. Dla procesu, który łącznie używa 1GiB swojej przestrzeni adresowej podaj rozmiar tablicy stron: (a) jednopoziomowej, (b) dwupoziomowej, gdzie katalog tablicy stron ma 1024 wpisy. Dla drugiego przypadku – jaki jest maksymalny i minimalny rozmiar tablicy stron?

**adres wirtualny** - liczba binarna w pamięci wirtualnej, która umożliwia procesowi wykorzystanie lokalizacji w pamięci głównej niezależnie od innych procesów i wykorzystanie większej ilości miejsca niż faktycznie istnieje w pamięci głównej poprzez tymczasowe przeniesienie części zawartości na dysk twardy.

**strona** - strona pamięci wirtualnej to ciągły blok pamięci wirtualnej o stałej długości opisany przez pojedyńczy **wpis w tablicy stron**

**wpis tablicy stron (PTE)** - zawiera mapowanie między adresem wirtualnym strony, a adresem ramki fizycznej. Zawiera również informacje pomocnicze o stronie, takie jak np. dirty bit.

**przestrzeń adresowa** - zakres adresów, do których odwołuje się proces

### Podaj rozmiar tablicy stron jednopoziomowej


W tablicy stron jednopoziomowej nie mamy podziału na podstrony, więc nie wiemy, które obszary są używane, a które nie są, więc zajmujemy obszar potrzebny na przetrzymanie danych w całej tablicy.

- System: 32 bitowy
- Rozmiar wpisu tablicy stron: 4 bajty
- Rozmiar strony 4 KiB = 4096 bajtów

Niech $x = liczba możliwych adresów wirtualnych$ oraz niech $y = rozmiar strony$. Wtedy liczba stron w tablicy wynosi $x / y = 2^{32} / 2^{12} = 2^{20} stron$.

Następnie musimy obliczyć niezbędną pamięć fizyczną na pomieszczenie wszystkich stron pamięci. Niech $x = rozmiar wpisu$ oraz niech $y = liczba stron w tablicy$. Wtedy rozmiar niezbędnej pamięci wynosi $x * y = 4 * 2^{20} = 2^{22} = 4 MiB$

### Podaj rozmiar tablicy stron dwupoziomowej. Jaki jest maksymalny i minimalny rozmiar tablicy stron?


W tablicy stron dwupoziomowej mamy znacznie korzystniejszą sytuację. W przypadku gdy wszystkie komórki pamięci na drugim poziomie w całym bloku są nieużywane, możemy to odnotować na pierwszym poziomie, że nic się w danej tablicy nie znajduje i jej nie potrzebujemy. Dzięki temu, możemy znacznie zaoszczędzić pamięć.

- Katalog tablicy stron: 1024 wpisy

W tym przypadku katalog stron ma 1024 wpisy, a liczba stron do pomieszczenia to $2^{20}$, więc każdy wpis katalogu stron wskazuje na 1024 inne tablice stron.

Maksymalny rozmiar tablicy stron liczymy w ten sposób, że wiemy że w jednym katalogu jest 1024 wpisów i każdy katalog wskazuje na 1024 inne tablice stron, a jeden wpis zajmuje 4 bajty, a więc mnożymy liczbę wpisów razy ich rozmiar i dodajemy rozmiar katalogu stron: $1024 * 4B + 4 MiB$. Zatem jest to rozmiar całkowitej niezbędnej pamięci fizycznej jednopoziomowej + rozmiar wszystkich wpisów pamięci dodatkowego poziomu.

Natomiast minimalny rozmiar tablicy stron jest znacznie niższy. Każda strona na drugim poziomie może odwzorować $2^{22}$ bajtów, ponieważ ma 1024 wpisy, a każdy z nich wskazuje na stronę o rozmiarze 4096 bajtów. Proces zużywa 1 GiB swojej przestrzeni adresowej, a więc potrzebujemy: $1 GiB / 2^{22} = 2^{30} / 2^{22} = 2^{8} = 256$ stron drugiego poziomu. Każda strona ma 4 KiB, więc całkowity rozmiar minimalny to 1024 KiB.

## Zadanie 2
:::info
Autor: Miłosz Urbanik
:::


**TLB** (translation lookaside buffer) - część MMU (kontroler pamięci - memory-management unit) służący translacji adresów wirtualnych na adresy fizyczne bez konieczności odszukiwania PTE (page table entries) w cache.

W zadaniu krzystamy z poniższych założeń:
- pamięć adresowana bajtowo
- dostępy do pamięci korzystają z 1 bajtowych słów
- adres wirtualny zapisany jest na 14 bitach
- adres fizyczny zapisany jest na 12 bitach
- rozmiar strony 64 bajty
- TLB 4-drożna z 16 miejscami
- 1-drożna pamięć z 4 bajtową linią i 16 zbiorami




- Strona ma rozmiar 64 bajtów stąd 6 bitów koduje offset wobec początku strony. (VPO)
- TLB ma 4 zbiory zatem 2 bity kodują indeks. (TLBI)
- blok cache ma 4 bajty zatem 2 bity kodują offset bloku cache (CO)
- 16 zbiorów cache stąd 4 bity kodują indeks cache (CI)

| adres wirtualny | VPN | TLBI | TLBT | TLB Hit | Page Fault | PPN | CO | CI | CT | Cache hit |
| --------------- | --- | ---- | ---- | ------- | ---------- | ---- | --- | ---- | ---- |-----------|
| 0x027c | 0x9 | 0x1 | 0x2 | tak | nie | 0x17 | 0x0 | 0x0f | 0x17 | nie |
| 0x03a9 | 0xe | 0x2 | 0x3 | nie | nie | 0x11 | 0x1 | 0xa | 0x11 | nie |
| 0x0040 | 0x1 | 0x1 | 0x0 | nie | tak | - | - | - | - | - |

tłumaczanie adresu `0x027c`

|VA|VPN|TLBI|TLBT|PPN = CT| VPO = PPO|
|--|---|----|----|-------|-----------|
|00 0010 0111 1100| 0000 1001|01|000010|0001 0111|1111 00|

|PA| CT| CI| CO |
|--|---| --| ---|
|010111 111100| 010111|1111|00|

## Zadanie 3
:::info
Autor: Magdalena Rzepka
:::

**w pełni asocjacyjny** - tag może być przechowywany w dowolnym miejscu
**ofiara** - wpis w tablicy, który musimy usunąć
**wtoczenie** - proces zapisywania strony z dysku
**ramka** - fizyczny blok pamięci trzymający strony
**błąd strony** - próba odczytania strony, która nie jest w ramce

4 - bity VPN
12 - bitów offsetu

**123d** = 0001 001000111101
VPN = 1
TLB = NO
PPN = page-fault dysk = 0x0D (kolejne wolne)

**08b3** = 0000 100010110011
VPN = 0
TLB = NO
PPN = HIT -> 05

**365c** = 0011 011001011100
VPN = 3
TLB = NO
PPN = HIT -> 06

**871b** = 1000 011100011011
VPN = 8
TLB = NO
PPN = page-fault dysk = 0x0E (kolejne wolne)

**bee6** = 1011 111011100110
VPN = 0B
TLB = NO
PPN = HIT -> 0C

**3140** = 0011 000101000000
VPN = 3
TLB = YES
PPN = 06

**c049** = 1100 000001001001
VPN = 0C
TLB = NO
PPN = brak/błąd

**Tablica stron**

| VPN | Valid | PPN |
|:---:|:-----:|:----:|
| 00 | 1 | 05 |
| 01 | 1 | 0D |
| 02 | 0 | dysk |
| 03 | 1 | 06 |
| 04 | 1 | 09 |
| 05 | 1 | 0B |
| 06 | 0 | dysk |
| 07 | 1 | 04 |
| 08 | 1 | 0E |
| 09 | 0 | dysk |
| 0A | 1 | 03 |
| 0B | 1 | 0C |
| 0C | 0 | brak |

**TLB**

| Valid | Tag | LRU | PPN |
|:-----:|:---:|:---:|:---:|
| 1 | 08 | 2 | 0E |
| 1 | 03 | 0 | 06 |
| 1 | 00 | 4 | 05 |
| 1 | 0B | 1 | 0C |

**Przejścia krok po kroku**
tag:
OB -> LRU = 1
07 -> LRU = 2
03 -> LRU = 3
04 -> tag:01 ; LRU = 0 ; PPN = 0D

tag:
OB -> LRU = 2
07 -> LRU = 3
03 -> tag:00; LRU = 0; PPN = 05
01 -> LRU = 1

tag:
OB -> LRU = 3
07 -> tag:03; LRU = 0; PPN = 06
00 -> LRU = 1
01 -> LRU = 2

tag:
OB -> tag:08; LRU = 0; PPN = 0E
03 -> LRU = 1
00 -> LRU = 2
01 -> LRU = 3

tag:
08 -> LRU = 1
03 -> LRU = 2
00 -> LRU = 3
01 -> tag:0B ; LRU = 0 ; PPN = 0C

tag - bez zmian bo trafienie tylko LRU++
08 -> LRU = 2
03 -> LRU = 0
00 -> LRU = 4
0B -> LRU = 1

## Zadanie 4
:::info
Autor:
:::

## Zadanie 5
:::info
Autor: Cezary Stajszczyk
:::

**Zbiór roboczy** - zbiór stron w pamięci, z których proces korzystał w ostatnim okresie czasu.

TLB: 4-drożny 64 wpisy czyli 16 zbiorów po 4 wpisy

Wariant optymistyczny:
Proces korzysta ze wszystkich wpisów we wszystkich zbiorach, czyli $64 \cdot 4KB = 256KB$

Wariant pesymistyczny:
Proces korzysta z tylko jednego zbioru, czyli $4 \cdot 4KB = 16KB$

**Duże strony** to strony o rozmiarze większym niż standardowe $4KB$. Nigdy nie trafiają one do pamięci wymiany i zawsze przechowywane są w pamięci RAM.

Aby zakodować dużą stronę w hierarchicznej tablicy stron należy ustawić bit $PS$. Możemy to zakodować tylko dla wpisu na pierwszym poziomie.

grep Hugepagesize /proc/meminfo

https://docs.oracle.com/database/121/UNXAR/appi_vlm.htm#UNXAR400

## Zadanie 6
:::info
Autor: Łukasz Pluta
:::

pamięć podręczna indeksowana i znakowana adresami fizycznymi - model pamięci w której bity tagu i bity indeksu są brane z adresu fizycznego

Równoległy dostęp do TLB i pamięci podręcznej używająć pamięci indeksowanej wirtualnie i znakowanej fizycznie:


W modelu PIPT musieliśmy wykonać sekwencyjny dostęp.
Najpierw do TLB, stamtąd wziać adres fizyczny, z niego odczytać bity tagu i indeksu i dopiero szukać adresu w cachu.

W modelu VIPT (z obrazka) mamy indeksowanie adresami wirtualnymi. Dzięki temu możemy wydłubać tag z cachu, równolegle uzyskując adres fizyczny z TLB i na końcu porównać czy tag adresu z tlb zgadza się z tagiem adresu który znaleźliśmy w cachu. Dzięki temu zyskujemy czas, bo zrównoleglamy sekwencyjne czynności.

## Zadanie 7
:::info
Autor: Łukasz Orawiec
:::

Każdy proces ma swoją własną wirtualną przestrzeń adresową, więc w momencie zmiany aktualnie wykonywanego procesu konieczne jest **przełączenie przestrzeni adresowej**.

Gdyby nowy proces korzystał z TLB poprzedniego procesu, to wirtualne adresy z nowej przestrzeni mogłyby być tłumaczone na adresy fizyczne należące do poprzedniego procesu.

Czyszczenie TLB sprawia, że po każdym przełączeniu przestrzeni adresowej translacje adresów wiążą się z chybieniami w TLB.

Problem ten mogą rozwiązać **identyfikatory przestrzeni adresowych**. Taki identyfikator stanowi część wpisu w TLB i jednoznacznie identyfikuje proces, do którego należy ten wpis. W przypadku, gdy inny proces się do niego odwoła, to będzie to traktowane jako chybienie w TLB. Dzięki temu każdy proces nadpisuje tyle wpisów w TLB ile rzeczywiście potrzebuje, nie likwidując wszystkich innych.

## Zadanie 8
:::info
Autor: Łukasz Pluta
:::

Używamy shchematu pamięci podręcznej indeksowanej i znakowanej adresami wirtualnymi.

problem homonimów - ten sam adres wirtualny może odnosić się do różnych adresów fizycznych (w różnych procesach może być ten sam adres wirutalny), więc kiedy odwołamy się do pamięci to nie będziemy wiedzieć skąd pobrać dane

problem synonimów - różne adresy wirtualne mogą wskazywać na jeden adres fizyczny, modyfikacja danych może zmienić tylko niektóre miejsca w cachu (ale nie wszystkie) i wtedy utracimy spójność danych