---
# System prepended metadata

title: Programowanie Współbieżne lista 1

---

### Zadanie 1
![](https://hackmd.io/_uploads/rJuWRBeW6.png)
Moc procesora pierwotnego: $$ P = CV^2 * f_1 $$
Z zadania wiemy że:
$$ P = cn_1 * \alpha^2 * f_1^3$$
gdzie n to liczba tranzystorów
A zatem moc zużywaną przez drugi procesor możemy przedstawić jako:
$$P_2 = c n_2 * \alpha^2 * f_2^3 $$
Ponieważ uruchamiamy algorytm na dwóch rdzeniach i uzyskujemy dwukrotne przyspieszenie to:
$$
P_2 = c n_2 * \alpha^2 * f_2^3 = 2 * c n_1 * \alpha^2*(\frac{1}{2}*f_1)^3=\\
2 * cn_1*\alpha^2*\frac{1}{8}*f_1^3 = \frac{1}{4}*cn_1*\alpha^2*f_1^3 = \frac{1}{4}P_1
$$
A zatem nasz drugi procesor zużywa mniej mocy od pierwotnego procesora.

### Zadanie 2
![](https://hackmd.io/_uploads/SJE_r8gb6.png)
![](https://hackmd.io/_uploads/B1ZsS8gZT.png)

Problem sekcji krytycznej - dwa wątki korzystają ze wspólnego zasobu, np. tak jak w tym przypadku - jeziora, podczas gdy w danym momencie tylko jeden proces może z niego korzystać.


Alicja:
1. Podnieś flagę.
2. Poczekaj, aż flaga Boba będzie opuszczona.
3. Wpuść smoka do jeziora.
4. Gdy smok powróci, opuść flagę.

Bob:
1. Podnieś flagę.
2. Dopóki flaga Alicji jest podniesiona:
    1. Opuść flagę.
    2. Poczekaj, aż flaga Alicji będzie opuszczona.
    3. Podnieś flagę.
3. Wpuść smoka do jeziora.
4. Gdy smok powróci, opuść flagę.

Poprawiona wersja:
Alicja:
1. Podnieś flagę
2. Dopóki flaga Boba jest w górze
    1. Jeśli napis wskazuje Bob:
        1. Obniż flagę
        2. Czekaj aż napis wskaże Alicja
        3. Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci
5. Ustaw napis na Bob
6. Obniż flagę

Bob:
1. Podnieś flagę
2. Dopóki flaga Alicji jest w górze:
    1. Jeśli napis wskazuje Alicja:
        1. Obniż flagę
        2. Poczekaj aż napis wskaże Bob
        3. Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci
5. Ustaw napis na Alicja
6. Opuść flagę


Zagłodzenie

Załóżmy nie wprost, że doszło do zagłodzenia, czyli jeden ze smoków nigdy nie wejdzie do jeziora (niech będzie to smok Boba). Skoro Bob chce wpuścić smoka, a nie może, to znaczy, że ma obniżoną flagę i czeka aż napis wskaże jego imię. Smok Alicji wracając ustawi napis na “Bob”, co prowadzi do sprzeczności.

Wzajemne wykluczanie

Załóżmy nie wprost, że w jeziorze znalazły się 2 smoki jednocześnie. Wtedy Alicja i Bob mają podniesione flagi. Bob wpuszcza smoka. Jeśli Alicja również wpuściła smoka, to odeszła od algorytmu, gdyż napis nie wskazywał jej imienia.

Zakleszczenie

Załóżmy nie wprost, że doszło do zakleszczenia, czyli zarówno Alicja jak i Bob chcą wpuścić smoka do jeziora, ale żadne z nich nie może tego zrobić. Napis wskazuje jedną z tych osób wpuszcza smoka do jeziora, a druga musi poczekać.

### Zadanie 3
![](https://hackmd.io/_uploads/r1s19Ux-a.png)

**Problem producenta-konsumenta**
Mamy dwa wątki działające równolegle oraz wspólny bufor (sekcja krytyczna). Wątki nie mogą być oba naraz w sekcji krytycznej. **Producent (Bob)** zapisuje dane do bufora a **konsument (Alicja)** je pobiera

Ulepszony algorytm:

Algorytm Alicji:
1. Czeka aż puszka zniknie z parapetu.
2. Wypuszcza smoki.
3. Stawia swoją puszkę.
4. Gdy zwierzęta wrócą:
    1. Jeżeli zjedzą wszystko, to Alicja pociąga za sznurek i strąca puszkę Boba, wpp. nie pociąga za sznurek.
    
Algorytm Boba:
1. Czeka aż puszka zniknie z parapetu.
2. Idzie do jeziora podrzucić jedzenie.
3. Stawia swoją puszkę.
4. Pociąga za sznurek i strąca puszkę Alicji.

### Zadanie 4
![](https://hackmd.io/_uploads/rkukhIlZ6.png)
1. Własność bezpieczeństwa - klienci zostaną obsłużeni osobno, po kolei
2. Własność bezpieczeństwa - nigdy dwa nie znajdą sie w tym samym miejscu
3. Własność żywotności - jeden zawsze wchodzi do sekcji krytycznej
4. Własność żywotności - po przerwaniu w ciągu sekundy otrzymujemy komunikat
5. Własność żywotności - otrzymujemy komunikat
6. Własność bezpieczeństwa - mamy zapewnienie że koszt życia nigdy nie spadnie
7. Własność żywotności

### Zadanie 5
![](https://hackmd.io/_uploads/SJeNNH-Za.png)

Nową strategią będzie nadanie więzniom roli. Jeden z więźniów będzie spamiętywał ile więźniów (załóżmy że jest ich n) weszło do przełączalni. Niech to będzie więzień X.
Na początku przełącznik jest wyłączony.
Mamy dwa przypadki:
**Przełącznik jest wyłączony**
- X nic nie robi

**Przełącznik jest włączony**
- X dodaje 1 do liczby więzniów które weszły do przełączalni.


Pozostali więzniowie po wejściu do przełączalni jeżeli zobaczą, że **przełącznik jest włączony**:
- nic nie robią

Natomiast jeżeli  **przełącznik jest wyłączony**:
- włączają przełącznik, jeżeli nigdy wcześniej go nie włączyli

Jeżeli X doliczy się do N-1 więźniów którzy weszli do przełączalni to znaczy że każdy z nich oprócz X musiał włączyć raz przełącznik (nie mogą włączyć go kilkukrotnie).

### Zadanie 6
![](https://hackmd.io/_uploads/SkeguSb-p.png)

Wykorzystujemy bardzo podobną strategię do tej z poprzedniego zadania z tą różnicą że liczymy do 2N a nie do N.

Tak jak w poprzednim zadaniu więzień X robi to samo, pozostali więzniowie również jednak tym razem mogą włączyć przełącznik maksymalnie dwa razy.

- Jeżeli przełącznik był na początku włączony
N - 1 więźniów mogło włączyć przełącznik już dwa razy wtedy jeden z więźniów (Y) mógł nie włączyć go ani razu. Zauważmy że w takim przypadku X doliczył się do 2N - 1 a zatem jeżeli wejdzie Y i w końcu go włączy doliczymy się do 2N.

- Jeżeli przełącznik był na początku wyłączony
Gdy każdy z więźniów wejdzie i włączy przełącznik dokładnie dwa razy otrzymamy wartość 2N

### Zadanie 7
![](https://hackmd.io/_uploads/SJ2rAr-Zp.png)
![](https://hackmd.io/_uploads/HyyLJIbb6.png)


1. Przy n dążącym do nieskończoności: $\frac{1}{(0.4 + \frac{0.6}{n})}= 2.5$

2. 2Przyspieszenie P' = Przyspieszenie P''

$$
    a'' = lim_{n \to \infty}{\frac{1}{\frac{1-p''}{x} + \frac{p''}{n}}} = \frac{x}{1-p''}, \\
    x = a'' * (1 - p'')\\
    p'' = 0.7 \\
    a'' = 2a' = 5 \\
    x = 5 * 0.3 = 1.5
$$
3. Ułamek
$$
a'' = lim_{n \to \infty}{\frac{1}{\frac{x}{3} + \frac{1-x}{n}}} = \frac{3}{x}\\
a'' = 2a' = 5\\
x = \frac{3}{5}
$$