Lab 5 Solutions

This handout was adapted from Jerry Cain’s Spring 2018 offering.

Getting started

Before starting, go ahead and clone the lab3 folder:

$ git clone /usr/class/cs110/repos/lab5/shared lab5
$ cd lab5
$ make

Problem 1: Read-Write Locks

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:

The leanest implementation I could come up with relies on two mutexes and two condition_variable_anys. 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 usage of condition_variable_any and understand how it works.

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 lifted 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 oslocks and osunlocks have been removed, for brevity) and sample run illustrate how the EventBarrier works:

static void minstrel(const string& name, EventBarrier& eb) {
    cout << name << " walks toward the drawbridge." << endl;
    sleep(random() % 3 + 3); // minstrels arrive at gate at different times
    cout << name << " arrives at the drawbridge gate, must wait." << endl;
    eb.wait(); // all minstrels wait until drawbridge gate is raised
    cout << name << " detects drawbridge gate lifted, starts crossing." << endl;
    sleep(random() % 3 + 2); // minstrels walk at different rates
    cout << name << " has crossed the bridge." << endl;
    eb.past();
}

static void gatekeeper(EventBarrier& eb) {
    sleep(random() % 5 + 7);
    cout << "Gatekeeper raises the drawbridge gate." << endl;
    eb.lift(); // lift the drawbridge
    cout << "Gatekeeper lowers drawbridge gate knowing all have crossed." << endl;
}

static string kMinstrelNames[] = {"Peter", "Paul", "Mary"};
static const size_t kNumMinstrels = 3;
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;
}

$ ./ebtest
Peter walks toward the drawbridge.
Paul walks toward the drawbridge.
Mary walks toward the drawbridge.
Mary arrives at the drawbridge gate, must wait.
Paul arrives at the drawbridge gate, must wait.
Peter arrives at the drawbridge gate, must wait.
Gatekeeper raises the drawbridge.
Paul detects drawbridge gate lifted, starts crossing.
Peter detects drawbridge gate lifted, starts crossing.
Mary detects drawbridge gate lifted, starts crossing.
Paul has crossed the bridge.
Mary has crossed the bridge.
Peter has crossed the bridge.
Gatekeeper lowers drawbridge gate knowing all have crossed.

The backstory for the above sample run: three singing minstrels approach a castle only to be blocked by a drawbridge gate. The three minstrels wait until the gatekeeper lifts the gate, allowing the minstrels to cross. The gatekeeper only lowers the gate after all three minstrels have crossed the bridge, and the three minstrels only proceed toward the castle once all three have cross the bridge.

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.

Here is event-barrier.h:

class EventBarrier {
public:
    EventBarrier();
    void wait();
    void lift();
    void past();

private:
    size_t numWaiting;
    bool occurring;
    std::mutex m;
    std::condition_variable_any cv;
};

Here is the implementation:

EventBarrier::EventBarrier(): numWaiting(0), occurring(false) {}

void EventBarrier::wait() {
    lock_guard<mutex> lg(m);
    numWaiting++;
    cv.wait(m, [this] { return occurring; });
}

void EventBarrier::lift() {
    lock_guard<mutex> lg(m);
    occurring = true;
    cv.notify_all();
    cv.wait(m, [this] { return numWaiting == 0; });
    occurring = false;
}

void EventBarrier::past() {
    lock_guard<mutex> lg(m);
    numWaiting--;
    if (numWaiting > 0) {
        cv.wait(m, [this] { return numWaiting == 0; });
    } else {
        cv.notify_all();
    }
}