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 “Test Passed!” or “Test Failed!”. You need to pass all the test cases.

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 (*):

  1. Any number of readers can acquire the lock at the same time.
  2. Only one thread can acquire the lock as a writer.
  3. (*) Writers should be preferred. This means that when there is a waiting writer, it will always acquire the lock before any waiting reader.
  4. A waiting writer thread will block until all readers release the lock or the active writer releases the lock.
  5. Any waiting reader will block until the active writer releases the lock and there is no waiting writer thread.
  6. (*) 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

  1. Use different condition variables for different priority levels, which are already provided in the structure definition.
  2. Always keep track of active/waiting readers and writers.
  3. 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=20 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.