Project 3: Synchronization

Project 3: Synchronization

This project consists of two synchronization problems.

Problem 1: Caltrain Automation

Caltrain has decided to improve its efficiency by automating not just its trains but also its passengers. From now on, passengers will be robots. Each robot and each train is controlled by a thread. You have been hired to implement synchronization that will guarantee orderly loading of trains. You must define a Station class that provides three methods:

  • When a train arrives in the station and has opened its doors, it invokes the method
    load_train(int available)
    where available indicates how many seats are available on the train. The method must not return until the train is satisfactorily loaded (all passengers are in their seats, and either the train is full or all waiting passengers have boarded).
  • When a passenger robot arrives in a station, it first invokes the method
    wait_for_train()
    This method must not return until a train is in the station (i.e., a call to load_train is in progress) and there are enough free seats on the train for this passenger to sit down. Once this method returns, the passenger robot will move the passenger on board the train and into a seat (you do not need to worry about how this mechanism works).
  • Once a passenger is seated, it will call the method
    seated()
    to let the station know that it's on board.

Here is some additional information for this problem:

  • You do not have to write code to create threads; we will provide a test harness that creates Station objects, plus threads to represent passengers and trains, and then invokes the methods that you write. At any given time, there may exist any number of Station objects, passenger threads, and train threads (subject to the restrictions below).
  • You may assume that there is never more than one train in a given Station at once, and that all trains (and all passengers) are going to the same destination. Any passenger can board any train.
  • Your code must allow multiple passengers to board simultaneously (it must be possible for several passengers to have called wait_for_train, and for that method to have returned for each of the passengers, before any of the passengers calls seated).
  • It must be possible to have multiple Station objects operating independently (activities in one Station should not affect any other Station).

Problem 2: Party Introductions

You have been hired by Stanford's Greek Houses to help manage parties at fraternities and sororities. In particular, you must create a C++ class Party with a single method that can be used to introduce incoming guests to each other. When a guest arrives at a party, they will invoke the following method on a Party object:

std::string meet(std::string &my_name, int my_sign, int other_sign);

The my_name argument gives the name for this guest and my_sign indicates the guest's Zodiac sign. The other_sign argument indicates that this guest would like to meet someone with that Zodiac sign. The meet method must not return until a guest has arrived with matching my_sign and other_sign, and meet must return the name of the matching guest. In addition:

  • Guests must be matched: if A receive's B's name, then B must receive A's name.
  • If a suitable match is not immediately available, then meet must wait until a match becomes available. In the meantime, it must be possible for non-interfering matches to occur.
  • Zodiac signs are represented with integers in the range 0-11, inclusive, which correspond to the birth months January-December. You may assume that callers never provide values outside the range 0-11.
  • It must be possible to have multiple Party objects all operating independently (activities in one Party should not affect any other Party).
  • Guests must be matched in order of arrival, where "arrival" means starting execution of meet and locking the synchronization mutex.

Developing and Testing

To get started on this project, login to the myth cluster and clone the starter repo with this command:

git clone http://web.stanford.edu/class/cs111/starters/sync.git cs111_p3

This will create a new directory cs111_p3. Do your work for the project in this directory. The directory will contain files caltrain.cc and party.cc with class and method declarations for the two problems: fill in the existing declarations and add any other definitions or methods that you need.

The directory also contains a Makefile; if you type make, it will compile your code for both problems. caltrain.cc will be compiled together with a test program caltrain_test.cc, and party.cc will be compiled together with a test program party_test.cc. You can invoke the command ./run_tests to run a series of basic tests on your solution. In addition to running tests with run_test, you should also test your Caltrain solution by invoking the following command:

./caltrain_test random

This runs a randomized test with a large number of waiting passengers and a variety of trains with different capacities. Check the output manually to make sure there are no errors. Try running this test many times, in order to generate a variety of scenarios.

We do not guarantee that the tests we have provided are exhaustive, so passing all of the tests is not necessarily sufficient to ensure a perfect score (CAs may discover other problems in reading through your code).

Getting Started

The best way to get started on these problems is to think about what information about the state of the world needs to be kept in a Station or Party object. Consider what information is needed to implement the methods. For example:

  • What information is needed in order to decide whether a passenger can safely board a train?
  • What information is needed to decide when a train can leave the station? We call these variables state variables because they keep track of the state of the world, such as how many passengers are currently waiting. Once you have an initial guess about the state to maintain, you can then try writing the methods. For starters, add enough code to maintain proper values for all of the state variables. Then you can write code that uses those values to determine when methods can safely return.

Debugging Irreproducible Failures

Bugs in synchronization code often result in failures that only occur occasionally; most of you will experience problems like this at some point during this project. The easiest way to debug these problems is with tracing. Add a statement to print out information each time a lock is acquired, before and after each condition variable wait, and after any other major decisions are made. Print out lots of information in each of these statements, including where in the code you are, which thread is running (if you can tell), and key state variables. Then pick a test that occasionally fails and run it repeatedly until it does fail (pipe the output to a file). If you walk through the log file, you will probably find a sequence of events that you hadn't expected to occur, and which your code can't handle properly.

Complexity Penalty

Synchronization code is hard to get right, so it's important for it to be clean, simple, and obvious. Unfortunately, submissions for this project often end up long and complicated; such solutions rarely work, and in real life they would be brittle and hard to maintain. If the CAs judge your code to be unnecessarily long and complicated, they will deduct up to 20% of the total score for this. Our solution for caltrain.cc has 49 lines and our solution for party.c has 38 lines, not including blank lines and comments. Note: your goal should be simplicity, not just line count; simple programs are usually shorter than complex ones, but the shortest program isn't always the simplest.

Other Requirements

  • Your solutions for both problems must be written in C++.
  • You must use the C++ library classes for synchronization. One way to do this is with the classes mutex, unique_lock, and condition_variable. Another set that is functionally equivalent for this project is mutex, lock_guard, and condition_variable_any.
  • You may use other STL container classes (vector, etc.) in your solutions, but you may not use any classes that simplify the synchronization issues. If you have any doubt about whether a class is acceptable or not, please check with the course staff.
  • There must be no busy-waiting in your solutions.
  • You must use the monitor design pattern for synchronization, as discussed in lecture. In particular, you may not use more than one mutex per Station or Party object.
  • You may use more than one condition variable for each Station or Party object. Code using one condition variable to wake up many different threads can sometimes be improved by using multiple condition variables. This way only threads you really want to wake get woken up.
  • You may assume that there are no spurious wakeups on condition variables. If you haven't heard the term "spurious wakeup" before, don't worry; you can just ignore this comment.

Submitting Your Work

To submit your solutions, cd to the directory containing your work, then invoke the command

./submit

If you discover problems or improvements after you have submitted, you may resubmit; only the latest submit will be graded.