Lecture Notes for Operating Systems

Concurrency Control Mechanisms, 9 October 2000

1. mediate concurrent access to shared resources

2. general solution: critical regions for mutually exclusive access to shared resources

3. general approach:
   do something, enter critical region;
   do something;
   do something, exit critical region

4. do what on entry and exit?

   1. interrupt play

      1. on entry, increase priority or disable interrupts

      2. on exit, restore priority or interrupts

      3. good - cheap, certain, supported, short critical regions

      4. bad - privileged, easily abused, doesn't fail gracefully, doesn't scale to multiprocessors, long critical regions

   2. simple software lock variables, flags, booleans...

      1. on entry: check flag, wait until true, set false

      2. on exit: set true

      3. good - cheap, quick

      4. bad - it doesn't work; flag a shared variable

   3. token passing

      1. on entry - wait until you get the token, then go

      2. on exit - pass the token on

      3. good - cheap, obviously correct

      4. bad - inefficient, unreliable

   4. correctly implemented software lock variables, flags, booleans; dekker's, peterson's algorithms

      1. on entry - indicate intention, set flag, wait

      2. on exit - clear intention

      3. good - simple, fast

      4. bad - not so simple

   5. hardware supported lock variables, flags, booleans

      1. atomic read-modify-write instructions

      2. test and set - tst reg, addr: copy addr to reg, set addr to 1

      3. on entry - test and set until reg is 0

      4. on exit - set addr to 0

      5. good - cheap, simple, fast, correct

      6. bad - non-portable, test and set can be funky on multiprocessor architectures, and some uniprocessors such as the alpha

   6. semaphores - a binary variable

      1. on entry - down(s): wait until s is 1, then subtract 1 and go

      2. on exit - up(s): if s is 0 add 1

      3. good - simple, intuitive, efficient

      4. bad - unstructured, low-level, non-portable

      5. many semaphore types: binary, split binary, counting

   7. monitors - data abstraction and structuring

      1. encapsulates data, provides access via entries

      2. waiting, condition variables

      3. on entry - call a monitor entry procedure

      4. on exit - return from the monitor entry procedure

      5. good - structured, understandable

      6. bad - subtle (nested monitors), heavyweight

5. message passing - (almost) nothing shared

   1. send and receive

   2. identifying sender and receiver

   3. synchornous or asyncnronous - rendezvous in ada

   4. higher level mechanisms - remote procedure call (rpc)

6. suspending - block or busy-wait

This page last modified on 10 October 2000.