Lost wakeup problem - how does UNIX deal with it

Question

(I give context for my question first, the question itself is at the bottom where it says QUESTION in bold).

Take two processes A and B. A checks a condition, sees that it isn't satisfied, and goes to sleep/blocks. B satisfies the condition and wakes A up. If everything happens in that order, then we have no problems.

Now if the scheduler goes:

1. A checks condition, it's not satisfied
2. B satisfies condition, wake A up
3. A goes to sleep/blocks

then we lose the wake-up that B performs for A.

I've come across this problem in the context of implementing a blocking semaphore (i.e. one that puts the wait()ing thread to sleep/blocks it instead of letting it spin-wait). Several sources give solutions to this, among them:

Andrew Tanenbaum, Modern Operating Systems, 4th edition, p. 130:

The essence of the problem here is that a wakeup sent to a process that is not (yet) sleeping is lost. If it were not lost, everything would work. A quick fix is to modify the rules to add a wakeup waiting bit to the picture. When a wakeup is sent to a process that is still awake, this bit is set. Later, when the process tries to go to sleep, if the wakeup waiting bit is on, it will be turned off, but the process will stay awake. The wakeup waiting bit is a piggy bank for storing wakeup signals. The consumer clears the wakeup waiting bit in every iteration of the loop.

This article in the Linux journal ("Kernel Korner - Sleeping in the Kernel", Linux Journal #137) mentions something similar:

This code avoids the lost wake-up problem. How? We have changed our current state to TASK_INTERRUPTIBLE, before we test the condition. So, what has changed? The change is that whenever a wake_up_process is called for a process whose state is TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE, and the process has not yet called schedule(), the state of the process is changed back to TASK_RUNNING.

Thus, in the above example, even if a wake-up is delivered by process B at any point after the check for list_empty is made, the state of A automatically is changed to TASK_RUNNING. Hence, the call to schedule() does not put process A to sleep; it merely schedules it out for a while, as discussed earlier. Thus, the wake-up no longer is lost.

As I understand, this basically says "you can mark a process as wanting to go to sleep/block such that a later wakeup can cancel the later sleep/block call".

Finally these lecture notes in the bottom couple paragraphs starting at "The pseudo-code below shows the implementation of such a semaphore, called a blocking semaphore:" gives code for a blocking semaphore and uses an atomic operation "Release_mutex_and_block (csem.mutex);". They claim that:

Please notice that the P()ing process must atomically become unrunnable and release the mutex. This is becuase of the risk of a lost wakeup. Imagine the case where these were two different operations: release_mutex(xsem.mutex) and sleep(). If a context-switch would occur in between the release_mutex() and the sleep(), it would be possible for another process to perform a V() operation and attempt to dequeue_and_wakeup() the first process. Unfortunately, the first process isn't yet asleep, so it missed the wake-up -- instead, when it again runs, it immediately goes to sleep with no one left to wake it up.

Operating systems generally provide this support in the form of a sleep() system call that takes the mutex as a parameter. The kernel can then release the mutex and put the process to sleep in an environment free of interruptions (or otherwise protected).

QUESTION: Do processes in UNIX have some way of marking them as "I'm planning on going to sleep", or a "wakeup waiting bit" as Tanenbaum calls it? Is there a system call sleep(mutex) that atomically releases a mutex and then puts the process to sleep/blocks it?

It's probably somewhat apparent that I'm not familiar with system calls and generally OS internals; if there are any false assumptions apparent in my question or misuses of terminology, I'd be happy to have them pointed out to me.

Answer 1

The classical Unixy solution is to let the "wakeup" signal consist of writing a byte to a pipe that the waiting process will try to read from.

(If the processes don't have a common ancestor that can help setting this up, a named pipe can be used instead).

The waiting process can then use the select() syscall (or one of its more recent redesigned alternatives such as pselect or poll/epoll) to atomically perform "wait until something is ready to read from such-and-such file descriptor". When it wakes up, it will read and discard everything there is to read, and then check what work is ready for it to do.