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).
Zadanie z tej grupy należy zrealizować na mechanizmach System V IPC (pamięć współdzielona, semafory i kolejki komunikatów).
Zadanie polega na realizacji problemu czytelników i pisarzy (opis wersji klasycznej w Wikipedii), przy czym:
Zadanie oparte jest na problemie ucztujących filozofów (opis w Wikipedii), przy czym:
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.
Zadanie oparte jest na problemie palaczy tytoniu (opis w Wikipedii (po angielsku)) przy czym:
Zadanie oparte jest na problemie śpiącego golibrody, opisanym w Wikipedii w wersji dla jednego fryzjera/golibrody.
Fryzjer działa cyklicznie wg. schematu:
Klient działa cyklicznie wg. schematu:
Zadanie z tej grupy należy zrealizować na wątkach z użyciem muteksów i zmiennych warunkowych w standardzie POSIX (pthread).
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)
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.
Ź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ę samolotów. Jeśli samolotów jest mniej niż (), 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).
Ź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.
Ź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.
Źródło: [PWit]
Wagonik kolejki może pomieścić pasażerów spośród ogólniej liczby użytkowników (). Wagonik może wyruszyć tylko wtedy, gdy jest pełny, czyli gdy pasażerów zdeklaruje gotować przejazdu.
Cel zadania: synchronizacja pasażerów i wagonika.
Małe skrzaty stroją choinkę na Boże Narodzenie, zawieszając na niej ozdoby, dostarczane przez Św. Mikołaja. W tym celu skonstruowały -poziomowe rusztowanie pozwalające dotrzeć do wyższych gałązek. Wytrzymałość rusztowania jest ograniczona — na poziomie -tym może być jednocześnie co najwyżej skrzatów. Poziom 1 jest najniższy oraz . Żeby dotrzeć na poziom -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 -tym wynosi . 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 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). |