Due: Mon Feb 26 11:59 pm
Late submissions accepted until Wed Feb 28 11:59 pm

Assignment by David Mazières and John Ousterhout, with modifications by Nick Troccoli, Benjamin Xie and Xiyu Zhang. Ethics case study includes material from Kathleen Creel.

IMPORTANT: reuse of prior work is not permitted for assign4. In other words, if you have done any work on assign4 in previous quarters, whether formerly enrolled or via auditing, reusing or referring to that work is not permitted while working on assign4 - this is because this assignment has changed significantly in some prior quarters, and so we require that you not refer to prior work (if any). Please let us know if you have any questions or concerns.

In this project you will reflect on the impact of complexities in writing multithreaded code and evaluating trust, and implement code using the "monitor" pattern to complete two synchronization problems with mutexes and condition variables. For the programs you will write, one is for passengers boarding Caltrain, and another is for grouping together guests at a party, and your task is to implement a class for each with the necessary instance variables and code to make the threads coordinate properly.

Learning Goals

• build your skills identifying race conditions and deadlock
• more fully understand where to use mutexes and condition variables as appropriate to coordinate between threads and avoid deadlock/race conditions
• get practice using the "monitor" pattern for designing multithreaded programs
• explore understandings of trust and how we trust the systems we use

Starter Code

To get started on the assignment, clone the starter project using the command

    git clone /afs/ir/class/cs111/repos/assign4/$USER assign4

This line creates a new folder called assign4 in your current working directory containing a copy of the starter code.

Here are the relevant files for your work on the assignment:

• questions.txt: a text file where you will add answers to some written questions
• caltrain.hh/cc: the implementation of the Station class that represents a single train station. You will edit the header file to add necessary instance variables, and edit the cc file to implement the provided methods.
• caltrain_test.cc: a test file containing various tests that spawn threads and call the Station methods in different ways.
• party.hh/cc: the implementation of the Party class that represents a single gathering. You will edit the header file to add necessary instance variables, and edit the cc file to implement the provided methods.
• party_test.cc: a test file containing various tests that spawn threads and call the Party methods in different ways.
• samples: a symbolic link to the shared directory for this assignment. It contains:
  • caltrain_test_soln: a provided sample caltrain_test solution executable that uses a fully-implemented Station class.
  • party_test_soln: a provided sample party_test solution executable that uses a fully-implemented Party class.

Writing and Debugging Synchronization Code

The first two parts of the assignment have you write two monitor-style classes. You do not have to write code to create threads; we provide a test harness for each problem that creates instances of your monitor class, plus threads, and then invokes the methods that you will write. Synchronization code is hard to get right, so it's important for it to be clean, simple, and obvious. The best way to get started on synchronization problems like these 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, for the Caltrain exercise below:

• 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. As you write and test the code, you may discover that your state variables don't have enough information to make important decisions; when that happens, you'll need to add more state variables.

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 assignment. Here are some tips:

• Stalling / deadlock? Try running the test case in GDB and ctl-c when it stalls, to poke around and see where it's stalling. That may point you to a condition variable wait that is never woken up, or some other issue that may give you more info.

• Need to gather more information? Add statements 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.

• Trying to replicate an occasional issue? Try adding sleep_for calls in your code to "force" a specific ordering of events that exposes an issue, and then debug further from there. (Note: you'll need to also #include "thread-utils.h")

Exercise 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 implement a Station class that provides three methods:

• load_train(int available): when a train arrives in the station and has opened its doors, it invokes this method, 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).
• wait_for_train(): When a passenger robot arrives in a station, it first invokes this method. 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 begin moving the passenger on board the train and into a seat (you do not need to worry about how this mechanism works).
• boarded(): Once a passenger is seated, it will call this method to let the station know that it's safely on board. This method is needed because it takes time for passengers to board the train once wait_for_train has given them the go-ahead, and the train mustn't leave the station until all of the admitted passengers are safely in their seats.

Another way to think about the simulation is a passenger can be in one of three states: waiting, boarding, or boarded. A waiting passenger is one who is waiting to board a train - either a train isn't in the station, or it is but there isn't space on the train. A boarding passenger is one who has reserved a seat on the train but is still getting on the train. A boarded passenger is one who has successfully gotten on the train.

Here is some additional information for this problem:

• At any given time, there may exist any number of Station objects, passenger threads, and train threads (subject to the restrictions below).
• Your code should not invoke any of the above methods (they will be invoked by the test harness).
• 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 boarded).
• It must be possible to have multiple Station objects operating independently (activities in one Station should not affect any other Station). This means that you shouldn't have any static class variables in Station (if you don't know what those are, no problem!).
• Our solution for each method is < 10 lines long each (excluding comments); Your methods don't necessarily have to be this short, but if they are significantly longer then you're probably taking a more complicated approach than you need.

Recommended Steps

1. Add just enough code for an arriving passenger to block in wait_for_train until a train has arrived. When a train arrives, all blocked calls to wait_for_train should return, and load_train should return immediately. Ignore train capacity, the boarding process and the boarded method. This isn't correct, of course, but it should allow your code to pass sanity check tests #2 and #3.
2. Now write enough code for load_train to block correctly: as long as passengers are boarding or waiting to board, the train should stay in the station, leaving only when all boarding passengers have invoked boarded. Continue to ignore train capacity: as long as a train is in the station, passengers can begin boarding. This should pass sanity check tests #4 - #7.
3. Now factor in train capacity; even if passengers are waiting, a train should leave if it has no more seats. Once a train leaves the station, even if it had open seats, no passengers should board until another train with space arrives. And even if a train is in the station, a passenger shouldn't board if there are no more seats. You should now pass sanity check tests #8 - #9; woohoo!

Testing

When you're debugging you'll find it useful to run tests individually. The output of sanitycheck shows the command to run for each test; for example,

./caltrain_test no_waiting_passengers

will run the first test, in which trains arrive when there are no passengers waiting. Try invoking this command: it prints out a series of messages indicating what the test is doing and any errors it encounters. You can compare this to the output of the sample solution in samples/caltrain_test_soln. When you're debugging, you'll also find it useful to look at the code in the test harness so you can see exactly what is going on. For example, the code for the no_waiting_passengers test is in the method no_waiting_passengers in caltrain_test.cc; each test is implemented by a method with the same name as the test.

Once you have passed all of the sanity checks for this exercise, you should also test your Caltrain solution by invoking the following command: ./caltrain_test random 1000 50 This will run a randomized test where 1000 passengers arrive at the station, followed by a series of trains with different capacities (there will be at most 50 free seats in any one train). Check the output manually to make sure things look correct. Try running this test many times to make sure it always works (see Debugging Irreproducible Failures). Try varying the parameters as well.

Note: the random test creates a large number of threads; depending on other activity on the machine, it's possible that the system may run out of threads. If this happens, the test will fail with an error message that says "Resource temporarily unavailable". When this happens, try again. If it fails repeatedly, you can either reduce the number of passengers or log out and log in to a different myth machine.

We do not guarantee that the tests we have provided are exhaustive, and may use further autograder tests/review to evaluate correctness.

Here is information about what sequence of events each test is evaluating:

Expand/Collapse Test Details

Exercise 2: Party Introductions

You have been hired as an organizer for parties where people want to be introduced to other guests with certain Zodiac signs. In particular, you must create a C++ class Party with a single method that can be used to introduce incoming guests to each other for conversation. 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 (a number from 0-11). The other_sign argument indicates that this guest would like to talk to 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:

• Guest names could be any string, including the empty string
• 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.
• It is possible for multiple guests to have the same name.
• It must be possible to have multiple Party objects all operating independently (activities in one Party should not affect any other Party). This means that you shouldn't have any static class variables in Party (if you don't know what those are, no problem!).
• Guests must be matched fairly: if there are several waiting guests that match a new arrival, the one that has been waiting longest should be chosen. To do this, you cannot rely on condition variables to be FIFO (meaning they will always go with the thread waiting the longest when handing over the lock or notifying threads); you will need to make sure that the guest waiting the longest is the one that matches.
• Our solution for the meet method is < 20 lines long (excluding comments); this isn't a hard requirement for you to adhere to, but if your implementation is significantly longer, then you're likely taking a more complicated approach than you need.

Design

For this exercise, use your learnings about design, incremental development and testing from the Caltrain exercise to devise a plan for how to tackle this problem. Here are a few tips:

• Consider helpful data structure(s): In addition to fixed-size arrays, C++ has built-in data structures that may come in handy. This is a more open-ended design problem; it's up to you to devise how to best store any necessary state!
• Structs bundle information together: If you find yourself wanting to store multiple fields in a single entry in a data structure, you can define a custom struct type in the private section of your class, and have your data structure use it. E.g. instead of having 5 parallel vectors for storing different fields, you can have one vector of structs, each of which contains those fields.
• C++ Data structures make copies: vector, map, queue, set, etc. generally make copies of elements that are inserted; so if you expect to insert an element, access it later and change it, and need that to change the original, consider how pointers might help instead. This also applies to the next note.
• Condition variables can't be copied: condition variables can't be inserted directly into C++ data structures because they can't be copied.
• No need to heap allocation: You should not need to use any heap allocation (e.g. new, delete). Any private instance variables will persist across method calls even without heap allocation.

Testing

Here is information about what sequence of events each provided test is evaluating:

Expand/Collapse Test Details

There is also the random test that you can run many times with various parameters. You can run it like this:

./party_test random 100 4

This runs a randomized test with a large number of party guests with different preferences. The first parameter (100) indicates how many guests will arrive, and the second parameter indicates how many distinct signs should appear among all the arrivals (4 means that only 4 of the numbers between 1 and 12 will be used as my_sign or other_sign; a smaller value like 4 is more likely to produce conflicts that expose bugs). Check the output manually to make sure there are no error messages. Try running this test many times (and also try varying the parameters), in order to generate a variety of scenarios.

Exercise 3: Reflecting on and Communicating Trust

As you may know, the Computer Science Department has begun adding short units on ethics to many of its classes. For CS 111 the ethics topic is trust. The overall goal of this topic is to raise your awareness of a variety of issues relating to trust. For this assignment you will consider techniques for establishing trust in a system.

Building on the lecture discussion about trust, answer the following questions in questions.txt:

Question 1: suppose you needed to convince another student in CS 111 that they can trust your code for this assignment. How would you go about that? Note: for someone else to trust your code, you may want to consider how you can increase the legitimacy of either the code itself or the creator of the code.

Question 2: for this assignment, the provided sanitycheck tests are not necessarily comprehensive. What additional steps could/did you take to increase your level of trust that the code will perform as expected?

Software bugs are examples of situations where systems are less trustworthy than we think or would like. They are to difficult to test for, yet they can have significant real-world impact. In 2020, Natalie Silvanovich of Google Project Zero discovered a race condition with Google’s video calling service, Duo. Please read this document, which describes the problem, and then apply Nguyen’s framework of trust as an unquestioning attitude to a real world race condition by answering the questions below in questions.txt:

Question 3: describe the race condition and its impact.

Question 4: in 1-3 sentences, describe one way developers of the Google Duo bug exhibit agential gullibility.

Question 5: in 1-3 sentences, identify two ways a mobile phone user could infer trust in Google Duo.

Question 6: in 1-3 sentences, identify one way a mobile phone user could substitute the need to trust Google Duo.

Other Coding Requirements

• Your solutions for both problems should be written in C++ and use the C++ library classes for synchronization.
• 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 declare any further mutexes other than the ones declared in the starter code.

Aside: Are Locks and Condition Variables FIFO?

The C++ classes for locks and condition variables are mostly FIFO (First In First Out: the first thread to wait is the first thread to wakeup) but not perfectly so. If you're curious to see this, try running

./party_test cond_fifo

This runs a test to see if condition variables are perfectly FIFO. If you run it several times, you'll see that it sometimes fails (the first thread to wait on a condition variable doesn't necessarily get notified first).

You can assume that things are generally "fair enough" to implement the Caltrain problem without worrying about this, but for the Party problem, you cannot rely on condition variables to be FIFO to satisfy the requirement that if there are several waiting guests that match a new arrival, the one that has been waiting longest should be chosen. You will need to make sure that the guest waiting the longest is the one that matches.

Submitting and Grading

Once you are finished working and have saved all your changes, submit by running the submit tool in the tools folder: ./tools/submit. We recommend you do a trial submit in advance of the deadline to allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work. You can confirm the timestamp of your latest submission in your course gradebook.

Your assignment will be graded using the tests we expose via sanitycheck, plus the following:

• potential additional autograder tests to test correctness
• reviewing your questions.txt responses for the short answer questions
• ensuring your program has no busy waiting or forced sleeping (i.e. calls to usleep)
• ensuring your program has no race conditions or other concurrency issues
• no static class variables or other designs that mean instances of Station or Party are interdependent
• ensuring compliance with the monitor pattern, meaning Station has exactly 1 mutex, and Party has exactly 1 mutex
• Style code review - Synchronization code is hard to get right, so it's important for it to be clean, simple, and obvious. 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. Check out our style guide for other style tips.