Project 5 - Multithreaded Metro Simulation
Due May 6th, 2009
In this project, you will develop a multi-threaded Ruby program that
simulates the Washington Metro. You will also write code to verify
the feasibility of simulation outputs.
- 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 Ruby program
- Public tests
- Inputs for verify tests
- Possible simulation outputs
- For public_simulate00.rb
- For public_simulate01.rb
- Ruby script to run public tests
Part 1: Metro Simulation
We will begin by describing the simulation; however, we suggest that
you actually start with the simulation verifier described below.
In the simulation, there will be metro trains, each of which runs on a
particular line, and people wanting to travel on the metro, each with
an initial and final destination. We will invoke your simulation with
the following code:
where input is a Ruby array describing the people's paths
through the system (see below). Here is how the simulation should
- The file metro.rb defines (a subset
of) the stops of the five metro lines (these are the only stops we
will use for this project). For example, here are the stops on the
$red_line = [
- During the simulation, exactly one train will run along each
line. At the begining of the simulation, trains are at the initial
stop on their line (e.g., Glenmont for the red line). They
move sequentially forward along the line, and then when they reach the
end, they move sequentially backward along the line, until they reach
the beginning, and then they continue indefinitely back and forth.
- Each train should be represented by its own thread. (Thus, since
there are five lines, your simulation will create at least five
- Each train waits for 0.1 second at its current stop, and then moves
to the next station.
- At most one train may be at a station at a time. Thus, at
stations where two lines intersect, if two trains happen to arrive at
the same time, one will wait (i.e., the thread representing it will
block) until the station is clear.
- Trains can carry an unlimited number of passengers.
- The file metro.rb includes a sample array input describing the
actions of people taking the metro. In this array, each entry
describes a person. The entry is itself an array, listing the
person's name followed by
stations the person wants to visit, in order. For example, here is
a sample input:
$sample_input = [
["Alice", "College Park", "Gallery Place"],
["Charlie", "Union Station", "Fort Totten", "College Park"]
This file lists the intended paths of two people. Alice
starts at College Park and wants to take the train to Gallery Place.
Charlie starts at Union Station, takes the train to Fort
Totten, and then takes the train to College Park.
- Each person in the simulation should also be represented by their
own thread. Thus, if you are simulating n people, there should be
5+n+1 threads in the system (5 for the trains, n for the people,
1 for the main thread).
- At the start of the simulation, each person begins at the initial
station on their path. They wait (i.e., the thread representing them
blocks) until the right train arrives. At that point, they board the train.
When the train arrives at their next destination, they disembark and
wait for the train they want to arrive, or exit (i.e., their thread
exits) if they have arrived at their final destination.
- Notice that the list of stations for each person does not tell you
what line they want to take. You'll need to compute that based on
the starting and ending destination for each segment. Sometimes there
may be more than one valid line, in which case the person can take
- It is possible, due to thread scheduling, that a person might miss
their train or might miss their stop. In that
case, they remain either in the station, or on the train,
respectively, until they can get off at their stop.
- You may assume that all passenger travel plans are valid.
For example, there is no direct line from College Park to
Vienna, so you can assume no person will try to go from one to the
other without explicitly listing an intermediate destination. You can
assume all the destinations listed for a passenger are valid stations.
- The simulation ends when all people have arrived at their final
stops. To achieve this, in the main thread you'll probably do a
join on all the threads representing the people. Notice
that it is legal if trains continue running for a while even after all
passengers have arrived.
No passengers should be able to board a train after it has left
the station. For example, a train thread should not print out
Train A leaving X before passenger threads say,
M boarding train A at X.
- You should set Thread.abort_on_exception = true in your
code, to avoid hiding errors in threads.
- There is no requirement on how many monitors you use for this
project---just that you use proper synchronization
In order to see what's going on during your simulation, your program
must print out various lines of text as actions occur. Here are the
messages you must print:
There should be no other output from the simulation
- When a train enters a station, you should print "Train c
entering s" where c is the train color, one of
red, green, yellow, orange, or
blue, and s is the station name, e.g., College Park.
Trains should also print this message when they
materialize at the initial stations at the beginning of the simulation.
- When a train leaves a station, you should print "Train c leaving
s", similarly to above
- When a person boards a train, you should print "p boarding train
c at s", where p is the person's name, c is the
train color, and s is the station name. For example,
"Alice boarding train green at College Park".
- When a person departs a train, you should print "p leaving train
c at s"
- Do not include quotes in the output strings; they're shown above
just to be clear what is in the string and what is excluded.
A sample output could then begin with something like the following:
Train green entering Greenbelt
Train blue entering Largo Town Center
Train orange entering New Carrolton
Train blue leaving Largo Town Center
Train yellow entering Fort Totten
Train red entering Glenmont
Train orange leaving New Carrolton
In order to make sure the output makes sense, you
must do the following:
Following the two rules above should ensure that if you build the simulation
correctly, your simulation output will be valid. Otherwise, you might
get strange interleavings of output messages that look incorrect even
if your simulation code is actually correct.
- Only print out the above statements while you are still holding a
- Immediately after printing, and before you release the lock, call
$stdout.flush to flush standard output.
You must use mutual exclusion to ensure your simulation is valid. We
will manually look at your submitted code to check that you've used
Part 2: Simulation Verifier
The simulation above can clearly have many different behaviors,
depending on the scheduler. However, there are certain restrictions
on the simulation output, e.g., people must get on trains when those
trains are at the station the person is at.
For this part of the project, you will write a Ruby program
that takes traces gathered from a simulation (as from part 2) and
checks whether they are valid. We suggest you do this part first,
since it might help you debug your simulation.
We will invoke your verifier for this part as
result = verify(input, output)
Here input is the description of the people in the
simulation. output is the output of the simulation, which is
an array, each line of which contains one line from the simulation
output, in order. There are no newlines at the end of each line (we
will remove them with chomp). Your verify function
should return true (or a non-false, non-nil value) if the
output is valid for the input, and false or
In particular, you should be sure to check for the following:
- Check that all the output messages are formatted exactly as
- Ensure that trains start at their initial station, and then move
forward and backward along the stations on their metro line
- Make sure trains enter a station before they leave it
- Make sure two trains are not at the same station at the same time
- Make sure that each person follows their path as given in
- Make sure people only board and leave a train at a station after
that train has entered the station, but before it leaves the station
- Make sure all people reach their destinations in the
- Make sure no extra people move around on the trains
You can submit your project in two ways:
Submit your file metro.rb directly to the
by clicking on the submit link in the column "web submission".
Next, use the submit dialog to submit your metro.rb file.
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:
java -jar submit.jar
You will be asked to enter your class account and password, then
all files in the directory (and its subdirectories) will be
put in a jar file and submitted to the submit server.
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.