Zadania (2019/20)
=================

Należy wybrać jedno zadanie z sekcji `Zadania oparte na klasycznych problemach synchronizacji`_ 
oraz jedno zadanie z sekcji `Inne problemy synchronizacji`_.

Punktacja

+------------------------------+-----+
| Problem                      | Pkt.|
+==============================+=====+
| `Czytelnicy i pisarze`_      | 100 |
+------------------------------+-----+
| `Pięciu kucharzy`_           |  80 |
+------------------------------+-----+
| `Pięciu głodomorów`_         |  80 |
+------------------------------+-----+
| `Palacze tytoniu`_           | 100 |
+------------------------------+-----+
| `Śpiący fryzjerzy-kasjerzy`_ | 100 |
+------------------------------+-----+
| `Port`_                      |  50 |
+------------------------------+-----+
| `Taśmociąg`_                 |  30 |
+------------------------------+-----+
| `Lotniskowiec`_              |  50 |
+------------------------------+-----+
| `Święty Mikołaj`_            |  60 |
+------------------------------+-----+
| `Cząsteczki wody`_           |  50 |
+------------------------------+-----+
| `Diabelska kolejka`_         |  30 |
+------------------------------+-----+
| `Choinka`_                   |  70 |
+------------------------------+-----+

Podstawą oceny jest poprawność rozwiązania, stopień współbieżności procesów 
(im mniej ograniczeń na współbieżność, tym lepiej) oraz "zasobożerność" 
(im mniej zasobów, tym lepiej).


Zadania oparte na klasycznych problemach synchronizacji 
-------------------------------------------------------

Zadanie z tej grupy należy zrealizować na mechanizmach System V IPC (pamięć 
współdzielona, semafory i kolejki komunikatów).


Czytelnicy i pisarze
~~~~~~~~~~~~~~~~~~~~

Zadanie polega na realizacji problemu czytelników i pisarzy 
(`opis wersji klasycznej w Wikipedii <https://pl.wikipedia.org/wiki/Problem_czytelnik%C3%B3w_i_pisarzy>`_), 
przy czym:

1. jest ustalona liczba procesów — :math:`N`;

#. każdy proces działa naprzemiennie w dwóch fazach: fazie relaksu i fazie 
   korzystania z czytelni;

#. w dowolnym momencie fazy relaksu proces może (choć nie musi) zmienić swoją 
   rolę: z pisarza na czytelnika lub z czytelnika na pisarza;

#. przechodząc do fazy korzystania z czytelni proces musi uzyskać dostęp we 
   właściwym dla swojej aktualnej roli trybie;

#. pisarz umieszcza efekt swojej pracy — swoje **dzieło** — w formie 
   komunikatu w kolejce komunikatów, gdzie komunikat ten pozostaje do momentu, 
   aż wszystkie procesy, które w momencie wydania dzieła były w roli czytelnika, 
   nie odczytają go (po odczytaniu przez wszystkie wymagane procesy komunikat 
   jest usuwany);
  
#. pojemność kolejki komunikatów — reprezentującej półkę z książkami — jest 
   ograniczona, tzn. nie może ona przechowywać więcej niż :math:`K` dzieł;

#. podczas pobytu w czytelni proces (również pisarz) czyta co najwyżej jedno 
   dzieło, po czym czytelnik opuszcza czytelnię, a pisarz czeka na miejsce w 
   kolejce, żeby opublikować kolejne dzieło.


Pięciu kucharzy
~~~~~~~~~~~~~~~

Zadanie oparte jest na problemie ucztujących filozofów 
(`opis w Wikipedii <https://pl.wikipedia.org/wiki/Problem_ucztuj%C4%85cych_filozof%C3%B3w>`_),
przy czym:

1. tutaj kucharz może albo przygotować porcję do zjedzenia, albo skonsumować 
   porcję przygotowaną wcześniej (być może przez innego kucharza);
   
#. zarówno do skonsumowania porcji, jak i do jej przygotowania kucharz potrzebuje 
   dwóch widelców;
   
#. porcje przygotowane przez kucharzy gromadzone są na stole, który ma ograniczoną 
   pojemność — :math:`K` oraz dopuszczalne obciążenie — :math:`W`;
   
#. każda przygotowana porcja zajmuje jedno miejsce na stole, a wagi przygotowywanych 
   porcji są zróżnicowane;

#. zawartość stołu jest reprezentowana przez kolejkę komunikatów. 


Pięciu głodomorów
~~~~~~~~~~~~~~~~~

Zadanie oparte jest na problemie ucztujących filozofów 
(`opis w Wikipedii <https://pl.wikipedia.org/wiki/Problem_ucztuj%C4%85cych_filozof%C3%B3w>`_),
przy czym każdy posiłek ma swoją wagę i odnotowywana jest łączna waga posiłków
zjedzonych przez każdego głodomora. Na podstawie łącznej wagi zjedzonych posiłków
ustalany jest priorytet głodomora — im mniej zjadł, tym ma wyższy priorytet. 


Palacze tytoniu
~~~~~~~~~~~~~~~

Zadanie oparte jest na problemie palaczy tytoniu
(`opis w Wikipedii (po angielsku) <https://en.wikipedia.org/wiki/Cigarette_smokers_problem>`_)
przy czym:

1. palacze rozliczają się między sobą za udostępniane składniki po aktualnym 
   kursie giełdowym;

#. rola agenta sprowadza się do ustalania kursu giełdowego składników;

#. palacze nie mogą mieć debetu, więc jeśli palacza nie stać na zakup składników, 
   musi poczekać na zmianę kursu lub przypływ gotówki za sprzedaż własnego 
   składnika (początkowy stan konta palacza jest większy od 0);  
   
#. palacz nabywa jednocześnie oba składniki; 

#. należy użyć kolejki komunikatów do przekazywania składników między palaczami.


Śpiący fryzjerzy-kasjerzy
~~~~~~~~~~~~~~~~~~~~~~~~~

Zadanie oparte jest na problemie śpiącego golibrody, `opisanym w Wikipedii <https://pl.wikipedia.org/wiki/Problem_%C5%9Bpi%C4%85cego_golibrody>`_
w wersji dla jednego fryzjera/golibrody. 

1. Zadanie należy zrealizować w wersji z :math:`F` fryzjerami (:math:`F` > 1) w jednym 
   salonie oraz :math:`N` fotelami (:math:`N<F`), 
   
#. Pojemność poczekalni wynosi :math:`P`. Należy ją zrealizować z użyciem 
   kolejki komunikatów.

#. Należy uwzględnić rozliczenie klienta z fryzjerem, w którym:

   * klient przekazuje fryzjerowi kwotę za usługę przed rozpoczęciem golenia;
   
   * fryzjer wydaje resztę po zakończeniu obsługi klienta, a w przypadku
     braku możliwości wydania reszty klient musi zaczekać, aż fryzjer 
     znajdzie resztę w kasie.
	 
#. Kasa jest wspólna dla wszystkich fryzjerów.

#. Płatność może być dokonania nominałami o wartościach 1, 2, i 5. 

Fryzjer działa cyklicznie wg. schematu:

1. wybiera klienta z poczekalni (ewentualnie czeka, jeśli go jeszcze nie ma),

#. znajduje wolny fotel,

#. pobiera opłatę za usługę i umieszcza we wspólnej kasie (opłata może być
   również przekazana do wspólnej kasy bezpośrednio przez klienta, ale fryzjer
   musi znać kwotę, żeby wyliczyć resztę do wydania),

#. realizuje usługę,

#. zwalnia fotel,

#. wylicza resztę i pobiera ze wspólnej kasy, a jeśli nie jest to możliwe, 
   czeka, aż pojawią się odpowiednie nominały w wyniku pracy innego fryzjera,
   
#. przekazuje resztę klientowi. 

Klient działa cyklicznie wg. schematu:

1. zarabia pieniądze,

#. przychodzi do salonu fryzjerskiego,

#. jeśli jest wolne miejsce w poczekalni, siada i czeka na obsługę (ewentualnie 
   budzi fryzjera), a w przypadku braku miejsc opuszcza salon i wraca do 
   zarabiania pieniędzy,
   
#. po znalezieniu fryzjera płaci za usługę,

#. czeka na zakończenie usługi,

#. czeka na resztę,

#. opuszcza salon i wraca do zarabiania pieniędzy.

Inne problemy synchronizacji
----------------------------

Zadanie z tej grupy należy zrealizować na wątkach z użyciem muteksów i 
zmiennych warunkowych w standardzie POSIX (pthread). 

Port
~~~~

Do portu zawijają statki, cumują w nim przez jakiś czas i go opuszczają. 
Każdy statek zarówno w celu wejścia do portu, jak i wyjścia z niego musi 
dostać pewną liczbę holowników, zależną od jego masy. Musi być też dla niego 
miejsce w doku. Zarówno liczba miejsc w doku, jak i liczba holowników są 
ustalone i ograniczone.

Cel zadania: synchronizacja statków (doki i holowniki to zasoby)


Taśmociąg
~~~~~~~~~

Przy taśmociągu, który dostarcza cegły z dołu na górę, pracują robotnicy.
Jedna grupa wkłada cegły na taśmociąg na dole, a druga zdejmuje je z taśmociągu
na górze. Cegły mają wagę 1 kg lub 2 kg, a dopuszczalne obciążenie taśmociągu 
wynosi 10 kg.

Cel zadania: synchronizacja robotników. 


Lotniskowiec
~~~~~~~~~~~~

Źródło: [WG93]_

Na lotniskowcu lądują i startują samoloty. W tym celu potrzebują wyłącznego 
dostępu do pasa. Lotniskowiec może pomieścić pewną ustaloną liczbę :math:`N` samolotów.
Jeśli samolotów jest mniej niż :math:`K` (:math:`K<N`), wówczas priorytet w dostępie do 
pasa mają samoloty lądujące. 

Cel zadania: synchronizacja samolotów (pas i miejsce na lotniskowcu to zasoby).


Święty Mikołaj
~~~~~~~~~~~~~~

Źródło: [PWit]_

Święty Mikołaj śpi w swojej chatce na biegunie północnym. Może go zbudzić 
jedynie przybycie dziewięciu reniferów lub trzy spośród dziesięciu skrzatów,
chcących poinformować Mikołaja o problemach z produkcją zabawek (snu Mikołaja
nie może przerwać mniej niż dziewięć reniferów ani mniej niż trzy skrzaty!). 
Gdy zbiorą się wszystkie renifery, Mikołaj zaprzęga je do sań, dostarcza zabawki
grzecznym dzieciom (oraz studentom realizującym pilnie zadania z synchronizacji 
współbieżnych procesów), wyprzęga je i pozwala odejść na spoczynek. Mikołaj 
zbudzony przez skrzaty wprowadza je do biura, udziela konsultacji a później 
żegna. Obsługa reniferów ma wyższy priorytet niż obsługa skrzatów.

Cel zadania: synchronizacja Św. Mikołaja, reniferów i skrzatów. 


Cząsteczki wody 
~~~~~~~~~~~~~~~

Źródło: [PWit]_

Producenci wodoru oraz tlenu umieszczają w swoich jednoelementowych buforach 
(w losowych odstępach czasu) atom wodoru lub atom tlenu. Gdy wśród wyprodukowanych 
atomów znajdą się dwa wodoru i jeden tlenu, powstaje woda a ich producenci wracają 
do pracy.

Cel zadania: synchronizacja producentów atomów. 


Diabelska kolejka
~~~~~~~~~~~~~~~~~

Źródło: [PWit]_

Wagonik kolejki może pomieścić :math:`P` pasażerów spośród ogólniej liczby 
:math:`N` użytkowników (:math:`P < N`). Wagonik może wyruszyć tylko wtedy, 
gdy jest pełny, czyli gdy :math:`P` pasażerów zdeklaruje gotować przejazdu. 

Cel zadania: synchronizacja pasażerów i wagonika. 

Choinka
~~~~~~~

Małe skrzaty stroją choinkę na Boże Narodzenie, zawieszając na niej ozdoby,
dostarczane przez Św. Mikołaja. 
W tym celu skonstruowały :math:`n`-poziomowe rusztowanie pozwalające dotrzeć 
do wyższych gałązek. Wytrzymałość rusztowania jest ograniczona — na poziomie 
:math:`i`-tym może być jednocześnie co najwyżej :math:`k_i` skrzatów. Poziom 1
jest najniższy oraz :math:`k_1 > k_2 > ... > k_n`. Żeby dotrzeć na poziom 
:math:`i`-ty, skrzat musi przejść kolejno przez wszystkie niższe poziomy, nie 
przeciążając rusztowania. Podobnie, żeby zejść, musi przejść przez kolejne
niższe poziomy. Liczba ozdób, jakie można zawiesić na choince, również jest 
ograniczona i na poziomie :math:`i`-tym wynosi :math:`p_i`. Ozdoby zabierane 
są z poziomu 0, na który dostarcza je sukcesywnie po kilka sztuk Św. Mikołaj, 
przy czym jest tam ograniczona przestrzeń — co najwyżej :math:`p_0` ozdób. 
Skrzat w jednym swoim przejściu zdoła przenieść jedną ozdobę (ozdoba nie 
stanowi dodatkowego obciążenia rusztowania). 

Cel zadania: synchronizacja skrzatów oraz Św. Mikołaja zakładając, że zawieszanie
ozdoby na choince zajmuje pewien czas. 


.. [WG93] Weiss Z., Gruźlewski T.: Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT W-wa 1993.

.. [PWit] Witkowski P.: http://www.ii.uni.wroc.pl/~pwit/Dydaktyka/so/proj/projekty.html (ostatni dostęp 20.12.2017).