Programming Assignment 2: Monitors                                               Due October 12, 1999

---

This assignment is to be done in teams of two. As part of your documentation, specify team members (name, ID) and a brief description of each member's responsibilities (or how you divided up the work). Also, please specify on the cover page of your hard copy your names and which one of you had submitted the electronic version.

Introduction

Specification

• void Bridges(int bridgeCount, int capacity): Calling this constructor creates an instance of the Bridges class with bridgeCount bridges across the river, each able to carry at most capacity persons crossing at one time. You will create exactly one instance of Bridges, probably in your main() method.
• void runSimulation(int personCount): You will also call this method from your main() method. It runs a simulation by creating threads representing people trying to cross the river. New people are created at random intervals on random sides of the river. When all the people have been created, the simulation waits for them all to finish (i.e., it waits for the threads to terminate) before printing (on System.out) some statistics about throughput, bridge occupancy, etc. and returning from the method runSimulation().
• void cross(int bridgeNumber, int direction): This method causes a person thread to cross bridge bridgeNumber (a number in the range 0...bridgeCount-1). You don't know how long this takes to execute. You will call it from Person.run() (described later). The direction parameter is Bridges.GOWEST for a person starting on the east shore traveling to the west shore, and Bridges.GOEAST for a person starting on the west shore traveling to the east shore. This method returns when the action is completed. Until it returns, the thread that called it is blocked. A thread can call this method while another is blocked in it, subject to the rules below.

Each person is a thread running a Person class, which you must write, that implements the following interface (see also the complete specification.)

• public Person(Bridges river, int direction): This constructor is used by the Bridges object to create a new person. The river argument is a pointer to the Bridges object; it is included so that the person can call river.cross(bridge, direction) at the appropriate time.
• public void run(): Person implements the Runnable interface. The run method should print a startup message, wait until it is safe to cross the river, call river.cross(bridge, direction), print another message, and return.

Use a ``monitor'' (a Java class with synchronized methods) as the synchronization mechanism for your solution. Create an instance of the monitor in the main() method and save it as a static field of the ``main'' class so that it can be easily referenced from Person.run().

Your solution must obey the following rules:

1. Each bridge is strong enough to hold only capacity persons at a time, where capacity is a parameter to the Bridges constructor. Additional people will break the bridge and they all will fall in the river and drown.
2. Bridges are one-way. If two people try to cross the same bridge in opposite directions at the same time, they will fall into the river.
3. If there is more than one person wanting to cross the river, as many bridges as possible should be in use at the same time.
4. People shouldn't wait any longer than necessary to cross the river.
5. Initially, all the bridges are unoccupied.

You may copy these examples of Person.java and Proj2.java and try them out to see how things should work.

You must prepare two solutions to this problem. In the first solution, each person crosses the first available bridge. In the second solution, there is a separate waiting line for each bridge. A newly arriving person gets in the shortest waiting line and waits for a chance to cross that bridge. (The length of the waiting line is the number of people on the same side of the river waiting to cross that particular bridge.) Which solution gives better performance?

Compiling and Running

    cp /home/fac1/matta/cs552-pa2/*.class .

    javac Project2.java
    time java Project2

More details on tests you should run will be posted before the due date.

Hints

You should not call Bridges.cross() from a synchronized method of CrossingGuard. If you do so, everything may seem to work fine, but you will get terrible performance. When a thread gets blocked in Bridges.cross(), it will still be holding the monitor lock for CrossingGuard, preventing any other thread from entering any method of CrossingGuard. The result will be that only one person will cross the river at a time, regardless of how many bridges there are and regardless how many people each bridge can hold. Instead, you should have two synchronized methods, one that blocks the caller until it is safe to call Bridges.cross() and the other to be called after Bridges.cross() returns.

For the second solution (where you have a separate waiting line for each bridge), you could still get by with one monitor. Each time a person finished crossing a bridge, he would call notifyAll, waking up all the waiting people. Each one would recheck whether it would be safe for him to cross, and go back to sleep otherwise. Such a solution would not be very efficient. It would be better if you used a separate instance of (another) monitor for each waiting line. Then you would only need to wake up people when there was a good chance they could cross. You would see the difference in the amount of CPU time printed at the end of your job.

See guidelines on What to Submit.