A single-lane bridge connects the two Vermont villages of North Tunbridge and South Tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked of a northbound and a southbound farmer get on the bridge at the same time. (Vermont farmers are stubborn and are unable to back up.)a. Using exactly one semaphore, design an algorithm that prevents deadlock. Do not be

concerned about starvation and inefficency.

b. Provide a solution using Monitor that is starvation-free.

Check the explanation

Explanation:

Main1.java

import java.lang.InterruptedException;

import java.lang.Thread;

import java.util.Random;

public class Main {

final private static int FARMERS = 10;

public static void main(String[] args) {

Bridge bridge = new Bridge();

Random r = new Random();

System.out.println("Running with " + FARMERS + " farmers...");

// Enter a bunch of farmers from different directions.

for (int i = 0; i < FARMERS; i++) {

Farmer farmer;

if (r.nextBoolean()) {

farmer = new SouthBoundFarmer(bridge);

} else {

farmer = new NorthBoundFarmer(bridge);

}

cross(farmer);

}

}

private static void cross(Farmer f) {

new Thread(f).start();

}

}

SouthBoundFarmer.java

public class SouthBoundFarmer extends Farmer {

public SouthBoundFarmer(Bridge b) {

super(b);

this.name = "South";

}

}

Farmer.java

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";

}

}

KINDLY CHECK THE OUTPUT BELOW :