====== Week 5 ======

~~NOTOC~~


 
===== Programming Assignment 2 =====

  * 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: [[https://www.cs.vassar.edu/~cs377/private/|private]]
  * Hints (see these from [[week3|Week 3]])


===== Class Exercise =====

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

{{mpd-2.19-interleavings.txt|mpd-2.19-interleavings.txt}}



===== Lecture Notes =====

**Semaphores**

  * Introduced by [[https://en.wikipedia.org/wiki/Edsger_W._Dijkstra|Edsger Dijkstra]] in the mid-1960s

  * Ben-Ari Ch 6
    * slides: {{slides.pdf|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: <code text> < await (s > 0) s = s - 1; > </code> 
    * signal(s)
      * Traditional: V(s)
        * originally: from the Dutch word, //vrijgeven// ("to release")
        * later: //verhogen// ("to increase")
      * Definition: <code text> < s = s + 1; > </code> 
  * ''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) {{cs377-bear-honeybees.pdf|PDF}}
    * try to solve with a single binary semaphore
    * (discuss)
    * try using split binary semaphores
      * where for binary semaphores s1 and s2: <code text>
  0 <= s1+s2 <= 1 </code>
    * technique: pass the baton