L5: Evacuation of the Acromyrmex Colony#
It is the year 2026, in the Argentine jungle. The final hours of peace for the Acromyrmex colony are fading away. Scouts report that massive legions of Eciton burchellii are preparing for a final assault, which will occur within the next twenty-four hours. The royal council has ordered an immediate evacuation.
However, there is one critical problem. The main food supplies, essential for the colony’s survival during migration, are located in a distant chamber reachable only through a labyrinth of dangerous tunnels. Time is short, and the terrain is unstable. Sending the entire workforce is too risky – if the workers get stuck, the colony is doomed before the attack even begins.
The Queen makes a decision. She tasks you, the court programmer, with creating a rapid simulation. Your program is to send scouts to find a path to the food chamber. Every scout that reaches the destination and finds food serves as proof of a viable route. This simulation, utilizing processes and pipes, will ultimately decide the fate of the colony.
The program takes 3 arguments: the path to a graph file, the start node index, and the destination node index with food. Example run: ./sop-ants colony08.txt 0 14.
Stages:#
Stage 1 (4 pts)#
The program takes a path to a file containing a graph definition in edge list format as an argument. The first line of the file contains the number of vertices \(V\), and each subsequent line contains a pair of numbers \(U~V\) representing a directed edge from \(U\) to \(V\). After reading the graph, the program creates a child process for each node. Each child process prints the message {ID}: {NEIGHBORS_LIST} (neighbors separated by spaces) and terminates. The main process waits for all child processes to finish.
Hint: You can assume that the number of vertices in the graph will not exceed
MAX_GRAPH_NODES.
Stage 2 (7 pts)#
Anonymous pipes must be used for inter-process communication. The main process creates one pipe for each node. A child process receives the read end of its own pipe and the write ends of the pipes of all its neighbors from the main process. The main process keeps only the write end to the start node (provided as a program argument along with the destination node). Each child process must close all unused descriptors. Node processes listen on their pipes in a loop until receiving a SIGINT signal, which releases all resources and ends the simulation.
Hint: To avoid deadlocks, you can close the read end of your own pipe in the signal handler.
Stage 3 (5 pts)#
Every 1000ms, the main process sends a new ant with a sequential ID to the start node in an infinite loop. An ant is a structure containing id, an array for the path (path), and its current length (path_length). The maximum path length is defined as a constant MAX_PATH_LENGTH. After processing an ant, each node process waits 100ms before it is ready to accept another one. Upon receiving an ant, each node appends itself to the ant’s path and then randomly forwards it to one of its neighbors. When an ant reaches the destination node, the process prints Ant {id}: found food. If an ant has nowhere to go or its path has reached the maximum length, the process prints Ant {id}: got lost.
Stage 4 (4 pts)#
After finding food, information about the path is sent to the main process via a named pipe (FIFO) called FIFO_NAME. Alternating with sending new ants, the main process non-blockingly reads messages from the named pipe and prints the discovered path in the format Ant {id} path: X1 X2 ... Xn.
Stage 5 (4 pts)#
Each node has a 2% chance of collapsing after an ant passes through. The process prints Node {ID}: collapsed and then terminates. Errors when writing to a closed pipe must be handled. An ant that could not be sent to a collapsed node is treated as lost – the sender process should then print the message Ant {id}: got lost. If the start node collapses, the main process should terminate the entire simulation.