# Architektury systemów komputerowych - pamięć operacyjna i dyskowa, pamięć podręczna, pamięć wirtualna

## Lista zadań nr 10
### Zadanie 1
Rozważmy dysk o następujących parametrach: $360$ obrotów na minutę (RPM), $512$ bajtów na sektor, $96$ sektorów na ścieżkę (avg#sectors / track), $110$ ścieżek na powierzchnię.

Procesor czyta z dysku całe sektory. Dysk sygnalizuje dostępność danych zgłaszając przerwanie na każdy przeczytany bajt. Jaki procent czasu procesora będzie zużywała obsługa wejścia-wyjścia, jeśli wykonanie procedury przerwania zajmuje $2.5 \mu s$? Należy zignorować czas wyszukiwania ścieżki i sektora.

Do systemu dodajemy kontroler DMA. Przerwanie będzie generowane tylko raz po wczytaniu sektora do pamięci. Jak zmieniła się zajętość procesora?

Obliczmy średni czas transferu sektora (czyli czas jednego obrotu w ms) ze wzoru:
$$T_{\text{avg transfer}} = \frac{60}{\text{RPM}} \cdot \frac{1}{\text{avg # sectors/track}} \cdot \frac{1000 \text{ms}}{1 \text{min}} \cdot 1000 = \frac{60}{360} \cdot \frac{1}{96} \cdot \underbrace{1000}_{\text{milisek.}} = 1.736ms$$

Skoro co bajt następuje przerwanie trwające $2.5 \mu s$, to łączny czas przerwań wyniesie:
$$512 \cdot 2.5\mu s = 0.00128 s = 1.28 ms$$

Procesor chcąc wczytać sektor danych z dysku musi więc poczekać $1.736 ms$, aby dysk wczytał te dane (pomijając wyszukiwanie sektora i ścieżki), dodatkowo musi przetworzyć wszystkie przerwania trwające łącznie $1.28 ms$. Obsługa wejścia-wyjścia zajmuje więc
$$\frac{\text{czas przerwań}}{\text{czas transferu}} \cdot 100\% = 100\% \cdot \frac{1.28}{1.736} = 73.7\%$$
czasu procesora. Gdy dodamy do systemu kontroler DMA, to przerwanie będzie generowane tylko raz po wczytaniu sektora, a więc będzie zajmowało $2.5 \mu s = 0.0025 ms$. Wtedy obsługa wejścia-wyjścia zajmie
$$\frac{\text{czas przerwań}}{\text{czas transferu}} \cdot 100\% = 100\% \cdot \frac{0.0025}{1.736} = 0.144 \% $$

### Zadanie 2
Moduł DMA kontrolera dysku do transferu danych używa techniki podkradania cykli. $32$-bitowa szyna ma przepustowość $10$ milionów transferów na sekundę. Procesor RISC bez pamięci podręcznej wykonuje $32$-bitowe instrukcje, z których $40\%$ to dostępy do pamięci. O ile procent zmieni się liczba wykonywanych instrukcji w wyniku aktywności modułu DMA, jeśli transferujemy z dysku dane z prędkością $2\text{MB/s}$.

**DMA** (Direct Memory Access) to kontroler umożliwiający niezależne działanie procesora, odciążający go (np. poprzez kopiowanie danych) aby procesor nie wykonywał zbędnych działań, jako że nie ma to za bardzo sensu - procesory są stworzone do bardziej skomplikowanych operacji.

**Podkradanie cykli** polega na tym, że jeśli procesor i DMA chciałyby korzystać z szyny pamięci w tym samym czasie, to DMA ma zawsze większy priorytet i procesor w danym cyklu pamięci będzie przetrzymywany, dopóki szyna się nie zwolni.

Mamy do czynienia z $32$-bitową (a więc $4$-bajtową) szyną o przepustowości $10$ milionów transferów na sekundę, odpowiada to więc transferowi $40\text{MB/s}$. Bez DMA procesor musi wykonać wszystkie instrukcje, a więc będzie ich $10$ milionów. Zgodnie z powyższym opisem DMA, może on odciążyć procesor, dzięki czemu nie będzie wykonywał on wszystkich instrukcji. Skoro DMA zajmie $2\text{MB}$ z $40\text{MB}$ transferu procesora, to pozostałe $38\text{MB}$ będzie do dyspozycji procesora na instrukcje nieoperujące na pamięci. Stąd możemy policzyć, że liczba wykonywanych instruckji zmniejszy się o:
$$\frac{10^7-9.5\cdot 10^6}{10^7} = \frac{5\cdot10^5}{10^7} = 5\%$$

Spójrzmy teraz na instrukcje, które nie są przypisaniem pamięci - bez DMA wykona się ich $10^7 \cdot (100-40)\% = 6\cdot 10^6$, a z DMA (mając już załatwione dostępy do pamięci) resztę instrukcji wykorzystamy jako instrukcje niebędące dostępami do pamięci.

### Zadanie 3
Nowoczesny procesor `x86-64` (np. i7-6700) ma następujące czasy dostępu do poszczególnych poziomów pamięci: L1 cache: $4$ cykle; L2 cache: $12$ cykli; L3 cache: $40$ cykli; pamięć DRAM: $200$ cykli. Jaki jest średni czas dostępu do pamięci, jeśli $90\%$ dostępów trafia w cache L1, $95\%$ w cache L2, $98\%$ w cache L3? Jaki jest pesymistyczny czas dostępu do pamięci?

W tym rozwiązaniu zakładamy, że czasy dostępu nie są kumulatywne, a więc czas dostępu np. do L3 zajmie $4+12+40 = 56$ cykli:
**[Średni czas dostępu do pamięci (AMAT)](https://en.wikipedia.org/wiki/Average_memory_access_time)** możemy policzyć w sposób przedstawiony w powyższym linku:
$$AMAT = H_1 + MR \cdot AMP_1, \text{ gdzie } AMP_1 = H_2 + MR_2 \cdot AMP_2$$

$$AMAT = 0.9 \cdot 4 + (1-0.9)\cdot 0.95 \cdot (12+4) + (1-0.9) \cdot (1-0.95) \cdot 0.98 \cdot (40 + 12 + 4) +\\
(1-0.9) \cdot (1-0.95) \cdot (1 - 0.98) \cdot 1 \cdot (200 + 40 + 12 + 4) \approx 5.42 \text{ cykli}$$

Pesymistyczny czas możemy łatwo policzyć sumując ilość wszystkich cykli na poszczególnych poziomach pamięci, a więc jest to $4+12+40+200=256$ cykli.

W drugim rozwiązaniu przyjmujemy, że czasy dostępu są kumulatywne (co zgadza się z dokumentacją intela):
$$AMAT=\frac{4\cdot 90+12 \cdot 9.5+40\cdot 0.49+0.01 \cdot 200}{100}=4.956\text{ cykli}$$

### Zadanie 4
Zreferuj protokół komunikacji kontrolera pamięci z modułami pamięci DRAM. Wyjaśnij jakie kroki musi podjąć kontroler by odczytać jedną lub kilka kolejnych komórek pamięci. Wyjaśnij źródło opóźnień $t_{CAS}$ (CL), $t_{RCD}$, $t_{RP}$, $t_{RAS}$ ograniczających wydajność operacji.

Program wybiera lokalizację pamięci używając wirtualnego adresu, a procesor tłumaczy go na adres fizyczny, a na samym końcu kontroler pamięci wybiera odpowiedni chip pamięci RAM odpowiadający temu adresowi. W celu wybrania pojedynczej komórki pamięci RAM na chipie, części adresu fizycznego są przekazywane w formie numerów linii adresu.

Odczyt danych z pamięci DRAM ([jakis polski opis (lekko sie rozni od pdfa)](http://cygnus.tele.pw.edu.pl/olek/doc/syko/www/rozdzial4_3_2.html)):
1. Cykl odczytu rozpoczyna się poprzez sprawienie przez kontroler pamięci, że adres wiersza jest dostępny na szynie adresowej i zmniejszeniu sygnału RAS. Wszystkie sygnały są czytane przy wzroście sygnału na zegarze CLK, a więc nie ma to znaczenia, czy sygnał jest całkowicie kwadratowy, dopóki jest on stabilny w czasie odczytu. Ustawienie adresu wiersza powoduje, że chip RAMu zaczyna zamykać ten wiersz.
2. Sygnał CAS wysyłany jest po czasie cyklu $t_{RCD}$. Adres kolumny jest przekazywany poprzez udostępnienie go na szynie adaresowej i zmniejszeniu sygnału CAS. Na rysunku widać w jaki sposób dwie części adresu mogą być wysyłane przez tę samą szynę adresową.
3. Adresowanie kończy się i dane mogą być przesyłane. Chip RAMu musi jednak się do tego "przygotować" - opóźnienie to nazywa się zwykle $t_{CAS}$ lub CL (na rysunku opóźnienie $t_{CAS} = 2$), różni się ono w zależności od jakości kontrolera pamięci, płyty głównej i samego modułu DRAM, może przyjmować również wartości połówkowe.
4. Moduł DRAM umożliwia wysyłanie większej ilości informacji, zwykle jest to 2, 4 albo 8 słów. Umożliwia to uzupełnienie całej pamięci podręcznej bez konieczności powtarzania kroków 1-3, jest również możliwe wysłanie sygnału CAS bez przestawiania aktualnego wiersza. Wtedy odczyty pamięci są znacznie szybsze, ponieważ sygnał RAS nie musi być co chwile wysyłany, a wiersz dezaktywowany.

Źródło opóźnień:
- $t_{CAS}$ (CL, Column Access Strobe Latency - wczytanie komórki): oczekiwanie między wysłaniem przez kontroler pamięci RAM żądania dostępu do określonej kolumny pamięci a otrzymaniem danych z tej kolumny przez kontroler,
- $t_{RCD}$ (Row-to-Column command Delay - przygotowanie kolumny): czas od zakończenia wykonywania polecenia aktywacji konkretnej kolumny ($t_{CAS}$) do rozpoczęcia wykonywania polecenia aktywacji konkretnego wiersza ($t_{RAS}$),
- $t_{RP}$ (Row Precharge - przygotowanie wiersza): czas między wykonaniem polecenia zamknięcia dostępu do wcześniej aktywowanego wiersza a rozpoczęciem wykonywania polecenia aktywacji kolejnego
- $t_{RAS}$ (Row Access Strobe): czas między żądaniem wykonania polecenia aktywacji wiersza aż do jego dezaktywacji

### Zadanie 5
Blok pamięci podręcznej procesorów `x86-64` ma $64$ bajty. Dla uproszczenia przyjmijmy, że w jednym cyklu zegarowym między pamięcią a procesorem można przesłać $64$ bity danych. Ile nanosekund, w pesymistycznym przypadku, zajmie sprowadzenie bloku pamięci podręcznej z pamięci DRAM dla poniżej scharakteryzowanych modułów:
- `DDR4-1600`, $t_{CLK} = 800$ MHz, $t_{CAS} = 10$, $t_{RCD} = 10$, $t_{RP} = 10$, $t_{RAS} = 25$,
- `DDR4-2133`, $t_{CLK} = 1066.67$ MHz, $t_{CAS} = 15$, $t_{RCD} = 15$, $t_{RP} = 15$, $t_{RAS} = 36$.

Powtórz obliczenia zakładając, że pamięć działa w trybie sekwencyjnym (ang. *burst mode*), tj. podaje na kolejnych zboczach zegara szesnaście $64$-bitowych słów bez czekania na polecenie zmiany kolumny.

Wiemy, że jeden blok ma $64$ bajty, a w trakcie jednego cyklu można przesłać $64$ bity, czyli jedno słowo. My jednak przesyłać będziemy $8$ słów, jako że pracujemy na pamięciach `DDR4`.

Przygotowanie wiersza zajmie czas $t_{RP}$, a więc musimy wybrać kolumnę, a następnie wczytać ją do specjalnego wiersza. Wczytanie wiersza zajmie czas $t_{RP} + t_{RCD}$, jako że najpierw musimy wyszukać wiersz, a następnie znaleźć szukaną komórkę w tym wierszu. Kolejnym krokiem jest wczytanie tej komórki, a więc ustawiany jest na niej wskaźnik i w razie odczytywania danych z kolejnych komórek, dodajemy czas $t_{CAS}$.

W pesymistycznym przypadku liczba cykli (odpowiednio dla `DDR4-1600` i `DDR4-2133`) wyniesie:
$$c_1 = t_{RP} + t_{RCD} + 8(t_{CAS} + 1) = 108 \\
c_2 = t_{RP} + t_{RCD} + 8(t_{CAS} + 1) = 150$$

Obliczmy więc czas wykorzystując obliczoną liczbę cykli i znane nam taktowanie:
$$ t_1 = \frac{c_1}{t_{CLK}} = \frac{108}{800\text{MHz}} = 135 \mu s \\
t_2 = \frac{c_2}{t_{CLK}} = \frac{150}{1066.67\text{MHz}} = 141 \mu s$$

Powtórzone obliczenia dla pamięci działającej w trybie sekwencyjnym, a więc wiersz jest wyszukiwany tylko raz, a następne komórki czytamy sekwencyjnie:
$$c_1 = t_{RP} + t_{RCD} + t_{CAS} + 8 = 38 \\
c_2 = t_{RP} + t_{RCD} + t_{CAS} + 8 = 53$$

Taktowanie nie ulega zmianie, korzystamy więc z tych samych wzorów:
$$ t_1 = \frac{c_1}{t_{CLK}} = \frac{38}{800\text{MHz}} = 47.5 \mu s \\
t_2 = \frac{c_2}{t_{CLK}} = \frac{53}{1066.67\text{MHz}} = 49.7 \mu s$$

### Zadanie 6
Program czyta sekwencyjnie jednowymiarową tablicę o rozmiarze $4\text{GiB}$ położoną pod adresem podzielnym przez $2^{20}$. W komputerze zainstalowano dwa moduły pamięci `DDR4-2133` o parametrach: $t_{CAS} = 15$, $t_{RCD} = 15$, $t_{RP} = 15$, $t_{RAS} = 36$, maksymalny rozmiar transferu sekwencyjnego to $16$ słów, długość wiersza (ang. DRAM page size) wynosi $8\text{KiB}$. Ile czasu zajmie sprowadzenie danych do procesora? Należy pominąć rozważanie opóźnień wynikających z działania pamięci podręcznej i kontrolera pamięci. Powtórz obliczenia dla systemu dysponującego pamięcią w konfiguracji dwukanałowej (ang. dual-channel).

Wiemy, że cała tablica zajmuje $4\text{GiB} = 2^{32} \text{ bajtów}$. Tablica będzie miała wymiary $2^{19} \text{ wierszy} \times 2^{13} \text{ kolumn}$. W jednym momencie możemy przeczytać $16$ słów, co odpowiada $2^7$ bajtom, a na cały wiersz składa się $8\text{KiB} = 2^{13}\text{bajtów}$. To znaczy, że przeczytanie jednego wiersza to $2^6$ burstów.
$$c_b=\frac{\text{cykle}}{\text{burst}}=t_{CAS}+16 = 31 \text{ cykle}$$
$$c_w=\frac{\text{cykle}}{\text{wiersz}}=t_{RP}+t_{RCD}+2^{6}c_b = 2014$$
$$t=\frac{2^{19}2014}{1066.67\text{MHz}}=0.989s$$

Powtarzamy obliczenia dla dual-channel. To znaczy, że szerokość naszej magistrali wynosi teraz 128bitów. Nasza tablica będzie miała zatem $2^{18} \text{ wierszy} \times 2^{13} \text{ kolumn}$.
Na raz czytamy $32$ słów, czyli $2^8$ bajtów. Przeczytanie jednego wiersza to $2^5$ burstów.

$$c_b'=t_{CAS}+32=47 \\
c_w'=t_{RP}+t_{RCD}+2^{5}47=1534 \\
t'=\frac{2^{18}1534}{1066.67\text{MHz}}=0.376s$$

### Zadanie 7
Nagraj na przenośny dysk USB program `memtest86` i uruchom go z poziomu wbudowanego oprogramowania UEFI. Podaj parametry systemu pamięci w swoim komputerze. Jaka jest przepustowość poszczególnych poziomów pamięci podręcznej i pamięci DRAM? Oszacuj, w taktach procesora, średni czas dostępu do pamięci podręcznej L1, L2, L3 i pamięci DRAM.

Uzyskane wyniki po przeprowadzeniu testu są następujące:

CPU Clk:  4214MHz
L1 Cache:     64K 287079 MB/s
L2 Cache:    256K 125040 MB/s
L3 Cache:   8192K  72964 MB/s
Memory:       16G  21119 MB/s

## Lista zadań nr 11
### Zadanie 1
Rozważmy **pamięć podręczną z mapowaniem bezpośrednim** (definicja jest wyżej w bloku z teorią) adresowaną bajtowo. Używamy adresów $32$-bitowych w następującym formacie:
$$(\text{tag, index, offset}) = (\text{addr}_{31...10}, \text{addr}_{9...5}, \text{addr}_{4...0})$$
* Jaki jest rozmiar bloku w $32$-bitowych słowach?
* Ile wierszy ma nasza pamięć podręczna?
* Jaki jest stosunek liczby bitów składujących dane do liczby bitów składujących metadane?

Offset zapisywany jest na $5$ bitach, a więc jego maksymalna wartość (pamiętając, że offset jest zawsze `unsigned int`) to $11111_{2} = 31$. Stąd mamy, że blok ma $32$ bajty, a więc zmieści się 8 $32$-bitowych słów.

W pamięci podręcznej z mapowaniem bezpośrednim mamy tyle samo zbiorów co wierszy/linii, a więc musimy spojrzeć na bity $\text{index}$. Jest ich $5$, podobnie jak przy bitach przesunięcia, a więc są $32$ różne możliwości, stąd mamy $32$ wiersze w pamięci podręcznej.

Przechowujemy dane w $8 \cdot 32 = 256$ bitach, a metadane zajmują kolejno $22$ bity na tag oraz $1$ valid bit. Mamy więc stosunek $\frac{256}{23} = 11.13$.

### Zadanie 2
Mamy system z pamięcią operacyjną adresowaną bajtowo. Szerokość szyny adresowej wynosi $12$. Pamięć podręczna ma organizację sekcyjno-skojarzeniową o dwuelementowych zbiorach, a blok ma $4$ bajty. Dla podanego niżej stanu pamięci podręcznej wyznacz, które bity adresu wyznaczają: offset, indeks, znacznik. Wszystkie wartości numeryczne podano w hex.
Określ, które z poniższych operacji wygenerują **trafienie** albo **chybienie** i ew. jakie wartości wczytają:

Pracujemy na systemie z sekcyjno-skojarzeniową pamięcią podręczną, w której każdy zbiór ma $2$ wiersze, a blok $4$ bajty. Szerokość szyny adresowej wynosi $12$ bitów.

Na podstawie tabelki z określonym stanem pamięci podręcznej mamy określić które bity adresu wyznaczają offset, indeks oraz tag. Skoro blok zajmuje $4$ bajty, to $B = 4 = 2^b \Rightarrow b = 2$, to offset będzie na bitach $a_1, a_0$. Indeksy w naszej pamięci są z zakresu od $0$ do $3$, a więc można je przedstawić na dwóch bitach, stąd będą to bity $a_3, a_2$. Pozostałe bity będą zarezerwowane na tag. Przedstawia to tabelka poniżej:

| $a_{11}$ | $a_{10}$ | $a_9$ | $a_8$ | $a_7$ | $a_6$ | $a_5$ | $a_4$ | $a_3$ | $a_2$ | $a_1$ | $a_0$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| t | t | t | t | t | t | t | t | i | i | o | o |

Kolejnym zadaniem jest określenie czy operacja na danym adresie wygeneruje trafienie lub chybienie. Najłatwiej jest to sprawdzić zmieniając adresy (a dokładniej ostatnią cyfrę) na system binarny, a następnie dopasować dane do tych, które znajdują się w tabelce.

Znacznik `83` pokrywa się w pierwszych dwóch adresach, musimy więc sprawdzić wartość ostatniej cyfry w systemie szesnastkowym. W pierwszym przypadku $2_{16} = 0010_{2}$, a więc sprawdzamy pierwszy zbiór (o indeksie $0$), a następnie wybieramy blok z przesunięciem $10_{2}$, czyli B2. Otrzymujemy wartość `0xCC`. Drugi adres jest w zbiorze o indeksie $1$, jednak nie ma tam żadnej wartości, więc chybimy. Ostatnim adresem jest `0xFFD`, jest to zbiór o indeksie $3$, znaczniku `0xFF` i przesunięciu $01_{2}$ (blok B1), a więc trafiamy w wartość `0xC0`.

| Adres HEX | Adres BIN | Trafienie? | Wartość |
|:---------:|:----------------:|:----------:|:-------:|
| `0x832` | `1000 0011 0010` | Tak | `0xCC` |
| `0x835` | `1000 0011 0101` | Nie | $-$ |
| `0xFFD` | `1111 1111 1101` | Tak | `0xC0` |

### Zadanie 3
Rozważmy pamięć podręczną z poprzedniego zadania. Mamy następującą sekwencję odwołań do czterobajtowych słów pamięci o adresach zadanych liczbami w systemie szesnastkowym:

      0x000 0x004 0x010 0x084 0x0E8 0x0A0 0x400 0x01C 0x08C 0xC1C 0x0B4 0x884

Załóż, że na początku pamięć podręczna jest pusta. Jak wiele bloków zostało **zastąpionych**? Jaka jest efektywność pamięci podręcznej (liczba trafień procentowo)? Podaj zawartość pamięci podręcznej po wykonaniu powyższych odwołań – każdy ważny wpis wypisz jako krotkę $\text{(tag, index, ...)}$. Dla każdego chybienia wskaż, czy jest ono przymusowe *(ang. **compulsory miss**)*, czy wynika z kolizji na danym adresie *(ang. **conflict miss**)* czy ograniczonej pojemności *(ang. **capacity miss**)*.

Blok zostaje **zastąpiony** gdy dochodzi do chybienia, wtedy kontroler pamięci podręcznej musi wybrać blok, który zostanie zastąpiony nowymi danymi. W rozwiązaniu zastąpienie bloku występuje na dwa możliwe sposoby: przy pierwszym zapisie zastępywany jest pusty blok, a przy kolejnych zapisach ten, który był używany najdawniej (LRU), stąd w naszej pamięci wszystkie bloki zostały zastąpione i wskaźnik trafień wynosi $0\%$.

Dane możemy sobie lekko sparsować, wyciągając wszystkie potrzebne dane, a więc znacznik, indeks zbioru i przesunięcie, i na podstawie tego będziemy mogli wszystko wywnioskować:

| # | Adres | Tag | Set | Offset | Krotki | Trafienie? | Zastąpiony? |
|:---:|:-------:|:----:|:---:|:------:|:------------:|:----------:|:-----------:|
| 1 | `0x000` | `00` | `0` | `0` | `(00, 0, 0)` | compulsory miss | tak |
| 2 | `0x004` | `00` | `1` | `0` | `(00, 1, 0)` | compulsory miss | tak |
| 3 | `0x010` | `01` | `0` | `0` | `(01, 0, 0)` | compulsory miss | tak |
| 4 | `0x084` | `08` | `1` | `0` | `(08, 1, 0)` | compulsory miss | tak |
| 5 | `0x0E8` | `0E` | `2` | `0` | `(0E, 2, 0)` | compulsory miss | tak |
| 6 | `0x0A0` | `0A` | `0` | `0` | `(0A, 0, 0)` | conflict miss | tak |
| 7 | `0x400` | `40` | `0` | `0` | `(40, 0, 0)` | conflict miss | tak |
| 8 | `0x01C` | `01` | `3` | `0` | `(01, 3, 0)` | compulsory miss | tak |
| 9 | `0x09C` | `09` | `3` | `0` | `(09, 3, 0)` | compulsory miss | tak |
| 10 | `0xC1C` | `C1` | `3` | `0` | `(C1, 3, 0)` | conflict miss | tak |
| 11 | `0x0B4` | `0B` | `1` | `0` | `(0B, 1, 0)` | conflict miss | tak |
| 12 | `0x884` | `88` | `1` | `0` | `(88, 1, 0)` | conflict miss | tak |

Korzystając z polityki wymiany LRU dla przeprowadzonych dostępów do pamięci możemy określić zawartość pamięci podręcznej po wykonaniu powyższych odwołań:


### Zadanie 4
Powtórz poprzednie zadanie dla poniższych organizacji pamięci podręcznej. Zakładamy, że bloki są długości dwóch słów pamięci. Ile dodatkowych bitów na linię pamięci podręcznej potrzeba na implementację określonej **polityki wymiany** *(ang. replacement policy)*:
* sekcyjno-skojarzeniowa $2$-drożna, $16$ bloków, polityka NRU (ang. Not Recently Used)
* w pełni asocjacyjna (ang. fully associative), $8$ bloków, polityka LRU (ang. Least Recently Used).

**Polityka wymiany** to ustalony sposób wyboru bloków w cache'u do zastąpienia

**Not recently used (NRU)** dla każdego zbioru pamiętamy 1 dodatowy bit R - referenced

**Least recently used (LRU)** - wymaga trzymania "age bits" dla każdej linii, minimalnie log z liczby linii silnia w zbiorze

Mamy dwa 4-bajtowe słowa, więc na offset potrzebujemy 3 bity.

| adres (hex) | adres (dec) | NRU | LRU |
|:--------------------:|:----------------:|:---:|:---:|
0| 0000 0000 0000| ComM | ComM|
4| 0000 0000 0100| Hit | Hit|
10| 0000 0001 0000| ComM|ComM|
84| 0000 1000 0100| ComM| ComM|
E8| 0000 1110 1000|ComM|ComM|
A0|0000 1010 0000| ComM| ComM|
400| 0100 0000 0000| ConM| ComM|
1C| 0000 0001 1100| ComM|ComM|
8C| 0000 1000 1100| ComM|ComM|
C1C| 1100 0001 1100| ComM| CapM|
B4| 0000 1011 0100| ComM|CapM|
884|1000 1000 0100| ConM|CapM|

gdzie ComM to chybienie przymusowe, ConM to chybienie z powodu kolicji, a CapM to chybienie z powodu ograniczonej pojemności cache'u. Średnio 8% trafień.

### Zadanie 5
Odpowiedz na następujące pytania dotyczące organizacji pamięci podręcznej:
1. Do wyboru zbioru pamięci podręcznej używamy bitów znajdujących się w środku adresu, zaraz przed offsetem bloku. Czemu jest to lepszy pomysł niż używanie najbardziej znaczących bitów adresu?
2. Zdecydowana większość procesorów posiada odrębną pamięć podręczną pierwszego poziomu dla danych i dla instrukcji. Jakie korzyści to przynosi?

Źródła: [pytanie pierwsze](https://courses.cs.washington.edu/courses/cse351/10sp/sections/section7-ppham-boards.html), [pytanie drugie](https://softwareengineering.stackexchange.com/questions/44731/why-are-there-separate-l1-caches-for-data-and-instructions).

Używane bity do wyboru zbioru (set index bits) są podstawową "restrykcją" mówiącą o tym, gdzie znajdują się dane w pamięci podręcznej. Gdyby te bity były ułożone na najbardziej znaczących bitach adresu, wtedy bardzo rozległe adresy odwoływałyby się do tego samego zbioru, powodując problemy - między innymi przez wiele chybień spadłaby wydajność cache.

Aby odpowiedzieć na drugie pytanie, spójrzmy na hierarchię pamięci procesora Intel Core i7:
Możemy zauważyć, że pamięć podręczna L1 jest podzielona na pamięć przeznaczoną dla danych (d-cache) oraz instrukcji (i-cache). Taki podział powstał ze względu na to, że w ogólności te dwie rzeczy są od siebie różne: cache instrukcji oprócz swoich danych przechowuje również przypisy o np. miejscu rozpoczęcia kolejnej instrukcji.

Kolejnym powodem jest możliwość uproszczenia budowy obwodu, gdyż cache instrukcji tylko odczytuje dane, gdy cache danych może je zapisywać i odczytywać.

Trzecim powodem jest zwiększenie przepustowości. Nowoczesne procesory mogą jednocześnie odczytywać dane z cache'u instrukcji oraz danych, a więc wykonują dwa odczyty i jeden zapis w cyklu.

W procesorach ARM mogą wykorzystywać mniej mocy dzięki temu podziałowi, gdy dany cache nie jest aktualnie wykorzystywany.

### Zadanie 6
Rozważamy system z dwupoziomową pamięcią podręczną z **polityką zapisu** *write back* z *write allocate*. Dodatkowo zakładamy, że blok o określonym adresie może znajdować się tylko na jednym poziomie pamięci podręcznej *(ang. exclusive caches)*. Przy pomocy schematu blokowego przedstaw algorytm obsługi zapisu słowa maszynowego do pamięci. Pierwszym elementem diagramu ma być predykat „Czy słowo jest w L1?”. Pamiętaj o bicie *dirty* i o tym, że pamięć podręczna może być całkowicie wypełniona! Zakładamy, że pamięć podręczna pierwszego poziomu nie może komunikować się bezpośrednio z pamięcią operacyjną.

[Tutaj](http://web.cs.iastate.edu/~prabhu/Tutorial/CACHE/interac.html) jest to troszkę lepiej opisane, tłumaczę tylko najważniejsze rzeczy.
Po trafieniu **polityka zapisu** rozróżnia różne rodzaje designu pamięci podręcznej:
* **write through**, w którym informacja jest zapisywana jednocześnie w pamięci podręcznej i bloku na niższym poziomie. Zaletą tego podejścia jest łatwość implementacji i dostęp do kopii danych w pamięci głównej, niestety zapis jest wolniejszy, każdy z nich musi odwołać się do pamięci głównej i zużywa więcej zasobów.
* **write back**, gdzie informacja jest zapisywana jedynie w jednym bloku pamięci podręcznej. Zmodyfikowany block cache jest zapisywany do pamięci głównej tylko wtedy, gdy jest zastępywany. Aby zmniejszyć częstotliwość zapisów używa się bitu *dirty* mówiącego o tym, czy blok został zmieniony w cache, czy nie. Jeżeli nie, to blok nie jest nadpisywany przy chybieniu. Zaletami tego podejścia są: szybkość zapisu, wielokrotne zapisy w jednym bloku wymagają tylko jednego zapisu w pamięci głównej, jest bardziej oszczędne. Niestety jest trudniejsze do zaimplementowania i odczyty powodujące zastąpienia mogą powodować zapisy bloków *dirty* do pamięci głównej.

W przypadku chybienia mamy również dwie możliwości:
* **write allocate** - blok jest ładowany przy chybieniu, jeśli chcemy coś zapisać i nie ma tego w cache, to dane są pobierane do cache i zapisywane
* **no write allocate** - blok jest modyfikowany w pamięci głównej i nie jest ładowany do pamięci podręcznej (a więc działamy tylko na pamięci głównej)

**Exclusive cache** to określenie na przechowywanie bloku o określonym adresie tylko na jednym poziomie pamięci, a więc mając dane np. w L1, nie przechowujemy ich już w L2.


### Zadanie 7
Załóżmy, że dostęp do pamięci głównej trwa $70ns$, a dostępy do pamięci stanowią $36\%$ wszystkich instrukcji. Rozważmy system z pamięcią podręczną o następującej strukturze: L1 – $2 \text{KiB}$, współczynnik chybień $8.0\%$, czas dostępu $0.66ns$ ($1$ cykl procesora); L2 – $1 \text{MiB}$, współczynnik chybień $0.5\%$, czas dostępu $5.62ns$. Procesor charakteryzuje się współczynnikiem **CPI** *(ang. clocks per instruction)* równym $1.0$, jeśli pominiemy instrukcje robiące dostępy do pamięci danych. Odpowiedz na poniższe pytania:
* Jaki jest średni czas dostepu do pamięci dla procesora: tylko z pamięcią podręczną L1, z L1 i L2?
* Procesor wykonuje wszystkie instrukcje, łącznie z dostępami do pamięci danych. Oblicz jego CPI kiedy posiada: tylko pamięć podręczną L1, z L1 i L2.

*Zakładamy, że wszystkie instrukcje wykonywane przez program są w pamięci podręcznej L1i.*

Średni czas dostępu do procesora tylko z pamięcią podręczną L1:
$$t_{\text{avg}} = \text{wsp. trafien} \times \text{czas L1} + \text{wsp. chybien} \times (\text{czas L1 + czas pamieci glownej}) =\\
= 0.92 \cdot 0.66 ns + 0.08 \cdot (0.66 ns + 70ns) = 6.22 ns = 9.5 \text{ cykli}$$

Średni czas dostępu do procesora z pamięcią podręczną L1 i L2 (wzór analogiczny do powyższego, uwzględniamy jezscze dostęp do L2):
$$t_{\text{avg}} = 0.92 \cdot 0.66ns + 0.08 \cdot 0.995 \cdot (0.66 ns + 5.62 ns) + \\ + 0.8 \cdot 0.005 \cdot (0.66 ns + 5.62 ns + 70 ns) = 1.41 ns = 2.14 \text{ cykli}$$

**CPI** *(ang. clocks per instruction)* to jeden z aspektów określających wydajność procesora, określa on liczbę potrzebnych cykli zegarowych na wykonanie instrukcji.

CPI dla pamięci podręcznej L1:
$$CPI_{L1} = \text{wsp. instrukcji} \times \frac{\text{ilosc cykli}}{\text{instrukcja}} + \text{wsp. dostepow do pamieci} \times t_{\text{avg} (L1)} = \\
= 0.64 \cdot 1 + 0.36 \cdot 9.5 \approx 4.06 \text{ cykli}$$

CPI dla pamięci podręcznej L1 z L2 (wzór identyczny jak wyżej):
$$CPI_{L1 + L2} = 0.64 \cdot 1 + 0.36 \cdot 2.14 \approx 1.41 \text{ cykli}$$

### Zadanie 8
Dla czterodrożnej sekcyjno-skojarzeniowej pamięci podręcznej implementujemy politykę zastępowania LRU. Masz do dyspozycji dodatkowe $\lceil \log_2(4!)\rceil$ bitów na zbiór. Nie można modyfikować zawartości linii w zbiorze, ani zamieniać elementów kolejnością. Jak wyznaczyć kandydata do usunięcia ze zbioru? Jak aktualizować informacje zawarte w dodatkowych bitach przy wykonywaniu dostępów do elementów zbioru?

Zastępowanie LRU(Least Recently Used): jeśli to możliwe to wybieramy linię z bitem `valid = 0`. Jeśli wszystkie linie mają bit `valid = 1`, szukamy lini użytej najdawniej.

Do każdego zbioru możemy dopisać $\lceil \log_2(4!)\rceil = 5$bitów. Zrobimy to na dwa sposoby.

#### 1
5 bitów wykorzystamy na opisanie kolejności dostępów do elementów zbioru. Będziemy opisywać permutacje 4 elemntowego zbioru, więc potrzebujemy $\lceil \log_2(4!)\rceil$ bitów.

Tak wygląda zbiór z dodatkowymi 5 bitami, tzn. bity LRU określają kolejność w jakiej były używane poszczególne wiersze (wartość po lewej użyta najdawniej, wartość po prawej ostatnio - odnosi się do numerów wierszy), bity $v_i$ to bity $\text{valid}$, a pozostałe to bity znacznika i przesunięcia bloku.
| LRU |$v_0$|tag & block|$v_1$|tag & block|$v_2$|tag & block|$v_3$|tag & block|
|:-:|:-:|:--:|:-:|:--:|:-:|:--:|:-:|:--:|
|$b_4b_3b_2b_1b_0$|$v_0$|xxx|$v_1$|xxx|$v_2$|xxx|$v_3$|xxx|

|$b_4b_3b_2b_1b_0$|najstarsza -> najmłodsza|wybór linii|$b_4b_3b_2b_1b_0$|najstarsza -> najmłodsza|wybór linii|
|:--:|:--:|:--:|:--:|:--:|:--:|
|00000|0123|0|01100|2013|2|
|00001|0132|0|01101|2031|2|
|00010|0213|0|01110|2103|2|
|00011|0231|0|01111|2130|2|
|00100|0312|0|10000|2301|2|
|00101|0321|0|10001|2310|2|
|00110|1023|1|10010|3012|3|
|00111|1032|1|10011|3021|3|
|01000|1203|1|10100|3102|3|
|01001|1230|1|10101|3120|3|
|01010|1302|1|10110|3201|3|
|01011|1320|1|10111|3210|3|

Aktualizowanie tych bitów powinno odbywać się w hardware w następujący sposób:
* W razie zapisu: wpisujemy dane do wierszy w kolejności $w_1, w_2, w_3, w_4$ gdzie numery wierszy $w_i \in \{ 0, 1, 2, 3 \}$, oczywiście aby wpisać dane najpierw wyszukujemy wierszy z bitami $v_i$ ustawionymi na $0$. Jeżeli wszystkie bity mają bit $v_i$ ustawiony na $1$, to w trakcie wpisywania danych do tych wierszy, powstanie nam jakaś permutacja wierszy, np. $2130$ (kolumna druga i piąta w tabelce). Mówi nam to o tym, że kolejny zapis, zgodnie z polityką LRU, nastąpi do wiersza o indeksie $2$, a sama permutacja wierszy zmieni się na $1302$.
* W razie odczytu danych np. z wiersza $3$, mając kolejność LRU $0132$, "wyjmujemy" trójkę z permutacji i wstawiamy ją na sam koniec, a więc uzyskujemy wtedy permutację $0123$.

#### 2 [Pseudo-LRU](https://www.seas.upenn.edu/~cit595/cit595s10/handouts/LRUreplacementpolicy.pdf)
3 bity wykorzystamy na opisanie najdawniej użytej lini poprzez binary search.

(Tak wygląda zbiór z dodatkowymi 3 bitami)
| LRU |$v_0$|tag & block|$v_1$|tag & block|$v_2$|tag & block|$v_3$|tag & block|
|:-:|:-:|:--:|:-:|:--:|:-:|:--:|:-:|:--:|
|$b_2b_1b_0$|$v_0$|xxx|$v_1$|xxx|$v_2$|xxx|$v_3$|xxx|

graph TD
        B(Czy wszystkie linie są valid?)
        B -->|Tak| D{b2=0?}
        B -->|Nie| C[Użyj którejś z pustych lini]
        D -->|Tak| E{b1=0?} 
        D -->|Nie| F{b0=0?}
        E -->|Tak| G[Linia 0]
        E -->|Nie| H[Linia 1]
        F -->|Tak| I[Linia 2]
        F -->|Nie| J[Linia 3]

Pierwsze 3 bity pozwalają nam zrobic binary search znajdujący najstarszą użytą linie.
|$b_5b_4b_3$|wybrana linia|aktualizacja $b_5b_4b_4$|
|:---:|:---:|:---:|
|00x|0|11_|
|01x|1|10_|
|1x0|2|0_1|
|1x1|3|0_0|
(x- dowolny bit)(_- ten sam bit co wcześniej)

Czyli ogólnie, odpalamy cache wszystkie linie maja bit `valid=0`. Po kolei wybieramy puste linie, kiedy wszystkie bedą już valid następne zastępowania robimy przez binary search.

Kodowanie:
$b_4b_3$ - najstarszy wybrany wiersz
$b_2b_1$ - przed-najstarszy wiersz
$b_0$ - Jeśli najmłodszy wiersz ma indeks większy od kolejnego to 0 wpw 1
|$b_4b_3b_2b_1b_0$|najstarsza -> najmłodsza|wybór lini|$b_4b_3b_2b_1b_0$|najstarsza -> najmłodsza|wybór lini|
|:--:|:--:|:--:|:--:|:--:|:--:|
|00010|0123|0|11000|2013|2|
|00011|0132|0|10001|2031|2|
|00100|0213|0|10010|2103|2|
|00101|0231|0|10011|2130|2|
|00110|0312|0|10110|2301|2|
|00111|0321|0|10111|2310|2|
|01100|1023|1|11010|3012|3|
|01001|1032|1|11101|3021|3|
|01100|1203|1|11010|3102|3|
|01101|1230|1|11011|3120|3|
|01110|1302|1|11100|3201|3|
|01111|1320|1|11101|3210|3|

Aktualizacja:
* Jeśli używamy najmłodszego wiersza nie zmieniamy.
* Jeśli uzywamy kolejnego (2 najmłodszy) negujemy $b_0$
* Jeśli używamy kolejnych (3 lub 4) musimy zdekodować zapis binarny dowiedzieć się o jakich wierszach mówi $b_0$ i na nowy zakodować nowo powstała permutacje.

## Lista zadań nr 12
### Zadanie 1 TODO
Sprzętowa **translacja adresów** umożliwiła systemom operacyjnym wydajną implementację **izolacji procesów**, **stronicowania na żądanie** *(ang.demand paging)*, **wymiany do pamięci drugorzędnej** *(ang. swapping)* i **współdzielenia pamięci**. Jakie korzyści przynosi stosowanie powyższych mechanizmów? Przekonaj prowadzącego i słuchaczy posługując się przykładami. Należy użyć pojęć: **zbiór rezydentny** *(ang. resident set)* i **zbiór roboczy** *(ang. working set)*.

Podstawowa idea **pamięci wirtualnej** polega na przydzieleniu każdemu programowi oddzielnej przestrzeni adresowej. Jest ona podzielona na fragmenty zwane stronami. Każda strona zawiera ciągły zakres adersów. Strony te mapowane są na pamięć fizyczną, ale nie wszystkie strony muszą znajdować się w pamięci fizycznej, aby można było uruchomić program.

**Translacja adresów** to proces "zamiany" adresów wirtualnych na adresy fizyczne.

**Izolacja procesów** polega na odosobnieniu każdy procesu, a więc każdy ma własną pamięć wirtualną, nie mają one dostępu parami do swojej pamięci wirtualnej. Mimo, że procesy myślą, że odwołują się do tej samej pamięci, to translator adresów przypisuje każdemu procesowi inną pamięć rzeczywistą.

**Stronicowanie na żądanie** to metoda zarządzania pamięcią wirtualną. System kopiuje stronę do fizycznej pamięci, tylko gdy jakiś proces robi dostęp do tej strony i nie ma jej aktualnie w pamięci operacyjnej. Po jakimś czasie proces posiada większość potrzebnych stron w pamięci i działa ze stosunkowo niewielką liczbą błędow braku strony.

**Wymiana** to jedno z rozwiązań problemu przeładowania pamięci. Polega ona na załadowaniu określonego procesu w całości, uruchomieniu go przez pewien czas, a następnie umieszczeniu go z powrotem na dysku. Bezczynne procesy zwykle są zapisane na dysku, zatem wtedy, gdy nie działają, w ogóle nie zajmują pamięci, choć niektóre z nich okresowo się budzą w celu wykonania wojej pracy, a następnie ponownie przechodzą w stan uśpienia.

**Współdzielenie pamięci** to specjalnie utworzony segment wirtualnej przestrzeni adresowej, do którego może mieć wiele procesów. Jest to najszybszy sposób komunikacji pomiędzy procesami. Podstawowy schemat korzystania z pamięci współdzielonej wygląda następująco: jeden z procesów tworzy segment pamięci współdzielonej, dowiązuje go powodując jego odwzorowanie w bieżący obszar danych proces, opcjonalnie zapisuje w stworzonym segmencie dane. Następnie, w zależności od praw dostępu inne procesy mogą odczytywać i/lub zapisywać wartości w pamięci współdzielonej. Każdy proces uzyskuje dostęp do pamięci współdzielonej względem miejsca wyznaczoneo przez jego adres dowiązania, stąd każdy proces korzystając z tych samych danych używa innego adresu dowiązania. W przypadku współbieżnie działających procesów konieczne jest najczęściej synchronizowanie dostępu np. za pomocą semaforów. Kończąc korzystanie z segmentu pamięci proces może ten segment odwiązać, czyli usunąć jego dowiązanie. Kiedy wszystkie procesy zakończą korzystanie z segmentu pamięci współdzielonej, za jego usunięcie najczęściej odpowiedzialny jest proces, który segment utworzył.

**Zbiór rezydentny** to porcja pamięci używana przez proces, która jest trzymana w pamięci operacyjnej. Pozostała część zajętej pamięci jest w pamięci wymiany (swap space) lub w plikach systemowych - albo z powodu nieobecności strony, albo z powodu niezaładowania części pliku wykonywalnego.

**Zbiór roboczy** to odpowiednia ilość pamięci, którą proces potrzebuje w danym odstępie czasu. Rozmiar tego zbioru jest zwykle potrzebną ilością pamięci do rozwiązania danego problemu.

Poważne współczesne aplikacje użytkowe, takie jak Photoshop, często zużywają dużo pamięci na samo uruchomienie i przetwarzanie danych. W konsekwencji utrzymywanie wszystkich procesów w pamięci przez cały czas wymaga olbrzymich ilości pamięci i nie może być zrealizowane, jeśli rozmiar pamięci na to niepozwala. Używając pamięci wirtualnej możemy sprawić, że używanie wielu programów naraz jest bezpieczne, łatwe i w miare szybkie.

Izolacja procesów zapewnia nam bezpieczeństwo, wiemy że używając jednej aplikacji nie nadpiszemy drugiej.

Podobny układ przestrzeni adresowej każdego programu, pozwala na łatwe linkowanie oraz wspóldzielenie pamięci. Ładując różne programy używające tych samych bibliotek w użyciu będziemy mieć jedną wspóldzieloną biblioteke.

Sam program nie potrzebuje używać wszystkiego co znajduje się w jego przestrzeni adresowej, faktyczne użytkowanie programu wymaga od niego dostępu tylko do części danych. Ziór rezydentny trzymany jest w pamięci operacyjnej więc jeśli proces potrzebuje zająć się czymś innym niż w danej chwili to może szybko sięgnąć po odpowiednie dane. Zbiór roboczy to pamięć nad która proces pracuje w ostatnim czasie.

### Zadanie 2
Zakładamy taki sam model podsystemu pamięci jak na slajdach do wykładu *„Virtual Memory: Systems”* (strony 9–16). 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**.


**Bufor TLB** *(ang. translation lookaside buffer)* (czasami **pamięć asocjacyjna**) to urządzenie sprzętowe służące do odwzorowywania adresów wirtualnych na fizyczne bez konieczności sięgania do tabeli stron. Zwykle jest ono zlokalizowane wewnątrz jednostki MMU i składa się z niewielkiej liczby pozycji - każda pozycja zawiera informacje dotyczące jednej strony, obejmują one numer strony wirtualnej (VPN), bit ustawiany w przypadku gdy strona jest zmodyfikowana, kod zabezpieczenia (uprawnienia czytania/pisania/uruchamiania) oraz fizyczną ramkę strony wskazującą na lokalizację strony w pamięci fizycznej. Pola te odpowiadają jeden do jednego polom w tabeli stron, wyjątkiem jest numer strony wirtualnej, który nie jest potrzebny w tabeli stron. Kolejny bit wskazuje na to, czy pozycja jest ważna (tzn. czy jest w użyciu), czy nie.

Sposób działania bufora TLB jest następujący: po przesłaniu adresu wirtualnego do jednostki MMU, aby dokonać translacji, sprzęt najpierw sprawdza, czy w buforze TLB znajduje się numer wirtualnej strony. W tym celu jednocześnie (tzn. współbieżnie) porównuje go ze wszystkimi pozycjami. Do tego celu potrzebuje specjalnego sprzętu, w który wyposażone są wszystkie jednostki MMU z TLB. Jeśli zostanie znaleziona pasująca pozycja, a dostęp do niej nie narusza reguł ustanowionych przez bity zabezpieczeń, ramka strony jest pobierana bezpośrednio z bufora TLB, bez potrzeby odwoływania się do tabeli stron. Jeśli numer strony wirtualnej znajduje się w buforze TLB, ale instrkucja poróbuje zapisać stronę tylko do odczytu, generowany jest błąd chybionego odwołania.

Interesujący przypadek zachodzi w czasie, kiedy numeru wirtualnej strony nie ma w buforze TLB. Jednostka MMU wykrywa ten brak i wykonuje standardową operację wyszukiwania w tabeli. Następnie usuwa jedną z pozycji z bufora TLB i zastępuje go odczytaną przed chwilą pozzycją z tabeli stron. W ten sposób, jeśli strona zostanie ponownie użyta w niedługim czasie, odwołanie do niej za drugim razem będzie trafione - strona będzie obecna w buforze TLB. Podczas gdy pozycja jest usuwana z bufora TLB, bit *zmodyfikowano* zostaje skopiowany do tabeli stron w pamięci. Pozostałe wartości już się tam znajdują - z wyjątkiem bitu *w użyciu*. Kiedy bufor TLB jest ładowany z tabeli stron, wszystkie pola są pobierane z pamięci.

**Tablica stron** służy do odwzorowania stron wirtualnych na ramki stron. Z matematycznego punktu widzenia tabela stron jest funkcją, w której numer wirtualnej strony stanowi argument, a numer strony fizycznej - wynik. Dzięki wykorzystaniu wyniku tej funkcji można zastąpić pole numeru strony w adresie wirtualnym polem ramki strony i w ten sposób utworzyć adres w pamięci fizycznej. Przykład działania tablicy stron przedstawia następujący schemat:

Wracając do samego zadania, działamy na takich adresach wirtualnych i fizycznych, jak przedstawione na schemacie poniżej. Adres wirtualny ma 8 bitów VPN, z czego $b_{13},\dots, b_{8}$ to TLBT (bity tagu bufora), $b_7, b_6$ to TLBI (bity indeksu zbioru bufora). Przesunięcie wirtualnej strony (VPO) jest równe przesunięciu fizycznej strony (PPO), a więc bity te kopiujemy za każdym razem. W adresie fizycznym bity $b_{11},\dots,b_6$ to bity znacznika pamięci podręcznej, $b_5,\dots, b_2$ to bity indeksu zbioru, a $b_1, b_0$ to bity przesunięcia.


| VA | VPN | TLBI | TLBT | TLB Hit | Page Fault | PPN | CO | CI | CT | Hit? | Byte |
|:--------:|:------:|:------:|:------:|:-------:|:----------:|:------:|:------:|:------:|:------:|:----:|:----:|
| `0x027c` | `0x09` | `0x01` | `0x02` | Yes | No | `0x17` | `0x00` | `0x0f` | `0x17` | No | Mem |
| `0x03a9` | `0x0e` | `0x02` | `0x03` | No | No | `0x11` | `0x01` | `0x0a` | `0x11` | No | Mem |
| `0x0040` | `0x01` | `0x01` | `0x00` | No | Yes | `-` | `-` | `-` | `-` | `-` | `-` |

Jak odbywa się tłumaczenie? Bierzemy sobie jakiś adres i wyciągamy z niego bezpośrednio VPN, TLBI, TLBT - wtedy sprawdzamy, czy pod podanym indeksem zbioru TLBI istnieje znacznik TLBT. Jeśli tak, to trafiamy w TLB, odczytujemy indeks strony fizycznej PPN i przechodzimy do pamięci podręcznej. Z VPO $\equiv$ PPO wyciągamy przesunięcie cache CO, indeks zbioru cache CI, a PPN odpowiada znacznikowi cache CT. Jeżeli pod danym indeksem CI znajduje się znacznik równy CT, to odczytujemy blok na danym przesunięciu CO. Gdy znacznik CT jest różny, to chybimy w pamięci podręcznej i dane musimy ściągnąć z pamięci (oznaczenie Mem w tabelce). Może się również zdarzyć, że nie trafimy w TLB - wtedy na podstawie indeksu strony wirtualnej VPO szukamy w tablicy stron odpowiadającej ramki (strony fizycznej), jeżeli jest ona ważna (ustawiony bit *V*), to bierzemy jej numer PPN i postępujemy podobnie jak wcześniej, tzn. szukamy danych w pamięci podręcznej. W przypadku gdy chybimy w TLB, a w tablicy stron nie istnieje ramka dla strony wirtualnej, otrzymujemy błąd strony.

### Zadanie 3
W tym zadaniu będziemy analizowali w jaki sposób system operacyjny musi aktualizować **tablicę stron** wraz z kolejnymi dostępami do pamięci głównej. Załóż, że strony są wielkości 4KiB, TLB jest **w pełni asocjacyjne** z zastępowaniem LRU. Najwyższa wartość pola LRU koduje najlepszego kandydata na **ofiarę** *(ang. victim)*. Jeśli potrzebujesz **wtoczyć** *(ang. swap-in)* stronę z dysku użyj następnego numeru **ramki** (ang. page frame) większego od największego istniejącego w tablicy stron.

Dla poniższych danych podaj ostateczny stan TLB i tablicy stron po wykonaniu wszystkich dostępów do pamięci. Dla każdej operacji dostępu do pamięci wskaż czy było to trafienie w TLB, trafienie w tablicę stron, czy też **błąd strony**.

Definicja tablicy stron w 2. zadaniu.

**Ramka strony** to jednostka w pamięci fizycznej odpowiadająca wirtualnej stronie. **Wtoczenie** strony z dysku polega na wczytaniu strony wirtualnej (nie będącej w RAMie) do pamięci podręcznej. **Ofiara** to blok/strona, która była najdawniej używana i jest najlepszym wyborem do zastąpienia. **Pamięć w pełni asocjacyjna (całkowicie skojarzeniowa)** to pamięć posiadająca jeden zbiór o wielu liniach/wierszach, więcej [tutaj](https://hackmd.io/3Y3V3093R3-XSudNCzxMMQ?view#Pami%C4%99%C4%87-ca%C5%82kowicie-skojarzeniowa).

Mamy strony o rozmiarze 4KiB, a więc mamy $\log_2 4096 = 12$ bitów VPO/PPO. Stąd wnioskujemy, że 3 ostatnie cyfry adresu mówią o przesunięciu, a pierwsza o VPN (interesuje nas więc tylko pierwsza cyfra adresu). W TLB największy PPN ma wartość `0x0c`, a więc kolejne wartości jakie będziemy używać to `0x0d`, `0x0e`, `0x0f`. Dostępy, trafienia TLB albo tabeli stron i błędy stron przedstawia poniższa tabelka:

| Adres | Trafienie TLB | Trafienie tablicy stron | Błąd strony | Dodatkowe info |
|:--------:|:-------------:|:-----------------------:|:-----------:|:--------------:|
| `0x123d` | Nie | Nie | Nie | pobieramy dane z dysku, przypisujemy PPN `0x0d` |
| `0x08b3` | Nie | Tak | - | |
| `0x365c` | Nie | Tak | - | |
| `0x871b` | Nie | Nie | Nie | pobieramy dane z dysku, przypisujemy PPN `0x0e` |
| `0xbee6` | Nie | Tak | - | |
| `0x3140` | Tak | - | - | |
| `0xc049` | Nie | Nie | Tak | dane nie istnieją na dysku, więc nic nie zmieniamy |

W tablicy stron zmieniają się tylko dwa wpisy (pozostałych nie wypisuję):

| TLB | Valid | PPN |
|:------:|:-----:|:------:|
| `0x01` | 1 | `0x0d` |
| `0x08` | 1 | `0x0e` |

Bufor TLB po wszystkich dostępach do pamięci jest następujący:

| Valid | Tag | LRU | PPN |
|:-----:|:---:|:---:|:---:|
| 1 | `0x08` | 1 | `0x0e` |
| 1 | `0x03` | 0 | `0x06` |
| 1 | `0x00` | 3 | `0x05` |
| 1 | `0x0b` | 2 | `0x0c` |

### Zadanie 4
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}$$

Przejdźmy teraz do dwupoziomowej tablicy stron. Katalog stron ma 1024 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.

Maksymalny rozmiar tablicy stron możemy obliczyć w następujący sposób: w jednym katalogu jest $2^{10}$ wpisów i każdy katalog wskazuje $2^{10}$ stron, a jeden wpis zajmuje 4 bajty. Do tego musimy dodać rozmiar katalogu stron, a więc 1024 wpisy mnożymy przez ich rozmiar, czyli 4B. Łącznie:
$$4\text{MiB} + 1024 \cdot 4 \text{B} = 4\text{MiB} + 4 \text{KiB}$$

Teraz przejdźmy do obliczenia minimalnego rozmiaru tablicy. Każda strona na drugim poziomie może odwzorować $2^{22}$ bajtów, ponieważ ma $1024 = 2^{10}$ wpisów, a każdy z nich wskazuje na stronę o rozmiarze $4\text{KiB}=2^{12} \text{b}$. Proces zużywa 1GiB swojej przestrzeni adresowej, a więc potrzebujemy
$$\frac{1\text{GiB}}{2^{22}} = \frac{2^{30}}{2^{22}} = 2^8 = 256 \text{ stron II poziomu}$$
Łączny rozmiar wyniesie wtedy $1 + 256 = 257$ stron, każda z nich ma $4\text{KiB}$, a więc $1028\text{KiB}$.

### Zadanie 5
Wiemy, że pamięć podręczna TLB jest niezbędna do przeprowadzania szybkiej translacji adresów. Czemu, w najogólniejszym przypadku, należy wyczyścić zawartość TLB przy **przełączaniu przestrzeni adresowych**? Jak można uniknąć tej kosztownej operacji?
**Wskazówka:** *Rozważ wprowadzenie identyfikatorów przestrzeni adresowych (ASID), tak jak w architekturze MIPS.*

Warto na samym początku rozróżnić tablicę stron od TLB, szczególnie miejscem przechowywania i zasadą działania. Tablica stron znajduje się w pamięci RAM i jest osobna dla każdego procesu, a TLB jest w pamięci podręcznej (L1, L2) procesora i jest wspólny dla wszystkich procseów.

Z tego powodu, w trakcie **przełączania przestrzeni adresowych**, tzn. zmiany pamięci wirtualnej spowodowanej zmianą procesu, należy wyczyścić zawartość TLB, aby "nowy" proces nie odwoływał się do błędnych danych (pod tym samym adresem wirtualnym dla dwóch procesów może być inny adres rzeczywisty).

Aby uniknąć tej operacji, można wzbogacić adres wirtualny o numer procesu, dzięki czemu przełączanie przestrzeni adresowych nie będzie wymagało czyszczenia TLB, gdyż w trakcie odczytu danych z TLB, będzie wiadomo do którego procesu należą wybrane dane.

Coś o ASID [tutaj](https://techpubs.jurassic.nl/manuals/hdwr/developer/R10K_UM/sgi_html/t5.Ver.2.0.book_341.html).

### Zadanie 6 TODO
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?

$$\text{TLB Reach} = \text{TLB size} \times \text{Page size}$$

Dla stron wielkości $4\text{KB}$: $\text{TLB Reach}= 64 *4\text{KB}=256\text{KB}$
Dla stron wielkości $4\text{MB}$: $\text{TLB Reach}= 64 *4\text{MB}=256\text{MB}$

Jeśli rozmiar zbioru roboczego mieści się w zasięgu TLB ($\text{TLB Reach}$), to nie będziemy generować nowych chybień. Jeśli rozmiar zbioru roboczego jest większy od zasięgu TLB to zaczniemy generować chybienia i będziemy tracić na nie czas.

### Zadanie 7
Opisz dokładnie pola **deskryptorów stron** *(ang. page table entry)* i **deskryptorów katalogów stron** *(ang. page directory entry)* dla architektury x86-64. Które z bitów pomocniczych:
* opisują politykę zarządzania pamięcią podręczną dla zawartości strony,
* wspomagają algorytmy zastępowania stron pamięci wirtualnej,
* określają uprawnienia dostępu do zawartości strony (w tym tryb pracy procesora).

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

**Deskryptor stron** to struktura określająca jednoznacznie położenie strony w pamięci, jego typ, rozmiar, prawa dostępu i inne pola opisane poniżej - różnią się one jednak między poziomami 1-3 PTE, a poziomem 4. Schemat przedstawia pola wpisu odwzorowującego 4KiB potomną stronę dla poziomów od pierwszego do trzeciego:

| Bity | Zawartość |
|:----------:|:---------|
| `0` | Bit obecności, musi być ustawiony na 1, aby PTE nie zostało zignorowane, mówi on więc o tym, czy strona jest dostępna w pamięci fizycznej. W systemach Linux bit `P` jest zawsze ustawiony na 1. |
| `1` | Bit odczytu/zapisu, dla 0 nie mogą być wykonywane zapisy do 4KiB strony (a więc tryb read-only), do której odwołuje się ten wpis. |
| `2` | Bit U/S mówi o tym, jaki wymagany jest tryb dostępu dla potomnej strony, tzn. user lub supervisor (kernel). |
| `3` | Bit mówiący o polityce zapisu (write-through lub write-back). |
| `4` | Bit określający, czy pamięć podręczna jest włączona czy wyłączona. |
| `5` | Bit referencji (accessed) ustawiany przez MMU przy odczytach i zapisach, pomocny jest on w algorytmie zastępowania stron pamięci wirtualnej. |
| `7` | Bit mówiący o rozmiarze strony (zdefiniowany tylko dla poziomu pierwszego), jest to albo 4KiB, albo 4 MiB. |
| `8` | Bit mówiący o tym, czy strona jest globalna, a więc czy powinna zostać zamieniona przy zamianie procesów. |
| `51:12` | Bazowy adres fizyczny strony (PPN). |
| `63` | 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. |

Ten schemat przedstawia PTE czwartego poziomu:

Różni się on 6. bitem - bitem *dirty*, określającym czy wykonano zapis przez MMU, bit 7. jest nieużywany, zawsze wyzerowany.

**Deskryptor katalogów** przechowuje informacje o tabelach stron. Jego struktura jest bardzo podobna do struktury deskryptora stron, główną różnicą jest typ przechowywanych danych na bitach `12:51`, tzn. znajduje się tam adres tabeli stron, a nie ramki strony. W schemacie interesować nas będą wiersze drugi i trzeci oraz czwarty do porównania PTE z PDE.

Tutaj podobnie bity pomocnicze niewiele się różnią (jak pomiędzy różnymi poziomami PTE), główne różnice to: nieużywany jest bit *dirty*, a bit *PS* (page size) jest zawsze wyłączony.

Dokładniejszy opis wszystkich bitów znajduje się [tutaj](https://www.intel.pl/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-system-programming-manual-325384.pdf), w rozdziale 4.5 (IA-32e Paging).

### Zadanie 8 TODO
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 wykonywać równolegle 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 25 do wykładu „Virtual Memory: Systems”, ale wytłumacz to szczegółowo!*


Z CSAPP:

Do odczytania danych z Cache potrzebujemy CT(cache tag), CI(cache index) i CO(cache offset).

PPN <- Translacja VPN
CT == PPN
(CI,CO) == PPO == VPO

Do wydobycia danych z L1 potrzebujemy wybrać zbiór, następnie linie, a potem spawdzić czy TAG się zgadza. TAG jest ostatnim krokiem, a zbiór i linia wykonują się w tym samym czasie. Możemy więc przesłać PPO do L1, a w tym samym czasie użyć MMU do translacji VPN. Kiedy otrzymamy PPN cache L1 będzie już gotowy na porównanie tagów.