title: How does this implementation of semaphore work?
body: <p>Merry Xmas!</p>
  
  <p>I'm reading the <a href="http://greenteapress.com/semaphores/" rel="nofollow">The Little Book of Semaphores</a>. There is an implementation of semaphores in C in the book that I don't completely understand. See below for code. There is this <em>wakeups</em> variable. The author explains:</p>
  
  <blockquote>
    <p>wakeups counts the number of pending signals; that is, the number of threads that have been woken but have not yet resumed execution. The reason for wakeups is to make sure that our semaphores have Property 3, described in Section 4.3</p>
  </blockquote>
  
  <p>and</p>
  
  <blockquote>
    <p>Property 3: if there are threads waiting on a semaphore when a thread executes signal, then one of the waiting threads has to be woken.</p>
  </blockquote>
  
  <p>Ok, I think I understand the meaning of the property. One of the waiting threads should get the mutex and not another one (for example the signaling threads.) Correct me if I'm wrong. What I do not understand is how this property is guaranteed with this mechanism. I'd say the property is not guaranteed. It's still possible that a non-waiting process gets the mutex. What am I missing?</p>
  
  <pre><code>typedef struct {
    int value, wakeups;
    Mutex *mutex;
    Cond *cond;
  } Semaphore;
  
  // SEMAPHORE
  
  Semaphore *make_semaphore (int value)
  {
    Semaphore *semaphore = check_malloc (sizeof(Semaphore));
    semaphore-&gt;value = value;
    semaphore-&gt;wakeups = 0;
    semaphore-&gt;mutex = make_mutex ();
    semaphore-&gt;cond = make_cond ();
    return semaphore;
  }
  
  void sem_wait (Semaphore *semaphore)
  {
    mutex_lock (semaphore-&gt;mutex);
    semaphore-&gt;value--;
  
    if (semaphore-&gt;value &lt; 0) {
      do {
        cond_wait (semaphore-&gt;cond, semaphore-&gt;mutex);
      } while (semaphore-&gt;wakeups &lt; 1);
      semaphore-&gt;wakeups--;
    }
    mutex_unlock (semaphore-&gt;mutex);
  }
  
  void sem_signal (Semaphore *semaphore)
  {
    mutex_lock (semaphore-&gt;mutex);
    semaphore-&gt;value++;
  
    if (semaphore-&gt;value &lt;= 0) {
      semaphore-&gt;wakeups++;
      cond_signal (semaphore-&gt;cond);
    }
    mutex_unlock (semaphore-&gt;mutex);
  }
  </code></pre>