Linux Process Sleep and Wakeup: Preventing Lost Wakeups with Correct State Ordering

Process States and the Scheduler

In Linux, a process that is only waiting for CPU time is called a ready process and is placed on a run queue with the state flag TASK_RUNNING. When a running process exhausts its time slice, the kernel scheduler deprives it of the CPU and picks another process from the run queue.

A process can also voluntarily relinquish the CPU by calling schedule(). When that process is later scheduled again, it resumes execution at the instruction immediately following the schedule() call.

Sleep States: Interruptible vs. Uninterruptible

When a process must wait for a specific event (device initialization, I/O completion, timer expiry), it is removed from the run queue and placed on a wait queue, entering a sleep state . Linux defines two sleep states: TASK_INTERRUPTIBLE – interruptible sleep. The process sleeps until a condition becomes true: a hardware interrupt occurs, a waited-for resource is released, or a signal is delivered. TASK_UNINTERRUPTIBLE – uninterruptible sleep. Similar to interruptible sleep, but signals cannot wake the process . This state is used when a process must wait without interruption until a specific event occurs.

Entering Sleep and Waking Up

Modern Linux kernels use schedule() to put a process to sleep. The typical sequence is:

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */

current

is a macro pointing to the executing process's task structure. set_current_state() changes the state from TASK_RUNNING to TASK_INTERRUPTIBLE. If schedule() is called by a process in TASK_RUNNING, it simply picks another process. If called by a process already in TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE, the current process is removed from the run queue before another process is scheduled, effectively putting it to sleep.

To wake a sleeping process, the kernel uses: wake_up_process(sleeping_task); This sets the target process's state to TASK_RUNNING and places it on the run queue. The process will actually run the next time the scheduler selects it.

The Lost Wakeup Problem

A lost wakeup (or invalid wakeup ) occurs when a process checks a condition, finds it false, but has not yet set its state to sleep; another process then makes the condition true and calls wake_up_process() on the first process. Because the first process is still TASK_RUNNING, the wakeup has no effect. The first process then sets its state to sleep and calls schedule(), sleeping indefinitely even though the condition is now satisfied.

The article illustrates this with two processes sharing a linked list protected by a spinlock:

Process A (consumer)

spin_lock(&list_lock);
if (list_empty(&list_head)) {
    spin_unlock(&list_lock);
    set_current_state(TASK_INTERRUPTIBLE);
    schedule();
    spin_lock(&list_lock);
}
/* process list */
spin_unlock(&list_lock);

Process B (producer)

spin_lock(&list_lock);
list_add_tail(&list_head, new_node);
spin_unlock(&list_lock);
wake_up_process(processa_task);

If Process A releases the lock (line 3) and is preempted before line 4 ( set_current_state), Process B can acquire the lock, add a node, and call wake_up_process(). Process A is still TASK_RUNNING, so the wakeup is lost. When Process A resumes, it sets its state to TASK_INTERRUPTIBLE and sleeps, missing the data that was just added.

Avoiding Lost Wakeups: Set State Before Checking

The fix is to make the condition check and the state change atomic with respect to wakeups. The correct pattern is:

Set the current state to TASK_INTERRUPTIBLE before checking the condition.

Acquire the lock, check the condition.

If the condition is false, release the lock and call schedule().

When woken, re-acquire the lock and re-check the condition (loop).

If the condition is true, set state back to TASK_RUNNING and proceed.

Corrected Process A

set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if (list_empty(&list_head)) {
    spin_unlock(&list_lock);
    schedule();
    spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* process list */
spin_unlock(&list_lock);

Now, if Process B calls wake_up_process() after Process A has set its state to TASK_INTERRUPTIBLE but before it calls schedule(), the wakeup will change the state back to TASK_RUNNING. When Process A subsequently calls schedule(), the scheduler sees TASK_RUNNING and does not remove it from the run queue, so it continues execution without sleeping.

Linux Kernel Implementation: Wait Queues

The kernel provides a formal wait-queue API that embodies this pattern:

/* q is the wait queue we want to sleep on */
DECLARE_WAITQUEUE(wait, current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE);
/* condition is the event we are waiting for */
while (!condition) {
    schedule();
}
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

Steps: 1. DECLARE_WAITQUEUE() creates a wait-queue entry. 2. add_wait_queue() adds the entry to the queue. 3. State is set to TASK_INTERRUPTIBLE (or TASK_UNINTERRUPTIBLE). 4. A while loop checks the condition; if false, schedule() is called. 5. When the condition becomes true, the loop exits, state is set to TASK_RUNNING, and the entry is removed from the wait queue.

This guarantees that the state is TASK_INTERRUPTIBLE before the condition is evaluated, eliminating the race window.

Real Kernel Example: migration_thread

From /kernel/sched.c (Linux 2.6), the migration thread uses the same pattern:

/* Wait for kthread_stop */
set_current_state(TASK_INTERRUPTIBLE);
while (!kthread_should_stop()) {
    schedule();
    set_current_state(TASK_INTERRUPTIBLE);
}
__set_current_state(TASK_RUNNING);
return 0;

The thread repeatedly checks kthread_should_stop() after setting its state to TASK_INTERRUPTIBLE. If another thread calls kthread_stop() (which wakes this thread) after the state is set but before schedule(), the wakeup will be effective because the state is already interruptible.

Summary

The key to avoiding lost wakeups in Linux is to set the process state to a sleep state ( TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE ) before checking the wait condition . If the condition is already satisfied, immediately reset the state to TASK_RUNNING. This ensures that any concurrent wakeup will either see the process as already sleeping (and wake it) or see it as running (and the subsequent schedule() will not sleep). The kernel's wait-queue API and real-world examples like migration_thread follow this discipline.