Linux内核等待队列详解

等待队列用于管理应等待某个条件成立或者事件发生而防人之心不可无的进程。进程发出的请求暂时无法满足的时候，需要将进程阻塞直到条件成立。内核将因相同原因而阻塞的进程集中在一个队列上，该队列就是等待队列，对于每个需要等待的事件都有一个相应的等待队列。等待队列采用链表的方式来存储，各个阻塞进程作为节点存储在链表中。链表头的类型是wait_queue_head_t，节点类型为wait_queue_t，如下所示：

//linux-3.13/include/linux/wait.h
struct __wait_queue_head {
    spinlock_t      lock;            //自旋锁
    struct list_head    task_list;   //指向队列的链表（成员是wait_queue_t类型）
};
typedef struct __wait_queue_head wait_queue_head_t;

typedef struct __wait_queue wait_queue_t;
struct __wait_queue {
    unsigned int        flags;    //唤醒进程的方式，0表示非互斥方式，1表示互斥方式（一个等待队列中flags标志为1的进程只能一次唤醒一个，即互斥）
#define WQ_FLAG_EXCLUSIVE 0x01
    void            *private;     //指向阻塞进程的task_struct
    wait_queue_func_t   func;     //唤醒函数（根据唤醒方式的不同而执行不同的唤醒操作）
    struct list_head    task_list;   //构成等待队列的双向链表
};

其中默认的唤醒函数wait_queue_func_t是对try_to_wake_up()的简单封装。

等待队列的使用包括两个步骤，等待和唤醒。当进程需要睡眠时，调用wait_event()将自己加入等待队列，让出CPU，比如在向块设备发出请求之后由于数据不能立即返回，所以需要睡眠，此时就调用wait_event()。当事件到达后，则利用wake_up()等函数唤醒等待队列中的进程。wait_event()宏的代码如下：

#define wait_event(wq, condition) \
do {                                    \
    if (condition)                          \
        break;                          \
    __wait_event(wq, condition);                    \
} while (0)

#define __wait_event(wq, condition) \
    (void)___wait_event(wq, condition, TASK_UNINTERRUPTIBLE, 0, 0,  \
                schedule())

#define ___wait_event(wq, condition, state, exclusive, ret, cmd) \
({                                  \
    __label__ __out;                        \
    wait_queue_t __wait;                        \
    long __ret = ret;                       \
                                    \
    INIT_LIST_HEAD(&__wait.task_list);              \
    if (exclusive)                          \
        __wait.flags = WQ_FLAG_EXCLUSIVE;           \
    else                                \
        __wait.flags = 0;                   \
                                    \
    for (;;) {                          \                      //循环等待
        long __int = prepare_to_wait_event(&wq, &__wait, state);\     //初始化__wait变量，并将其加入wq中，然后设置进程的运行状态为TASK_UNINTERRUPTIBLE
                                    \
        if (condition)                      \                  //如果条件满足，则跳出循环，否则继续循环下去
            break;                      \
                                    \
        if (___wait_is_interruptible(state) && __int) {     \
            __ret = __int;                  \
            if (exclusive) {                \
                abort_exclusive_wait(&wq, &__wait,  \
                             state, NULL);  \
                goto __out;             \
            }                       \
            break;                      \
        }                           \
                                    \
        cmd;                            \                       //传入的cmd是schedule()
    }                               \
    finish_wait(&wq, &__wait);                  \               //设置进程的运行状态为TASK_RUNNING，并将进程从等待队列wq中删除
__out:  __ret;                              \
})

从代码中可以看出，只要所等待的条件（condition）不满足应付一直循环等待，直到条件满足后执行finish_wait()。其中condition是传入的参数，例如软盘驱动代码中会有wait_event(command_done, command_status >= 2);。在等待队列上的进程可能因为wake_up()而唤醒，wake_up()将会执行__wake_queue->func()唤醒函数，默认是default_wake_function()，default_wake_function()调用try_to_wake_up()将进程更改为可运行状态并设置待调度标记。wake_up()的代码如下：

//linux-3.13/include/linux/wait.h
#define wake_up(x) __wake_up(x, TASK_NORMAL, 1, NULL)

void __wake_up(wait_queue_head_t *q, unsigned int mode,
            int nr_exclusive, void *key)
{
    unsigned long flags;

    spin_lock_irqsave(&q->lock, flags);
    __wake_up_common(q, mode, nr_exclusive, 0, key);
    spin_unlock_irqrestore(&q->lock, flags);
}

static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
            int nr_exclusive, int wake_flags, void *key)
{
    wait_queue_t *curr, *next;

    //遍历等待队列q
    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;

        //执行wait_queue_t变量中注册的唤醒函数
        if (curr->func(curr, mode, wake_flags, key) &&
                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
            break;
    }
}

等待队列的的使用在驱动代码中会有很多，另外，Java中Object.wait()/notify()方法的实现也与等待队列有关。