# SO - Lista 12
###### tags: `SO`
## Zadanie 1
Zmienna współdzielona jest to zmienna, do której instancji ma dostęp wiele wątków jednocześnie
Zmienna będąca źródłem wyścigów to zmienna, która jest w pewnym momencie programu edytowana przez kilka wątków na zmianę (Przeplot sekcji krytycznej)
| Zmienna | współdzielona | źrodło wyścigów |
|---------|---------------|------------------|
|myid | TAK | TAK |
|strtab | TAK | NIE |
|vargp | NIE | NIE |
|cnt | TAK | TAK |
|argc | NIE | NIE |
|argv[0] | NIE | NIE |
## Zadanie 2
Sekcja krytyczna - Ciąg instruktrukcji, które powinny być wykonane nieprzerywalnie dla każdego wątku
1. **Mutual exclusion.** If process $P_i$ is executing in its critical section, then no other processes can be executing in their critical sections. - Jeśli jeden proces jest w sekcji krytycznej, to żaden inny nie może być w swojej sekcji krytycznej
2. **Progress.** If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely - Jeżeli żaden proces nie wykonuje swojej sekcji krytycznej, to o wejście do sekcji ubiegają się procesy nie wykonujące pozostałej części programu. Wybór nie może być odłożony w nieskończoność.
3. **Bounded waiting.** There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. - żaden proces nie może czekać w nieskończoność na swoją sekcję krytyczną
```
while (true) {
entry section
critical section
exit section
remainder section
}
```
Wyłączanie przerwań nie ma sensu w środowiskach multiprocesorowych, bo jest wolne. Przesyłanie wiadomości o wyłączeniu przerwań od każdego z procesorów jest kosztowne
## Zadanie 3
```c=
def function CompareAndSwap(int* p, int old, int new):
if (*p == old) {
*p = new;
}
return *p;
```
```c=
typedef int spin_t;
void lock(spin_t *lock) {
while (CompareAndSwap(lock, 0, 1) == 1); // spin
}
void unlock(spin_t *lock) {
*lock = 0;
}
```
Ile czasu? $O(n^2)$
## Zadanie 4
Aktywne czekanie - Marnowanie czasu procesora
``` c
void init() {
flag = 0;
}
void lock() {
while (CompareAndSwap(flag, 0, 1) == 1)
yield(); // give up the CPU
}
void unlock() {
flag = 0;
}
```
"Let us now consider the case where there are many threads (say 100) contending for a lock repeatedly. In this case, if one thread acquires the lock and is preempted before releasing it, the other 99 will each call lock(), find the lock held, and yield the CPU. Assuming some kind of round-robin scheduler, each of the 99 will execute this run-and-yield pattern before the thread holding the lock gets to run again. While better than our spinning approach (which would waste 99 time slices spinning), this approach is still costly; the cost of a context switch can be substantial, and there is thus plenty of waste."
```c
int TestAndSet(int *ptr, int new) {
int old = *ptr; // fetch old value at ptr
*ptr = new; // store ’new’ into ptr
return old; // return the old value
}
typedef struct __lock_t {
int flag;
int guard;
queue_t *q;
} lock_t;
void lock_init(lock_t *m) {
m->flag = 0;
m->guard = 0;
queue_init(m->q);
}
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());
//setpark(); // new code
m->guard = 0;
park();
}
}
void unlock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1); //acquire guard lock by spinning
if (queue_empty(m->q))
m->flag = 0; // let go of lock; no one wants it
else
unpark(queue_remove(m->q)); // hold lock (for next thread!)
m->guard = 0;
}
```
Problem bez setpark() jest następujący:
1. Dodajemy proces do kolejki
2. oddajemy kontrole
3. wywołany jest unpark
4. Proces zostaje zdjęty z kolejki
5. Wraca przed parkiem i idzie spać
## Zadanie 5
### Conditions for Deadlock
Four conditions need to hold for a deadlock to occur:
• **Mutual exclusion**: Threads claim exclusive control of resources that
they require (e.g., a thread grabs a lock).
• **Hold-and-wait**: Threads hold resources allocated to them (e.g., locks
that they have already acquired) while waiting for additional resources (e.g., locks that they wish to acquire).
• **No preemption**: Resources (e.g., locks) cannot be forcibly removed
from threads that are holding them.
• **Circular wait**: There exists a circular chain of threads such that
each thread holds one more resources (e.g., locks) that are being
requested by the next thread in the chain.
### Prevention
#### Circular wait
Probably the most practical prevention technique (and certainly one that
is used frequently) is to write your locking code such that you never induce a circular wait. The way to do that is to provide a total ordering on
lock acquisition. For example, if there are only two locks in the system (L1
and L2), we can prevent deadlock by always acquiring L1 before L2. Such
strict ordering ensures that no cyclical wait arises; hence, no deadlock.
**W skrócie* - dodajemy warunek numerowania blokad, tak aby występowały one w jakiejś ustalonej kolejności
#### Hold-and-wait
Możemy tego uniknąć gwarantując wykonywanie wszystkich blokad po sobie, atomowo - unikamy nakładania się blokad.
```c=
lock(prevention);
lock(L1);
lock(L2);
...
unlock(prevention);
```
#### No Preemption
Bierzemy blokady tylko jak są dostępne. Jezeli nie mozmy uzyskac blokady, to zwalniamy tą którą posiadamy, by nie blokować zasobów dla innych procesów.
```c
top:
lock(L1);
if (trylock(L2) == -1) {
unlock(L1);
goto top;
}
```
Problem - livelock, procesy moga w tym samym czasie prosic o blokade i oba blokady nie dostac. I tak ciągle. Solution-random delay
#### Mutual exclusion
Mozemy przygotowac takie st
```c
void AtomicIncrement(int *value, int amount) {
do {
int old = *value;
} while (CompareAndSwap(value, old, old + amount) == 0);
}
```
## Zadanie 6
turn = 1
blocked = {true, true}
| P 0 | P 1 |
|--------------------------|--------------------------|
| P(0) | |
| - | P(1) |
| - | blocked[1] = true; |
| - | pętla (turn != 1) |
| - | pętla (blocked[0]) |
| blocked[0] = true | - |
| petla(turn==0) | - |
| CRITICAL | - |
| - | turn = 1 |
| - | CRITICAL |
## Zadanie 7
**Mutual exclusion**
```P0``` and ```P1``` can never be in the critical section at the same time. If ```P0``` is in its critical section, then ```blocked[0]``` is ```true```. In addition, either ```blocked[1]``` is ```false``` (meaning that ```P1``` has left its critical section), or turn is 0 (meaning that ```P1``` is just now trying to enter the critical section, but graciously waiting), or ```P1``` is at label ```P1_gate``` (trying to enter its critical section, after setting ```flag[1]``` to ```true``` but before setting turn to 0 and busy waiting). So if both processes are in their critical sections, then we conclude that the state must satisfy ```flag[0]``` and ```flag[1]``` and ```turn = 0``` and ```turn = 1```. No state can satisfy both ```turn = 0``` and ```turn = 1```, so there can be no state where both processes are in their critical sections. (This recounts an argument that is made rigorous in.[5])
**Progress**
Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. Note that for a process or thread, the remainder sections are parts of the code that are not related to the critical section. This selection cannot be postponed indefinitely. A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.
**Bounded waiting**
Bounded waiting, or bounded bypass, means that the number of times a process is bypassed by another process after it has indicated its desire to enter the critical section is bounded by a function of the number of processes in the system. In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.
## Zadanie 8
mutex - semafor binarny, ogłaszający blokadę
delay - Jest ustawiany jeśli nie ma wolnych miejsc
count - Liczba uśpionych procesów (jeśli -1 to jeden proces śpi)
P(mutex) - nałożenie blokady
V(mutex) - zdjęcie blokady
mutex=1
delay=0
count=2
|P1 | P2 | P3 | P4 |
|-------------|--------------|--- | -- |
|P(mutex) | | | |
|count =1 | | | |
|V(mutex) | | | |
|CRITICAL | | | |
| | P(mutex) | | |
| | count=0 | | |
| | V(mutex) | | |
| | Critical | | |
| | | P(mutex) | |
| | | count=-1 | |
| | | V(mutex) | |
| | | P(delay) | |
| | | | P(mutex)
| | | | count=-2
| | | | V(mutex)
| | | | P(delay)
|P(mutex) | |
|count=-1 | |
|V(delay) | |
|V(mutex) | |
| | P(mutex) | |
| | count=0 | |
| | V(delay) | |
| | V(mutex) |
| | | P(mutex)
| | | count=1
| | | V(mutex)
## Zadanie 9
a.
1. błąd w 13 linijce
Dla n = 1;
6 pushujemy item - kolejka jest pełna
7 Wykonujemy 7 linijkę - nie jest pusta
-> oddajemy kontrolę
13 consumer ściąga element z kolejki
14/15 budzi producenta
11 idzie dalej
12 idzie spać (bo pusta)
-> oddajemy kontrole
8 Producer wykonuje 8 linijke - budzi konsumenta
**13** pop na pustej kolejce
2. błąd w 6 linijce
Dla n = 1
13 popujemy item - kolejka jest pusta
14 wchodzimy w if w 14 linijce
-> oddajemy kontrolę
6 producent dodaje do kolejki element
7/8 budzi konsumenta
9/10 producent idzie spac (bo pelna)
-> oddaje kontrole
15 konsument wykonuje 15 linijke - budzi producenta
**6** producent push na pelnej kolejce
b.
Dla n = 1;
Producent wchodzi w ```if queue.full()```
Przekazuje kontrolę consumerowi
consumer ściąga item
budzi producenta
Producent od razu zasypia
Kolejka jest pusta, więc consumer idzie spać
Sign in with Wallet
Connect another wallet