How Linux Processes Sleep, Wake Up, and Avoid Invalid Wakeups

Process States and Scheduling

In Linux a runnable process has the state flag TASK_RUNNING and resides on a run‑queue. When its time slice expires the scheduler preempts it and selects another TASK_RUNNING task. A process can also voluntarily give up the CPU by calling the scheduler function schedule(). After being rescheduled the process continues execution at the instruction following the schedule() call.

Sleep States

Interruptible sleep – state flag TASK_INTERRUPTIBLE Uninterruptible sleep – state flag TASK_UNINTERRUPTIBLE An interruptible sleep ends when a wake‑up condition becomes true (e.g., a hardware interrupt, a released resource, or a delivered signal). An uninterruptible sleep behaves similarly but ignores signals, making it suitable for situations where the task must not be interrupted until a specific event occurs.

Putting a Process to Sleep

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
/* code that runs after the task wakes */

current

is a macro that points to the currently executing task_struct. set_current_state() changes the task’s state from TASK_RUNNING to the requested sleep state. When schedule() is invoked the scheduler removes the task from the run‑queue and may switch to another runnable task.

Waking a Sleeping Process

wake_up_process(sleeping_task);

The wake‑up call sets the task’s state back to TASK_RUNNING and re‑adds it to the run‑queue; the task will actually run the next time the scheduler selects it.

Invalid Wake‑up Race Condition

When a task checks a condition and then goes to sleep, a race can occur if another task wakes it between the condition check and the state change. The classic example involves two tasks, A and B, that share a linked list:

Original A‑process code

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

If task B adds an element to the list and calls wake_up_process() after task A has released the lock but before it has executed set_current_state(), the wake‑up is lost. Task A then goes to sleep even though the list is no longer empty, causing an indefinite block.

Improved A‑process code

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);
/* … */
spin_unlock(&list_lock);

By setting the state to TASK_INTERRUPTIBLE *before* testing the condition, any wake‑up that occurs after the condition check will transition the task to TASK_RUNNING, preventing the lost wake‑up.

Typical Kernel Wait‑Queue Pattern

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

This sequence safely adds the task to a wait queue, puts it to sleep, repeatedly checks the waiting condition, and finally restores the task to TASK_RUNNING before removing it from the queue.

Real‑world Example from kernel/sched.c (Linux 2.6)

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

The migration thread sets its state to TASK_INTERRUPTIBLE before checking kthread_should_stop(). Any wake‑up that occurs while the condition is being evaluated therefore cannot be lost, because the task is already in a sleep state.

Key Takeaway

To avoid invalid wake‑ups in the Linux kernel, set the task’s state to TASK_INTERRUPTIBLE (or TASK_UNINTERRUPTIBLE) *before* evaluating the waiting condition, and reset it to TASK_RUNNING once the condition is satisfied. This ordering guarantees that wake_up_process() always sees a sleeping task and that the wake‑up is effective.