写在前面:等待队列是linux内核中一种重要的机制,常见于各种内核或者驱动代码中,由于常见常忘,特写一个博客记录于此
参考博客:https://www.cnblogs.com/hueyxu/p/13745029.html
参考书籍:<深入Linux设备驱动程序内核机制>
1.Linux等待队列概述
以进程阻塞和唤醒的过程为例,等待队列的使用场景可以简述为:
进程 A 因等待某些资源(依赖进程 B 的某些操作)而不得不进入阻塞状态,便将当前进程加入到等待队列 Q 中。进程 B 在一系列操作后,可通知进程 A 所需资源已到位,便调用唤醒函数 wake up 来唤醒等待队列Q上的进程,注意此时所有等待在队列 Q 上的进程均被置为可运行状态。
2.等待队列头和等待队列节点
等待队列以循环链表为基础结构,链表头和链表项分别为等待队列头和等待队列节点,分别用结构体wait_queue_head_t 和 wait_queue_entry_t 描述(定义在./include/linux/wait.h)
2.1.基本概念
等待队列头:
struct wait_queue_head {
spinlock_t lock;
struct list_head head;
};
typedef struct wait_queue_head wait_queue_head_t;
等待队列节点:
typedef int (*wait_queue_func_t)(struct wait_queue_entry *wq_entry, unsigned mode, int flags, void *key);
int default_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int flags, void *key);
/* wait_queue_entry::flags */
#define WQ_FLAG_EXCLUSIVE 0x01
#define WQ_FLAG_WOKEN 0x02
#define WQ_FLAG_BOOKMARK 0x04
/*
* A single wait-queue entry structure:
*/
struct wait_queue_entry {
unsigned int flags; /* 标识节点状态与属性 */
void *private; /* 用于指向关联进程task_struct 结构体的指针 */
wait_queue_func_t func; /* 函数指针,用于指向等待队列被唤醒时的回调的唤醒函数 */
struct list_head entry; /* 链表项 */
};
typedef struct wait_queue_entry wait_queue_entry_t;
从以上可以看出:等待队列头:wait_queue_head_t(struct wait_queue_head)包含lock和head两个成员
等待队列节点:wait_queue_entry_t(struct wait_queue_entry)包含flags/private/func/entry四个成员
这里着重介绍一下等待队列节点中的WQ_FLAG_EXCLUSIVE:
上述场景中看到,当某进程调用 wake up 函数唤醒等待队列时,队列上所有的进程均被唤醒,在某些场合会出现唤醒的所有进程中,只有某个进程获得了期望的资源,而其他进程由于资源被占用不得不再次进入休眠。如果等待队列中进程数量庞大时,该行为将影响系统性能。
内核增加了"独占等待”(WQ_FLAG_EXCLUSIVE)来解决此类问题。一个独占等待的行为和通常的休眠类似,但有如下两个重要的不同:
- 等待队列节点设置 WQ_FLAG_EXCLUSIVE 标志时,会被添加到等待队列的尾部,而非头部。
- 在某等待队列上调用 wake up 时,执行独占等待的进程每次只会唤醒其中第一个(所有非独占等待进程仍会被同时唤醒)。
2.2.等待队列头的创建和初始化
等待队列头的定义和初始化有两种方式:init_waitqueue_head(&wq_head) 和宏定义 DECLARE_WAIT_QUEUE_HEAD(name)/DECLARE_WAIT_QUEUE_HEAD_ON_STACK(name)
./include/linux/wait.h与./kernel/sched/wait.c
extern void __init_waitqueue_head(struct wait_queue_head *wq_head, const char *name, struct lock_class_key *);
#define init_waitqueue_head(wq_head) \
do { \
static struct lock_class_key __key; \
\
__init_waitqueue_head((wq_head), #wq_head, &__key); \
} while (0)
./include/linux/wait.h
#define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
.head = { &(name).head, &(name).head } }
#define DECLARE_WAIT_QUEUE_HEAD(name) \
struct wait_queue_head name = __WAIT_QUEUE_HEAD_INITIALIZER(name)
#ifdef CONFIG_LOCKDEP
#define __WAIT_QUEUE_HEAD_INIT_ONSTACK(name) \
({ init_waitqueue_head(&name); name; })
#define DECLARE_WAIT_QUEUE_HEAD_ONSTACK(name) \
struct wait_queue_head name = __WAIT_QUEUE_HEAD_INIT_ONSTACK(name)
#else
#define DECLARE_WAIT_QUEUE_HEAD_ONSTACK(name) DECLARE_WAIT_QUEUE_HEAD(name)
#endif
2.3.等待队列节点的创建和初始化
创建等待队列节点较为普遍的一种方式是调用宏定义 DECLARE_WAITQUEUE(name, task) ,将定义一个名为 name 的等待队列节点, private 数据指向给定的关联进程结构体 task ,唤醒函数为 default_wake_function() 。
./include/linux/wait.h
#define __WAITQUEUE_INITIALIZER(name, tsk) { \
.private = tsk, \
.func = default_wake_function, \
.entry = { NULL, NULL } }
#define DECLARE_WAITQUEUE(name, tsk) \
struct wait_queue_entry name = __WAITQUEUE_INITIALIZER(name, tsk)
内核源码中还存在其他定义等待队列节点的方式,调用宏定义 DEFINE_WAIT(name) 和 init_wait(&wait_queue) 。
这两种方式都将当前进程(current)关联到所定义的等待队列上,唤醒函数为 autoremove_wake_function() ,注意此函数与上述宏定义方式时不同(上述定义中使用 default_wake_function() )。
下文也将介绍 DEFINE_WAIT() 和 DECLARE_WAITQUEUE() 在使用场合上的不同
./include/linux/wait.h
#define DEFINE_WAIT_FUNC(name, function) \
struct wait_queue_entry name = { \
.private = current, \
.func = function, \
.entry = LIST_HEAD_INIT((name).entry), \
}
#define DEFINE_WAIT(name) DEFINE_WAIT_FUNC(name, autoremove_wake_function)
#define init_wait(wait) \
do { \
(wait)->private = current; \
(wait)->func = autoremove_wake_function; \
INIT_LIST_HEAD(&(wait)->entry); \
(wait)->flags = 0; \
} while (0)
2.4.添加和移除等待队列
内核提供了两个函数(定义在 ./kernel/sched/wait.c )用于将等待队列节点 wq_entry 添加到等待队列 wq_head 中: add_wait_queue() 和 add_wait_queue_exclusive() 。
- add_wait_queue() :在等待队列头部添加普通的等待队列元素(非独占等待,清除 WQ_FLAG_EXCLUSIVE 标志)。
- add_wait_queue_exclusive() :在等待队列尾部添加独占等待队列节点(独占等待,设置了 WQ_FLAG_EXCLUSIVE 标志)。
- remove_wait_queue() 函数用于将等待队列节点 wq_entry 从等待队列 wq_head 中移除
所以,整个等待队列的结构看起来如下图:
3.等待(./include/linux/wait.h)
内核中提供了等待事件 wait_event() 宏(以及它的几个变种),可用于实现简单的进程休眠,等待直至某个条件成立,主要包括如下四个定义:
wait_event()-TASK_UNINTERRUPTIBLE:进程只能被wake_up_xxx()显示唤醒
wait_event_interruptible()-TASK_INTERRUPTIBLE:进程可以被wake_up_xxx()显示唤醒,可以被信号唤醒
wait_event_timeout():进程可以被wake_up_xxx()显示唤醒,时间逾期后自动唤醒
wait_event_interruptible_timeout():进程可以被wake_up_xxx()显示唤醒,进程可以被信号唤醒,时间逾期后自动唤醒
这里只着重介绍wait_event()
总结:
经过源码分析可以看到:
wait_event()会默认生成一个等待队列节点,该节点为普通节点(non-exclusive),且唤醒函数为autoremove_wake_function(),并将该节点插入等待队列头部,使进程进入非中断休眠状态;
当进程被wake_up_xxx()唤醒(调用autoremove_wake_function()),继续将等待队列节点插入等待队列头部,判断条件condition为真,退出for循环,调用finish_wait()将节点从等待队列移除
4.唤醒
前文已经简单提到, wake_up 函数可用于将等待队列上的所有进程唤醒,和 wait_event 相对应, wake_up 函数也包括多个变体。主要包括:
./include/linux/wait.h, ./kernel/sched/wait.c
#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, 1)
#define wake_up_all_locked(x) __wake_up_locked((x), TASK_NORMAL, 0)
#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)
wake_up() 可以用来唤醒等待队列上的所有进程,而 wake_up_interruptible() 只会唤醒那些执行可中断休眠的进程。因此约定, wait_event() 和 wake_up() 搭配使用,而 wait_event_interruptible() 和 wake_up_interruptible() 搭配使用。
前文提到,对于独占等待的进程, wake_up() 只会唤醒第一个独占等待进程。 wake_up_nr() 函数提供功能,它能唤醒给定数目nr个独占等待进程,而不是只有一个 ,这里着重介绍wake_up()
./include/linux/wait.h,./include/linux/sched.h
./kernel/sched/wait.c
总结:
wake_up() 函数会遍历等待队列上的所有节点(包括TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE)),根据 nr_exclusive 参数的要求唤醒进程,同时实现了分批次唤醒工作。最终会回调等待队列节点所绑定的唤醒函数。
前文已经提到,定义等待队列节点时主要涉及到两种唤醒回调函数:
- default_wake_function() :宏定义 DECLARE_WAITQUEUE(name, tsk) 使用的唤醒函数。
- autoremove_wake_function() : DEFINE_WAIT(name) , init_wait(wait) 和 wait_event() 中调用的 init_wait_entry() 使用此唤醒函数。
./kernel/sched/wait.c
int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flags, void *key)
{
return try_to_wake_up(curr->private, mode, wake_flags);
}
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
unsigned long flags;
int cpu, success = 0;
raw_spin_lock_irqsave(&p->pi_lock, flags);
smp_mb__after_spinlock();
// 此处对进程的状态进行筛选,跳过不符合状态的进程(TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE)
if (!(p->state & state))
goto out;
trace_sched_waking(p);
/* We're going to change ->state: */
success = 1;
cpu = task_cpu(p);
smp_rmb();
if (p->on_rq && ttwu_remote(p, wake_flags))
goto stat;
... ...
// Try-To-Wake-Up
ttwu_queue(p, cpu, wake_flags);
stat:
ttwu_stat(p, cpu, wake_flags);
out:
raw_spin_unlock_irqrestore(&p->pi_lock, flags);
return success;
}
static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)
{
struct rq *rq = cpu_rq(cpu);
struct rq_flags rf;
... ...
rq_lock(rq, &rf);
update_rq_clock(rq);
ttwu_do_activate(rq, p, wake_flags, &rf);
rq_unlock(rq, &rf);
}
static void
ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
struct rq_flags *rf)
{
int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
lockdep_assert_held(&rq->lock);
... ...
activate_task(rq, p, en_flags);
ttwu_do_wakeup(rq, p, wake_flags, rf);
}
/*
* Mark the task runnable and perform wakeup-preemption.
*/
static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
struct rq_flags *rf)
{
check_preempt_curr(rq, p, wake_flags);
p->state = TASK_RUNNING;
trace_sched_wakeup(p);
... ...
}
总结:
从函数调用过程中可以看到, default_wake_function() 实现唤醒进程的过程为:
default_wake_function() --> try_to_wake_up() --> ttwu_queue() --> ttwu_do_activate() --> ttwu_do_wakeup()
值得一提的是, default_wake_function() 的实现中并未将等待队列节点从等待队列中删除。autoremove_wake_function() 相比于 default_wake_function() ,在成功执行进程唤醒工作后,会自动将等待队列元素从等待队列中移除。
5.TASK_INTERRUPTIBLE & TASK_UNINTERRUPTIBLE
最后总结一下自己对上述两种状态的认识和实验结果:
参考./kernel/time/timer.c中schedule_timeout的描述:
TASK_INTERRUPTIBLE与TASK_UNINTERRUPTIBLE实际上就是设置进程睡眠时的状态
TASK_INTERRUPTIBLE:可中断睡眠,进程可以被信号中断唤醒(实测硬件中断不能唤醒),可以被wake_up_process显示唤醒,可以被timeout到期自动唤醒
TASK_UNINTERRUPTIBLE:不可中断睡眠,可以被wake_up_process显示唤醒,可以被timeout到期自动唤醒,不可以被信号中断唤醒(实测硬件中断不能唤醒)
以上两种情况下,系统对硬件中断都可以正常响应