进程调度

发表于 分类于 ， ， ， 阅读次数： 本文字数： 26k 阅读时长 ≈ 23 分钟

第3章讨论了进程，它在操作系统看来是程序的运行态表现形式。本章将讨论进程调度程序，它是确保进程能有效工作的一个内核子系统。
调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序（常常简称调度程序）可看作在可运行态程序之间分配有限的处理器时间资源的内核子系统。调度程序是像Linux这样的多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度的发挥作用，多进程才会并发执行的效果。
调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，只要有可以执行的进程，那么总会有进程正在执行。但是只要系统中可运行的进程的数目比处理器的个数多，就注定某一给定时刻会有一些进程不能执行。这些进程在等待运行。这一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。

多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。在单处理机器上，这会产生多个进程在同时运行的幻觉。在多处理器机器上，这会使多个进程在不同的处理机上真正同时、并行的运行。无论在单处理器或者是多处理器机器上，多任务操作系统都能使多个进程处于堵塞或者睡眠状态，也就是说，实际上不被投入运行，直到工作确实就绪。这些任务尽管位于内存，但并不处于可运行状态。相反，这些进程利用内核阻塞自己，直到某一事件（键盘输入、网络数据、过一段时间等）发生。因此，现代Linux系统也许有100个进程在内存，但是只有一个处于可运行状态。
多任务系统可以划分为两类：非抢占式多任务（cooperative multitasking）和抢占式多任务（preemptive multitasking）。像所有Unix的变体和许多其他现代操作系统一样，Linux提供了抢占式的多任务模式。在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到运行机会。这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间都是预先设置好的，而且有一个专门的名字，叫进程的时间片（timeslice）。时间片实际上就是分配给每个可运行进程的处理器时间段。有效管理时间片能使调度程序从系统全局的角度做出调度决定，这样做还可以避免个别进程独占系统资源。当今众多现代操作系统对程序运行都采用了动态时间片计算的方式，并且引入了可配置的计算策略。不过我们将看到，Linux的独一无二的“公平”调度程序本身并没有采用时间片来达到公平调度。
相反，在非抢占式多任务模式下，除非进程自己主动停止运行，否侧它会一直运行。进程主动挂起自己的操作叫做让步（yielding）。理想情况下，进程通常做出让步，以便让每个可允许的进程都享有足够的处理器时间。但这种机制有很多缺点：调度程序无法对每个进程该执行多长时间做出统一规定，所以进程独占的处理器时间可能超出用户的预料；更糟糕的是，一个绝不做出让步的悬挂进程就能使系统崩溃。幸运的是，近20年来，绝大部分操作系统的设计都采用了抢占式多任务–除了Mac OS 9（以及其前身）、Windows 3.1（以及其前身）这些出名且麻烦的异端以外。毫无疑问，Unix从一开始就采用的是抢占式的多任务模式。

Linux的进程调度

从1991年Linux的第1版到后来的2.4内核系列，Linux的调度程序都相当简陋，设计几乎原始。当然它很容易理解，但是它在众多可允许进程或者多处理器的环境下都难以胜任。
正因为如此，在Linux2.5开发系列的内核中，调度程序做了大手术。开始采用了一种叫做O(1)调度程序的新调度程序–它是因为其算法的行为而得名的。它解决了先前版本Linux调度程序的许多不足，引入了许多强大的新特性和性能特征。这里主要感谢静态时间片算法和针对每一处理器的运行队列，它们帮助我们摆脱了先前调度程序设计上的限制。
O(1)调度器虽然在拥有数以十计的多处理器的环境下尚能表现得近乎完美的性能和可扩展性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却有一些先天不足。这些程序我们称之为交互进程–它无疑包括了所有需要用户交互的程序。正因为如此，O(1)调度程序虽然对于大服务器的工作负载很理想，但是在很多交互程序运行的桌面系统中则表现不佳，因为其缺少交互进程。自2.6内核系统开发初期，开发人员为了提高对交互程序的调度性能引入了新的进程调度算法。其中最为著名的是“反转楼梯最后期限调度算法（Rotating Staircase Deadline scheduler）”（RSDL），该算法吸取了队列理论，将公平调度的概念引入了Linux调度程序。并且最终在2.6.23内核版本中替代了O(1)调度算法，它此刻被称为“完全公平调度算法”，或者称为CFS。
本章将讲解调度程序设计的基础和完全公平调度程序如何运用、如何设计、如何实现以及与它相关的系统调用。我们当然也会讲解O(1)调度程序，因为它毕竟是经典Unix调度程序模型的实现方式。

策略

策略决定调度程序在何时让什么进程运行。调度器的策略往往就决定系统的整体印象，并且，还要负责优化使用处理器时间。无论从哪个方面看，它都是至关重要的。

I/O消耗型和处理器消耗型的进程

进程可以被分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或者等待I/O请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短一会，因为它等待更多的I/O请求时最后总会阻塞（这里所说的I/O是指任何类型的可阻塞资源，比如键盘输入、或者是网络I/O）。举例来说，多数用户图形界面程序（GUI）都属于I/O密集型，即便它们从不读取或者写入硬盘，它们也会在多数时间等待来自键盘或者鼠标的用户交互操作。
相反，处理器消耗型进程把时间大多用在了执行代码上。除非被抢占，否则它们通常一直都不停的运行，因为它们没有太多的I/O需求。但是，因为它们不属于I/O驱动类型，所以从系统响应速度考虑，调度器不应该让它们经常运行。对于这类处理器消耗型的进程，调度策略往往就是尽量降低它们的调度频率，而延长其运行时间。处理器消耗型进程的极端例子就是无限循环地执行。更具代表性的例子就是那些执行大量数学计算的程序，如sshkeygen或者MATLAB。
当然，这种划分方法并非是绝对的。进程可以同时展示这两种行为：比如，X Window 服务器既是I/O消耗型，也是处理器消耗型。还有些进程可以是I/O消耗型，但属于处理器消耗型的范围。其典型的例子就是字处理器，其通常坐以等待键盘输入，但在任何一时刻可能又黏住处理器疯狂的进行拼写检查或宏计算。
调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。为了满足上述需求，调度程序通常采用一套非常复杂的算法来决定最值得运行的进程投入运行，但是它往往并不保证低优先级进程会被公平对待。Unix系统的调度程序更倾向于I/O消耗型程序，以提供更好的程序响应速度。Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。虽然如此，但在下面你会到，调度程序也并非忽略处理器消耗型的进程。

进程优先级

调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程地价值和其对处理器时间的需求来对进程分级的想法。通常做法是（其并未被Linux系统完全采用）优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。在某些系统中，优先级高的进程运行时间也长。调度程序总是选择时间片未用尽且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。
Linux采用两种不同的优先级范围。第一种是用nice值，它的范围是从-20到+19，默认值为0；越大的nice值意味着越低的优先级–nice似乎意味着你对系统中的其他进程更为“优待”。相比高nice值（低优先级）的进程，低nice值（高优先级）的进程能获得更多的处理器时间。nice值是所有Unix系统中标准化的概念–但不同的Unix系统中由于调度方式的不同，因此nice值的运用方式有所差异。比如一些基于Unix的操作系统，如Mac OS X，进程的nice值代表着分配给进程的时间片的绝对值；在Linux中，nice值代表时间片的比例。你可以通过ps -el命令查看系统中的进程列表，结果中标记N1的一列就是进程的nice值。
第二种范围是实时优先级，其值是可配置的，默认情况下它的变化范围值0到99。与nice值意义相反，越高的实时优先级代表着越高的进程优先级。任何实时进程的优先级都高于普通进程，也就是说实时优先级和nice值优先级属于两个互不相交的范畴。Linux实时优先级的实现参考的Unix相关标准–特别是POSIX.1b。大部分现代Unix操作系统都通过类似的机制。你可以通过命令：

1
ps -eo state,uid,pid,ppid,rtprio,time,comm.

查看到你系统中的进程列表，以及它们对应的实时优先级（位于RTPRIO下），其中如果有对应列显示“-”，则说明它不是实时进程。

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片，但这并不是一件简单的事情。时间片过长会导致系统对交互的响应表现欠佳，让人认为系统无法并发执行应用程序；时间片太短会导致明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在了进程切换上，而这些进程能够用来运行的时间片却很少。此外，I/O消耗型和处理器消耗型的进程之间的矛盾也再次显露出来：I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好，这样可以让它们的高速缓存的命中率更高。
从上面的争论可以看出，任何长时间片都将导致系统交互表现欠佳。很多操作系统都特别重视这一点，所以默认的时间片很短，如10ms。但是Linux的CFS调度器并没有分配时间片到进程，它是将处理器的使用比例划给进程。这样一来，进程所获得的处理器时间其实都是和系统负载密切相关的。这个比例还会进一步受nice值的影响，nice值作为权重将调制进程所使用的处理器时间比。具有高nice值（更低优先级）得进程将会被赋以更低的权重，从而丧失一小部分的处理器时间比；而具有低nice值（更高优先级）的进程将被赋以高权重，从而强的更高的处理器时间比。
像前面所说的，Linux系统是抢占式的。当一个进程进入可运行态，它就被准许投入运行。在多数操作系统中，是否要将一个进程投入运行（也就是抢占当前进程），则完全由进程优先级和是否有时间片决定的。而在Linux系统中使用新的CFS调度器，其抢占时间取决于新的可运行程序消耗了多少处理器时间比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则，将推迟其运行。

调度策略的活动

想象下面这样一个系统，它拥有两个可运行的进程：一个文件编辑程序和一个视频编码程序。文字编辑程序显然是I/O消耗型的，因为它大部分时间都在等待用户的键盘输入（无论用户的输入速度有多快，都不可能赶上处理器速度）。用户总是希望按下按键就能马上得到响应。相反，视频编码程序是处理器消耗型的。除了最开始从磁盘上读出原始数据流和最后把处理好的视频输出外，程序所有的时间都用来对原始视频数据进行视频编码，处理器很轻易地被100%使用。它对什么时间开始运行没有太严格的要求–用户几乎分辨不出也不关心它到底是立刻就运行还是半秒钟之后才开始的。当然。它完成的越早越好，至于所花时间并不是我们所关心的主要问题。
在这样的场景中，理想情况是调度器应该给与文本编辑程序相比视频编码更多的处理器时间，因为它属于交互式应用。对于文本编辑器而言，我们有两个目标。第一是我们希望系统给它更多的处理器时间，这并非是因为它需要更多的处理器时间（其实它并不需要），是因为我们希望在它需要时总能得到处理器；第二是我们希望文本编辑器程序能在其被唤醒时（也就是用户开始打字时）抢占视频解码程序。这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入。在多数操作系统中，上述目标的达成是要依靠系统分配给文本编辑器更多的时间片和进程优先级。先进的操作系统可以自动发现文本编辑器是交互性程序，从而自动的完成上述分配动作。Linux操作系统同样追求上述目标，但是它采用不同的方法。它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。假如假如文本编辑器和视频解码程序是仅有的两个运行进程，并且又具有相同的nice值，那么处理器的使用比都将是50%–它们平分了处理器时间。但因为文本编辑器将大部分时间用于等待用户输入，因此它肯定不会用到处理器的50%。同时，视频解码程序无疑能够用到超过50%的处理器时间，以便它能更快速地完成解码任务。
这里关键的问题是，当文本编辑器被唤醒是将会发生什么。我们首要目标是确保其能在用户输入发生时立刻运行。在上述场景中，一旦文本编辑器被唤醒，CFS注意到给它的处理器时间比是50%，但其实它却用的少之又少。特别是，CFS发现文本编辑器比视频解码器运行的时间要短的多。这种情况下，为了兑现让所有进程公平分享处理器时间的承诺，它会立刻抢占视频解码程序，让文本编辑器程序投入运行。文本编辑器投入运行之后，立即处理了用户的按键输入，有一次进入了休眠等待用户的下一次输入。因为文本编辑器并没有消耗掉承诺给它的50%处理器使用比，因此情况依旧，CFS总毫不犹豫地让文本编辑器在需要时投入运行，而让视频处理程序只能在剩下的时刻运行。

Linux调度算法

在前面的内容中，我们抽象的讨论了进程调度原理，只是偶尔提及Linux如何把给定的理论应用到实际中。在已有的调度原理基础上，我们进一步探讨具有Linux特色的进程调度程序。

调度器类

Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性的选择调度算法.
这种模块化结构被称为调度器类（scheduler classes），它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，并选择下面要执行的那一个程序。
完全公平调度算法（CFS）是一个针对普通进程的调度类，在Linux中被称为SCHED_NORMAL（在POSIX中被称为SCHED_OTHER），CFS算法算法实现定义在文件kernel/sched_fair.c中。下面我们将重点讨论CFS算法–该内容对于所有2.6.23以后的内核版本意义非凡。

Unix系统中的进程调度

在讨论CFS算法之前，我们必须认识一下传统Unix系统的进程调度过程。正如前面所述，现代进程调度器有两个通用的概念：进程优先级和时间片。时间片是指进程运行多长时间，进程一旦启动就会有一个默认的时间片。具有更高优先级的进程将运行的更频繁，而且（在多数系统上）也会被赋予更多的时间片。在Unix系统上，优先级以nice值形式输出给用户空间。这点听起来简单，但是在现实中，却会导致很多反常的问题，我们下面具体讨论。
第一个问题，若要将nice值映射到时间片，就必然需要将nice单位值对应到处理器的绝对时间。但这样做就会导致进程切换无法最优化进行。举例说明，假定我们将默认nice值（0）分配给一个进程–对应的是一个100ms的时间片：同时再分配一个最高nice值（+20，最低的优先级）给另一个进程–对应的时间片是5ms。我们接着假定上述两个进程都处于可运行状态。那么默认优先级的进程将获得20/21（105ms中的100ms）的处理器时间，而低优先级的进程将获得1/21（105ms中的5ms）的处理器时间。我们本可以选择任意数值用于此例子中，但这个分配是最具有说服力的，所以我们选择它。现在，我们看看运行两个同等低优先级的进程情况将如何。我们是希望它们能各自获得一半的处理器时间，事实上也确实如此。但是任何一个进程每次仅仅只能获得5ms的处理器时间（10ms中各自占一半）。也就是说，相比刚才例子中的105ms内进行一次进程上下文切换，现在则需要在10ms内继续进行2次进程上下文切换。类推，如果是两个具有普通优先级的进程，它们同样会每个获得50%的处理器时间，但是是在100ms内获得一半。显然，我们看到这种时间片分配方式并不理想：它们是给定nice值到时间片映射与进程运行优先级混合的共同作用结果。事实上，给定高nice值的进程往往是后台进程，且多是计算密集型；而普通优先级的进程则更多是前台用户任务。所以这种时间片分配方式显然是和初衷背道而驰的。
第二个问题涉及相对nice值，同时和前面的nice值到时间片映射关系也脱不了干系。假设我们拥有两个进程，分别具有不同的优先级。第一个假设nice值只有0，第二个假设是1。它们将分别被映射到时间片值100ms和95ms（O(1)调度算法确实这么干了）。它们的时间片几乎一样，其差别微乎其微。但是如果我们的进程分别赋予18和19的nice值，那么它们分别被映射到时间片10ms和5ms。如果这样，前者相比后者获得了两倍的处理器时间！不过nice值通常都是用相对值（nice系统调用是在原值上增加或者减小，而不是在绝对值上操作），也就是说：“把进程的nice值减小1”所带来的效果极大的取决于其nice的初始值。
第三个问题，如果执行nice值到时间片的映射，我们需要能分配一个绝对时间片，而且这个绝对时间片必须能在内核的测试范围内。在多数操作系统中，上述要求意味着时间片必须是定时器节拍的整数倍。但这么做必然会引发了几个问题。首先，最小时间片必然是定时器节拍的整数倍，也就是10ms或者1ms的倍数。其次，系统定时器限制了两个时间片的差异：连续的nice值映射到时间片，其差别范围多至10ms或者少至1ms。最后，时间片还会随着定时器节拍改变。
第四个问题也是最后一个问题是关于基于优先级的调度器为了优化交互任务而唤醒相关进程的问题。这种系统中，你可能为了进程能更快的投入运行，而去对新要唤醒的进程提升优先级，即便它们的时间片已经用尽了。虽然上述方法确实能提升不少交互性能，但是一些例外情况也有可能发生，因为它同时也给某些特殊的睡眠/唤醒用例一个玩弄调度器的后门，使得给定进程打破公平原则，获得更多的处理器时间，损害系统中其他进程的利益。
上述问题中的绝大多数都可以通过对传统Unix调度器进行改造解决，虽然这种改造不小，但也并非是结构性调整。比如，将nice值呈几何增加而非算数增加的方式解决第二个问题；采用一个新的度量机制将从nice值到时间片的映射与定时器节拍分离开来，以此解决第三个问题。但是这些解决方案都回避了实质问题–即分配绝对的时间片引发的固定的切换频率，给公平性造成了很大变数。CFS采用的方法是对时间片的分配方式进行根本性的重新设计：完全摒弃时间片而是给进程一个处理器使用比重。通过这种方式，CFS确保了进程调度中能有恒定的公平性，而将切换频率至于不断变换中。

公平调度

CFS的出发点基于一个简单的理念：进程调度的效果应当如同系统中具备了一个理想中的完美多任务处理器。在这种系统中，每个进程都将获得1/n的处理器时间–n是指可运行进程的数量。同时，我们可以调度调度给它们无限小的时间周期，所以在任何可测量周期中，我们给与n个进程中每个进程同样多的运行时间。举例来说，假如我们有两个可运行进程。在标准Unix调度模型中，我们先运行其中一个5ms，再运行另一个5ms。但它们任何一个运行时都将占有100%的处理器。而在理想情况下，完美的多任务处理器模型应该时这样的：我们能在10ms内同时运行两个进程，它们各自使用处理器一半的能力。
当然，上述理想模型并非现实，因为我们无法真的在同一个处理器上同时运行多个进程。而且每个进程运行无限小的时间周期也是不高效的–因为调度时进程抢占会带来一定的代价：将一个进程换出，另一个换入本身有消耗，同时还会影响到缓存的效率。因此虽然我们希望所有的进程能只运行一个非常短的周期，但是CFS充分考虑了这将带来的额外消耗，实现中首要保证系统性能不受损失。CFS的做法是允许每一个进程运行一段时间、循环轮转、选择运行时间最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS在所有可运行进程总数基础上计算出一个进程一个运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值（越低的优先级）进程获得更低的处理器使用权重，这是相对默认nice值进程的进程而言；相反，更低的nice值（越高的优先级）的进程获得更高的处理器使用权重。
每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行，为了计算准确的时间片，CFS为完美任务中的无限小调度周期的近似值设立了一个小目标。而这个目标称作目标延迟，越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统吞吐总能力。让我们假定目标延时值是20ms，我们有两个同样优先级的可运行任务（无论这些任务的优先级是多少）。每个任务在被其他任务抢占之前运行10ms，如果我们有4个这样的任务，则每个只能运行5ms。进一步设想，如果有20个这样的任务，那么每个仅仅只能获得1ms的运行时间。
你一定注意到了，当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间片都将趋于零。这样无疑造成了不可接受的切换消耗。CFS为此引入每个进程所获得的时间片底线，这个底线称为最小粒度。默认情况下这个值时1ms。这样一来，即便可运行进程的数量趋于无限，也能保证每个进程最少获得1ms的可运行时间。确保切换消耗被限制在一定的范围内。
假如进程数量变得非常多的情况下，CFS并非一个完美的公平调度，因为这时处理器时间时间片再小也无法突破最小粒度。尽管修改过的公平队列方法确实能够提高这方面的公平性，但是CFS的算法本身其实已经决定在这方面做折中了。但是还好，因为通常情况下系统中只会有几百个可运行的进程，无疑，这时的CFS是公平的。
现在，让我们再来看看具有不同的nice值的两个可运行进程的运行情况–比如一个具有默认nice值（0），另一个具有的nice值为5。这些不同的人nice值对应不同的权重，所以上述两个进程都将获得不同的处理器使用比。在这个例子中，nice值为5的进程的权重将是nice值为0的进程的1/3。如果我们的目标延迟是20ms，那么这两个进程将分别获得15ms和5ms的处理器时间。再比如我们两个可运行进程的nice值是10和15，它们分配的时间片将会是多少呢？还是15ms和5ms！可见，绝对的nice值不再影响调度决策：只有相对值才会影响处理器时间的分配比例。
总结一下，任何进程所获得处理器时间是由它自己和其他可运行的进程的nice值的相对值差所决定的。nice值对时间片的作用不再是算术加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器使用比。CFS被称为公平调度器是因为它确保给每个进程公平的处理器使用比。正如我们所知道的，CFS不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下，降低了调度延迟带来的不公平性。

Linux调度的实现

在讨论了采用CFS调度算法的动机和内部逻辑之后，我们现在可以开始探索CFS是如何得以实现的。其代码位于kernel/sched_fair.c中，我们将特别关注以下四部分：

  1. 时间进账
  2. 进程选择
  3. 调度器入口
  4. 睡眠和唤醒

时间进账

所有的调度器都必须对进程运行时间做记账。多数Unix系统，正如我们前面所述，分配一个时间片给每一个进程。那么每次当系统节拍发生时，时间片都会减少一个节拍周期。当一个进程的时间片被减少到0时，它就会被另一个尚未减少为0的时间片可运行进程抢占。

调度器实体结构

CFS不再有时间片的概念，但是它也必须维护每个进程运行的时间记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。CFS使用调度器实体结构（定义在文件<linux/sched.h>的struct_sched_entity中）来追踪进程运行记账：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct sched_entity {
    struct load_wieght  load;
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;
    u64                 exec_start;
    u64                 sum_exec_runtime;
    u64                 vruntime;
    u64                 prev_sum_exec_runtime;
    u64                 last_wakeup;
    u64                 avg_overlap;
    u64                 nr_migrations;
    u64                 start_runtime;
    u64                 avg_wakeup;
    //这里省略了很多统计变量，只有在设置了CONFIG_SCHEDSTATS时才启用这些变量
};

调度器实体结构作为一个名为se的成员变量，嵌入在进程描述符struct task_struct内。

虚拟实时

vruntime变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算是经过了所有可运行进程总数的标准化（或者说是被加权的）。虚拟时间是以ns为单位的，所以vruntime不再与定时器节拍有关系。虚拟运行时间可以帮助我们逼近CFS模型追求的“理想多任务处理器”。如果我们真有这样一个理想的处理器，那么我们就不再需要vruntime了。因为优先级相同的所有可运行进程的虚拟运行时间都是相同的–所有任务都将接收到相等的处理器份额。但是因为处理器无法实现完美的多任务。它们必须依次运行每个任务。因此CFS使用vruntime变量来记录一个进程已经运行了多久以及它还能再运行多久。
定义在kernel/sched_fair.c文件中的update_curr()函数实现了该记账功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock;
    unsigned long delta_exec;

    if(unlikely(!curr))
        return;
    //获得最后一次修改负载后当前任务所占用的运行总时间（在32位系统上这不会溢出）
    delta_exec = (unsigned long)(now - curr->exec_start);
    if(!delta_exec)
        return;
    __update_curr(cfs_rq,curr,delta_exec);
    curr->exec_start = now;

    if(entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);
        trace_sched_stat_runtime(curtask,delta_exec,curr->vruntime);
        cpuacct_charge(curtask,delta_exec);
        account_group_exec_runtime(curtask,delta_task);
    }
}

update_curr()计算了当前进程的执行时间，并且将其存放在变量delta_exec中。然后它又将运行时间传递给了__update_curr()，由后者再根据当前可运行进程总数对运行时间进行加权运算。最终将上述的权重值与当前运行进程的vruntime相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//更新当前任务的运行时统计数据。跳过不在调度类中的当前任务
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
              unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;

    schedstat_set(curr->exec_max,max((u64)delta_exec,curr->exec_max));

    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq,exec_clock,delta_exec);
    delta_exec_weighted = calc_delta_fair(delta_exec,curr);

    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

update_curr()是由系统定时器周期性调用的，无论是在进程处于可运行状态，还是被堵塞处于不可运行状态。根据这种方式，vruntime可以准确的测量给定的运行时间，而且可以知道谁应该是下一个被运行的进程。

进程选择

在前面内容中我们的讨论中谈到若存在一个完美的多任务处理器，所有可运行进程的vruntime值将一致。但是实际上我们并没有找到完美的多任务处理器，因此CFS试图利用一个简单的规则去均衡进程的虚拟运行时间：当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。这其实就是CFS调度算法的核心：选择具有最小vruntime的任务。那么剩下的内容我们就来讨论到底是如何实现选择具有最小vruntime值的进程。
CFS使用红黑树来组织可运行进程队列，并利用其迅速找到vruntime最小的进程。在Linux中，红黑树被称为rbtree，它是一个自平衡二叉搜索树。红黑树是一种以树形节点存储的数据结构，这些数据都会对应一个键值。我们可以通过这些键值来快速检索节点上的数据（重要的是，通过键值检索到对应节点的速度与整个树的节点规模成指数比关系）。

挑选下一个任务

我们先假设，有那么一个红黑树存储了系统中所有的可运行进程，其中节点的键值便是可运行进程的虚拟运行时间。CFS调度器选取待运行的下一个进程，是所有进程中vruntime最小的那个，它对应的便是在树中最左侧的叶子节点。也就是说，你从树的根节点沿着左边的子节点向下找，一直找到叶子节点，你便找到了其vruntime最小的那个进程。CFS的进程选择算法可简单总结为“运行rbtree树中最左边叶子节点所代表的那个进程”。实现这一过程的函数是__pick_next_entuty()，它定义在文件kernel/sched_fail.c中：

1
2
3
4
5
6
7
8
9
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;

    if(!left)
        return NULL;
    
    return rb_entity(left,struct sched_entity, run_code);
}

注意
__pick_next_entity()函数本身并不会遍历树找到最左叶子节点，因为该值已经缓存在rb_leftmost字段中。虽然红黑树让我们可以很有效的找到最左叶子节点（O（树的高度）等于树节点总数的O（logn），这就是平衡树的优势），但是更容易的做法是把最左叶子节点缓存起来。这个函数的返回值便是CFS调度选择的下一个运行进程。如果该函数的返回值是NULL，那么表示没有最左叶子节点，也就是说树中没有任何节点了。这种情况下，表示没有可运行的进程，CFS调度器便选择idle任务运行。

向树中加入进程

现在，我们来看CFS如何将进程加入rbtree中，以及如何缓存最左叶子节点。这一切发生在进程变成可运行状态（被唤醒）或者通过fork()调用第一次创建进程时。enqueue_entity()函数实现了它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void
enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se,int flags)
{
    //通过调用update_curr()，在更新min_vruntime之前先更新规范的vruntime
    if(!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
        se->vruntime += cfs_rq->min_vruntime;
    
    //更新“当前任务”的运行时统计数据
    update_curr(cfs_rq);
    account_entity_enqueue(cfs_rq,se);

    if(flags & ENQUEUE_WAKEUP) {
        place_entity(cfs_rq,se,0);
        enqueue_sleeper(cfs_rq,se);
    }

    update_stats_enqueue(cfs_rq,se);
    check_spread(cfs_rq,se);
    if(se != cfs_rq->curr)
        __enqueue_entity(cfs_rq,se);
}

该函数更新运行时间和其他一些统计数据，然后调用__enqueue_entity()进行繁重的插入操作，把数据项真正的插入到红黑树中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//把一个调度实体插入到红黑树中
static void __enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    s64 key = entity_key(cfs_rq,se);
    int leftmode = 1;

    //在红黑树中查找合适的位置
    while(*link) {
        parent = *link;
        entry = rb_entry(parent,struct sched_entity,run_code);
        //我们不关心冲突。具有相同键值的节点呆在一起
        if(key < entity_key(cfs_rq,entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    //维护一个缓存，其中存放树最左叶子节点
    if(leftmost) 
        cfs_rq->rb_leftmost = &se->run_code;

    rb_link_code(&se->run_code,parent,link);
    rb_insert_color(&se->run_code,&cfs_rq->task_timeline);
}

我们来看看上述函数，while()循环中遍历树以寻找合适的匹配键值，该值就是被插入到进程的vruntime。平衡二叉树的基本规则是，如果键值小于当前节点的键值，则需转入树的左分支；相反，如果大于当前节点的键值，则转向右分支。如果一旦走过右边分支，哪怕一次，也说明新插入的进程不会是新的最左节点，因此可以设置leftmost为0。如果一直都是向左移动，那么leftmost维持1，这说明我们有一个新的最左节点，并且可以更新缓存–设置rb_leftmost指向被插入的进程。当我们沿着一个方向和一个没有子节点的节点比较后：link如果这时候是NULL，循环随之终止。当退出循环后，接着在父节点上调用rb_link_node(),以使得新插入的进程成为其子节点。最后函数rb_insert_color()更新树的自平衡相关属性。

从树中删除进程

最后我们看看CFS是如何从红黑树中删除进程的。删除动作发生在进程堵塞（变为不可运行状态）或终止时（结束运行）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void
dequeue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se,int sleep)
{
    //更新“当前任务”的运行时统计数据
    update_curr(cfs_rq);

    update_stats_dequeue(cfs_rq,se);
    clear_buddies(cfs_rq,se);

    if(se != cfs_rq->curr)
        __dequeue_entity(cfs_rq,se);
    account_entity_dequeue(cfs_rq,se);
    update_min_vruntime(cfs_rq);

    //在更新min_vruntime之后对调度实体进行规范化，因为更新可以指向“->curr”项，我们需要在规范化的位置反映这一变化
    if(!sleep)
        se->vruntime -= cfs_rq->min_vruntime;
}

和给红黑树添加进程一样，实际工作是由辅助函数__dequeue_entity()完成的。

1
2
3
4
5
6
7
8
9
10
11
static void __dequeue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
{
    if(cfs_rq->rb_leftmost == &se->run_code) {
        struct rb_node *next_node;

        next_node = rb_next(&se->run_node);
        cfs_rq->rb_leftmost = next_node;
    }

    rb_erase(&se->run_node,&cfs_rq->tasks_timeline);
}

从红黑树中删除进程要容易得多。因为rbtree实现了rb_erase()函数，它可完成所有工作。该函数的剩下工作就是更新rb_leftmost缓存。如果要删除的是最左节点，那么该函数要调用rb_next()按顺序遍历，这道谁是下一个节点，也就是当最左节点被删除后，新的最左节点。

调度器入口

进程调度的主要入口点是函数schedule()，它定义在文件kernel/sched.c中。它正是内核其他部分用于调度进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。schedule()通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类–后者需要有自己的可运行队列，然后问后者谁是下一个该运行的进程。知道了这个背景，就不会吃惊为什么schedule()函数会实现的如此简单。该函数中唯一重要的事情是，它会调用pick_next_task()（也是定义在文件kernel/sched.c中）。pick_next_task()会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最该优先级的进程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//挑选最高优先级的任务
static inline struct task_struct *pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    //优化：我们知道如果所有任务都在公平类中，那么我们就可以直接调用那个函数
    if(likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if(likely(p))
            return p;
    }
    class = sched_class_highest;
    for(;;) {
        p = class->pick_next_task(rq);
        if(p)
            return p;
        //永不会为NULL，因为idel类总会返回非NULL的p
        class = class->next;
    }
}

注意该函数开始部分的优化。因为CFS是普通进程的调度类，而系统运行的绝大多数进程都是普通进程，因此这里有一个小技巧用来加速选择下一个CFS提供的进程，前提是所有可运行进程数量等于CFS类对应的可运行进程数（这样就说明所有可运行进程都是CFS类的）。
该函数的核心是for循环，它以优先级为序，从最高的优先级类开始，遍历了每一个调度类，每一个调度类都实现了pick_next_task()函数，它会返回指向下一个可运行进程的指针，或者没有时返回NULL。我们会从第一个返回非NULL的类中选择下一个可运行的进程。CFS中pick_next_task()实现会调用pick_next_entity()，而该函数会再来调用我们前面内容讨论过的__pick_next_entity()函数。

睡眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行状态。这点非常重要，如果没有这种特殊状态的话，调度程序就可能选择出本不愿意被执行的进程，更糟糕的是，休眠就必须以轮询的方式进行了。进程休眠有多种原因，但肯定就是为了等待一些事件。事件可能是一段时间从文件I/O读更多数据，或者某个硬件事件。一个进程还有可能在尝试获取一个以被占用的内核信号量时被迫进入休眠。休眠的一个常见原因就是文件I/O–如一个进程对文件进行read()操作，而这需要从磁盘读取。还有，进程在获取键盘输入的时候也需要等待。无论哪种情况，内核的操作都相同：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反：进程被设置成可执行状态，然后再从等待队列中移到可执行红黑树中。
第3章有讨论过，休眠有两种相关的进程状态：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。他们的唯一区别是处于TASK_UNINTERRUPTIBLE的进程会忽略信号，而处于TASK_INTERRUPTIBLE状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的进程处于同一等待队列上，等到某些事件，不能够运行。

等待队列

休眠通过等待队列进行处理。等待队列是由某些等待事件发生的进程组成的简单链表。内核用wake_queue_head_t来代表等待队列。等待队列可以通过DECLARE_WAITQUEUE()静态创建，也可以由init_waitqueue_head()动态创建。进程把自己放入等待队列中并设置从不可执行状态。当与等待队列相关的事件发生时，队列上的进程会被唤醒。为避免产生竞争条件，休眠与唤醒的实现不能有纰漏。
针对休眠，以前曾经使用过一些简单的接口。但那些接口会带来竞争条件：有可能导致在判定条件为真后，进程却开始了休眠，那样就会使进程无限期休眠下去。所以，在内核中进行休眠的推荐操作就相对复杂一些。

1
2
3
4
5
6
7
8
9
10
//'q'是我们希望休眠的等待队列
DEFINE_WAIT(wait);

add_wait_queue(q,&wait);
while(!condition) { //'condition'是我们在等待的事件
    prepare_to_wait(&q,&wait,TASK_INTERRUPTIBLE);
    if(signal_pending(current))//处理信号
        schedule();
}
finish_wait(&q,&wait);

进程通过执行以下几个步骤让自己加入等待队列中：

  1. 调用宏DEFINE_WAIT()创建一个等待队列的项。
  2. 调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它。当然我们必须在其他地方撰写相关代码，在事件发生时，对等待队列进行wake_up()操作。
  3. 调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列。这是在接下来的循环遍历中需要的。
  4. 如果状态被设置为TASK_INTERRUPTIBLE，则信号唤醒进程。这就是所谓的伪唤醒（唤醒不是因为事件的发生），因此检查并处理信号。
  5. 当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环；如果不是，它再次调用schedule()并一直重复这步操作。
  6. 当条件满足后，进程将自己设置为TASK_RUNNING并调用finish_wait()方法把自己移出等待队列。

如果在进程开始休眠之前条件就已经达成，那么循环会退出，进程不会存在错误的进入休眠的倾向。需要注意的是，内核代码在循环体内常常需要完成一些其他任务，比如，它可能在调用schedule()之前需要释放掉锁，而在这以后在重新获取它们，或者响应其他事件。
函数inotify_read()，位于文件fs/notify/inotify_user.c中，负责从通知文件描述符中读取信息，它的实现无疑是等待队列的一个典型用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
static ssize_t inotify_read(struct file *file,char __user *buf,
                            size_t  count,loff_t *pos)
{
    struct fsnotify_group *group;
    struct fsnotify_event *kevent;
    char __user *start;
    int ret;
    DEFINE_WAIT(wait);

    start = buf;
    group = file->private_data;

    while(1) {
        prepare_to_wait(&group->notification_waitq,
                        &wait,
                        TASK_INTERRUPTIBLE);
        mutex_lock(&group->notification_mutex);
        kevent = geet_one_event(group,event);
        mutex_unlock(&group->notification_mutex);

        if(kevent) {
            ret = PTR_ERR(kevent);
            if(IS_ERR(kevent))
                break;
            ret = copy_event_to_user(group,kevent,buf);
            fsnotify_put_event(kevent);
            if(ret < 0)
                break;
            buf += ret;
            count -= ret;
            continue;
        }
        ret = -EAGAIN;
        if(file->f_flags & O_NONBLOCK)
            break;
        ret = -EINTR;
        if(signal_pending(current))
            break;
        
        if(start != buf)
            break;
        
        schedule();
    }
    finish_wait(&group->notification_waitq,&wait);

    if(start != buf && ret != -EFAULT)
        ret = buf - start;
    return ret;
}

这个函数遵循了我们例子中的使用模式，主要的区别是它在while循环中检查了状态，而不是在while循环条件语句中。原因是该条件的检测更复杂一些，并且需要获得锁。也正因为如此，循环是通过break完成的。

唤醒

唤醒操作通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_to_wake_up()，该函数将进程设置为TASK_RUNNING状态，调用enqueue_task()将进程放进红黑树中，如果被唤醒的进程的优先级比当前正在执行的进程的优先级高，还要设置need_resched标志。通常哪段代码促使等待条件达成，它就要负责随后调用wake_up()函数。举例来说，当磁盘数据到来时，VFS就要负责对等待队列调用wake_up()，以便唤醒队列中等待这些数据的进程。
关于休眠有一点需要注意，存在虚假的唤醒。有时候进程被唤醒并不是因为它所等待的条件达成了才需要用一个循环处理来保证它等待的条件真正达成。

抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成了两项基本的工作：

  1. 调用声明在<asm/mmu_context.h>中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
  2. 调用声明在<asm/system.h>中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。
    img not found
    内核必须知道在什么时候调用schedule()。如果仅靠用户程序代码显式地调用schedule()，它们可能就会永远的执行下去。相反，内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时，schedule_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态时，try_to_wake_up()也会设置这个标志，内核检查该标志，确认其被设置，调用schedule()来切换到一个新的进程。该标志对内核来说是一个信息，它表示有其他进程应当被运行了，要尽快调用调度程序。
    用于访问和操作的need_resched的函数
    函数 目的
    set_tsk_need_resched() 设置指定进程中的need_resched标志
    clear_tsk_need_resched() 清除指定进程中的need_resched标志
    need_resched() 检查need_resched标志的值，如果被设置就返回真，否则返回假

在返回用户空间以及从中断返回的时候，内核也会检查need_resched标志。如果已被设置，内核会在继续执行之前调用调度程序。
每个进程都包含一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量快（因为current宏速度很快并且描述符通常都在高速缓存中）。在2.2以前的内核版本中，该标志曾经是一个全局变量。2.2到2.4版内核中它在task_struct中。而在2.6版本中，它被移到thread_info结构体里，用一个特别的标志变量中的一位来表示。

用户抢占

内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。在内核返回用户空间的时候，它知道自己是安全的，因为既然它可以继续去执行当前进程，那么它当然可以再去选择一个新的进程去执行。所以，内核无论是在中断处理程序还是系统调用后返回，都会检查need_resched标志。如果它被设置了，那么，内核会选择一个其他的进程投入运行。从中断处理程序或者系统调用返回的返回路径都是更体系结构相关的，在entry.S（此文件不仅包含内核入口部分的程序，内核退出部分的相关代码也在其中）文件中通过汇编语言来实现。
简而言之，用户抢占在以下情况时产生：

  1. 从系统调用返回用户空间时。
  2. 从中断处理程序返回用户空间时。

内核抢占

与其他大部分的Unix变体喝其他大部分的操作系统不同，Linux完整地支持内核抢占。在不支持内核抢占的其他内核中，内核代码可以一直执行，到它完成为止。也就是说，调度程序没有办法办法在一个内核级的任务正在执行地时候重新调度–内核中的各任务是以协作方式调度的，不具备抢占性。内核代码一直要执行到完成（返回用户空间）或明显的阻塞为止。在2.6版的内核中，内核引入了抢占内力；现在，只要重新调度是安全的，内核就可以在任何时刻抢占正在执行的任务。
那么，什么时候重新调度才是安全的呢？只要没有持有锁，内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持SMP的，所以，如果没有持有锁，正在执行的代码就是可以重新导入的，也就是可以抢占的。
为了支持内核抢占所做的第一处变动，就是为每一个进程的thread_info引入preempt_count计数器。该计数器初始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0时，内核就可以抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果need_resched被设置，并且preempt_count为0的话，这说明有一个更为重要的任务需要执行且可以安全的抢占，此时，调度程序就会被调用。如果preempt_count不为0，说明当前任务持有锁，所以抢占是不安全的。这时，内核就会像通常那样直接从中断返回当前执行进程。如果当前进程持有的所有的锁都被释放了，preempt_count就会重新为0。此时，释放锁的代码会检查need_resched是否被设置。如果是的话，就会调用调度程序。有些内核代码需要允许或禁止内核抢占。
如果内核中的进程内阻塞了，或它显式的调用了schedule()，内核抢占也会显式地发生。这种形式的内核抢占从来都是受支持的，因为根本无须额外的逻辑来保证内核可以安全地被抢占。如果代码显式地调用了schedule()，那么它应该清楚自己是可以安全地被抢占的。
内核抢占发生在：

  1. 中断处理程序正在执行，且返回内核空间之前。
  2. 内核代码再一次具有可抢占性的时候。
  3. 如果内核中的任务显式地调用schedule()。
  4. 如果内核中的任务阻塞（这样同样会导致调用schedule()）。

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。借助调度类的框架，这些实时策略并不被完全公平调度器来管理，而是被一个特殊的实时调度器来管理。具体的实现定义在文件kernel/sched_rt.c中，在接下来的内容中我们将讨论实时调度策略和算法。
SCHED_FIFO实现了一种简单的、先入先出的调度算法：它不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止；它不基于时间片，可以一直执行下去。只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的同优先级的SCHED_FIFO级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器的时候才会退出。只要有SCHED_FIFO级进程在执行，其他级别较低的进程就只能等待它变为不可运行态后才有机会运行。
SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再继续执行了。也就是说。SCHED_RR是带有时间片的SCHED_FIFO–这是一种实时轮流调度算法。当SCHED_RR任务耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度。时间片只用来调度同一优先级的进程。对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程绝不能抢占SCHED_RR任务，即使它的时间片耗尽。
这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定级别的实时进程总能抢占优先级比它低的进程。
Linux的实时调度算法提供了一种软实时工作方式。软实时的含义是，内核调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求。相反，硬实时系统保证在一定条件下，可以满足任何调度的要求。Linux对于实时任务的调度不做任何保证。虽然不能保证硬实时工作方式，但Linux的实时调度算法的性能还是很不错的。2.6版的内核可以满足严格的时间要求。
实时优先级范围从0到MAX_RT_PRIO减1。默认情况下，MAX_RT_PRIO为100–所以默认的实时优先级范围是从0到99。SCHED_NORMAL级进程的nice值共享了这个取值空间；它的取值范围是从MAX_RT_PRIO到（MAX_RT_PRIO + 40）。也就是说，在默认情况下，nice值从-20到+19直接对应的是从100到139的实时优先级范围。

与调度有关的系统调用

Linux提供了一个系统调用族，用于管理与调度程序相关的参数。这些系统调用可以用来操作和处理进程优先级、调度策略及处理器绑定，同时还提供了显式地将处理器交给其他进程的机制。
与调度相关的系统调用

系统调用 描述
nice() 设置进程的nice值
sched_setscheduler() 设置进程的调度策略
sched_getscheduler() 获取进程的调度策略
sched_setparam() 设置进程的实时优先级
sched_getparam() 获取进程的实时优先级
sched_get_priority_max() 获取实时优先级的最大值
sched_get_priority_min() 获取实时优先级的最小值
sched_rr_get_interval() 获取进程的时间片值
sched_setaffinity() 设置进程的处理器的亲和力
sched_getaffinity() 获取进程的处理器的亲和力
sched_yield() 暂时让出处理器

与调度策略和优先级相关的系统调用

sched_setscheduler()和sched_getscheduler()分别用于设置和获取进程的调度策略和实时优先级。与其他的系统调用相似，它们的实现也是由许多参数检查、初始化和清理构成的。其实最重要的工作在于读取或改写进程task_struct的policy和rt_priority的值。
sched_setparam()和sched_getparam()分别用于设置和获取进程的实时优先级。这两个系统调用获取封装在sched_param特殊结构体的rt_priority中。sched_get_priority_max()和sched_get_priority_min()分别用于返回给定调度策略的的最大和最小优先级。实时调度策略的最大优先级是MAX_USER_RT_PRIO减1，最小优先级等于1。
对于一个普通的进程，nice()函数可以将给定进程的静态优先级增加一个给定的量。只有超级用户才能在调用它时使用负值，从而提高进程的优先级。nice()函数会调用内核的set_user_nice()函数，这个函数会设置进程的task_struct的static_prio和prio值。

与处理器绑定相关的系统调用

Linux调度程序提供强制的处理器绑定（processor affinity）机制。也就是说，虽然它尽力通过一种软的（或者说自然的）亲和性试图使进程尽量在同一个处理器上运行，但它也允许用户强制指定“这个进程无论如何都必须在这些处理器上运行”。这种强制的亲和性保存在进程task_struct的cpus_allowed这个位掩码标志中。该掩码标志的每一位对应一个系统可用的处理器。默认情况下，所有的位都被设置，进程可以在系统中所有的处理器上执行。用户可以通过sched_setaffinity()设置不同的一个或几个位组合的位掩码，而调用sched_getaffinity()则返回当前的cpus_allowed位掩码。
内核提供的强制处理器绑定的方法很简单。首先，当进程第一次创建时，它继承了父进程的相关掩码。由于父进程运行在特定的处理器上，子进程也运行在相应处理器上.其次，当处理器绑定关系改变时，内核会采用“移植线程”把任务推送到合法的处理器上。最后，加载平衡器只把任务拉到允许的处理器上，因此，进程只运行在指定处理器上，对处理器的指定是由该进程描述符的cpus_allowed域设置的。

放弃处理器时间

Linux通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。它是通过将进程从活动队列中（因为进程在执行，所以它肯定在此活动队列中）移到过期队列中实现的。由此产生的效果不仅仅抢占了该进程并将其放入优先级队列的最后面，还将其放入过期队列中–这样能确保它在一段时间内不会再运行了。由于实时进程不会过期，所以属于例外。它们只被移动到其优先级队列的最后面（不会放到过期队列中）。在Linux的早期版本中，sched_yield()的语义有所不同，进程只会被放到优先级队列的末尾，放弃的时间往往不会太长。现在，应用程序甚至内核代码在调用sched_yield()前，应该仔细考虑是否真的希望放弃处理器时间。
内核代码为了方便，可以直接调用yield()，先要确定给定进程确实处于可执行状态，然后再调用sched_yield()。用户空间的应用程序直接使用sched_yield()系统调用就可以了。

小结

进程调度程序是内核重要的组成部分，因为运行着的进程首先在使用计算机（至少在我们大多数人看来）。然而，满足进程调度的各种需要绝不是轻而易举的：很难找到“一刀切”的算法，既适合众多的可运行进程，又具有可伸缩性，还能在调度周期和吞吐量之间求得平衡，同时还满足各种负载的需求。不过，Linux内核新的CFS调度程序尽量满足了各个方面的需求，并比较完善的可伸缩性和新颖的方法提供了最佳的解决方案。
前面的章节覆盖了进程管理的相关内容，本章则考察了进程调度所遵循的基本原理、具体实现、调度算法以及目前Linux内核所使用的接口。