The single-lane bridge problem


The single-lane bridge problem (one way bridge)  is a classic synchronization puzzle in concurrent programming. It models a bridge that only allows one-way traffic at a time, where cars moving in opposite directions cannot cross simultaneously, though multiple cars can cross in the same direction safely. The core problem is to prevent deadlocks (no one can cross) and starvation (one side waits forever) while maximizing throughput

Restrictive rules:

  1. A car takes the bridge if the bridge is free or on the bridge there are cars going in the same direction.
  2. If cars, coming from the other direction arrive, while there are cars on the bridge, the opposing cars wait until the bridge is clear.

bridge - resource

public class Bridge {
    private int nVh;
    Bridge(){
        nVh = 0;        //nVh>0 - vehicles crossing  from right to left are on the bridge
                             //nVh<0 - vehicles crossing  from left to right are on the bridge
    }
    synchronized public int brN(){
        return nVh;  
    }
    synchronized public void takeB(boolean lr ){
        while((nVh>0)&& (lr==true)||
              (nVh<0) && (lr==false)){
            System.out.println("\t"+Thread.currentThread().getName()+" waiting");
            try{     wait();   }
            catch(InterruptedException e){
                System.err.println(e);
            }
        }
        if (lr) nVh--;
        else nVh++;
        System.out.println(Thread.currentThread().getName()+" on the bridge");
    }
    synchronized public void leaveB(boolean lr ){
        if (nVh>0) nVh--;
        else nVh++;
        System.out.println("\t\t"+Thread.currentThread().getName()+" leave the bridge");
        notifyAll();
    }
}

Vehicles - threads

public class Vehicle extends Thread{
    boolean lr;
    Bridge b;
    String name;
    static int num;
    Vehicle(boolean lr, Bridge b){
        this.lr=lr;
        this.b = b;
        name = "V "+ ++num + (lr?" left->":" <-right");
        super.setName(name);
    }
    public void run(){
        try {           //arriving to bridge
            sleep(20);
        } catch (InterruptedException e){} 
        b.takeB(lr);
        try {         // crossing the bridge
            sleep(200);
        } catch (InterruptedException e){} 
        b.leaveB(lr);
    }
}

The model:

public class Circ {
    public static void main(String arg[]){
        Bridge b = new Bridge();
        for(int i = 0; i < 20; i++){
            try {          
                Thread.sleep(20);
            } catch (InterruptedException e){}
            (new Vehicle(Math.random()>0.5?true:false, b)).start();
        }
    }
}

Exercise: Modify the program to introduce the rule:

Rule 3.The bridge should not be blocked by an endless stream of cars coming from one direction.

Another example:

Two consecutive one-way bridges. A place without restriction of places in between. Generate a random number of cars that have to pass. Each car waits a random amount of time before passing and needs a certain amount of time passing. To enter the bridge you must not have cars driving in the opposite direction. Create a program in Java to model the situation.

If the number of places between two bridges is limited the task becomes much more complicated! For those who like challenges!