Baboons A tribe of baboons live on the west side of a canyon and gather food on the east side. The only way to cross the canyon is on a vine that is securely attached on both sides. Any number of baboons may be on the vine at any one time, but they must all be moving in the same direction. Fast eastbound baboons may climb over slower eastbound baboons, but a baboon that wishes to travel westbound must wait until no more eastbound baboons are on the vine. If baboons on the vine are westbound, then eastbound baboons must wait. Model a baboon as a process that continually gathers food and brings it to its tree, where access to the vine is controlled by semaphores. Name all resources and variables, explicitly state whether they are shared or local and note their initial values. This is a variation on the concurrent readers and concurrent writers discussed in class. You may use one and only one counter to keep track of baboons on the vine.

Baboons SOLUTION:

Semaphores: VineExcl=1; WestCtl=1; EastCtl=1;

Variables: OnVine=0; Direction=East;

loop

/* Go east */

P(EastCtl);

if Direction==West {

P(VineExcl);

/* This is an Atomic Test n Set */

Direction=East;

}

OnVine++;

V(EastCtl);

CrossCanyon();

/* Get off Vine */

P(EastCtl);

OnVine--;

if OnVine==0 V(VineExcl);

V(EastCtl);

/* Go west */

P(WestCtl);

if Direction==East {

P(VineExcl);

Direction=West;

}

OnVine++;

V(WestCtl);

CrossCanyon();

/* Get off Vine */

P(WestCtl);

OnVine--;

if OnVine==0 V(VineExcl);

V(WestCtl);

endloop