---
# System prepended metadata

title: 'Ćwiczenia 10, grupa śr. 10-12, 10 maja 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 10, grupa śr. 10-12, 10 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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk            |       |     |     |     |     |     |     |     |     | 
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |     |
Kacper Jóźwiak           | X     |  X  | X   | X   |  X  |  X  |     | X   |     |
Dominik Kiełbowicz       |       |     |     |     |     |     |     |     |     |
Michał Kolasa            |       |     |     |     |     |     |     |     |     |
Konrad Kowalczyk         |   X   |  X  |  X  |  X  |  X  |  X  |  X  |  X  |     |
Oskar Kropielnicki       |   X   |  X  |  X  |==X==|     |  X  |     |  X  |     |
Anna Krysta              |   X   |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  |
Jakub Krzyżowski         |   X   |  X  |  X  |  X  |==X==|  X  |     |  X  |     |
Oskar Kubkowski          |  X    |   X | ==X==    |  X   | X    | X    |     | X    |     |
Mateusz Mazur            |   X    |  X   |  X   |  X   |  X   |  X   |     |     |     |
Barbara Moczulska        |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Kacper Sojda             |    X   |  X   |  X   |   X  |  X   |   X  |     |     |     |
Marta Strzelec           |     X  | X    | X    | X    |     | X    |     |   X  |     |
Mikołaj Swoboda          |   X   |  X  |  X  |  X  |  X  |    |     |  X  |     |
Filip Szczepański        |   X    |  X   | X    | X    |   X  |  X   |     |  X   |     |
Julian Włodarek          |   X    |  X   | X    | X    |   X  |  X   |     |  X   |     |
Beata Łakoma             |  x     |  x   |  x   |  x   |  x   |  x   |     |  x   |     |
Michał Łukasik           |   X   |  X  |  X  |     |  X  |  X  |     |  X  |     |
:::


Tu można zadeklarować zadanie 8 z listy 9:
-Anna Krysta
-
-



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



## Zadanie 1
:::success
Autor:	Michał Łukasik	
:::

![](https://hackmd.io/_uploads/r1zhX0_Vh.png)

Najstarsze bity zmieniają się znacznie rzadziej od młodszych bitów adresu, np. iterując po tablicy.
Korzystając ze środkowych bitów adresu podobne adresy mają takie same lub podobne tagi, ale różne zbiory i offsety.

Korzystając z najstarszych bitów podobne adresy mają takie same lub podobne zbiory oraz różne tagi i offsety.
Ponieważ podczas iteracji po tablicy często powtarzały by się zbiory, lecz z różnymi tagami, to następowało by więcej kolizji i zastąpień.

![](https://hackmd.io/_uploads/S1gdB0_Vn.png)


## Zadanie 2
:::success
Autor:	Marta Strzelec	
:::

![](https://hackmd.io/_uploads/S1mCmAdN2.png)

Rozważmy 5-bitowe adresy o następującym formacie:

**Pamięć z mapowaniem  bezpośrednim** : tag - 2 bity, index - 2 bity, offset - 1 bit
W takim formacie mamy cztery zbiory po jednym bloku.


| tag  | index | offset | hit |
| ---- | ----- | ------ | --- |
| 00     | 00      | 0       | compulsory miss    |
| 00     |   10    |     0   |  compulsory miss   |
|    01  |  10     |   0     |   conflict miss  |
| 00     | 00      | 0       | hit    |

**Pamięć dwudrożna używająca LRU jako polityki wymiany:** tag - 3 bity; index - 1 bit; offset - 1 bit
W takim formacie mamy 2 zbiory po 2 bloki.

| tag | index | offset | hit  |
| --- | ----- | ------ | ---- |
|  000   |   0    |  0      | compulsory miss     |
| 001    |    0   |   0     |   compulsory miss   |
|   011  |  0     |    0    |   conflict miss   |
| 000 | 0     |  0      | conflict miss --> pierwszy wpis zostal usuniety |


## Zadanie 3
:::success
Autor:	Oskar Kubkowski	
:::
### a)

![](https://hackmd.io/_uploads/r1svyQu4n.png)
![](https://hackmd.io/_uploads/HyO_y7_Vn.png)



### b)

![](https://hackmd.io/_uploads/HkSF17dNn.png)
![](https://hackmd.io/_uploads/B1G5JQOV2.png)



### c)

![](https://hackmd.io/_uploads/SJ0NX0uE2.png)
![](https://hackmd.io/_uploads/S1xpk7_En.png)





## Zadanie 4
:::success
Autor:	Oskar Kropielnicki	
:::

![](https://hackmd.io/_uploads/ByBwdMOV2.png)
![](https://hackmd.io/_uploads/H1KuOG_N2.png)

$4\text{KiB} = 2^{12}\text{B} \implies$ 12 bitów na VPO/PPO.
Adresy są 16-bitowe, więc 4 ($= 16 - 12$) bity przeznaczane są na VPN.
TLB jest w pełni asocjacyjna, więc jest tylko jeden zbiór, więc indeks zbioru nie musi być przechowywany w VPN, więc wszystkie 4 bity przeznaczane są na znacznik.

:::spoiler ciąg dostępów do pamięci
T
:::

:::spoiler początkowy stan TLB
| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
| 1      | 11  | 0   | 12  |
| 1      | 7   | 1   | 4   |
| 1      | 3   | 2   | 6   |
| 0      | 4   | 3   | 9   |
:::

:::spoiler początkowy stan tablicy stron
| VPN | Valid? | PPN  |
|-----|--------|------|
| 0   | 1      | 5    |
| 1   | 0      | dysk |
| 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 |
:::
<br>

<style>
    .c {
        font-family: monospace;
        font-size: 1.2em;
    }
</style>

:::spoiler 4669 - page fault
<span class="c">4669~(10)~ = ++0001++ 0010 0011 1101~(2)~</span>

Znacznik = 1.
Szukamy go w TLB... brak. Szukamy go w tablicy stron... `Valid?` = 0, brak, błąd strony.

page fault - błąd strony
![](https://hackmd.io/_uploads/rkmHuM_Nh.png)

Ponieważ nie znaleźliśmy szukanej strony w TLB i tablicy stron, dobrze by było pobrać ją z dysku oraz umieścić w TLB i tablicy.

#### TLB

Wyrzucamy z TLB:
 * dowolną krotkę, w której `Valid?` = 0, lub
 * krotkę, która była najdawniej używana (LRU = 0).
W jej miejsce wstawiamy nową - ze znacznikiem, którego nie znaleźliśmy, i z PPN takim, żeby, zgodnie z treścią zadania, był większy od największego numeru ramki (PPN) istniejącego w tablicy stron. Nowa krotka jest ==zaznaczona==.

Ramka
 ~ [the smallest fixed-length contiguous block of physical memory into which memory pages are mapped by the operating system](https://en.wikipedia.org/wiki/Page_(computer_memory)) (najmniejszy ciągły blok fizycznej pamięci, na którą strony są mapowane).

Do tego zmniejszamy LRU pozostałych krotek o 1. Jeśli LRU = 0, to zostawiamy 0.

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

#### Tablica stron

Tablicę stron aktualizujemy podobnie; krotkę z odpowiednim VPN już mamy, więc zmieniamy tylko PPN i `Valid?`.

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

:::spoiler 2227 - page hit
<span class="c">2227~(10)~ = ++0000++ 1000 1011 0011~(2)~</span>

Znacznik = 0.
Szukamy go w TLB... brak. Szukamy go w tablicy stron... `Valid?` = 1, jest; PPN = 5; $█▬█\ \ █\ \ ▀█▀$.

#### TLB

W TLB zastępujemy najdawniej używaną krotkę i aktualizujemy LRU dla pozostałych.

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

#### Tablica stron

Tablica stron w tym przypadku pozostaje bez zmian.

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

:::spoiler 13916 - TLB hit
<span class="c">13916~(10)~ = ++0011++ 0110 0101 1100~(2)~</span>

Znacznik = 3.
Szukamy go w TLB... jest. Nie musimy szukać go w tablicy stron; PPN = 6; $█▬█\ \ █\ \ ▀█▀$.

#### TLB

W tym przypadku tylko aktualizujemy LRU wszystkich krotek.

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

#### Tablica stron

Tablica stron również w tym przypadku pozostaje bez zmian.

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

:::spoiler 34587 - page fault
<span class="c">34587~(10)~ = ++1000++ 0111 0001 1011~(2)~</span>

Znacznik = 8.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... brak.

#### TLB

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

#### Tablica stron

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

:::spoiler 48870 - page hit
<span class="c">48870~(10)~ = ++1011++ 1110 1110 0110~(2)~</span>

Znacznik = 11.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... jest.

#### TLB

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

#### Tablica stron

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

:::spoiler 12608 - TLB hit
<span class="c">12608~(10)~ = ++0011++ 0001 0100 0000~(2)~</span>

Znacznik = 3.
Szukamy go w TLB... jest.

#### TLB

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

#### Tablica stron

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

:::spoiler 49225 - page fault<sup>2</sup>
<span class="c">49225~(10)~ = ++1100++ 0000 0100 1001~(2)~</span>

Znacznik = 12.
Szukamy go w TLB... brak.
Szukamy go w tablicy stron... brak^2^.
Nawet na dysku go nie ma. :flushed: 

#### Ostateczny stan TLB

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

#### Ostateczny stan tablicy stron

| 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:	Jakub Krzyżowski	
:::
![](https://hackmd.io/_uploads/BksvKK7V2.png)
Mamy:
4 KiB ($2^{12}$ B) page size - rozmiar strony,
32-bit address space - $2^{32}$ adresów wirtualnych,
4 B PTE (Page Table Entry) - wpis tablicy stron

(a)
$2^{32} / 2^{12} = 2^{20}$ stron
$2^{20} * 2^2 = 2^{22}$ B = 4 MiB

(b)
![](https://hackmd.io/_uploads/By2C1MOEh.png)
Katalog tablicy stron: $2^{10} * 2^2B = 2^{12}B$

$1 GiB = 2^{30}B$
A więc najmniej będziemy potrzebować $2^{30} / 2^{12} = 2^{18}$ stron.
A zatem najmniejsza liczba wpisów jaką będziemy potrzebować w tablicy stron 2-go poziomu to: $2^{18}$, więc minimalny rozmiar tablicy 2-go poziomu to $2^{18} * 2^2B$.
Więc minimalny rozmiar dwupoziomowej tablicy stron dla tego procesu wyniesie:
$2^{10} * 2^2B + 2^{18} * 2^2B = (2^{10} + 2^{18}) * 2^2 = (1 + 2^8) * 2^{10} * 2^2B \approx 2^{20}B = 1 MiB$

Tablica stron przybierze maksymalny rozmiar kiedy proces będzie używał całej przestrzeni adresowej: $2^{32}B$
Wtedy będziemy mieć $2^{32}/2^{12} = 2^{10}$ stron, a więc wpisów w tablicy stron 2-go poziomu będzie też $2^{10}$.
Więc maksymalny rozmiar tablicy stron dla tego procesu wyniesie:
$2^{10} * 2^2B + 2^{20} * 2^2B = (2^{10} + 2^{20}) * 2^2 = (1 + 2^{10}) * 2^{10} * 2^2B \approx 2^{22}B = 4 MiB$

## Zadanie 6
:::success
Autor:	Filip Szczepański	
:::
![](https://hackmd.io/_uploads/B1Y64RO4n.png)

Zbiór roboczy to zbiór aktualnie aktywnych stron w pamięci wirtualnej wykorzystywanych przez proces.

TLB zawiera 64 wpisy, po 4 wpisy na zbiór, czyli 64/4 = 16 zbiorów.

Przestrzeń adresowa 2^48B

1) wielkość strony 4KiB

Optymistycznie: Czyli wykorzystujemy całe TLB (64 wpisy)
64 * 4KiB = 256KiB

Pesymistycznie: (4 wpisy)
4 * 4KiB = 16KiB

2) wielkość strony 4MiB

Optymistycznie:(64 wpisy)
256MiB

Pesymistycznie:(4 wpisy)
16MiB

## Zadanie 7
:::success
Autor:	Konrad Kowalczyk	
:::

![](https://hackmd.io/_uploads/HkuyrAO4h.png)

Procesory w architekturze x86-64 używają czteropoziomowej tablicy stron, gdzie tablice wyższych poziomów zawierają wpisy przekierowujące do tablic niższych poziomów. Używane są 48-bitowe adresy wirtualne z 36-bitowym VPN i 12-bitowym VPO.
VPO jest bez żadnych przekształceń przesyłany jako 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ć żądanego adresu z TLB, VPN jest dzielony na 4 części po 9 bitów. Każda z tych części oznacza offset na kolejnych poziomach tablicy stron. Tymczasem adresy kolejnych tablic są przechowywane we wpisach tablic wyższych poziomów, tzn. wpis w tablicy poziomu 1 zawiera adres do odpowiedniej tablicy poziomu 2 itd. Szukany wpis w tablicy poziomu pierwszego jest ustalany przez specjalny rejestr CR3, którego wartość jest częścią instrukcji aktualnie wykonywanego procesu.

![](https://hackmd.io/_uploads/SJjnVCdE2.png)

Wpisy w tablicach poziomu 1, 2 oraz 3 są w tym samym formacie:
![](https://hackmd.io/_uploads/ByxXH0OV2.png)

| Pole | Opis |
| :---: | :---: |
| P | określa czy pole adresowe zawiera adres do następnego poziomu tablicy |
| R/W | określa czy strony dostępne z tego adresu (tzn. strony w całym regionie obejmowanym przez ten poziom tablicy) są dostępne tylko do odczytu czy do odczytu i zapisu |
| U/S | określa czy dostęp do stron w całym regionie obejmowanym przez ten poziom tablicy mają programy użytkownika czy też dostęp ma jedynie jądro systemu |
| WT | określa czy strony w całym regionie obejmowanym przez ten poziom tablicy używają polityki zapisu write-back czy write-through |
| CD | określa czy strony w całym regionie obejmowanym przez ten poziom tablicy mają być sprawdzane czy też należy od razu odwołać się do pamięci głównej |
| A | specjalny bit referencji, ustawiany za każdym razem gdy proces uzyskuje dostęp do strony, używany do określania, które tablice stron powinne zostać wyrzucone w przypadku chybienia |
| PS | określa czy rozmiar pojedynczej strony wynosi 4 KB czy 4 MB (określony tylko dla tablicy poziomu 1) |
| G | określa czy strona powinna zostać wyrzucona z TLB w przypadku zmiany obecnego zadania w procesie |
| Page table physical base addr | Adres do odpowiedniej tablicy niższego poziomu |
| XD | określa czy ze stron w całym regionie obejmowanym przez ten poziom tablicy można odczytać instrukcje dla procesów |


Wpisy w tablicach poziomu 4 (pola o nazwach takich samych jak w tablicach wyższych poziomów pełnią takie same funkcje):
![](https://hackmd.io/_uploads/HkaSS0_En.png)

| Pole | Opis |
| :---: | :---: |
| D | tzw. dirty bit, określa czy strona została zmodyfikowana i czy musi zostać zmodyfikowana w pamięci głównej przed jej usunięciem w pamięci podręcznej |

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:	Beata Łakoma	
:::

![](https://hackmd.io/_uploads/B1s2VAOVh.png)
![](https://hackmd.io/_uploads/BJMwB0_En.png)

wcześniej
va->pa - weź set - znajdz tag
optymalizacja:
Set można pobrać równolegle z translacją adresu, kiedy vpo jest takie samo jak ppo. Taka optymalizacja nie jest możliwa gdy ppo>vpo.  

## Zadanie 9
:::success
Autor:	Anna Krysta	
:::
![](https://hackmd.io/_uploads/ryeUrAONh.jpg)
![](https://hackmd.io/_uploads/rkoIrA_Nn.jpg)

![](https://hackmd.io/_uploads/SJ9DBRd4n.jpg)

![](https://hackmd.io/_uploads/rkcFrRONh.jpg)
