Question

A single-lane bridge connects village A to village B. Farmers in the two villages use this bridge to deliver their products to the neighboring town. The bridge can become deadlocked if a farmer from village A and a farmer from village B get on the bridge at the same time. Using semaphores and/or mutex locks (do not be concerned about starvation) implement your solution in Java. In particular, represent village A and village B farmers as separate threads. Once a farmer is on the bridge, the associated thread will sleep for a random period of time, representing traveling across the bridge.

Answer 1

a.

semaphore ok_to_cross = 1;

void enter_bridge() {

P(ok_to_cross);

}

void exit_bridge() {

V(ok_ to_cross);}

b.

/*the correct-direction enter function must be called before getting on

the bridge. The corresponding exit function must be called when the

thread is ready to leave the bridge.*/

monitor bridge {

int num_waiting_north = 0;

int num_waiting_south = 0;

int on_bridge = 0;

condition ok_to_cross;

int prev = 0;

void enter_bridge_north() {

num_waiting_north++;

while (on_bridge ||(prev == 0 && num_waiting_south > 0))

ok_to_cross.wait();

on_bridge=1;

num_waiting_north--;

prev = 0;

}

void exit_bridge_north() {

on_bridge = 0;

ok_to_cross.broadcast();

}

void enter_bridge_south() {

num_waiting_south++;

while (on_bridge ||(prev == 1 && num_waiting_north > 0))

ok_to_cross.wait();

on_bridge=1;

num_waiting_south--;

prev = 1;

}

void exit_bridge_south() {

on_bridge = 0;

ok_to_cross.broadcast();

}

}

Note that this problem can have many alternative solutions. One alternative solution is as follows

(adapted from one student’s homework submission):

Monitor Bridge {

int nWaiting=0, sWaiting=0, sOnBridge=0, nOnBridge=0;

condition north_turn, south_turn;

enterNorth() {

if (sWaiting>0 || sOnBridge>0)

{

nWaiting++;

wait(north_turn);

while (sOnBridge>0)

wait(north_turn);

nWaiting--;

}

nOnBridge++;

if (sWaiting==0)

signal(north_turn);

}

exitNorth() {

nOnBridge--;

if (nOnBridge ==0)

signal(south_turn);

}

enterSouth() {

if (nWaiting>0 || nOnBridge>0)

{

sWaiting++;

wait(south_turn);

while (nOnBridge>0)

wait(south_turn);

sWaiting--;

}

sOnBridge++;

if (nWaiting==0)

signal(south_turn);

}

exitSouth() {

sOnBridge- -;

if(sOnBridge == 0)

signal(north_turn);

}

}