从源码角度来解读 Linux 等待队列机制, 了解休眠与唤醒的运转原理
- kernel/include/Linux/wait.h
- kernel/kernel/sched/wait.c
- kernel/include/Linux/sched.h
- kernel/kernel/sched/core.c
一, 概述
Linux 内核的等待队列是非常重要的数据结构, 在内核驱动中广为使用, 它是以双循环链表为基础数据结构, 与进程的休眠唤醒机制紧密相联, 是实现异步事件通知, 跨进程通信, 同步资源访问等技术的底层技术支撑.
研究等待队列这个内核非常基础的数据结构, 对于加深理解 Linux 非常有帮忙, 等待队列有两种数据结构: 等待队列头 (wait_queue_head_t) 和等待队列项(wait_queue_t), 两者都有一个 list_head 类型 task_list. 双向链表通过 task_list 将 等待队列头和一系列等待队列项串起来, 源码如下所示.
二, 等待队列
- 2.1 struct wait_queue_head_t
- struct __wait_queue_head {
- spinlock_t lock; // 用于互斥访问的自旋锁
- struct list_head task_list;
- };
- typedef struct __wait_queue_head wait_queue_head_t;
可通过宏 DECLARE_WAIT_QUEUE_HEAD(name)来创建类型为 wait_queue_head_t 的等待队列头 name.
- #define DECLARE_WAIT_QUEUE_HEAD(name) \
- struct wait_queue_head name = __WAIT_QUEUE_HEAD_INITIALIZER(name)
- #define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \
- .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
- .head = { &(name).head, &(name).head } }
- 2.2 struct wait_queue_t
- struct __wait_queue {
- unsigned int flags;
- void *private; // 指向等待队列的进程 task_struct
- wait_queue_func_t func; // 唤醒函数
- struct list_head task_list; // 链表元素, 将 wait_queue_t 挂到 wait_queue_head_t
- };
- typedef struct __wait_queue wait_queue_t;
可通过宏 DECLARE_WAITQUEUE(name, tsk)来创建类型为 wait_queue_t 的等待队列项 name, 并将 tsk 赋值给成员变量 private, default_wake_function 赋值给成员变量 func.
- #define DECLARE_WAITQUEUE(name, tsk) \
- struct wait_queue_entry name = __WAITQUEUE_INITIALIZER(name, tsk)
- #define __WAITQUEUE_INITIALIZER(name, tsk) { \
- .private = tsk, \
- .func = default_wake_function, \
- .entry = { NULL, NULL } }
- 2.3 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);
- }
该方法的功能是将 wait 等待队列项 挂到等待队列头 q 中.
- 2.4 remove_wait_queue
- 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 __remove_wait_queue(wait_queue_head_t *head, wait_queue_t *old)
- {
- list_del(&old->task_list);
- }
该方法主要功能是将 wait 等待队列项 从等待队列头 q 中移除.
到这里, 已经介绍了 wait_queue_head_t 和 wait_queue_t 这两个创建方法, 以及增加和删除等待队列元素的方法. 接下里说一说如何在等待队列的基础上建立休眠与唤醒机制.
三, 休眠与唤醒
- 3.1 wait_event
- #define wait_event(wq, condition) \
- do { \
- if (condition) \
- break; \
- __wait_event(wq, condition); \
- } while (0)
- #define __wait_event(wq, condition) \
- (void)___wait_event(wq, condition, TASK_UNINTERRUPTIBLE, 0, 0, schedule())
将___wait_event()宏展开如下所示
- ___wait_event(wq, condition, state, exclusive, ret, cmd){
- wait_queue_t __wait;
- INIT_LIST_HEAD(&__wait.task_list);
- for (;;) {
- // 当检测进程是否有待处理信号则返回值__int 不为 0,[见 3.1.1]
- 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 中移除
- }
- 3.1.1 prepare_to_wait_event
再来看看进入睡眠状态之前的准备工作, 用于防止 wait 没有队列中, 而事件已产生, 则会无线等待.
- long prepare_to_wait_event(wait_queue_head_t *q, wait_queue_t *wait, int state)
- {
- unsigned long flags;
- if (signal_pending_state(state, current)) // 信号检测
- return -ERESTARTSYS;
- wait->private = current;
- wait->func = autoremove_wake_function; // 设置 func 唤醒函数,[小节 3.1.2]
- spin_lock_irqsave(&q->lock, flags);
- if (list_empty(&wait->task_list)) { // 当 wait 不在队列 q, 则加入其中, 防止无法唤醒
- if (wait->flags & WQ_FLAG_EXCLUSIVE)
- __add_wait_queue_tail(q, wait);
- else
- __add_wait_queue(q, wait);
- }
- set_current_state(state); // 设置进程状态
- spin_unlock_irqrestore(&q->lock, flags);
- return 0;
- }
wait_event(wq, condition): 进入睡眠状态直到 condition 为 true, 在等待期进程状态为 TASK_UNINTERRUPTIBLE. 对应的唤醒方法是 wake_up(), 当等待队列 wq 被唤醒时会执行如下两个检测:
检查 condition 是否为 true, 满足条件, 则跳出循环.
检测该进程 task 的成员 thread_info->flags 是否被设置 TIF_SIGPENDING, 被设置则说明有待处理的信号, 则跳出循环.
wait_event_xxx 有一组用于睡眠的函数, 基于是否可中断 (TASK_UNINTERRUPTIBLE), 是否有超时机制, 在方法名后缀加上 interruptible,timeout 等信息, 对应的含义就是允许中断(TASK_INTERRUPTINLE) 和带有超时机制, 比如 wait_event_interruptible(), 这里就不再列举. 另外 sleep_on()也是进入睡眠状态, 没有 condition, 不过该方法有可能导致竞态, 从 kernel 3.15 移除该方法, 采用 wait_event 代替 sleep_on().
- 3.1.2 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;
- }
- 3.2 wake_up
- #define wake_up(x) __wake_up(x, TASK_NORMAL, 1, NULL)
- 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;
- // 调用唤醒函数 [小节 3.2.1]
- if (curr->func(curr, mode, wake_flags, key) &&
- (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
- break;
- }
- }
wait_event(wq)遍历整个等待列表 wq 中的每一项 wait_queue_t, 依次调用唤醒函数来唤醒该等待队列中的所有项, 唤醒函数如下:
对于通过宏 DECLARE_WAITQUEUE(name, tsk) 来创建 wait, 再调用 add_wait_queue(wq, wait)方法, 则唤醒函数为 default_wake_function
对于通过 wait_event(wq, condition)方式加入的 wait 项, 则经过调用 prepare_to_wait_event()方法, 则唤醒函数为 autoremove_wake_function, 由小节 [1.3.5] 可知, 该方法主要还是调用 default_wake_function 来唤醒.
wake_up_xxx 有一组用于唤醒的函数, 跟 wait_event 配套使用. 比如 wait_event()与 wake_up(),wait_event_interruptible()与 wake_up_interruptible().
3.2.1 default_wake_function
再来看看唤醒函数函数
- int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
- void *key)
- {
- // 获取 wait 所对应的进程 [小节 3.2.2]
- return try_to_wake_up(curr->private, mode, wake_flags);
- }
- 3.2.2 try_to_wake_up
- 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); //[小节 3.2.3]
- stat:
- ttwu_stat(p, CPU, wake_flags);
- out:
- raw_spin_unlock_irqrestore(&p->pi_lock, flags); // 恢复本地中断
- ...
- return success;
- }
- 3.2.3 ttwu_queue
- static void ttwu_queue(struct task_struct *p, int CPU)
- {
- struct rq *rq = cpu_rq(CPU); // 获取当前进程的运行队列
- raw_spin_lock(&rq->lock);
- lockdep_pin_lock(&rq->lock);
- ttwu_do_activate(rq, p, 0); // [小节 3.2.4]
- lockdep_unpin_lock(&rq->lock);
- raw_spin_unlock(&rq->lock);
- }
在 kernel/sched/core.c 目录中发现有大量 ttwu_xxx 的方法, 这个单词缩写可真是厉害, 琢磨一会结合上下文, 才明白原来是 try to wake up 的缩写, 另外为了简化, 这里只介绍单处理器的逻辑.
- 3.2.4 ttwu_do_activate
- static void ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
- {
- ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
- ttwu_do_wakeup(rq, p, wake_flags);
- }
- static inline void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
- {
- activate_task(rq, p, en_flags); // 将进程 task 加入 rq 队列
- p->on_rq = TASK_ON_RQ_QUEUED;
- if (p->flags & PF_WQ_WORKER)
- wq_worker_waking_up(p, cpu_of(rq)); //worker 正在唤醒中, 则通知工作队列
- }
- static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
- {
- check_preempt_curr(rq, p, wake_flags);
- p->state = TASK_RUNNING; // 标记该进程为 TASK_RUNNING 状态
- ...
- }
四, 总结
通过 DECLARE_WAIT_QUEUE_HEAD(name)可初始化 wait_queue_head_t 结构体, 通过 DECLARE_WAITQUEUE 可初始化 wait_queue_t 结构体, 由等待队列头 (wait_queue_head_t) 和等待队列项 (wait_queue_t) 构建一个双向链表. 可通过 add_wait_queue 和 remove_wait_queue 分别向双向链表中添加或删除等待项.
休眠与唤醒流程:
进程 A 调用 wait_event(wq, condition)就是向等待队列头中添加等待队列 wait_queue_t, 该 wait_queue_t 中的 private 记录了当前进程以及 func 记录唤醒回调函数, 然后调用 schedule()进入休眠状态.
进程 B 调用 wake_up(wq)会遍历整个等待列表 wq 中的每一项 wait_queue_t, 依次每一项的调用唤醒函数 try_to_wake_up(). 这个过程会将 private 记录的进程加入 rq 运行队列, 并设置进程状态为 TASK_RUNNING.
进程 A 被唤醒后只执行如下检测:
检查 condition 是否为 true, 满足条件则跳出循环, 再把 wait_queue_t 从 wq 队列中移除;
检测该进程 task 的成员 thread_info->flags 是否被设置 TIF_SIGPENDING, 被设置则说明有待处理的信号, 则跳出循环, 再把 wait_queue_t 从 wq 队列中移除;
否则, 继续调用 schedule()再次进入休眠等待状态, 如果 wait_queue_t 不在 wq 队列, 则再次加入 wq 队列.
喜欢的话请帮忙转发一下能让更多有需要的人看到吧, 有些技术上的问题大家可以多探讨一下.
以上 Android 资料以及更多 Android 相关资料及面试经验可在 QQ 群里获取: 936903570. 有加群的朋友请记得备注上简书, 谢谢
来源: http://www.jianshu.com/p/2a156b224187