Week 6

  • Exam next week
    • review session next Mon, Oct 10
    • take-home: Mon
    • hand-in: Wed

Semaphores

  • Two operations:
    • wait(s)
      • Traditional: P(s)
      • Definition:
         < await (s > 0) s = s - 1; > 
    • signal(s)
      • Traditional: V(s)
      • Definition:
         < s = s + 1; > 
  • wait(s) and signal(s) work the same for binary and counting (general) semaphores
    • binary semaphore: value is always either 1 or 0
    • general semaphore: value is nonnegative

Interleavings

  • Formula(number of possible interleavings):
    • # interleavings = $\frac{(nk)!} {(k!)^n}$
    • where n = # processes and k = # instructions / process

Class exercises

  • The Bear and the Honeybees (handout) PDF
    • split binary semaphores
      • where for binary semaphores s1 and s2:
          0 <= s1+s2 <= 1 
    • technique: pass the baton

Semaphores

  • Ben-Ari Ch 6
    • slides: PDF
      • begin slide 105