Lab Handout 5: rwlocks and Event Barriers
The lab checkoff sheet for all students can be found right here.
Get Started
Before starting, go ahead and clone the lab5
folder, which contains the test framework for the EventBarrier
class discussed in Problem 2.
git clone /usr/class/cs110/repos/lab5/shared lab5
Problem 1: Read-Write Locks
The following was a final exam question from a few years ago. The students were expected to write the code that follows.
The read-write lock (implemented by the rwlock
class) is a mutex
-like class with three public
methods:
class rwlock {
public:
rwlock();
void acquireAsReader();
void acquireAsWriter();
void release();
private:
// object state omitted
};
Any number of threads can acquire the lock as a reader without blocking one another. However, if a thread acquires the lock as a writer
, then all other acquireAsReader
and acquireAsWriter
requests block until the writer releases the lock. Waiting for the write lock will block until all readers release the lock so that the writer is guaranteed exclusive access to the resource being protected. This is useful if, say, you use some shared data structure that only very periodically needs to be modified. All reads from the data structure require you to hold the reader lock (so as many threads as you want can read the data structure at once), but any writes require you to hold the writer lock (giving the writing thread exclusive access).
The implementation ensures that as soon as one thread tries to get the writer lock, all other threads trying to acquire the lock—either as a reader or a writer—block until that writer gets the locks and releases it. That means the state of the lock can be one of three things:
- Ready, meaning that no one is trying to get the write lock.
- Pending, meaning that someone is trying to get the write lock but is waiting for all the readers to finish.
- Writing, meaning that someone is writing.
The following solution (written by Jerry Cain) relies on two mutex
es and two condition_variable_any
s. Here is the full interface for the rwlock
class:
class rwlock {
public:
rwlock(): numReaders(0), writeState(Ready) {}
void acquireAsReader();
void acquireAsWriter();
void release();
private:
int numReaders;
enum { Ready, Pending, Writing } writeState;
mutex readLock, stateLock;
condition_variable_any readCond, stateCond;
};
And here are the implementations of the three public
methods:
void rwlock::acquireAsReader() {
lock_guard<mutex> lgs(stateLock);
stateCond.wait(stateLock, [this]{ return writeState == Ready; });
lock_guard<mutex> lgr(readLock);
numReaders++;
}
void rwlock::acquireAsWriter() {
stateLock.lock();
stateCond.wait(stateLock, [this]{ return writeState == Ready; });
writeState = Pending;
stateLock.unlock();
lock_guard<mutex> lgr(readLock);
readCond.wait(readLock, [this]{ return numReaders == 0; });
writeState = Writing;
}
void rwlock::release() {
stateLock.lock();
if (writeState == Writing) {
writeState = Ready;
stateLock.unlock();
stateCond.notify_all();
return;
}
stateLock.unlock();
lock_guard<mutex> lgr(readLock);
numReaders--;
if (numReaders == 0) readCond.notify_one();
}
Very carefully study the implementation of the three methods, and answer the questions that appear below. This lab problem is designed to force you to really internalize the condition_variable_any
—one of the more difficult concepts in the entire threading segment of the course, and understand how it works.
- The implementation of
acquireAsReader
acquires thestateLock
(via thelock_guard
) before it does anything else, and it doesn’t release thestateLock
until the method exits. Why can’t the implementation be this instead?
void rwlock::acquireAsReader() {
stateLock.lock();
stateCond.wait(stateLock, [this]{ return writeState == Ready; });
stateLock.unlock();
lock_guard<mutex> lgr(readLock);
numReaders++;
}
-
The implementation of
acquireAsWriter
acquires thestateLock
before it does anything else and it releases thestateLock
just before it acquires thereadLock
. Why can’tacquireAsWriter
adopt the same approach asacquireAsReader
and just hold ontostateLock
until the method returns? -
Notice that we have a single
release
method instead ofreleaseAsReader
andreleaseAsWriter
methods. How does the implementation know if the thread acquired therwlock
as a writer instead of a reader (assuming proper use of the class)? -
The implementation of
release
relies onnotify_all
in one place andnotify_one
in another. Why are those the correct versions ofnotify
to call in each case? -
A thread that owns the lock as a reader might want to upgrade its ownership of the lock to that of a writer without releasing the lock first. Besides the fact that it’s a waste of time, what’s the advantage of not releasing the read lock before re-acquiring it as a writer, and how could the implementation of
acquireAsWriter
be updated so it can be called afteracquireAsReader
without an intervening release call?
Problem 2: Event Barriers
An event barrier allows a group of one or more threads—we call them consumers—to efficiently wait
until an event occurs (i.e. the barrier is lift
ed by another thread, called the producer). The barrier is eventually restored by the producer, but only after consumers have detected the event, executed what they could only execute because the barrier was lifted, and notified the producer they’ve done what they need to do and moved past
the barrier. In fact, consumers and producers efficiently block (in lift
and past
, respectively) until all consumers have moved past the barrier. We say an event is in progress while consumers are responding to and moving past it.
The EventBarrier
implements this idea via a constructor and three zero-argument methods called wait
, lift
, and past
. The EventBarrier
requires no external synchronization, and maintains enough internal state to track the number of waiting consumers and whether an event is in progress. If a consumer arrives at the barrier while an event is in progress, wait
returns immediately without blocking.
The following test program (where all oslock
s and osunlock
s have been removed, for brevity) and sample run illustrate how the EventBarrier
works. The backstory for the sample run: singing minstrels approach a castle only to be blocked by a drawbridge gate. The minstrels wait until the gatekeeper lifts the gate, allowing the minstrels to cross. The gatekeeper only lowers the gate after all minstrels have crossed the bridge, and the minstrels only proceed toward the castle once all have crossed the bridge.
static void minstrel(const string& name, EventBarrier& eb) {
cout << oslock << name << " walks toward the drawbridge." << endl << osunlock;
sleep(random() % 3 + 3); // minstrels arrive at drawbridge at different times
cout << oslock << name << " arrives at the drawbridge, must wait." << endl << osunlock;
eb.wait(); // all minstrels wait until drawbridge has been raised
cout << oslock << name << " detects drawbridge lifted, starts crossing." << endl << osunlock;
sleep(random() % 3 + 2); // minstrels walk at different rates
cout << oslock << name << " has crossed the bridge." << endl << osunlock;
eb.past();
cout << oslock << name << " carries on, knowing all others have crossed." << endl << osunlock;
}
static void gatekeeper(EventBarrier& eb) {
sleep(random() % 5 + 7);
cout << oslock << "Gatekeeper raises the drawbridge." << endl << osunlock;
eb.lift(); // lift the drawbridge
cout << oslock << "Gatekeeper lowers drawbridge knowing all have crossed." << endl << osunlock;
}
static string kMinstrelNames[] = {
"Peter", "Paul", "Mary", "Manny", "Moe", "Jack"
};
static const size_t kNumMinstrels = 6;
int main(int argc, char *argv[]) {
EventBarrier drawbridge;
thread minstrels[kNumMinstrels];
for (size_t i = 0; i < kNumMinstrels; i++) {
minstrels[i] = thread(minstrel, kMinstrelNames[i], ref(drawbridge));
}
thread g(gatekeeper, ref(drawbridge));
for (thread& c: minstrels) c.join();
g.join();
return 0;
}
myth52$ ./event-barrier-test
Peter walks toward the drawbridge.
Paul walks toward the drawbridge.
Manny walks toward the drawbridge.
Moe walks toward the drawbridge.
Mary walks toward the drawbridge.
Jack walks toward the drawbridge.
Peter arrives at the drawbridge, must wait.
Paul arrives at the drawbridge, must wait.
Manny arrives at the drawbridge, must wait.
Mary arrives at the drawbridge, must wait.
Jack arrives at the drawbridge, must wait.
Moe arrives at the drawbridge, must wait.
Gatekeeper raises the drawbridge.
Peter detects drawbridge lifted, starts crossing.
Paul detects drawbridge lifted, starts crossing.
Manny detects drawbridge lifted, starts crossing.
Mary detects drawbridge lifted, starts crossing.
Jack detects drawbridge lifted, starts crossing.
Moe detects drawbridge lifted, starts crossing.
Peter has crossed the bridge.
Paul has crossed the bridge.
Manny has crossed the bridge.
Jack has crossed the bridge.
Mary has crossed the bridge.
Moe has crossed the bridge.
Moe carries on, knowing all others have crossed.
Gatekeeper lowers drawbridge knowing all have crossed.
Peter carries on, knowing all others have crossed.
Paul carries on, knowing all others have crossed.
Manny carries on, knowing all others have crossed.
Jack carries on, knowing all others have crossed.
Mary carries on, knowing all others have crossed.
Your lab5
folder includes event-barrier.h
, event-barrier.cc
, and ebtest.cc
, and typing make
should generate an executable called ebtest
that you can run to ensure that the EventBarrier
class you'll flesh out in event-barrier.h
and .cc
are working properly. The one exercise in this lab that has you do any coding is this one, as it expects you complete the implementation stub you've been supplied with.
Icons by Piotr Kwiatkowski