等待队列

from:等待队列


等待队列（wait queue）用于使进程等待某一特定的事件发生而无需频繁的轮询，进程在等待期间睡眠，在某件事发生时由内核自动唤醒。

数据结构


每个等待队列都有一个队列的头，我们可以看看等待队列的代码：

<linux/wait.h>



struct __wait_queue_head {
    spinlock_t lock;
    struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;


因为等待队列也可以在中断的时候修改，在操作队列之前必须获得一个自旋锁，task_list是一个双链表，用于实现双联表最擅长表示的结构，就是队列：

<linux/wait.h>



struct __wait_queue {
    unsigned int flags;
#define WQ_FLAG_EXCLUSIVE   0x01    void *private;
    wait_queue_func_t func;
    struct list_head task_list;
};


我们可以看到链表__wait_queue中的各个字段，其字段意义如下：

字段说明
flags为WQ_FLAG_EXCUSIVE或为0，WQ_FLAG_EXCUSIVE表示等待进程想要被独占地唤醒
private是一个指针，指向等待进程的task_struct实例，这个变量本质上可以指向任意的私有数据
func等待唤醒进程
task_list用作一个链表元素，用于将wait_queue_t实例防止到等待队列中

为了使当前进程在一个等待队列中睡眠，需要调用wait_event函数。进程进入睡眠，将控制权释放给调度器。内核通常会在向块设备发出传输数据的请求后调用这个函数，因为传输不会立即发送，而在此期间又没有其他事情可做，所以进程就可以进入睡眠，将CPU时间交给系统中的其他进程。

在内核中的另一处，例如，来自块设备的数据到达后，必须调用wake_up函数来唤醒等待队列中的睡眠进程。在使用wait_event让进程睡眠后，必须确保在内核的另一块一定有一个对应的wake_up调用，这是必须的，否则睡眠的进程永远无法醒来。

进程睡眠


add_wait_queue函数用于将一个进程增加到等待队列，这个函数必须要获得自旋锁，在获得自旋锁之后，将工作委托给__add_wait_queue。

<linux/wait.h>



static inline void __add_wait_queue(
    wait_queue_head_t *head,
    wait_queue_t *new)
{
    list_add(&new->task_list, &head->task_list);
}


在将新进程统计到等待队列的时候，除了使用list_add函数并没有其他的工作要做，内核还提供了add_wait_queue_exclusive函数，它的工作方式和这个函数相同，但是将进程插入到链表的尾部，并将其设置为WQ_EXCLUSIVE标志。

让进程在等待队列上进入睡眠的另一种方法是prepare_to_wait，在这个函数中还需要进程的状态，代码如下：

<kernel/wait.c>



void
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);
    set_current_state(state);
    // 解锁一个自旋锁    spin_unlock_irqrestore(&q->lock, flags);
}
EXPORT_SYMBOL(prepare_to_wait);


除了将进程休眠添加到队列里中，内核提供了两个标准方法可用于初始化一个动态分配的wait_queue_t实例，分别为init_waitqueue_entry和宏DEFINE_WAIT。

<linux/wait.h>



static inline void init_waitqueue_entry(
    wait_queue_t *q,
    struct task_struct *p)
{
    q->flags = 0;
    q->private = p;
    q->func = default_wake_function;
}


default_wake_function只是一个进行参数转换的前端，然后使用try_to_wake_up函数来唤醒进程。

宏DEFINE_WAIT创建wait_queue_t的静态实例：

<linux/wait.h>



#define DEFINE_WAIT_FUNC(name, function)    wait_queue_t name = {
        .private    = current,
        .func       = function,
        .task_list  = LIST_HEAD_INIT((name).task_list),
    }

#define DEFINE_WAIT(name) \
    DEFINE_WAIT_FUNC(name, autoremove_wake_function)


这里用autoremove_wake_function来唤醒进程，这个函数不仅调用default_waike_function将所述等待队列从等待队列删除。add_wait_queue通常不直接使用，我们更经常使用wait_event，这是一个宏，代码如下：

<linux/wait.h>



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


这个宏等待一个条件，会确认这个条件是否满足，如果条件已经满足，就可以立即停止处理，因为没有什么可以继续等待的了，然后将工作交给__wait_event。

<linux/wait.h>



#define __wait_event(wq, condition)do {
    DEFINE_WAIT(__wait);
    for (;;) {
        prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE);
        if (condition)
            break;
        schedule();
    }
    finish_wait(&wq, &__wait);
} while (0)


使用DEFINE_WAIT建立等待队列的成员之后，这个宏产生一个无限循环。使用prepare_to_wait使进程在等待队列上睡眠。每次进程被唤醒时，内核都会检查指定的条件是否满足，如果条件满足，就退出无线循环，否则将控制权交给调度器，进程再次睡眠。

在条件满足时，finish_wait将进程状态设置回TASK_RUNNING，并从等待队列的链表移除对应项。

除了wait_event之外，内核还定义了其他几个函数，可以将当前进程置于等待队列中，实现等同于sleep_on。

<linux/wait.h>



#define wait_event_interruptible(    wq, condition)
({
    int __ret = 0;
    if (!(condition))
        __wait_event_interruptible(
            wq, condition, __ret
        );
    __ret;
})


wait_event_interruptible使用的进程状态为TASK_INTERRUPTIBLE，因而睡眠进程可以通过接收信号而唤醒。

<linux/wait.h>



#define wait_event_interruptible_timeout(    wq, condition, timeout)
({
    long __ret = timeout;
    if (!(condition))
        __wait_event_interruptible_timeout(
            wq, condition, __ret
        );
    __ret;
})


wait_event_interruptible_timeout让进程睡眠，但可以通过接受信号唤醒，它注册了一个超时限制。

<linux/wait.h>



#define wait_event_timeout(wq, condition, timeout)({
    long __ret = timeout;
    if (!(condition))
        __wait_event_timeout(
            wq, condition, __ret
        );
    __ret;
})


wait_event_timeout等待满足指定的条件，但如果等待时间超过了指定的超时限制，那么就停止，这防止了永远睡眠的情况。

唤醒进程


唤醒进程的过程比较简单，内核定义了一些列的宏用户唤醒进程。

<linux/wait.h>



#define wake_up_poll(x, m)    __wake_up(x, TASK_NORMAL, 1, (void *) (m))

#define wake_up_locked_poll(x, m)    __wake_up_locked_key((x), TASK_NORMAL, (void *) (m))

#define wake_up_interruptible_poll(x, m)    __wake_up(x, TASK_INTERRUPTIBLE, 1, (void *) (m))

#define wake_up_interruptible_sync_poll(x, m)    __wake_up_sync_key((x), TASK_INTERRUPTIBLE, 1, (void *) (m))


在获得了用户保护等待队列首部的锁之后，_wake_up将工作委托给_wake_up_common，代码如下：

<linux/wait.h>



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;
    // 反复扫描链表，直到没有更多需要唤醒的进程    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;

        if (curr->func(curr, mode, wake_flags, key) &&
                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
                /* 检查唤醒进程的数目是否达到了nr_exclusive
                 * 避免所谓的惊群问题
                 * 如果几个进程在等待独占访问某一资源
                 * 那么同时唤醒所有的等进程时没有意义的
                 * 因为除了其中的一个进程之外
                 * 其他的进程都会再次进入睡眠
                 */
            break;
    }
}


q用于选定等待队列，而mode指定进程的状态，用于控制唤醒进程的条件，nr_exclusive表示将要唤醒的设置了WQ_FLAG_EXCLUSIVE标志的进程的数目。从上面的注释可以看出nr_exclusive是非常有用的，这个数字表示检查唤醒进程的数目是否达到了nr_exclusive，从而避免所谓的惊群的问题。

惊群问题是，当需要唤醒进程的时候，不需要将所有等待某一资源的进程全部唤醒，因为即便全部唤醒，也只能有一个进程需要唤醒，而其他的进程都要再次进入睡眠，这是非常浪费资源的，更不要说每次进程唤醒都会出现这样的问题。

但并不是说所有的进程都不能同时被唤醒，如果进程在等待的数据传输结束，那么唤醒等待队列中的所有进程是可行的，因为这几个进程的数据可以同时读取而不会被干扰。


时间：