Lecture Notes for Concurrent Programming

25 June 2002 - Semaphores

1. abstract entry and exit code

   1. roll-your-own solutions are complex and confusing

   2. better to abstract them into higher-level constructs

   3. this is a scandalously lax area of language design

2. the bowl and stone metaphor

   1. a bowl has a stone in it

   2. a process must take the stone to proceed past the bowl

   3. a process must wait for the stone if the bowl's empty

   4. a stone must return to the bowl from which it came

3. semaphores

   1. an abstract data type representing a bowl with stones

      class semaphore {
      
        public
      
          semaphore(unsigned c) : cnt(c) { }
      
          void p(void) { <wait cnt > 0 ; cnt = 0> }
      
          void v(void) { <cnt = 1> }
      
        private
      
          unsigned cnt
        }
      

   2. v() atomicity is important

   3. p() wake-up behavior varies - one or all; which one

   4. usually implemented in the operating system for efficiency and security

   5. needs a weakly-fair scheduler

4. mutual exclusion and semaphores

   1. use semaphores to implement critical regions around shared-global access

      // Bad - x write conflicts int x = ... co x = ... x ... || x = ... x ... oc

      // Good - no write conflicts int x = ... semaphore x_mutex(1) co x_mutex.lock() x = ... x ... x_mutex.unlock() || x_mutex.lock() x = ... x ... x_mutex.unlock() oc

   2. the traditional terms are mutex for the semaphore, lock for p(), and unlock for v()

   3. mutex granularity - simplicity vs. concurrency

      1. coarsest granularity - one mutex for all globals

      2. finest granularity - one mutex for each global, or even each global component (array elements, record fields)

      3. concurrency is improved with finer granularity

      4. simplicity is improved with coarser granularity

      5. group related globals and a mutex in a struct

         struct disk_controller {
           semaphore mutex(1)
           word command_reg
           word blockno_reg
           word address_reg
           word results_reg
           }
         

5. comments

   1. there are lots of different ways to implement semaphores; understand how yours are implemented.

   2. understand the semaphore type

      1. a binary semaphore satisfies the property cnt <= 1

      2. a counting (or general) semaphore satisfies the property cnt >= 0

         void d() { <wait cnt > 0 ; cnt--> }
         void v() { <cnt++> }
         

      3. binary semaphores provide mutual exclusion and synchronization; counting semaphores manage resources.

      4. they're equally powerful, but have different behaviors - don't use a counting semaphore for mutual exclusion

   3. understand how waiters come off a d() - it varies from implementation to implementation, and it can get funky

      1. one at a time or all at once

      2. if one at a time, in which order - queue or priority

   4. semaphores frequently implement other operations - know what they are

      1. count() - return the number of stones in the bowl; negative numbers indicate the number of waiters.

      2. locked() - return true iff the semaphore is locked

      3. bool try_lock() - lock the semaphore if open

   5. different sequential computations can operate on the same semaphore

      1. it may be meaningless, but it can't (in general) be prohibited

         semaphore s(1)
         
         co
           s.down()
         ||
           s.up()
         oc
         

      2. this is an obvious source of painful errors

      3. it's also a useful technique - split-binary semaphores

   6. don't let the simplicity fool you - semaphores can quickly lead to subtle, difficult errors

This page last modified on 27 June 2002.