How does this implementation of semaphore work?

问题:

Merry Xmas!

I'm reading the The Little Book of Semaphores. There is an implementation of semaphores in C in the book that I don't completely understand. See below for code. There is this wakeups variable. The author explains:

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

and

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.

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?

typedef struct {
  int value, wakeups;
  Mutex *mutex;
  Cond *cond;
} Semaphore;

// SEMAPHORE

Semaphore *make_semaphore (int value)
{
  Semaphore *semaphore = check_malloc (sizeof(Semaphore));
  semaphore->value = value;
  semaphore->wakeups = 0;
  semaphore->mutex = make_mutex ();
  semaphore->cond = make_cond ();
  return semaphore;
}

void sem_wait (Semaphore *semaphore)
{
  mutex_lock (semaphore->mutex);
  semaphore->value--;

  if (semaphore->value < 0) {
    do {
      cond_wait (semaphore->cond, semaphore->mutex);
    } while (semaphore->wakeups < 1);
    semaphore->wakeups--;
  }
  mutex_unlock (semaphore->mutex);
}

void sem_signal (Semaphore *semaphore)
{
  mutex_lock (semaphore->mutex);
  semaphore->value++;

  if (semaphore->value <= 0) {
    semaphore->wakeups++;
    cond_signal (semaphore->cond);
  }
  mutex_unlock (semaphore->mutex);
}

回答1:

The wakeups member is not intended to protect the mutex from being acquired by something other than a waiting thread - it's intended to prevent too many threads from being released from the sem_wait() function.

The pthread_cond_signal() function call that cond_signal() wraps has the following statements in its documentation (emphasis added):

The pthread_cond_signal() function shall unblock at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond).

And:

On a multi-processor, it may be impossible for an implementation of pthread_cond_signal() to avoid the unblocking of more than one thread blocked on a condition variable.

So as an example, it's possible that when 3 threads are waiting on the condition, that two (or all three) might be released when the cond_signal() call is made. The wakeups counter ensures that only the appropriate number of threads actually make it out of the sem_wait() function. The other ones will remain in the do/while loop and wait on the condition again.

回答2:

What this property means is that signaling thread should release CPU in behalf of one of waiting threads, if there are any. pthread_cond_signal() guarantees exactly this and for the same reason.

The pthread_cond_signal() function shall unblock at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond).