A student majoring in anthropology and minoring in computer science has embarked
ID: 3866443 • Letter: A
Question
A student majoring in anthropology and minoring in computer science has embarked on a research project to see if African baboons can be taught about deadlocks. He locates a deep canyon and fastens a rope across it, so the baboons can cross hand-overhand. Several baboons can cross at the same time, provided that they are all going in the same direction. If eastward-moving and westward-moving baboons ever get onto the rope at the same time, a deadlock will result (the baboons will get stuck in the middle) because it is impossible for one baboon to climb over another one while suspended over the canyon. If a baboon wants to cross the canyon, he must check to see that no other baboon is currently crossing in the opposite direction. Write a program using semaphores that avoids deadlock. Do not worry about a series of eastward-moving baboons holding up the westward-moving baboons indefinitely.
Explanation / Answer
// Program
enum direction { west=0 , east=1 } // in the problem 2 directions are mentioned weast & east.
semaphore mutex; // initially 1 , it protects the critical sections
semaphore block[2]; // one for each direction. Each one initailly 0 , so it is always sleep on first P
int blocked[2]; // number of baboons waiting on each side
int travelers[2]; // number of baboons on rope towards each direction
baboon(direction d)
{
int reversedir = !d; // for reverse direction
mutex->P();
while (travelers[reversedir])
{
blocked[d]++; // to block
mutex->V(); // mutex for block
block[d]->P();
mutex->P();
}
travelers[d]++; // for to cross freely
mutex->V(); // for crossing bridge
mutex->P();
travelers[d]--;
if(!travelers[d])
{
//if the last one heading this way , wake up the baboons waiting to finish.
while(blocked[reversedir]--)
block[reversedir]->V();
}
mutex->V();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.