一.概述
- 等待队列在Linux中是十分常用的数据结构,等待队列和进程的调度紧密关联在一起，在驱动程序中，使用等待队列来实现进程的阻塞和进程的唤醒，在epoll中也有等待队列的实现,所以我们很有必要来学习一下等待队列
二.等待队列
- 等待队列用于让进程等待某一个特定事件发生而不需要频繁的轮询，进程在等待期间睡眠，在事件发生的时候由内核来进行自动唤醒
每一个等待队列都由一个等待队列头来决定的，其中定义在 <linux/wait.h>之中
struct __wait_queue_head {
spinlock_t lock; //用于互斥访问的自旋锁
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
因为等待队列可以在中断的时候进行修改，所以操作队列之前会给队列加上一个自旋锁,task_list其中是双向队列
- 在下面展示一下队列中的成员
struct __wait_queue {
unsigned int flags; //标志等待进程是不是需要被独占唤醒
void * private; /指向等待队列的进程task_struct
wait_queue_func_t func; // 唤醒函数
struct list_head task_list; 、//函数元素
};
为了让当前进程在一个等待队列中进行睡眠,需要调用wait_event 函数，进程进入睡眠，将控制权释放给调度器，但是在执行了wait_event函数之中，得要有相应的能够达到的地方进行wake_up调用，让进程从沉睡状态中进行唤醒
如何让进程睡眠?
我们可以使用add_wait_queue函数来将一个进程添加到等待队列，该函数在获得必要的自旋锁之后，会执行__add_wait_queue函数
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);
}
将任务插到队列的头部，其中我们还可以使用一下add_wait_queue_exclusive,这个函数会将任务插到队列的尾部，并且将标签进行设置为WQ_EXCLUSIVE
void fastcall add_wait_queue_exclusive(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_tail(q, wait);
spin_unlock_irqrestore(&q->lock, flags);
}
我们也可以同时使用prepare_to_wait.还需要进程的状态
void fastcall
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)) //wait没有在其中
__add_wait_queue(q, wait); //添加到队列之中
/*
* don't alter the task state if this is just going to
* queue an async wait queue callback
*/
if (is_sync_wait(wait))
set_current_state(state); //设置状态
spin_unlock_irqrestore(&q->lock, flags); //解锁
}
EXPORT_SYMBOL(prepare_to_wait);
那么我们应该如何初始化一个等待队列?
//初始化等待分配
void init_waitqueue_head(wait_queue_head_t *q)
{
spin_lock_init(&q->lock); // 获取一个自旋锁
INIT_LIST_HEAD(&q->task_list); // 进行队列的初始化
}
static inline void init_waitqueue_entry(wait_queue_T *q , struct task_struct *p){
q->flags = 0;
q->private = p;
q->func = defalut_wake_function;
｝
我们在这里看一下默认的唤醒函数
int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
void *key)
{
return try_to_wake_up(curr->private, mode, wake_flags);
}
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
unsigned long flags;
int cpu, src_cpu, success = 0;
bool freq_notif_allowed = !(wake_flags & WF_NO_NOTIFIER);
bool check_group = false;
wake_flags &= ~WF_NO_NOTIFIER;
smp_mb__before_spinlock();
raw_spin_lock_irqsave(&p->pi_lock, flags); //关闭本地中断
src_cpu = cpu = task_cpu(p);
//如果当前进程状态不属于可唤醒状态集，则无法唤醒该进程
//wake_up()传递过来的TASK_NORMAL等于(TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE)
if (!(p->state & state))
goto out;
success = 1;
smp_rmb();
if (p->on_rq && ttwu_remote(p, wake_flags)) //当前进程已处于rq运行队列，则无需唤醒
goto stat;
...
ttwu_queue(p, cpu);
stat:
ttwu_stat(p, cpu, wake_flags);
out:
raw_spin_unlock_irqrestore(&p->pi_lock, flags); //恢复本地中断
...
return success;
}
我们也可以使用一个宏来进行wait_queue_t的初始化
#define DEFINE_WAIT(name) \
wait_queue_t name = { \
.private = current, \
.func = autoremove_wake_function, \
.task_list = LIST_HEAD_INIT(name),task_list), \
}
在这里我们使用了autoremove_wake_function 来进行进程的唤醒,还将等待队列成员从等待队列中进行删除
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); //从列表中移除wait
return ret;
}
但是使用的过程中,add_wait_queue 通常是不直接使用的，经常使用的是wait_event
这是一个宏,我们可以将其展开
___wait_event(wq, condition, state, exclusive, ret, cmd){
wait_queue_t __wait;
INIT_LIST_HEAD(&__wait.task_list);
for (;;) {
//当检测进程是否有待处理信号则返回值__int不为0
long __int = prepare_to_wait_event(&wq, &__wait, state);
if (condition) //当满足条件，则跳出循环
break;
//当有待处理信号且进程处于可中断状态(TASK_INTERRUPTIBLE或TASK_KILLABLE))，则跳出循环
if (___wait_is_interruptible(state) && __int) {
__ret = __int;
break;
}
cmd; //schedule()，进入睡眠，从进程就绪队列选择一个高优先级进程来代替当前进程运行
}
finish_wait(&wq, &__wait); //如果__wait还位于队列wq，则将__wait从wq中移除
}
除此之外，内核还定义了其他的几个函数，可以将当前进程放置于等待队列中
#define wait_event_interruptible(wq,condition)
#define wait_event_timeout(wq,condition,timeout) {…}
#define wait_event_interruptible_timeout(wq,condition,timeout)
wait_event_interruptible 使用的进程状态为task_interruptible,因而睡眠程序可以通过接受信号而被唤醒
wait_event_timeout 等待满足指定条件，等待时间超过了指定的超时限制而停止，防止进程永久沉睡
wait_event_interruptible_timeout 让进程睡眠，但可以通过接受信号来进行唤醒，注册一个超时的时间
唤醒进程，可用于唤醒等待队列的进程，它们基于同一个函数
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);
}
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;
}
//q用于选定等待队列，mode指定进程的状态，用于控制唤醒进程的条件 nr_exclusive
//表示将要唤醒的设置了WQ_FLAG_EXCLUSIVE标志的进程的数据
}
在这里会反复的扫描链表，直到没有更多的进程需要唤醒，或者已经唤醒的独占进程的数目达到了nr_exclusive.该限制用于避免所谓的惊群问题.如果几个进程在等待独占访问的某一个资源，那么同时唤醒所有等待进程应该是毫无意义的，除了其中一个，其他进程都会再次睡眠