L5: Ewakuacja kolonii Acromyrmex#
Jest rok 2026, w argentyńskiej dżungli. Ostatnie godziny spokoju dla kolonii Acromyrmex dobiegają końca. Zwiadowcy donoszą, że ogromne legiony Eciton burchellii szykują się do ostatecznego ataku, który nastąpi w ciągu następnych dwudziestu czterech godzin. Królewska rada wydała rozkaz natychmiastowej ewakuacji.
Istnieje jednak jeden krytyczny problem. Główne zapasy żywności, niezbędne do przeżycia kolonii podczas migracji, znajdują się w odległej komorze, do której można dotrzeć jedynie przez labirynt niebezpiecznych tuneli. Czas jest krótki, a teren niestabilny. Wysłanie całej siły roboczej jest zbyt ryzykowne — jeśli robotnice utkną, kolonia zginie jeszcze przed atakiem.
Królowa podejmuje decyzję. Powierza Tobie, dworskiemu programiście, zadanie stworzenia szybkiej symulacji. Twój program ma wysyłać zwiadowców, aby znaleźli ścieżkę do komory z żywnością. Każdy zwiadowca, który dotrze do celu i znajdzie pożywienie, stanowi dowód na istnienie przejezdnej trasy. Ta symulacja, wykorzystując procesy i łącza, ostatecznie zadecyduje o losie kolonii.
Program przyjmuje 3 argumenty: ścieżkę do pliku z grafem, indeks węzła startowego oraz indeks węzła docelowego z pożywieniem. Przykładowe uruchomienie: ./sop-ants colony08.txt 0 14.
Etapy:#
Etap 1 (4 pkt)#
Program przyjmuje jako argument ścieżkę do pliku zawierającego definicję grafu w formacie listy krawędzi. Pierwsza linia pliku zawiera liczbę wierzchołków \(V\), a każda kolejna linia zawiera parę liczb \(U~V\) reprezentującą skierowaną krawędź od \(U\) do \(V\). Po wczytaniu grafu program tworzy proces potomny dla każdego węzła. Każdy proces potomny wypisuje komunikat {ID}: {NEIGHBORS_LIST} (sąsiedzi oddzieleni spacjami) i kończy działanie. Proces główny czeka na zakończenie wszystkich procesów potomnych.
Wskazówka: Możesz założyć, że liczba wierzchołków w grafie nie przekroczy
MAX_GRAPH_NODES.
Etap 2 (7 pkt)#
Do komunikacji między procesami należy użyć łączy nienazwanych (anonymous pipes). Proces główny tworzy jedno łącze dla każdego węzła. Proces potomny otrzymuje od procesu głównego koniec do odczytu własnego łącza oraz końce do zapisu łącz wszystkich swoich sąsiadów. Proces główny zachowuje jedynie koniec do zapisu łącza węzła startowego (podanego jako argument programu wraz z węzłem docelowym). Każdy proces potomny musi zamknąć wszystkie nieużywane deskryptory. Procesy węzłów nasłuchują na swoich łączach w pętli, aż do otrzymania sygnału SIGINT, który zwalnia wszystkie zasoby i kończy symulację.
Wskazówka: Aby uniknąć zakleszczeń, można zamknąć koniec do odczytu własnego łącza w procedurze obsługi sygnału.
Etap 3 (5 pkt)#
Co 1000 ms proces główny wysyła nową mrówkę z kolejnym numerem ID do węzła startowego w nieskończonej pętli. Mrówka jest strukturą zawierającą id, tablicę dla ścieżki (path) oraz jej aktualną długość (path_length). Maksymalna długość ścieżki jest zdefiniowana jako stała MAX_PATH_LENGTH. Po przetworzeniu mrówki każdy proces węzłowy czeka 100 ms, zanim będzie gotowy do przyjęcia kolejnej. Po otrzymaniu mrówki każdy węzeł dopisuje się do jej ścieżki, a następnie losowo przekazuje ją do jednego ze swoich sąsiadów. Gdy mrówka dotrze do węzła docelowego, proces wypisuje Ant {id}: found food. Jeśli mrówka nie ma dokąd pójść lub jej ścieżka osiągnęła maksymalną długość, proces wypisuje Ant {id}: got lost.
Etap 4 (4 pkt)#
Po znalezieniu pożywienia informacja o ścieżce jest wysyłana do procesu głównego za pomocą nazwanego łącza (FIFO) o nazwie FIFO_NAME. Naprzemiennie z wysyłaniem nowych mrówek, proces główny nieblokująco odczytuje wiadomości z nazwanego łącza i wypisuje odkrytą ścieżkę w formacie Ant {id} path: X1 X2 ... Xn.
Etap 5 (4 pkt)#
Każdy węzeł ma 2% szans na zawalenie się po przejściu mrówki. Proces wypisuje Node {ID}: collapsed i kończy działanie. Błędy podczas pisania do zamkniętego łącza muszą być obsługiwane. Mrówka, która nie mogła zostać wysłana do zawalonego węzła, jest traktowana jako zagubiona — proces nadawcy powinien wtedy wypisać komunikat Ant {id}: got lost. Jeśli węzeł startowy się zawali, proces główny powinien zakończyć całą symulację.