---
# System prepended metadata

title: 'Ćwiczenia 10, grupa cz. 12-14, 19. maja 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ćwiczenia 10, grupa cz. 12-14, 19. maja 2022

###### tags: `SYK21` `ć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   | 
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
 Daniel Boguszewski      |   x   |     |  x  |  x  |     |     |     |     |     | 
 Adam Ciężkowski         |       |     |     |     |     |     |     |     |     | 
 Jacek Długopolski       |       |     |  x   |  x   |     |  x   |  x   |  x   |  x   |
 Jakub Fila              |   x   |  x  |  x  |  x  |  x  |     |     |     |     | 
 Krzysztof Grynkiewicz   |       |     |     |     |     |     |     |     |     |
 Michał Hetnar           |   x   |  x  |   x |     |     |     |     |     |     | 
 Hubert Jabłoński        |  x    |  x  |  x  |==x==|  x  |     |     |     |     | 
 Antoni Kamiński         |       |     |     |     |     |     |     |     |     | 
 Paweł Karaś             |  X  | X | X | X | X  |     |     |     |     | 
 Emil Kisielewicz        |   x   |  x  |  x  |  x  |     |     |     |     |     | 
 Kacper Komenda          |    x   |     | x    |     |     |     |     |     |     | 
 Filip Komorowski        |    x   |  x   |   x  |   x  |  x   | x    |     |   x  |     | 
 Piotr Piesiak           |   x    |  ==x==   |  x   |  x   |  x   |  x   |     |  x   |  x  | 
 Artur Krzyżyński        |   x   |  x  |  x  |   x |  x  |  x  |     |  x  |     | 
 Patryk Mazur            |   X    |  X   | ==X==  |  X   |  X   |  X   |     |     |     | 
 Szymon Mleczko          |     X  |  X   |   X  |  X   |  X   |  X   |     |     |     | 
 Michał Mróz             |   x   |  x  |  x  |==x==|  x  |     |     |     |     | 
 Dominik Olejarz         |   x    |   x  |  x   |     |  x   |     |     |  x   |     | 
 Magdalena Słonińska     |   X   |  X  |==X==|  X  |  X  |  X  |     |     |     | 
 Oleś Kulczewicz         |   X   |  X  |  X  |  X  |     |     |     |     |     | 
 Adam Szeruda            |   X   |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  | 
 Kamil Tasarz            |       |     |     |     |     |     |     |     |     | 
 Michał Zieliński        | ==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ł Zieliński
:::

### Treść
Rozważmy alternatywny sposób indeksowania pamięci podręcznej, w którym do wyboru numeru zbioru używa się nie środkowych bitów adresu, lecz najstarszych bitów. Dlaczego to podejście nie jest rozsądne?

### Rozwiązanie
Najstarsze bity zmieniają się wolniej niż środkowe, oznacza to, że blisko siebie umieszczone dane zamiast znaleźć się w sąsiednich liniach, znajdą się w tej samej lini. ![](https://i.imgur.com/7CytWyS.jpg)
Wymusza to na nas większą asocjatywność - musimy być w stanie odróżnić sety. Długie ciągi zmapowane do tej samej linii dają dużo konfliktów.

## Zadanie 2
:::success
Autor: Piotr Piesiak
:::

Rozważmy 5-btiowe adresy z 1 bitem na offset. Pamięć będzie mieć łącznie 4 bloki. Organizacje pamięci:

1. Mapowanie bezpośrednie:
Adresy postaci: TT II OO
4 zbiory po 1 bloku
00 00 0 - miss
00 10 0 - miss
01 10 0 - replace
00 00 0 - hit

2. Pamięć dwudrożna:
Adresy postaci TTT I O
2 zbiory po 2 bloki
000 0 0 - miss
001 0 0 - miss
011 0 0 - replace
000 0 0 - replace (bo 1 wpis usunelismy - LRU)


## Zadanie 3
:::success
Autor: Patryk Mazur
:::
![](https://i.imgur.com/1NM5O8F.png)
![](https://i.imgur.com/UeJmA0N.png)

:::spoiler 0x027c
![](https://i.imgur.com/HEnSVCu.png)
:::

:::spoiler 0x03a9
![](https://i.imgur.com/dVb8rXq.png)
:::

:::spoiler 0x0040
![](https://i.imgur.com/AAeKohv.png)

:::

## Zadanie 4
:::success
Autor: Hubert Jabłoński
:::
![](https://i.imgur.com/bKhEbNG.png)

![](https://i.imgur.com/hHQVZZn.png)

![](https://i.imgur.com/yXk0E8F.png)

![](https://i.imgur.com/cQHshNE.png)

![](https://i.imgur.com/pvFMoLr.png)

$4$ KiB strona -> $log_2(4 \cdot 1024) = 12$ bitów na page offset
$4$ bitów na VPN

VA = VPN + VPO = $16b$

### Adres: 4669
VA = 1001000111101
VPN = 0001 = 1
VPO = 001000111101

TLB: Miss
Page table: Page fault
Największy PPN: 12 => PPN: 13
LRU: Tag 4

New TLB:

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

### Adres: 2227
VA = 100010110011
VPN = 0000 = 0
VPO = 100010110011

TLB: Miss
Page table: Hit: PPN: 5
LRU: Tag 3

New TLB:

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

### Adres: 13916
VA = 11011001011100
VPN = 0011 = 3
VPO = 011001011100

TLB: Miss
Page table: Hit: PPN: 6
LRU: Tag 7

New TLB:

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

### Adres: 34587
VA = 1000011100011011
VPN = 1000 = 8
VPO = 011100011011

TLB: Miss
Page table: Page fault
Największe PPN: 13 => PPN: 14
LRU: Tag 11

New TLB:

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

### Adres: 48870
VA = 1011111011100110
VPN = 1011 = 11
VPO = 111011100110

TLB: Miss
Page table: Hit: PPN: 12
LRU: Tag 1

New TLB:

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

### Adres: 12608
VA = 11000101000000
VPN = 0011 = 3
VPO = 000101000000

TLB: Hit: PPN: 6

New TLB:

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

### Adres: 49225
VA = 1100000001001001
VPN = 1100 = 12
VPO = 000001001001

TLB: Hit: Miss
Page table: Page fault

TLB:

| Valid? | Tag | LRU | PPN |
|--------|-----|-----|-----|
|   1    | 8   |  0  |  14 |
|   1    | 3   |  2  |  6  |
|   1    | 0   |  3  |  5  |
|   1    | 11  |  1  |  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 |   0    | dysk|
|  11 |   1    |  3  |
|  12 |   1    | brak|

## Zadanie 5
:::success
Autor: Dominik Olejarz
:::
![](https://i.imgur.com/ibkm35M.jpg)



## Zadanie 6
:::success
Autor: Szymon Mleczko
:::
![](https://i.imgur.com/AMU5Tnl.png)

Aktualnie aktywny zbiór pamięci wirtualnej wykożystywanej przez proces (odwołanie w ostzatnich I instrukcjach+) nazywamy zbiorem roboczym

czterodrożna TLB bedzie miała 4 wpisy w secie zatem aby zmieścić 64 wpisy będziemy  mieli 16 setów
zatem z 48 bitów dostępnych w adresowaniu potrzebujemy 4 bit na set i 2 na wpis
zatem 48-7 = 41
4KiB = 2^{12} zatem możemy wszystko zaadresować
optymistycznie wykożystujemy całe TBL zatem do dyspozycji mamy 4KiB * 64 = 256KiB
pesymistycznie wszystie odwołania do jednego setu 4KiB * 4 = 16KiB
4MiB=2^{26} zatem możemy wszystko zaadresować
wtedy optymistycznie jest 256MiB
pesymistycznie 16MiB
## Zadanie 7
:::success
Autor: Adam Szeruda
:::


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

Wpis w tablicach poziomu 1-3: 512 wpisów po 64 bity, w sumie 4KiB.

![](https://i.imgur.com/yeOlspk.png)

Wpis w tablicy poziomu 4:

![](https://i.imgur.com/e4TSNNk.png)

Schemat całego układu translacji adresów:

![](https://i.imgur.com/UYQ6mDp.png)


## Zadanie 8
:::success
Autor: Filip Komorowski
:::

![](https://i.imgur.com/pBT73Oy.png)

![](https://i.imgur.com/w62MK4T.png)

![](https://i.imgur.com/M1b3iv5.png)
![](https://i.imgur.com/1sCy0iq.png)
Gdy długość VPO i PPO są takie same (jak powyżej) możemy zrównoleglić te kroki:
* translacja adresu na adres fizyczny
* indeksowanie pamięci podręcznej

## Zadanie 9
:::success
Autor: Piotr Piesiak
:::

W tablicy jednopoziomowej dla adresów n bitowych i rozmairu strony k, potrzebujemy $2^{n-k}$ wpisów, jeśli n to 64, k to 12 (4KB) musielibyśmy dla każdego procesu utrzymywać $2^{52}$ wpisów.

Żeby zmniejszyć tę liczbę korzystamy z wielopoziomowych tablic, jednak pwoodują one wiele odwołań do pamięci. Inny sposób:

Utrzymywanie jednej tablicy stron, która nie jest indeksowana adresami wirtualnymi, tylko faktycznymi adresami stron. 


![](https://i.imgur.com/czqsgVF.png)
![](https://i.imgur.com/DnboozT.png)
