调度器

“调度器”

Linux Kernel调度器的过去，现在和未来

https://my.oschina.net/u/4585157/blog/4672238

调度器简介，以及Linux的调度策略

进程是操作系统虚拟出来的概念，用来组织计算机中的任务。但随着进程被赋予越来越多的任务，进程好像有了真实的生命，它从诞生就随着CPU时间执行，直到最终消失。不过，进程的生命都得到了操作系统内核的关照。就好像疲于照顾几个孩子的母亲内核必须做出决定，如何在进程间分配有限的计算资源，最终让用户获得最佳的使用体验。内核中安排进程执行的模块称为调度器 (scheduler) 。这里将介绍调度器的工作方式。

进程状态

调度器可以切换进程状态 (process state) 。一个Linux进程从被创建到死亡，可能会经过很多种状态，比如执行、暂停、可中断睡眠、不可中断睡眠、退出等。我们可以把Linux下繁多的进程状态，归纳为三种基本状态。

就绪 (Ready) : 进程已经获得了CPU以外的所有必要资源，如进程空间、网络连接等。就绪状态下的进程等到CPU，便可立即执行。 执行 (Running) : 进程获得CPU，执行程序。 阻塞 (Blocked) : 当进程由于等待某个事件而无法执行时，便放弃CPU，处于阻塞状态。

进程创建后，就自动变成了就绪状态。如果内核把CPU时间分配给该进程，那么进程就从就绪状态变成了执行状态。在执行状态下，进程执行指令，最为活跃。正在执行的进程可以主动进入阻塞状态，比如这个进程需要将一部分硬盘中的数据读取到内存中。在这段读取时间里，进程不需要使用CPU，可以主动进入阻塞状态，让出CPU。当读取结束时，计算机硬件发出信号，进程再从阻塞状态恢复为就绪状态。进程也可以被迫进入阻塞状态，比如接收到SIGSTOP信号。

调度器是CPU时间的管理员。Linux调度器需要负责做两件事: 一件事是选择某些就绪的进程来执行；另一件事是打断某些执行中的进程，让它们变回就绪状态。不过，并不是所有的调度器都有第二个功能。有的调度器的状态切换是单向的，只能让就绪进程变成执行状态，不能把正在执行中的进程变回就绪状态。支持双向状态切换的调度器被称为抢占式 (pre-emptive) 调度器。

调度器在让一个进程变回就绪时，就会立即让另一个就绪的进程开始执行。多个进程接替使用CPU，从而最大效率地利用CPU时间。当然，如果执行中进程主动进入阻塞状态，那么调度器也会选择另一个就绪进程来消费CPU时间。所谓的上下文切换 (context switch) 就是指进程在CPU中切换执行的过程。内核承担了上下文切换的任务，负责储存和重建进程被切换掉之前的CPU状态，从而让进程感觉不到自己的执行被中断。应用程序的开发者在编写计算机程序时，就不用专门写代码处理上下文切换了。

进程的优先级

调度器分配CPU时间的基本依据，就是进程的优先级。根据程序任务性质的不同，程序可以有不同的执行优先级。根据优先级特点，我们可以把进程分为两种类别。

实时进程 (Real-Time Process) : 优先级高、需要尽快被执行的进程。它们一定不能被普通进程所阻挡，例如视频播放、各种监测系统。 普通进程 (Normal Process) : 优先级低、更长执行时间的进程。例如文本编译器、批处理一段文档、图形渲染。 普通进程根据行为的不同，还可以被分成互动进程 (interactive process) 和批处理进程 (batch process) 。互动进程的例子有图形界面，它们可能处在长时间的等待状态，例如等待用户的输入。一旦特定事件发生，互动进程需要尽快被激活。一般来说，图形界面的反应时间是50到100毫秒。批处理进程没有与用户交互的，往往在后台被默默地执行。

实时进程由Linux操作系统创造，普通用户只能创建普通进程。两种进程的优先级不同，实时进程的优先级永远高于普通进程。进程的优先级是一个0到139的整数。数字越小，优先级越高。其中，优先级0到99留给实时进程，100到139留给普通进程。

一个普通进程的默认优先级是120。我们可以用命令nice来修改一个进程的默认优先级。例如有一个可执行程序叫app，执行命令:

$nice -n -20 ./app 命令中的-20指的是从默认优先级上减去20。通过这个命令执行app程序，内核会将app进程的默认优先级设置成100，也就是普通进程的最高优先级。命令中的-20可以被换成-20至19中任何一个整数，包括-20 和 19。默认优先级将会变成执行时的静态优先级 (static priority) 。调度器最终使用的优先级根据的是进程的动态优先级:

动态优先级 = 静态优先级 – Bonus + 5

如果这个公式的计算结果小于100或大于139，将会取100到139范围内最接近计算结果的数字作为实际的动态优先级。公式中的Bonus是一个估计值，这个数字越大，代表着它可能越需要被优先执行。如果内核发现这个进程需要经常跟用户交互，将会把Bonus值设置成大于5的数字。如果进程不经常跟用户交互，内核将会把进程的Bonus设置成小于5的数。

O(n)和O(1)调度器 下面介绍Linux的调度策略。最原始的调度策略是按照优先级排列好进程，等到一个进程运行完了再运行优先级较低的一个，但这种策略完全无法发挥多任务系统的优势。因此，随着时间推移，操作系统的调度器也多次进化。

先来看Linux 2.4内核推出的O(n)调度器。O(n)这个名字，来源于算法复杂度的大O表示法。大O符号代表这个算法在最坏情况下的复杂度。字母n在这里代表操作系统中的活跃进程数量。O(n)表示这个调度器的时间复杂度和活跃进程的数量成正比。

O(n)调度器把时间分成大量的微小时间片 (Epoch) 。在每个时间片开始的时候，调度器会检查所有处在就绪状态的进程。调度器计算每个进程的优先级，然后选择优先级最高的进程来执行。一旦被调度器切换到执行，进程可以不被打扰地用尽这个时间片。如果进程没有用尽时间片，那么该时间片的剩余时间会增加到下一个时间片中。

O(n)调度器在每次使用时间片前都要检查所有就绪进程的优先级。这个检查时间和进程中进程数目n成正比，这也正是该调度器复杂度为O(n)的原因。当计算机中有大量进程在运行时，这个调度器的性能将会被大大降低。也就是说，O(n)调度器没有很好的可拓展性。O(n)调度器是Linux 2.6之前使用的进程调度器。当Java语言逐渐流行后，由于Java虚拟机会创建大量进程，调度器的性能问题变得更加明显。

为了解决O(n)调度器的性能问题，O(1)调度器被发明了出来，并从Linux 2.6内核开始使用。顾名思义，O(1)调度器是指调度器每次选择要执行的进程的时间都是1个单位的常数，和系统中的进程数量无关。这样，就算系统中有大量的进程，调度器的性能也不会下降。O(1)调度器的创新之处在于，它会把进程按照优先级排好，放入特定的数据结构中。在选择下一个要执行的进程时，调度器不用遍历进程，就可以直接选择优先级最高的进程。

和O(n)调度器类似，O(1)也是把时间片分配给进程。优先级为120以下的进程时间片为:

(140–priority)×20毫秒

优先级120及以上的进程时间片为:

(140–priority)×5 毫秒

O(1)调度器会用两个队列来存放进程。一个队列称为活跃队列，用于存储那些待分配时间片的进程。另一个队列称为过期队列，用于存储那些已经享用过时间片的进程。O(1)调度器把时间片从活跃队列中调出一个进程。这个进程用尽时间片，就会转移到过期队列。当活跃队列的所有进程都被执行过后，调度器就会把活跃队列和过期队列对调，用同样的方式继续执行这些进程。

上面的描述没有考虑优先级。加入优先级后，情况会变得复杂一些。操作系统会创建140个活跃队列和过期队列，对应优先级0到139的进程。一开始，所有进程都会放在活跃队列中。然后操作系统会从优先级最高的活跃队列开始依次选择进程来执行，如果两个进程的优先级相同，他们有相同的概率被选中。执行一次后，这个进程会被从活跃队列中剔除。如果这个进程在这次时间片中没有彻底完成，它会被加入优先级相同的过期队列中。当140个活跃队列的所有进程都被执行完后，过期队列中将会有很多进程。调度器将对调优先级相同的活跃队列和过期队列继续执行下去。过期队列和活跃队列，如图2所示。

图2 过期队列和活跃队列 (需要替换)

我们下面看一个例子，有五个进程，如表1所示。

表1 进程

Linux操作系统中的进程队列 (run queue) ，如表2所示。

表2 进程队列

那么在一个执行周期，被选中的进程依次是先A，然后B和C，随后是D，最后是E。

注意，普通进程的执行策略并没有保证优先级为100的进程会先被执行完进入结束状态，再执行优先级为101的进程，而是在每个对调活跃和过期队列的周期中都有机会被执行，这种设计是为了避免进程饥饿 (starvation) 。所谓的进程饥饿，就是优先级低的进程很久都没有机会被执行。

我们看到，O(1)调度器在挑选下一个要执行的进程时很简单，不需要遍历所有进程。但是它依然有一些缺点。进程的运行顺序和时间片长度极度依赖于优先级。比如，计算优先级为100、110、120、130和139这几个进程的时间片长度，如表3所示。

表3 进程的时间片长度

从表格中你会发现，优先级为110和120的进程的时间片长度差距比120和130之间的大了10倍。也就是说，进程时间片长度的计算存在很大的随机性。O(1)调度器会根据平均休眠时间来调整进程优先级。该调度器假设那些休眠时间长的进程是在等待用户互动。这些互动类的进程应该获得更高的优先级，以便给用户更好的体验。一旦这个假设不成立，O(1)调度器对CPU的调配就会出现问题。

完全公平调度器 从2007年发布的Linux 2.6.23版本起，完全公平调度器 (CFS，Completely Fair Scheduler) 取代了O(1)调度器。CFS调度器不对进程进行任何形式的估计和猜测。这一点和O(1)区分互动和非互动进程的做法完全不同。

CFS调度器增加了一个虚拟运行时 (virtual runtime) 的概念。每次一个进程在CPU中被执行了一段时间，就会增加它虚拟运行时的记录。在每次选择要执行的进程时，不是选择优先级最高的进程，而是选择虚拟运行时最少的进程。完全公平调度器用一种叫红黑树的数据结构取代了O(1)调度器的140个队列。红黑树可以高效地找到虚拟运行最小的进程。

我们先通过例子来看CFS调度器。假如一台运行的计算机中本来拥有A、B、C、D四个进程。内核记录着每个进程的虚拟运行时，如表4所示。

表4 每个进程的虚拟运行时

系统增加一个新的进程E。新创建进程的虚拟运行时不会被设置成0，而会被设置成当前所有进程最小的虚拟运行时。这能保证该进程被较快地执行。在原来的进程中，最小虚拟运行时是进程A的1 000纳秒，因此E的初始虚拟运行时会被设置为1 000纳秒。新的进程列表如表5所示。

表5 新的进程列表

假如调度器需要选择下一个执行的进程，进程A会被选中执行。进程A会执行一个调度器决定的时间片。假如进程A运行了250纳秒，那它的虚拟运行时增加。而其他的进程没有运行，所以虚拟运行时不变。在A消耗完时间片后，更新后的进程列表，如表6所示。

表6 更新后的进程列表

可以看到，进程A的排序下降到了第三位，下一个将要被执行的进程是进程E。从本质上看，虚拟运行时代表了该进程已经消耗了多少CPU时间。如果它消耗得少，那么理应优先获得计算资源。

按照上述的基本设计理念，CFS调度器能让所有进程公平地使用CPU。听起来，这让进程的优先级变得毫无意义。CFS调度器也考虑到了这一点。CFS调度器会根据进程的优先级来计算一个时间片因子。同样是增加250纳秒的虚拟运行时，优先级低的进程实际获得的可能只有200纳秒，而优先级高的进程实际获得可能有300纳秒。这样，优先级高的进程就获得了更多的计算资源。

以上就是调度器的基本原理，以及Linux用过的几种调度策略。调度器可以更加合理地把CPU时间分配给进程。现代计算机都是多任务系统，调度器在多任务系统中起着顶梁柱的作用。

https://juejin.im/post/6844903556131061773

Linux 调度器发展简述

摘要

引言 进程调度是操作系统的核心功能。调度器只是是调度过程中的一部分，进程调度是非常复杂的过程，需要多个系统协同工作完成。本文所关注的仅为调度器，它的主要工作是在所有 RUNNING 进程中选择最合适的一个。

引言

进程调度是操作系统的核心功能。调度器只是是调度过程中的一部分，进程调度是非常复杂的过程，需要多个系统协同工作完成。本文所关注的仅为调度器，它的主要工作是在所有 RUNNING 进程中选择最合适的一个。作为一个通用操作系统，Linux 调度器将进程分为三类:

交互式进程

此类进程有大量的人机交互，因此进程不断地处于睡眠状态，等待用户输入。典型的应用比如编辑器 vi。此类进程对系统响应时间要求比较高，否则用户会感觉系统反应迟缓。

批处理进程

此类进程不需要人机交互，在后台运行，需要占用大量的系统资源。但是能够忍受响应延迟。比如编译器。

实时进程

实时对调度延迟的要求最高，这些进程往往执行非常重要的操作，要求立即响应并执行。比如视频播放软件或飞机飞行控制系统，很明显这类程序不能容忍长时间的调度延迟，轻则影响电影放映效果，重则机毁人亡。

根据进程的不同分类 Linux 采用不同的调度策略。对于实时进程，采用 FIFO 或者 Round Robin 的调度策略。对于普通进程，则需要区分交互式和批处理式的不同。传统 Linux 调度器提高交互式应用的优先级，使得它们能更快地被调度。而 CFS 和 RSDL 等新的调度器的核心思想是"完全公平”。这个设计理念不仅大大简化了调度器的代码复杂度，还对各种调度需求的提供了更完美的支持。

在探讨CFS和RSDL之前，我们首先回顾一下Linux2.4和Linux2.6.0中所使用的调度器。

内核调度器的简单历史

2.1 Linux2.4 的调度器 Linux2.4.18 中使用的调度器采用基于优先级的设计，这个调度器和 Linus 在 1992 年发布的调度器没有大的区别。该调度器的 pick next 算法非常简单: 对 runqueue 中所有进程的优先级进行依次进行比较，选择最高优先级的进程作为下一个被调度的进程。(Runqueue 是 Linux 内核中保存所有就绪进程的队列) 。术语 pick next 用来指从所有候选进程中挑选下一个要被调度的进程的过程。

每个进程被创建时都被赋予一个时间片。时钟中断递减当前运行进程的时间片，当进程的时间片被用完时，它必须等待重新赋予时间片才能有机会运行。 Linux2.4 调度器保证只有当所有 RUNNING 进程的时间片都被用完之后，才对所有进程重新分配时间片。这段时间被称为一个 epoch。这种设计保证了每个进程都有机会得到执行。

各种进程对调度的需求并不相同，Linux2.4 调度器主要依靠改变进程的优先级，来满足不同进程的调度需求。事实上，所有后来的调度器都主要依赖修改进程优先级来满足不同的调度需求。

实时进程

实时进程的优先级是静态设定的，而且始终大于普通进程的优先级。因此只有当 runqueue 中没有实时进程的情况下，普通进程才能够获得调度。

实 时进程采用两种调度策略: SCHED_FIFO 和 SCHED_RR。FIFO 采用先进先出的策略，对于所有相同优先级的进程，最先进入 runqueue 的进程总能优先获得调度；Round Robin 采用更加公平的轮转策略，使得相同优先级的实时进程能够轮流获得调度。

普通进程

对 于普通进程，调度器倾向于提高交互式进程的优先级，因为它们需要快速的用户响应。普通进程的优先级主要由进程描述符中的 Counter 字段决定 (还要加上 nice 设定的静态优先级) 。进程被创建时子进程的 counter 值为父进程 counter 值的一半，这样保证了任何进程不能依靠不断地 fork() 子进程从而获得更多的执行机会。

Linux2.4调度器是如何提高交互式进程 的优先级的呢？如前所述，当所有 RUNNING 进程的时间片被用完之后，调度器将重新计算所有进程的 counter 值，所有进程不仅包括 RUNNING 进程，也包括处于睡眠状态的进程。处于睡眠状态的进程的 counter 本来就没有用完，在重新计算时，他们的 counter 值会加上这些原来未用完的部分，从而提高了它们的优先级。交互式进程经常因等待用户输入而处于睡眠状态，当它们重新被唤醒并进入 runqueue 时，就会优先于其它进程而获得 CPU。从用户角度来看，交互式进程的响应速度就提高了。

该调度器的主要缺点:

可扩展性不好: 调度器选择进程时需要遍历整个 runqueue 从中选出最佳人选，因此该算法的执行时间与进程数成正比。另外每次重新计算 counter 所花费的时间也会随着系统中进程数的增加而线性增长，当进程数很大时，更新 counter 操作的代价会非常高，导致系统整体的性能下降。

高负载系统上的调度性能比较低: 2.4的调度器预分配给每个进程的时间片比较大，因此在高负载的服务器上，该调度器的效率比较低，因为平均每个进程的等待时间于该时间片的大小成正比。

交互式进程的优化并不完善: Linux2.4 识别交互式进程的原理基于以下假设，即交互式进程比批处理进程更频繁地处于SUSPENDED状态。然而现实情况往往并非如此，有些批处理进程虽然没有用 户交互，但是也会频繁地进行IO操作，比如一个数据库引擎在处理查询时会经常地进行磁盘IO，虽然它们并不需要快速地用户响应，还是被提高了优先级。当系 统中这类进程的负载较重时，会影响真正的交互式进程的响应时间。

对实时进程的支持不够: Linux2.4内核是非抢占的，当进程处于内核态时不会发生抢占，这对于真正的实时应用是不能接受的。

为了解决这些问题，Ingo Molnar开发了新的O(1)调度器，在CFS和RSDL之前，这个调度器不仅被Linux2.6采用，还被backport到Linux2.4中，很多商业的发行版本都采用了这个调度器。

2.2 Linux2.6的O(1)调度器 从 名字就可以看出O(1)调度器主要解决了以前版本中的扩展性问题。O(1)调度算法所花费的时间为常数，与当前系统中的进程个数无关。此外 Linux2.6内核支持内核态抢占，因此更好地支持了实时进程。相对于前任，O (1) 调度器还更好地区分了交互式进程和批处理式进程。

Linux2.6内核也支持三种调度策略。其中SCHED_FIFO和SCHED_RR用于实时进程，而SCHED_NORMAL用于普通进程。O(1)调度器在两个方面修改了Linux2.4调度器，一是进程优先级的计算方法；二是pick next算法。

2.2.1 进程的优先级计算

普通进程的优先级计算

普通进程优先级是动态计算的，计算公式中包含了静态优先级。一般来讲，静态优先级越高，进程所能分配到的时间片越长，用户可以通过nice系统调用修改进程的静态优先级。

动态优先级由

公式一 计算得出: 公式一 dynamic priority = max (100, min ( static priority – bonus +5, 139))复制代码 其中bonus 取决于进程的平均睡眠时间。由此可以看出，在linux2.6中，一个普通进程的优先级和平均睡眠时间的关系为: 平均睡眠时间越长，其bonus越大，从而得到更高的优先级。

平均睡眠时间也被用来判断进程是否是一个交互式进程。如果满足下面的公式，进程就被认为是一个交互式进程:

公式二 Dynamic priority ≤ 3 x static priority /4 + 28复制代码 平 均睡眠时间是进程处于等待睡眠状态下的时间，该值在进程进入睡眠状态时增加，而进入RUNNING状态后则减少。该值的更新时机分布在很多内核函数内: 时 钟中断scheduler_tick()；进程创建；进程从TASK_INTERRUPTIBLE状态唤醒；负载平衡等。

实时进程的优先级计算

实时进程的优先级由sys_sched_setschedule()设置。该值不会动态修改，而且总是比普通进程的优先级高。在进程描述符中用rt_priority域表示。

2.2.2 pick next算法

普 通进程的调度选择算法基于进程的优先级，拥有最高优先级的进程被调度器选中。2.4中，时间片counter同时也表示了一个进程的优先级。2.6中时间 片用任务描述符中的time_slice域表示，而优先级用prio (普通进程) 或者rt_priority (实时进程) 表示。

调度器为每一个CPU维护了两个进程队列数组: active数组和expire数组。数组中的元素着保存某一优先级的进程队列指针。系统一共有140个不同的优先级，因此这两个数组大小都是140。

当 需要选择当前最高优先级的进程时，2.6调度器不用遍历整个runqueue，而是直接从active数组中选择当前最高优先级队列中的第一个进程。假设 当前所有进程中最高优先级为50(换句话说，系统中没有任何进程的优先级小于50)。则调度器直接读取active[49]，得到优先级为50的进程队列 指针。该队列头上的第一个进程就是被选中的进程。这种算法的复杂度为O(1)，从而解决了2.4调度器的扩展性问题。

为了实现上述算法 active数组维护了一个bitmap，当某个优先级别上有进程被插入列表时，相应的比特位就被置位。Sched_find_first_bit()函 数查询该bitmap，返回当前被置位的最高优先级的数组下标。在上例中sched_find_first_bit函数将返回49。在IA处理器上可以通 过bsfl等指令实现。

为了提高交互式进程的响应时间，O(1)调度器不仅动态地提高该类进程的优先级，还采用以下方法:

每 次时钟tick中断中，进程的时间片(time_slice)被减一。当time_slice为0时，调度器判断当前进程的类型，如果是交互式进程或者实 时进程，则重置其时间片并重新插入active数组。如果不是交互式进程则从active数组中移到expired数组。这样实时进程和交互式进程就总能 优先获得CPU。然而这些进程不能始终留在active数组中，否则进入expire数组的进程就会产生饥饿现象。当进程已经占用CPU时间超过一个固定 值后，即使它是实时进程或者交互式进程也会被移到expire数组中。

当active数组中的所有进程都被移到expire数组中后，调度器交换active数组和expire数组。当进程被移入expire数组时，调度器会重置其时间片，因此新的active数组又恢复了初始情况，而expire数组为空，从而开始新的一轮调度。

2.2.3 O(1)调度器小节

Linux2.6调度器改进了前任调度器的可扩展性问题，schedule()函数的时间复杂度为O(1)。这取决于两个改进:

一．Pick next算法借助于active数组，无需遍历runqueue；

二．取消了定期更新所有进程counter的操作，动态优先级的修改分布在进程切换，时钟tick中断以及其它一些内核函数中进行。

O(1)调度器区分交互式进程和批处理进程的算法与以前虽大有改进，但仍然在很多情况下会失效。有一些著名的程序总能让该调度器性能下降，导致交互式进程反应缓慢:

fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c 这些不足催生了Con Kolivas的楼梯调度算法SD，以及后来的改进版本RSDL。Ingo Molnar在RSDL之后开发了CFS，并最终被2.6.23内核采用。接下来我们开始介绍这些新一代调度器。

回页首

3 新一代调度器 Linux2.6.0 发布之前，很多人都担心调度器存在的问题将阻碍新版本的发布。它对于交互式应用仍然存在响应性差的问题，对NUMA支持也不完善。为了解决这些问题，大量 难以维护和阅读的复杂代码被加入Linux2.6.0的调度器模块，虽然很多性能问题因此得到了解决，可是另外一个严重问题始终困扰着许多内核开发者。那 就是代码的复杂度问题。

Con Kolivas，在2004年提出了第一个改进调度器设计的patch: staircase scheduler。为调度器设计提供了一个新的思路。之后的RSDL和CFS都基于SD的许多基本思想。本章中，我们将简要探讨这三个主要的调度器算法。

3.1 楼梯调度算法 staircase scheduler 楼梯算法(SD)在思路上和O(1)算法有很大不同，它抛弃了动态优先级的概念。而采用了一种完全公平的思路。前任算法的主要复杂性来自动态优先级的计算，调度器根据平均睡眠时间和一些很难理解的经验公式来修正进程的优先级以及区分交互式进程。这样的代码很难阅读和维护。

楼梯算法思路简单，但是实验证明它对应交互式进程的响应比其前任更好，而且极大地简化了代码。

和O(1)算法一样，楼梯算法也同样为每一个优先级维护一个进程列表，并将这些列表组织在active数组中。当选取下一个被调度进程时，SD算法也同样从active数组中直接读取。

与 O(1)算法不同在于，当进程用完了自己的时间片后，并不是被移到expire数组中。而是被加入active数组的低一优先级列表中，即将其降低一个级 别。不过请注意这里只是将该任务插入低一级优先级任务列表中，任务本身的优先级并没有改变。当时间片再次用完，任务被再次放入更低一级优先级任务队列中。 就象一部楼梯，任务每次用完了自己的时间片之后就下一级楼梯。

任务下到最低一级楼梯时，如果时间片再次用完，它会回到初始优先级的下一级任 务队列中。比如某进程的优先级为1，当它到达最后一级台阶140后，再次用完时间片时将回到优先级为2的任务队列中，即第二级台阶。不过此时分配给该任务 的time_slice将变成原来的2倍。比如原来该任务的时间片time_slice为10ms，则现在变成了20ms。基本的原则是，当任务下到楼梯 底部时，再次用完时间片就回到上次下楼梯的起点的下一级台阶。并给予该任务相同于其最初分配的时间片。总结如下:

设任务本身优先级为P，当它从第N级台阶开始下楼梯并到达底部后，将回到第N+1级台阶。并且赋予该任务N+1倍的时间片。

以上描述的是普通进程的调度算法，实时进程还是采用原来的调度策略，即FIFO或者Round Robin。

楼梯算法能避免进程饥饿现象，高优先级的进程会最终和低优先级的进程竞争，使得低优先级进程最终获得执行机会。

对于交互式应用，当进入睡眠状态时，与它同等优先级的其他进程将一步一步地走下楼梯，进入低优先级进程队列。当该交互式进程再次唤醒后，它还留在高处的楼梯台阶上，从而能更快地被调度器选中，加速了响应时间。

楼梯算法的优点

从实现角度看，SD基本上还是沿用了O(1)的整体框架，只是删除了O(1)调度器中动态修改优先级的复杂代码；还淘汰了expire数组，从而简化了代码。它最重要的意义在于证明了完全公平这个思想的可行性。

3.2 RSDL (The Rotating Staircase Deadline Schedule) RSDL也是由Con Kolivas开发的，它是对SD算法的改进。核心的思想还是"完全公平”。没有复杂的动态优先级调整策略。

RSDL重新引入了expire数组。它为每一个优先级都分配了一个 “组时间配额”， 我们将组时间配额标记为Tg；同一优先级的每个进程都拥有同样的"优先级时间配额"本文中用Tp表示，以便于后续描述。

当 进程用完了自身的Tp时，就下降到下一优先级进程组中。这个过程和SD相同，在RSDL中这个过程叫做minor rotation。请注意Tp不等于进程的时间片，而是小于进程的时间片。下图表示了minor rotation。进程从priority1的队列中一步一步下到priority140之后回到priority2的队列中，这个过程如下图左边所示， 然后从priority 2开始再次一步一步下楼，到底后再次反弹到priority3队列中，如图1所示。

图 1. 图 1

在 SD算法中，处于楼梯底部的低优先级进程必须等待所有的高优先级进程执行完才能获得CPU。因此低优先级进程的等待时间无法确定。RSDL中，当高优先级 进程组用完了它们的Tg(即组时间配额)时，无论该组中是否还有进程Tp尚未用完，所有属于该组的进程都被强制降低到下一优先级进程组中。这样低优先级任 务就可以在一个可以预计的未来得到调度。从而改善了调度的公平性。这就是RSDL中Deadline代表的含义。

进程用完了自己的时间片time_slice时 (下图中T2) ，将放入expire数组中它初始的优先级队列中(priority 1)。

图 2 图 2

当active数组为空，或者所有的进程都降低到最低优先级时就会触发major rotation: 。Major rotation交换active数组和expire数组，所有进程都恢复到初始状态，再一次从新开始minor rotation的过程。

RSDL对交互式进程的支持

和SD同样的道理，交互式进程在睡眠时间时，它所有的竞争者都因为minor rotation而降到了低优先级进程队列中。当它重新进入RUNNING状态时，就获得了相对较高的优先级，从而能被迅速响应。

3.3 CFS 完全公平调度器 CFS是最终被内核采纳的调度器。它从RSDL/SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再企图区分交互式进程。它将所有的进程都统一对待，这就是公平的含义。CFS的算法和实现都相当简单，众多的测试表明其性能也非常优越。

按 照作者Ingo Molnar的说法: “CFS百分之八十的工作可以用一句话概括: CFS在真实的硬件上模拟了完全理想的多任务处理器”。在"完全理想的多任务处理器 “下，每个进程都能同时获得CPU的执行时间。当系统中有两个进程时，CPU的计算时间被分成两份，每个进程获得50%。然而在实际的硬件上，当一个进程 占用CPU时，其它进程就必须等待。这就产生了不公平。

假设runqueue中有n个进程，当前进程运行了10ms。在"完全理想的多任务 处理器"中，10ms应该平分给n个进程(不考虑各个进程的nice值)，因此当前进程应得的时间是(10/n)ms，但是它却运行了10ms。所以 CFS将惩罚当前进程，使其它进程能够在下次调度时尽可能取代当前进程。最终实现所有进程的公平调度。下面将介绍CFS实现的一些重要部分，以便深入地理 解CFS的工作原理。

CFS如何实现pick next

CFS抛弃了active/expire数组，而使用红黑树选取下一个被调度进程。所有状态为RUNABLE的进程都被插入红黑树。在每个调度点，CFS调度器都会选择红黑树的最左边的叶子节点作为下一个将获得cpu的进程。

tick中断

在 CFS中，tick中断首先更新调度信息。然后调整当前进程在红黑树中的位置。调整完成后如果发现当前进程不再是最左边的叶子，就标记 need_resched标志，中断返回时就会调用scheduler()完成进程切换。否则当前进程继续占用CPU。从这里可以看到CFS抛弃了传统的 时间片概念。Tick中断只需更新红黑树，以前的所有调度器都在tick中断中递减时间片，当时间片或者配额被用完时才触发优先级调整并重新调度。

红黑树键值计算

理解CFS的关键就是了解红黑树键值的计算方法。该键值由三个因子计算而得: 一是进程已经占用的CPU时间；二是当前进程的nice值；三是当前的cpu负载。

进 程已经占用的CPU时间对键值的影响最大，其实很大程度上我们在理解CFS时可以简单地认为键值就等于进程已占用的CPU时间。因此该值越大，键值越大， 从而使得当前进程向红黑树的右侧移动。另外CFS规定，nice值为1的进程比nice值为0的进程多获得10%的CPU时间。在计算键值时也考虑到这个 因素，因此nice值越大，键值也越大。

CFS为每个进程都维护两个重要变量: fair_clock和wait_runtime。在本文中，我们将为每个进程维护的变量称为进程级变量，为每个CPU维护的称作CPU级变量，为每个runqueue维护的称为runqueue级变量。

进程插入红黑树的键值即为

fair_clock – wait_runtime。 fair_clock 从其字面含义上讲就是一个进程应获得的CPU时间，即等于进程已占用的CPU时间除以当前runqueue中的进程总数；wait_runtime是进程 的等待时间。它们的差值代表了一个进程的公平程度。该值越大，代表当前进程相对于其它进程越不公平。

对于交互式任务，wait_runtime长时间得不到更新，因此它能拥有更高的红黑树键值，更靠近红黑树的左边。从而得到快速响应。

红黑树是 平衡树，调度器每次总最左边读出一个叶子节点，该读取操作的时间复杂度是O(LgN)。

调度器管理器

为 了支持实时进程，CFS提供了调度器模块管理器。各种不同的调度器算法都可以作为一个模块注册到该管理器中。不同的进程可以选择使用不同的调度器模块。 2.6.23中，CFS实现了两个调度算法，CFS算法模块和实时调度模块。对应实时进程，将使用实时调度模块。对应普通进程则使用CFS算法。Ingo Molnar还邀请Con Kolivas可以将RSDL/SD写成一个调度算法模块。

CFS源代码分析

Sched.c 中scheduler_tick()函数会被时钟中断直接调用。它首先更新runqueue级变量clock；然后调用CFS的tick处理函数 task_tick_fair()。task_tick_fair在sched_fair.c中。它主要的工作是调用entity_tick()

函数entiry_tick源代码如下:

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { struct sched_entity *next; dequeue_entity(cfs_rq, curr, 0); enqueue_entity(cfs_rq, curr, 0); next = __pick_next_entity(cfs_rq); if (next == curr) return; __check_preempt_curr_fair(cfs_rq, next, curr, sched_granularity(cfs_rq)); }复制代码 首先调用dequeue_entity()函数将当前进程从红黑树中删除，再调用enqueue_entity () 重新 插入。这两个动作就调整了当前进程在红黑树中的位置。_pick_next_entity()返回红黑树中最左边的节点，如果不再是当前进程，就调用 _check_preempt_curr_fair。该函数设置调度标志，当中断返回时就会调用schedule()进行调度。

函数enqueue_entity()的源码如下:

enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity se, int wakeup) { / * Update the fair clock. */ update_curr(cfs_rq); if (wakeup) enqueue_sleeper(cfs_rq, se); update_stats_enqueue(cfs_rq, se); __enqueue_entity(cfs_rq, se); }复制代码 它的第一个工作是更新调度信息。然后将进程插入红黑树中。其中update_curr()函数是核心。完成调度信息的更新。

static void update_curr(struct cfs_rq *cfs_rq) { struct sched_entity *curr = cfs_rq_curr(cfs_rq); unsigned long delta_exec; if (unlikely(!curr)) return; delta_exec = (unsigned long)(rq_of(cfs_rq)->clock - curr->exec_start); curr->delta_exec += delta_exec; if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) { __update_curr(cfs_rq, curr); curr->delta_exec = 0; } curr->exec_start = rq_of(cfs_rq)->clock; }复制代码 该函数首先统计当前进程所获得的CPU时间，rq_of(cfs_rq)->clock值在tick中断中被更 新，curr->exec_start就是当前进程开始获得CPU时的时间戳。两值相减就是当前进程所获得的CPU时间。将该变量存入 curr->delta_exec中。然后调用__update_curr()

__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long delta, delta_exec, delta_fair, delta_mine; struct load_weight *lw = &cfs_rq-load; unsigned long load = lw->weight; delta_exec = curr->delta_exec; schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max)); curr->sum_exec_runtime += delta_exec; cfs_rq->exec_clock += delta_exec; if (unlikely(!load)) return; delta_fair = calc_delta_fair(delta_exec, lw); delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw); if (cfs_rq->sleeper_bonus > sysctl_sched_min_granularity) { delta = min((u64)delta_mine, cfs_rq->sleeper_bonus); delta = min(delta, (unsigned long)( (long)sysctl_sched_runtime_limit - curr->wait_runtime)); cfs_rq->sleeper_bonus -= delta; delta_mine -= delta; } cfs_rq->fair_clock += delta_fair; add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec); }复制代码 __update_curr()的主要工作就是更新前面提到的fair_clock和wait_runtime。这两个 值的差值就是后面进程插入红黑树的键值。变量Delta_exec保存了前面获得的当前进程所占用的CPU时间。函数calc_delta_fair() 根据cpu负载 (保存在lw变量中) ，对delta_exec进行修正，然后将结果保存到delta_fair变量中，随后将fair_clock增加 delta_fair。函数calc_delta_mine()根据nice值 (保存在curr->load.weight中) 和cpu负载修正 delta_exec，将结果保存在delta_mine中。根据源代码中的注释，delta_mine就表示当前进程应该获得的CPU时间。

随 后将delta_fair加给fair_clock而将delta_mine-delta_exec加给wait_runtime。函数 add_wait_runtime中两次将wait_runtime减去delta_mine-delta_exec。由于calc_delt_xx() 函数对delta_exec仅做了较小的修改，为了讨论方便，我们可以忽略它们对delta_exec的修改。最终的结果可以近似看成 fair_clock增加了一倍的delta_exec，而wait_runtime减小了两倍的delta_exec。因此键值fair_clock- wait_runtime最终增加了一倍的delta_exec值。键值增加，使得当前进程再次插入红黑树中就向右移动了。

CFS小结

以 上的讨论看出CFS对以前的调度器进行了很大改动。用红黑树代替优先级数组；用完全公平的策略代替动态优先级策略；引入了模块管理器；它修改了原来 Linux2.6.0调度器模块70%的代码。结构更简单灵活，算法适应性更高。相比于RSDL，虽然都基于完全公平的原理，但是它们的实现完全不同。相 比之下，CFS更加清晰简单，有更好的扩展性。

CFS还有一个重要特点，即调度粒度小。CFS之前的调度器中，除了进程调用了某些阻塞函数 而主动参与调度之外，每个进程都只有在用完了时间片或者属于自己的时间配额之后才被抢占。而CFS则在每次tick都进行检查，如果当前进程不再处于红黑 树的左边，就被抢占。在高负载的服务器上，通过调整调度粒度能够获得更好的调度性能。

4 总结 通过对Linux调度器历史发展的探讨，能进一步了解CFS调度器开发的背景知识。其实目前任何调度器算法都还无法满足所有应用的需要，CFS也有一些负 面的测试报告。我们相信随着Linux的不断发展，还会出现新的调度算法，让我们拭目以待。有抱负的程序员也可以尝试着在这个领域为Linux作出贡献。

http://www.cnblogs.com/zhoug2020/p/3967385.html https://www.cnblogs.com/vamei/p/9364382.html