Ćwiczenia 10, grupa śr. 17-19, 18. maja 2022

# Ćwiczenia 10, grupa śr. 17-19, 18. 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 | | ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- | Grzegorz Bielecki | | | | | | | | | | Kamila Brzozowska | X | X |==X==| X | X | X | | X | | Adam Ciężkowski | X | X | X | X | ==X== | X | | X | | Natalia Czerep | X | X | X | | X | | | X | X | Jan Dalecki | X | | X | X | | | | | | Marko Golovko | X |==X==| X | | X | X | | | | Adam Górkiewicz | X | X | X | X | X | | | | | Piotr Gunia | X | X | X | X | X | | | | | Krzysztof Jadłowski | X | X | X | X | X | | | | | Magdalena Jarecka | X | | | X | X | | | | | Mikołaj Jaszcza | X | X | X | X | X | | | | | Monika Jędrzejkowska | | | | | | | | | | Michał Kierul | X | X | X | X | | X | | | | Damian Lukas | | | | | | | | | | Karol Ochman-Milarski | | | | | | | | | | Piotr Piesiak | | | | | | | | | | Damian Ratajski | | | | | | | | | | Aleksandra Rozkrut | X |==X==| X | X | X | X | | | | Marcin Sarnecki | X | X | X |==X== | X | X | | | | Maria Szlasa | | | X | X | X | | | | | Mateusz Burdyna | ==X== | X | X | X | X | | | X | | Magdalena Słonińska | | | | | | | | | | Nikola Wrona | X | X | X | X | X | | | | | Marcin Wróbel | 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: Mateusz Burdyna ::: ![](https://i.imgur.com/FKKSXNH.png) ![](https://i.imgur.com/wylpfFN.png) ## Zadanie 2 :::success Autor: Marko Golovko ::: 32-bitowe adresy Rozmiar bloku 32 bajty 32 wiersze ma pamięć tag - 22 bity index - 5 bitów offset - 5 bitów ``` tag index offset hit 0000000000000000000000 00000 00010 cold 0000000000000000000000 10000 00000 cold 0000000000000000000001 10000 00000 replace 0000000000000000000000 00000 00100 hit ``` * Pamięć dwudrożna używa LRU jako polityki wymiany 16 wiersze ma pamięć tag - 22 bity index - 4 bity offset - 5 bitów ``` tag index offset hit 00000000000000000000000 0000 00010 cold 00000000000000000000001 0000 00000 cold 00000000000000000000011 0000 00000 replace 00000000000000000000000 0000 00100 replace ``` :::danger Autor: Krzysztof Jadłowski ::: ## Zadanie 3 :::success Autor: Jan Dalecki ::: TLB - Niewielka pamięć przechowująca niektóre wpisy tablicy stron, którą MMU może bezpośrednio używać bez konieczności pobierania wpisu z tablicy stron w pamięci operacyjnej. 0x027c = 10 | 01 | 111100 0x03a9 = 11 | 10 | 101001 0x0040 = 00 | 01 | 000000 | Adres | VPN | VPO | TLBI | TLBT | PPN | CO | CI | CT | |:------:|:---:|:----:|:----:|:----:|:----:|:---:| --- |:----:| | 0x027c | 0x9 | 0x3c | 0x1 | 0x2 | 0x17 | 0x0 | 0xf | 0x17 | | 0x03a9 | 0xe | 0x29 | 0x2 | 0x3 | 0x11 | 0x1 | 0xa | 0x11 | | 0x0040 | 0x1 | 0x0 | 0x1 | 0x0 | -- | -- | -- | -- | ## Zadanie 4 :::success Autor: Marcin Sarnecki ::: ![](https://i.imgur.com/ub6UqiF.png) 4KiB = 4096B $2^{12}=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? | | ---- | -------------- | -------- | --------- | | 0001 | 0010 0011 1101 | nie | nie | | Valid? | Tag | LRU | PPN | | ------ | --- | --- | --- | | 1 | 11 | 1 | 12 | // pozostałe postarzamy o 1 | 1 | 7 | 2 | 4 | | 1 | 3 | 3 | 6 | | 1 | 1 | 0 | 13 | // nadpisujemy najstarszy zapis | 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 | --- Krok 2: | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 0000 | 1000 1011 0011 | nie | tak | | Valid? | Tag | LRU | PPN | | ------ | --- | --- |:--------------- | | 1 | 11 | 2 | 12 | | 1 | 7 | 3 | 4 | | 1 | 0 | 0 | 5 (nadpisujemy) | | 1 | 1 | 1 | 13 | | 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 | --- Krok 3 | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 0011 | 0110 0101 1100 | nie | tak | | Valid? | Tag | LRU | PPN | | ------ | --- | --- |:--- | | 1 | 11 | 3 | 12 | | 1 | 3 | 0 | 6 | | 1 | 0 | 1 | 5 | | 1 | 1 | 2 | 13 | | 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 | --- Krok 4 | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 1000 | 0111 0001 1011 | nie | nie | | Valid? | Tag | LRU | PPN | | ------ | --- | --- |:--- | | 1 | 8 | 0 | 14 | | 1 | 3 | 1 | 6 | | 1 | 0 | 2 | 5 | | 1 | 1 | 3 | 13 | | 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 | --- Krok 5 | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 1011 | 1110 1110 0110 | nie | tak | | Valid? | Tag | LRU | PPN | | ------ | --- | --- |:--------------:| | 1 | 8 | 1 | 14 | | 1 | 3 | 2 | 6 | | 1 | 0 | 3 | 5 | | 1 | 11 | 0 | 12 (nadpisuje) | | 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 | --- Krok 6 | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 0011 | 0001 0100 0000 | tak | ----- | | 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 | | 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 | --- Krok 7 | VPN | VPO | TLB hit? | Page hit? | | ---- | -------------- | -------- | ---------- | | 1100 | 0000 0100 1001 | nie | nie | | Valid? | Tag | LRU | PPN | | ------ | --- | --- |:--- | | 1 | 8 | 2 | 14 | | 1 | 3 | 0 | 6 | | 1 | 0 | 3 | 5 | | 1 | 11 | 1 | 12 | | 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 | --- Wynik końcowy | Valid? | Tag | LRU | PPN | | ------ | --- | --- | --- | | 1 | 8 | 2 | 14 | | 1 | 3 | 0 | 6 | | 1 | 0 | 3 | 5 | | 1 | 11 | 1 | 14 | | 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: Adam Ciężkowski ::: ![](https://i.imgur.com/iCLG4sx.png) a) $2^{32} \cdot 2^{-12} \cdot 2 ^ 2 = 2^{22}$ (4MiB) b) $1$ GiB = $2^{30}$ B 4 KiB = $2^{12}$ B Potrzebujemy $2^{30} / 2^{12} = 2^{18}$ stron Minimalny: $(2^{8} + 1) \cdot 2^{10} \cdot 2^{2} \approx 2^{20}$ (1MiB) Maksymalny: $(2^{10} + 1) \cdot 2^{10} \cdot 2^{2} \approx 2^{22}$ (4MiB) ## Zadanie 6 :::success Autor: Michał Kierul ::: ![](https://i.imgur.com/tPEJTUs.png) Zbiór roboczy to zbiór aktualnie aktywnych stron w pamięci wirtualnej wykorzystywanych przez proces. Czterodrożne TLB o 64 wpisach ma 16 setów po 4 wpisy. W optymistycznym przypadku wykorzystane są wszystkie 64 wpisy, czyli pamięć 4KiB * 64 = 256KiB. W pesymistycznym wypadku wszystkie wykorzystywane strony mogą należeć do tego samego seta. Wtedy maksymalnie tych stron może być 4, więc pamięć 4KiB * 4 = 16KiB. Dla dużych stron jest odpowiednio 256MiB i 16MiB. ## Zadanie 7 :::danger Autor: ::: ## Zadanie 8 :::success Autor: Marcin Wróbel ::: ![](https://i.imgur.com/jpZvVOG.png) ![](https://i.imgur.com/AAU6hdY.png) Gdy w architekturze rozmiar **VPO** równy rozmiarowi **PPO**, możemy wykorzystać tę informację, do równoległego wykonania następujących **2** czynności: - obliczenia **CI**, oraz **CO**, i pobraniania odpowiegniego set'u z cache - przetłumaczenia **VPN** na **PPN** Dzięki temu będziemy po wykonaniu powyższych zadań będziemy musieli tylko porównać **CT** = **PPN** z tagami w setcie ## Zadanie 9 :::success Autor: Natalia Czerep ::: Źródło (oprócz książki): https://web.eecs.umich.edu/~akamil/teaching/sp04/040104.pdf Ogólne idee: 1) Zamiast jednego wpisu na każdą wirtualną stronę należącą do procesu, zawiera jeden wpis dla każdej strony fizycznej w pamięci głównej. 2) Kazdy proces ma tą samą page table 3) Page Table Entry jest indeksowane przez fizyczny nr strony a nie vpn **Wersja najprostsza:** Skoro tabela jest współdzielona przez procesy , każdy wpis musi zawierać identyfikator procesu. A skoro fizyczne strony są teraz mapowane na wirtualne, każdy wpis zawiera wirtualny numer strony zamiast fizycznego. Fizyczny numer strony nie jest przechowywany, ponieważ odpowiada mu indeks w tabeli. Aby przetłumaczyć wirtualny adres, porównuje się wirtualny numer strony i bieżący identyfikator procesu dla każdego wpisu, przechodząc kolejno przez tablicę. Jeśli nie zostanie znalezione żadne dopasowanie, wystąpi błąd strony. ![](https://i.imgur.com/52EB66X.png) **Wersje z haszowaniem:** Hashed inverted page table dodaje dodatkowy poziom przed rzeczywistą tabelą stron, nazywany hash anchor table. Ta tabela jest co najmniej tak duża jak page table i odwzorowuje identyfikatory procesów i vpn na wpisy w tabeli. Ponieważ mogą wystąpić kolizje, tabela stron musi mieć tzw łańcuchy. Ponieważ każdy element w łańcuchu musi mapować do tej samej części pamięci fizycznej, łańcuch może być reprezentowany jako sekwencja wpisów w tablicy stron, przy czym każdy wpis wskazuje na następny wpis w łańcuchu. Teraz, aby przetłumaczyć adres wirtualny, identyfikator procesu i numer strony wirtualnej są haszowane, aby uzyskać wpis w hash anchor table. Idziemy dzięki wskaźnikowi do wpisu w page table. Identyfikator procesu i vpn są porównywane z zapisanymi tam. Jeśli się nie zgadzają, proces jest powtarzany z dalszymi wpisami w łańcuchu aż do znalezienia dopasowania. ![](https://i.imgur.com/57H1URC.png) ![](https://i.imgur.com/p72XcIH.png)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.