Project 5 - Multithreaded Metro Simulation

Introduction

In this project, you will develop a multi-threaded Ruby program that can be used to simulate the Washington Metro. You will also write code to process simulation output to display the state of the simulation and (optionally) verify its feasibility.

Getting Started

• Download the archive file p5.zip and extract its contents.

Along with files used to make direct submissions to the submit server (submit.jar, .submit , submit.rb), you will find the following project files:

• Your Ruby program
  • sim.rb - driver for simulator
  • metro.rb - simulator (make all your edits here)
  • displayExample.rb - example showing how to use displayState()
• Public tests
  • pub1.in
  • pub2.in
  • pub3.in
  • pub4.in
  • pub5.in
  • pub6.in
  • pub7.in
  • pub8.in
  • pub9.in
• Public test display outputs
  • pub1-display.out
  • pub2-display.out
  • pub3-display.out
  • pub4-display.out
• Possible public test simulation outputs
  • pub1-simulate1.out
  • pub2-simulate1.out
  • pub2-simulate2.out
  • pub2-simulate3.out
  • pub3-simulate1.out
  • pub4-simulate1.out
  • pub4-simulate2.out
  • pub4-simulate3.out
  • pub5-simulate1.out
  • pub5-simulate2.out
  • pub5-simulate3.out
  • pub6-simulate1.out
  • pub6-simulate2.out
  • pub6-simulate3.out
• Public test verify outputs (optional)
  • pub6-verify.out
  • pub7-verify.out
  • pub8-verify.out
  • pub9-verify.out
• Ruby script to run public tests
  • goTest.rb

Project Description

Metro Simulation Rules

• 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.

• Trains
  • 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.

• Passengers
  • 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 destination.

  • 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 desired station.

  • Any line transfers will be explicit in the list of stations on the itinerary. For example, if there is no direct connection from College Park to Vienna, so you can assume passenger itineraries will not try to go directly from one station to the other without using an intermediate station as a transfer point.
  • An unlimited number of passengers may be aboard a train.

Metro Simulation Outputs

• 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

• 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

• Simulation output - possible simulation output to be examined

=== Lines ===
Red, Glenmont, Silver Spring, Union Station, Bethesda, Shady Grove
=== Trains ===
Red=1
=== 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
...

Simulation Driver

lines = {
  "Red" => ["Glenmont", "Silver Spring", "Union Station", "Bethesda", "Shady Grove"]
}
numTrains = {
  "Red" => 1
}
passengers = {
  "Amy" => ["Silver Spring", "Bethesda"],
  "Ann" => ["Glenmont", "Bethesda"],
  "Art" => ["Union Station", "Silver Spring"],
  "Aaron" => ["Bethesda", "Glenmont"]
}
simOut = [
  "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 hash for metro lines contains the metro line "Red" which begins at the station Glenmont and ends at the station Shady Grove.

• The hash for the number of trains contains an int value for each metro line, specifying the number of trains on that line.

• The hash for passengers contains a list of stations names (forming the itinerary) for each passenger. The first station is the passenger starting point, the last station is the final passenger destination.

• Any simulation output will be put into an array of strings, with each string corresponding to one simulation event message.

     ruby sim.rb [simulate|display|verify] simFileName

Note sim.rb outputs simulation parameters before simulation messages, so that its output (if saved in a file) may be passed directly to the simulation display/verify routines.

Project Implementation

Part 1: Simulation Display

The first part of your project is to implement a model of the simulation (by processing simulation event messages) sufficiently detailed to display the following

• 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:

Red
                   Glenmont       Ann            
              Silver Spring       Amy            
              Union Station       Art            
                   Bethesda     Aaron            
                Shady Grove   

Amy boarding train Red 1 at Silver Spring
Red
                   Glenmont                      
              Silver Spring            [Red 1 Amy Ann]
              Union Station       Art            
                   Bethesda     Aaron            
                Shady Grove      

sim.rb and submit server tests will invoke your verifier for this part of the project as

     display(lines,passengers,simOut)

A function displayState(lines,stations,trains) is provided for actually printing out the state of the simulation. If you wish to use it you will simply need to collect enough information in your model to provide two hashes: stations, trains. These hashes should contain information on trains/passengers at each station, and passengers on each train as follows:

• stations[station name] => hash for metro line
• stations[station name][line name] => hash for trains at station (for line)
• stations[station name][line name][train num] where train num is "1", "2", etc...
• stations[station name]["passenger"] => hash for passengers at station
• stations[station name]["passenger"][passenger name] exists when passenger is at the station
• trains[train name] => hash for passengers on train
• trains[train name][passenger name] exists when passenger is on the train

Part 2: Metro Simulation

• 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).

• 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 (i.e., Ruby monitors) to avoid data races and ensure your simulation is valid. You should use the monitor associated with each metro line to prevent all data races for that metro line. So a simulation with n metro lines could have up to n train and/or passenger threads executing concurrently.

• You must use conditional variables to ensure your simulation uses synchronization efficiently. Use at least two condition variables per monitor, one for trains and one for passengers. Trains should wake up passengers when entering stations, and wake up trains when exiting stations.

• 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.

• Notice that 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 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.

• If there are no passengers, each train must complete at least one round trip from the first to the last station (and back) on its metro line before the simulation ends.

• You should set Thread.abort_on_exception = true in your code, to avoid hiding errors in threads.

• In order to see what's going on during your simulation, your program must print out various lines of text as simulation events occur. These lines of text are described in the Metro Simulation Outputs section above. For the output makes sense, you must do the following:
  • Only print out a message while you are holding a lock.
  • Immediately after printing, and before you release the lock, call $stdout.flush to flush standard output to the screen.

  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.

     simulate(lines,numTrains,passengers,simMonitor)

Optional: Simulation Verifier

It should be clear that a multithreaded simulation may have many different behaviors, depending on the thread scheduler. However, there are certain restrictions on the simulation output, e.g., people can board trains only when those trains are at the station. If you wish, you can write a Ruby program that examines your simulation outputs and checks whether they are valid (i.e., follows all the metro simulation rules in the project description).

The list of possible error in simulation output is nearly endless, so you only check some common errors associated with data races resulting from incorrect synchronization. Some conditions you can look for in the simulation are:

• Trains start by entering the initial station on their metro line
• Trains move forward and backward along the stations on their metro line
• Trains enter a station before they leave it
• Two trains from the same metro line are not at the same station at the same time
• Each passenger follows their itinerary
• Passengers only board and leave a train while it is at a station (i.e., after that train has entered the station, but before it leaves the station)
• All passengers reach their final destination by the end of the simulation
• If there are no passengers in the simulation, each train must complete at least one round trip from the first to the last station (and back) on its metro line

We provide some test cases for your verifier, if you wish to test it on the submit server. sim.rb and submit server tests will invoke your verifier for this part of the project as

     result = verify(lines,numTrains,passengers,simOut)

where lines, numTrains, passengers, simOut are the hashes and array produced in sim.rb from the simulation file. The function verify should return true if the simulation is valid, and false otherwise.

Submission

• Submit your file metro.rb directly to the submit server 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 p5.zip, 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

Academic Integrity

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.