分类： LINUX
2010-04-15 12:35:35
0. 摘要
在LINUX系统中，当前执行进程需要获得某个条件不满足而不能继续执行下去时，进程会被标记为一种特殊状态而从调度器中移走，并且进入等待队列进行“休眠”。直到等待的条件满足才会再次从等待队列中移走而继续执行，从而实现同步。本文就是对实现这种等待队列机制原理实现的描述。
当一个进程可能要等待一些事件的发生，如磁盘操作结束、一些系统资源的释放等等。如果一个进程要等待一个事件发生，那么该进程便将自身放入相应的等待队列中进入睡眠，而放弃控制权，直到等待事件发生后才会被内核唤醒继续执行。通俗地说，等待队列就是暂时存放等待某些事件发生的进程链表的集合体。
等待队列头是等待队列的第一项，用来对整个等待队列进行管理和控制。数据结构定义如下：
typedef struct __wait_queue_head wait_queue_head_t;
struct __wait_queue_head
{
spinlock_t lock; /* 多处理器访问的自旋锁 */
struct list_head task_list;/* 通用队列链表指针 */
};
等待队列中的自旋锁lock表明在任意时刻，只能在同一处理器上执行。list_head task_list表明等待队列是一个带头结点的指针队列。
等待队列项是等待队列里面的具体元素，用来表示加到等待队列中的一个元素。
typedef struct __wait_queue wait_queue_t;
struct __wait_queue
{
unsigned int flags; /* 睡眠进程是互斥进程还是非互斥型 */
struct task_struct *task;(
状态描述符的地址 */
wait_queue_func_t func; /* 挂接唤醒函数 */
struct list_head task_list; /*用于将进程链接进等待相同事件发生的
进程链表中*/
};
Flags表明当前睡眠进程在唤醒时候的类型，当取值是WQ_FLAG_EXCLUSIVE表示每次唤醒当前进程后不再唤醒其他进程，否则需要搜索整个队列的其他进程。
Task就是当前进程描述符指针，当唤醒后就执行的进程指针。
Fun就是挂接唤醒回调指针，用以指示唤醒锁必须的相关动作处理。
Task_list这是个通用链表指针，用以描述等待同一事件发生的所有进程链表。
综合wait_queue_head和wait_queue两个数据结构关系如下图：
当某个正在执行的进程需要进行一些可能因为暂时条件不满足，而操作失败的时候（比如从空的缓存区读取数据时候），我们需要调用wait_event,以实现进程的可阻塞式获取的目的。当然如果条件不满足，当前进程便会进入等待相关条件的休眠队列，开始主动让出处理器。当相关的条件满足时候由其他进程发出唤醒动作，由调度器重新调度，从而返回到休眠进程处继续执行。
2.1进程休眠
最新的2.6内核中让进程进入等待独立而休眠的功能的接口有wait_event函数，这是一个宏定义，如下：
#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是针对当前进程进入等待队列前进行相关准备工作。包括记录当前进程描述符（private）和唤醒回调函数（fun），这个fun函数将在2.2唤醒同步中提到。
而prepare_to_wait主要是进行入队列操作，并且用WQ_FLAG_EXCLUSIVE告诉调度器schedule，可以同时唤醒多个同类型的等待进程。代码如下:
prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
wait->flags &= ~WQ_FLAG_EXCLUSIVE; /* 指定当前进程为非互斥式唤醒 */
spin_lock_irqsave(&q->lock, flags);/* 多处理器访问保护 */
if (list_empty(&wait->task_list)) /* 避免重复加入等待队列 */
__add_wait_queue(q, wait);
。。。。
spin_unlock_irqrestore(&q->lock, flags);
}
很明显在wait_event 的for循环中，当条件不满足时候会进入等待队列让出处理器，直到条件condition条件满足，才可以“醒来”继续执行下面的操作。这样正在运行的进程便开始“休息”。那么什么时候，他才会“醒来”呢？这些动做便是函数挂接在队列元素函数指针wait_queue_func_t func完成，那么这个回调函数是如何唤醒当前等待队列中的某个进程呢？
2.2唤醒同步
唤醒是有其他进程在完成某个动作后主动调用wake_up函数。wake_up中调用在进入等待队列前挂接的函数指针func上的函数try_to_wake_up实现（见2.1进程休眠）。先看这个函数代码片段：
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
int nr_exclusive, int sync, void *key)
{
。。。。。。
list_for_each_safe(tmp, next, &q->task_list) { /* 遍历队列每个元素 */
wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
unsigned flags = curr->flags;
/* 如果是互斥式，则唤醒第一个进程后即退出 */
if (curr->func(curr, mode, sync, key) &&
(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
break;
}
}
可见，所谓的唤醒就是遍历整个等待队列里的每个带唤醒的进程指针，然后调用在进入等待队列前挂接在curr->func指针上的函数，这个唤醒后的回调函数可以自己定义，但是通常使用默认的try_to_wake_up即可，这个函数就是把相关等待该事件发生的task指针放入到待调度run_list队列，并将其状态置为TASK_RUNNING等待schedule调度器进行调度。
综合看来，等待休眠wait_event和唤醒wake_up交互方式可以得到下面的流程图：
从上面的分析可以看出完整的“休眠和唤醒”完成需要三个步骤：首先是把等待进程链入等待队列链表。然后主动调用schedul把处理器让出来，当下一次其他进程唤醒时再由调度器调度到原来的位置。最后执行清理工作，也就是把等待队列中已经唤醒的进程指针从等待队列中删除。
3.等待队列与信号量
从上面的等待队列同步机制可以看出，等待队列的等待和唤醒机制与常用的信号量机制有些相似之处。没错，实际上信号量机制是等待队列机制是同步机制在更高层次上的封装和改良，因为信号量的down和up操作在底层实际上就是通过等待队列的同步机制实现。只不过在在使用信号量时，我们通常强调是资源共享，因而把信号量预先设置为0或者1，表示资源可用与否。而使用等待队列则意味着，我们在执行某个操作时，强调某个条件满足与否，从而决定当前进程的“休眠”和“唤醒”状态。
考虑下面一个典型场景：多进程通过同一串口完成读写动作，读写共用一个缓冲区。
由于等待队列会使进程让出处理器进入休眠，必须等待其他进程唤醒才可以继续执行，因此使用时应该注意：
1. 不能在具有原子特性的上下文中（比如自旋锁spin_loc保护的代码）使用等待队列，这是因为原子上下文是对处理器的独占，而不能并发访问,这样就很容易导致我们的进程进入永远休眠而导致死锁。
2. 由于可能多个等待队列里面的不同进程都在等待同一个条件唤醒时，很可能刚刚满足的条件已被其他等待队列里面的进程占用并修改，而当前进程仍旧不满足条件，所以在唤醒之前必须再次判断条件是否满足，这也就是wait_event中唤醒前判断condition的意义所在。
