---
# System prepended metadata

title: 'Ćwiczenia 14, grupa cz. 12-14, 23. czerwca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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	
:::
![](https://i.imgur.com/RjqbD9a.jpg)

```
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.
![](https://i.imgur.com/M4CQer8.jpg)
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	
:::
![](https://i.imgur.com/QrnTGxZ.jpg)
![](https://i.imgur.com/hQS95rC.jpg)
![](https://i.imgur.com/IapsTUT.jpg)



## Zadanie 7
:::success
Autor:	Szymon Mleczko	
:::
![](https://i.imgur.com/GiKT6Ua.jpg)

## 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. 

![](https://i.imgur.com/lhspRbH.png)
![](https://i.imgur.com/eqavqW6.png)

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. 

![](https://i.imgur.com/CXSycrD.png)
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
....

![](https://i.imgur.com/Q2ph5H4.png)

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	
:::
![](https://i.imgur.com/UF6vt0I.png)

![](https://i.imgur.com/sH9qF6B.png)


