Project 5 - Multithreaded Metro Simulation

Introduction

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.

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
  • metro.rb
• Public tests
  • public_simulate00.rb
  • public_simulate01.rb
  • public_verify00.rb
  • public_verify01.rb
  • public_verify02.rb
  • public_verify03.rb
• Inputs for verify tests
  • public_verify01.in
  • public_verify02.in
  • public_verify03.in
• Possible simulation outputs
  • For public_simulate00.rb
    • public_simulate00a.out
    • public_simulate00b.out
    • public_simulate00c.out
  • For public_simulate01.rb
    • public_simulate01a.out
    • public_simulate01b.out
    • public_simulate01c.out
• Ruby script to run public tests
  • goTest.rb

Project Description

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:

require "metro.rb"
simulate(input)

where input is a Ruby array describing the people's paths through the system (see below). Here is how the simulation should work:

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

  $red_line = [
    "Glenmont",
    "Silver Spring",
    "Fort Totten",
    "Union Station",
    "Gallery Place",
    "Metro Center",
    "Bethesda",
    "Shady Grove"
  ]
  

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

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

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

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

• Only print out the above statements while you are still holding a lock.

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

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

require "metro.rb"
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 nil otherwise. In particular, you should be sure to check for the following:

• Check that all the output messages are formatted exactly as specified
• 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 input
• 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 simulation
• Make sure no extra people move around on the trains

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.