# Ćwiczenia 1, grupa śr. 14-16, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Michał Chawar | X | X | X | X | X | X | X |
Fabian Grodek | X | X | X | X | X | X | X |
Maria Hreniak | X | X | X |==X==| X | X | |
Aleksandra Jędrzejak | X | X | X | X | X | X | |
Jan Kamyk | X | X | X | X |==X==| X | |
Viktoriia Kashpruk | X |X |==X== |X |X | X | X |
Miłosz Krzysiek | | | | | | | |
Michał Łukasik | X | X | X | | X | X | |
Kacper Pajor | X | X | X | X | X | X | X |
Ksawery Plis | X | X | X | X | X |==X==| X |
Kacper Ponikowski | X | X | X | X | X | X | |
Yaryna Rachkevych |==X==| X | X | X | X | X | X |
Cyprian Skrzypczak | x | x | x | x | x | x | x |
Antoni Strasz | x | x | x | x | x | x | x |
Marta Strzelec | | x | x | x | x | x | x |
Dominik Szczepaniak | X | X | X | X | X | X | X |
Piotr Thamm | X | X | X | X | X | X | |
Michał Włodarczak | X | ==X== | X | X | X | X | X |
:::

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

## Zadanie 1
:::success
Autor: Yaryna Rachkevych
Wzór na moc zużywaną przez oryginalny procesor to:
$$ P_1 = C_1 * V_1^2 * f_1 $$

Możemy użyć dwóch rdzeni, co dało by
dwukrotne przyspieszenie. Aby uzyskać takie same wyniki jak procesor jednordzeniowy w tym samym czasie, nowy procesor może pracować z częstotliwością dwa razy mniejszą:
$$ f_2 = \frac{f_1}{2} $$

Wiemy, że napięcie
V jest proporcjonalne do częstotliwości, więc obniżając częstotliwość, możemy również obniżyć napięcie:
$$ V_2 = \frac{V_1}{2} $$

Zwiększenie liczby rdzeni do dwóch zwiększa pojemność układu, ale zależy ona liniowo od liczby tranzystorów. Zakładamy, że podwojenie liczby rdzeni podwaja również pojemność:
$$ C_2 = 2*C_1 $$

Obliczmy moc zużywaną przez nowy procesor, korzystając z wzoru:
$$ P_2 = C_2 * V_2^2 * f_2 $$

Podstawiając:
$$ P_2 = 2C_1 * (\frac{V_1}{2})^2 * \frac{f_1}{2} = C_1 * (\frac{V_1^2}{4}) *f_1 = \frac{1}{4} * P_1 $$
$$P_2 < P_1$$

:::

## Zadanie 2
:::success
Autor: Michał Włodarczak
:::
**Problem sekcji krytycznej** - kilka wątków korzysta z jednego zasobu (zasobu dzielonego), w danej chwili może z niego korzystać co najwyżej jeden wątek

Protokół Alicji:

1. Podnieś flagę
2. Dopóki flaga Boba też jest podniesiona:
* Jeżeli napis wskazuje na Boba (jego tura):
a) Obniż flagę
b) Czekaj aż napis będzie pokazywał Alicje
c) Podnieś flagę
3. Wpuść smoka do jeziora
4. Jak smok wróci to pociągnij za sznurek zmieniając napis na Boba
5. Obniż flagę

Protokół Boba:

1. Podnieś flagę
2. Dopóki flaga Alicji też jest podniesiona:
* Jeżeli napis wskazuje na Alicje (jej tura):
a) Obniż flagę
b) Czekaj aż napis będzie pokazywał Boba
c) Podnieś flagę
3. Wpuść smoka do jeziora
4. Jak smok wróci to pociągnij za sznurek zmieniając napis na Alicje
5. Obniż flagę

**Wzajemne wykluczenie** - załóżmy nie wprost że dwa smoki są w jeziorze oraz Alicja wpuściła smoka jako druga. To znaczy, że napis wskazywał na Boba i Bob miał flagę w górze. Jeżeli Alicja wpuściła swojego smoka to znaczy, że flaga Boba nie była podniesiona co jest sprzecznością.

Nie dojdzie do **zakleszczenia**, ponieważ
a) Jeśli tylko jeden smok chce wejść to wejdzie, bo tylko jedna flaga jest w górze.
b) Jeśli dwa smoki chcą wejść, to wskaźnik będzie wskazywał na którąś z osób, a to oznacza, że może ona wypuścić smoka do jeziora, druga wtedy musi poczekać.

Nie dojdzie do **zagłodzenia**, ponieważ, BSO, gdy smok Boba chce wejść do jeziora a nie może, to znaczy, że ma obniżoną flagę i czeka aż napis wskaże jego imię. Wiadomo, że jeśli smok Alicji wróci to ustawi napis Bob, więc wtedy ten smok może wejść do jeziora.

## Zadanie 3
:::success
Autor: Viktoriia Kashpruk
Alicja ma smoki, a Bob ma jedzenie.
Bob jest producentem, będzie dokładać jedzenie, jeśli poprzednie już zostało zjedzone.
Alicja jest konsumentem. Wypuszcza smoków, kiedy jest jedzenie w jeziorze.
Modyfikacja:
Alicja i Bob będą mieli puszki.

Alicja:
1. Czeka aż puszka zniknie z parapetu.
2. Wypuszcza smoki.
3. Gdy zwierzęta wrócą, Alicja sprawdza, czy zjadły
wszystko. Jeśli tak, to ustawia swoją puszkę z powrotem na miejscu. Pociąga za sznurek i strąca puszkę Boba, sygnalizując, że jej puszka już stoi na parapecie.**

Bob:
1. Czeka, aż jego puszka zostanie stącona.
2. Zostawia jedzenie w jeziorze.
3. Ustawia swoją puszkę, pociąga za sznurek i strąca puszkę Alicji.

Dzięki takiemu protokołu, jest spełniony warunek producenta-konsumenta, bo jedzenie nie będzie dokładane, jeśli nie wszystkie zostało zjedzone, oraz smoki nie będą wypuszczone, jeśli nie ma jedzenia w jeziorze.

Jeśli chodzi o warunki wzajemnego wykluczania i niezagłodzenia to są one spełnione.
Zał, nie wprost, że Bob i smoki są w jeziorze. Wtedy to by znaczyło, że Bob wszedł do jeziorza, kiedy puszka jeszcze nie została psotawiona na parapecie. Sprzeczność. Wzajamne wykluczanie jest spełnione.

:::

## Zadanie 4
:::success
Autor: Maria Hreniak
:::

1. bezpieczeństwa - każdy klient kiedyś zostanie obsłużony sprawiedliwie (zgodnie z kolejnością przybycia)
2. żywotności - obiekt kiedyś zejdzie na dół
3. żywotności - pożądane jest wejście do sekcji, a skoro jednemu się udaje to staje się coś pożądanego
4. żywotności - pożądane jest wydrukowanie komunikatu po sekundzie od przerwania
5. żywotności - pożądane jest wydrukowanie komunikatu w momencie przerwania
6. bezpieczeństwa - skoro koszt życia nigdy nie spada, to nigdy nic złego się nie stanie
7. żywotności - pożądane są śmierć i podatki, ponieważ są one pewne to kiedyś się staną:)

## Zadanie 5
:::success
Autor: Jan Kamyk
:::


N więźniów, z których jeden pełni rolę lidera, ma za zadanie śledzić, ilu więźniów odwiedziło pokój z przełącznikiem. Każdy więzień może odwiedzać przełącznik dowolną liczbę razy.

Strategia obrana przez lidera:

* Jeśli przełącznik jest włączony, to oznacza, że ktoś już tu był i go włączył. Wtedy lider dodaje jeden do licznika, bo przynajmniej jedna osoba musiała tu wejść. Lider wyłącza przełącznik
* Jeśli przełącznik jest wyłączony, lider nie zmienia licznika, bo nikt nie był tu przed nim.
* Gdy lider doliczy się N-1, ogłasza, że każdy więzień przynajmniej raz odwiedził pokój z przełącznikiem.

Strategia obrana przez pozostałych więźniów:

* Jeśli przełącznik jest włączony, nie robią nic.
* Jeśli przełącznik jest wyłączony, włączają go, aby zaznaczyć swoją obecność. Robią to tylko raz

## Zadanie 6
:::success
Autor: Ksawery Plis
:::
Niech jeden z więźniów będzie "zliczającym" - będzie spamiętywał ile z reszty więźniów (powiedzmy że jest ich $n$) weszło do przełączalni
Strategia:
* Dla "zliczającego":
* Jeśli przełącznik jest wyłączony to nic nie robi
* Jeśli przełącznik jest włączony to dodaje 1 do liczby więźniów i go wyłącza
* Dla reszty więźniów:
* Jeśli przełącznik jest wyłączony i nie włączyli go więcej niż 2 razy to go włączają
* Jeśli przełącznik jest włączony to nic nie robią

Jeśli "zliczający" doliczy się do $2n$:
* przełącznik był początkowo wyłączony i każdy więzień włączył go 2 razy
* przełącznik byl początkowo włączony i jeden z więźniów włączył go tylko raz

Gdyby któraś osoba nigdy nie weszła to "zliczający" miałby maksymalnie:
$$(n-1) * 2 + 1 = 2n - 2 + 1 = 2n - 1 < 2n$$
W takim razie zliczając do $2n$ mamy pewność że każdy więzień wszedł przynajmniej raz.
## Zadanie 7
:::success
Autor: Fabian Grodek
:::

Klasy z polecenia:

class Fork {
    boolean taken;
    int id;

    public Fork(int myID) {
        id = myID;
    }

    public synchronized void get() throws InterruptedException {
        while (taken) {
            wait();
        }
        taken = true;
    }

    public synchronized void put() {
        taken = false;
        notify();
    }
}


class Philosopher extends Thread {
    int id;
    Fork left;
    Fork right;

    public Philosopher(int myID, Fork myLeft, Fork myRight) {
        id = myID;
        left = myLeft;
        right = myRight;
    }

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

}


Każdy z filozofów, gdy jest głodny czeka, aż lewy widelec się zwolni, gdy go weźmie czeka na prawy.

Zakleszczenie może nastąpić w sytuacji gdy wszystkie widelce są wolne i kazdy filozof zacznie kolejno brać widelce, wówczas każdy z nich weźmie do ręki lewy widelec tym samym zmuszając filozofa po jego lewej do czekania na ten widelec (dla niego to prawy)

Aby pozbyć się tego problemu możemy ponumerować widelce i wprowadzić następującą zasadę:
* Filozof najpierw sięga po widelec z mniejszym indeksem
* Filozof odkłada je na odwrót, najpierw większy potem mniejszy

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

W tym wypadku, jeśli czterech filozofów podniesie widelce z niższym numerem to na stole pozostanie widelec z najwyższym numerem, przez co ostatni filozof nie będzie mógł podnieść żadnego.
Tylko jeden filozof ma dostęp do widelca z najwyższym numerem, więc będzie on mógł jeść dwoma widelcami. Gdy skończy, najpierw odłoży widelec z najwyższym numerem, a następnie z niższym, umożliwiając kolejnemu filozofowi zabranie drugiego sztućca.