CS 332 s20 — Semaphores and Advanced Locks

Table of Contents

1 Video Lecture

Please watch the video lecture: It contains sections on

  1. semaphores (0:00)
  2. reader-writer locks (15:16)
  3. lock contention (29:05)
  4. MCS locks (34:39)
  5. RCU locks (38:44)

The Panopto viewer has table of contents entries for each slide (https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=73aa6b75-ef25-40cd-b15b-abae010e1237). You can access the lecture slides here.

2 Reading: Semaphores and Reader-Writer Locks

Read OSTEP chapter 31, sections 31.1-31.5 and 31.8 (p. 389-400, p. 404-405) after watching the video sections on semaphores and reader-writer locks. It goes into more detail on applications of semaphores and their implemention. It also provides C code for a simple reader-writer lock.

3 Code

3.1 Reader-Writer Lock

3.1.1 RWLock.h

class RWLock{
  private:
    // Synchronization variables
    Lock lock;
    CV readGo;
    CV writeGo;

    // State variables
    int activeReaders;
    int activeWriters;
    int waitingReaders;
    int waitingWriters;

  public:
    RWLock();
    ~RWLock() {};
    void startRead();
    void doneRead();
    void startWrite();
    void doneWrite();

  private:
    bool readShouldWait();
    bool writeShouldWait();
};

3.1.2 RWLock.cc

// Wait until no active or waiting
// writes, then proceed.
void RWLock::startRead() {
    lock.acquire();
    waitingReaders++;
    while (readShouldWait()) {
        readGo.Wait(&lock);
    }
    waitingReaders--;
    activeReaders++;
    lock.release();
}

// Done reading. If no other active
// reads, a write may proceed.
void RWLock::doneRead() {
    lock.acquire();
    activeReaders--;
    if (activeReaders == 0 
         && waitingWriters > 0) {
        writeGo.signal();
    }
    lock.release();
}

// Read waits if any active or waiting
// write ("writers preferred").
bool 
RWLock::readShouldWait() {
    return (activeWriters > 0 
             || waitingWriters > 0);
}


// Wait until no active read or
// write then proceed.
void RWLock::startWrite() {
    lock.acquire();
    waitingWriters++;
    while (writeShouldWait()) {
        writeGo.Wait(&lock);
    }
    waitingWriters--;
    activeWriters++;
    lock.release();
}

// Done writing. A waiting write or
// read may proceed.
void 
RWLock::doneWrite() {
    lock.acquire();
    activeWriters--;
    assert(activeWriters == 0);
    if (waitingWriters > 0) {
        writeGo.signal();
    } 
    else {
        readGo.broadcast();
    }
    lock.release();
}

// Write waits for active read or write.
bool
RWLock::writeShouldWait() {
    return (activeWriters > 0 
             || activeReaders > 0);
}

3.2 MCS Lock

class MCSLock {
  private:
    Queue *tail = NULL;
}

MCSLock::release() {

    if (compare_and_swap(&tail, 
                    myTCB, NULL)) {

        // If tail == myTCB, no one is 
        // waiting. MCSLock is now free.

    } else { 
        // Someone is waiting.
        while (myTCB->next == NULL)
            ; // spin until next is set 

        // Tell next thread to proceed.
        myTCB->next->needToWait = FALSE;
    }
}

MCSLock::acquire() {
    Queue *oldTail = tail;

    myTCB->next = NULL;
    while (!compare_and_swap(&tail,
                  oldTail, &myTCB)) {

        // Try again if someone else
        // changed tail in the meantime.

        oldTail = tail;
    }

    // If oldTail == NULL, lock acquired.
    if (oldTail != NULL) {
        // Need to wait.
        myTCB->needToWait = TRUE;
        memory_barrier();
        oldTail->next = myTCB;
        while (myTCB->needToWait)
            ; //spin
    }
}

3.3 RCU Lock

An RCU lock implementation as well as a list implementation using it.

3.3.1 RCULock.cc

class RCULock{
  private:
  // Global state
    Spinlock globalSpin;
    long globalCounter;
  // One per processor
    DEFINE_PER_PROCESSOR(
       static long, quiescentCount); 

  // Per-lock state
    Spinlock writerSpin;

  // Public API omitted
}

void RCULock::ReadLock() {
    disableInterrupts();
}

void RCULock::ReadUnlock() {
    enableInterrupts();
}

// Called by scheduler 
void RCULock::QuiescentState(){ 
    memory_barrier();
    PER_PROC_VAR(quiescentCount) =
                    globalCounter;
    memory_barrier();
}

void RCULock::writeLock() {
    writerSpin.acquire();  
}

void RCULock::writeUnlock() {
    writerSpin.release();
}

void RCULock::publish (void **pp1, 
                         void *p2){
    memory_barrier();
    *pp1 = p2;
    memory_barrier();
}

void
RCULock::synchronize() {
    int p, c;

    globalSpin.acquire(); 
    c = ++globalCounter;
    globalSpin.release(); 

    FOREACH_PROCESSOR(p) {
        while((PER_PROC_VAR(
          quiescentCount, p) - c) < 0) {
            // release CPU for 10ms
            sleep(10); 
        }
    }
}

3.3.2 RCUList.h

typedef struct ElementS{
  int key;
  int value;
  struct ElementS *next;
} Element;

class RCUList {
  private:
    RCULock rcuLock;
    Element *head;
  public:
    bool search(int key, int *value);
    void insert(Element *item, value);
    bool remove(int key);
};

3.3.3 RCUList.cc

bool
RCUList::search(int key, int *valuep) {
    bool result = FALSE;
    Element *current;

    rcuLock.readLock();
    current = head;
    for (current = head; current != NULL; 
                current = current->next) {
        if (current->key == key) {
            *valuep = current->value;
            result = TRUE;
            break;
        }
    }
    rcuLock.readUnlock();
    return result;
}
void 
RCUList::insert(int key, 
                   int value) {
    Element *item;

    // One write at a time.
    rcuLock.writeLock();

    // Initialize item.
    item = (Element*)
         malloc(sizeof(Element));
    item->key = key; 
    item->value = value;
    item->next = head;  

    // Atomically update list.
    rcuLock.publish(&head, item); 

    // Allow other writes 
    // to proceed.
    rcuLock.writeUnlock();

    // Wait until no reader 
    // has old version.
    rcuLock.synchronize(); 
}
bool
RCUList::remove(int key) {
    bool found = FALSE;
    Element *prev, *current;

    // One write at a time.
    rcuLock.WriteLock();
    for (prev = NULL, current = head;
            current != NULL; prev = current, 
            current = current->next) {
        if (current->key == key) {
            found = TRUE;

            // Publish update to readers
            if (prev == NULL) {
                rcuLock.publish(&head, 
                          current->next);
            } else {
                rcuLock.publish(&(prev->next), 
                          current->next);
            }
            break;
        }
    }

    // Allow other writes to proceed.
    rcuLock.writeUnlock();

    // Wait until no reader has old version.
    if (found) {
        rcuLock.synchronize();
        free(current);
    }
    return found;
}

4 Homework

  1. Remember that Lab 2 is due 9pm tonight (May 1). Email me if you want to use a late day.
  2. Please fill out an anonymous mid-term evalution. I really want to hear from you about how the course is going.

Have a good midterm break!