# Ćwiczenia 1, grupa śr. 16-18, 9 października 2024

###### tags: `PRW24` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Bartosz Borecki | | X | X | X | X | X | X |
Miriam Bouhajeb | X | X | X | X | X | X | |
Marceli Buczek | X | X | X | X | X | X | X |
Maciej Ciepiela | X | X | X | X | X | ==X== | X |
Maciej Dominiak | x | x| x | x | x | x | |
Michał Hajahmadov | X | X | X | X | X | X | X |
Julia Kulczycka | x | ==X== | x | x | x | | |
Adam Majchrowski | X | X | X | X | ==X== | X | X |
Hanna Makowska | X | X | X | ==X== | X | X | X |
Cezary Miłek | X | X | X | X | X | X | X |
Błażej Molik | X | X | ==X== | X | X | X | X |
Konrad Oleksy | | | | | | | |
Kacper Osadowski | | | | | | | |
Maciej Szałasz | ==X== | X | X | X | X | | |
Aliaksandr Tyszecki | | | | | | | |
Miłosz Urbanik | X | X | X | X | X | | |
:::

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

## Zadanie 1
:::success
Autor: Maciej Szałasz
:::
### Cel

Procesor równie szybki ($T$ bez zmian) minimalizujący zużywaną moc.

### Rozwiązanie
- $P \sim C$
- $P \sim V^2$
- $P \sim f$
- $f \sim V$ - Napięcie zależy od częstotliwości liniowo
- Pojemność elektryczna zależy liniowo od liczby tranzystorów
- Dla wzorcowego jednordzeniowego procesora, czas wykonania algorytmu $T$ zależy od częstotliwości procesora $f$, zgodnie z wzorem $f \sim \frac{1}{T}$. Dlatego dokładając drugi rdzeń czas pracy zmniejsza się o połowę

### Optymalizacja
Zmniejszając $f$ o połowę zmniejszymy również $V$ i otrzymamy:
$$P_1=C_1{V_1}^2f_1=C{(\frac{V}{2})}^2\frac{f}{2}=\frac{P}{8}$$
Czyli procesor wolniejszy o połowę, ale zużywający 8-krotnie mniej energii.

Dodając drugi rdzeń zwiekszamy dwukrotnie jego pojemność elektryczną $C_2=2C$:

$$P2 = C_2{V_2}^2f_2 = 2C(\frac{V}{2})^2\frac{f}{2} = \frac{P}{4}$$
Jeśli uruchomimy algorytm na dwóch rdzeniach, to czas pozostanie bez zmian, a zużycie mocy zostanie znacznie obniżone.

## Zadanie 2
:::success
Autor: Julia Kulczycka
:::
**Protokół z flagami**:
- flaga może być opuszczona lub podniesiona
- stan flagi modyfikuje tylko właściciel, ale widzi każdy
- flaga podniesiona = właściciel wpuszcza smoka

**Ryzyko**:
- któryś smok (Boba) może zostać zagłodzony, jeśli flaga (Alicji) będzie ciągle w górze, bo Alicja ma pierwszeństwo

**Sekcja krytyczna** - fragment kodu, który podlega wzajemnemu wykluczeniu = jezioro

**Najważniejsza idea**: jak ktoś wpuści swojego smoka, to następnym razem daje pierwszeństwo drugiej osobie; to, kto ma pierwszeństwo, wyznacza wskaźnik
Zmodyfikowany protokół wygląda następująco:

1. Jeśli smok Alicji chce wejść do jeziora, sprawdza ona, czy wskaźnik wskazuje na Boba. Jeśli tak, czeka, aż wskaźnik się zmieni.
2. Jeśli smok Boba chce wejść do jeziora, Bob sprawdza, czy wskaźnik wskazuje na Alicję. Jeśli tak, również czeka.
3. Jeśli obydwie flagi są ustawione (czyli oba smoki chcą wejść do jeziora), smok, na którego wskazuje wskaźnik, daje pierwszeństwo drugiemu smokowi.
4. Po wejściu do jeziora właściciel smoka zmienia wskaźnik na sąsiada, aby dać mu pierwszeństwo następnym razem.

Protokół dla Alicji:

1. Podnieś flagę
2. Jeśli Bob ma podniesioną flagę to:
- jeśli wskaźnik wskazuje na Boba to opuść flagę i wróć do punktu 1.

3. Wpuść smoka.
4. Po wyjściu smoka z jeziora pociągnij za sznurek.
5. Opuść flagę.

Protokół dla Boba:

1. Podnieś flagę
2. Jeśli Alicja ma podniesioną flagę to:
- jeśli wskaźnik wskazuje na Alicję to opuść flagę i wróć do punktu 1.

3. Wpuść smoka.
4. Po wyjściu smoka z jeziora pociągnij za sznurek.
5. Opuść flagę.

Powyższy protkół nie spełnia warunku wzajemnego wykluczania. Przykład.

1. Jezioro jest puste, obydwie flagi opuszczone, wskaźnik wskazuje na Boba.
2. Alicja podnosi flagę. Ponieważ flaga Boba jest opuszczona to Alicja, zgodnie z protokołem, wpuszcza smoka do jeziora.
3. Bob podnosi flagę. Zauważa, że flaga Alicji jest podniesiona, a wskaźnik wskazuje na Boba, zatem zgodnie z protokołem
wpuszcza smoka do jeziora.
4. Obydwa smoki są w jeziorze.

"Dobry" protokół dla Alicji i Boba:

Dla Alicji:

1. Alicja podnosi flagę.
2. Alicja ciągnie za sznurek.
3. Dopóki flaga Boba jest podniesiona a wskaźnik wskazuje na Boba wykonuj punkt 3.
4. Wpuść smoka do jeziora
5. Po powrocie smoka opuść flagę.

Dla Boba:

1. Bob podnosi flagę.
2. Bob ciągnie za sznurek.
3. Dopóki flaga Alicji jest podniesiona a wskaźnik wskazuje na Alicję wykonuj punkt 3.
4. Wpuść smoka do jeziora
5. Po powrocie smoka opuść flagę.

To jest algorytm Peterson. Dowód poprawności będzie na wykładzie.

## Zadanie 3
:::success
Autor: Błażej Molik
:::



Ponadto:
1. Bob dokłada jedzenie, tylko gdy poprzednia porcja zostanie zjedzona.
2. Alicja nie wpuszcza swoich smoków jeśli w jeziorze nie ma jedzenia.

**Alicja**

1. Czeka dopóki jej puszka nie zostanie strącona.
2. Ustawia swoją puszkę.
3. Wypuszcza smoki.
4. Gdy smoki wrócą Alicja sprawdza, czy wszystko zostało zjedzone, jeśli tak to strąca puszkę Boba.

**Bob**

1. Czeka dopóki jego puszka nie zostanie strącona.
2. Ustawia swoją puszkę.
3. Wypuszcza ryby.
4. Strąca puszkę Alicji.

## Zadanie 4
:::success
Autor: Hanna Makowska

:::

## Zadanie 5
:::success
Autor: Adam Majchrowski

:::

## Zadanie 6
:::success
Autor: Maciej Ciepiela
:::

Spośród 'n’ więźniów, niech jeden pełni rolę przywódcy, odpowiedzialnego za zliczanie ilości więźniów, którzy już odwiedzili pokój.

Przywódca:
1. Jeżeli przycisk jest włączony - dodaje 1 do "licznika" i wyłącza przycisk
2. Jeżeli przycisk jest wyłączony - nic nie robi
3. Jeżeli zliczył „2n-2” - ogłasza, że wszyscy odwiedzili pokój

Więzień:
1. Jeżeli jest wyłączony i nie włączał jeszcze przycisku dwukrotnie – włącza go
2. Jeżeli przycisk jest włączony – nic nie robi

## Zadanie 7
:::success
Autor: Bartosz Borecki

public void run() {
    Random random = new Random();
    while (true) {
        try {
            sleep(random.nextInt(1000));
            System.out.println("Philosopher " + id + " is hungry");
            if (id % 2 == 0) {
                right.get();
                left.get();
                System.out.println("jem sobie " + id);
                sleep(100);
                right.put();
                left.put();
            } else {
                left.get();
                right.get();
                System.out.println("jem sobie " + id);
                sleep(100);
                left.put();
                right.put();
            }
        } catch (InterruptedException ex) {
            return;
        }
    }
}

:::