Project 4: Implementing Locks and Condition Variables

In this project you will extend your work in Project 2 by adding locks and condition variables.

Basic APIs

You will create two C++ classes: Mutex and Condition. The Mutex class has the following methods:

Mutex()
This is the constructor for Mutex objects. It has no arguments.

void lock()
Locks the Mutex. If the Mutex is currently locked, blocks the calling thread until the Mutex is unlocked. If there are multiple blocked threads, they should return from lock in FIFO order.

void unlock()
If there are threads waiting to lock the Mutex, passes ownership of the Mutex to the first waiting thread and wakes it up. If there are no threads waiting, releases the lock.

bool mine()
Returns true if the calling thread owns the lock, false otherwise.

The Condition class has the following methods:

Condition(Mutex &m)
This is the constructor for Condition objects. The m argument is the Mutex associated with the condition. Note that this class differs from the std::condition_variable class in C++ in that the associated lock is passed to the constructor rather than the wait method.

void wait()
Releases the associated lock and blocks the thread until signal or broadcast has been invoked, then reacquires the associated lock. The associated lock must be held when this method is called.

void signal()
If any threads are blocked on the condition variable, wakes up the one that has been blocked the longest. If no threads are blocked, then this method does nothing. The associated lock must be held when this method is called.

void broadcast()
Wakes up all of the threads currently blocked on the condition variable. The associated lock must be held when this method is called.

Developing and Testing

To get started on this project, make a copy of your work for Project 2 by typing the following command in the parent directory of Project 2:

cp -r cs111_p2 cs111_p4

This will create a directory cs111_p4. Do your work for the project in this directory. The files thread.h and sync.cc contain a skeleton for all of the code you need to write. Add to the declarations in thread.h and fill in the bodies of the methods in sync.cc to implement the facilities described above. Use the features you implemented in Project 2 for this project.

The directory also contains a Makefile; if you type make, it will compile your code along with a test program, creating an executable test. You can then invoke ./run_tests lock_tests, which will run a simple set of tests on your code. You can also invoke test with an argument specifying a particular test name; this will run a single test and print out its results. Invoke test with no arguments to print out all of the available test names.

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).

Miscellaneous Notes

• You may assume that your code will only run on single-core systems, so disabling interrupts ensures that no other thread will run. You do not need to add spin locks as described in lecture for multicore implementations.

Submitting Your Work

To submit your solution, cd to the directory containing your work and invoke the command

./submit

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