Difference between completion variables and semaph

Question

In the linux kernel, semaphores are used to provide mutual exclusion for critical sections of data and Completion variables are used to synchronize between 2 threads waiting on an event. Why not use semaphores for such a synchronization ? Is there any advantage of using a completion variable over a semaphore ?

Answer 1

There are two reasons you might want to use a completion instead of a semaphore. First, multiple threads can wait for a completion, and they can all be released with one call to complete_all(). It's more complex to have a semaphore wake up an unknown number of threads.

Second, if the waiting thread is going to deallocate the synchronization object, there is a race condition if you're using semaphores. That is, the waiter might get woken up and deallocate the object before the waking thread is done with up(). This race doesn't exist for completions. (See Lasse's post.)

Answer 2

Explanation of why completions were originally implemented: http://lkml.indiana.edu/hypermail/linux/kernel/0107.3/0674.html

The basic summary is that we had this (fairly common) way of waiting for certain events by having a locked semaphore on the stack of the waiter, and then having the waiter do a "down()" which caused it to block until the thing it was waiting for did an "up()".

This works fairly well, but it has a really small (and quite unlikely) race on SMP, that is not so much a race of the idea itself, as of the implementation of the semaphores. We could have fixed the semaphores, but there were a few reasons not to:

• the semaphores are optimized (on purpose) for the non-contention case. The "wait for completion" usage has the opposite default case
• the semaphores are quite involved and architecture-specific, exactly
  due to this optimization. Trying to change them is painful as hell.

So instead, I introduced the notion of "wait for completion":

More recent thread about completions vs semaphores http://lkml.org/lkml/2008/4/11/323