L5: Posix Expedition#
Posix is a toroidal planet where the surface coordinates wrap around: e.g. moving North from the edge reappears at the Southern edge of the same longitude. Humanity has sent several Expeditions to explore this hostile world. Managed by an orbiting Mothership, these expeditions must scout the surface, gathering resources to survive while navigating this hostile Posix environment.
Stages:#
Stage 1 (8 pts)#
The program accepts one argument \(M\) (\(2 \leq M \leq 6\)). The main process (Mothership) forks \(M^2\) child processes (Nodes). Each node \(k \in [0, M^2-1]\) calculates its surface coordinates \((x, y)\) where \(x = \frac{k}{M}\) and \(y = k \bmod M\). Every node is assigned one unnamed pipe for receiving data. A node maintains the read-end of its own pipe and the write-ends of the pipes belonging to its four toroidal neighbors (North, South, West, East). All unused pipe ends must be closed. The Mothership must keep the write-ends of all \(M^2\) unnamed pipes open to send data to the Nodes, and close all \(M^2\) read-ends.
After setting up the required pipes and closing all unused ends, each node prints its coordinates and the number of open descriptors: Node [k] (x, y): Opened {count} descriptors. Similarly, the Mothership prints: Mothership: Opened {count} descriptors. To get the number of opened file descriptors, use the provided function count_descriptors. Right before exiting, each process must print its descriptor count again using the exact same format. The main process waits for all children to exit.
Stage 2 (7 pts)#
The Mothership acts as a deployment hub. Create a named FIFO at MOTHERSHIP_FIFO. The Mothership reads deployment commands from this FIFO in the format: SPAWN <x> <y>. The Mothership process reads the FIFO line-by-line. For every valid command, the Mothership creates a binary struct expedition_t and writes it into the pipe of the specified Node. This structure must be sent through the pipe as exactly 8 bytes of raw binary data (representing the two int fields). Expeditions are assigned unique IDs starting from 100 down to 1 and start with SUPPLIES_CAPACITY resources.
The node reads from its pipe in an infinite loop and greets the expeditions: Expedition {id}: arrived at node [k] (x, y). After MOTHERSHIP_FIFO is closed for writing the main process sends special expedition with ID=0 to all processes. When a node receives expedition with ID=0 it releases all resources and exits.
Hint: Use
cat > /tmp/mothershipto write to the named FIFO.
Stage 3 (4 pts)#
Implement the expedition survival protocol. All communication must use a fixed-size structure expedition_t from the previous stage.
Each node starts with a random amount of local_supplies (\(0\)–\(2\)). When a node receives an expedition:
- Scouting: If
local_supplies > 0, the expedition takes local supplies (adding to itssuppliescount and decrementinglocal_supplies) up to itsSUPPLIES_CAPACITYand printsExpedition {id}: Good stuff. - Movement: If the expedition’s
supplies > 0, the node prints:Expedition {id}: Tomorrow comes. The expedition’ssuppliesis decremented by 1 and after 200 ms the node forwards it to a randomly chosen neighbor. - Death: Otherwise, if the expedition’s
suppliesreached 0, it dies. The node prints:Expedition {id}: For those who come afterand itslocal_suppliesare incremented by \(2\).
Stage 4 (5 pts)#
Posix is a dangerous environment. After an expedition is forwarded, there is a 5% chance the node “Collapses”. It prints Node [k] (x, y): Collapsing, releases all resources and exits. When forwarding expeditions, detect if the destination node is collapsed and send it elsewhere safe. If a node finds all its neighbors have collapsed, it also collapses and exits. When the Mothership deploys an expedition to an already collapsed node it prints Expedition {id}: failed and continues listening for commands.