---
# System prepended metadata

title: 'Ćwiczenia 14, grupa śr. 17-19, 22. czerwca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ćwiczenia 14, grupa śr. 17-19, 22. 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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |  --- | --- |
Grzegorz Bielecki        |       |     |     |     |     |     |     |     |     |      |     |
Kamila Brzozowska        |       |     |     |     |     |     |     |     |     |      |     |
Adam Ciężkowski          |   X    |  X   |  X   |  X   |     |  X   |  X   |   X  |  ==X==   |  X   |     |
Natalia Czerep           |    X   |  X   |  X   |   ==X==  |     |     |     |     |     |     |     |
Jan Dalecki              |   X    |   X  |     |     |     |  X   |     |     | X    |     |     |
Marko Golovko            |   X   | X   | X   |  X  |     |     | ==X== |     |     |     |     |
Adam Górkiewicz          |       |     |     |     |     |     |     |     |     |     |     |
Piotr Gunia              |       |  X  |  X  |     |     |     |     |     |     |     |     |
Krzysztof Jadłowski      |       |     |     |     |     |     |     |     |     |     |     |
Magdalena Jarecka        |       |     |     |     |     |     |     |     |     |     |     |
Mikołaj Jaszcza          |       |     |     |     |     |     |     |     |     |     |     |
Monika Jędrzejkowska     |       |     |     |     |     |     |     |     |     |     |     |
Michał Kierul            |       |     |     |     |     |     |     |     |     |     |     |
Damian Lukas             |       |     |     |     |     |     |     |     |     |     |     |
Karol Ochman-Milarski    |       |     |     |     |     |     |     |     |     |     |     |
Piotr Piesiak            |       |     |     |     |     |     |     |     |     |     |     |
Damian Ratajski          |       |     |     |     |     |     |     |     |     |     |     |
Aleksandra Rozkrut       |       |     |     |     |     |     |     |     |     |     |     |
Marcin Sarnecki          |       |     |     |     |     |     |     |     |     |     |     |
Maria Szlasa             |       |     |     |  X  |     |  X  |  X  |  X  |  X  |     |     |
Mateusz Burdyna          |       |     |     |     |     |     |     |     |     |     |     |
Magdalena Słonińska      |       |     |     |     |     |     |     |     |     |     |     |
Nikola Wrona             |       |     |     |     |     |     |     |     |     |     |     |
Marcin Wróbel            |       |     |     |     |     |     |     |     |     |     |     |
:::



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

## Zadanie 1
:::success
Autor:	Jan Dalecki	
:::
:::info
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ą.
:::

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

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

Funkcja increment działa dla dowolnej liczby procesów tzn. daje poprawną wartość *v+k po k inkrementacjach. Niestety może zajść zdarzenie głodzenia procesów, które na czas działania innych procesów będą zapętlone w instrukcji while. Z tego powodu jeżeli nieznana jest liczba wykonanywanych inkrementacji przez dany proces to nie powinniśmy używać funkcji increment. Być może zbyt długo zagłodzimy procesy i spowolnimy działanie systemu. Taka sytuacja może nastąpić w przypadku a.



## Zadanie 2
:::success
Autor:	Piotr Gunia	
:::
![](https://i.imgur.com/fUAj29R.png)
![](https://i.imgur.com/nv4RKfH.png)


```
int lock = false; - lock współdzielony

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

## Zadanie 3
:::success
Autor:	Marko Golovko	
:::

![](https://i.imgur.com/9gS6CGW.png)
![](https://i.imgur.com/XQvRaI2.png)
![](https://i.imgur.com/aItUz2L.png)

```c=
wait(lock) {
    while (test_and_set(&lock) == 1);
}

signal(lock) {
   lock = 0; 
}
```

```
mutex:
flag = false;
lock()
{
 while(test_and_set(flag));
}
unlock()
{
    flag = false;
}


semaphore:
flag = false;
wait(semaphore *S) {
 S->value--;
 if (S->value < 0) {
 lock();
 }
}
signal(semaphore *S) {
 S->value++;
 if (S->value <= 0) {
 unlock()
 }
} 
```
[Implementacja semafora zliczającego przy pomocy mutexów](http://www.cs.umd.edu/~shankar/412-Notes/10x-countingSemUsingBinarySem.pdf)


## Zadanie 4
:::success
Autor:	Natalia Czerep	
:::

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

**Co to jest monitor?**
Monitor to wysokopoziomowy konstrukt (taki obiekt(?)), który może być wykorzystywany przez kilka wątków i zwalnia programistę z odpowiedzialności za implementację mutexów semaforów itd.
![](https://i.imgur.com/bexwMTl.png)

 Metody monitora chronione są przez muteksy, przez co w dowolnym momencie czasowym z dowolnej metody może korzystać tylko jeden wątek naraz.
 Zapewnia to właściwość **wzajemnego wykluczania.**
 
 a) bez zmiennych warunkowych
![](https://i.imgur.com/Dvm2YNR.png)

b) ze zmiennymi warunkowymi

 W wielu sytuacjach wzajemne wykluczanie nie wystarcza. Wątki próbujące wykonać pewną operację mogą wymagać zaczekania na spełnienie określonego warunku, aby móc kontynuować. Zwykłe aktywne czekanie przy pomocy pętli nie wystarcza
 **Wątek w dalszym ciągu zajmuje monitor, przez co nikt inny nie ma szans na zmianę jego stanu i spełnienie warunku. Rozwiązaniem są zmienne warunkowe.**
 ![](https://i.imgur.com/qPZnrHU.png)
 Źródła:
 https://pl.wikipedia.org/wiki/Monitor_(programowanie_wsp%C3%B3%C5%82bie%C5%BCne)
 https://www.youtube.com/watch?v=ufdQ0GR855M

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

## Zadanie 6
:::success
Autor:	Maria Szlasa	
:::
:::info
Zdefiniuj problem producenta i konsumenta z ograniczonym buforem. Przedstaw jego rozwiązanie przy użyciu semaforów i muteksów.

**Wskazówka** “Synchronization examples”, slajdy 4 – 6. Podrozdział 7.1.1 Abraham Silberschatz, Peter B. Galvin, and Greg Gagne. 2012. Operating System Concepts (8th/10th. ed.).
:::
[10th ed.](https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf)
![](https://i.imgur.com/6vyAccM.png)

![](https://i.imgur.com/kcOKOik.png)
![](https://i.imgur.com/0lLvLGO.png)
![](https://i.imgur.com/BarCnmX.png)

## Zadanie 7
:::success
Autor:	Adam Ciężkowski	
:::

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

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

![](https://i.imgur.com/67XjprI.png)
![](https://i.imgur.com/XsWwTq4.png)



## Zadanie 8
:::success
Autor:	Maria Szlasa	
:::
:::info
Przedstaw rozwiązanie problemu czytelników i pisarzy, które nie głodzi pisarzy. 
**Wskazówka** Podrozdział 4.2, a w szczególności 4.2.4 – 4.2.5, ”The Little Book of Semaphores”.
:::
![](https://i.imgur.com/utFnZFs.png)
![](https://i.imgur.com/Uaz61Cm.png)
![](https://i.imgur.com/ueaK6EH.png)
![](https://i.imgur.com/N8YlV3Y.png)

## Zadanie 9
:::success
Autor:	Adam Ciężkowski	
:::

![](https://i.imgur.com/qJKjNuB.png)
![](https://i.imgur.com/uKYJkhe.png)
![](https://i.imgur.com/pXzGFKR.png)
![](https://i.imgur.com/M1AIyNd.png)


## Zadanie 10
:::success
Autor:	Adam Ciężkowski	
:::

![](https://i.imgur.com/AaXCg37.png)
![](https://i.imgur.com/BHANBmy.png)
![](https://i.imgur.com/UAAs4uB.png)


## Zadanie 11
:::danger
Autor:	
:::
