L6: Habemus Regem!#

Po śmierci Króla Michała Korybuta Wiśniowieckiego w 1673 roku, przyszedł czas na wybór nowego króla Rzeczypospolitej. Dziesiątki tysięcy magnatów i szlachciców przybyli do Koła pod Warszawą, gotowi zobaczyć kandydatów, debatować i głosować. Jedynym problemem było zakwaterowanie osób z całego kraju na czas trwania sejmu elekcyjnego. Z tego powodu, mieszkańcy Warszawy zostali zobowiązani do przyjęcia niektórych przybyszy.

Rada bogatego, lecz małego miasta (Warszawa wtedy zajmowała jedynie obszar Starego Miasta) widzi poważny problem z pomieszczeniem gości. Zarówno szlachcice, jak i mieszczanie powinni mieć (względnie) komfortowe warunki. Jeden z członków rady wpadł na pomysł stworzenia systemu rezerwacji dla szlachciców. Interrex Kazimierz Florian Czartoryski uznał to za wspaniały pomysł i postanowił pomóc — ofiarował maszynę liczącą kompatybilną z POSIX-em oraz kilku chłopów do wprawienia trybików maszyny w ruch. Brakuje jedynie programu. Pomóż Niezwyciężonej i zaimplementuj system rezerwacji!

Etapy:#

Etap 1 (6 pkt)#

Program przyjmuje dwa argumenty pozycyjne: \(1 \leq n \leq 15\) — liczba kamienic w Starej Warszawie — oraz \(5 \leq m \leq 20\) — liczba szlachciców do zakwaterowania. Utwórz anonimowy blok pamięci dzielonej zawierający \(n\) współdzielonych muteksów. Następnie utwórz \(m\) procesów reprezentujących szlachciców. Każdy szlachcic jest leniwy i próbuje zająć dom najbliżej bramy miejskiej — przeiteruj po muteksach i zajmij pierwszy dostępny (Wskazówka: można użyć funkcji pthread_mutex_trylock). Po zablokowaniu muteksu proces-szlachcic wypisuje [<PID>] Jakże komfortowy dom nr <i>!, gdzie \(i\) oznacza indeks muteksu, śpi przez 300 ms, odblokowuje muteks i kończy działanie. Gdy żaden muteks nie jest dostępny, wypisuje [<PID>] Po cóż tu przybyłem? i kończy działanie.

Proces nadrzędny czeka na wszystkie procesy potomne i kończy działanie.

We wszystkich etapach, każdy proces musi zwolnić wszystkie użyte zasoby przed poprawnym zakończeniem.

W kolejnych etapach każdy obiekt synchronizacji i zmienne współdzielone muszą znajdować się w utworzonym anonimowym bloku pamięci, o ile nie zaznaczono inaczej (może być konieczna zmiana rozmiaru bloku).

Etap 2 (5 pkt)#

Ze względu na dużą liczbę niezadowolonych szlachciców, którzy nie znaleźli zakwaterowania, rada miasta planuje stworzyć poczekalnię. Utwórz współdzieloną zmienną warunkową powiązaną z licznikiem wolnych domów (chronionym przez muteks). Po zajęciu domu (zablokowaniu muteksu) zmniejsz licznik. Gdy proces-szlachcic nie znajdzie miejsca, zamiast kończyć działanie, czeka na zmiennej warunkowej, aż inny proces opuści dom i zwiększy licznik. Proces opuszczający dom powiadamia jeden z oczekujących procesów. Po powiadomieniu, proces-szlachcic wypisuje [<PID>] Spróbuję jeszcze raz i ponownie przeszukuje domy, aż znajdzie wolny muteks lub — jeśli się nie uda — wraca do poczekalni. Każdy szlachcic powinien znaleźć dom.

Wskazówka: inicjalizacja współdzielonej zmiennej warunkowej przebiega analogicznie do inicjalizacji współdzielonego muteksu (należy użyć pthread_condattr_t zamiast pthread_mutexattr_t).

Etap 3 (3 pkt)#

Tłum szlachty zaczyna napierać na bramę miejską. Wzmocnij mury za pomocą semafora. Każdy szlachcic, przed przeszukiwaniem domów, otwiera nazwany semafor /gate (jeśli nie istnieje, tworzy go z wartością początkową 10) i czeka na nim. Po zakończeniu pobytu w domu (i przed zakończeniem działania) zwiększa wartość semafora o 1.

W procesie rodzicu, usuń semafor zarówno na początku programu (jeśli istnieje), jak i na jego końcu.

Etap 4 (5 pkt)#

Polscy szlachcice słyną z porywczego charakteru. Potrafią łatwo wpaść w furię, co objawia się zniszczonymi meblami, wybitymi szybami, a nawet zburzonymi ścianami.¹ Rada miasta chciałaby wiedzieć, które domy zostały zniszczone, aby skutecznie zaplanować naprawy po skończonym sejmie.

W procesie głównym usuń (jeśli istnieje), a następnie utwórz i zmapuj nazwany obiekt pamięci dzielonej /houses o rozmiarze \(n\) liczb całkowitych i wypełnij go zerami. Następnie zamknij obiekt pamięci i zwolnij zasoby powiązane z pamięcią dzieloną przed utworzeniem procesów potomnych.

Procesy-szlachcice, po utworzeniu, otwierają i mapują ten obiekt pamięci. Proces, który zablokował \(i\)-ty muteks, ma 10% szans na uszkodzenie domu. W takim przypadku wypisuje jeden (losowy) z komunikatów:

• [<PID>] Czas wyburzyć ścianę w domu <i>!
• [<PID>] W domu <i> jest tyle miodu pitnego, wypiję wszystko!
• [<PID>] Co? Brak wanny w domu <i>? Sam ją wykopię!

oraz ustawia \(i\)-tą wartość w pamięci na \(1\) przed odblokowaniem muteksu.

W procesie głównym, po zakończeniu wszystkich procesów potomnych, otwórz ponownie obiekt pamięci, wypisz jego zawartość i usuń go z systemu plików.

Etap 5 (5 pkt)#

Proces-szlachcic, który napotka uszkodzony dom, natychmiast umiera z wściekłości. Przed czekaniem 300 ms, sprawdza odpowiednią wartość. Jeśli jest niezerowa, wypisuje [<PID>] Dom <i> to ostatnia rzecz, jaką zobaczę, zwalnia semafor i wywołuje abort() (przy zablokowanym muteksie). Gdy inny proces spróbuje wejść do domu, w którym znajduje się ciało, wypisuje [<PID>] Nie może tak być! Sam posprzątam dom <i>! i ustawia flagę z powrotem na 0.

Jeśli uruchomisz teraz swoje rozwiązanie kilka razy z większym prawdopodobieństwem zniszczeń (np. 50%), program może się zawiesić (dlaczego?). Aby uniknąć zakleszczenia, wykryj w procesie głównym, czy proces potomny zakończył się nieprawidłowo (Wskazówka: można użyć Status Information oraz makra WIFEXITED), a następnie — donośnym krzykiem z zaświatów — powiadom wszystkie procesy oczekujące w poczekalni.

Kod startowy#

• Makefile
• ops-booking.c

Download as zip