一文讲解Linux进程调度-CFS调度器
说明:
Kernel版本:4.14
ARM64处理器,Contex-A53,双核
使用工具:Source Insight 3.5, Visio
1. 概述
Completely Fair Scheduler
,完全公平调度器,用于Linux系统中普通进程的调度。CFS
采用了红黑树算法来管理所有的调度实体sched_entity
,算法效率为O(log(n))
。CFS
跟踪调度实体sched_entity
的虚拟运行时间vruntime
,平等对待运行队列中的调度实体sched_entity
,将执行时间少的调度实体sched_entity
排列到红黑树的左边。调度实体
sched_entity
通过enqueue_entity()
和dequeue_entity()
来进行红黑树的出队入队。
老规矩,先上张图片来直观了解一下原理:

每个
sched_latency
周期内,根据各个任务的权重值,可以计算出运行时间runtime
;运行时间
runtime
可以转换成虚拟运行时间vruntime
;根据虚拟运行时间的大小,插入到CFS红黑树中,虚拟运行时间少的调度实体放置到左边;
在下一次任务调度的时候,选择虚拟运行时间少的调度实体来运行;
在开始本文之前,建议先阅读下Linux进程调度器-基础
。
2. 数据结构
2.1 调度类
Linux内核抽象了一个调度类struct sched_class
,这是一种典型的面向对象的设计思想,将共性的特征抽象出来封装成类,在实例化各个调度器的时候,可以根据具体的调度算法来实现。这种方式做到了高内聚低耦合,同时又很容易扩展新的调度器。

在调度核心代码
kernel/sched/core.c
中,使用的方式是task->sched_class->xxx_func
,其中task
表示的是描述任务的结构体struct task_struck
,在该结构体中包含了任务所使用的调度器,进而能找到对应的函数指针来完成调用执行,有点类似于C++中的多态机制。
【文章福利】小编推荐自己的Linux内核技术交流群:【749907784】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面,有需要的可以自行添加哦!!!(含视频教程、电子书、实战项目及代码)


2.2 rq/cfs_rq/task_struct/task_group/sched_entity
struct rq
:每个CPU都有一个对应的运行队列;struct cfs_rq
:CFS运行队列,该结构中包含了struct rb_root_cached
红黑树,用于链接调度实体struct sched_entity
。rq
运行队列中对应了一个CFS运行队列,此外,在task_group
结构中也会为每个CPU再维护一个CFS运行队列;struct task_struct
:任务的描述符,包含了进程的所有信息,该结构中的struct sched_entity
,用于参与CFS的调度;struct task_group
:组调度(参考前文),Linux支持将任务分组来对CPU资源进行分配管理,该结构中为系统中的每个CPU都分配了struct sched_entity
调度实体和struct cfs_rq
运行队列,其中struct sched_entity
用于参与CFS的调度;struct sched_entity
:调度实体,这个也是CFS调度管理的对象了;
来一张图看看它们之间的组织关系:

struct sched_entity
结构体字段注释如下:
struct cfs_rq结构体的关键字段注释如下:
3. 流程分析
整个流程分析,围绕着CFS调度类实体:fair_sched_class
中的关键函数来展开。
先来看看fair_sched_class
都包含了哪些函数:
3.1 runtime与vruntime
CFS调度器没有时间片的概念了,而是根据实际的运行时间和虚拟运行时间来对任务进行排序,从而选择调度。那么,运行时间和虚拟运行时间是怎么计算的呢?看一下流程调用:

Linux内核默认的
sysctl_sched_latency
是6ms,这个值用户态可设。sched_period
用于保证可运行任务都能至少运行一次的时间间隔;当可运行任务大于8个的时候,
sched_period
的计算则需要根据任务个数乘以最小调度颗粒值,这个值系统默认为0.75ms;每个任务的运行时间计算,是用
sched_period
值,去乘以该任务在整个CFS运行队列中的权重占比;虚拟运行的时间 = 实际运行时间 * NICE_0_LOAD / 该任务的权重;
还是来看一个实例吧,以5个Task为例,其中每个Task的nice
值不一样(优先级不同),对应到的权重值在内核中提供了一个转换数组:
图来了:

3.2 CFS调度tick
CFS调度器中的tick函数为task_tick_fair
,系统中每个调度tick都会调用到,此外如果使用了hrtimer
,也会调用到这个函数。流程如下:

主要的工作包括:
更新运行时的各类统计信息,比如
vruntime
, 运行时间、负载值、权重值等;检查是否需要抢占,主要是比较运行时间是否耗尽,以及
vruntime
的差值是否大于运行时间等;
来一张图,感受一下update_curr
函数的相关信息更新吧:

3.3 任务出队入队
当任务进入可运行状态时,需要将调度实体放入到红黑树中,完成入队操作;
当任务退出可运行状态时,需要将调度实体从红黑树中移除,完成出队操作;
CFS调度器,使用
enqueue_task_fair
函数将任务入队到CFS队列,使用dequeue_task_fair
函数将任务从CFS队列中出队操作。

出队与入队的操作中,核心的逻辑可以分成两部分:1)更新运行时的数据,比如负载、权重、组调度的占比等等;2)将sched_entity插入红黑树,或者从红黑树移除;
由于
dequeue_task_fair
大体的逻辑类似,不再深入分析;这个过程中,涉及到了
CPU负载计算
、task_group组调度
、CFS Bandwidth带宽控制
等,这些都在前边的文章中分析过,可以结合进行理解;
3.3 任务创建
在父进程通过fork
创建子进程的时候,task_fork_fair
函数会被调用,这个函数的传入参数是子进程的task_struct
。该函数的主要作用,就是确定子任务的vruntime
,因此也能确定子任务的调度实体在红黑树RB中的位置。
task_fork_fair
本身比较简单,流程如下图:

3.4 任务选择
每当进程任务切换的时候,也就是schedule
函数执行时,调度器都需要选择下一个将要执行的任务。在CFS调度器中,是通过pick_next_task_fair
函数完成的,流程如下:

当需要进程任务切换的时候,
pick_next_task_fair
函数的传入参数中包含了需要被切换出去的任务,也就是pre_task
;当
pre_task
不是普通进程时,也就是调度类不是CFS,那么它就不使用sched_entity
的调度实体来参与调度,因此会执行simple
分支,通过put_pre_task
函数来通知系统当前的任务需要被切换,而不是通过put_prev_entity
函数来完成;当
pre_task
是普通进程时,调用pick_next_entity
来选择下一个执行的任务,这个选择过程实际是有两种情况:当调度实体对应task时,do while()
遍历一次,当调度实体对应task_group
是,则需要遍历任务组来选择下一个执行的任务了。put_prev_entity
,用于切换任务前的准备工作,更新运行时的统计数据,并不进行dequeue
的操作,其中需要将CFS队列的curr
指针置位成NULL;set_next_entity,用于设置下一个要运行的调度实体,设置CFS队列的
curr
指针;如果使能了
hrtimer
,则将hrtimer
的到期时间设置为调度实体的剩余运行时间;
原文作者:LoyenWang
