Semaphores

0x10. WHAT

0x20. HOW

ALG1. spin semaphore

P(S):
    while (S <= 0)
        ; // busy wait
    S--
 
V(S):
    S++

ALG2. blocking semaphore

P(S):
    acquire(lock)
    S--
    if (S < 0):
        add this thread to queue
        sleep()
    release(lock)
 
V(S):
    acquire(lock)
    S++
    if (S <= 0):
        wakeup one thread from queue
    release(lock)

0xF0. WHY not

CONS

  1. difficult to code
  2. difficult to prove correctness
    1. errors are not reproducible
    2. errors are observed rarely
  3. requires voluntary cooperation
  4. single misuse affect entire system