How Linux Schedules Processes: Sleep, Wakeup, and Avoiding Invalid Wakeups

Linux Process Sleep and Wakeup

In Linux, a process that is merely waiting for CPU time is in the TASK_RUNNING state and resides on the run‑queue. When its time slice expires, the scheduler removes it from the CPU and selects another runnable process. A process can also voluntarily relinquish the CPU by calling the schedule() function, which puts it to sleep and later resumes execution from the next line after schedule() when it is scheduled again.

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

Linux defines two sleep states:

Interruptible sleep – state flag TASK_INTERRUPTIBLE Uninterruptible sleep – state flag TASK_UNINTERRUPTIBLE Interruptible sleep ends when a hardware interrupt, resource release, or signal occurs. Uninterruptible sleep is similar but ignores signals; it is used when a process must not be awakened until a specific condition is met.

Typical code to put a running task to sleep looks like:

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

Here current is a macro pointing to the current task structure. set_current_state() changes the task’s state from TASK_RUNNING to TASK_INTERRUPTIBLE. When schedule() is invoked, the scheduler selects another TASK_RUNNING process, and the sleeping task is removed from the run‑queue.

To wake a sleeping task, the kernel calls wake_up_process(sleeping_task), which 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 picks it.

Invalid Wakeup Problem

Sometimes a process checks a condition, finds it true, and then goes to sleep anyway. If another process tries to wake it after the condition became true but before the sleeping task actually entered the sleep state, the wake‑up is ineffective, leading to an indefinite sleep – this is the “invalid wakeup” issue.

The root cause is a race condition: the check and the state transition are not atomic. For example, process A checks that a linked list is empty and prepares to sleep, while process B adds an element and calls wake_up_process(). If B runs between A’s check and A’s call to schedule(), A will miss the wake‑up and sleep forever.

Avoiding Invalid Wakeup

The solution is to make the condition check and the transition to sleep an indivisible operation, typically by setting the task state to TASK_INTERRUPTIBLE *before* testing the condition. If the condition is already satisfied, the task immediately restores its state to TASK_RUNNING and skips the sleep.

Rewritten A‑process code demonstrates this approach:

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);
/* Rest of the code ... */
spin_unlock(&list_lock);

By setting the state first, any concurrent wake_up_process() from process B will correctly change the state from TASK_INTERRUPTIBLE to TASK_RUNNING, preventing the task from being erroneously scheduled out.

Kernel Example

The Linux kernel itself follows this pattern. A typical wait‑queue sleep looks like:

/* 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 predicate we are waiting for */
while (!condition) {
    schedule();
    set_current_state(TASK_INTERRUPTIBLE);
}
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

Another real‑world snippet from kernel/sched.c (Linux 2.6) shows a migration thread that sleeps until kthread_should_stop() becomes true:

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

In both cases the task state is set to a sleeping state before the condition is examined, guaranteeing that any wake‑up occurring after the check but before schedule() will be effective.

Conclusion

To prevent invalid wake‑ups in Linux, always set the task’s state to TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE *before* testing the wait condition, and restore it to TASK_RUNNING as soon as the condition is satisfied. This ensures the scheduler never removes a task from the run‑queue prematurely, eliminating the risk of indefinite sleep.