基于Linux内核的CFS调度算法研究.pdf

《基于Linux内核的CFS调度算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CFS随着Linux内核的／fi断发展，Linux已经被许多人视为是未来最彳j．前途的操作系统之一。进程调度是Linux操作系统的核心功能，在Linux的发展史上二起着非常重要的作用，不同的算法对系统性能的影响也是不一样的。2．4内核的0(n)算法和早期2．6内核的O(1)算法都是以往调度算法中的经典算法，但是存在着一些缺点。2．6．23内核发布的CFS算法将公平的理念用到调度算法中，具钉划时代的意义。本文将在研究以往调度算法优缺点的基础上重点介绍CFS调度算法。2．Linux2．4与Linux2．6调度算法简介2．1Linux2．4内核调度算法2．4内

2、核采用的调度算法是基于优先级的设计。它存每次进程切换时，内核扫描町运行进程的链表，计算进程的优先级，然后选择“最佳”进程来运行⋯。通过对2．4调度算法研究，发现存在以下几个缺点：(1)开销太大：选择最佳进程所要消耗的时『日J与町运行的进程数量相关，凶此达不到实时性的要求。(2)内核小支持抢占：当进程处于内核态时不会发生抢占，这对真正的实时应用是不能接受的。(3)SMP效率：在2．4内核中，就绪进程队列是一。个全局数据结构，调度算法对它的所，fr操作都会

3、人l全局自旋锁而导致系统各个处理机之间的等待，这将导致大部分的CPU处于空闲状态，从而影响SMP效率[

4、21。2．2Linux2．6内核调度算法针对2．4内核的缺点，IngoMolnar设计并实现了早期2．6内核的调度算法，它的算法复杂度为O(1)，所以又叫O(1)算法。它继承和发扬了2．4内核调度算法的特点，极人地改善了0(n)调度算法的缺陷。首先，O(1)调度算法所花费的时间为常数，与当前系统中的进程个数无关。其次，它支持内核态抢占，更好地支持了实时进程。最后，增强了SMP的可扩展性，每个处理器拥有独市的运行队列和自旋锁，不会产生互斥13】，极大地提高了SMP效率。在O(1)算法中，每个CPU都有一个运行队列，每个运行队列是一个二元数组arrays，按

5、时间片是否J}}J完分为两个队列和两个队列指针14I，指针active指向时间片没用完、当前作者简介：刘婷，女，安徽蚌埠人，硕士研究生。间片之后，它就被移动到expired队列中。在移动过程中，调度算法会对其时间片重新进行计算。当active队列中没有就绪进程时，active和expired两个指针将执行互换操作。相比O(n)算法，O(1)算法在交互性方面有很大的改进，它实现了基十进程过去行为的启发式算法，以确定进程应该被当作交白：式进程还是批处理进程。fH是，它对于交瓦式应用仍然存在响应件差的^d题，对NUMA支持也不完善。为了解决这磐^d题，大苣代石

6、f5被加入调度算法中，虽然很多性能问题得到了解决，但是代码很复杂且难以维护和阅读。3．CFS算法在Linux2．6．23内核中发布了一种新的调度算法——CFS算法，CFS是“CompletelyFairScheduler”的缩写，它主要是改进早期2．6内核调度算法的代码复杂度的^d题，使调度算法变得更加简单有效。它的出现彻底改变r内核看待进程调度的方式，不再依赖划分时间片和增加抢占点。0(1)算法的事要复杂性来自动态优先级的计算，调度算法根据甲均睡眠时间和一些很难理解的经验公式来修正进程的优先级以区分交互式进程和批处理进程。这样的代码很难阅读和维护。相比

7、O(1)算法，CFS算法思路简单，抛弃了时间片和复杂的算法，它总足试图按照对CPU时间的最大需求运行进程，这彳r助于确保每个进程町以获得对CPU的公平共享。3．1CFS算法基本理论通过研究Linux2．6．23内核发现，CFS算法从RSDL／SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再企图l叉：分交互式进程。它将所有的进程都统一对待，这就是公甲的含义。但足所谓的公平并不是绝对公平，而是相对公平。在以往的调度算法中，当给一个进程分配40ms的CPU计算时间时，它会一直占有CPU，其它进程必须等待，这就产生不公平。但足对于CFS算法，它会将40

8、ms的CPU计算时间根据优先级比例分配给不同的进程，使每个进程都能牛日对公平地获得CPU的执行时间。3．1．1CFS算法主要思想CFS算法的核心思想是围绕着虚拟时钟展开的。虚拟时钟区别十硬件的实际时钟，虚拟时钟町以根据权重调节步调，一6l一按照不同的步调前进。而实际时钟是按着同定的步调前进，不能改变。每个处理器不仪维护实际的时钟，还任对应的运行队列维护着一个虚拟时钟，它的前进步伐与该处理器上的进程总权重成反比。总权重越大，虚拟时钟前进的步伐越慢。l司时，每个进程也有自己的虚拟时钟，它记录着进程已经占用CPU的虚拟时间。它的前进步伐与进程的权重成反比。进程

9、的权重对应进程的优先级，对丁不同优先级的迸程，一般来说，优先级低的进程其虚拟时钟