Reader/Writer Locks ([Programming with Threads]p. 248 & [UNIX Thread] p. 199)

In many situations, one thread is responsible for updating data accessed (as read only) by several other threads. The primitives documented above allow the correct implementation of such synchronization, but we can do better. We can increase the level of concurrency (i.e. increase the number of threads that are 'schedulable' at a given time) by allowing multiple threads to read the data simultaneously. We need only ensure that no reader thread is 'schedulable' when the writer thread is performing its critical section. The Reader-Writer lock mechanism is provided as a primitive in the UNIX threads Interface.

We will develop the interface for this mechanism using reader.lock(), write.lock() and reader.write.unlock()function
setClass("readWriteLock", representation(                   
                          mtx             = "mutex",	   
                          reader.condVar  = "condVariable" 
                          writer.condVar  = "condVariable" 
                          num.readers     = "integer"	   
                          waiting.writers = "integer"	   
                        ),				   
         prototype=list(mutex(),			   
                        condVariable(),			   
                        condVariable(),			   
                        0, 0				   
       )						   
 )                                                         
This establishes the class which describes a Read Write Lock. We need to be able to determine the number of readers currently accessing the data and the number of writers waiting for access to the data. We use the convention that a value of -1 for the number of readers indicates that there is a thread currently writing to the data. Of course, we need a mutex to protect these variables and the data in question. Also, we need a condition variable to signal the writers and another to signal the readers. These must be independent for this mechanism to work.
read.lock <-
function(rw) {                                             
  lock(rw@mtx)                                          
  while( rw@num.readers < 0 || rw@waiting.writers > 0)   
     wait(rw@reader.condVar,  rw@mtx)                    
   rw@num.readers = rw@num.readers + 1                   
  unlock(rw@mtx)
 return(T)
}  
The read lock function must check to see if there are any writer threads currently accessing, or waiting to access, the data. It determines this from the components in the readWriteLock object passed to this function. Since this object is shared across the threads accessing the data, checking these variables must be enclosed within a critical section protected by the mutex within the readWriteLock object. If the conditon is true (that there are writer threads currently accessing or poised to access the data), this data must give up the lock on the mutex and allow them to finish. It then waits to be notified by the writer thread that it has finished. Then it can compete for the mutex lock again. This is all achieved with the simple while(...) wait loop. When this thread holds the mutex lock it inceases the number of reader threads so that any writer thread will be aware of its activity and unlocks the mutex. Now, no writer thread can modify the data, but other reader threads are not excluded because the mutex lock has been released.
write.lock <-
function(rw) {                                    
  lock(rw@mtx) 			       
   while( rw@num.readers != 0) {	       
     rw@waiting.writers = rw@waiting.writers + 1       
     wait(rw@writer.condVar,  rw@mtx)
     rw@waiting.writers = rw@waiting.writers -1       # invariant within this loop
  }					              # must decrement by 1 so next
                                                      # time around counter doesn't increment
                                                      # erroneously
                                                      # Note that on return from wait,
                                                      # mutex is locked by this thread
                                                      # so incrementing is valid!

  rw@num.readers = -1			       
  unlock(rw@mtx)
 return(T)
}  
The writer.lock is similar to the read.lock but differs in the conditions that must exist before it can proceed. It checks to see that there are no reader threads currently accessing the data and also no writer threads currently activex in the critical section. It waits while this condition is not true using wait() after incrementing the number of waiting writers by 1. This allows a reader thread to yield control to one of these writer threads instead of accessing the data. When it gains control of the mutex lock, it indicates that there is one writer thread currently active in this section (rw@num.readers = -1).
readWriteUnlock <-
function(rw) {

 lock(rw@mtx)
  if(rw@num.readers < 0) 
     rw@num.readers = 0
  else  if( rw@num.readers == 0) { # if == 0, we are in a mess
                                   # as there should be no threads here!
    stop("UnLocking a mutex that you can't have locked!")
   }
  else
     rw@num.readers = rw@num.readers -1

  writers.waiting = (rw@waiting.writers > 0 && rw@num.readers == 0)

  unlock(rw@mtx)

 if(writers.waiting == T) 
    signal(rw@writer.condVar, rw@mtx)
 else
    broadcast(rw@reader.condVar, rw@mtx)

 return(T)
}
This function takes care of decrementing the number of threads of this type (reader or writer) currently active and announces its completion in this critical section to the other interested threads. If this is a reader thread (rw@num.readers > 0), then we decrement the number of reader threads currently active. If this is a writer thread, we change the number of writer threads to 0. Next we determine whether there are any writer threads waiting and it is possible for them to proceed. If this is the case, we arrange to wake one of them using signal. If this is not the case, we announce to other reader threads that they can proceed because we have given up the mutex lock.
Clearly these functions can be extended to produce an equivalent tryLock functions and a destroy method for readWriteLock.


Last modified: Tue Feb 11 17:35:00 1997