Computer Science 61 and E61
Systems Programming and Machine Organization
Assignment 5: Mastering Synchronization
This assignment is all about synchronization. There are rather few lines of code to write, but getting those lines correct can be tricky. Think carefully through the questions and make sure you understand what you need to accomplish.
As in past assignments, you may discuss the problem set with other students, however, each student must submit his/her own code for this assignment; there will be no partners allowed. Go to the grading server and configure problem set 5 to use your personal repository and not your partner's from previous assignments. Please do this immediately so we don't run into last minute problems at submission time.
After completing this assignment, you should be able to:
- Use semaphores, mutexes, locks, and condition variables effectively.
- Identify and protect shared state.
- Select an appropriate synchronization primitive to solve a synchronization problem.
- Solve moderately challenging synchronization problems.
Get the Code
Note: The code is ready to go for this assignment, but you will not be able to compile or run on the grading server. We are working on that and will let you know when it's ready. In the meantime, this should work just fine on the appliance.
First, ensure that your repository has a
handout remote. Type
% git remote show handout
If this reports an error, you need to create handout as a local name for the remote course problem set repository. You do this by typing:
% git remote add handout git://code.seas.harvard.edu/cs61/cs61-psets.git
git pull handout master. This will merge our Assignment 5 code with your previous work. If you have any “conflicts” from Assignment 4 resolve them before continuing further. Run
git push to save your work back to code.seas.
You may also create a new
cs61-psets repository for this assignment. You’ll need to tell us using the grading server if you do.
Part I: Warm Up Problems
Learning to select the right synchronization primitive to solve a problem is a key skill to develop. For each scenario listed below, select the best synchronization primitive from the following list and justify your choice. You may use each synchronization primitive as many times as you need to. Write your answers in your
- Counting semaphore
- Binary semaphore
- Lock (without a condition variable)
- Lock and a condition variable
(WP stands for written problem.)
WP-1. Soccer players often receive concussions by simultaneously jumping for headers. FIFA, in attempt to draw attention away from their corruption scandal, decided that clever CS61 students could easily solve this problem with a synchronization primitive to arbitrate which player got to jump up for the header; in addition, FIFA demanded these primitives be very high performance. Which primitive would you suggest?
WP-2. Professor Seltzer was making pancakes for hungry teenagers. The pancakes come out in batches of three and the teenagers are well-behaved -- each one will eat only one pancake at a time, and as long as there are enough pancakes for the teenagers given access to the pancakes, they won't fight. She'd like a synchronization primitive that would allocate pancakes to teenagers to prevent any fighting. (There is no need to worry about leftovers between batches -- all pancakes are consumed pretty much instantly.) Suggestions?
WP-3. You are competing in a new Olympic event called a distributed relay. One team member has to run one lap at the Harvard track. The next team member must run a lap at the Yale track. The third team member runs a lap at Brown track, and the last team member runs a lap at the Columbia track. Each runner must not start until the previous runner has completed his/her lap. The traditional passing of the baton or slapping of the hands clearly won't work, so they've turned to you, a savvy CS61 student, to provide the proper synchronization. What mechanism do you use?
WP-4. Last winter, competition for parking in Cambridge became brutal due to the massive quantities of snow that accumulated on our streets. The traditional use of space-savers (e.g., cones that mark a spot as being "owned" by someone who invested physical labor into shoveling it out) became contentious. In anticipation of another snowy winter, the Cambridge Department of Public Works is looking for a solution for this year. They've decided:
- Neighborhoods will hand out parking tokens
- Any car without a visible token will be towed to the far reaches of the universe.
- Each neighborhood will have a token check-in point: cars must drive to the check-in point to obtain a token for a specific spot and return a token when they leave a spot (subject to enormous fines if they steal the token).
CDPW would like the check-in points to operate efficiently, allocating and deallocating spots in parallel as much as possible. What synchronization primitive(s) should they use?
WP-5. It is well known that graduate students (as well as many others) are motivated by free food. A graduate student's day consists of mainly two things: doing research and checking email to determine if anyone has announced any free food. When research is going well, students experience flow and are unlikely to look at their email. The students have built a cool Bayesian filter that detects when a message for food comes in and beeps. Unfortunately, these students never took CS61 and they have a race condition! If the food notification arrives just as the student finishes checking email, but before returning to research, the beep gets lost. Can you propose a primitive to fix this race condition?
The remainder of this assignment will require coding. You've been hired by Uber to help them launch some new initiatives. Each of these initiatives requires careful synchronization of critical Uber state. Once you've come up with synchronization strategies for each part, please explain your strategies in a comment block in the files relevant to each part. You will not receive full points if you do not explain your correctness criteria, synchronization strategy, and the reasons why your strategy works.
Part II: Uber-Pi
The masterminds at Uber have concocted a new revenue model. In addition to driving passengers around, they've decided that they can use the onboard computers in their drivers' vehicles to perform mathematical calculations. They wish to test their system out, by performing a parallel computation to compute pi.
Every time one of their cars makes a trip, its computer participates in a massively distributed Monte Carlo simulation.
We provide you code that supports
uber drivers/vehicles and
NUM_PASSENGERS who each have to make
NUM_TRIPS Uber trips.
In this sad, sad world, only one person can ride in an Uber.
You will be working in the
uber-pi directory for this exercise.
We provide you with driver code that runs our Uber simulation, including the routines that compute pi on the results generated by the different cars.
We also provide you with a synchronized version of the
passenger function, which permits a correct solution.
Unfortunately, the solution is correct, but not particularly high performance -- its parallelism is severely limited. If you run the
solution, you'll see that Uber drivers are driving passengers only about 25% of the time -- this makes drivers very sad, because they do not make money, and it makes passengers sad, because they are waiting for rides while Uber drivers are idle!
You can run the program at the command line:
./uber-pi 0 or by using
WP-6. Read the code in
uber-pi.c and, in your
README.txt file, explain the limitations of this implementation.
Part II-A: Better initialization
Write a new version of the passenger thread function in
passenger_better_init. This version should still uses mutexes, but should produce significantly improved Uber utilization (that is, Uber drivers should be driving almost 80 or 90% of the time). That is, we wish to increase the
parallelism achievable. Think about better ways to begin a passenger's search for a free Uber vehicle. Explain your solution in a comment block in
Part II-B: Trylocking
Now, write a new passenger thread function in
passenger_trylock, that uses
pthread_mutex_trylock to achieve even better utilization. Explain your solution in a comment block in
WP-7. Under what conditions do you believe your
trylock implementation will outperform your earlier implementation?
(Write the answer in your
Part III: Ubler Dispatch
Having successfully helped Uber run their pilot for performing mathematical computations, Uber would now like your help implementing a dispatching service (which will be an integral part of their new Ubler service described in Part IV).
Business is picking up and Uber's unsynchronized dispatching scheme has produced angry drivers who arrive to pick up passengers, only to find that they've jumped into another Uber vehicle. Passengers are angry too, because sometimes they end up waiting a long time and are never picked up. Surely you can help!
Take a look at the files in the
dispatch directory. There are slightly more files than the previous exercise but don't panic yet; most of them are just helper routines that you don't have to implement yourself. The file
dispatch.c contains a simulation of Uber's unsynchronized, first-in-first-out, queue-based mechanism, and this is the only file where you need to write your own code (apart from
dispatch.h where you need to fill out some additional struct fields)! The dispatcher receives requests for rides from
STDIN. You can find some requests we generated for you in the
dispatch_tests directory. (You can generate more requests by using
testgen.py) The dispatcher calls the
dispatch() function for each job it encounters and that's where your code comes in! Take a close look at the code in
dispatch.c to see what has already been done for you. You should provide proper enqueue synchronization to make sure that:
- Every job gets enqueued exactly once.
- The queue capacity is never exceeded. (The size of the queue never exceeds
The dispatcher expects each request passed in via
STDIN to have the following format:
cid time x1 y1 x2 y2
cid (customer id) and
time are integers, and
(x1, y1) and
(x2, y2) are floating point pairs denoting the coordinates of the origin and destination associated with the requests. Each request is ended by a new line (
The drivers are implemented as a set of threads that run the
driver_thread() function. Each driver is supposed to get a request from the queue, and serve that request by calling the provided
drive() function (declared in
request.h). Here too we have some synchronization challenges to address! You must guarantee that:
- Drivers never starve -- that is if a driver goes to retrieve a job, but the queue is empty, the driver must wait for new jobs to arrive (busy waiting is not acceptable).
- Every passenger request gets handled, and no passenger request is served twice.
You also need to make sure your program properly exits once there are no more requests to handle.
Explain your synchronization strategy in the provided comment block in
- Take a look at
queue.cto see how the queue works. Does it work when it's being accessed by multiple drivers plus the dispatcher?
- Apart from synchronization, also keep in mind that you are supposed to manage memory properly. Look for things that are dynamically allocated in
dispatch.cand make sure your drivers don't leak memory.
- Your solution should work for any reasonable queue size (<= 15 in this exercise)! You can change the queue size by changing the definition of the
queue.h. Be aware that a smaller queue may expose more bugs. (Why?)
- The test program provided in
dispatch_test.cmay or may not expose all bugs in your implementation! Think about all possible race conditions before you code.
- We may test your
dispatch.cwith different tests (different
main()functions) on the grading server. Make sure your solution works with any single-dispatcher/multiple-driver setup. You can try modifying the provided test program files to expose more race conditions.
- DO NOT use the grading server as the debugging server. We will NOT provide debug outputs on the grading server.
Part IV: Uber meets Foodler
Uber and Foodler have decided to team up to offer a novel service to Boston area residents! You will find the code for this problem in the
Using the new Ubler app, customers place orders to one of a select number of local restaurants. Depending on where a driver is, an Ubler driver either picks up passengers and takes them to the restaurant where their food is being prepared or picks up the food at the restaurant and brings it to the customers at their home. Customers seem to love the excitement of not knowing whether they are going out to dinner or having takeout!
ubler_helpers.c file contains the
create_and_run_requests method, which sets up the passengers, drivers, and data structures. There's a lot going on, but for the most part, you only need to worry about the driver threads (implemented in the
driver_thread function in
ubler.c). A driver receives half of a request, which is either a meal or a customer. The driver needs to make sure that if the request is a customer, that the customer's food is not already in transit, and that if the request is a meal, that the customer isn't already en route to the restaurant.
We provide a number of helper functions to interface with the meal, customer, and restaurant data structures, so most of your synchronization code should go in
Every Ubler trip has two endpoints: a location that the driver must go to to pick someone/something up (either a meal or a customer), and a location that the driver has to go to to drop the meal or customer off. Once the driver has a customer or a meal, the driver can use
meal_get_customer, respectively, to find the other end of the trip. Once the driver has both a customer and a meal, the driver can use
customer_get_location to get the location of a customer, and
meal_get_restaurant to get the restaurant where a meal is (which in turn has a destination). Before driving off to pick up a meal or customer, the driver must check to make sure that neither of the two endpoints of the trip has been picked up yet (using
A correct implementation will:
- Ensure that every passenger/meal pair gets delivered.
- No passenger/meal gets delivered more than once.
- Passengers and their meals are not simultaneously being moved around at the same time. In other words, when a passenger arrives at a restaurant, the order had better still be there and when an order gets delivered to a passenger's home, the passenger had better be there.
- There are no deadlocks.
- Be more fine-grained than just one "big lock" - i.e., do not just lock the entire body of the while loop in
driver_thread. You should ensure that multiple Ubler drivers can service multiple requests at once.
For this part, you can expect to make changes to
struct customer, and
customer.c. Don't overthink this part! A correct implementation can be achieved in about a dozen lines of new code.
Once you have completed this part, tests 1-6 should pass (
cd into the
ubler folder and run
make check-1-6). If one of the tests prints an error message or times out, there's a problem with the synchronization. You can also run the testing code yourself by running
./ubler_test num_requests num_drivers num_restaurants. This will run
create_and_run_requests with the correct parameters and print out
Success! on success or information about what went wrong if something went wrong.
As in previous exercises, explain your synchronization strategy in the provided comment block in
NB Throughout the handout code, you might see references to "Part One" and "Part Two" - if you do, ignore the comments about part two unless you decide to try the Just for Fun challenge (the comments were left over from an earlier version of the code where this part was called Part One, and the Just for Fun was called Part Two).
Synchronization problems are notoriously difficult to debug -- deadlocks are relatively easier to find than race conditions, because your system grinds to a halt; race conditions can be enormously difficult to track down. Here are some tips to use when debugging.
- Precisely state your correctness conditions. We have given you a list of criteria that a correct solution must enforce; translate those into statements about state in your solution. (Include this in your code comments.)
- Map each correctness condition to a synchronization protocol. Before you write code, go through your protocols asking yourself, "What if I get descheduled here?" between every two steps in your protocol. (Include this in your code comments.)
- It is sometimes helpful to add calls to sleep in your code to increase the probability that threads interweave in interesting ways.
Just for Fun
If you look in the code for
ubler_test.c in Part IV, you'll notice that it's listening for a
--mix-up-meals option. This codes simulates the following scenario:
After running their experiment for a few weeks, the folks at Ubler have started to realize that restaurants tend to mix up customers' orders at an alarming rate. In particular, they have noticed that restaurants have a bad habit of swapping two customers' meals unexpectedly. To help deal with this problem, Ubler drivers can now call on
fix_mismatch when they suspect that a meal has been assigned to the wrong customer. In this part of the assignment, you will have to leverage the interfaces into meals and customers to determine when a meal has been assigned to the wrong customer, and you will have to synchronize calls to
The specific way that meals can get mixed up is as follows:
- Each customer has a pointer to a meal, and each meal has a pointer to a customer. In a perfect world, these relationships are essentially two-way relationships.
- However, sometimes the pointers that the meals have have been swapped. For example, let's say that customer A ordered meal A, and customer B ordered meal B. When meals A and B are swapped, meal A will have a pointer to customer B, and meal B will have a pointer to customer A, but customer A will still have a pointer to meal A, and customer B will still have a pointer to meal B.
fix_mismatchtakes in meal A from the above example and fixes both meal A and meal B.
To trigger this behavior, you can pass
--mix-up-meals to the end of
./ubler_test. A correct implementation has all the same criteria as for Part IV - it's just more difficult to get it to that point. You can automatically check that your code works by running
make extra. This will run tests 7-9, which are
Submit your assignment by doing all of the following:
README.txt to document any collaboration and send us any grading notes. Please explicitly state that your assignment is ready for grading by adding the line "GRADE ME."
2. Commit your changes to your git repository with the commit message "A5 Grade Me"
3. Push your repository to
4. Update the grading server with your current repository information.
5. If you are taking late days, please put a line in your
README.txt file and annotate any commits that you make after the due date with "do not grade" (place that at the end of a useful commit message).
This lab was designed for CS61 (2015).