Mutex

Wait queue

Wait queues hold threads that must wait for a particular event before they can continue to run. Wait queues coordinate access to shared data by threads. When a thread tries to acquire any shared resource but finds that it is held by another thread, it is denied access of the resource. The thread that was denied access puts itself in the resource wait queue. When the thread that owns the lock is ready to release the resource, it checks for waiting threads, and, if threads are waiting, it wakes up one or more thread in the wait queue.

The Linux kernel implements wait queue by using a simple data structure containing a list of threads waiting for the resource. When processes are added to the end of a wait queue they can either be interruptible or uninterruptible. Interruptible processes may be interrupted by events such as timers expiring or signals being delivered whilst they are waiting on a wait queue. The waiting process' state will reflect this and either by INTERRUPTIBLE or UNINTERRUPTIBLE. As this process cannot now continue to run, the scheduler is run and, when it selects a new process to run.
 When the wait queue is processed, the state of one or more process in the wait queue is set to RUNNING. The next time the scheduler runs, the processes that are on the wait queue in RUNNING state are now candidates to be run as they are now no longer waiting. When a process from the wait queue is scheduled, the first thing that it will do is remove itself from the wait queue.

Declaration:

In Linux, a wait queue is managed by means of a wait queue head a structure of type wait_queue_head_t, which is defined in <linux/wait.h>. A wait queue head can be defined and initialized statically with:

DECLARE_WAIT_QUEUE_HEAD(name);

or dynamically as follows:

wait_queue_head_t my_wq;

init_waitqueue_head(&my_wq);

Usage:

When a process sleeps, it does so in expectation that some condition will become true in the future. As we noted before, any process that sleeps must check to be sure that the condition it was waiting for is really true when it wakes up again. Linux provides different APIs to put a task in wait queue and to wake up them when desired condition is met. Some frequently used APIs are discussed below.

wait_event(wq, condition)

sleep until a condition gets true

wq: the waitqueue to wait on
condition: a C expression for the event to wait for

The process is put to sleep (TASK_UNINTERRUPTIBLE) until the condition evaluates to true. The condition is checked each time  the waitqueue wq is woken up.
wake_up(wq) has to be called after changing any variable that could change the result of the wait condition.

int wait_event_timeout(wq, condition, timeout)

Sleep until a condition gets true or a timeout elapses

wq: the waitqueue to wait on

condition: a C expression for the event to wait for
timeout: timeout, in jiffies

The process is put to sleep (TASK_UNINTERRUPTIBLE) until the condition evaluates to true. The condition is checked each time the waitqueue wq is woken up.

wake_up() has to be called after changing any variable that could change the result of the wait condition.
The function returns 0 if the timeout elapsed, and the remaining jiffies if the condition evaluated to true before the timeout elapsed.

int wait_event_interruptible(wq, condition)

The process is put to sleep (TASK_INTERRUPTIBLE) until the condition evaluates to true or a signal is received.  The condition is checked each time the wait queue wq is woken up.  wake_up_interruptible(wq) has to be called after changing any variable that could change the result of the wait condition.
The function will return -ERESTARTSYS if it was interrupted by a signal and 0 if condition evaluated to true.

int wait_event_interruptible_timeout(wq, condition, timeout)

The process is put to sleep (TASK_INTERRUPTIBLE) until the condition evaluates to true or a signal is received or wait timer is expired.   The condition is checked each time the wait queue wq is woken up.
wake_up_interruptible() has to be called after changing any variable that could change the result of the wait condition.
The function returns 0 if the timeout elapsed, -ERESTARTSYS if it was interrupted by a signal, and the remaining jiffies otherwise if the condition evaluated to true before the timeout elapsed.
wake_up() wakes up every process in the queue. The exception is if one has TASK_EXCLUSIVE set, in which case the remainder of the queue will not be woken.
There are many more variants of wait_event() and wake_up() available. For more detail refere include/linux/wait.h header file in kernel source.

Previous (Mutex)                                                                                                   Next (Spin Lock)