A single-lane bridge connects the two Vermont villages of North Tun-bridge and South Tunbridge. Farmers use the bridge to bring food to the neighboring town. If a northbound and southbound farmer get on the bridge at the same time, the bridge will become deadlocked. Using semaphores and/or mutex locks, come up with an algorithm in pseudocode that will prevent deadlocks. Your solution should be starvation free (i. e. southbound farmers cannot prevent northbound farmers from crossing forever and vice versa).

see explaination

Explanation:

import java.lang.InterruptedException;

import java.util.Random;

public class Farmer implements Runnable {

private Bridge bridge;

private Random random;

protected String name;

public Farmer(Bridge b) {

this.bridge = b;

this.random = new Random();

}

public void crossBridge(Bridge bridge) {

System.out.println("[" + this.name + "] Waiting to enter bridge...");

try {

bridge.enter();

System.out.println("[" + this.name + "] Entering bridge...");

// Crossing bridge...some farmers are fast, others are slow :P

Thread.sleep(1000 + random.nextInt(9000));

System.out.println("[" + this.name + "] Leaving bridge...");

} catch (InterruptedException e) {

System.out.println("...Interrupted!");

} finally {

bridge.leave();

}

}

public void run() {

this.crossBridge(this.bridge);

}

}

Bridge.java

import java.lang.InterruptedException;

import java.util.concurrent.Semaphore;

public class Bridge {

private Semaphore lock;

public Bridge() {

this.lock = new Semaphore(1);

}

public void enter() throws InterruptedException {

this.lock.acquire();

}

public void leave() {

this.lock.release();

}

}

NorthBoundFarmer.java

public class NorthBoundFarmer extends Farmer {

public NorthBoundFarmer(Bridge b) {

super(b);

this.name = "North";

}

}