Project 5

Updates

• Fix to previous update. A train should not leave until passengers finish boarding. No passengers should be able to board a train after it has left. 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. See this post on the web forum.
• Fixed a typo in the example. Should be wait as long as y > 0 rather than "y <= 0".
• There is no requirement on how many monitors you use for this project---just that you use proper synchronization

Introduction

In this project, you will develop a multi-threaded Ruby program that simulates the Washington Metro. In lecture, we've talked about writing multi-threaded Java programs. Multi-threading in Ruby works almost the same way, and at this point in the class, you should be able to move those ideas from Java to Ruby easily.

A Brief Primer on Threading in Ruby

To create a new thread in Ruby, use Thread.new:

t = Thread.new {
  sleep 1  # sleep for 1 second
  puts "Running in a new thread!"
  $stdout.flush  # make sure standard output is seen
}

Unlike Java, when a Thread is created in Ruby, it has access to all the variables that were in scope at the point it was created (including local variables). But, probably, you should use global variables for data shared among threads.

To get a mutual exclusion lock, you can use the Monitor class:

require 'monitor.rb'
l = Monitor.new
l.synchronize {
  # lock l held during this block
}

You can use condition variables with a monitor:

require 'monitor.rb'
l = Monitor.new
c = l.new_cond
l.synchronize {
  c.wait_while { y > 0 }   # wait as long as y > 0
}
l.synchronize {
  c.broadcast  # wake up all waiters
}

Also note that in Ruby, unlike in Java, once the main thread exits, all the threads in the system are killed. To find out more, look up classes Thread, Monitor, and MonitorMixin::ConditionVariable.

Part 2: The Simulation

We will begin by describing the simulation; however, we suggest that you actually start with the other part of the project, described below. (That's why we've called this "part 2.")

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 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 infinite 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 the sample input:

  $sample = [
    ["Alice", "College Park", "Gallery Place"],
    ["Bob", "Silver Spring", "Bethesda"],
    ["Charlie", "Union Station", "Fort Totten", "College Park"],
    ["Dave", "Silver Spring", "Metro Center", "Ballston"]
  ]
  

  This file lists the intended paths of four people. For example, Alice starts at College Park and wants to take the train to Gallery Place. As another example, 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, even if it arrives, 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 need not worry about people that have impossible travel plans. 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.

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.

There should be no other output from the simulation

IMPORTANT: In order to make sure the output makes sense, you absolutely 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 1: A Verifier in Ruby

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 we asked.
• Ensure that trains start at their initial station, and then move forward and backward along their lines
• 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 with that train
• Make sure all the people get to where they're going in the simulation.
• Make sure no extra people move around on the trains.

It's possible we've left something off the above list that is required according to the writeup for part 2; you still need to check for every case for part 2, even if we forgot to mention something just above.

Starting Code

You can get a (very minimal) skeleton for this project at

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.