# Lista 11, 16 czerwca 2021

###### tags: `sju21` `ćwiczenia`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie w trakcie dyskusji (co najwyżej jedno!) oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| |11-1 |11-2 |11-3 |11-4 |11-5 |11-6 |
| ---------------------:| --- | --- | --- | --- | --- | --- |
| Jacek Bizub | |==X==| | | | X | 2
| Wojciech Jasiński | | X | | |==X==| | 2
| Artur Juraszek | | | | | | | 0
| Michał Myczkowski | | | | | | | 0
| Michał Odorczuk | | | | | | | 0
| Damian Ratajski | | | | | | | 0
| Łukasz Siudek | | | | | | | 0
| Błażej Sowa | | | | | | | 0
| Andrzej Turko | X | X | X | X | X |==X==| 6
| Maksymilian Zawartko | |==X==| | X | X | | 3
:::

## Zadanie 11-1

:::info
Autor: Andrzej Turko
:::

**mmap** -- używa pmap_enter, żeby stworzyć mapowanie
**munmap** munmap używa pmap_remove -- usuwa mapowanie
**mprotect** -- pmap_protect (zmiana uprawnień)

**fork** -- pmap_page_protect (implementacja copy-on-write -- u rodzica), pmap_activate / pmap_deactivate (przełączanie przestrzeni adresowych)
**execve** -- pmap_activate / pmap_deactivate (przełączanie przestrzeni adresowych)

**demon stronnicowania** (pageout demon) -- używa pmap_page_remove, żeby oznaczyć dla wszystkich przestrzeni wirtualnych, że tej strony nie ma już w RAM.

pmap_activate / pmap_deactivate muszą wyczyścić całe TLB.
pmap_remove musi usuwać pojedyncze zapisy.

Trzeba utrzymywać listę pv_entry odnoszących się do danej ramki po to, aby móc w nich zaznaczyć fakt wycofania ramki z pamięci systemowej.

Użycie listy pv_entry ([link](https://mimiker.ii.uni.wroc.pl/source/more/NetBSD/sys/uvm/pmap/pmap.c?refs=mdpg_first):
* pmap_page_remove -- wołane przy usuwaniu ramki z pamięci fizycznej -- usuwa tę stronę ramkę z mapowań fizycznych
* pmap_page_protect -- obniża uprawnienia dla wszystkich mapowań danej strony

## Zadanie 11-2

:::info
Autor: Jacek Bizub
:::

> Zarządzanie buforem translacji adresów komplikuje się na maszynach SMP (ang.Shared Memory Processor).

> Czemu zawartość TLB poszczególnych rdzeni nie jest automatycznie synchronizowana?

Bo to drogie.

> Kiedy zachodzi potrzeba ich synchronizacji?

Synchronizację między procesorami trzeba zrobić kiedy korzystają ze wspóldzielonych danych. Dzieje się tak wtedy kiedy np.
- zmiana dotyczy przestrzeni jądra
- mamy wspóldzieloną pamięć między procesami
- wielowątkowy proces jest uruchomiony na kilku procesorach

> Wyjaśnij działanie prostego algorytmu zestrzeliwania wpisów TLB (ang.TLBshootdown) z systemu Mach.


## Zadanie 11-3

:::info
Autor: Andrzej Turko
:::

[alloc](https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/vm/vm_phys.c?r=80f39bd9#vm_phys_alloc_freelist_pages) (862-874): iterujemy się po kolejnych poziomach freelist zaczynając od podanego (dostatecznie duże bloki). Gdy znajdziemy niepustą listę:
1. Zwracamy pewien prefiks znalezionego bloku.
2. Pozostałą pamięć rozbijamy na mniejsze bloki i umieszczamy we freelistach. Pierwszy blok jest takiego rozmiaru, jak ten zaalokowany, każdy następny jest dwa razy większy (aż będzie równy połowie znalezionego wolnego bloku). Te nowe bloki 'zakrywają' stary wolny blok od lewej do prawej.

[free](https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/vm/vm_phys.c?r=80f39bd9#vm_phys_free_pages): zwalniamy blok stron fizycznych długości potęgi dwójki złączając go z innymi wolnymi blokami wewnątrz segmentu.
1. Iterując się po rosnących rzędach bloków znajdujemy naszego bliźniaka i jeśli jest wolny (rozpoznajemy po wartości order), usuwamy go z odpowiedniej freelisty i powiększamy nasz blok.
2. Wpisujemy się na odpowiednią freelistę.

## Zadanie 11-4

:::info
Autor: Maksymilian Zawartko
:::

vmem to algorytm zarządzania obszarami adresów (przedziałami liczb całkowitych), a nie bezpośrednio pamięcią.

`vmem_xalloc` przeszukuje listy boundary tagów, aż znajdzie odpowiedni element. W strategii first fit sprawdza tylko pierwszy bt.

`vmem_xfree`, podobnie jak `vmem_xalloc` pomija sprawdzenie czy pamięć należy do quantum cache. Przy zwalnianiu adres początkowy jest haszowany, wyszukiwany w hash list i sprawdzana jest zgodność rozmiaru.

Motywacją do wprowadzenia nowego algorytmu zarządzania przestrzenią adresową do jądra była nieefektywność starego algorytmu.

Argumenty `vmem_xalloc`:
* `vmem_t *vm` - https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/kern/subr_vmem.c?r=80f39bd9#136
* `vmem_size_t size0` - rozmiar pamięci do zaalokowania
* `int flags` - https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/sys/malloc.h?r=80f39bd9#55

## Zadanie 11-5

:::info
Autor: Wojciech Jasiński
:::

* płyty (slab)
- trzyma elementy jednakowego rozmiaru
- nagłówek:
- w zarządzanej pamięci lub zewnętrzny (optymalizacja zależnie od rozmiaru)
- maska bitowa zajętych pól
- liczba zajętych pól
- rozmiar: wielokrotność strony
* antałki (keg)
- trzymają pełne/częściowe/puste płyty i alokują gdzie trzeba
- zwalniają płyty na żądanie (pośrednio od demona stronicowania)
* wiaderka (bucket), magazynki
- lokalne pule obiektów procesora
- przyspieszają dostęp przez cache CPU
- trzymają "obiekty" do użycia (lokalizacje pamięci gdzie można zmieścić obiekt)
- z magazynka możemy przekazać obiekt (lokalizację) (jeśli jest) albo go do niego zwrócić (jeśli jest miejsce)
- rozmiar trzymany w nagłówku → dzięki temu alokator strefowy może zmieniać rozmiar na bieżąco
* alokator strefowy
- uzupełnianie magazynków
Kiedy trzeba (z winy konkretnego CPU) alokor strefowy utworzy nowy magazynek (alokowany w strefie magazynków) i zażąda od odpowiedniego antałka wypełnienia go
- zwalnia pamięć kiedy demon stronicowania jej zażąda
- przechodzi przez posiadane pełne magazynki i każe antałkowi zwrócić obiekty
- antałek zwraca obiekty do płyty i pełne (pełne wolnego miejsca) zwraca do `vmem`
- demon stronicowania może zażądać zmniejszenia rozmiaru magazynków
- a nawet spłukania pamięci podręcznej wszystkich CPU
* Czemu każdy procesor posiada zestaw dwóch magazynków?
* "każdy procesor"
- żeby uniknąć blokowania się wielu procesorów na tej samej blokadzie
* "dwóch magazynków"
- zapewniają możliwość alokacji i zwolnienia przynajmniej M obiektów zanim zajdzie potrzeba odwołania do alokatora strefowego (z blokadą dzieloną między CPU)
- M = <rozmiar kubełka>
- jeśli magazynek jest dwa razy większy, będziemy wymieniać je co najmniej dwa razy rzadziej. Tak możemy kontrolować częstość użycia antałka (używamy go przy uzupełnianiu magazynków)
- kiedy oba stają się pełne lub oba stają się puste, wymieniamy jeden na przeciwny
- (chyba moglibyśmy trzymać półpełne magazynki w zapasie i używać jednego, ale to raczej gorsze rozwiązanie)
* W jaki sposób system dobiera dynamicznie rozmiar magazynków?
Kiedy alokator strefowy chce pobrać pamięć od antałka, najpierw próbuje założyć blokadę nieblokująco. Jeśli to się nie powiedzie, rejestruje to i dopiero wtedy blokuje się. Stąd możemy wnioskować, czy nie blokujemy się za często na antałku.
* W trakcie przydziału lub zwalniania bloków procesor może wystrzelać obydwa magazynki – co się wtedy dzieje? (nie ma magazynków w strefie, antałek nie posiada płyt z miejscem)
Jesteśmy w alokatorze strefowym:
1. alokujemy nowy magazynek ze strefy magazynków (co się dzieje gdy ten scenariusz zaaplikujemy rekurencyjnie do strefy magazynków?)
2. każemy antałkowi go wypełnić
3. antałek zagląda do płyt i widzi że nie mają miejsca
4. antałek pyta `vmem` o nową płytę
5. antałek alokuje obiekty na nowej płycie (/nowych płytach) i przenosi ją na listę częściowo użytych/pustych (pusta = nie ma wolnego miejsca) płyt
6. zwracamy pełen magazynek

## Zadanie 11-6

:::info
Autor: Jacek Bizub
:::

> Przypomnij do czego służą `vm_object `i `obiekty przesłaniające` (ang.shadow object)? Jak implementacja wywołań systemowych fork(2) i mmap(2) modyfikuje łańcuchy obiektów przesłaniających dla odwzorowań prywatnych? Na podstawie ustępu „Collapsing of Shadow Chains”z [4,§6.5] zreferuj algorytm skracania łańcuchów obiektów przesłaniających. Kiedy zachodzi potrzeba jego wykonania?

`vm_object` to reprezentacja pliku w wirtualnej przestrzeni adresowej.

`obiekty przesłaniające` służą do "wirtualnego nadpisywania" pojedyńczych stron plików. Izolują też widoczność zmian dla poszczególnycn procesów.

Kiedy proces chce dostać daną stronę to przegląda kolejno cały łancuch (na końcu będzie właściwy vm_object) aż do pierwszego trafienia.


Kiedy proces robi forka to mamy współdzieloną przestrzeń adresową, która jest `copy-on-write` i w momencie zapisu tworzony jest odpowiedni obiekt przesłaniający.

Podobnie dzieje się w wypadku zmapowania pliku do przestrzeni adresowej procesu w trybie "private" ponieważ nie chcemy, żeby zmiany były zapisywane na dysk ani widoczne dla innych procesów.