CS 134

Implementing Locks and Condition Variables

In this portion of the assignment, you will flesh out one vital part of OS/161: locks (a.k.a. mutexes) and condition variables. Your code will become part of a pull request offered to your classmates for review; if you win the review, your code will be merged into the master branch of the OS/161 repository and used by everyone in subsequent assignments.

Locks and condition variables are described in Week 3, Lesson 1, which specifically gives the requirements for locks and condition variables in OS/161. (Although that lesson observes that locks and condition variables can be implemented in terms of semaphores, you should not do so for this assignment—instead implement them directly.)

Before You Code

You should use the provided implementation of semaphores for inspiration and as a reminder of OS/161 coding style. You should have reviewed that code as part of the written portion of this assignment, but you may want to review it more closely now.

Think about the design of your implementation. You should consider the following questions:

  • Are there design choices you need to make?
  • What fields will you add to the struct lock and struct cv structures?
  • What do you need to be careful about?

Document Your Design

You will eventually need to provide documentation for your code, in the file handin/lock-cv-design.md. You may want to start this document now, with your initial thoughts about the design of your implementation.

Actual Coding

You should only need to edit two files:

  • kern/include/synch.h
  • kern/threads/synch.c

Coding Rules

Remember, your code needs to match the style of the OS/161 codebase. You can use clang-format -i synch.c to format your code. Note that you should be careful about running clang-format on entire files, as you might accidentally reformat code that you didn't write, which is generally considered uncool.

Technically, however, you may modify any of the source files of OS/161 to provide your implementation. Your criteria for change should be sanity and invasiveness. For example, redefining spl0 as disable_interrupts because you think that your name is clearer is likely not to be viewed very kindly by your peer reviewers because such a change modifies a large number of files and offers marginal benefits.

Testing

The OS/161 tests menu (?t to see the option) has three useful tests for checking your implementation:

  • sy2 tests locks (only) (using the locktest function in kern/test/synchtest.c)
  • sy3 tests locks and condition variables (using the cvtest function in kern/test/synchtest.c)
  • sy4 also tests locks and condition variables (using the cvtest2 function in kern/test/synchtest.c)

Although these tests are useful, you should not assume that they are exhaustive.

Finish Documentation

When you have working code, ensure it is adequately commented and finish describing your design in handin/lock-cv-design.md. This file will be read by your peer reviewers, so assume that they are as familiar with OS/161 and the overall problem as you are. Your goal is to comment on anything notable about your implementation so they can understand it (and hopefully vote for it), not to explain how locks and condition variables work.

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)