作者：世至其美
原文地址：https://hqber.com
Linux调度算法
1. 时间记账
1.1 调度器实体结构
CFS使用调度器的实体结构（源代码 | linux/sched.h）追踪进程运行记账，然后将实体结构体作为se的成员变量，嵌入在进程描述符struct task_struct内。
struct sched_entity {
/* For load-balancing: */
struct load_weight load;// 权重，跟优先级有关
unsigned long runnable_weight;// 在所有可运行进程中所占的权重
struct rb_node run_node;// 红黑树的节点
struct list_head group_node;// 所在进程组
unsigned int on_rq;// 标记是否处于红黑树运行队列中
u64 exec_start;// 进程开始执行的时间
u64 sum_exec_runtime;// 进程总运行时间
u64 vruntime;// 虚拟运行时间
u64 prev_sum_exec_runtime;// 上个周期中sum_exec_runtime
u64 nr_migrations;
struct sched_statistics statistics;
// 以下省略了一些在特定宏条件下才会启用的变量
};
1.2 虚拟实时
vruntime变量存放进程的虚拟时间，单位为ns，和定时器节拍不再相关。因为优先级相同的所有进程的虚拟运行时间是相同的，所有进程都将接收到相等的处理器份额。处理器只能是依次运行每个进程，无法实现多任务运行。
因此，CFS使用vruntime变量来记录一个程序到底运行了多长时间以及还需要运行多久。update_curr函数是由系统定时器周期性调用的，无论进程在哪种状态。
update_curr函数（源代码 | kernel/sched/fair.c）
/*
* 计算当前进程的执行时间，存放在delta_exec
*/
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
/*获取从最后一次修改负载后当前任务所占用的运行总时间
*/
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
//设置开始时间
curr->exec_start = now;
//根据当前进程总数对运行时间进行加权计算
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cgroup_account_cputime(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
2. 进程选择
在进程选择方面，CFS调度算法核心是选择最小vruntime的任务，CFS是通过红黑树来组织可运行进程队列，并利用其迅速找到最小的vruntime值的进程。（红黑树最左侧的叶子节点）
2.1 挑选下一个Task
__pick_next_entity函数（源代码 | kernel/sched/fair.c）
static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{
//获取红黑树中vruntime值最小的可运行进程
struct rb_node *next = rb_next(&se->run_node);
if (!next)
return NULL;
return rb_entry(next, struct sched_entity, run_node);
}
如果没有可运行线程，CFS调度器会选择idle的线程执行。
2.2 向树中加入进程
当一个新的进程状态转换为可运行时，需要向可运行队列中插入一个新的节点。而这个过程本质上是向红黑树中插入新节点的过程。
这会发生在两种情况下：
- 当进程由阻塞态被唤醒
- fork()调用创建新的进程
enqueue_entity函数（源代码 | kernel/sched/fair.c）
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
bool curr = cfs_rq->curr == se;
/* * 如果要加入的进程就是当前正在运行的进程，重新规范化vruntime */
if (renorm && curr)
se->vruntime += cfs_rq->min_vruntime;
//更新“当前任务”运行时的统计数据
update_curr(cfs_rq);
/* * 如果不是当前正在运行的进程，也要恢复到当前的时间 */
if (renorm && !curr)
se->vruntime += cfs_rq->min_vruntime;
/* * 更新对应调度器实体的各种记录值 */
//更新同步实体和cfs_rq
update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
//将se加入group中
update_cfs_group(se);
//重新分配权重占比，将其新的权重添加到cfs_rq-> load.weight
enqueue_runnable_load_avg(cfs_rq, se);
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_WAKEUP)
place_entity(cfs_rq, se, 0);
check_schedstat_required();
update_stats_enqueue(cfs_rq, se, flags);
check_spread(cfs_rq, se);
if (!curr)
__enqueue_entity(cfs_rq, se);//将数据项插入红黑树
se->on_rq = 1;
if (cfs_rq->nr_running == 1) {
list_add_leaf_cfs_rq(cfs_rq);
check_enqueue_throttle(cfs_rq);
}
}
__enqueue_entity函数（源代码 | kernel/sched/fair.c）
/* * 将entity加入红黑树（rb-tree） */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
bool leftmost = true;
/* * 在红黑树中搜索合适的位置 */
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/* * 具有相同键值的节点会被放在一起，键值是vruntime */
if (entity_before(se, entry)) {
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = false;
}
}
//向树中插入子节点
rb_link_node(&se->run_node, parent, link);
//更新红黑树的自平衡相关属性，通过leftmost判断该节点是否为vruntime最小进程
rb_insert_color_cached(&se->run_node,
&cfs_rq->tasks_timeline, leftmost);
}
2.3 从树中删除进程
当进程堵塞（不可运行态）或者终止时（结束运行），需从红黑树中删除进程。
dequeue_entity函数（源代码| kernel/sched/fair.c）
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/* * 更新加载，保持entity和cfs_rq同步 */
//从cfs_rq->load.weight中减去entity的权重
update_curr(cfs_rq);
//从cfs_rq->runnable_avg中减去entity负载
update_load_avg(cfs_rq, se, UPDATE_TG);
//对于group的entity，更新其权重以反映其组的cfs_rq新份额
dequeue_runnable_load_avg(cfs_rq, se);
update_stats_dequeue(cfs_rq, se, flags);
clear_buddies(cfs_rq, se);
//从树中进行删除节点
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);
/* * 重新规范化vruntime */
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= cfs_rq->min_vruntime;
/* 返回剩余运行的时间 */
return_cfs_rq_runtime(cfs_rq);
update_cfs_group(se);
if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) != DEQUEUE_SAVE)
update_min_vruntime(cfs_rq);
}
实际对树节点操作的工作由__dequeue_entity()实现的，
__dequeue_entity函数（源代码 | kernel/sched/fair.c）
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}
rb-tree中实现的树节点删除函数，stackoverflow | Linux中的EXPORT_SYMBOL和c语言中的extern的区别
rb_erase_cached函数（ 源代码 | lib/rbtree.c）
void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
{
struct rb_node *rebalance;
rebalance = __rb_erase_augmented(node, &root->rb_root,
&root->rb_leftmost, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase_cached);//EXPORT_SYMBOL只是一种类似于extern的机制，但它是可加载模块之间的参考，而不是文件
3. 调度器入口
进程调度的统一入口是__schedule函数，它会选择一个最高优先级的调度类，每个调度类都有自己的可运行队列，然后可以知道下一个运行的进程。
__schedule函数（源代码 | kernel/sched/core.c）
static void __sched notrace __schedule(bool preempt)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq_flags rf;
struct rq *rq;
int cpu;
cpu = smp_processor_id();
rq = cpu_rq(cpu);
prev = rq->curr;
schedule_debug(prev);
if (sched_feat(HRTICK))
hrtick_clear(rq);
local_irq_disable();
rcu_note_context_switch(preempt);
/* * Make sure that signal_pending_state()->signal_pending() below * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE) * done by the caller to avoid the race with signal_wake_up(). * * The membarrier system call requires a full memory barrier * after coming from user-space, before storing to rq->curr. */
rq_lock(rq, &rf);
smp_mb__after_spinlock();
/* Promote REQ to ACT */
rq->clock_update_flags <<= 1;
update_rq_clock(rq);
switch_count = &prev->nivcsw;
if (!preempt && prev->state) {
if (unlikely(signal_pending_state(prev->state, prev))) {
prev->state = TASK_RUNNING;
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
prev->on_rq = 0;
if (prev->in_iowait) {
atomic_inc(&rq->nr_iowait);
delayacct_blkio_start();
}
/* * If a worker went to sleep, notify and ask workqueue * whether it wants to wake up a task to maintain * concurrency. */
if (prev->flags & PF_WQ_WORKER) {
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev);
if (to_wakeup)
try_to_wake_up_local(to_wakeup, &rf);
}
}
switch_count = &prev->nvcsw;
}
//通过优先级获取最高优先级的调度类，然后从最高优先级的调度类中选择最高优先级的进程
next = pick_next_task(rq, prev, &rf);
clear_tsk_need_resched(prev);
clear_preempt_need_resched();
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
/* * The membarrier system call requires each architecture * to have a full memory barrier after updating * rq->curr, before returning to user-space. * * Here are the schemes providing that barrier on the * various architectures: * - mm ? switch_mm() : mmdrop() for x86, s390, sparc, PowerPC. * switch_mm() rely on membarrier_arch_switch_mm() on PowerPC. * - finish_lock_switch() for weakly-ordered * architectures where spin_unlock is a full barrier, * - switch_to() for arm64 (weakly-ordered, spin_unlock * is a RELEASE barrier), */
++*switch_count;
trace_sched_switch(preempt, prev, next);
/* Also unlocks the rq: */
rq = context_switch(rq, prev, next, &rf);
} else {
rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
rq_unlock_irq(rq, &rf);
}
balance_callback(rq);
}
pick_next_task主要功能是从发生调度的CPU运行队列中选择最高优先级的进程。
系统中的调度顺序为：实时进程→普通进程→空闲进程。（rt_sched_class → fair_sched_class → idle_sched_class ）
pick_next_task函数（源代码 | kernel/sched/core.c）
/* * 挑选最高优先级的任务 */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
const struct sched_class *class = &fair_sched_class;
struct task_struct *p;
/* * 优化：如果当前所有要调度的进程都是普通进程，那么就直接采用普通进程的调度类（CFS） */
//就绪队列中的进程数是否与普通进程的就绪队列中的进程数是否相同
if (likely(prev->sched_class == class &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq, prev);
if (unlikely(p == RETRY_TASK))
goto again;
/* 如果没有cfs调度类的进程处于就绪状态，也就是fair_sched_class->next == idle_sched_class（空闲进程）， * 每个CPU都有一个空闲调度类进程，永远不会阻塞。 */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev);
return p;
}
// 如果是实时进程，则遍历调度类
again:
for_each_class(class) {
p = class->pick_next_task(rq, prev);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}
BUG(); /* the idle class will always have a runnable task */
}
4.睡眠和唤醒
- 睡眠：将进程标记成休眠状态，然后从可执行红黑树中移除，放入等待队列，然后调用选择和执行一个其他进程。
- 唤醒：将进程标记成可执行状态，然后从等待队列转移到可执行红黑树中。
休眠在Linux中有两种状态，一种是TASK_UNINTERRUPTIBLE的进程会忽略信号，另一种是TASK_INTERRUPTIBLE的进程会在收到信号的时候被唤醒并响应。不过这两种状态的进程是处于同一个等待队列上的，等待事件，不能运行。
4.1 等待队列
等待队列的实现只是一个简单的链表，由等待某些事件发生的进程组成。wait_queue_head_t表示链表的头节点，加入了一个自旋锁来保持一致性（等待队列在中断时可以被随时修改）
wait_queue_head_t定义（源代码 | /include/linux/wait.h）
struct __wait_queue_head {
spinlock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
进入休眠的进程需要把自己加入到一个等待队列中，主要流程如下：
- 调用宏DEFINE_WAIT()创建一个等待队列的项（即链表的节点）
- 调用add_wait_queue()把自己加入等待队列中，该进程会在等待队列中等待事件发生，执行wake_up()函数唤醒进程，同时须编写唤醒后处理代码（你可以理解为一个回调函数）
- 调用prepare_to_wait()方法设置两种休眠状态中的其中一种
add_wait_queue函数（源代码 | /kernel/sched/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);
}
__add_wait_queue函数（源代码 | /include/linux/wait.h）
static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
//将节点加入链表
list_add(&new->task_list, &head->task_list);
}
prepare_to_wait函数（源代码 | /kernel/sched/wait.c）
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);
}
4.2 唤醒
唤醒操作主要通过调用wake_up函数，它会唤醒指定等待队列上的所有满足事件的进程，并将对应的进程标记为TASK_RUNNING状态，接着将进程加入红黑树中。具体调用过程如下：
wake_up函数（源代码 | /include/linux/wait.h）
#define wake_up(x) __wake_up(x, TASK_NORMAL, 1, NULL)
__wake_up函数（源代码 | /kernel/sched/wait.c）
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);
}
__wake_up_common函数（源代码 | /kernel/sched/wait.c）
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;
}
}
作者：世至其美
原文地址：https://hqber.com
