# Ćwiczenia 10, grupa cz. 14-16, 11 maja 2023

###### tags: `SYK23` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Wojciech Bogucki | X | | | | X | X | X | X | X |
Mateusz Cerulewicz | X | X | X | ==X==| X | X | X | | |
Mateusz Garncarczyk | X | X | X | X | | | | | |
Mateusz Golisz | | | | | | | | | |
Mateusz Kitzol | X | X | X | X | X | X | | X | |
Piotr Mańkowski | | | | | | | | | |
Aleksandra Nicpoń | X | X | X | X | X | X | | X | |
Ksawery Plis | X | X | ==X== | X | X | X | X | | X |
Patryk Rybak | X | X | X | X | X | | | | |
Rafał Spyra | X | | X | X | X | X | X | X | X |
Dominik Szczepaniak | X | X | X | X | X | X | ==X== | X | X |
Taras Tsehenko | | | | | | | | | |
Maksymilian Wiśniewski | X | | X | X | | | | X | X |
Martyna Wybraniec | X | X | X | X | X | X | | X | |
Natalia Zychowicz | X | X | X | X | | | X | X |==X==|
Patryk Maciąg | X | X | X | X | X | X | X | ==X== | |
Michał Mękarski | ==X== | 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: Michał Mękarski
:::


## Zadanie 2
:::success
Autor: Mateusz Garncarczyk
:::


32-bitowe adresy
Rozmiar bloku to 32 bajty

### Pamięć z mapowaniem bezpośrednim

pamięć - 32 wiersze
tag - 22 bity
index - 5 bitów
offset - 5 bitów

      tag                    index offset hit?
      0000000000000000000001 10000 00010  compulsory miss
      0000000000000000000001 00000 00000  compulsory miss
      0000000000000000000000 00000 00000  conflict miss
      0000000000000000000001 10000 00010  hit

### Pamięć dwudrożna używa LRU jako polityki wymiany

pamięć - 16 wierszy
tag - 23 bity
index - 4 bity
offset - 5 bitów

      tag                     index offset hit?
      00000000000000000000011 0000  00010  compulsory miss
      00000000000000000000010 0000  00000  compulsory miss
      00000000000000000000000 0000  00000  conflict miss
      00000000000000000000011 0000  00010  conflict miss

## Zadanie 3
:::success
Autor: Ksawery Plis
:::

**Translacja adresów:** proces tłumaczenia adresów wirtualnych na fizyczne
**TLB (Translation Lookaside Buffer):** niewielka pamięć przechowująca fragmenty tablicy stron, którą MMU może bezpośrednio używać bez konieczności pobierania wpisu z tablicy stron w pamięci operacyjnej.
**Tablica stron:** tablica przetrzymywana w pamięci operacyjnej, która ma w sobie informacje potrzebne do translacji adresu wirtuanego danego procesu, na adres fizyczny.

**a) 0x027c**

0x027c$_{16}$ = 1001111100$_2$


Tag: 10$_2$ = 2$_{10}$
Index: 01$_2$ = 1$_{10}$

Nie znaleźliśmy PPN w TLB.
Szukamy po VPN: 1001$_2$ = 9$_{16}$


PPN: 17$_{16}$ = 10111$_2$


**b) 0x03a9**

0x03a9$_{16}$ = 1110101001$_2$

Tag: 11$_2$ = 3$_{10}$
Index: 10$_2$ = 2$_{10}$


Nie znaleźliśmy PPN w TLB.
Szukamy po VPN: 1110$_2$ = E$_{16}$


PPN: 11$_{16}$ = 10001$_2$


**c) 0x0040**

0x0040$_{16}$ = 1000000$_2$


Tag: 0$_2$ = 0$_{10}$
Index: 1$_2$ = 1$_{10}$

Nie znaleźliśmy w ogóle w TLB
Szukamy po VPN: 1$_2$ = 1$_{16}$


Nie ma PPN w tablicy stron - chybiliśmy
## Zadanie 4
:::success
Autor: Mateusz Cerulewicz
:::

4 KiB = 2^2 * 2^10 = 2^12
Czyli na offset potrzebujemy 12 bitow

Wiec na VPN 4 bity

4669 = 0001 001000111101

TLB: Miss
Page table: Page fault

| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
| 1 | 11 | 0 | 12 |
| 1 | 7 | 1 | 4 |
| 1 | 3 | 2 | 6 |
| 1 | 1 | 3 | 13 |

2227 = 0000 100010110011

TLB: Miss
Page table: PPN = 5

| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
| 1 | 0 | 3 | 5 |
| 1 | 7 | 0 | 4 |
| 1 | 3 | 1 | 6 |
| 1 | 1 | 2 | 13 |

13916 = 0011 011001011100

TLB: PPN = 6

| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
| 1 | 0 | 2 | 5 |
| 1 | 7 | 0 | 4 |
| 1 | 3 | 3 | 6 |
| 1 | 1 | 1 | 13 |

34587 = 1000 011100011011

TLB: Miss
Page table: Page fault

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

48870 = 1011 111011100110

TLB: Miss
Page table: PPN = 12

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

12608 = 0011 000101000000

TLB: PPN = 6

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

49225 = 1100 000001001001

TLB: Miss
Page table: Nie ma nigdzie

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

Page table:

| 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: Patryk Rybak
:::

a)
Rozmiar strony wynosi 4 KiB = 2^12 bajtów.

Rozmiar wpisu tablicy stron to 4 bajty.

Aby obliczyć liczbę stron, musimy podzielić liczbę możliwych adresów wirtualnych przez rozmiar strony:

2^32 / 2^12 = 2^20

Skoro wpis w talbicy wynosi 4 bajty to całkowity rozmiar tablicy jest równy 2^20 * 2^2 = 2^22 bajty (4MiB)

b)
1GiB = 2^30 B
tablica stron pierwszego poziomu = 2^10 * 2^2 B = 2^12 B

Będziemy potrzebować 2^30 / 2^12 = 2^18 stron
W takim razie musimy mieć 2^18 wpisów w tablicy drugiego poziomu.
Każdy wpis zajmuje 2^2 bjatów.
Więc minimalny rozmiar talbicy drugiego poziomu wynosi 2^18 * 2^2 B = 2^20 B

Minimalny rozmiar tablicy dwupoziomowej jest równy:
rozmiar talbicy pierwszego poziomu + rozmiar talbicy drugiego poziomu = 2^12 B + 2^20 B = ok. 1MiB

Maksymalny rozmair zostanie osiągnięty w przypadku wykorzystania całej przstrzeni adresowej 2^32
Mamy wtedy 2^32 / 2^12 = 2^20 stron czyli tyle też będzie łącznie wpisów w tablicach drugiego poziomu.
Maksymalny rozmiar tablicy dwupoziomowej jest równy:
rozmiar talbicy pierwszego poziomu + rozmiary talbic drugiego poziomu = 2^12 B + 2^20 * 2^2 B = ok. 4MiB

adres wirtualny ma 32 bity:
|VPN1|VPN2|VPO|
|10  | 10 |12|

wniosek: tablice stron 2 poziomu również mają po 1024 wpisy

1. Przypadek optymistyczny (wszystkie tablice stron zapełnione wpisami):
2^18 / 2^10 = 2^8 tablic stron, każda z nich ma 1024 wpisy 4 bajtowe.
Sumaryczny rozmiar tablic stron drugiego poziomu to: 2^8 * 2^10 * 2^2 = 2^20

## Zadanie 6
:::success
Autor: Aleksandra Nicpoń
:::

## Zadanie 7
:::success
Autor: Dominik Szczepaniak
:::


Procesor Core i7 wykorzystuje czteropoziomową hierarchię tablic stron. Każdy proces posiada swoją prywatną hierarchię tablic stron. Gdy proces Linux jest uruchomiony, tablice stron związane z przydzielonymi stronami znajdują się w pamięci, chociaż architektura Core i7 pozwala na wymianę tych tablic stron. Rejestr kontrolny CR3 zawiera fizyczny adres początku tablicy stron poziomu 1 (L1). Wartość CR3 jest częścią kontekstu każdego procesu i jest przywracana podczas każdego przełączenia kontekstu.
Używane są 48-bitowe adresy wirtualne, gdzie 36 bitów ma VPN, a 12 VPO. VPO przesyłany jest bezpośrednio do PPO, tymczasem VPN jest najpierw dzielony na 32-bitowe TLBT i 4-bitowe TLBI i przesyłane jako adres do czterodrożnego TLB z 16 zbiorami. Jeśli nie uda się wydobyć żadnego adresu następuje inna metoda - dzielenie na 4 cześci.



Rysunek 9.24 przedstawia format wpisu w tablicy stron poziomu 4. Gdy P=1, pole adresowe zawiera 40-bitowy PPN wskazujący na bazę pewnej strony w pamięci fizycznej. Ponownie, wymuszane jest wyrównanie do 4 KB dla stron fizycznych.

PTE zawiera trzy bity uprawnień kontrolujące dostęp do strony.
1. Bit R/W określa, czy zawartość strony jest zapisywalna-czytelnia, czy tylko do odczytu.
2. Bit U/S, który określa, czy strona może być dostępna w trybie użytkownika, chroni kod i dane w jądrze systemu operacyjnego przed programami użytkowników.
3. Bit XD (execute disable), wprowadzony w systemach 64-bitowych, może być używany do wyłączenia pobierania instrukcji z poszczególnych stron pamięci. Jest to ważna nowa funkcja, która umożliwia jądrze systemu operacyjnego zmniejszenie ryzyka ataków przepełnienia bufora przez ograniczenie wykonywania do segmentu kodu tylko do odczytu.

Podczas tłumaczenia każdego adresu wirtualnego przez MMU, aktualizowane są także dwa inne bity, które mogą być używane przez obsługę wyjątków stronicowania jądra. MMU ustawia bit A, który jest znany jako bit odwołania, za każdym razem, gdy strona jest używana. Jądro może użyć bitu odwołania do wdrożenia swojego algorytmu zastępowania stron. MMU ustawia bit D, czyli bit brudny, za każdym razem, gdy strona jest zapisywana. Strona, która została zmodyfikowana, nazywana jest czasami brudną stroną. Bit brudny informuje jądro, czy musi zapisać victim page przed skopiowaniem strony zastępczej. Jądro może wywołać specjalną instrukcję trybu jądra, aby wyczyścić bity odwołania lub brudne.


Rysunek 9.25 pokazuje, jak procesor Core i7 wykorzystuje czteropoziomową tablicę stron do tłumaczenia adresu wirtualnego na adres fizyczny. 36-bitowy VPN jest podzielony na cztery części po 9 bitów, z których każda jest używana jako offset do tablicy stron. Rejestr CR3 zawiera adres fizyczny tablicy stron L1. VPN 1 jest używany jako offset do PTE (Page Table Entry) tablicy stron L1, który zawiera adres bazowy tablicy stron L2. VPN 2 jest używany jako offset do PTE tablicy stron L2 i tak dalej.

Przewagą tablicy czteropoziomowej nad jednopoziomową jest duża oszczędność pamięci. Jeśli adres w tablicy wyższego poziomu nie jest określony, to nie ma konieczności rezerwowania pamięci dla tablic niższych poziomów.

## Zadanie 8
:::success
Autor: Patryk Maciąg
:::




## Zadanie 9
:::success
Autor: Natalia Zychowicz
:::