Week 5

• UPC Exercises 1.1 through 1.7
• Due: Today, Mon, Sep 26, 11:59pm
  • extension? (I've had a few requests)
• Here's a link: private
• Hints (see these from Week 3)

More practice with interleavings (Adapted from Problem 2.19 from Andrews's MPD text)

mpd-2.19-interleavings.txt

Semaphores

• Introduced by Edsger Dijkstra in the mid-1960s

• Ben-Ari Ch 6
  • slides: PDF
    • begin slide 6.1, p. 111

• Two operations:
  • wait(s)
    • Traditional: P(s)
      • originally: from the Dutch word, passeren (“to pass”)
      • later: prolagen—formed from the Dutch words proberen (“to try”) and verlagen (“to decrease”)
    • Definition:

       < await (s > 0) s = s - 1; > 

  • signal(s)
    • Traditional: V(s)
      • originally: from the Dutch word, vrijgeven (“to release”)
      • later: verhogen (“to increase”)
    • 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

Class exercises

• The Bear and the Honeybees (handout) PDF
  • try to solve with a single binary semaphore
  • (discuss)
  • try using split binary semaphores
    • where for binary semaphores s1 and s2:

        0 <= s1+s2 <= 1 

  • technique: pass the baton