# Ć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ą.
:::

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
:::

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
:::


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
:::


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

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

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.**
Ź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)


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




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

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


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


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