L5: Ekspedycja Posix#
Posix to planeta w kształcie torusa, na której współrzędne powierzchniowe ulegają zapętleniu: np. poruszając się na północ poza krawędź, pojawiamy się na południowej krawędzi tego samego południka. Ludzkość wysłała kilka ekspedycji w celu zbadania tego niebezpiecznego świata. Nadzorowane przez orbitujący statek-matkę, ekspedycje muszą przeszukiwać powierzchnię i gromadzić zasoby niezbędne do przetrwania w nieprzyjaznym środowisku Posix.
Etapy:#
Etap 1 (8 pkt)#
Program przyjmuje jeden argument \(M\) (\(2 \leq M \leq 6\)). Proces główny (statek-matka) tworzy \(M^2\) procesów potomnych (węzły). Każdy węzeł \(k \in [0, M^2-1]\) wyznacza swoje współrzędne \((x, y)\), gdzie \(x = \frac{k}{M}\), a \(y = k \bmod M\). Każdy węzeł posiada przypisane jedno łącze nienazwane służące do odbierania danych. Węzeł zarządza końcem do odczytu własnego łącza oraz końcami do zapisu łącz swoich czterech sąsiadów w topologii torusa (północ, południe, zachód, wschód). Wszystkie nieużywane deskryptory łącz muszą zostać zamknięte. Statek-matka musi utrzymywać otwarte końce do zapisu wszystkich \(M^2\) łącz nienazwanych (aby móc wysyłać dane do węzłów) oraz zamknąć wszystkie \(M^2\) końce do odczytu.
Po skonfigurowaniu łączy i zamknięciu niepotrzebnych deskryptorów, każdy węzeł wypisuje swoje współrzędne oraz liczbę otwartych deskryptorów: Node [k] (x, y): Opened {count} descriptors. Podobnie statek-matka wypisuje: Mothership: Opened {count} descriptors. Do zliczenia otwartych deskryptorów plików należy użyć dostarczonej funkcji count_descriptors. Tuż przed zakończeniem pracy każdy proces musi ponownie wypisać liczbę deskryptorów w tym samym formacie. Proces główny oczekuje na zakończenie wszystkich procesów potomnych.
Etap 2 (7 pkt)#
Statek-matka pełni rolę centrum logistycznego. Utwórz łącze nazwane pod ścieżką MOTHERSHIP_FIFO. Statek-matka odczytuje z niego komendy rozmieszczenia ekspedycji w formacie: SPAWN <x> <y>. Proces statku-matki przetwarza FIFO linia po linii. Dla każdej poprawnej komendy statek-matka tworzy strukturę binarną struct expedition_t i przesyła ją do łącza odpowiedniego węzła. Struktura musi zostać przesłana jako dokładnie 8 bajtów surowych danych binarnych (reprezentujących dwa pola int). Ekspedycje otrzymują unikalne identyfikatory (ID) malejąco od 100 do 1 i rozpoczynają misję z zapasami o wielkości SUPPLIES_CAPACITY.
Węzeł odczytuje dane ze swojego łącza w nieskończonej pętli i wita przybywające ekspedycje komunikatem: Expedition {id}: arrived at node [k] (x, y). Gdy MOTHERSHIP_FIFO zostanie zamknięte do zapisu, proces główny wysyła do wszystkich węzłów specjalną ekspedycję o ID=0. Otrzymanie ekspedycji o ID=0 oznacza dla węzła polecenie zwolnienia zasobów i zakończenia pracy.
Wskazówka: Do pisania do łącza nazwanego można użyć polecenia
cat > /tmp/mothership.
Etap 3 (4 pkt)#
Zaimplementuj protokół przetrwania ekspedycji. Wszelka komunikacja musi odbywać się przy użyciu struktury expedition_t o stałym rozmiarze.
Każdy węzeł rozpoczyna z losową ilością lokalnych zapasów local_supplies (z zakresu \(0\)–\(2\)). Po otrzymaniu ekspedycji węzeł wykonuje następujące kroki:
- Rekonesans: Jeśli
local_supplies > 0, ekspedycja przejmuje lokalne zapasy (zwiększając swój liczniksuppliesi zmniejszająclocal_supplies) do maksymalnego poziomuSUPPLIES_CAPACITY, po czym węzeł wypisujeExpedition {id}: Good stuff. - Przemieszczanie: Jeśli ekspedycja posiada zapasy (
supplies > 0), węzeł wypisuje:Expedition {id}: Tomorrow comes. Liczniksuppliesekspedycji jest zmniejszany o 1, a po upływie 200 ms węzeł przesyła ją do losowo wybranego sąsiada. - Śmierć: W przeciwnym razie, gdy poziom
suppliesspadnie do 0, ekspedycja ginie. Węzeł wypisuje:Expedition {id}: For those who come after, a jego poziomlocal_supplieszostaje zwiększony o \(2\).
Etap 4 (5 pkt)#
Posix to skrajnie niebezpieczne środowisko. Po przekazaniu ekspedycji dalej, istnieje 5% szans, że węzeł ulegnie “zapadnięciu”. Wypisuje wtedy komunikat Node [k] (x, y): Collapsing, zwalnia zasoby i kończy pracę. Podczas przesyłania ekspedycji należy sprawdzać, czy węzeł docelowy nie uległ zapadnięciu – jeśli tak, należy spróbować wysłać ją w inne, bezpieczne miejsce. Jeśli węzeł stwierdzi, że wszyscy jego sąsiedzi są zapadnięci, sam również się zapada i kończy działanie. W przypadku próby wysłania nowej ekspedycji przez statek-matkę do węzła, który już nie istnieje, statek-matka wypisuje Expedition {id}: failed i kontynuuje nasłuchiwanie komend.