Lab Sync

In this lab your will implement a priority read/write lock library, building on top of mutexes and condition variables supplied by the POSIX threading library (pthread).

Setup

As with Lab Memory, we will use a different repo for Lab Sync. Please clone the repo via:

$ git clone git@gitlab.oit.duke.edu:os-course/sync.git
Cloning into 'sync'...

You need to run the lab on a Linux system. We recommend you use the Docker image we provided (i.e., same as the xv6 Docker).

You only need to modify rwlock.c and rwlock.h to finish this lab.

To test your solution, please run make test. Each test case (TC) will print out “Passed” or “Failed”.

To submit your solution, please run make gradescope, and submit your submission.zip to Gradescope.

Priority RWLock Semantics

It is helpful to understand basic RW locks both from the course slides and Chapter 31.5 in OSTEP read/write lock. However, in this lab, we’ve changed some of the semantics to support a notion of priority levels for writers. Below, we provide an overview of the semantics with modifications or potentially non-standard choices marked with an asterisk (*):

Any number of readers can acquire the lock at the same time.
Only one thread can acquire the lock as a writer.
(*) Writers should be preferred. This means that when there is a waiting writer, it will always acquire the lock before any waiting reader.
A waiting writer thread will block until all readers release the lock or the active writer releases the lock.
Any waiting reader will block until the active writer releases the lock and there is no waiting writer thread.
(*) There should be three priority levels for writers: high, medium and low. For simplicity, we represent these levels with 0, 1 and 2 (respectively). Writers with higher priority levels will always beat out writers with lower priority levels in acquiring the lock (e.g., a writer with priority 0 will always acquire the lock before writer with priority 1). Writers with the same priority level are equals.

Implement rwlock

We provide the structure of read/write lock and basic functions in ‘rwlock.h’.

    typedef struct {
      pthread_mutex_t     mutex;
      pthread_cond_t      r_cond;
      pthread_cond_t      w_cond[3];
      int                 r_active;
      int                 w_active[3];
      int                 r_wait;
      int                 w_wait[3];
    }rwl;

You will implement five methods that handles the read/write lock behavior.

    void rwl_init(rwl *l);
    void rwl_rlock(rwl *l);
    void rwl_runlock(rwl *l);
    void rwl_wlock(rwl *l, int priority);
    void rwl_wunlock(rwl *l, int priority);

Hints

Use different condition variables for different priority levels, which are already provided in the structure definition.
Always keep track of active/waiting readers and writers.
Feel free to add helper functions or modify the lock struct if you want to, but don’t change the five methods.

Tests

You can test and grade your rwlock library locally by running

$ make test

Alternatively, you can run the testing script which is used on Gradescope by running (assumes you have already run make):

$ python3 grade_lab.py

This script simply runs each test N=100 times to provide a higher probability that non-determinism is not leading to the submission being marked as passing. A correct solution should pass tests deterministically.

How are tests specified?

static struct Step stepsBasicReadWrite[] = {
  //  CLK ID ECLK
  WL0(  0,  0,  0),
  WL0(  1,  1,  2), // Depends on WU0 at Clock 2
  RL (  1,  2,  3), // Depends on WU0 at Clock 3
  WU0(  2,  0),
  WU0(  3,  1),
  RL (  4,  3,  4),
  RU (  5,  2),
  WL0(  6,  0,  8), // Depends on RU at Clock 8
  RL (  7,  2,  9), // Depends on WU0 at Clock 9
  RU (  8,  3),
  WU0(  9,  0),
  RU ( 10,  2)
};

We have some #define macro syntax in the tests.c file to help construct structures while keeping this view simpler for ease of creating / viewing testing logic.

Each line is a step that takes place at a given logical clock timestamp (CLK, first column) for a given tester/thread ID (ID, second column). These steps are what you would imagine given the lab spec: you can issue a write lock/unlock at varying priorities, and you can issue a read lock/unlock. The action at each step is specified on the left, which invokes the corresponding C macro.

For steps that involve a lock action, there is a third variable specified regarding the dependency (ECLK, third column). This relates to when the lock should be acquired based on an unlock action at a later step. For instance, thread 0 takes a write lock (priority 0) at time 0, followed by thread 1 attempting to take the write lock (priority 0) at time 1. Thread 1 will block because the write lock is already held by thread 0. It should block until time 2, at which point thread 0 will unlock.

This should give you enough of an idea for: 1) how to interpret the tests, and 2) how to play around and construct other test cases as you wish.

What do failures look like?

If you are just starting out the project, you should be greeted with the following output from the new python3 grade_lab.py :

student@dfef19880ec0:~/labs$ python3 grade_lab.py
make: Nothing to be done for 'all'.

Test 'BasicRead': Passed

Test 'BasicWrite': Failed
[M] Changing clock to 0
[0] Write Lock (Priority 0)
[M] Changing clock to 1
[1] Write Lock (Priority 0)
[1] ERROR: Acquired lock out of order (clock 1 instead of 2)
Test Failed!

Test 'PriorityWrite': Failed
[M] Changing clock to 0
[1] Write Lock (Priority 1)
[M] Changing clock to 1
[0] Write Lock (Priority 0)
[0] ERROR: Acquired lock out of order (clock 1 instead of 2)
Test Failed!

Test 'BasicReadWrite': Failed
[M] Changing clock to 0
[0] Write Lock (Priority 0)
[M] Changing clock to 1
[1] Write Lock (Priority 0)
[1] ERROR: Acquired lock out of order (clock 1 instead of 2)
Test Failed!

Test 'PriorityReadWrite': Failed
[M] Changing clock to 0
[1] Write Lock (Priority 0)
[M] Changing clock to 1
[0] Write Lock (Priority 0)
[0] ERROR: Acquired lock out of order (clock 1 instead of 2)
Test Failed!

Here, “BasicRead” passes because, even if we do absolutely nothing, it’s fine that all readers enter their critical section at the same time.

However, if we look at “BasicReadWrite”, we can see that there was an out-of-order acquisition of the lock. As we noted in the previous section, thread 1 should need to wait until thread 0 releases its write lock; however, since the initial state of rwlock.c doesn’t do anything, there are overlapping acquires of the write lock which violates our safety property.

In some cases, you may encounter a deadlock being reported (not shown above) when one thread should make progress (i.e., has no dependency) but can’t. This also corresponds to a failure.