In this project, you will use threads, thread synchronization, and thread communication to write a simulation of cars, ships, and a draw bridged (a bridge that lifts so that boats can pass under it). Each actor in the simulation is implemented with a thread, and the threads interact via synchronization and signalling. In three sections below, we describe the Ship class, which you will be given, and the basics of the Car and Bridge classes, which you must implement. We also included some helper classes, AbstractEntity, EventPrinter and Analyzer . We will also describe the basic functionality of the helper classes.
Please note: how you use synchronization, immutability, signalling (e.g. wait, notifyAll, etc.) to implement these classes is entirely up to you. None of the methods on the signatures given will have synchronized specified on them. It is up to you to determine which ones should be synchronized, if any. The interaction between the Car and Bridge classes is also up to you, within the limits defined below. That is, you can add data and methods as you wish to implement the simulation.
You are also free to add extra helper classes if you want to. However, you must not modify the Ship class or any of the helpers (AbstractEntity, EventPrinter and Analyzer ). We will test your project with the original version of these classes.
Writing multi-threaded programs is hard. Testing becomes much harder because the behavior of the program can change from execution to execution. Finding bugs in multi-threaded programs is, accordingly, an active area for research, and a number of useful testing tools have been developed. We strongly recommend that you use two of these tools to test your project before submitting it:
Both of these tools can help you identify potential bugs in your project. By their nature they are both somewhat conservative. Things that they identify as problems may actually be OK. But, in general, if there is something that these tools don't like in your code, it is likely to be at least a poor design choice. Also, we will be using these tools in testing your projects to identify possible bugs so you are well advised to do the same.
Here is a description of the assumptions you will be working with. You need to pay close attention to the synchronization rules described in this section. Some issues will be explained further when we give details of the skeleton code for the project. There are three main types of actors in this scenario, each running in its own thread: cars, ships, and a bridge. The system contains only one bridge, which will be the main synchronization point of all the actors.
Our scenario requires managing traffic under and across a draw bridge. Our bridge has some particular rules, which we will now explain. As you might expect, ships cross under the bridge when it is raised, while cars cross over it when it is lowered. The bridge has a number of traffic lanes cars can cross on. In our simulation, there can be only one car on a bridge lane at any time. In order to avoid long lines at the bridge, the bridge builders have provided a parking lot for each such lane. When a car arrives at the bridge (knowing which lane it wants to cross on), it enters the parking lot for that lane. Once a lane is safe to cross on---which can only happen when the lane is empty and the bridge is down---the bridge operators signal the cars in the parking lot for that lane that one of them should start crossing. It is here that the engineers have not thought this through, since there is not preset order. Whichever driver reacts quickly and manages to enter the bridge is allowed to cross, while the others have to wait for their turn again. The waterway under the bridge is not very wide, which means there is little room for manoeuvring. Therefore, only one ship can cross under the bridge at any time. While ships are crossing the bridge---meaning the bridge is lifted---there can be no cars crossing over. Also, since this is a very busy waterway, ships have priority, which means that whenever a ship arrives at the bridge, the bridge operators will wait for any cars on the bridge to finish crossing, then lift the bridge and allow the ship(s) to cross. If there are multiple ships waiting at the bridge simultaneously, then it is up to their navigators to decide which goes first (meaning they don't necessarily have to cross in the same order they arrived).
These are the scheduling rules that your implementation must follow. You should also look at the implementation related rules in section 4.
We will now describe the details of the skeleton implementations of the three actors and the helper classes. Also read the hints section. It contains important information that may help you solve the problem if you get stuck.
All three actors are derived from a base abstract class, AbstractEntity, which encapsulates the common functionality. All actors will be assigned a name and a unique ID upon creation. You should not modify AbstractEntity:
public abstract class AbstractEntity extends Thread {
protected int ID;
protected String name;
public AbstractEntity(String name);
public int getID();
public String getEntityName();
// Internally used
private static int lastID = 0;
public static synchronized int generateID();
}
The Ship class has the following form:
public class Ship extends AbstractEntity {
protected int timeCross;
protected int numCrossings;
protected int busyTime;
protected Bridge bridge;
private int index = 0;
public Ship(String name, int timeCross, int numCrossings,
int busyTime, Bridge bridge);
public int getTimeCross();
public int getNumCrossings();
public int getBusyTime();
public void run();
}
A ship receives the following at initialization:
A ship is an autonomous actor (it runs in its own thread). We have provided you with the implementation of this class. You may use the run method as a t emplate to implement the Car's run method:
public void run() {
while(true) {
// Check if we're done
if(index == numCrossings) break;
// we defer printing any mesages to the Bridge, since
// messages should be synchronized properly for grading
bridge.crossUnderBridge(this);
// time to get busy
index++;
try {
Thread.sleep(busyTime);
} catch(InterruptedException e) {}
}
// for helping purposes
System.out.println("Ship " + name + " done!");
}
You may notice that the implementation is very simple: the ship simply calls the Bridge's crossUnderBridge method, which should take care of any synchronization (for instance, if the ship has to wait because the bridge is down or because another ship is crossing). Once it has finished crossing under the bridge, the crossUnderBridge method returns and the ship can continue its schedule.
The Car class is similar:
public class Car extends AbstractEntity {
protected int speed;
protected int numCrossings;
protected int busyTime;
protected Bridge bridge;
private int index = 0;
private int lane = 0;
public Car(String name, int speed, int numCrossings,
int busyTime, int lane, Bridge bridge);
public int getSpeed();
public int getNumCrossings();
public int getBusyTime();
public void run();
}
Unlike the Ship, the Car is given
a speed (in miles per second). This information
should be used by the bridge thread to
determine the time it should take a certain
car to cross it. The car is also given
a number of crossing attempts, a "busy
time" (which
has the same meaning as for the Ship)
and a preferred lane (the lane parameter).
As stated before, a car should always
attempt to cross the bridge on its preferred
lane. You need to complete the run method
for the Car class.
The Bridge is the most complext actor:
public class Bridge extends AbstractEntity {
protected int length;
protected int numLanes;
protected boolean lifted = false;
public Bridge(String name, int length, int numLanes);
public void crossOverBridge(Car car, int lane) throws IllegalArgumentException;
public void crossUnderBridge(Ship ship);
public void run();
public int getLength();
public int getNumLanes();
public boolean isLifted();
}
The Bridge has a length (in miles) and a number of lanes. There are three methods that you will need to implement for this class: crossOverBridge , crossUnderBridge and run. We will describe the purpose of these methods in Section 4.
The EventPrinter class is a component that will help produce traces. These traces are used in grading, as explained in Section 4. They can also give you important clues to what is happening with your code. EventPrinter produces output and also logs all messages into an internal format that is later passed to the Analyzer class. The Analyzer checks that your implementation conforms to the scheduling rules described in this assignment. Here is a set of methods from EventPrinter that you will need to use in your code:
Most of these methods take an AbstractEntity that produced them as a parameter. printCarArrive and printCarStart also require the lane number on which the car arrives at or starts crossing the bridge. The following section will contain sample code for these methods.
The Analyzer class is similar to the script that we will use in grading. However, we do not guarantee that this version will be used in grading and that we will not use other testing methods in addition to the Analyzer.
Your assignment has two parts:
The first part should be straightforward, especially with the Ship run method as a template; it should not take more than a few lines. You need to make sure that a car always attempts to cross on its preferred lane and that is sleeps for the specified "busy time".
The second part involves a number of things:
The crossOverBridge and crossUnderBridge methods are called by cars and ships respectively whenever they attempt crossing over/under the bridge. The crossOverBridge method for instance should only return when the calling Car thread has finished crossing, and the crossUnderBridge should have similar semantics for Ships. Since this method may be called by multiple Car threads at once, inside the method you should make sure that you conform to the rules expressed in Section 2 (for instance, you might want to make sure that cars are not crossing the bridge while it is lifted and there are no two cars crossing the bridge on the same lane at the same time). You also need to call the appropriate printXXX methods from EventPrinter. Please note that there are many ways to implement this assignment. You may choose to implement some rules in the crossXXX methods, and some others in the run method of the Bridge class. You should observe the following:
Here are a few sample calls to EventPrinter's printXXX methods:
public void crossOverBridge(Car car, int lane) {
// Your code
EventPrinter.out.printCarArrive(car,lane);
// Some other code
EventPrinter.out.printCarStart(car,lane);
// Some other code
EventPrinter.out.printCarDone(car);
}
Since you have complete freedom over how the Car and Bridge classes interact, we can only test them together (i.e., we cannot test your Car with our Bridge, etc.). So you will not get any points for completing just the Car class. Your assignment will be graded by running it on a total of 10 simulated scenarios with varying numbers of ships, cars, lanes, etc.
You should only upload the Car.java and Bridge.java files, along with any helper classes you may develop. Please make sure that your code compiles on the Linuxlab machines.
We believe we have provided you with a correct implementation of the Analyzer class. However, if you do spot a bug in our implementation, we will give you a bonus of 5 points be bug for a maximum of 15. NOTE: Tests that you think are "missing" from the Analyzer will not be considered. We already stated that the implementation you are given should cover most of the possible cases. We're looking for cases where the Analyzer rejects correct traces or accepts incorrect ones.
In order to test your project, we've provided you with a Simulation class that creates and starts a Bridge and some Car and Ship threads. As the simulation runs, the threads will interact, and the calls to EventPrinter's printXXX methods will display an execution trace. When all the Car and Ship threads have terminated, the simulation ends. Note that you will need to implement the Car and Bridge classes first for this simulation to work.
To test your project, you should make a variety of different simulations by modifying our Simulation class. The main method of the Simulation class also performs log analysis and informs you of any problems there may be with your trace.
We have also provided a trace of the execution of this simulation with our implementation. Not that, by the non-deterministic nature of multi-threaded programming, you should not expect your traces from the simulation to be identical to these, but only that your traces be correct given the description of the project.
Here are a few hints that may help you solve this assignment:
Thread A
synchronized(lockA) {
synchronized(lockB) {
.... operations ...
}
}
Thread B
synchronized(lockB) {
synchronized(lockA) {
.... operations ...
}
}
is a potential deadlock situation. If you need to acquire multiple locks but avoid deadlocks, you can think of an ordering of these locks (such as lockA < lockB), and you should make sure that your code always acquires lockA before acquiring lockB. Avoiding deadlocks should be a priority, because it is very likely that an implementation that deadlocks will fail all our tests.
Consumersynchronized(available) { try { available.wait(); } catch(InterruptedException e) {} ....consume element.... System.out.println("Consumed!"); } Producer .....produce element.... synchronized(available) { available.notifyAll(); } System.out.println("Produced!");
may result in the following output:
Consumed!
Produced!
Use the output provided by the Analyzer to identify where your output maybe placed incorrectly.