Project 5 - Multithreaded Metro Simulation

• 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

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

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

  3. 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 returning.

  4. 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().

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

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 Java program
  • Simulation.java - main driver for simulator
  • SimulationEvent.java - simulation events
  • TrainLine.java - metro line
  • Station.java - metro station
  • Train.java - metro train
  • Passenger.java - metro passenger
• JUnit public tests
  • PublicTests.java - public tests
  • TestingSupport.java - code to run tests and create & compare log files
• Public test inputs
  • pub1.in
  • pub2.in
  • pub3.in
  • pub4.in
  • pub5.in
  • pub6.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
• Additional Files
  • CALFUZZER-README - directions for using Calfuzzer

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, 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

• 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

     java Simulation [simulate|display] simFileName

Project Implementation

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

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:

• 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      

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

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

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

Submission

• Submit your Simulation.java file and any other .java files you used to implement your simulation directly to the submit server. 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 p5.zip, To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:
  ruby submit.rb

  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

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.