共享笔记：等待列队的详细解释

俺写的东西，费了3个多小时。


1：等待事件 唤醒进程
情景：
buffer: 全局变量
read (void *caller_buffer) 从buffer中copy数据到caller_buffer
write () 写数据到buffer中
waiters: 等待列队
add_wait_list: 加入等待列队
wake_up_waiters: 唤醒列队上所有等待的进程
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
read 试图把buffer里的内容返回给调用者，一个不好的代码如下：
bad_read:
read (void *caller_buffer)
{
while (!buffer) ;
copy (caller_buffer, buffer);
}
bad_write:
write ()
{
fill (buffer);
}
注释：这里之所以效率不高的原因是，read 一直对buffer进行测试，因为这个时候read实际上是在占用处理器，而如果write这个函数没有得到执行的话，那么实际上read是在作无用功，而在单处理器上确实是如此。

good_read:
read (void *caller_buffer)
{
while (1) {
if (buffer != NULL)
break;
else
add_wait_list (waits); //加入到等待列队中
schedule (); //让出处理器资源，从runqueue队列中移出
}
copy (caller_buffer, buffer);
}
good_write:
write ()
{
fill (buffer);
wake_up_waiters (waiters)；
}
注释：这样的好处是不言自明的，read并不用一直在那里占用着处理器。大家可以好好的想象中断的好处：避免了轮询时的无用功，采用通知机制。而在我们的事例中，通知者就是write，当buffer不为NULL的时候，它就唤醒所有的在waiters上的等待进程，也就是把他们的重新转移到runqueue队列中去，这样进程就可以被重新调度了。需要申明一点的是：如果进程加入到一个没有处理队列中去的话，那这个进程可不知道要睡到何年何月了。


2: 详细解释
从上面的事例中可以看出，有两个比较重要的数据结构，一个等待链表，一个是等待元（暂且称每一个特定的等待为等待元）
等待列表数据类型为：wait_queue_head_t
等待元数据类型为：wait_queue_t
加入到一个列队，首先要创建一个列队，在函数中一般使用这样的方式：
static DECLARE_WAIT_QUEUE_HEAD (wait_queue_name);
这个语句实际上创建了一个名为wait_queue_name的等待列队，该列队可以被其他的函数所引用或者是处理，一般来说等待列队的数据形式为：
struct __wait_queue_head {
spinlock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
当一个等待列队初始化之后，那么就可以在函数中加入一个个待处理的等待了，在函数中一般如如下添加等待
wait_event (wait_queue_name, condition) 例如：wait_event (wq, buffer != NULL)
在这个函数被调用之后，当前的进程就会休眠，直到另外的执行流开始处理这个等待列队，并且当condition为真的时候，那么在wait_event之后的指令就会得到执行，如果condition为假的话，那么进程会一直的休眠下去，直到conditon为真。来看宏wait_event的实现：
#define wait_event(wq, condition)
do {
if (condition)
break;
__wait_event(wq, condition);
} while (0)
可以看到首先进程测试条件是否为真，如果为真，则直接执行wait_event之后的指令，否则的话，就调用宏__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来创建一个等待的元素，该元素会被加入到双向链表的等待列队中去，DEFINE_WAIT:
#define DEFINE_WAIT(name)
wait_queue_t name = {
.private = current,
.func = autoremove_wake_function,
.task_list = LIST_HEAD_INIT((name).task_list),
}

//autoremove_wake_funciton
int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
int ret = default_wake_function(wait, mode, sync, key);

if (ret)
list_del_init(&wait->task_list);
return ret;
}

该宏主要是初始化一个等待元，private中的current代表这当前的task_struct数据类型的指针，主要是为了以后另外的执行流唤醒该进程；func这个主要是处理等待列队的执行流如何唤醒该进程，一般来说autoremove_wake_function就是调用try_to_wake_up（default_wake_function 引用）函数来唤醒进程，同时使用函数list_del_init用来删除该等待元。让我们再次回到__wait_event这个宏去。在完成了定义等待元之后，prepare_to_wait这个函数主要是把已经初始化了的等待元加入到已经初始化好了的等待列队中去，同时设置当前的进程的状态为TASK_UNINTERRUPTIBILE。完成该函数之后，进程作最后的一次检查条件，如果该条件还不成立的话，那么当前进程就以前放弃了处理器资源的使用，于是调用schedule，该函数用来选择一个进程来执行。这里需要仔细注意的就是：因为这个进程的状态是被设置成了TASK_UNINTERRUPTIBLE，所以这个进程一定是不能被信号唤醒，只有通过try_to_wake_up来唤醒，在现面的代码中可以看出，实际上是另外的执行流在处理等待列队的时候，用try_to_wake_up来唤醒该进程，并且把该进程对应的等待元删除掉了，所以该函数还需要重新用prepare_to_wait再次的初始化一个等待元。

一般来说，另外的执行流，需要调用宏wake_up(wait_queue_head_t wq)来唤醒一个等待列队上的所有的进程，该宏的主体为：
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int sync, void *key)
{
struct list_head *tmp, *next;

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;
}
}
__wake_up_common这个函数主要是用list_for_each_safe来处理每一个等待元，然后，用预先在等待元中定义好的func来处理该等待元，从上面我们可以得知，func主要是删除该等待元，同时调用try_to_wake_up这个函数来唤醒进程。首先func调用default_wake_up来唤醒进程，也就是把这个等待元中的current这个任务的状态设置为TASK-RUNNING，同时把该进程转移到runqueue列队中，如果这一切顺利完成的话，那么，try_to_wake_up就会返还1，然后就可以删除该进程对应的等待元了。当一个进程的状态为TASK_RUNNING的时候，那么它就有可能被调用使用处理器资源了。
一切搞定了。

3：应用
下面看应用：
......
void buffer[64];
static DECLARE_WAIT_QUEUE_HEAD (wq)
......

function_add_wait_queue ()
{
......
wait_event (wq, buffer != NULL);
copy_to_user (buffer_user, buffer, 64);
......
}

function_do_wait_queu ()
{
......
strcpy (buffer, buffer_other, 64);
wake_up (wq);
......
}