🚂 Train Deadlock Concurrency Problem

Problem Statement

• Multiple trains run on a shared circular track (like a subway loop).

• Only one train can occupy a track segment at a time (mutual exclusion).

• Trains must avoid collisions (race conditions) and deadlocks (gridlock where all trains are stuck waiting).

• Goal: Implement a thread-safe system where trains move without crashing or freezing.

💡 Solution Approaches

1. Basic Version (Using Semaphores)

• Each track segment is guarded by a semaphore (1 permit = available, 0 = occupied).

• Trains acquire the next segment’s semaphore before moving.

• Risk: If all trains hold one segment and wait for the next → circular deadlock.

Java Implementation

import java.util.concurrent.Semaphore;

public class TrainDeadlockBasic {
    static final int NUM_SEGMENTS = 5;
    static Semaphore[] segments = new Semaphore[NUM_SEGMENTS];

    public static void main(String[] args) {
        // Initialize segments (all available initially)
        for (int i = 0; i < NUM_SEGMENTS; i++) {
            segments[i] = new Semaphore(1);
        }

        // Create 3 trains (threads)
        for (int i = 0; i < 3; i++) {
            new Thread(new Train(i)).start();
        }
    }

    static class Train implements Runnable {
        private int id;
        private int currentSegment;

        public Train(int id) {
            this.id = id;
            this.currentSegment = id % NUM_SEGMENTS; // Start at different segments
        }

        @Override
        public void run() {
            while (true) {
                try {
                    int nextSegment = (currentSegment + 1) % NUM_SEGMENTS;

                    System.out.printf("Train %d WAITING for segment %d\n", id, nextSegment);
                    segments[nextSegment].acquire(); // Request next segment
                    System.out.printf("Train %d ENTERED segment %d\n", id, nextSegment);

                    Thread.sleep(1000); // Simulate travel time

                    segments[currentSegment].release(); // Leave current segment
                    System.out.printf("Train %d LEFT segment %d\n", id, currentSegment);

                    currentSegment = nextSegment;
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
    }
}

⚠️ Problem: Deadlock Risk!

• If all trains hold their current segment and wait for the next → system freezes.

• Example:

  • Train 0 holds S0, waits for S1.

  • Train 1 holds S1, waits for S2.

  • Train 2 holds S2, waits for S0.
    → Circular deadlock!