wait队列，及函数解析

在内核里面，等待队列是有很多用处的，尤其是在中断处理、进程同步、定时等场合。
有时候，一个进程可能要等待一些事件的发生，如磁盘操作结束、一些系统资源的释放等等。等待队列存放着是暂时资源未得到满足的进程。
如果需求的资源得到满足，就会从等待队列移动到运行队列(linux没有就绪队列)。


它通过一个双链表和把等待tast的头，和等待的进程列表链接起来。从上图可以清晰看到。所以我们知道，如果要实现一个等待队列，首先要有两个部分。队列头和队列项。下面看他们的数据结构。
队列头：
struct __wait_queue_head {
    spinlock_t lock;              //自旋锁
    struct list_head task_list;   //双向链表，有list_head *prev list_head *next
};
typedef struct __wait_queue_head wait_queue_head_t;

队列项：
struct __wait_queue {
    unsigned int flags;          //该标志判断进程是否为互斥进程(0为非互斥进程而1为互斥进程)
#define WQ_FLAG_EXCLUSIVE    0x01
    void *private;               //2.6版本是采用void指针，而以前的版本是struct task_struct * task;
                                 //实际在用的时候，仍然把private赋值为task
    wait_queue_func_t func;      //唤醒函数，一般默认default_wake_function
    struct list_head task_list;
};
typedef struct __wait_queue wait_queue_t;
所以队列头和队列项是通过list_head联系到一起的，list_head是一个双向链表。并且在list.h中对它有着很多的操作。

flag：
互斥进程(exclusive processes)和非互斥进程：

   总是唤醒所有等待该事件的进程并不一定是合适的。比如考虑这样一种情况：如果队列中的多个进程等待的资源是要互斥访问的，一定时间内只允许一个进程去访问的话，这时候，只需要唤醒一个进程就可以了，其他进程继续睡眠。如果唤醒所有的进程，最终也只有一个进程获得该资源，其他进程让需返回睡眠。

   因此，等待队列中的睡眠进程可被划分为互斥、非互斥进程。
   互斥进程：等待的资源是互斥访问的；互斥进程由内核有选择的唤醒，等待队列项的flag字段为1；
   非互斥进程：等待的资源是可多进程同时访问的。非互斥进程在事件发生时，总是被内核唤醒，等待队列元素的flag字段为0。




2.对列头和队列项的初始化：

#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 } }
//声明一个队列头，让他的链表前后都指向自己，这个时候还没有加入任何的链表项。




#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 } }
//这个是初始化一个队列项，设定tast_list链表前后都是空，说明还没有加入到链表里面。
//私有数据private为任务的任务结构。



等待队列的添加和删除：

      add_wait_queue( )
      add_wait_queue_exclusive( )
      add_wait_queue()函数把一个非互斥进程插入等待队列链表的第一个位置；
      在wait.c中：
      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);
          __add_wait_queue(q, wait);
          spin_unlock_irqrestore(&q->lock, flags);
      }
      EXPORT_SYMBOL(add_wait_queue);
      内嵌内核函数__add_wait_queue()，并且使用了所机制对该操作进行互斥保护。
      add_wait_queue_exclusive( )函数把一个互斥进程插入等待队列链表的最后一个位置；
      remove_wait_queue( )函数从等待队列链表中删除一个进程；
      waitqueue_active( )函数检查一个给定的等待队列是否为空。
注：互斥进程全部在队列尾部




下面主要对这4个唤醒队列函数作对比说明：
 155#define wake_up(x)                      __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, NULL)
 156#define wake_up_nr(x, nr)               __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr, NULL)
 157#define wake_up_all(x)                  __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 0, NULL)
 158#define wake_up_interruptible(x)        __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
 
 其中wake_up_interruptible(x)只能唤醒可被信号唤醒的进程。而其他3个函数能唤醒被信号唤醒的进程，也能唤醒不能被信号唤醒的进程。
 
 __wake_up()函数只是定义自旋锁(关闭中断，且保存CPU的状态)，只要实现的函数
 __wake_up_common(q, mode, nr_exclusive, 0, key)定义在：linux/kernel/sched.c
 

 3626/*
3627 * The core wakeup function.  Non-exclusive wakeups (nr_exclusive == 0) just
3628 * wake everything up.  If it's an exclusive wakeup (nr_exclusive == small +ve
3629 * number) then we wake all the non-exclusive tasks and one exclusive task.
3630 *
3631 * There are circumstances in which we can try to wake a task which has already
3632 * started to run but is not in state TASK_RUNNING.  try_to_wake_up() returns
3633 * zero in this (rare) case, and we handle it by continuing to scan the queue.
3634 */
3635static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3636                             int nr_exclusive, int sync, void *key)
3637{
3638        struct list_head *tmp, *next;
3639
3640        list_for_each_safe(tmp, next, &q->task_list) {
3641                wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
3642                unsigned flags = curr->flags;
         //这里的func实际上是唤醒函数，指向
         int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,void*key)
 
           
3644                if (curr->func(curr, mode, sync, key) &&
3645                                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
3646                        break;
3647        }
3648}

参数注释：wait_queue_head_t *q(唤醒的队列的队列头)      unsigned int mode(设置能被信号中断和不能被信号中断)
         int nr_exclusive(传递过来就是上面4个函数的第3个参数)    //如：(156行的nr) 其他则是1或0
         int sync用来禁止被唤醒的进程抢占本地CPU上正在运行的进程。(不能保证是正确的)
         void *key只想wakeup函数的指针


其中最主要就是if判断的代码了。
curr->func(curr, mode, sync, key)唤醒成功返回1；
nr_exclusive=0，唤醒队列的共享该资源所有进程， ！--nr_exclusive永远为0
nr_exclusive不等于0时，首先唤醒所有共享该资源的所有非互斥进程(非互斥进程排在队列前面)，然后根据nr_exclusive的大小，
唤醒nr_exclusive数目的互斥进程(一般nr_exclusive设置为1，所以唤醒一个互斥进程)

注：互斥进程的flags为1，当为互斥进程唤醒时，--nr_exclusive(自减)。当不是互斥进程的时候，flags不会自减。
这有牵连到编译器，如  (a&&--b)当a=0是，编译器直接返回0，而不对后面判断。所以--b并没有执行。




常用的睡眠操作有interruptible_sleep_on和sleep_on，只不过前者将进程的状态从就绪态（TASK_RUNNING）设置为TASK_INTERRUPTIBLE，允许通过发送signal唤醒它（即可中断的睡眠状态）；而后者将进程的状态设置为TASK_UNINTERRUPTIBLE，在这种状态下，不接收任何singal中断。

在当前进程上操作的sleep_on()函数：
void sleep_on(wait_queue_head_t *wq)
    {
        wait_queue_t wait;

        init_waitqueue_entry(&wait, current);          /* 构造当前进程对应的等待队列项 */      
        current->state = TASK_UNINTERRUPTIBLE;         /* 将当前进程的状态从TASK_RUNNING改为TASK_UNINTERRUPTIBLE */    
        wq_write_lock_irqsave(&q->lock,flags);        
        __add_wait_queue(q, &wait);               /* 将等待队列项添加到指定链表中 */
        wq_write_unlock(&q->lock);
         schedule( );                                  /* 进程重新调度，放弃执行权 */      
        wq_write_lock_irq(&q->lock);
         __remove_wait_queue(q, &wait);            /* 本进程被唤醒，重新获得执行权，首要之事是将等待队列项从链表中删除 */
        wq_write_unlock_irqrestore(&q->lock,flags);
    }
   
该函数把当前进程的状态设置为TASK_UNINTERRUPTIBLE，并把它插入到特定的等待队列。然后，它调用调度程序，而调度程序重新开始另一个进程的执行。当睡眠进程被唤醒时，调度程序重新开始执行sleep_on()函数，把该进程队列中删除。

# interruptible_sleep_on()：
interruptible_sleep_on()与sleep_on()函数基本上是一样的，但是interruptible_sleep_on()把当前进程的状态设置为TASK_INTERRUPTIBLE而不是TASK_UNINTERRUPTIBLE，因此，接受一个信号就可以唤醒当前进程；