linux等待队列实现分析

转载http://www.cnblogs.com/zhuyp1015/archive/2012/06/09/2542894.html
在Linux内核中等待队列有很多用途，可用于中断处理、进程同步及定时。我们在这里只说，进程经常必须等待某些事件的发生。等待队列实现了在事件上的条件等待: 希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制全。因此，等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒它们。

等待队列由循环链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头(wait queue head),等待队列头是一个类型为wait_queue_head_t的数据结构

（1）定义等待队列头（相关内容可以在linux/include/wait.h中找到）

等待队列头结构体的定义：

struct __wait_queue_head {

　　spinlock_t  lock;          //自旋锁变量，用于在对等待队列头          

　　struct list_head task_list;  // 指向等待队列的list_head

}; 

typedef struct __wait_queue_head  wait_queue_head_t;

使用等待队列时首先需要定义一个wait_queue_head，这可以通过DECLARE_WAIT_QUEUE_HEAD宏来完成，这是静态定义的方法。该宏会定义一个wait_queue_head，并且初始化结构中的锁以及等待队列。当然，动态初始化的方法也很简单，初始化一下锁及队列就可以了。

#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 } }

将lock赋为unlocked, 将等待队列头指向的等待队列链表指向name,从而将等待队列头和等待队列连起来;

 一般在写程序的时候将DECLARE_WAIT_QUEUE_HEAD分成两步来完成：

声明：

wait_queue_head_t  wait_que;

初始化：

init_waitqueue_head( &wait_que);

 

     Linux中等待队列的实现思想如下图所示，当一个任务需要在某个wait_queue_head上睡眠时，将自己的进程控制块信息封装到wait_queue中，然后挂载到wait_queue的链表中，执行调度睡眠。当某些事件发生后，另一个任务（进程）会唤醒wait_queue_head上的某个或者所有任务，唤醒工作也就是将等待队列中的任务设置为可调度的状态，并且从队列中删除。

 

（2）等待队列中存放的是在执行设备操作时不能获得资源而挂起的进程

定义等待对列：

struct __wait_queue {

　　　  unsigned int flags;  //prepare_to_wait()里有对flags的操作，查看以得出其含义

          #define WQ_FLAG_EXCLUSIVE        0x01 //一个常数,在prepare_to_wait()用于修改flags的值

                                                                                             

          void * private          //通常指向当前任务控制块

          wait_queue_func_t func;    //唤醒阻塞任务的函数 ，决定了唤醒的方式

　　　  struct list_head task_list;    // 阻塞任务链表

};

typedef struct __wait_queue          wait_queue_t;

 //声明一个等待队列并初始化为name

#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 } }

 

//下列两个函数用于对特定的成员进行赋值（当传入不同类型的参数时）；

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;  //使用默认的唤醒函数

}

 

static inline void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)

{

　　q->flags = 0;

　　q->private = NULL;

　　q->func = func;       // 自定义的唤醒函数

}

 

（3）对等待队列进行操作

  

static inline int waitqueue_active(wait_queue_head_t *q)

{

　　return !list_empty(&q->task_list);

}

  判断等待对列头是否为空，当一个进程访问设备而得不到资源时就会被放入等待队列头指向的等待队列中。

static inline void __add_wait_queue(wait_queue_head_t *head,\                                         wait_queue_t *new)  /

{

list_add(&new->task_list, &head->task_list);

}

//增加一个等待队列new到等待队列头head指向的等待队列链表中；

 

static inline void __add_wait_queue_tail(wait_queue_head_t *head, wait_queue_t *new)

{

　　list_add_tail(&new->task_list, &head->task_list);

}

增加一个等待队列到表尾

 

static inline void __remove_wait_queu (wait_queue_head_t *head,  wait_queue_t *old)

{

　　list_del(&old->task_list);

}

 

 

 //wq: 在等待事件的等待队列，condition: 等待的条件

#define __wait_event(wq, condition) \                                                                                 

do {                                                                        \

DEFINE_WAIT(__wait);                \  //定义并初始化一个wait_queue_t结构        

for (;;) {                                                        \

　　prepare_to_wait(&wq, &__wait,TASK_UNINTERRUPTIBLE);        \

　　if (condition)        \  //看wait_queue:wq要等的condition是否满足

　　　　break;                                                \

　　schedule();        \     //condition不成立，放弃cpu重新调度一个task

}                                                                \

finish_wait(&wq, &__wait);                                        \

} while (0)

 上面程序的执行过程：

1．用当前的进程描述块（PCB）初始化一个wait_queue描述的等待任务。

2．在等待队列锁资源的保护下，将等待任务加入等待队列。

3．判断等待条件是否满足，如果满足，那么将等待任务从队列中移出，退出函数。

4．如果条件不满足，那么任务调度，将CPU资源交与其它任务。

5．当睡眠任务被唤醒之后，需要重复（2）、（3）步骤，如果确认条件满足，退出等待事件函数。

 我在一个程序中因为使用使用wait_event_interruptible()遇到了很大的麻烦，原因就是不知道condition在函数中具体起个什么作用，通过分析源码终于搞清楚。（后面会有专门的文章来介绍那个问题。）

 

等待队列编程接口：

wait_event(wq, condition)

这是一个宏，让当前任务处于等待事件状态。输入参数如下：

@wq：等待队列

@conditions：等待条件

 

wait_event_timeout(wq, condition, timeout)

功能与wait_event类似，多了一个超时机制。参数中多了一项超时时间。

 

wait_event_interruptible(wq, condition)

这是一个宏，与前两个宏相比，该宏定义的等待能够被消息唤醒。如果被消息唤醒，那么返回- ERESTARTSYS。输入参数如下：

@wq：等待队列

@condition：等待条件

@rt：返回值

 

wait_event_interruptible_timeout(wq, condition, timeout)

与上一个相比，多了超时机制

 

wake_up(x)

唤醒等待队列中的一个任务

 

wake_up_interruptible(x)

用于唤醒wake_event_interruptible()睡眠的进程

 

wake_up_all(x)

唤醒等待队列中的所有任务

 

Linux将进程状态描述为如下五种：

TASK_RUNNING：可运行状态。处于该状态的进程可以被调度执行而成为当前进程。

TASK_INTERRUPTIBLE：可中断的睡眠状态。处于该状态的进程在所需资源有效时被唤醒，也可以通过信号或定时中断唤醒（因为有signal_pending()函数）。

TASK_UNINTERRUPTIBLE：不可中断的睡眠状态。处于该状态的进程仅当所需资源有效时被唤醒。

TASK_ZOMBIE：僵尸状态。表示进程结束且已释放资源，但其task_struct仍未释放。

TASK_STOPPED：暂停状态。处于该状态的进程通过其他进程的信号才能被唤醒。

通过 前一篇文章 的介绍我们队等待队列有了一个比较具体的认识，本文将来分析一下等待队列是如何睡眠一个进程和如何唤醒一个进程的。

使用等待队列前通常先定义一个等待队列头：static wait_queue_head_t wq ,然后调用wait_event_*函数将等待某条件condition的当前进程插入到等待队列wq中并睡眠，一直等到condition条件满足后，内核再将睡眠在等待队列wq上的某一进程或所有进程唤醒。

这里我们来分析一下唤醒的过程，举比较常用的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_timeout(wq, condition, ret)        \ do {                                                               \

       DEFINE_WAIT(__wait);                                          \

                                                               \ for (;;) {                                            \

              prepare_to_wait(&wq, &__wait, TASK_INTERRUPTIBLE);  \ if (condition)                                         \ break;                                      \ if (!signal_pending(current)) {                         \

                     ret = schedule_timeout(ret);                     \ if (!ret)                               \ break;                               \ continue;                                \

              }                                                \

              ret = -ERESTARTSYS;                             \ break;                                             \

       }                                                       \

       finish_wait(&wq, &__wait);                             \

} while (0) 

 

__wait_event_interruptible首先定义了一个wait_queue_t类型的等待队列项__wait:

 

#define DEFINE_WAIT(name)  DEFINE_WAIT_FUNC(name, autoremove_wake_function) #define DEFINE_WAIT_FUNC(name, function)                           \ wait_queue_t name = {                                    \

              .private = current,                         \

              .func = function,                       \

              .task_list = LIST_HEAD_INIT((name).task_list),    \

       }

 

可以发现，这里__wait的private成员(通常用来存放进程的描述符)已经被初始化为current, 表示该等待队列项对应为当前进程。func成员为该等待队列项对应的唤醒函数，该进程被唤醒后会执行它，已经被初始化为默认的autoremove_wake_function函数。

 

然后在一个for (;;) 循环内调用prepare_to_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);

}

 

 

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 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)被阻塞的地方继续往下执行。

 

3. 等待队列的唤醒过程

 

直到这里我们明白等待队列是如何睡眠的，下面我们分析等待队列的唤醒过程。

使用等待队列有个前提，必须得有人唤醒它，如果没人唤醒它，那么同眠在该等待队列上的所有进程岂不是变成“僵尸进程”了。

对于设备驱动来讲，通常是在中断处理函数内唤醒该设备的等待队列。驱动程序通常会提供一组自己的读写等待队列以实现上层(user level)所需的BLOCK和O_NONBLOCK操作。当设备资源可用时，如果驱动发现有进程睡眠在自己的读写等待队列上便会唤醒该等待队列。

唤醒一个等待队列是通过wake_up_*函数实现的。这里我们举对应的wake_up_interruptible作为例子分析。定义如下：

#define wake_up_interruptible(x) __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)

这里的参数x即要唤醒的等待队列对应的等待队列头。唤醒TASK_INTERRUPTIBLE类型的进程并且默认唤醒该队列上所有非独占等待进程和一个独占等待进程。

__wake_up定义如下：

/**

* __wake_up - wake up threads blocked on a waitqueue.

* @q: the waitqueue

* @mode: which threads

* @nr_exclusive: how many wake-one or wake-many threads to wake up

* @key: is directly passed to the wakeup function */ 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);

}

__wake_up 简单的调用__wake_up_common进行实际唤醒工作。

__wake_up_common定义如下： /* * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just

 * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve

 * number) then we wake all the non-exclusive tasks and one exclusive task.

 *

 * There are circumstances in which we can try to wake a task which has already

 * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns

 * zero in this (rare) case, and we handle it by continuing to scan the queue. */ 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) break;

       }

}

 

__wake_up_common循环遍历等待队列内的所有元素，分别执行其对应的唤醒函数。这里的唤醒函数即先前定义等待队列项DEFINE_WAIT(__wait)时默认初始化的autoremove_wake_function函数。autoremove_wake_function最终会调用try_to_wake_up函数将进程置为TASK_RUNNING状态。这样后面的进程调度便会调度到该进程，从而唤醒该进程继续执行。