# SyK lista 10
## **Zadanie 1**

Przy klasycznym użyciu pamięci mamy większą różnorodność na mniej znaczących bitach adresu. Chcemy zapewnić jak największą różnorodność indeksów aby nasz program mógł zapisywać w wielu miejscach pamięci podręcznej. Tym samym możemy w pełni wykorzystać przekazany programiście potencjał. WPP nasz program ograniczyłby się do używania ułamka dostępnej przestrzeni pamięci podręcznej, co doprowadziłoby do większej ilości chybień, co negatywnie wpłynęłoby na współczynnik CPI.

## **Zadanie 3** (ASK Z2L12)
Wzorując się na slajdach do wykładu „Virtual Memory Systems” (strony 10–21) powtórz proces translacji adresów i adresowania pamięci podręcznej dla adresów: 0x027c, 0x03a9 i 0x0040 zakładając poniższy stan TLB, pamięci podręcznej i tablicy stron.

TLB:

Pamięc fizyczna:

Tablica stron:

### a) 0x027c = $00001001111100_2$

| TLBT(ag) | TLBI(ndex) | Offset |
| -------- |:---------- | ------- |
| 00 0010 | 01 | 11 1100 |

VPN - $00001001_2$ = 0x09
VPO - $111100_2$ = 0x3C
TLBI - $01_2$ = 0x1 (set)
TLBT - $000010_2$ = 0x02 (tag)
TLB Hit? Nie (Miss)
PPN - 0x17 (na bazie odczytu tablicy stron) = 23~10~
Physical adress - $10111 111100_2$

| CT(ag) | CI(ndex) | CO(ffset) |
| ------- |:-------- | --------- |
| 01 0111 | 1111 | 00 |

CO - $00_2$ = 0x0 (offset - który bajt)
CI - $1111_2$ = 0xF (indeks)
CT - $10111_2$ = 0x17 (tag)
MISS

### b) 0x03a9 = $00001110101001_2$

| TLBT(ag) | TLBI(ndex) | Offset |
| -------- |:---------- | ------- |
| 00 0011 | 10 | 10 1001 |

VPN - $00001110_2$ = 0x0E
VPO - $101001_2$ = 0x29
TLBI - $10_2$ = 0x2
TLBT - $000011_2$ = 0x03
TLB Hit? N
Page Fault? N
PPN - 0x11
Physical adress - $10001 101001_2$

| CT(ag) | CI(ndex) | CO(ffset) |
| ------- |:-------- | --------- |
| 01 0001 | 1010 | 01 |

CO - $01_2$ = 0x1
CI - $1010_2$ = 0xA
CT - $10001_2$ = 0x11
MISS

### c) 0x0040
0x0040 = $00000001000000_2$

| TLBT(ag) | TLBI(ndex) | Offset |
| -------- |:---------- | ------- |
| 00 0000 | 01 | 00 0000 |

VPN - $000000001_2$ = 0x01
VPO - $000000_2$ = 0x00
TLBI - $01_2$ = 0x1
TLBT - $0000000_2$ = 0x00
TLB Hit? N
Page Fault? Y

## **Zadanie 4** (ASK Z3L12)


4KiB = 4096B
$2^{\text{page.offset.bits}}=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? | Segfault |
| ---- | -------------- | -------- | --------- | ------------------ |
| 0001 | 0010 0011 1101 | nie | nie | nie, tylko swap-in |

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

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

---

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

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

| Valid? | Tag | LRU | PPN |
| ------ | --- | --- |:--------------- |
| 1 | 11 | 2 | 12 |
| 1 | 7 | 3 | 4 |
| 1 | 0 | 0 | 5 (nadpisujemy) |
| 1 | 1 | 1 | 13 |

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

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

| Valid? | Tag | LRU | PPN |
| ------ | --- | --- |:--- |
| 1 | 11 | 3 | 12 |
| 1 | 3 | 0 | 6 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 2 | 13 |

---
Krok 4
| VPN | VPO | TLB hit? | Page hit? | Segfault |
| ---- | -------------- | -------- | ---------- | ------------------ |
| 1000 | 0111 0001 1011 | nie | nie | nie, tylko swap-in |

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

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

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

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

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

---
Krok 6

| VPN | VPO | TLB hit? | Page hit? | Segfault |
| ---- | -------------- | -------- | ---------- | ------------------ |
| 0011 | 0001 0100 0000 | tak | n/d | nie |

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

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

---
Krok 7

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

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

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

---

Wynik:

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

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

## **Zadanie 5** (ASK Z4L12)
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) dwupioziomowej, gdzie katalog tablicy stron (czyli tablica stron pierwszego poziomu) ma 1024 wpisy. Dla drugiego przypadku – jaki jest maksymalny i minimalny rozmiar tablicy stron?

32-bitowe adresy wirtualne -> max adres $2^{32}$
rozmiar strony $4KiB = 2^{12}B$
rozmiar wpisu $4=2^{2}B$ bajty
przestrzeń adresowa 1GiB = $2^{30}B$ = $1024^{3}B$
a) $\frac{2^{32}*2^{2}}{2^{12}}=2^{22}B = 4MiB$
b) 12 bitów na offset -> na pierwszą i drugą tablicę jest po 10 bitów
$\frac{2^{30}}{2^{10}*2^{12}}= 2^{8}$ tablic II poziomu
minimalny rozmiar tablicy stron:
poziom II: $2^{8}*2^{10}*2^{2} = 2^{20}B = 1 MiB$
poziom I: $2^{10}*2^{2} = 2^{12} = 4 KiB$
1MiB + 4 KiB
maksymalny rozmiar tablicy stron:
wszystkie tablice w drugim poziomie są używane
poziom II: $2^{10}*2^{10}*2^{2} = 2^{22}B = 4 MiB$
poziom I: $2^{10}*2^{2} = 2^{12} = 4 KiB$
4MiB + 4 KiB

Z ASKa
#### Jednopoziomowa

Po prostu odcinamy od adresu bity potrzebne na offset i mnożymy ilość wpisów przez ich rozmiar.
$2^{32}/2^{12}*2^{2}=2^{22} = 4MiB$

#### Dwupoziomowa
Ilość wpisów w sumie (w tablicach drugiego poziomu): $2^{32}/2^{12}=2^{20}$
Ilość wpisów dla jednej tablicy poziomu 2: $2^{20} / 1024= 2^{10}$

Ilość tablic drugiego poziomu: 1024

Wielkość wpisów w 1GiB przestrzeni adresowwej: $2^{18}$

##### Maksymalny
Mamy 1024 wpisy w katalogu tablic, czyli $2^{10}$
Zakładając, że układamy wpisy w kolejnych tablicach stron w katalogu, sumujemy rozmiar katalogu z rozmiarem zapełnionych katalogów, czyli (2^{10} + 2^{10}*2^{10}) razy rozmiar jednego wpisu.
Finalnie otrzymujemy działanie $(2^{10} + 2^{10}*2^{10}) * 4B = 4KiB + 4MiB$

##### Minimalny
Bierzemy ponownie rozmiar samych wpisów katalogu: $2^{10} = 4KiB$
W tym przypadku zakładamy, że są wypełnione w najoptymalniejszy spobób. Więc wszystkie zmieszczą się w $2^8$ wpisach w katalogu.
Otrzymujemy wzór $4KiB + 2^{8}*4KiB = 4KiB + 1MiB$

---
---
---
### whiskey
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) dwupioziomowej, gdzie katalog tablicy stron ma 1024 wpisy. Dla drugiego przypadku – jaki jest maksymalny i minimalny rozmiar tablicy stron?

Na sam początek pokażę różnicę w organizacji tabeli stron jedno i dwupoziomowych. Załóżmy, że pracujemy na 8-bitowych wirtualnych adresach, gdzie po 4 bity przeznaczamy na VPN i VPO:
W tablicy stron jednopoziomowej nie mamy żadnego podziału, a więc nie wiemy który obszar jest używany, a który nie, zajmujemy więc obszar potrzebny na przetrzymanie danych w całej tablicy.

W przypadku tablicy dwupoziomowej, gdy wszystkie komórki na drugim poziomie w jednym bloku są nieużywane, możemy odnotować na pierwszym poziomie (w katalogu stron), że nic się w danej tablicy nie znajduje i jej nie potrzebujemy, dzięki czemu oszczędzamy pamięć.

Zajmiemy się najpierw tablicą stron jednopoziomową. System operuje na 32-bitowych adresach wirtualnych, rozmiar wpisu tablicy stron zajmuje 4 bajty (32 bity), rozmiar strony ma $4\text{ KiB} = 4\cdot1024\text{ b} = 2^2 \cdot 2^{10}\text{ b}$. Liczbę stron w tablicy możemy policzyć wtedy z poniższego wzoru:

$\text{liczba stron w tablicy} = \frac{\text{liczba mozliwosci adresow wirtualnych}}{\text{rozmiar strony}} = \frac{2^{32}}{2^{12}} = 2^{20} \text{ stron}$

Teraz możemy przejść do obliczenia potrzebnej pamięci fizycznej na wszystkie strony:
$\text{potrzebna pamiec} = \text{rozmiar wpisu (w bajtach)} \cdot \text{liczba stron w tablicy} = 4 \cdot 2^{20} = 4\text{ MiB}$

b)
Przejdźmy teraz do dwupoziomowej tablicy stron. Katalog stron ma $1024 = 2^{10}$ wpisy i każdy jego wpis wskazuje na 1024 tablice stron, gdyż łącznie mamy $2^{20} \text{ stron} = 2^{10} \text{ wpisow katalogu} \cdot 2^{10} \text{ tablic stron}$. Proces zużywa 1GiB pamięci i musimy określić maksymalny i minimalny rozmiar tablicy stron.


Teraz przejdźmy do obliczenia minimalnego rozmiaru tablicy.
skoro $\text{1GiB} = 2^{30}\text{B}$, a obecna struktura pozwala na przechowywanie $2^{32}$ adresów, to posiadamy 4 razy za dużo tablic drugiego poziomu. Zatem minimalny rozmiar pamięci to:
$1024 * \text{4B} + 1/4*\text{4MiB} = \text{4KiB} + \text{1MiB}$

## Zadanie 6

:::info
Wyznacz maksymalny rozmiar zbioru roboczego procesu, dla którego nie będzie on generował nowych chybień w TLB (ang. TLB reach)? Rozważ wariant pesymistyczny i optymistyczny dla czterodrożnego TLB o 64 wpisach. Jak zmieni się oszacowanie, jeśli zezwolimy na używanie dużych stron (ang. huge pages) o wielkości 4MiB?

:::

***Zbiór roboczy*** to ta część przydzielonej pamięci adresowej procesu która jest faktycznie wykorzystywana.
skoro TLB jest 4-drożne to w każdym zbiorze znajdują się 4 wpisy tablicy stron, a skoro wszystkich wpisów jest 64 to zbiorów jest $64/4 = 16$.
Strony domyślnie mają po 4KiB.

Optymistyczny warniant to taki, w którym nie mamy żadnych konfliktów i każdy wpis jest używany. Skoro używalibyśmy wszystkich 64 wpisów, a każda strona ma po 4KiB to mamy łącznie $64*4KiB = 256KiB$
Pesymistyczny wariant to taki, w którym wszystko trafiło do jednego zbioru wtedy mamy tylko 4 wpisy, czyli $4*4KiB = 16KiB$

Dla dużych stron strony zamiast 4KiB mają 4MiB
W przypadku optymistycznym mamy
$64*4MiB = 256MiB$
w Pesymistycznym
$4*4MiB = 16MiB$

## **Zadanie 7**
Zdefiniuj format czteropoziomowej tablicy stron zaimplementowany w procesorach architektury x86-64. W jaki sposób tłumaczone są adresy wirtualne na fizyczne? Jaką przewagę ma taka taka tablica nad tablicą jednopoziomową? Opisz dokładnie format pola w tablicach każdego poziomu i wyjaśnij znaczenie bitów pomocniczych.

*Wskazówka: Przeczytaj rodział 7.9.1 z podręcznika CSAPP3e. Szczegóły można znaleźć w rodziale 4.5 wolumenu 3 dokumentacji procesorów Intel.*




Figure 9.23 shows the format of an entry in a level 1, level 2, or level 3 page table. When P = 1 (which is always the case with Linux), the address field contains a 40-bit physical page number (PPN) that points to the beginning of the appropriate page table. Notice that this imposes a 4 KB alignment requirement on page tables.
Figure 9.24 shows the format of an entry in a level 4 page table. When P = 1, the address field contains a 40-bit PPN that points to the base of some page in physical memory. Again, this imposes a 4 KB alignment requirement on physical pages.


Figure 9.25 shows how the Core i7 MMU uses the four levels of page tables to translate a virtual address to a physical address. The 36-bit VPN is partitioned into four 9-bit chunks, each of which is used as an offset into a page table. The CR3 register contains the physical address of the L1 page table. VPN1 provides an offset to an L1 PTE, which contains the base address of the L2 page table. VPN2 provides an offset to an L2 PTE, and so on.

## **Zadanie 8** (ASK Z8L12)
Na wykładzie przyjęliśmy, że translacja adresów jest wykonywana przed dostępem do pamięci podręcznej. Taki schemat określa się mianem pamięci podręcznej **indeksowanej** i **znakowanej adresami fizycznymi** (ang. physically-indexed, physically-tagged). Wyjaśnij jak zrównoleglić dostęp do TLB i pamięci podręcznej, stosując schemat pamięci indeksowanej wirtualnie i znakowanej fizycznie.
Wskazówka: Posłuż się slajdem 34 do wykładu „Virtual Memory: Concepts”, ale wytłumacz to szczegółowo!

Z mojego zeszytu z ask:
VPN jest tłumaczony na PPN a VPO = PPO, koszystając z faktu, że CI oraz CO pochodzą tylko z PPO możemy wziąć VPO przed tłumaczeniem i w trakcie tłumaczenia odczytać już odpowiedni set z L1 cache i przygotować go do porównywania z CT, czyli z PPN, który w tym samym czasie jest tłumaczony