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