# Ćwiczenia 12, grupa cz. 10-12, 19 stycznia 2023

###### tags: `SO22` `ć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!**

:::warning
**Uwaga**: Dzisiaj deklarujemy zadania **6 -- 10** z **listy 11** oraz **1 -- 4** z **listy 12**.

Formularz deklaracji **listy 11**:
[https://hackmd.io/@iiuwr-kba/BJROOHTcs/edit](https://hackmd.io/@iiuwr-kba/BJROOHTcs/edit)
:::

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Miriam Bouhajeb | X | X | | X | | | | | |
Kacper Chmielewski | X | X | X | X | X | X | X | | X |
Jan Jankowicz | X | X | X | X | X | X | X | | X |
Jakub Kaczmarek | | | | | | | | | |
Jarosław Kadecki | X | X | X | X | X | X | X | | X |
Zuzanna Kania | X | X | X | X | X | X | X | | X |
Julia Konefał | X | X | | | | | | | |
Daniel Sarniak | X | X | X | X | X | X | X | | X |
Paweł Tkocz | X | X | X | X | | X | X | | X |
Miłosz Urbanik | X | X | X | X | | X | X | | X |
Tomasz Wołczański | X | X | X | X | | X | X | X | X |
Radosław Śliwiński | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Paweł Tkocz
:::

**Zmienne współdzielone** – zmienna jest współdzielona jeśli do co najmniej dwa różne wątki wykonują referencję pewnej jej instancji

**Wyścig** – sytuacja, w której wynik działania programu zależy od przeplotu wykonania wątków (może się pojawić, gdy któryś z wątków modyfikuje zmienną współdzieloną)

| zmienna | współdzielona | wyścig |
| -------- | ------ | -------- |
| `myid` | tak | tak |
| `strtab` | tak | nie |
| `vargp` | nie | nie |
| `cnt` | tak | tak |
| `argc` | nie | nie |
| `argv[0]`| tak | nie |

`myid` – słowo kluczowe __thread, gwarantuje, że każdy wątek będzie miał swoją instancję tej zmiennej. Jednak wątek główny, tworząc w pętli wątki, podaje jako argument funkcji thread() wskaźnik na swoją instancję `myid`. Następnie nowo utworzony wątek wykonuje dereferencję tego adresu i przypisuje wartość do swojej instancji `myid`. Zatem zmienne `myid` utworzonych w pętli wątków nie są współdzielone, ale zmienna `myid` wątku głównego jest. Może to doprowadzić do wyścigu – wątek główny wykona instrukcje z linijek 15 i 16 a zanim nowo utworzony wątek wykona instrukcję z linijki 5, główny wątek ponownie wykona instrukcję z linijki 15. Wówczas dwa lub więcej wątków przypisze sobie takie samo id.

`strtab` – statyczna zmienna globalna, wątki w instrukcji z linijki 7 odczytują wartość z tej tablicy, ale nigdy jej nie modyfikują, zatem nie może dojść do wyścigu

`vargp` – argumenty funkcji są zmiennymi lokalnymi, każdy wątek ma swoje instancje tych zmiennych, zatem nie są one współdzielone miedzy wątkami

`cnt` – zmienna statyczna funkcji thread, zatem wszystkie wątki odwołują się do tej samej instancji. Może prowadzić to do wyścigu, bo w linijce 7 wykonywana jest nieatomowa operacja `++cnt`

`argc` – wątek główny jest jedynym wątkiem, który wykonuje referencję tej zmiennej

`argv[0]` – wykonanie instrukcji z linijki 13 sprawia, że `strtab` wskazuje na to samo miejsce w pamięci co `argv[0]`. Ponieważ zmienna `strtab` jest współdzielona, to `argv[0]` również staje się współdzielone

## Zadanie 2
:::success
Autor: Jarosław Kadecki
:::

Each process has a segment of code, called a critical section,
in which the process may be accessing — and updating — data that is shared
with at least one other process. The important feature of the system is that,
when one process is executing in its critical section, no other process is allowed
to execute in its critical section.

Założenia rozwiązania problemu sekcji krytycznej:

Wyłączenie przerwań - metoda polegająca na uniemożliwieniu obsługi przerwań co odbiera możliwość przełączanie się na inny proces, który mógłby mieć dostęp do zmiennych współdzielonych.


Blokowanie drobnoziarniste - praktyka polegająca na ustawianiu wielokrotnie rozmieszczonych lock'ów na ktrótkich sekcjach krytycznych.

## Zadanie 3
:::success
Autor: Jan Jankowicz
:::
Funkcja compare-and-swap w pseudokodzie:

function T CompareAndSwap(T *actual, T expected, T new):
    T oldValue = *actual;
    if (oldValue == expected):
        *actual <- new
    return oldValue

(aby cała instrukcja była atomowa, między T oldValue = *actual; a *actual <- new; nie może nastąpić zmiana wartości *actual)

Blokada wirująca zaimplementowana przy pomocy compare-and-set:

void lock(spin_t *flag) {
	while (CompareAndSwap(flag, 0, 1));
}

void unlock(spin_t *flag) {
	*flag = 0;
}

>Czemu blokada wirująca nie jest sprawiedliwa (ang. fair)?

Blokada wirująca nie jest sprawiedliwa, ponieważ nie gwarantuje wszystkim wątkom ani dostępu do sekcji krytycznej, ani tym bardziej ustalonej kolejności zajmowania sekcji krytycznej. Może się zdarzyć sytuacja, w której wątek będzie chciał wejść do sekcji krytycznej, ale za każdym razem inny wątek go uprzedza. To zjawisko nosi nazwę zagłodzenia wątku, bo taki wątek nigdy nie nabędzie sekcji krytycznej na wyłączność.

>Uruchamiamy n identycznych wątków. Kolejno każdy z nich wchodzi do sekcji krytycznej, po czym zostaje wywłaszczony przez jądro. Ile czasu zajmie wszystkim wątkom jednokrotne przejście przez sekcję krytyczną – algorytm planisty to round-robin, kwant czasu wynosi 1ms.

Round robin - najprostszy algorytm szeregowania dla procesów w systemie operacyjnym, który przydziela każdemu procesowi równe przedziały czasowe, nie uwzględniając żadnych priorytetów.

Załóżmy, że jeśli sekcja krytyczna jest wolna, to wejście do niej jest natychmiastowe, a czas na przebycie sekcji krytycznej wynosi cs.
Pierwszy wątek, który uzyska czas procesora wejdzie od razu do sekcji krytycznej i zostanie wywłaszczony: 0ms.
Pozostałe n-1 wątków będzie aktywnie oczekiwało w pętli po 1 ms. Łącznie: (n-1)ms.
Aktywne oczekiwanie (n-1) wątków powtórzy się cs/1ms razy, czyli czas potrzebny na przebycie przez jeden wątek sekcji krytycznej z n-1 oczekującymi wątkami wynosi (cs/1ms)*(n-1)ms = (n-1)cs. Dodatkowo trzeba doliczyć czas na przejście samego wątku przez sekcję krytyczną. Łącznie n*cs.
Czas potrzebny na przebycie sekcji przez wszystkie wątki po kolei jest zatem dany równaniem rekurencyjnym T(n) = n*cs + T(n-1), które równoważne jest równości (z szeregu skończonego ciągu arytmetycznego) T(n) = (n(n+1)/2)cs.

## Zadanie 4
:::success
Autor: Miriam Bouhajeb


Aktywne czekanie (spinning, busy waiting) - technika w której proces cały czas sprawdza czy pewien warunek jest spełniony, jak np. wciśnięcie przycisku na klawiaturze czy zwolnienie blokady.

Nie jest ona właściwym sposobem oczekiwania na zwolnienie blokady, gdyż mogłaby wystąpić następująca sytuacja:
Mamy uruchomione dwa wątki na jednym procesorze, gdzie jeden z nich jest w sesji krytycznej i z jakiegoś powodu zostaje przerwany. Drugi wątek próbuje uzyskać blokadę, ale jest ona trzymana przez pierwszy. Więc cały czas aktywnie czeka przez długi czas. W końcu przerwanie w pierwszym wątku się kończy i drugi uzyskuje zwolnioną blokadę. Udało mu się ją uzyskać ale kosztem bardzo długiego czekania, czyli zmarnowaliśmy czas.

Oddanie czasu za pomocą funkcji yield
Yield sprawia, że wątek oddaje procesor innemu wątkowi zamiast ciągle czekać na zwolnienie blokady. Ponieważ wątek może być w 3 różnych stanach (running, ready, blocked), to można sobie wyobrazić że yield sprawia że jeden wątek ze statusu running przechodzi na ready, co sprawia że inny wątek się zmienia na running.

park() usypia wątek
unpark(threadID) budzi wątek.
Te funkcje mogą zostać użyte aby uśpić wątek wołający jeśli próbuje uzyskać trzymaną blokadę a następnie go budzić gdy jest wolna.

Jest to o tyle lepsze od yield, gdyż w yield gdybyśmy mieli np 100 wątków, to w pesymistycznym przypadku każdy z nich by dostał CPU i zrobił yield, a dopiero potem ten wątek co trzyma blokadę by ją zwolnił.

void lock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1)
   //acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1; // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

Można w tej funkcji zauważyć race-condition, tuż przed zawołaniem park(). Jeśli wątek zaśnie, bo nie otrzymał zwolnionej blokady. Jeśli wtedy by wystąpiło przerwanie i inny wątek by zwolnił blokadę to wtedy pierwszy wątek by się nigdy nie obudził. Nazywa się to wakeup/waiting race.

setpark() jest dodatkową funkcją która sprawia, że wątek może zasygnalizować że kładzie się spać (ale jeszcze nie śpi). Jeśli wtedy zostanie przerwany, a inny wątek się obudzi zanim park() zostanie zawołane, to ten park() od razu zostaje zwrócony zamiast kłaść wątek do spania.

queue_add(m->q, gettid());
setpark(); // new code
m->guard = 0;

:::

## Zadanie 5
:::success
Autor: Daniel Sarniak


Warunki konieczne do powstania **zakleszczenia** to:

* **wzajemne wykluczanie** (ang. mutual exclusion) - wątki przejmują wyłączną kontrolę nad zasobami, których potrzebują (np. używając blokady)
* **podtrzymanie własności** (ang. hold-and-wait) - wątki nie zwalniają zasobów im przyznanym, oczekując na kolejne zasoby
* **pierwszeństwo** (ang. no preemption) - zasób zostaje przejęty i nie może zostać odebrany
* **wzajemne oczekiwanie** (ang. circular wait) - istnieje taki cykl: dwa wątki potrzebują jakiegoś zasobu i trzymają inny. Aby jeden wątek otrzymał zasób, musi zwolnić poprzedni, taka sama sytuacja występuje dla drugiego wątku:

Najrostszym sposobem zapobiegania zakleszczenia jest zapobieganie wzajemnemu oczekiwaniu. Aby zapobiec wzajemnemu oczekiwaniu można stworzyć taki program, aby zasoby nie były przejmowane w różnej kolejności w zależności od wykonania programu. Polega to na tym, że jeśli są dwie blokady, L1 oraz L2, to aby zapobiec zakleszczeniu, zawsze L1 będzie wykorzystane przed L2. Dzięki temu dwa wątki nie będą na siebie wzajemnie czekać.

Lockdep nie operuje na pojedynczych blokadach, ale na **klasach
blokad**. Dwie blokady są w tej samej klasie blokad, jeżeli zostały
stworzone przez to samo wystąpienie funkcji inicjującej w kodzie.

spinlock t x, y, z;
    void init a(spinlock t *l) {
    spin lock init(l);
}
    void init b(spinlock t *l) {
    spin lock init(l);
}
void main_init() {
    init a(&x);
    init a(&y);
    init b(&z);
}

W powyższym kodzie spinlocki `x` i `y` są w tej samej klasie, a `z` w
oddzielnej.

Lockdep tworzy dla każdej klasy blokad $L$ listę "przed", która przechowuje klasy blokad będące kiedyklowiek już zablokowane w momencie użycia blokady klasy $L$ i listę "po", która przechowuje klasy blokad będące wywołane w momencie, gdy blokada klasy $L$ jest już zablokowana.
Członkowie tych list reprezentują odpowednio wierzchołki wchodzące i wychodzące do $L$.

W celu sprawdzenia poprawności w momencie użycia blokady klasy $L$ validator sprawdza, czy któraś z aktualnie przetrzymywanych blokad (konkretniej jej klasa) nie znajduje się na liście "po" klasy $L$. Jeżeli tak jest, może wystąpić błąd.
Alogrytm łączy również listy "po" z listą "przed" i za pomocą alogrytmu przechodzącego po grafie sprawdza, czy nie nastąpiło nigdzie zaburzenie kolejności.

Lockdep może zgłosić błąd przy poprawnym programie jeśli nie są spełnione jego założenia dotyczące blokowania, ale nigdy nie zwróci informacji o pporawnym działaniu programu, jeżeli ten jest błędny.

Założenia:
* Niezmienność zasad blokowania w czasie – zasady blokowania dla danego zamka nie mogą się zmieniać w czasie jego istnienia. Nawet w prawidłowych protokołach blokowania walidator wykrywa ryzyko wyścigu danych, jeśli zasady blokowania zależą od stanu obiektu. Na przykład, gdy obiekt ma różne reguły blokowania tworzenia i niszczenia.

* Wspólne reguły blokowania dla tych samych obiektów – drugim ograniczeniem jest to, że wszystkie zamki z jednej klasy zamków muszą podlegać tym samym regułom blokowania. Lockdep nie jest w stanie wykryć różnic w regułach blokowania między poszczególnymi obiektami. Problem ilustruje przykładowy kod poniżej. Istnieje drzewo, a każdy z jego węzłów ma prywatne dane. Programista zdecydował, że węzeł główny musi uzyskać blokady w innej kolejności. Kod nie może spowodować zakleszczenia, ale lockdep zgłosi to jako błąd.

struct node_data {
    ...
    mutex_t lock;
};
struct tree_node {
    ...
    struct node_data *data;
    mutex_t lock;
};
void lock_tree_node_and_storage(struct tree_node *A) {
    if (is_root(A)) {
        mutex_lock(A->lock);
        mutex_lock(A->data->lock);
    } else {
        mutex_lock(A->data->lock);
        mutex_lock(A->lock);
    }
}

:::

## Zadanie 6
:::success
Autor: Zuzanna Kania

* wątek 1 ustawia `blocked[1]=true`
* wątek 1 wchodzi do pętli w linii 7 (`turn==0`)
* wątek 1 omija pętlę w linii 8 (`blocked[0]==false`)
* wątek 0 ustawia `blocked[0]=true`
* wątek 0 omija pętlę w linii 7 (`turn==0`)
* wątek 0 wchodzi do sekcji krytycznej
* wątek 1 ustawia `turn=1`
* wątek 1 wychodzi z pętli w linii 7 (`turn==1`)
* wątek 1 wchodzi do sekcji krytycznej

Wzajemne wykluczenie nie zachodzi - dwa wątki są w sekcji krytycznej!
:::

## Zadanie 7
:::success
Autor: Miłosz Urbanik
:::

shared boolean blocked [2] = { false, false };
shared int turn = 0;
 
void P (int id) {
    while (true) {
        blocked[id] = true;
        turn = 1 - id; // turn = other
        while ( blocked[1 - id] && turn == (1 - id)) // while(blocked[other] && turn == other)
           continue;
        /* put code to execute in critical section here */
        blocked[id] = false;
      }
 }

 void main() { parbegin (P(0), P(1)); }

Proces rozpoczyna wykonywanie sekcji krytycznej, gdy w lini 8 warunek jest fałszywy.
Załóżmy niewprost, że algorytm nie jest poprawny i oba procesy znalazły się w sekcji krytycznej.
Bez straty ogólności załóżmy, że P(0) jako pierwsze weszło do sekcji krytycznej, wykonując wcześniej:

blocked[0] = true

turn = 1

Przypadki wejścia do CS przez P0:

1. blocked[1 - id] == false, czyli blocked[1] == false
2. turn != (1 - id), czyli turn == 0
3. Koniunkcja powyższych

Następnie P1, próbuje wejść do sekcji krytycznej. Rozważmy przypadki

1. blocked[1 - id] == false, czyli blocked[0] = false
2. turn != (1 - id), czyli turn == 1
3. Koniunkcja powyższych

Ad 1.1 Jeśli P0 w CS to blocked[0] == true, czyli pierwszy warunek nie może zostać spełniony. P1 nie może modyfikować blocked[0]

Ad 1.2 Jeśli turn == 1, P0 weszło do CS z blocked[1] == false, zatem P1 musiało być przed linią 6, gdzie natępuje przypisanie blocked[1] == true. P1 wchodząc do CS musi przejść przez linię 7, tym samym uniemożliwiając sobie wejście.
Sprzeczność
Zatem oba wątki nie mogą jednocześnie znaleźć się w sekcji krytycznej.

## Zadanie 8
:::success
Autor: Tomasz Wołczański
:::

Rozważmy następujące wykonanie:
1. Po zainicjowaniu semafora `count` zostaje zmniejszone do 0 przez wątki wywołujące `csem::P`.
2. Wątek $A$ wywołuje `csem::P` i zostaje zatrzymany tuż przed wykonaniem `P(delay)`. W tym momencie wartość zmiennej `count` to -1.
3. Wątek $B$ wywołuje `csem::P` i zostaje zatrzymany tuż przed wykonaniem `P(delay)`. W tym momencie wartość zmiennej `count` to -2.
4. Wątek $C$ wywołuje `csem::V`. Po zakończeniu wywołania wartość zmiennej `count` to -1, a wartość semafora binarnego `delay` to 1.
5. Wątek $D$ wywołuje `csem::V`. Po zakończeniu wywołania wartość zmiennej `count` to 0, a wartość semafora binarnego `delay` to nadal 1.
6. Wątek $A$ zostaje wznowiony, wywołuje `P(delay)`, zmniejszając wartość `delay` do 0 i powraca z `csem::P`.
7. Wątek $B$ zostaje wznowiony, wywołuje `P(delay)` i zostaje uśpiony, bo wartość `delay` to 0.
8. Wątek $C$ wywołuje `csem::P` i zostaje uśpiony w wywołaniu `P(delay)`, bo wartość `delay` to 0.

Po wykonaniu tych kroków wartość `count` to -1, ale liczba uśpionych wątków to 2.

## Zadanie 9
:::success
Autor: Jarosław Kadecki

:::

Błąd wykonania w liniach 6 i 13
P0 - producent
P1 - konsument
n = 1
Kolejka pusta

P0: 3,4,6
Kolejka pełna
P0: 7,8,3,4,5
P1: 11, 13, 14
P0: 2,3,4,6
Kolejka pełna
P0: 7,8 (lost wake-up), 3,4,5
P1: 15
P0: 6

Producent dokłada item pomimo,
że kolejka jest pełna.

Zakleszczenie w liniach 5 i 12
P0 - producent
P1 - konsument
n = 1
Kolejka pusta

P0: 3,4
P1: 11
P0: 6
Kolejka pełna
P0: 7, 8 (lost wake-up), 3, 5
P1: 12