多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。在单处理器机器上，这会产生多个进程在同时运行的幻觉。在多处理器机器上，这会使多个进程在不同的处理机上真正同时、并行地运行。无论在单处理器或者多处理器机器上，多任务操作系统都能使多个进程处于堵塞或者睡眠状态，也就是说，实际上不被投入执行，直到工作确实就绪。这些任务尽管位于内存，但并不处于可运行状态。相反，这些进程利用内核阻塞自己，直到某一事件（键盘输入、网络数据、过一段时间等）发生。因此，现代Linux系统也许有100个进程在内存，但是只有一个处于可运行状态。

抢占多任务

像所有Unix的变体和许多其他现代操作系统一样，Linux 提供了抢占式的多任务模式。在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会。这个强制的挂起动作就叫抢占( preemption)。进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，叫进程的时间片(timeslice)。时间片实际上就是分配给每个可运行进程的处理器时间段。有效管理时间片能使调度程序从系统全局的角度做出调度决定，这样做还可以避免个别进程独占系统资源。当今众多现代操作系统对程序运行都采用了动态时间片计算的方式，并且引入了可配置的计算策略。不过我们将看到，Linux 独一无二的“公平”调度程度本身并没有采取时间片来达到公平调度。

非抢占多任务

相反，在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步( yielding)。理想情况下，进程通常做出让步，以便让每个可运行进程享有足够的处理器时间。但这种机制有很多缺点:调度程序无法对每个进程该执行多长时间做出统一规定，所以进程独占的处理器时间可能超出用户的预料﹔更糟的是，一个决不做出让步的悬挂进程就能使系统崩溃。幸运的是，近20年以来，绝大部分的操作系统的设计都采用了抢占

Linux的进程调度

O(1)调度器虽然在拥有数以十计（不是数以百计）的多处理器的环境下尚能表现出近乎完美的性能和可扩展性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却有一些先天不足。这些程序我们称其为交互进程——它无疑包括了所有需要用户交互的程序。正因为如此，O(1)调度程序虽然对于大服务器的工作负载很理想，但是在有很多交互程序要运行的桌面系统上则表现不佳，因为其缺少交互进程。自2.6内核系统开发初期，开发人员为了提高对交互程序的调度性能引入了新的进程调度算法。其中最为著名的是“反转楼梯最后期限调度算法(Rotating Staircase Deadline scheduler)”(RSDL)，该算法吸取了队列理论，将公平调度的概念引入了Linux 调度程序。并且最终在2.6.23内核版本中替代了O(1)调度算法，它此刻被称为“完会公平调度算法"击简称CFS

总结就是 O(1)交互程序不不行，所以提出啦cfs

Linux策略

I/0消耗型和处理器消耗型的进度

进程可以被分为IO消耗型和处理器消耗型。前者指进程的大部分时间用来提交IO请求或是等待IO请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为它在等待更多的I/O请求时最后总会阻塞（这里所说的IO是指任何类型的可阻塞资源，比如键盘输入，或者是网络IO)。举例来说，多数用户图形界面程序(GUI)都属于IO密集型，即便它们从不读取或者写人磁盘，它们也会在多数时间里都在等待来自鼠标或者键盘的用户交互操作。

相反，处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的IO需求。但是，因为它们不属于IO驱动类型，所以从系统响应速度考虑，调度器不应该经常让它们运行。对于这类处理器消耗型的进程，调度策略往往是尽量降低它们的调度频率，而延长其运行时间。处理器消耗型进程的极端例子就是无限循环地执行。更具代表性的例子是那些执行大量数学计算的程序，如sshkeygen或者MATLAB。

也有两者集合：比如，X Window服务器既是I/O消耗型，也是处理器消耗型。还有些进程可以是IO消耗型，但属于处理器消耗型活动的范围。其典型的例子就是字处理器，其通常坐以等待键盘输入，但在任一时刻可能又粘住处理器疯狂地进行拼写检查或者宏计算。

调度策略通常要在两个矛盾的目标中间寻找平衡:进程响应迅速（响应时间短）和最大系统利用率（高吞吐量)。为了满足上述需求，调度程序通常采用一套非常复杂的算法来决定最值得运行的进程投入运行，但是它往往并不保证低优先级进程会被公平对待。Unix系统的调度程序更倾向于IO消耗型程序，以提供更好的程序响应速度。Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化（缩短响应时间)，更倾向于优先调度IO消耗型进程。虽然如此，但在下面你会看到，调度程序也并未忽略处理器消耗型的进程。

进程优先级

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（包括和99)。与nice值意义相反，越高的实时优先级数值意味着进程优先级越高。任何实时进程的伏先级都高于普通的进程，也就是说实时优先级和nice优先级处于互不相交的两个范畴。Linux 实时优先级的实现参考了Unix相关标准—一特别是POSIX.1b。

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片，但这并不是件简单的事。时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序﹔时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。此外，I/O消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来:IO消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如这样可以让它们的高速缓存命中率更高)。

Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的。这个比例进一步还会受进程nice值的影响，nice值作为权重将调整进程所使用的处理器时间使用比。具有更高nice值（更低优先权）的进程将被赋予低权重，从而丧失一小部分的处理器使用比﹔而具有更小nice值（更高优先级）的进程则会被赋予高权重，从而抢得更多的处理器使用比。

像前面所说的，Linux系统是抢占式的。当一个进程进入可运行态，它就被准许投入运行。在多数操作系统中，是否要将一个进程立刻投入运行（也就是抢占当前进程)，是完全由进程优先级和是否有时间片决定的。而在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，

调度策略的活动

想象下面这样一个系统，它拥有两个可运行的进程:一个文字编辑程序和一个视频编码程序。文字编辑程序显然是I/O消耗型的，因为它大部分时间都在等待用户的键盘输入（无论用户的输入速度有多快，都不可能赶上处理的速度)。用户总是希望按下键系统就能马上响应。相反，视频编码程序是处理器消耗型的。除了最开始从磁盘上读出原始数据流和最后把处理好的视频输出外，程序所有的时间都用来对原始数据进行视频编码，处理器很轻易地被100%使用。它对什么时间开始运行没有太严格的要求——用户几乎分辨不出也并不关心它到底是立刻就运行还是半秒钟以后才开始的。当然，它完成得越早越好，至于所花时间并不是我们关注的主要问题

在这样的场景中，理想情况是调度器应该给予文本编辑程序相比视频编码程序更多的处理器时间因为它属于交互式应用。对文本编辑器而言，

我们有两个目标。第一是我们希望系统给它更多的处理器时间，这并非因为它需要更多的处理器时间（其实它不需要)，是因为我们希望在它需要时总是能得到处理器﹔第二是我们希望文本编辑器能在其被唤醒时（也就是当用户打字时）抢占视频解码程序。这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入。

在Linux操作系统同样需要追求上述目标，但是它采用不同方法。它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。假如文本编辑器和视频解码程序是仅有的两个运行进程，并且又具有同样的nice值，那么处理器的使用比将都是50%——它们平分了处理器时间。但因为文本编辑器将更多的时间用于等待用户输人，因此它肯定不会用到处理器的50%。同时，视频解码程序无疑将能有机会用到超过50%的处理器时间，以便它能更快速地完成解码任务。

这里关键的问题是，当文本编辑器程序被唤醒时将发生什么。

我们首要目标是确保其能在用户输人发生时立刻运行。在上述场景中，一旦文本编辑器被唤醒，CFS注意到给它的处理器使用比是50%，但是其实它却用得少之又少。特别是，CFS 发现文本编辑器比视频解码器运行的时间短得多。这种情况下，为了兑现让所有进程能公平分享处理器的承诺，它会立刻抢占视频解码程序，让文本编辑器投入运行。文本编辑器运行后，立即处理了用户的击键输入后，又一次进入睡眠等待用户下一次输入。因为文本编辑器并没有消费掉承诺给它的50%处理器使用比，因此情况依旧，CFS总是会毫不犹豫地让文本编辑器在需要时被投入运行，而让视频处理程序只能在剩下的时刻运行。

Linux调度算法

调度器类

这种模块化结构被称为调度器类（ scheduler classes)，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

完全公平调度(CFS）是一个针对普通进程的调度类，在Linux中称为SCHED_NORMAL(在POSIX中称为SCHED_OTHER),CFS算法实现定义在文件kerneUsched_fair.c中。

Unix系统的进程调度

第一个问题，若要将nice值映射到时间片，就必然需要将nice单位值对应到处理器的绝对时间。但这样做将导致进程切换无法最优化进行。

举例说明，假定我们将默认nice值(0)分配给一个进程——对应的是一个100ms的时间片﹔同时再分配一个最高nice值（+20，最低的优先级）给另一个进程——对应的时间片是5ms。我们接着假定上述两个进程都处于可运行状态。那么默认优先级的进程将获得20/21 ( 105ms中的100ms）的处理器时间，而低优先级的进程会获得1/21 ( 105ms中的5ms)的处理器时间。我们本可以选择任意数值用于本例子中，但这个分配值正好是最具说服力的，所以我们选择它。现在，我们看看如果运行两个同等低优先级的进程情况将如何。我们是希望它们能各自获得一半的处理器时间，事实上也确实如此。但是任何一个进程每次仅仅只能获得5ms的处理器时间（10ms中各占一半)。也就是说，相比刚才例子中 105ms内进行一次上下文切换，现在则需要在10ms 内继续进行两次上下文切换。类推，如果是两个具有普通优先级的进程，它们同样会每个获得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。最后，时间片还会随着定时器节拍改变

第四个问题也是最后一个是关于基于优先级的调度器为了优化交互任务而唤醒相关进程的问题。

这种系统中，你可能为了进程能更快地投入运行，而去对新要唤醒的进程提升优先级，即便它们的时间片已经用尽了。虽然上述方法确实能提升不少交互性能，但是一些例外情况也有可能发生，因为它同时也给某些特殊的睡眠/唤醒用例一个玩弄调度器的后门，使得给定进程打破公平原则,获得更多处理器时间，损害系统中其他进程的利益。

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的运行时间。

你一定注意到了，当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间片都将趋于0。这样无疑造成了不可接受的切换消耗。CFS为此引入每个进程获得的时间片底线,这个底线称为最小粒度。默认情况下这个值是1ms。如此一来，即便是可运行进程数量趋于无穷，每个最少也能获得1ms 的运行时间，确保切换消耗被限制在一定范围内。(敏锐的读者会注意到假如在进程数量变得非常多的情况下，CFS并非一个完美的公平调度，因为这时处理器时间片再小也无法突破最小粒度。的确如此，尽管修改过的公平队列方法确实能提高这方面的公平性，但是CFS的算法本身其实已经决定在这方面做出折中了。但还好，因为通常情况下系统中只会有几百个可运行进程，无疑，这时CFS是相当公平的。)

现在，让我们再来看看具有不同nice值的两个可运行进程的运行情况——比如一个具有默认nice值(0)，另一个具有的nice值是5。这些不同的nice值对应不同的权重，所以上述两个进程将获得不同的处理器使用比。在这个例子中，nice值是5的进程的权重将是默认nice进程的1/3。如果我们的目标延迟是20ms，那么这两个进程将分别获得15ms和5ms的处理器时间。再比如我们的两个可运行进程的nice值分别是10和15，它们分配的时间片将是多少呢﹖还是15和5ms !可见，绝对的nice值不再影响调度决策:只有相对值才会影响处理器时间的分配比例。
总结一下，任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS称为公平调度器是因为它确保给每个进程公平的处理器使用比。正如我们知道的，CFS不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下,降低了调度延迟带来的不公平性。
 

`