CFS 调度器-阿里云开发者社区

开发者社区> 人工智能> 正文

CFS 调度器

简介:

首先简单介绍一下基本的设计思路,CFS思路很简单,就是根据各个进程的权重分配运行时间(权重怎么来的后面再说)。进程的运行时间计算公式为:
分配给进程的运行时间 调度周期 进程权重 所有进程权重之和   (公式1)
调度周期很好理解,就是将所有处于TASK_RUNNING态进程都调度一遍的时间,差不多相当于O(1)调度算法中运行队列和过期队列切换一次的时间(我对O(1)调度算法看得不是很熟,如有错误还望各位大虾指出)。举个例子,比如只有两个进程A, B,权重分别为12,调度周期设为30ms,那么分配给ACPU时间为:30ms * (1/(1+2)) = 10ms,BCPU时间为:30ms * (2/(1+2)) = 20ms那么在这30msA将运行10msB将运行20ms
    公平怎么体现呢?它们的运行时间并不一样阿?
    其实公平是体现在另外一个量上面,叫做virtual runtime(vruntime),它记录着进程已经运行的时间,但是并不是直接记录,而是要根据进程的权重将运行时间放大或者缩小一个比例。
我们来看下从实际运行时间到vruntime的换算公式

vruntime = 实际运行时间 * 1024 / 进程权重 。 (公式2)

为了不把大家搞晕,这里我直接写1024,实际上它等于nice0的进程的权重,代码中是NICE_0_LOAD也就是说,所有进程都以nice0的进程的权重1024作为基准,计算自己的vruntime增加速度。还以上面AB两个进程为例,B的权重是A2倍,那么Bvruntime增加速度只有A的一半。现在我们把公式2中的实际运行时间用公式1来替换,可以得到这么一个结果:

vruntime = (调度周期 进程权重 所有进程总权重) * 1024 / 进程权重 调度周期 * 1024 / 所有进程总权重

看出什么眉目没有?没错,虽然进程的权重不同,但是它们 vruntime增长速度应该是一样的 ,与权重无关。(实际运行时间和权重有关,vruntime也和权重有关,抵消)

好,既然所有进程的vruntime增长速度宏观上看应该是同时推进的,那么就可以用这个vruntime来选择运行的进程,谁的vruntime值较小就说明它以前占用cpu的时间较短,受到了不公平对待,因此下一个运行进程就是它。这样既能公平选择进程,又能保证高优先级进程获得较多的运行时间。这就是CFS的主要思想了。

再补充一下权重的来源,权重跟进程nice值之间有一一对应的关系,可以通过全局数组prio_to_weight来转换,nice值越大,权重越低

下面来分析代码。网上已经有很多cfs的文章,因此我打算换一个方式来写,选择几个点来进行情景分析,包括进程创建时,进程被唤醒,主动调度(schedule),时钟中断。

介绍代码之前先介绍一下CFS相关的结构第一个是调度实体sched_entity,它代表一个调度单位,在组调度关闭的时候可以把他等同为进程。每一个task_struct中都有一个sched_entity,进程的vruntime和权重都保存在这个结构中。那么所有的sched_entity怎么组织在一起呢?红黑树。所有的sched_entityvruntimekey(实际上是以vruntime-min_vruntime为单位,难道是防止溢出?反正结果是一样的)插入到红黑树中,同时缓存树的最左侧节点,也就是vruntime最小的节点,这样可以迅速选中vruntime最小的进程。注意只有等待CPU的就绪态进程在这棵树上,睡眠进程和正在运行的进程都不在树上。我从ibm developer works上偷过来一张图来展示一下它们的关系: 


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章