CFS调度算法详细解析_cfsschedule

需积分: 48 163 浏览量更新于2023-03-16 3 收藏 713KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

CFS 调度器

--wxc200

大家好哈，

兄弟最近在学习调度器，有点儿心得，更多得是迷惑，写出心得来与大家分享，

贴出迷惑来请大家解答。呵呵

linux 自 2.6.23 后引入了一种新的调度器，叫'Completely Fair Scheduler'（wiki）.是

由 Ingo Molnar

在很短的时间内写的。他与的 cfs 代码是对之前另一种调度器

"O(1) scheduler" 的替换.

先扯一下 o(1)调度.

先看 wiki 的解释:

"An O(1) scheduler is a kernel scheduling design that can schedule processes within a

constant amount of time, regardless of how many processes are running on the operating

system (OS)."

Understanding Linux Kernel(3th) 这本书 chapter 7 讲的进程调度,7.2 节提

到"Scheduling Algorithm",说 2.6 对进程的选择是 constant time,兼顾了批处理和交互

式进程.进程分类,实时进程(又分为 SCHED_FIFL AND SCHED_RR)和普通进程.

最主要的问题是这些进程怎么组织的,简单看下结构:

没办法传图片,请参照附件"数组".

它有两个数

组,active 里面是

has time-slice

,expired 数组是

out-of-slice。简单

的说，一个普通

的进程被调度运

行后，放在 active

里，当其时间片

用光后，可能就要移到 expired “ ”数组里了。说可能是因为有的进程就不移走。比

如交互式进程。

说白了,就是把所有的 process 按照优先级挂在链表上,从里面按照优先级高低选择

第一个不为空的进程运行.

普通进程的优先级是 100~139,实时进程要更低,这符合调度的算法.

我有点等不及了,咱们直接奔 cfs 吧~

另外有点就是,引入 hrtimer 之后,进程调度还是在 tick 中断完成的.每个 tick 都会检

查进程是否应该调度,当然,主动让 cpu(即调用 scheduler().)的就不算了吧...

hrtimer 那部分东东等咱们聊完了 cfs 再说，那个主要是在原有的时间管理 layer 上

“ ”新添加了时间事件，把时间中断以事件的方式注册。精确度由之前的 hz 提升到

了 ns（需要硬件支持）。。。

cfs

Documentation/scheduler/sched-design-CFS.txt 介绍了 cfs 相关东西，也可以在线看 .

“ ”我按照我的理解来添油加醋地翻译下。

1 概括

“80% of CFS's design can be summed up in a single sentence: CFS basically models

an "ideal, precise multi-tasking CPU" on real hardware.”

""Ideal multi-tasking CPU" is a (non-existent :-)) CPU that has 100% physical

power and which can run each task at precise equal speed, in parallel, each at

1/nr_running speed. For example: if there are 2 tasks running, then it runs

each at 50% physical power --- i.e., actually in parallel.

模拟了个理想的，多任务 cpu.假如有 n 个进程，那么每个进程的执行速度是 1/n,,

即所有的任务都是并行执行的。我认为就算是有并行执行的 cpu，速度也不应该

完全平均，按照优先级再分比较划算。比如 2 个进程，a,b，a 的优先级是 b 的两

倍，那么就照着速度比 a:b = 2:1 呗~

“On real hardware, we can run only a single task at once, so we have to

introduce the concept of "virtual runtime." The virtual runtime of a task

specifies when its next timeslice would start execution on the ideal

multi-tasking CPU described above. In practice, the virtual runtime of a task

is its actual runtime normalized to the total number of running tasks. ”

当然没有这种 cpu,故引进了个新概念"virtual runtime",这个概念真是折磨人好久。

我曾经在 clf

上发帖子问过，有个兄弟回复还是不错的。后面看过代码后，我的理

解是：1 ）红黑树结点排列的值 2 ）每次 task run time 转换的一个值 .

先看上文颜色部分，我真是很难翻译它~ 照字面理解，是实际运行时间与任务数

量的一个比值？我举个例子来说明它是怎么计算的吧。。

在 __update_curr(）这个函数里，会更新当前任务的运行时间信息。假如一个任务

a 自上次调度到这次调度时间间隔为 delta, 那么它的 vrumtime 的增量是按照这个公

式：delta * NICE_0_LOAD / a->se.load。假如把 NICE_0_LOAD / a->se.load 作为一

个比值 p 的话，我们可以这么描述 p 的变化：优先级越高，p 越小。这个 load 是

与 nice 值相关的，有一个静态的数组，我后面在代码里会介绍。

所以，一堆进行都运行了一段时间 delta，那么它们的 vrumtime 就遵循上面的公

式。很明显，优先级最大的进程 vrumtime 增量最小。。。

2 操作细节

cfs 就是通过追踪这个 vruntime 来进行任务调度的。它总是选 vruntime 最小的进程

来运行。

3 红黑树。

红黑树这个数据结构在内核里用得还不少嘛，不过俺不太懂。哪位兄弟给扫扫

盲？ hrtimer 里也用到了 red-black-tree。这里把进程的 vruntime 用 rb-tree 来存储。

4 一些 feature

cfs has no time-slice concept.o(1)有的，cfs “ ”没有明显得用，它偷偷摸摸地用。呵

呵 “翻译完这几段咱再说这个。文档里面那个接口估计是用来调整最小粒

” “ ” “ “ 度的。用于桌面和服务器两种不同的调度。后者可能不太希望频繁的调

度，浪费时间。前者则希望面面俱到--” “不患寡妇而患不均也

5 调度 policy

SCHED_FIFO/_RR are implemented in sched_rt.c and are as specified by POSIX. 实时

进程调度

实时调度和普通进程调度。

6 调度的类。

调度哭可以模块化注册，所以你可以选择实时调度或者是 cfs 调度。不错！

sched_fair.c 文件实现了 cfs 调度的所以 classes

7 组调度。

不光是普通进程，组调度也实现了。。这个是后来一个 patch 加的。

×××××××××××××××××××××××××××××××××××

上面是对着内核的一篇文档，简要地说了几部分。。。在正式进行我们的 hack

之前，先唠叨几句，算是个总结和感性的认识吧~吼吼

关于实时进程的调度，这一次先不分析，它和 o1 差不多，还保持着优先级数组的

” “ ” “做法，那是上流社会玩儿的游戏，后面再折腾它。普通大众们玩儿的就是 cfs

了。

cfs 调度，我写两部分，一部分是普通进程的调度，没有组的概念。一部分是组

的调度。我个人觉得组得调度比较难理解~ 这几天一直在思考。。。今天下午好

像豁然开朗了。。。画了个草图，到后面我做出这张图来，大家看看对不对 :D

咱们先说普通进程的调度

关于普通进程的组织，应该有这么一种印象。

有一个队列，叫 cfs_rq,里面维护了个红黑树。每一个 task_struct has a se,称为调度

实体。它就代表了一个被调度的进程，里面有此进程的一些信息，比如前面提到

的 vruntime.

一个进程创建的时候，就会被放置在这个红黑树里。它自己的位置是由它的

vruntime 值来决定的。在每个 tick 中断的时候，会更新进程的信息，并检查这个

红黑树，判断某些进程是不是要被替换掉。

现在我们来想象下面一个例程。

进程 a 被创建了，sched_fork()会做一些新创建进程调度方面的初始化。然后应该

尝试把此进程放到队列里啊，让它被调度。 set_task_cpu()做了这部分工作。然后

这个进程如果不是实时进程，就让它跟 cfs 的类绑定在一块儿，这样下面用到调度

的一些方法，就会到 cfs 相关的类去找喽~ 这时候如果抢占打开了，会去调度一

次，以让新创建的进程有机会被调度一次。或者在下一个 tick 的时候，会检查已

经红黑树，以确认这个进程是不是调度。（注：上面红色这句有点胡扯的嫌疑，

请明白人指点）

比如在每个 tick 中断的时候，会去红黑树里面找 vruntime 最小的那个（红黑树最

左边的叶子）去调度。那么这个调度过程，所有用到的方法，就是上面提到的 cfs

的类给实现的。

最后，大家再对 rb-tree 里面的任务结点有个感性的认识吧：

优先级高的进程，总是靠左，以有最大调度机会。比如说有 n 个进程，那么在一

段时间内，应该把 n 个进程都运行一遍。这儿有两三个问题，一段时间是多久？

每个进程有多少时间去运行呢？每个进程分到的运行时间跟 vruntime 有什么关系

呢？

一段时间，与运行着的进程数目有关。进程越多，时间越长。每个进程并不是平

均分配这些时间的。按照我的理解，分到这个时间越多的进程，后面 vruntime 增

长得越慢。

上面这几句话，我可是晕了近一个星期才明白的。不知道跟大家的理解一致么？

本来我错误得理解是这样的，完全公平调度么，当然所有的进程有同样的运行时

间。如果是这样，那么 rb-tree 就没用了。因为每个结点都一样的值。所以，请大

家有这样一种概念：两个进程，a 优先级特别低，b 特高。假如现在有 n 个正被调

剩余33页未读，继续阅读

Knight_Dragon

粉丝: 0
资源: 6

会员权益专享

CFS调度算法 详细解析

CFS调度器（3）-组调度.pdf

CFS调度器（4）-PELT(per entity load tracking).pdf

CfS辅助代码

Linux进程优先级与调度策略解析

解释进程调度CFS调度算法原理，给出主要数据结构和函数的相关解释

2．分析linux(4.X版本以上)进程调度源码，尝试解释进程调度CFS调度算法原理，给出主要数据结构和函数的相关解释（给出代码出处——路径和文件名）30分

实时进程队列也会用CFS调度器吗

高响应比优先调度算法底层采用的是CFS吗

CFS调度器永远都会运行在CPU中吗？不会被抢占？

python进程调度算法

LINUX进程调度策略有哪几种？普通进程采用哪种调度策略？比较用户抢占与内核抢占的区别。

linux处理器调度算法

5.Linux进程调度算法

/* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq; /* rq "owned" by this entity/group: */ struct cfs_rq *my_q; /* cached value of my_q->h_nr_running */ unsigned long runnable_weight;

linux调度算法比较

linux 进程调度算法模拟

Linux完全公平调度算法

时间片轮转调度算法linux

Linux进程调度算法

linux进程调度算法实验

会员权益专享

最新资源

CFS调度算法详细解析

/* rq on which this entity is (to be) queued: / struct cfs_rq cfs_rq; /* rq "owned" by this entity/group: / struct cfs_rq my_q; /* cached value of my_q->h_nr_running */ unsigned long runnable_weight;