1. 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).

1.1. 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).

1.1.1. Czytelnicy i pisarze

Zadanie polega na realizacji problemu czytelników i pisarzy (opis wersji klasycznej w Wikipedii), przy czym:

1. jest ustalona liczba procesów — $N$;
2. każdy proces działa naprzemiennie w dwóch fazach: fazie relaksu i fazie korzystania z czytelni;
3. w dowolnym momencie fazy relaksu proces może (choć nie musi) zmienić swoją rolę: z pisarza na czytelnika lub z czytelnika na pisarza;
4. przechodząc do fazy korzystania z czytelni proces musi uzyskać dostęp we właściwym dla swojej aktualnej roli trybie;
5. 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);
6. pojemność kolejki komunikatów — reprezentującej półkę z książkami — jest ograniczona, tzn. nie może ona przechowywać więcej niż $K$ dzieł;
7. 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.

1.1.2. Pięciu kucharzy

Zadanie oparte jest na problemie ucztujących filozofów (opis w Wikipedii), przy czym:

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

1.1.3. Pięciu głodomorów

Zadanie oparte jest na problemie ucztujących filozofów (opis w Wikipedii), 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.

1.1.4. Palacze tytoniu

Zadanie oparte jest na problemie palaczy tytoniu (opis w Wikipedii (po angielsku)) przy czym:

1. palacze rozliczają się między sobą za udostępniane składniki po aktualnym kursie giełdowym;
2. rola agenta sprowadza się do ustalania kursu giełdowego składników;
3. 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);
4. palacz nabywa jednocześnie oba składniki;
5. należy użyć kolejki komunikatów do przekazywania składników między palaczami.

1.1.5. Śpiący fryzjerzy-kasjerzy

Zadanie oparte jest na problemie śpiącego golibrody, opisanym w Wikipedii w wersji dla jednego fryzjera/golibrody.

1. Zadanie należy zrealizować w wersji z $F$ fryzjerami ($F$ > 1) w jednym salonie oraz $N$ fotelami ($N<F$),
2. Pojemność poczekalni wynosi $P$. Należy ją zrealizować z użyciem kolejki komunikatów.
3. 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.
4. Kasa jest wspólna dla wszystkich fryzjerów.
5. 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),
2. znajduje wolny fotel,
3. 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),
4. realizuje usługę,
5. zwalnia fotel,
6. 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,
7. przekazuje resztę klientowi.

Klient działa cyklicznie wg. schematu:

1. zarabia pieniądze,
2. przychodzi do salonu fryzjerskiego,
3. 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,
4. po znalezieniu fryzjera płaci za usługę,
5. czeka na zakończenie usługi,
6. czeka na resztę,
7. opuszcza salon i wraca do zarabiania pieniędzy.

1.2. 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).

1.2.1. 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)

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

1.2.3. 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ę $N$ samolotów. Jeśli samolotów jest mniej niż $K$ ($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).

1.2.4. Ś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.

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

1.2.6. Diabelska kolejka

Źródło: [PWit]

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

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

1.2.7. 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 $n$-poziomowe rusztowanie pozwalające dotrzeć do wyższych gałązek. Wytrzymałość rusztowania jest ograniczona — na poziomie $i$-tym może być jednocześnie co najwyżej $k_i$ skrzatów. Poziom 1 jest najniższy oraz $k_1>k_2>...>k_n$. Żeby dotrzeć na poziom $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 $i$-tym wynosi $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 $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]

(1, 2, 3) Witkowski P.: http://www.ii.uni.wroc.pl/~pwit/Dydaktyka/so/proj/projekty.html (ostatni dostęp 20.12.2017).