wait queue机制

//Based on linux v3.14 source code
一、概述
等待队列在内核中有很多用途，尤其在中断处理、进程同步及定时。等待队列实现事件上的条件等待；希望等待特定事件的进程把自己放在合适的等待队列，并放弃控制权。

二、相关结构体
1. 等待队列由双向链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头，即wait_queue_head_t结构。
struct __wait_queue_head {
    spinlock_t lock;
    struct list_head task_list; //等待进程链表
};
typedef struct __wait_queue_head wait_queue_head_t;

2. 等待队列链表中的元素，即wait_queue_t结构
等待队列链表中的每个元素代表一个睡眠进程，进程描述符地址存入private字段中。
typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, void *key);

struct __wait_queue {
    unsigned int flags;    //标志
#define WQ_FLAG_EXCLUSIVE 0x01
    void *private;    //进程描述符
    wait_queue_func_t func;    //唤醒函数，缺省为default_wake_function
    struct list_head task_list;    //链接到等待队列链表中
};
typedef struct __wait_queue wait_queue_t;

三、等待队列操作
1. 定义等待队列头
(1)静态定义
#define DECLARE_WAIT_QUEUE_HEAD(name) wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \
    .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
    .task_list = { &(name).task_list, &(name).task_list } }

(2)动态初始化
#define init_waitqueue_head(q) \
    do { \
        static struct lock_class_key __key; \
     \
        __init_waitqueue_head((q), #q, &__key); \
    } while (0)

void __init_waitqueue_head(wait_queue_head_t *q, const char *name, struct lock_class_key *key)
{
    spin_lock_init(&q->lock);
    lockdep_set_class_and_name(&q->lock, key, name);
    INIT_LIST_HEAD(&q->task_list);
}

2. 定义等待队列元素wait_queue_t
(1)静态定义，定义一个名为name的等待队列项，并将当前进程的进程描述符赋值给private，并设置缺省的唤醒函数default_wake_function。
#define DECLARE_WAITQUEUE(name, tsk) \
            wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)

#define __WAITQUEUE_INITIALIZER(name, tsk) { \
    .private = tsk, \
    .func = default_wake_function, \
    .task_list = { NULL, NULL } }

3. 将元素插入等待队列
void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    wait->flags &= ~WQ_FLAG_EXCLUSIVE;
    //上锁，关中断
    spin_lock_irqsave(&q->lock, flags);
    //将等待队列项wait挂入等待队列
    __add_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

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

add_wait_queue()是把一个非互斥进程插入等待队列的第一个位置。
add_wait_queue_exclusive()是把一个互斥进程插入等待队列的最后一个位置。

4. 将元素从等待队列中删除
void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    spin_lock_irqsave(&q->lock, flags);
    __remove_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __remove_wait_queue(wait_queue_head_t *head, wait_queue_t *old)
{
    list_del(&old->task_list);
}

5. 实例 sleep_on_common()函数
static long __sched sleep_on_common(wait_queue_head_t *q, int state, long timeout)
{
    unsigned long flags;
    wait_queue_t wait;

    //初始化进程所在的等待队列项wait
    init_waitqueue_entry(&wait, current);

    //设置进程状态
    __set_current_state(state);

    spin_lock_irqsave(&q->lock, flags);
    //将当前进程所在的等待队列项wait挂入等待队列中
    __add_wait_queue(q, &wait);
    spin_unlock(&q->lock);
    //进行进程调度
    timeout = schedule_timeout(timeout);

    //进程被唤醒
    spin_lock_irq(&q->lock);
    //将该进程进程所在的等待队列项从等待队列中删除
    __remove_wait_queue(q, &wait);
    spin_unlock_irqrestore(&q->lock, flags);

    return timeout;
}

6. 根据等待队列的实现，linux提供了多种休眠、唤醒方式。
(1) 基于sleep_on_common的休眠。当要必须测试条件，当条件不满足时接着睡眠，就不能使用sleep_on类的睡眠。应当使用手工睡眠，或者wait_event类的函数
//sleep_on将进程设置为TASK_UNINTERRUPTIBLE状态，然后插入等待队列
void __sched sleep_on(wait_queue_head_t *q)
{
    sleep_on_common(q, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}

//interruptible_sleep_on将进程设置为TASK_INTERRUPTIBLE状态，然后插入等待队列.因此接受一个信号就能唤醒队列
void __sched interruptible_sleep_on(wait_queue_head_t *q)
{
    sleep_on_common(q, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}

//sleep_on_timeout与sleep_on类似，但是设置了时间间隔，过了间隔会唤醒进程。时间未到会返回剩余时间
long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
{
    return sleep_on_common(q, TASK_UNINTERRUPTIBLE, timeout);
}

//interruptible_sleep_on_timeout与interruptible_sleep_on类似，只是设置了时间间隔
long __sched interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
{
    return sleep_on_common(q, TASK_INTERRUPTIBLE, timeout);
}

(2)手工休眠
1)建立并初始化一个等待队列项
DEFINE_WAIT(my_wait) <==> wait_queue_t my_wait; init_wait(&my_wait);
2)将等待队列项添加到等待队列头中，并设置进程的状态
void prepare_to_wait(wait_queue_head_t *queue, wait_queue_t *wait, int state)
void prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
3)调用schedule()，告诉内核调度别的进程运行
4)schedule返回，完成后续清理工作finish_wait()

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);
}

void 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);
    }
}

(3) wait_event类睡眠，有条件的睡眠，condition是任意一个布尔表达式，在休眠前后多次对condition求值，为真则唤醒
//进程将被置于非中断休眠，只有condition为真进程才退出睡眠
wait_event(queue, condition)
//进程可被信号中断休眠,或者condition为真进程退出睡眠
wait_event_interruptible(queue, condition)
//等待限定时间timeout，或者condition为真退出睡眠
wait_event_timeout(queue, condition, timeout)
//进程可被信号中断休眠,或者等待限定时间timeout，或者condition为真进程退出睡眠
wait_event_interruptible_timeout(queue, condition, timeout)

(4)唤醒进程的基本函数是wake_up
#define wake_up(x) __wake_up(x, TASK_NORMAL, 1, NULL)
#define wake_up_nr(x, nr) __wake_up(x, TASK_NORMAL, nr, NULL)
#define wake_up_all(x) __wake_up(x, TASK_NORMAL, 0, NULL)
#define wake_up_locked(x) __wake_up_locked((x), TASK_NORMAL, 1)
#define wake_up_all_locked(x) __wake_up_locked((x), TASK_NORMAL, 0)

#define wake_up_interruptible(x) __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_interruptible_nr(x, nr) __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_interruptible_all(x) __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)
#define wake_up_interruptible_sync(x) __wake_up_sync((x), TASK_INTERRUPTIBLE, 1)
注意：
<1>所有宏都考虑到处于TASK_INTERRUPTIBLE状态的睡眠进程，如果宏中带有interruptible的，则会也唤醒处于TASK_UNINTERRUPTIBLE状态的睡眠进程.
<2>所有宏都唤醒具有请求状态的非互斥进程。
<3>宏中含有nr的宏，唤醒给定数目的具有请求状态的互斥进程(非互斥进程都被唤醒)。
<4>宏中含有all的宏，唤醒所有具有请求状态的互斥进程(非互斥进程都被唤醒)。
<5>宏中含有sync的宏，检查被唤醒的进程优先级是否高于系统中正在运行进程的优先级，并在必要时调用schedule().
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;

    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;
        //调用唤醒函数，缺省为default_wake_function，调用try_to_wake_up将进程更改为可运行状态并置待调度标志
        if (curr->func(curr, mode, wake_flags, key) && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
            break;
    }
}

try_to_wake_up涉及到进程调度，不在这里深究。