Project 5 - Multithreaded Metro Simulation
May 6th May 10, 2010
In this project, you will develop a multi-threaded Java program that
can be used to simulate the Washington Metro. You will also write code
to display the state of a simulation based on a list of simulation
Apr 30: Fixes & clarifications
Apr 30: More fixes
- Changed submit.rb to use Dir.chdir("metro") to enter metro subdirectory.
- Notes on tests
- Many student submissions are failing because they're not ensuring Train threads stop executing at the end of the simulation. As a result the Train threads are running and spewing messages into the output for other tests, causing them to fail.
- The submit server evaluates JUnit tests in random order. So if you're not terminating your Train threads, any submit server test may fail (including display tests) if they're evaluated after the first simulation test with non-terminating threads.
- Public simulation tests are just placeholders locally and will always pass. They're only useful for generating output (log files in student_outputs) that you can check by hand. So passing them on your own computer doesn't mean you'll pass them on the submit server.
- Simulation tests on the submit server are actually performed by a Ruby script that is checking the correctness of your simulation output for the given simulation parameters. Unfortunately this means that the submit server will only be able to report whether the script succeeded or failed (i.e., return a junit.framework.AssertionFailedError if the Ruby verification script fails).
- Changed submit.rb to only submit .java files from metro directory
- Added call to Collections.sort(lines) at beginning of displayState()
- Updated CALFUZZER-README to support packages
Apr 29: Changes to support JUnit tests on submit server
- p5.zip has been updated and can now be imported into Eclipse
as project p5 (select Import->Existing Projects into Workspace->Select archive file)
- Public tests have been implemented as JUnit tests, and may
be invoked by selecting "Run As->JUnit Test".
- Output is piped to log files in the folder student_outputs (e.g., pub1-display.log, pub1-simulate.log)
- Select Refresh (F5) after running JUnit tests to make log files visible in Eclipse
- Display tests are fully implemented locally, and will verify that
your code is generating the correct output.
- Simulation tests are only partially implemented locally, and will just
generate simulation output. On the submit server the simulation
output will be verified for correctness.
- If you have already started on the project, you need to
make the following changes to your code. Look in the
updated Simulation.java in p5.zip for the new methods
- Put all your code in the package "metro". I.e., move all java
files into a folder "metro" and add the line "package metro;"
to the beginning of each java file.
- Add the method printParams() to Simulation.java. It prints the
simulation parameters read from the simulation input file.
Invoke printParams() before simulate() so that simulation output
is preceded by the simulation parameters.
This change allows you to feed the output of your simulation
to your display routine to see the state of your simulation.
- Ensure all train threads exit before simulate() returns.
A simple approach is for the main thread to set a flag
once all passengers reach their destinations. Train
threads should check the flag occasionally to see whether
they can stop running. Train threads do not have to
stop immediately after passengers reach their destination
(i.e., they can continue entering & exiting stations),
but they need to stop after some reasonable interval
(i.e., quickly enough so that the simulation will not
time out on the submit server). simulate() can then use
join() to ensure all train threads have completed before
- Add the method initSimulation() to Simulation.java. It resets
all the Hash data structures used by parseFile() so that
multiple simulations may be processed. Invoke initSimulation()
at the beginning of every call to parseFile().
- Similarly, make sure that your code reinitializes any static
data structures each time simulate() or display() is
invoked, since submit server tests will call Simulation.main()
multiple times from the same test case to try different inputs.
- Download the archive file
and extract its contents.
Along with files used to make direct submissions to the
submit server (submit.jar,
submit.rb), you will
find the following project files:
- Your Java program
- JUnit public tests
- Public test inputs
- Public test display outputs
- Possible public test simulation outputs
- Additional Files
Metro Simulation Rules
We will begin by describing how the metro simulation works.
In the simulation, there will be metro trains, each of which runs on a
particular metro line, and passengers traveling on the metro, each with
an itinerary. There are a number of rules governing
how trains and passengers may move between metro stations.
- Metro lines & stations
- The metro consists of a number of metro lines.
- Metro lines consist of a number of metro stations (stops).
- The same metro station may be on multiple metro lines.
- At the beginning of the simulation, trains enter the initial
stop on their line (e.g., Glenmont for the red line).
- Trains travel between the first and last station on each metro line, in order.
- Trains first move sequentially forward along the stations on the metro line. When trains reach the
station at the end of the metro line, they move sequentially backward along the line,
until they reach the beginning of the metro line. The process repeats indefinitely.
- Trains continue to move indefinitely back and forth between the first and last
station on the metro line. They may stop once all passengers reach their destinations.
- If there are no passengers in the entire simulation, then each train
must complete at least one round trip from the first to the last
station (and back) on its metro line.
- Multiple trains may travel on a metro line. Each train is assigned a number
unique to that metro line, beginning with 1 and increasing by 1 at a time.
- Trains are named by the name of the metro line, followed by its number, separated
by a space. For example, if the metro line "Red" has 3 trains, their names would be
"Red 1", "Red 2", and "Red 3".
- At most one train from each metro line may be at a station at a time
(think of it as metro stations having only one platform per metro line).
Thus, if there are multiple trains on a metro line, if two trains from
the same metro line happen to arrive at the same time, one will have to
wait until the station is clear.
- Two trains from the same metro
line may not be at the same station even they are traveling in opposite directions.
- If there are multiple trains waiting to enter a station, the order
they enter is unspecified.
- There may be multiple trains traveling between metro stations,
and trains may pass each other between stations (think of it as stations
being connected by multiple train tracks). Thus the order two trains
arrive at a station do not affect the order they arrive at the next station.
- In the simulation, passengers have a itinerary, a list
of stations they plan to visit. Passengers travel on trains from
station to station on their itinerary until they reach their final
- At the start of the simulation, passengers are located at the first
station on their itinerary.
- Passengers wait until a train arrives at their station
that will also stop at the next station on their itinerary.
At that point, they leave the station and board the train.
- Passengers may board any train traveling to the next
station on their itinerary. Passengers may board trains
traveling in either direction, regardless of which direction
requires fewer stops. Similarly, if the current and destination
stations are both on multiple metro lines, then any train on
either metro line may be boarded.
- When a train carrying a passenger arrives at the
next station on the passenger's itinerary, the passenger
disembarks (leaves the train and enters the station).
- Passengers continue traveling until they reach the
final station on their itinerary.
- It is possible that passengers at a station
might miss their train as it passes through. In that case,
the passengers remain in the station and waits for another
opportunity to board a train.
- Similarly, if passengers on a train misses their stop, the passengers
remain on the train and wait for another opportunity to exit at the
- Any line transfers will be explicit in the list of stations on
the itinerary. For example, there is no single train line that goes
from College Park to Vienna, so you can assume the itinerary of a
passenger interested in going between these two stations will include
a transfer point, e.g., going from College Park to L'Enfant Plaza and
then L'Enfant Plaza to Vienna.
- Any number of passengers may be aboard a train.
Metro Simulation Outputs
A metro simulation may be described by a number of simulation events
occurring in a particular order. There are four possible events,
which when output by a simulation are formatted as follows:
The simulator must output these simulation messages in the order they occur.
These messages (and their order of occurrence) may then be analyzed.
In this project you will write code to analyze them to display the
state of the simulation after each event. We will use the output
events to determine whether your simulation code is valid.
- Train line num entering station name
- Train line num leaving station name
- Passenger name boarding train line num at station name
- Passenger name leaving train line num at station name
Metro Simulation Parameters
Each metro simulation is performed for a specific set of simulation parameters.
These parameters are stored in a simulation file, and include the
In addition, the simulation file may contain an example output for a simulation
performed with this set of simulation parameters.
- Metro lines - name of metro line followed by a list of stations on metro line
- Metro trains - name of metro line followed by number of trains running on line
- Passengers - name of passenger followed by list of stations in passenger itinerary
The following is an example simulation file (pub3.in):
- Simulation output - possible simulation output to be examined
=== Lines ===
Red, Glenmont, Silver Spring, Union Station, Bethesda, Shady Grove
=== Trains ===
=== Passengers ===
Amy, Silver Spring, Bethesda
Ann, Glenmont, Bethesda
Art, Union Station, Silver Spring
Aaron, Bethesda, Glenmont
=== Output ===
Train Red 1 entering Glenmont
Ann boarding train Red 1 at Glenmont
Train Red 1 leaving Glenmont
Train Red 1 entering Silver Spring
Amy boarding train Red 1 at Silver Spring
Train Red 1 leaving Silver Spring
The simulation driver code given you
in Simulation.java will read in a simulation file
containing simulation parameters
for use by your code.
Simulation.java will also take a command line parameter
specifying whether the program should
perform a simulation or simply display or
verify the feasibility of the simulation output.
It can be invoked as
java Simulation [simulate|display] simFileName
So typing java Simulation simulate pub3.in would execute a
simulation using the simulation parameters in pub3.in (ignoring the
simulation output in pub3.in), while typing
java Simulation display pub3.in would display
the state of the metro simulation in pub3.in
an analysis of the simulation output in pub3.in
based on the simulations events listed in the simulation output.
For this project, you are required to implement two
functions: display and simulate. The two parts
may be implemented independently, though they may
also share data structures.
A number of skeleton implementations of various classes
have been provided for you. It is up to you whether you
use these classes. The only class that you are required
to use is the Simulation class.
For this project you may use Java synchronization constructs from
either Java 1.4 or 1.5. You may find the Calfuzzer tool
useful for detecting potential data races and deadlocks in your code.
However, Calfuzzer only works for Java 1.4 synchronization. Included
with the project files is a README
file explaining how to install, set up, and run Calfuzzer on your
project to find deadlocks or data races.
Part 1: Simulation Display
A multithreaded simulation can clearly have many different behaviors,
depending on the thread scheduler. One way to help determine whether
a simulation is proceeding correctly (i.e., avoiding data races)
is to model the state of the simulation by processing the simulation
outputs. The model can then be used to display the state of the simulation,
and/or determine its validity.
The first part of your project is to implement a model of the
simulation by reading in a sequence of simulation event messages and
outputting the state of the world in the simulation, as follows:
Your code should display the initial state of the simulation.
Then it should list each simulation event message in order it is read
in, followed by a display of the state of the simulation after
- Trains at each station
- Passengers at each station
- Passengers on board each train
For instance, for the simulation parameters in pub3.in
described above, your code should display the initial
state of the simulation as follows:
Silver Spring Amy
Union Station Art
Then, after processing the message
Amy boarding train Red 1 at Silver Spring in the simulation output,
your model should contain enough information to
display the following:
Amy boarding train Red 1 at Silver Spring
Silver Spring [Red 1 Amy Ann]
Union Station Art
A function displayState() is provided that will print out the
display information for each metro station in the format needed.
You will need to write code to pass it the necessary information
in the form of three Map data structures.
The function displayState() should output the trains and passengers
in sorted order. The amount of whitespace separating station/passenger/train
names will be ignored by the submit server tests.
Note that this part of the project need not be, and probably should
not be, multi-threaded. Just read in each event message and output
the appropriate state.
Part 2: Metro Simulation
For part 2 you will write a Java program
that actually performs a multithreaded simulation using the simulation
parameters supplied. Your simulation should be implemented as follows.
- Each train and passenger in the simulation should be represented
by its own thread. Thus, if you are simulating m trains
and n people, there should be m+n+1 threads in the
system (m trains threads, n threads for passengers,
and 1 for the main thread). In the sample code we have given,
the Train and Passenger classes both extend the Thread class.
- The initial state of the simulation should be as described in
the metro simulation rules (i.e., all passengers at the first
station in their itinerary, all trains poised to enter the
first metro station on their metro line).
- You must use synchronization
to avoid data races and ensure your simulation is valid.
- You must use conditions (e.g., the wait and notifyAll calls on
monitor objects used to avoid data races) to ensure your simulation
uses synchronization efficiently, and to avoid busy waiting.
- Each train should sleep for 0.01 seconds after entering
a station before exiting.
- TAs will look at your submitted code to check that you are using
synchronization correctly. They may also run Calfuzzer to find data
races and deadlocks permitted by your code.
- The list of stations in the itinerary
for each passenger does not tell you
what metro line they want to take. You'll need to compute that based on
the current station and next destination. If there
is more than one valid metro line, the passenger can board a
train from any valid line.
- The simulation ends when all passengers have arrived at their final
stops. To achieve this, in the main thread you'll probably do a
join on all the threads representing passengers. It is legal
if trains continue running for a while even after all passengers have
- If there are no passengers, each train must complete at least one
round trip from the first station to the last station (and back) on its
metro line before the simulation ends. Each train must finish
exiting the first station before its round trip is complete. This
code will probably need to be a special case in your main thread.
When your simulation is underway, it will print out event messages of
the format given above (in the Simulation Outputs section) as the
relevant simulation events occur.
For the output to make sense, you must do the following:
- Only print out a message while you are holding an appropriate
lock. In other words, you want each message output to be atomic,
and to avoid parts of one message being interleaved in the output
with parts of another message. Holding a lock may also be useful to
prevent racing on the order of output, e.g., printing that a train
has left the station before a passenger has disembarked from it,
even if those actions occur in the proper order in your code.
- Immediately after printing, and before you release the lock, call
System.out.flush() to flush standard output to the screen. This
ensures the output is printed immediately, and not buffered to be
You can submit your project in two ways:
Submit your Simulation.java file and any other .java files you used to
implement your simulation directly to the
You'll need to put all files in a .zip archive first.
On Windows you can select the files, then right click to
select the "Send to->Compressed (zipped) Folder" option
to create a .zip archive.
The .java files be at the top level when the archive is unzipped.
I.e., they must not be in any subdirectories (e.g., metro, src/metro).
Otherwise the submit server will not be able to find the files.
Once your files are in a single zip archive, submit the archive by
clicking on the submit link in the column "web submission".
Select your file using the "Browse" button,
then press the "Submit project!" button.
Submit directly by executing a Java program on a computer
with Java and network access. Use the submit.jar file
from the archive
To submit, go to the directory containing your project, then either
execute submit.rb or type the following command directly:
You will be asked to enter your class account and password, then
all files in the "metro" subdirectory will be
put in a jar file and submitted to the submit server.
Note that submit.rb has been modified for this project.
If your submission is successful you will see the message:
Successful submission # received for project 5
The Campus Senate has adopted a policy asking students to include the
following statement on each assignment in every course: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this assignment." Consequently your program is requested to
contain this pledge in a comment near the top.
Please carefully read the academic honesty section of the
course syllabus. Any evidence of impermissible cooperation on
projects, use of disallowed materials or resources, or unauthorized
use of computer accounts, will be submitted to the Student
Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabus---please review it at this time.