Date: Mon, 11 Nov 1996 17:25:18 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Tue, 27 Feb 1996 15:51:55 GMT Content-length: 3318 CS 537 - Quiz #3
UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
CS 537
Spring 1996
Bart Miller
Quiz #3
Wednesday, February 21

Using Monitors to Save Your Life

You are to write the code to provide the synchronization to control access to a couple of pedestrian bridges. The bridges are used to cross a dangerous, shark-infested river. The picture below illustrates the problem.

Bridges

You have provided to you (already written) a procedure called CrossBridge(bridgenum). You don't know how long this takes to execute. This procedure causes the person process to cross bridge bridgenum (which can have valid values of 1 or 2). A person starting on the east shore will end up on the west shore. A person starting on the west shore will end up on the east shore. This procedure returns when the action is completed.

Use monitors as the synchronization mechanism for your solution. Use the syntax that was presented in lecture: monitors are simply C++ classes with the extra "monitor" keyword.

Each person is a process and these processes arrive randomly. You will write a procedure called Person() that will be called by people wanting to cross the river. You will write any additional procedures that you need.

Your solution must obey the following rules:

  1. Each bridge is strong enough to hold only 1 person at a time. Additional people will break the bridge and they all will fall in the river and be eaten.
  2. If there is more than one person wanting to cross the river, both bridges should be in use at the same time.
  3. People should get to use the bridge in approximately the same order in which they arrived.
  4. Initially, both bridges are unoccupied.

Hint: the Person() procedure is probably not in the monitor. You might consider having this procedure call procedures in a "BridgeControl" monitor; this is similar to how we did the readers/writers problem.

BridgeControl river;

void Person()
{
    int b = river.GetBridge();
    CrossBridge(b);
    river.Done(b);
}
monitor class BridgeControl {

public:
    BridgeControl();
    int GetBridge();
    void Done(int);

private:
    int busy[2];
    cond waitList;
};
BridgeControl::BridgeControl() {
    busy[0] = busy[1] = 0;
}
int
BridgeControl::GetBridge();
{
    while (1) {         /* Note: this is NOT busy waiting. */
        for (int i = 0; i < 2; i++) {
            if (!busy[i]) {
                busy[i] = 1;
                return (i+1);
            }
        }
        wait(waitList);
    }
}
void BridgeControl::Done(int bridge)
{
        busy[bridge-1] = 0;
        wakeup(waitList);
}


Last modified: Wed Feb 21 10:59:47 CST 1996 by bart