Bot Arena

Operating systems assingment for demonstrating how deadlocks occur.

Group members

• Enzo Moraes da Costa
• Gabriel de Menezes Balthazar
• Marcos Vinícius Alves Martins
• Pedro Caetano Pires

Professor

• Helio do Nascimento Cunha Neto

deadlock.mov

Note

First of all, we must emphasize that this deadlock prevention is on a separate branch named 'preventDeadlock', and not on main.

How to run the program

Prerequisites

• Python 3.7 or higher
• An operating system that supports the curses library (Linux, macOS, or Windows with WSL)

Run instructions

1. Clone the repository:

   git clone https://github.com/caetano-dev/JogoSO1.git

2. Navigate to the project directory:

    cd JogoSO1

3. Run the main program:

   python3 main.py

   or

   python main.py

4. Game controls:

   • Arrow keys: Move the player robot (P)
   • Q: Quit the game
   • The game runs automatically until only one robot survives or all die

Output files

log.txt: Log file with the main actions of robots and mutexes. The log is automatically cleared on each run.

Important notes

The terminal must be large enough to display the full grid (minimum 40x25 characters). On Windows systems, it is recommended to use WSL or a terminal compatible with curses. To test the version without deadlock, switch to the preventDeadlock branch with:

git checkout preventDeadlock

How does it work?

During development we identified that a deadlock could occur in situations where multiple robots compete for the same shared resources: the batteries[...]

Deadlock scenario

A deadlock occurs when two or more robots acquire mutexes in different orders, creating a circular dependency:

1. Robot A acquires the grid_mutex and then tries to acquire the battery_mutex for a specific battery
2. Robot B already holds the battery_mutex of the same battery and tries to acquire the grid_mutex
3. Result: Robot A waits for the mutex Robot B holds, while Robot B waits for the mutex Robot A holds

This situation creates a circular wait where neither robot can proceed, freezing the whole system.

Conditions for deadlock

Deadlock occurs when all four conditions are met:

• Mutual exclusion: Mutexes can be held by only one robot at a time
• Hold and wait: Robots hold resources while waiting for others
• No preemption: Mutexes cannot be forcibly taken away
• Circular wait: There is a cycle of dependencies between robots

Example of detected deadlock

Robot 0 acquires grid_mutex and tries to move to battery 1, while robot 4 already holds the battery_mutex for battery 1 and tries to acquire the grid_mutex:

Robot 0 (holds grid_mutex, wants battery_mutex):

[12:15:15.793] Robo 0 - grid_mutex ACQUIRED
[12:15:15.796] Robo 0 - Found battery 1, acquiring mutex
[12:15:15.796] DEADLOCK RISK: Robo 0 - Trying to acquire battery_mutex while holding grid_mutex
[12:15:15.848] Robo 0 - TRYING TO ACQUIRE battery_mutex of battery 1

Robot 4 (holds battery_mutex, wants grid_mutex):

[12:15:16.033] Robo 4 - ACQUIRING grid_mutex to move from (2,12) to (3,12)
[12:15:16.033] DEADLOCK RISK: Robo 4 - Acquiring grid_mutex first
[12:15:16.033] DEADLOCK RISK: Robo 4 - Already holds battery mutex of battery 1

Result: Deadlock occurs and no other robot can move, causing the entire game to freeze.

Prevention implemented

To solve this problem, we implemented ordered resource acquisition:

Consistent mutex acquisition order

All robots now follow the same acquisition order: battery_mutex → grid_mutex

# Consistent order in both try_move and try_move_to_battery
if not self.acquire_battery_mutex(battery_id): # If it can't acquire the battery mutex, it doesn't proceed
    #...
    return
try:
    #...
    with self.shared_state.grid_mutex: # Acquire the grid mutex
        # Process movement

This implementation is present in the try_move and try_move_to_battery functions of the robot.py class, ensuring that deadlocks do not occur.

In the logs:

[19:14:20.152] Robo 1 - TRYING TO ACQUIRE battery_mutex of battery 1
[19:14:20.152] Robo 1 - battery_mutex of battery 1 SUCCESSFULLY ACQUIRED
[19:14:20.152] Robo 1 - ACQUIRING grid_mutex to move from (15,4) to (15,3)
[19:14:20.152] DEADLOCK PREVENTION: Robot 1 - Following consistent order: battery_mutex → grid_mutex
[19:14:20.153] Robo 1 - grid_mutex ACQUIRED

What is what?

- main.py

This is the module responsible for initializing the program. Right away it clears any existing log file to ensure the log only reflects a single execution[...]

Main functions:

main(stdscr)

Main function that manages the entire game lifecycle. It initializes the shared state, creates and starts robot processes, manages the graphical interface using curses, and processes user input[...]

update_alive_count(shared_state, num_robots)

Counts how many robots are still alive in the game, determines if there is a winner or a tie, and updates the game's flags. This function is called continuously to check whether the game has ended.

- viewer.py

This module is responsible for printing the game to the screen, such as the map, robot statuses, and the final game message indicating Victory or Tie.

Main functions:

display_grid(self, stdscr)

Main rendering function that draws the game grid, robot statuses, counters and control messages on the screen.

is_robot_on_battery(self, x, y)

Checks whether a robot is located on a battery to show the charging indicator (⚡) in the interface.

format_game_status_message(self, flags)

Formats end-of-game messages (victory or tie) based on current game flags.

- robot.py

Responsible for managing everything related to robots, such as initializing robots with random attributes, attaching shared memory to each robot, initializing the batteries[...]

Main functions:

__init__(self, robot_id, is_player, shared_objects)

Constructor for the Robot class that initializes a robot with a unique ID, determines if it is player-controlled, and sets up the structures required for inter-process communication.

attach_shared_memory(self)

Attaches the robot to the shared memory state, allowing it to read and modify shared data such as the grid, robot states and batteries.

initialize_arena_if_needed(self)

Initializes the game arena only once. The first robot to call this function places the batteries on the map and initializes the shared data for all robots at random positions.

place_batteries(self)

Randomly positions batteries on the map, ensuring each battery occupies 2 horizontal cells and does not overlap with barriers.

sense_act(self)

Main decision-and-action loop for the robot. It analyzes the environment, decides next actions (move or collect battery), and executes them.

try_move(self, dx, dy, robot_data_snapshot)

Attempts to move the robot to a new position. Checks collisions, handles movement to batteries, and initiates duels when encountering other robots. This function is where deadlock could occur[...]

try_move_to_battery(self, old_x, old_y, new_x, new_y)

Specialized move version that first acquires the battery mutex before the grid mutex.

initiate_duel(self, other_robot_id, old_x, old_y, new_x, new_y)

Handles combat between two robots when they occupy the same position. Calculates each robot's power (2×Strength + Energy) and determines the winner, which can result in a tie where both die[...]

acquire_battery_mutex(self, battery_id) / release_battery_mutex(self)

Functions that manage safe acquisition and release of battery mutexes, ensuring only one robot may interact with a specific battery at a time.

housekeeping(self)

A separate thread that runs in parallel to the main loop, responsible for updating the robot's energy.

update_robot_state(self, robot_id, new_x=None, new_y=None, energy_difference=0, new_status=None)

Central function to modify a robot's state. Updates position, energy and status, automatically checking if the robot died due to lack of energy.

find_nearest_battery_direction(self, grid_snapshot, robot_data)

Analyzes the grid to find the nearest battery and returns the direction to move toward it. Used only for non-player-controlled robots.

- shared_memory.py

This is where all data that needs to be shared across program modules is stored, to keep these data centralized and avoid transfer errors[...]

Main functions:

create_shared_state()

Creates and initializes all shared data structures using multiprocessing.Manager(). Sets up the grid with borders and obstacles, initializes arrays for robots and batteries, and creates all[...]

get_grid_cell(self, x, y) / set_grid_cell(self, x, y, value)

Functions to read and write individual grid cells. They include bounds checking to avoid invalid accesses.

get_robot_data(self, robot_id) / set_robot_data(self, robot_id, robot_data)

Manage access to robot data (position, energy, strength, speed, status).

get_battery_data(self, battery_id) / set_battery_data(self, battery_id, battery_data)

Control access to battery information (position, collection state, current owner).

take_grid_snapshot(self)

Creates a full copy of the current grid state for analysis.

The run cycle

Right after starting, you will see the screen below:

From there you will see each robot's status such as energy, strength, and speed, as well as whether a robot is on a battery receiving charge, indicated by the lightning icon next to it.

Execution flow

Order of execution:

1. main.py clears logs and initializes shared structures
2. Creates and starts NUM_ROBOTS Robot processes
3. Each robot attaches to shared memory and initializes the arena (only the first one does the full initialization)
4. Robots start their sense_act() loops and housekeeping() threads
5. main() enters the graphical interface loop and processes user input
6. update_alive_count() continuously checks end-of-game conditions

Mutexes used:

• init_mutex: Ensures one-time arena initialization
• grid_mutex: Protects modifications to the game grid
• robots_mutex: Synchronizes updates to robot data
• battery_mutexes[]: Array of individual mutexes, one for each battery