# Lista 12
###### tags: `SO2022`

## Deklaracja
:::spoiler

| Zadanie | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|-----------|---|---|---|---|---|---|---|---|---|
|Deklaracja |:heavy_check_mark:|||||:heavy_check_mark:|||:heavy_check_mark:|

:heavy_check_mark:
:::

## Zadanie 1

**Zmienne współdzielone** – zmienna jest współdzielona jeśli różne wątki mają dostęp do tej samej zmiennej

**Wyścig** – sytuacja, w której wynik działania programu zależy od przeplotu wykonania wątków

| 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

**Sekcja krytyczna** – fragment kodu programu, w którym korzysta się z zasobu dzielonego, a co za tym idzie, w danej chwili może być wykorzystywany przez co najwyżej jeden wątek.

In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to do so is known as a critical section or critical region. This protected section cannot be entered by more than one process or thread at a time

**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** - metoda w której staramy się jak najbardziej minimalizować sekcje krytyczne, tak aby było ich wiele, ale dość małych. Pozwala to na większe uwspółbieżnienie programu zgodnie z prawem Amdahla.

## Zadanie 3

**Spinlock (wirująca blokada)** – sposób realizacji synchronizacji międzyprocesowej, w którym oczekiwanie na zwolnienie blokady polega na ciągłym badaniu jej stanu. Spinlock działa więc na zasadzie aktywnego oczekiwania, tj. zużywa czas procesora, wykonując cały czas pustą pętlę.



## Zadanie 4

## Zadanie 5

lockdep: https://www.kernel.org/doc/Documentation/locking/lockdep-design.txt
## Zadanie 6

**Wzajemne wykluczenie** - zasada według której co najwyżej jeden wątek może w tym samym czasie przebywać w danej ścieżce krytycznej

Załóżmy, że mamy dwa wątki A i B, gdzie początkowo turn = a; (tj. a.id = 0, b.id = 1), oraz, że kolejność wykonywania instrukcji będzie jak poniżej:

B.write(blocked[B] = true)
B.read(turn = A), spełniony warunek z linii 7, wchodzimy do while
B.read(blocked[A] = false), niespełniony warunek z linii 8
###### następna będzie linia 10, B zostaje przed tym wywłaszczone

A.write(blocked[A] = true)
A.read(turn = A), niespełniony warunek z linii 7
**CS(A)** (tj. A wchodzi do ścieżki krytycznej)
###### A zostaje wywłaszczone

B.write(turn = B)
B.read(turn = B), niespełniony warunek z linii 7
**CS(B)**

sekwencja wykonania instrukcji przedstawiona powyżej prowadzi do wejścia obu wątków do ścieżki krytycznej

## Zadanie 7


## Zadanie 8

niech v = 0
count = v = 0

A P(mutex) (linijka 14)
A count-- (-1)
A if(-1 < 0) spełnione
A V(mutex)

B P(mutex) (linijka 14)
B count-- (-2)
B if(-2 < 0) spełnione
B V(mutex)

C P(mutex) (linijka 24)
C count++ (-1)
C if(-1 <= 0) spełnione
C V(delay)

D P(mutex) (linijka 24)
D count++ (0)
D if(0 <= 0) spełnione
D V(delay)

A P(delay) (linijka 18)

D ciągle V(delay)

B P(delay) (linijka 18)

mamy teraz count = 0 i 4 uśpione wątki

to tez jest spoko, tez na 4 watkach, down to nasze P, up to nasze V
a tu rozw problemu

## Zadanie 9

* a)
* Wykonujemy if z linii 7/14
* Przełączamy wątek i opróżniamy/zapełniamy kolejkę po czym usypiamy wątek
* Wracamy do pierszego wątku i budzimy drugi wątek
* Drugi wątek prubuje użyć ustej/pełnej kolejki
* ERROR
* b)
* Wykonujemy if z linii 4/11
* Przełączamy wątek i opróżniamy/zapełniamy kolejkę po czym usypiamy wątek
* Wracamy do pierszego wątku i zasypiamy
* Oba wątki śpią