等待队列

等待队列

谨以此文纪念过往的岁月。

进程的阻塞以及非阻塞，关于其概念可以参考其他的地方。
在linux中主要使用等待队列来实现阻塞，下面主要看等待队列的实现以及主要使用。

一. 等待队列的实现以及主要函数
1.1 定义
等待队列头成员包括自旋锁和任务链表：
struct __wait_queue_head {
 spinlock_t lock;
 struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
等待队列定义如下：
struct __wait_queue {
 unsigned int flags;
#define WQ_FLAG_EXCLUSIVE 0x01
 void *private;
 wait_queue_func_t func;
 struct list_head task_list;
};
关于上述两个参数成员的使用以及各个成员的含义，下面看。
1.2 初始化
等待队列的初始化包括等待队列头的初始化和等待队列的初始化。
等待队列初始化：
#define __WAITQUEUE_INITIALIZER(name, tsk) {    \
 .private = tsk,      \          --保存进程信息
 .func  = default_wake_function,   \--wake的默认处理函数
 .task_list = { NULL, NULL } }         --任务链表

#define DECLARE_WAITQUEUE(name, tsk)     \
 wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)  --采用宏定义来实现等待队列的初始化。

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) {    \    --等待队列头的初始化
 .lock  = __SPIN_LOCK_UNLOCKED(name.lock),  \        --定义自旋锁为未锁定
 .task_list = { &(name).task_list, &(name).task_list } } --将任务链表指向自己

#define DECLARE_WAIT_QUEUE_HEAD(name) \
 wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

函数init_waitqueue_head其实现的功能与上面的宏定义一致。
void init_waitqueue_head(wait_queue_head_t *q)
{
 spin_lock_init(&q->lock);  --初始化自旋锁
 INIT_LIST_HEAD(&q->task_list); --初始化链表，一般的链表初始化时均会将其前置和后置都指向自己
}
1.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);  --锁定自旋锁
 __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);
}
移除等待队列，其本质即是将等待队列头从等待队列中移除。
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 __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
 list_add(&new->task_list, &head->task_list);
}
上面两个函数都是对链表的操作。
1.4 等待事件
等待事件其实是等待condition满足。
与信号量的等待类似。区分于是否可以中断，是否设定条件不满足时的最长时间。
wait_evet不可以中断，也没有条件不满足时间，这种情况在condition一直不满足的情况下会造成僵尸进程。
#define __wait_event(wq, condition)      \
  schedule();      \             --仅仅是切换，对于中断以及调度时间不管

#define __wait_event_timeout(wq, condition, ret)   \
  ret = schedule_timeout(ret);    \    --对于调度时间溢出的处理
  if (!ret)      \
   break;      \

#define __wait_event_interruptible(wq, condition, ret)   \
  if (!signal_pending(current)) {    \       --对于异常中断的处理
   schedule();     \
   continue;     \
  }       \
  ret = -ERESTARTSYS;     \
  break;       \
以上是三种等待事件的区别。从源码中可以看出三种之间的差异。针对上面的共同点来看，以wait_event为例：
#define __wait_event(wq, condition)      \
do {         \
 DEFINE_WAIT(__wait);      \         --新定义name为__wait的队列
 for (;;) {       \
  prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE); \
  if (condition)      \
   break;      \
  schedule();      \
 }        \
 finish_wait(&wq, &__wait);     \
} while (0)
下面的函数也很好理解
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);
 }
}
以上也是简单的链表处理。
1.5 唤醒队列
下面是几种唤醒队列的宏定义，其最终均为调用__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)

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

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

void __wake_up_common(wait_queue_head_t *q, unsigned int mode,int nr_exclusive, int sync, 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, sync, key) &&(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
   break;
 }
}
唤醒队列上的进程。这个涉及内核进程的切换，这个在以后的进程中再学习。