Why Linux Processes Sleep Wrongly and How to Prevent Invalid Wakeups

1 Linux Process Sleep and Wakeup

In Linux, a process that only waits for CPU time is called a runnable process and is placed on the run‑queue with the state flag TASK_RUNNING. When its time slice expires, the scheduler removes it from the run‑queue and selects another process to run.

A process can also voluntarily give up the CPU by calling the scheduler function schedule(). After being rescheduled, execution resumes at the line following the schedule() call.

When a process must wait for an event (device initialization, I/O completion, timer expiry, etc.), it is removed from the run‑queue and placed on a wait‑queue, entering a sleep state.

2 Invalid Wakeup

Linux defines two sleep states: TASK_INTERRUPTIBLE (interruptible) and TASK_UNINTERRUPTIBLE (uninterruptible). An interruptible sleep can be awakened by a hardware interrupt, resource release, or signal, while an uninterruptible sleep ignores signals and is used only when a process must not be interrupted.

Invalid wakeup occurs when a process checks a condition, finds it false, goes to sleep, but a concurrent wake‑up happens before the process actually changes its state to sleeping, causing the wake‑up to be ignored and the process to sleep indefinitely. This is a classic race‑condition problem.

Example of Invalid Wakeup

Two processes share a list. Process A checks if the list is empty; if it is, it sleeps. Process B adds an element and calls wake_up_process(). If B wakes A before A has set its state to TASK_INTERRUPTIBLE, the wake‑up is lost and A sleeps forever.

// Process A (original buggy version)
spin_lock(&list_lock);
if (list_empty(&list_head)) {
    spin_unlock(&list_lock);
    set_current_state(TASK_INTERRUPTIBLE);
    schedule();
    spin_lock(&list_lock);
}
/* Rest of the code ... */
spin_unlock(&list_lock);

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

3 Avoiding Invalid Wakeup

The key is to make the check‑and‑sleep sequence atomic. Set the process state to sleeping *before* testing the condition, and if the condition becomes true after the check, immediately restore the state to TASK_RUNNING. This eliminates the window where a wake‑up could be missed.

// Process A (fixed version)
set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if (list_empty(&list_head)) {
    spin_unlock(&list_lock);
    set_current_state(TASK_RUNNING); // condition became true, stay runnable
} else {
    // condition still false, go to sleep
    schedule();
    spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);

4 Linux Kernel Example

The kernel itself follows the same pattern. A typical sleep‑wait loop looks like this:

DECLARE_WAITQUEUE(wait, current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE);
while (!condition) {
    schedule();
}
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

In the migration_thread of Linux 2.6, the code avoids invalid wakeups by setting the state to TASK_INTERRUPTIBLE before entering the loop that checks kthread_should_stop():

set_current_state(TASK_INTERRUPTIBLE);
while (!kthread_should_stop()) {
    schedule();
    set_current_state(TASK_INTERRUPTIBLE);
}
__set_current_state(TASK_RUNNING);
return 0;

Conclusion

To prevent invalid wakeups in Linux, always set the process state to TASK_INTERRUPTIBLE (or TASK_UNINTERRUPTIBLE when appropriate) before testing the wait condition, and revert to TASK_RUNNING if the condition is already satisfied. This ensures that a wake‑up request will never be lost, keeping the scheduler behavior correct and the system stable.