1. 等待隊列數據結構
等待隊列由雙向鏈表實現，其元素包括指向進程描述符的指針。每個等待隊列都有一個等待隊列頭(wait queue head)，等待隊列頭是一個類型為wait_queque_head_t的數據結構：
struct __wait_queue_head {
spinlock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
其中，lock是用來防止並發訪問，task_list字段是等待進程鏈表的頭。
等待隊列鏈表中的元素類型為wait_queue_t,我們可以稱之為等待隊列項：
struct __wait_queue {
unsigned int flags;
#define WQ_FLAG_EXCLUSIVE 0x01
void *private;
wait_queue_func_t func;
struct list_head task_list;
};
typedef struct __wait_queue wait_queue_t;
每一個等待隊列項代表一個睡眠進程，該進程等待某一事件的發生。它的描述符地址通常放在private字段中。Task_list字段中包含的是指針，由這個指針把一個元素鏈接到等待相同事件的進程鏈表中。
等待隊列元素的func字段用來表示等待隊列中睡眠進程應該用什麼方式喚醒(互斥方式和非互斥方式)。
整個等待隊列的結構如下圖所示：
下面看看等待隊列的工作原理。
2. 等待隊列的睡眠過程
使用等待隊列前通常先定義一個等待隊列頭：static wait_queue_head_t wq ,然後調用wait_event_*函數將等待某條件condition的當前進程插入到等待隊列wq中並睡眠，一直等到condition條件滿足後，內核再將睡眠在等待隊列wq上的某一進程或所有進程喚醒。
定義等待隊列頭沒什麼好講的，下面從調用wait_event_*開始分析：
這裡我們舉比較常用的wait_event_interruptible：
/**
* wait_event_interruptible - 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_INTERRUPTIBLE) until the
* @condition evaluates to true or a signal is received.
* 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 will return -ERESTARTSYS if it was interrupted by a
* signal and 0 if @condition evaluated to true.
*/
#define wait_event_interruptible(wq, condition) \
({ \
int __ret = 0; \
if (!(condition)) \
__wait_event_interruptible(wq, condition, __ret); \
__ret; \
})
這裡很簡單，判斷一下condition條件是否滿足，如果不滿足則調用__wait_event_interruptible函數。
#define __wait_event_interruptible(wq, condition, ret) \
do { \
DEFINE_WAIT(__wait); \
\
for (;;) { \
prepare_to_wait(&wq, &__wait, TASK_INTERRUPTIBLE); \
if (condition) \
break; \
if (!signal_pending(current)) { \
schedule(); \
continue; \
} \
ret = -ERESTARTSYS; \
break; \
} \
finish_wait(&wq, &__wait); \
} while (0)
__wait_event_interruptible首先定義了一個wait_queue_t類型的等待隊列項__wait :
#define DEFINE_WAIT(name) \
wait_queue_t name = { \
.private = current, \
.func = autoremove_wake_function, \
.task_list = LIST_HEAD_INIT((name).task_list), \
}
可以發現，這裡__wait的private成員(通常用來存放進程的描述符)已經被初始化為current, 表示該等待隊列項對應為當前進程。func成員為該等待隊列項對應的喚醒函數，該進程被喚醒後會執行它，已經被初始化為默認的autoremove_wake_function函數。
然後在一個for (;;) 循環內調用prepare_to_wait函數：
void fastcall prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
unsigned long flags;
wait->flags &= ~WQ_FLAG_EXCLUSIVE;
spin_lock_irqsave(&q->lock, flags);
if (list_empty(&wait->task_list))
__add_wait_queue(q, wait);
/*
* don't alter the task state if this is just going to
* queue an async wait queue callback
*/
if (is_sync_wait(wait))
set_current_state(state);
spin_unlock_irqrestore(&q->lock, flags);
}
prepare_to_wait做如下兩件事，將先前定義的等待隊列項__wait插入到等待隊列頭wq，然後將當前進程設為TASK_INTERRUPTIBLE狀態。prepare_to_wait執行完後立馬再檢查一下condition有沒有滿足，如果此時碰巧滿足了則不必要在睡眠了。如果還沒有滿足，則准備睡眠。
睡眠是通過調用schedule()函數實現的，由於之前已經將當前進程設置為TASK_INTERRUPTIBLE狀態，因而這裡再執行schedule()進行進程切換的話，之後就永遠不會再調度到該進程運行的，直到該進程被喚醒（即更改為TASK_RUNNING狀態）。
這裡在執行schedule()切換進程前會先判斷一下有沒signal過來，如果有則立即返回ERESTARTSYS。沒有的話則執行schedule()睡眠去了。
for (;;) 循環的作用是讓進程被喚醒後再一次去檢查一下condition是否滿足。主要是為了防止等待隊列上的多個進程被同時喚醒後有可能其他進程已經搶先把資源占有過去造成資源又變為不可用，因此最好再判斷一下。(當然，內核也提供了僅喚醒一個或多個進程（獨占等待進程）的方式，有興趣的可以參考相關資料)
進程被喚醒後最後一步是調用finish_wait(&wq, &__wait)函數進行清理工作。finish_wait將進程的狀態再次設為TASK_RUNNING並從等待隊列中刪除該進程。
void fastcall finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;
__set_current_state(TASK_RUNNING);
if (!list_empty_careful(&wait->task_list)) {
spin_lock_irqsave(&q->lock, flags);
list_del_init(&wait->task_list);
spin_unlock_irqrestore(&q->lock, flags);
}
}
再往後就是返回你先前調用wait_event_interruptible(wq, condition)被阻塞的地方繼續往下執行。
