# Ćwiczenia 14, grupa cz. 12-14, 23. czerwca 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 | 10 | 11 |
| ---------------------- | ----- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | | | | | | | | | | | |
Adam Ciężkowski | | | | | | | | | | | |
Jacek Długopolski | | | | | | | | | | | |
Jakub Fila | | | | | | | | | | | |
Krzysztof Grynkiewicz | | | | | | | | | | | |
Michał Hetnar | | | | | | | | | | | |
Hubert Jabłoński | | | | | | | | | | | |
Antoni Kamiński | | | | | | | | | | | |
Paweł Karaś | | | | | | | | | | | |
Emil Kisielewicz | | | | | | | | | | | |
Kacper Komenda | x | | | | | | | | x | x | x |
Filip Komorowski | | | | | | | | | | | |
Piotr Piesiak | | | | | | | | | | | |
Artur Krzyżyński | | | | | | | | | | | |
Patryk Mazur | | | | | | | | | | | |
Szymon Mleczko | x | x | | x | | x | x | | | | |
Michał Mróz | | | | | | | | | | | |
Dominik Olejarz | | | | | | | | | | | |
Magdalena Słonińska | | | | | | | | | | | |
Oleś Kulczewicz | | | | | | | | | | | |
Adam Szeruda | | | | | | | | | | | |
Kamil Tasarz | | | | | | | | | | | |
Michał Zieliński |==X== | X | X | X | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Michał Zieliński
:::

### Polecenie
Rozważmy implementację metody increment() atomowego
licznika, opierającą się na instrukcji maszynowej
compare_and_swap. W którym z poniższych scenariuszy użycie tak
zaimplementowanego licznika będzie poprawne, a w którym nie.

a) grupa procesów wykonuje w nieskończonej pętli instrukcje, jedną z nich jest wywołanie metody increment() na współdzielonym liczniku. Dla każdej liczby naturalnej k, każdy proces musi wykonać przynajmniej k obrotów swojej pętli.

b) grupa procesów wykonuje w pętli instrukcje, jedną z nich jest inkrementacja licznika, ale tym razem każdy proces wykonuje n obrotów swojej pętli, gdzie n jest ustaloną liczbą naturalną.

### Rozwiązanie
#### Nasze instrukcje
##### increment

void increment(atomic_int *v)
{
    int temp;
    do 
    {
        temp = *v;
    }
    while (temp != (compare_and_swap(v,temp,temp+1));
}

###### compare_and_swap

int compare_and_swap(int *value, int expected, int new_value)
{
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

▪ Properties
• Executed atomically
• Returns the original value of passed parameter value
• Set the variable value the value of the passed parameter
new_value but only if *value == expected is true. That is, the
swap takes place only under this condition.
#### Wnioski
Taka implementacja daje wzajemne wykluczanie, dzięki atomowości compare_and_set.
Jakaś próba inkrementacji przy pomocy compare_and_set nie uda się (i proces dalej będzie się kręcić w pętli) tylko jeżeli inny proces dokona inkrementacji zanim ta próba się skończy. Oznacza to, że nie może dojść do deadlocka.
#### Podpunkty
##### a
każdy proces może wykonać increment nieskończenie wiele razy. W naszym kodzie nie mówimy kto kiedy może dokonać inkrementacji. Mamy do czynienia z sytuacją, "kto szybszy (nie pierwszy) ten lepszy". Może być tak, że jakiś proces nigdy nie zdąży dokonać inkrementacji, bo inne ciągle będą się przed niego "wciskać". Mamy zatem brak ograniczonego czekania i może dojść do zagłodzenia.
W tym scenariuszu użycie tak zaimplementowanego licznika NIE będzie poprawne.
##### b
każdy proces wykonuje increment skoczończoną liczbę razy, a nie może dojść do zakleszczenia. Oznacza to, że koniec końców każdy wątek wykona n wywołań increment.
W tym scenariuszu użycie tak zaimplementowanego licznika będzie poprawne.
## Zadanie 2
:::success
Autor: Szymon Mleczko
:::

int lock=false;
void increment(int *v)
{
    while(test_and_set(&lock));
    *v++;
    lock=false;
}

## Zadanie 3
:::success
Autor: Michał Zieliński
:::
### Polecenie

Przypomnij semantykę instrukcji wait() i signal()
semafora. Zaimplementuj semafor używający aktywnego czekania
(ang. busy waiting), przy pomocy jednej z dwóch poznanych
instrukcji maszynowych.
### Rozwiązanie

#### mutex

locked = false;
lock()
{
    while(test_and_set(locked))
}
unlock()
{
    locked = false
}

#### semafor

value
a = mutex(value>0)
b = mutex(true)

wait()
{
    a.lock();
    b.lock();
    value --;
    if value > 0
        a.unlock();
    b.unlock();
}

signal()
{
    b.lock();
    value++;
    if value == 1
        a.unlock()
    b.unlock
        
}

## Zadanie 4
:::success
Autor: Szymon Mleczko
:::
Monitor jest to obiekt który w sposób automatyczny ustawia semafory, pozwala to na zmniejszenie liczby lini kodu, przez co lizczby błędów, w przypadku programów wielowątkowych.
Z uwagi na implemenntację semaforów zapewniamy wzajemne wykluczenie jako że monitor pilnuje wykonywania jedynie 1 procesu
a) bez zimennych warunkowych możliwe jest że proces zostanie zajęty przez 1 wątek który następnie czekać będzie na jakieś dane przed zwolnieniem blokady.
B) powyższy przypadek można rozwiązać za pomocą dodatkowych zminnych warujnkowych które pozwolą na dodatkowe warunki zwolnienia procesu.

## Zadanie 5
:::danger
Autor:
:::

## Zadanie 6
:::success
Autor: Szymon Mleczko
:::

## Zadanie 7
:::success
Autor: Szymon Mleczko
:::

## Zadanie 8
:::success
Autor: Kacper Komenda
:::

Reader writers to problem, gdzie pewien fragment kodu może być wykonywany w dwóch przypadkach:
a) dowolna liczba readerów go wykonuje
b) jest wykonywany tylko przez jednego writera
Dzieje się tak, bo tylko writer może zmodyfikować strukturę.
W rozwiązaniu głodzącym writerów może być tak, że readerzy po wejściu do sekcji będą pojawiać się w nieskończoność, a wtedy nie dopuszczą żadnego writera do sekcji. W rozwiązaniu niegłodzącym musimy dopuścić writera po pewnym momencie.


W działaniu writera, gdy ten wejdzie do pokoju, to blokuje następnych readerów przed wchodzeniem.

## Zadanie 9
:::success
Autor: Kacper Komenda
:::

Bariera jest wtedy gdy chcemy aby, dana część kodu wykonała się dopiero po tym jak wszystkie wątki wykonają wcześniej ustalony kod.

Przypuśćmy, że mamy takie fragmenty programu:

A
.
B

Wtedy szybsze wątki muszą poczekać, aż pozostałe przejdą przez część A, dopiero wtedy można wstąpić do części B.

W rozwiązaniu najpierw wątki pojedynczo zwiększają licznik (zapewnione mutexem), następnie blokują się na barierze. Gdy n-ty wątek wykona incrementację licznika, to odblokuje on wątek czekający na sygnał. Później kolejno odblokowane zostaną pozostałe wątki

## Zadanie 10
:::success
Autor: Kacper Komenda
:::
W barierze wznawialnej mamy ten sam problem, tylko takich fragmentów (barier) kodu, na których wątki muszą czekać może być więcej.

A
.
B
.
C
....


W rozwiązaniu mamy dwa countery, jeden incrementujący numer i drugi dekrementujący.
Najpierw wątki blokują się na barierze (turnstile) i czekają aż n-ty wątek ukończy fragment kodu. Gdy tak się stanie (counter w mutexie ustawi się na n), to odblokowuje następną część kodu, a blokuje tę po niej i tak dalej w zależności ile barier ustawił programista. Warto zwrócić uwagę na dwa liczniki dekrementujący i inkrementujący i dwie zmienne turnstile, to wystarcza aby zaimplementować k takich barier, nie potrzeba k liczników i k zmiennych.

## Zadanie 11
:::danger
Autor: Kacper Komenda
:::