Woolies
Copyright RIT 2006
$Id: writeup.xml,v 1.19 2009/02/11 14:34:55 vcss232 Exp $
In this lab you will learn techniques for controlling the synchronization between running multiple threads.
Woolies
You are to work on this lab in teams of size 2. Students who do not abide by this rule will not get full points for in-class participation.
Review your class notes on thread synchronization.
Read through the Java tutorial's section on thread synchronization (http://java.sun.com/books/tutorial/essential/threads/) .
Fetch this lab's jar file (http://www.cs.rit.edu/~vcss232/pub/lab09/Binaries/lab9.jar) .
In the land of the Woolies, the towns of Merctran and Sicstine are on opposite sides of the Zyxnine River. There is a single bridge that connects these two towns. Any woolie that wishes to go to the town on the other side of the river must cross this bridge.
Bridge
In this activity you will create a class, named Bridge, that simulates a woolie crossing the bridge. The bridge can carry more than one woolie at a time, so the Woolie class is written so that each simulated woolie runs in a separate thread, i.e., it extends the Thread class. The following paragraph explains how it works. It is not one of the classes you have to write, just understand.
Every woolie has a name, and like most people, woolies walk at different speeds. The constructor of the Woolie class will be given: the woolie's name, the number of seconds it takes the woolie to cross the bridge, and the name of the city (Merctan or Sicstine) that the woolie is going to. The Woolie.run() method of the Woolie class simulates the Woolie crossing the bridge. There is also a bridge troll (./Auxiliary/totwb.mp3) , represented by the Troll class. The woolie tries to start crossing the bridge as soon as the Woolie.run() method begins execution. The first thing the woolie must do is ask the troll permission to cross the bridge. (In this version the troll always grants permission immediately; it will play a more important role in the next activity.)Then the Woolie.run() method enters a loop, that executes once for every second the woolie is on the bridge. The body of the loop invokes Thread.sleep(long) to delay for one second (one second is equivalent to 1000 milliseconds). The Woolie.run() method also generates some output, the specifications for which are contained in the Javadoc description of Woolie class. Finally, the woolie informs the troll that it is leaving the bridge. See the Troll class javadoc for details.
The bridge between Merctran and Sicstine gets a lot of foot traffic because many woolies need to go back and forth between the two cities on a regular basis. The bridge itself is very old and the municipal engineers have noticed many cracks developing in the structural members of the bridge. The state of the bridge is so bad that the engineers feel that they need to limit the bridge to carry only three woolies at a time.
Collapse
The woolies are a rather impatient and unruly bunch of people. Even though they know that the bridge might collapse under the weight of more than three woolies, plunging them into the Zyxnine River, they will not wait until it is safe to cross. The government has employed the mean-spirited troll to police the bridge and limit passage to a maximum of three woolies at a time.
In this activity you will write the class that simulates the bridge. The bridge should not allow more than three woolies on at any point in time. Note that even though each Woolie needs to get permission from the bridge troll before it can cross the bridge, the Troll class in this activity does not make a decision. It simply passes the request on to the Bridge class. It also passes along notification of woolies leaving the bridge so that the Bridge class can maintain its count.
The Bridge class contains two methods: Bridge.enter() that the Troll invokes to indicate that a woolie wishes to cross the bridge, and Bridge.leave() that is invoked when the woolie has finished crossing the bridge. The Bridge.enter() method will contain the code that ensures that only up to three Woolies are on the bridge at a time. The Bridge.leave() method contains the code that deals with the fact that a Woolie is off the bridge The complete specifications for the Bridge class are contained in the Javadoc pages. Remember that the Java synchronization mechanisms can be used to do most of the tricks of the Bridge class.
In this activity you are to write the Bridge class. The others are provided in the jar file.
Test your Bridge class by writing a test program that creates multiple Woolies with different names, crossing times and destinations. Be sure to verify the following things:
You can try creating a whole bunch of woolies
simultaneously, or staggering their execution by separating
their start() calls with calls to
Thread.sleep(int).
Once you are convinced everything is working correctly, submit your code using the following command:
|
Troll
The Woolies who were using the bridge were getting upset because the bridge troll did not keep track of the order in which the Woolies arrived at the bridge. When the time came to allow another Woolie to cross the bridge, the bridge troll was selecting a Woolie at random, and granting them permission to cross the bridge. The Woolies made it clear to their government representatives, that the troll should be instructed to let the Woolies cross in the order in which they arrived at the bridge. The engineers appointed one of the Woolie computer specialists to teach the bridge troll about queues.
NOTE: The javadocs for Bridge and Troll are DIFFERENT from the previous activity. They describe the changing interface needed for proper behavior. Be certain to copy and revise your previous activity's classes accordingly. For instance, the Woolie class is changed so that it passes an instance of itself when calling the Troll's enterBridgePlease() method.
In this activity you will change the Bridge and Troll classes so that the bridge troll ensures that the Woolies cross the bridge in the order in which they arrive. Now the bridge troll will need to maintain a queue of woolies waiting to cross the bridge. This special queue called WoolieQueue is provided. Since each Woolie executes in a separate thread of execution, the troll should store Woolies (Threads) in the queue. The interface of the Woolie class remains unchanged. Woolies already knew they had to tell the troll of their comings and goings. It's just that the troll now maintains some records about who's getting on! Of course, since the troll is mean-spirited, and is being asked to do more work, and since the Woolies are a wild bunch, the troll makes sure to scowl at each woolie who enters his queue, otherwise the Woolies might get out of hand (see the Troll.enterBridgePlease method for specifics on the scowl message).
When there is space on the bridge, Troll.enterBridgePlease returns to the Woolie caller. In that way the bridge troll essentially notifies the next woolie who is waiting to cross the bridge. You must ensure that only the Woolie who is next actually starts crossing the bridge; the other Woolies must continue waiting. This means that the Troll manages the queue and queries the Bridge as to the number of woolies that are currently on it. Since the Bridge object is only called by the Troll object, the former class no longer needs synchronized methods, and that latter one now does. Remember it is possible that multiple Woolies leave the bridge before one of the waiting ones starts crossing. Also, be sure that you do not allow a new Woolie to cross the bridge in front of those waiting to cross, i.e., always queue requests. Look at the javadoc for the Bridge and Troll classes to see the revised methods and the new ones that have been added to help with the synchronization.
You may want to write more varied tests for this activity. Keep in mind that the order you start threads is not necessarily the order that they run. Insert short sleeps between each start() invocation in order to minimize the chances that the woolies try to get on the bridge in an order other than the one you intended.
Once you have the code compiled, run it and look at the results. Once you are convinced everything is working correctly, submit your code using the following command:
|
Grade Breakdown: