Lecture Notes for Concurrent Programming

27 June 2002 - Split Binary Semaphores

1. observe the pattern in produce-consumer syncnronization

   1. the stone appears to figure-eight between the empty and full semaphores

   2. note that "appears to" - it's a convention, not a property

   3. this pattern leads to the split binary semaphores

2. split binary semaphore - a set b_i of binary semaphores

   1. a split binary semaphore has effectively one stone

   2. sum(i = 1 to n ; b_i.cnt) <= 1

   3. a split binary semaphore ringing code provides mutual exclusion

   4. each component binary semaphore can represent a different synchronization condition for the critical region

3. readers-writers synchronization

   1. a common database problem

      1. an infinite sequence of readers and writers use a database

      2. readers don't change the database, writers do

      3. readers don't need exclusive access, writers do

      4. allow maximum performance with timely updates

   2. a simple mutex solution

      semaphore mutex(1)
      
      // reader or writer
      
      mutex.lock()
      // work the database
      mutex.unlock()
      

      1. simple and obviously correct

      2. low performance, depends on unlock semantics

   3. a counting readers solution

      int readers = 0
      semaphore mutex(1)
      
      // reader
      
      <nr++ ; if (nr == 1) mutex.lock()>
      // work the database
      <nr-- ; if (nr == 0) mutex.unlock()>
      
      // writer
      
      mutex.lock()
      // work the database
      mutex.unlock()
      

      1. use a mutex semaphore to implment atomicity

      2. it allows as many readers as possible

      3. starves writers

   4. a split-binary solution

      1. what do you want to do

         1. no writers in and readers waiting - let a reader go

         2. nothing in and writers waiting - let a writer go

         3. nothing in and nothing waiting - nothing

         int nr = 0
         int nw = 0
         int dr = 0
         int dw = 0
         
         semaphore mutex(1)
         semaphore waitingr(0)
         semaphore waitingw(0)
         
         // reader
         
         mutex.lock()
         if (nw > 0)
           dr++
           mutex.unlock()
           waitingr.wait()
         nr++
         pass()
         // work the database
         mutex.lock()
         nr--
         pass()
         
         // writer
         
         mutex.lock()
         if nr > 0 or nw > 0
           dw++
           mutex.unlock()
           waitingw.wait()
         nw++
         pass()
         //work the database
         mutex.lock()
         nw--
         pass()
         
         // pass
         
         if (nw == 0 and dr > 0)
           dr--
           waitingr.signal()
         else if (nr == 0 and nw == 0 and dw > 0)
           dw--
           waitingw.signal()
         else
           mutex.unlock()
         

This page last modified on 2 July 2002.