linux内核之cfs调度和组调度

《linux内核之cfs调度和组调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Linux内核之CFS调度和组调度作者：harveywang邮箱：harvey.perfect@gmail.com新浪博客地址：http://blog.sina.com.cn/harveyperfect，有关于减肥和学习英语相关的博文，欢迎交流Linux支持三种进程调度策略，分别是SCHED_FIFO、SCHED_RR和SCHED_NORMAL。Linux支持两种类型的进程，实时进程和普通进程。实时进程可以采用SCHED_FIFO和SCHED_RR调度策略；普通进程采用SCHED_NORMAL调度策

2、略。本文主要讨论普通进程的调度算法，为了描述方便，后面章节中的“进程”指“普通进程”。从Linux2.6.23内核到目前最新的Linux3.3.5内核的普通进程（采用调度策略SCHED_NORMAL）采用了绝对公平调度算法，CFS(completelyfairschedule)。CFS从RSDL/SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再区分交互式进程。它将所有的进程都统一对待，这就是公平的含义。CFS调度中，进程数据结构中的动态优先级成员prio还继续有效，只是内核不再动态调整进程

3、的动态优先级了。进程的优先级为100—139，对应的nice值为-20—19。和之前版本的优先级规定相同。Nice和优先级对应关系如下如何实现公平调度的？内核给每个进程维护了一个虚拟运行时间vruntime，每个进程运行一段时间后，虚拟运行时间会增加，但是运行同样的实际时间每个进程增加的数值是不同的。比如nice值为0的进程运行了10ms，其虚拟运行时间增加了1vms（vms为1虚拟毫秒，为了描述方便而定义）；nice为19的进程运行10ms，其虚拟运行时间增加了1000vms。进程在其生命周期中，

4、其虚拟运行时间一直都是在增加的。内核把虚拟运行时间看做实际运行时间，为了公平起见要选择运行时间短的进程进行运行。所以内核在调度中总是选择虚拟运行时间小的进程。对内核来说，这样就很公平了，O(∩_∩)O同样运行10ms，如何确定一个进程该增加多少vms？增加的虚拟运行时间和进程的优先级nice数值有关，每个nice数值对应一个权重数值，见下图。每个进程虚拟运行时间增加的时间量和（NICE_0_LOAD/nice_n_weight）成正比。其中NICE_0_LOAD为1024，即nice数值为0的权重，

5、nice_n_weight即为nice数值为n的进程的权重，如nice为-20（优先级最高的普通进程）的权重为88761。从这种算法也可以看出，优先级高的进程的虚拟运行时间增加的慢，其实际运行时间累计数值也就长。同样，这种算法能保证优先级低的进程也有运行机会，只是实际运行的时间比较短。内核要把所有running状态的进程放到一起，在需要调度时从中取出一个虚拟运行时间短的进程。因为发生调度的频率非常高，查找合适进程的算法就变的很重要了。在CFS调度中，内核采用了以进程虚拟运行时间为key值的红黑树数据

6、结构挂接各个running的进程。有关红黑树请参考《linux内核之红黑树》。先要引入一个重要概念，调度实体(schedentiy)：就是调度的对象。每个进程的task_struct包含了调度实体成员变量se。为何要引入调度实体，而不是直接使用进程的task_struct？是因为在CFS中支持CFS组调度，一个组中可能包含1个或多个进程。不能通过组中任何进程的task_struct来调度组，所以引入了调度实体的概念。为了统一起见，进程组和进程都使用调度实体保存调度相关的信息。后面会介绍CFS组调度。

7、在多核系统中，每个CPU（此处指一个核心）对应一个全局变量per_cpu_runqueues，其数据结构为structrq，该变量为调度的最顶层的数据结构。在该数据结构中包含了cfs，其数据结构为structcfs_rq。cfs就是在该cpu上CFS调度的顶级结构，或者说是CFS调度的入口点。其实rq中还包括了rt成员变量，rt是实时进程调度的顶级结构。structcfs_rq{为了说明方便，只保留部分成员变量structrb_roottasks_timeline;structrb_node*rb_

8、leftmost;structsched_entity*curr,*next,*last,*skip;}其中成员变量tasks_timeline指向了红黑树的根，所有的进程都挂到这棵红黑树上（有些是间接挂接的）。如下图中的单个进程，进程数据结构task_struct中包含了成员变量se，即调度实体。调度实体se中包含了run_node节点，se通过该节点挂接到红黑树上。在选择需要调度的进程时，内核将搜索这个红黑树，找到虚拟运行时间小的进程，并把该进程从树上摘下。同时会