Mutual exclusion via sleep and wake

Mutual exclusion means that only one task at a time may execute its critical section (code using a shared resource). Busy waiting does this by spinning and wasting CPU. Sleep and wake solves this by putting the waiting task to sleep (blocked state) so it uses no CPU, and waking it when the resource becomes free.

Operation

1. A task wants to enter the critical section and finds the resource locked by another task.
2. Instead of looping, it calls sleep() (block): the kernel moves it to the blocked state, adds it to the resource's wait queue and runs another ready task.
3. When the owner finishes the critical section and releases the resource, it calls wakeup() for the waiting task.
4. The kernel moves the woken task to the ready state; when scheduled, it enters the critical section.

void enter(void)                 /* acquire */
{
    disable_interrupts();
    if (locked) { add_to_wait_queue(me); sleep(); }
    else          locked = 1;
    enable_interrupts();
}
void leave(void)                 /* release */
{
    disable_interrupts();
    if (queue_not_empty()) wakeup(remove_from_queue());
    else                   locked = 0;
    enable_interrupts();
}

Semaphores and mutexes are the standard implementations of sleep/wake.

Advantages: no CPU wasted, fair order through the queue, suits long waits. Problem to avoid: lost wake-up (a wakeup sent before the task goes to sleep is lost), solved by testing and sleeping atomically, as semaphores do. Also priority inversion and deadlock must be considered.