CFS调度算法交互性能分析与增强

余飞 阳国贵

（国防科学技术大学，计算机学院，湖南，410072）

摘要：CFS算法具有较强的扩展能力，能较好地适应多种硬件平台，但研究发现，该算法在交互性方面存在明显不足。本文在深入分析CFS算法实现原理的基础上，对CFS算法以及O（1）算法的交互式性能进行对比分析，指出了CFS算法在进行交互式处理时存在的问题和不足，并提出了解决办法，测试结果显示，修改后的算法交互能力得到明显提高。

关键词：完全公平调度算法；O（1）算法；BFS算法；交互性；性能评价

Interactive Performance Analysis and Enhancement of Completely Fair Scheduling Algorithm

Yu Fei，Yang Guogui

（Computer School，National university of defence technology，Hunan，410072，China）

Abstract：CFS scheduling algorithm has strong scalability and can adapt to aVariety of hardware platforms.However，the study found that the interactive aspect of the algorithm has obvious shortcomings.Based on in-depth analysis of the algorithm’s principle and comparing with the O（1）algorithm，this paper pointed out the problems and the insufficiency of the CFS algorithm when dealing with the interactive processes and proposed a solution，the testing results showed that the modified algorithm can significantly improve the interactive ability.

Key words： Completely Fair Scheduling（CFS），O（1）scheduler algorithm，Brain Fuck Scheduler（BFS），Interactivity，Performance Evaluation

1 引言

过去的十年间，Linux操作系统的调度算法经历了许多重要的变化，从最初的O（n）算法到2002年的O（1）算法，再到2007年的CFS算法，算法本身发生了根本性的变化，适应能力也得到了空前的增强。随着新硬件架构的出现以及网络应用的发展，给调度器的设计带来了巨大的挑战。目前这种挑战主要来自两个方面：一是多片多核架构的广泛应用，调度器面对的是由不同方式（如SMP、NUMA）组织起来的多核众核处理器平台，如何增强调度器的可扩展性，发挥多处理器优势，提高系统吞吐率，成为商用服务器系统急需解决的重大难题；二是多媒体应用的不断发展，用户对系统响应速度的要求也越来越高，大力提高交互式进程的响应速度成为桌面应用领域的主要需求。CFS算法在扩展能力上较之早期的算法有了明显提升，使得Linux成为当前扩展能力最强的操作系统之一，不足的是，其交互性仍不能满足用户的需求。

本文分析了CFS算法的原理及其对交互式进程的处理方式，借鉴早期的O（1）算法以及2009年出现的BFS算法思想，提出对CFS算法的改进方法，以提高该算法对交互式进程的响应速度。第二节介绍CFS调度算法的原理，第三节对CFS算法的交互性能进行测试，第四节在分析CFS算法不足的基础上，提出改进方法，第五节对论文进行总结与展望。

2 CFS调度算法原理

CFS根据进程权重分配CPU时间，其计算公式如下：

其中，Wi为进程权重，ϕ是队列中可执行任务的集合，P为队列中所有任务执行一遍所耗费的总时间（以下简称轮转周期），其大小由队列中的进程数量决定：

sysctl_sched_latency，sched_nr_latency，sysctl_sched_min_granularity的值可以由用户设定，系统预设为20ms，5，4ms。CFS采用红黑树来组织进程队列，它为每个普通进程分配了一个调度实体se，每一个se对应红黑树上的一个节点，节点的键值为进程的虚拟运行时间（Virtual Runtime，VR），CFS即通过VR来保证各进程执行时间的公平性。假设是nice为0所对应的权重（即1024），则进程i在执行了t单位的时间后其VR的值为：

将公式（1）代入公式（3）中可知进程在某一个周期P内执行完自己的时间片后VR值为：

由此可以看出，在固定的轮转周期P内，权重越大的进程分得的时间片越大，其VR值增长得越慢，在一个周期P结束时，队列中的每个进程都循环执行了一遍，并且VR值都相同。如果某一进程的VR值小于其它进程的VR值，则它将会被放到红黑树的左侧而得以运行。CFS不将交互式进程和批处理进程区别对待，对于交互式进程，由于其单次运行的时间较短，睡眠时间较长，当它被唤醒时可能其VR值远小于红黑树中最左侧进程的VR值（min-vruntime），此时如果不对其VR值进行修正，则它将占用大量的CPU时间直至其VR值超过min-vruntime，从而导致其它进程饥饿。因此调度器在唤醒一个进程后将其VR值设置为：

修正后，进程的VR值仍然小于当前树中所有进程的VR值，因此将被放置于树的最左侧而得以最快运行，从而提高了交互式进程的响应速度。

3 CFS

算法交互性能分析

一般来说，交互式进程的平均延迟时间应在50～150ms，否则将会降低用户体验。因此，各类算法在设计时都充分考虑了用户的需求。原有的O（1）算法采用启发式计算，该算法在大多数情况下有效，但一些经典的程序（如fiftyp.c，thud.c等）总能让它的交互性能下降。并且张科等人通过研究发现O（1）算法存在误判，少数情况下会导致真正的交互式进程得不到及时响应。CFS抛弃了O（1）算法中复杂的启发式计算，将交互式进程与普通批处理进程同等对待，使得调度器的实现大大简化。

一般来说，交互式进程的平均延迟时间应在50～150ms，否则将会降低用户体验。因此，各类算法在设计时都充分考虑了用户的需求。原有的O（1）算法采用启发式计算，该算法在大多数情况下有效，但一些经典的程序（如fiftyp.c，thud.c等）总能让它的交互性能下降。并且张科等人通过研究发现O（1）算法存在误判，少数情况下会导致真正的交互式进程得不到及时响应。CFS抛弃了O（1）算法中复杂的启发式计算，将交互式进程与普通批处理进程同等对待，使得调度器的实现大大简化。

一般来说，交互式进程的平均延迟时间应在50～150ms，否则将会降低用户体验。因此，各类算法在设计时都充分考虑了用户的需求。原有的O（1）算法采用启发式计算，该算法在大多数情况下有效，但一些经典的程序（如fiftyp.c，thud.c等）总能让它的交互性能下降。并且张科等人通过研究发现O（1）算法存在误判，少数情况下会导致真正的交互式进程得不到及时响应。CFS抛弃了O（1）算法中复杂的启发式计算，将交互式进程与普通批处理进程同等对待，使得调度器的实现大大简化。

为了验证CFS在交互性方面对O（1）算法改进的有效性，本文使用Interbench测试工具对这两种算法的交互式性能进行测试。Interbench可以测试调度器在不同的负载背景下对交互式进程的响应延时，这里选择两类不同的应用进行对比分析：一类是音频播放类应用，这种应用每间隔50ms发出一次请求，占用大约5%的处理器时间，测试结果如图1和图2所示。另一类是X-window类应用，它模拟的是用户进行桌面操作时的行为，用户的输入具有一定的随机性，测试结果如图4和图5所示。从测试的结果看，在音频类应用中，CFS算法的延迟总体比O（1）算法低，并且O（1）存在最坏的情况，如在编译负载下最大延迟达到19.6ms。在X-window类应用中，O（1）算法的表现比CFS要好，CFS的最大延迟达到136ms，远远超过O（1）算法的10ms。由此可以看出，CFS对O（1）算法在交互性能方面的改进相对有限。正是由于CFS算法的交互性能不强，催生出了BFS算法，该算法将交互式进程单独列为一类进行调度。Taylor等人通过测试，认为在周转时间方面，CFS优于BFS，而 BFS 的调度延迟小于 CFS，且交互性相对要好一些。但BFS以损失扩展性为代价来提高交互性，难以被主流操作系统接受。

4 CFS算法的不足及改进

CFS算法的交互式处理存在较坏的情况。如运行队列中有n个可运行的进程，轮转周期可以由公式2计算得出，n越大，轮转周期就越长。假设某一轮调度的时间分配如下图所示：

进程T0在时刻t0接收到用户操作，该操作需要δ单位时间进行处理，即运行到时刻t2才能给出响应，但由于T0剩余的时间不足δ，处理器在时刻t1进行进程切换，开始运行进程T1，则T0剩下的操作只能推迟到下一轮循环中进行，即从t3处继续运行，t4处给出响应结果。t0至t4即为此次操作的响应时间t，它的大小与轮转周期P有关。而CFS中，周期P是经常变化的，如果在进程T0两次执行期间有多个进程产生或唤醒，按照CFS算法，新产生或唤醒的进程将会得到运行，并且唤醒的进程还会获得一定时间的补偿。当系统中运行的进程数量较多时，一方面，周期P较大，另一方面，上述情况出现的可能性也较大，导致此次用户操作的响应变得不可预测。因此，CFS将交互式进程与普通批处理进程同等对待的作法一定程度上损失了交互性。

为提高CFS算法的响应速度，本文实现了一个与O（1）算法截然相反的方法。即通过跟踪进程的行为来鉴别计算集中类的进程，通过提高该类进程的nice值来增加交互式进程的运行机会，以间接实现交互式进程对计算集中类进程的抢占。这样做的好处有三个：一是计算集中类的进程容易鉴别，很难存在误判的情况；二是缩短轮转周期，使得上述较差情况下的响应时间t减小；三是该方法与CFS结合时，不会出现像O（1）算法中被误判为交互式进程的I/O集中类进程驻留活跃数组，导致真正的交互式进程因运行时间超过阈值而被放入过期数组中长期得不到运行的情况。nice值增加在调度函数scheduler（ ）中进行，增加的条件由以下公式计算：

sum_exec_time＞sum_sleep_time×（nice_add＋1）2×f（sum_exe_time＞τ）

其中，sum_sleep_time是进程睡眠总时间，sum_exec_time是进程执行总时间，可在调度器内统计获得，nice_add是在进程调度实体结构中增加的nice变化量，默认为0。f是一个可以调节的因子，决定nice值增加的快慢，在八核ccNUMA架构的PowerEdge T710服务器上进行测试时使用1000的值，表示了解进程特性需要跟踪的时间，测试中使用100ms的值。Nice值调整最大不超过3，因为进程nice值每提升1，执行时间将减少10%，调整过多容易导致进程饥饿。同时，为了防止误判，nice值增加的难度是递增的。修改相应的内核代码并编译重启后，使用Interbench工具对修改前后的CFS调度器进行测试，其结果如下：音频类应用的测试结果如图1和图3所示，修改后的算法平均延迟较CFS有了一定的降低，但改进不太明显，其原因是该类应用请求的频度不高，每次需要处理的时间较短，减少背景负载的执行时间对其响应速度提升不明显，但X_window类应用有较明显的改进，在刻录及编译负载下，最大延迟从115、136降至90、100，平均延迟也从10.6、9.8降至7.8、6.7ms，说明当背景负载的nice值增加后，更容易被交互式进程替换，从而降低了交互式进程的响应时间。

5 结束语

本文通过对CFS算法进行改进，在一定程度上提高了CFS的交互性能，但仍不能保证交互式操作在可预期的时间内得到响应。随着桌面应用的不断发展，未来调度算法设计必须充分考虑交互式进程的需求，提高其对批处理进程的抢占能力，以降低系统的响应时间。

作者简介

余飞，1984生，男，安徽省潜山县人，硕士研究生，主要研究领域为操作系统线程调度，yufei84@yahoo.cn，湖南长沙国防科技大学计算机学院六队，15874182682；

阳国贵，1964生，男，湖南冷水江人，博士，研究员，主要研究领域为操作系统线程调度，csmydb@126.com。