Linux CFS调度算法分析

简岩

摘要：一个操作系统的核心是进程调度。那么操作系统最重要的程序之一则是进程调度程序，同时进程调度程序也是多任务操作系统执行频度最高的一部分，操作系统的整体性能也决定于进程调度程序的性能。本文剖析了从O(1)算法到CFS算法的演变。最后用测试工具对CFS的稳定性和计算速度进行了分析。

关键词：Linux调度O(1)CFS调度器红黑树

1 linux进程调度的概述

所谓进程调度就是指操作系统正确的匹配CPU时间之后来准确的执行等待中的进程。怎样从若干个可运行的进程里面找到其中最优先的进程执行的同时又能保证响应时间短、吞吐量高是进程调度的核心所在。进程调度有何时启动调度器和调度器执行什么调度算法两部分。

进程调度的要求就是吞吐量大、响应时间快、周转时间短以及效率高。由进程的响应时间Linux内核可以把进程分为三类：实时进程、批处理进程和交互进程。根据这三类进程内核又产生了三种不同的调度方法：先进先出策略（SCHED_FIFD）、轮转策略（SCHED_RR）和适合交互分时的程序（SCHED_OTHER）。

2 进程调度算法

①当CPU运行进程时，调度是被禁止的；只有当CPU处于无进程运行时，可以进入调度。

②当准备队列空闲时，执行缺省的idle-task、进程。

③当准备队列非空闲时，执行的进程需要调度器在准备队列中挑选出来。这时，goodness（）函数将会从调度器在准备队列中挑选出来的进程中计算其权值，只有权值最大才能有执行的优先级。

④如果经过goodness（）函数计算之后每个进程的权值均是0，则说明CPU所提供给实时进程的准备队列中进程的时间片全部用光了，需要进行重置之后返回步骤①，继续执行调度。

⑤当实时进程都执行完成之后，CPU将对普通进程开始支持。当每一个普通进程的权值均是0时，则说明CPU所提供给普通进程的准备队列中进程的时间片全部用光了，需要进行重置之后返回步骤①，继续执行调度。

3 linux从O(1)调度器到CFS调度器

3.1 O(1)调度器

在Linux新版本Linux2.6.22中，其内核采用的是O（1）调度器，其不仅仅能够支持SMP并且可以确保系统的负载和处理器的数目如何变化，其判断相对应的任务所匹配CPU所利用的时间是不变的。

有2种不同的任务是O（1）调度器的分内工作：

①计算动态任务优先级。利用公式dynamicpriority=max（100，min（staticpriority-bonus+5,139））进行计算。

②当拥有最高优先级的进程执行过程中，选择出下一个需要进行执行的进程。CPU利用调度器对所有进程进行了任务排队：expired数组与active数组。其数组中的某一元素寄存着该任务队列某一优先级的指针，如果需要判断下一个执行的进程时，并不需要将所有的队列进行遍历，只需要在active数组排列好的队列中直接选择优先级最高的进程进行执行。上述方法的复杂度是O（1）。

为了让交互式任务的响应速度变得更快，任何一次时钟中断里，处于执行的任务的时间片减一，如果时间片是O的时候，将对其类型进行判断，若是交互式任务，需要将时间片进行重置然后将active数组再次插入其中；若不是交互式任务，需要把active数组转到expired数组中，如此便可以让CPU优先被交互式任务所使用。当然，并不能够将进城长期的放在active数组里面，当CPU被交互式任务占用达到了一定的数值时，将会把任务转到expired数组中去。如果active数组处于空的状态时，则将两个数组进行互换，从而执行下一轮调度。

O（1）调度器的优点已经显而易见了，与此同时其算法也存在一些不可避免的缺陷，如执行导交互式任务的时候反应速度并不理想。多任务队列和动态优先级是O（1）调度器所应用的相对繁琐的方法，这样就迫使了调度器较为繁琐以及对代码维护的时候难度非常之大。此外，在实际使用的时候发现，相对于在类似于服务器等不存在较大的交互性应用需求的时候，在桌面应用这种对交互性要求很高的环境下，O（1）调度器的效果表现非常不理想。基于这种缺点，Ingo Molnar研发了新的完全公平调度器 (Completely Fair Scheduler，CFS)，此款调度器与O（1）调度器的框架完全不同，在Linux2.6.23版本中，就将CFS作为默认调度器进行使用。

3.2 CFS 调度器

3.2.1 算法的主要思想

CFS并没有采用以往的将进程进行排列分组以及进行动态的优先级分类，也没有采用睡眠时间的概念，同时也没有将任务分为交互任务和其他，CFS则是引入了一个新的概念——红黑树；所谓红黑树就利用时间来计算一个键值从而来选择下一个执行进程，进而利用全部进程所对CPU所利用的时间状态来调度任务。全部的准备状态中的进程被赋予的键值数值被放在红黑树的叶子节点上，按照键值从小到大一次排列在从左到右。在任何一个调度点上，调度器会从红黑树排列好的进程从左至右的对CPU进行进程的调度，这种执行的复杂度为O（log2N）。

在所有的时钟中断上面，其首要的任务是更新调度信息，其次是对红黑树上的排列好的进程进行进一步的调整。当检测到正在执行的进程并不是最左边的进程时，将对其进行need_resched标记，当执行中断返回的时候就要利用scheduler_tick（）来完成对进程的切换，如果没有这个过程，CPU将会被一直占用。

3.2.2 红黑树

CFS依靠进程的虚拟运行时间作为其变量，进而使用红黑树把每一个准备好执行的进程排列成“runqueue”。CFS将之前一直运用的FIFO以及Hash映射形式的线性“qunqueue”彻底移除，每一个runqueue都是利用红黑树来进行组成的。

红黑树的特点也是非常明显的：首先，红黑树上的每一个节点都能够保证一项规律，那就是该节点的左边节点永远小于该几点，相对的右边的节点就大于该节点，这就是之所以红黑树从左至右依次增大的效果；其次，红黑树上分布的所有节点都是均匀的，绝对不会出现不均匀的情况；最后，其操作代价非常低，插入、查找以及删除的代价都是0（logn）。在CFS实际的应用中，表现最为突出的还是第一条特点。

该算法中，每一个节点都作为virtual_runtime键值植入到红黑树里面，当有进程需要进行执行的时候，将键值进行更新之后植入到红黑树，之后从左至右的一次进行执行进程。

当CFS进行调度的过程中，其复杂度是O（logn），可是因为CFS具有实现代价低的特点，实际执行的过程中，反应速度反而快了很多。此外，Linux中的CFS还赋予了很多可操作性的功能，像可以进行灵活配置的调整选项等，这样可以让用户在任何情况之下都能够得到最好的性能体验。

3.2.3 源代码分析

我们参考内核2. 6. 24 源代码中的sched. c 和sched_fair. c来分析:

Scheduler_tick()函数是Sched.c中的一个函数，Scheduler_tick()函数改变当前的时间值与clock 值后CPU会刷新当前的负载情况，最后调用sched_class函数和task_tick( ) 函数。

static void task_tick_fair(struct rq* rq，struct task_struct * curr)

{

struct cfs_rq* cfs_rq;

struct sched_entity* se = ＆curr － > se;

for_each_sched_entity(se) {

cfs_rq = cfs_rq_of(se);

entity_tick(cfs_rq，se);

}

}

task_tick_fair函数的目的是使待调度任务执行entity_tick()函数:

static void entity_tick( struct cfs_rq * cfs_rq，struct sched _entity *

curr)

用函数dequeue_entity( )与enqueue_entity( )的主要目的是在红黑树里把任务删除在插入到红黑树里用来调整任务在红黑树里的位置。_pick_next_entity()函数是返回到CFS中红黑树的最左边的叶子节点，如果发现这个节点它不是当前的任务，那么就调用_check_preempt_

curr_fair( ) 设置调度标志，当中断返回时就会调用schedule_tick() 进行调度，替换当前任务。

参考文献：

[1]杜慧江.Linux内核2.6.24的CFS调度器分析[J].计算机应用与软件，2010(2).

[2]冯宇.Linux进程调度算法分析[J].计算机与现代化，2009(6).

[3]张永选.Linux 2.6 内核调度机制剖析与改进[J].计算机系统应用，2009(11).

endprint