Lecture Notes for Concurrent Programming

11 June 2002 - Atomicity and Critical Sections

1. remember

   1. interference and mis-synchronization lead to undesirable results

   2. atomicity and synchronization limit execution traces to desirable results

2. atomicity

   1. atomicity represents indivisible execution - within the concurrent computation

   2. hardware only provides fine-grain atomicity - portability assumptions

   3. coarser-grained atomicity requires programmer effort - sometimes languages help

3. a critical section (region) models atomicity

   1. a fence with two gates around an atomic action

   2. only one computation at a time is allowed in.

   3. four critical section properties

      1. mutual exclusion (mutex) - no sharing begs the atomicity question

      2. deadlock free - one competing process always wins

      3. low delay - non-competing processes don't wait

      4. fairness - every competing process eventually wins

4. implementing atomicity

   1. assume a concurrent computation of two sequential computations SC₁ and SC₂

      while (true) 
        code accessing only locals
        < code accessing locals and globals >
        code accessing only locals
      

   2. general approach - shrink the angle brackets

      1. the smaller the angle brackets, the more concurrency

      2. smaller angle brackets are easier to implement

         while (true) 
           code accessing only locals
           < entry protocol >
           code accessing locals and globals
           < exit protocol >
           code accessing only locals
         

   3. approaches

      1. disjoint variables - not practical; each tries to communicate with the other

      2. weakened assertions - possible but unlikely; must enforce atomicity (but, readers atomicity)

      3. synchronization - begs the question.

      4. that leaves global properties

   4. the mutex (mutual exclusion) global property

      1. the boolean global in_i is true if and only if SC_i is in the critical section

      2. the global mutex property is not (in₁ and in₂)

5. implementing critical sections

   1. first cut

      1. try the obvious - if one sequential computation wants in and the other isn't in, then enter

         1. wait !in_j ; in_i = true

   2. tie breaker (peterson's)

      1. what's wrong with the obvious - interference

         1. while !in_i ; in_j = true

      2. use write-local, read-global variables to avoid interference - violates the global invariant, deadlocks

         1. in_j = true ; while !in_i

      3. deadlock is easy to break - order

         1. last = i ; in_i = true ; < wait !in_j or last = j >

         2. at least once is violated - atomicity required

         3. what does it mean for both to be in the critical section

            1. last = i and last = j - impossible

         4. implement the wait with a while

      4. n-party versions are complicated

   3. ticketing

      1. take a number and wait your turn

         < turn[i] = number ; number++ > // 1
         < wait turn[i] == next >        // 2
         critical section
         < next = next + 1 >             // 3
         

      2. 2 becomes true and stays true - weak fairness

      3. global invariant

         1. next is positive

         2. if CS_i in cr, then turn[i] = next

         3. nonzero turn values are unique

      4. implementation

         1. 2 obeys at most one

         2. 3 is executed atomically (careful!)

         3. 1 is a problem - atomicity hides interference (maintaining uniqueness), multiple critical references (increasing number)

         4. use a second critical section algorithm to implement 1 - peterson's

      5. naturally n-party, but expensive for small values of n

   4. bakery numbering

      1. take a number, wait your turn

         1. take a number larger than all current waiters

         2. wait until your number is smallest among the waiters

   5. global invariant

      1. each waiter's number is unique

      2. the computation in the critical section has the smallest number among the waiters

   6. implementation

      1. need to ignore the non-waiters - low numbers that don't count

         < number[i] = max(number[1..n]) + 1 >              // 1
         in[i] = true
         < for j = 1 to n
             if i != j
               while in[j] and number[i] > number[j] { } >  // 2
         critical section
         in[i] = false
         

      2. these are huge, expensive atomic actions

         1. for 2, numbers added after i are larger than numbers[i] - no interference

         2. for 1, atomicity provides uniqueness

            1. recover uniqueness by breaking ties with the computation id

            2. a more complicated ticket number that can't tie - (number[i], i) > (number[j], j)

This page last modified on 22 June 2002.