Synchronization in Linux/Unix Kernel - Part 4 (Reader-Writer Lock)

Till now we saw how we can atomically read-modify-write global variables using special instructions provided by the processor. We also saw the use and implementation of Spin Locks and Semaphores. In this post we will discuss about a new locking mechanism called Reader-Writer Lock.

Consider a case where we have a file shared across various processes with the following constraints.

1. Multiple processes can read the file simultaneously.
2. Only one process can write to the file at a time. No other process should be allowed to read/write the file while one of the process is writing to the file.

We can’t use Spin Lock here as it allows only one process to access the file. Spin Lock can’t distinguish between readers and writers. Also, read/write to file on disk is time consuming operation and spin lock is not suitable here.

Semaphores or Counting Semaphores are also not suitable here as they can’t distinguish between reader and writer.

We need a separate type of lock here called Reader Writer Lock.

It keeps track of number of readers/writers reading/writing to the file. It also keep track of number of readers/writers that are waiting to take the lock.

Reader Write Lock

• If there are only readers it allows all of them to take the lock.
• If a new writer comes it blocks the writer until all readers are done. But, if new readers keep coming and we allow them to take the lock, it will cause writers to starve.
• Similarly, if a writer is active, all new readers and writers will be blocked.

Question is whom to wake up after the writer is done ? Should it wake up another writer or all other readers ? If writers are given preference, readers could starve.

To solve the problem of starvation

• All new readers are blocked if there is any writer already waiting so that we don’t starve writers.
• If a reader releases the lock, it takes no action if some readers are already active. When the last reader releases the lock, it issues wakeup to the waiting writer.
• If a writer realease the lock, it issues wakeup to all the blocked readers. If there are no blocked readers, it issues wakeup to the single blocked writer.

With this scheme we can alternate access to the resource between a writer and bunch of readers.

Implementation of reader writer lock

typedef struct  rwLock {

   spinLock sl;          // spin lock to synchronize access

                         // to following members of lock

                         // by multiple threads.

   int nActive;          // number of active readers.

                         // if -1, a writer is active

   int nReadPending;     // number of blocked readers

   int nWritePending;    // number of blocked writers

   queue readers;        // queue to put blocked readers

   queue writers;        // queue to put blocked writers

} rwLock;

void LockRead (rwLock *lock)

{

   acquire the spin lock  // acquire the spin lock

   lock->nReadPending++;

   if (nWritePending) {   // if any writer already blocked

      add itself to readers wait queue

      release the spin lock

      sleep

      acquire the spin lock

   }

   while (lock->nActive == -1) {  // if any writer already

                                  //acquired the lock

      add itself to reader wait queue

      release the spin lock

      sleep

      acquire the spin lock

   }  

  

   lock->nActive++;

   lock->nReadPending--;

   release the spin lock

}

void LockWrite (rwLock *lock)

{

   spinLock(&lock->sl);     // acquire the spin lock

   lock->nWritePending++;

   while (lock->nActive) {  // any reader/writer active

      add itself to writer queue

      release spin lock

      sleep

      acquire the spin lock

   }

   lock->nWritePending--;

   lock->nActive = -1;

   release the spin lock

}

void UnlockRead (rwLock *lock)

{

   acquire the spin lock

   lock->nActive--;

   if (lock->nActive == 0) {  // no readers/writers active

      issue wakeup to writers

      release spin lock

   } else {

      release the spin lock   // if any reader writer

                              // active, don’t do anything

   }  

}

void UnlockWrite (rwLock *lock)

{

   Acquire the spin lock

   lock->nActive = 0;

  

   if (nReadPending) {       // if any readers blocked

      wake all readers

      release the spin lock

   } else {

      wake the single writer

      release the spin lock

   }

}

Note that  the structure rwLock lock has several members. All these members can be accessed by various processes concurrently. So, to synchronize access to all these members a single spin lock is used. This spin lock should be taken before accessing any member of the rwLock.

Reader Writer lock is used by filesystem code while doing any read/write to a file in a filesystem. The lock is acquired at the start of read/write system call and released as soon as the system call is done. It allows multiple readers to read the file but allows only a single writer to write the file.