O(n)、O(1)和CFS调度器(Linux内核调度)

一、前言

随着内核版本的演进，其源代码的膨胀速度也在递增，这让Linux的学习曲线变得越来越陡峭了。这对初识内核的同学而言当然不是什么好事情，满腔热情很容易被当头浇灭。我有一个循序渐进的方法，那就是先不要看最新的内核，首先找到一个古老版本的内核（一般都会比较简单），将其吃透，然后一点点的迭代，理解每个版本变更背后的缘由和目的，最终推进到最新内核版本。

本文就是从2.4时代的任务调度器开始，详细描述其实现并慢慢向前递进。当然，为了更好的理解Linux调度器设计和实现，我们在第二章给出了一些通用的概念。之后，我们会在第四章讲述O（1）调度器如何改进并提升调度器性能。真正有划时代意义的是CFS调度器，在2.6.23版本的内核中并入主线。它的设计思想是那么的眩目，即便是目前最新的内核中，完全公平的设计思想仍然没有太大变化，这些我们会在第六章描述。第五章是关于公平调度思想的引入，通过这一章可以了解Con Kolivas的RSDL调度器，它是开启公平调度的先锋，通过这一章的铺垫，我们可以更顺畅的理解CFS。

二、任务调度器概述

为了不引起混乱，我们一开始先澄清几个概念。进程调度器是传统的说法，但是实际上进程是资源管理的单位，线程才是调度的单位，但是线程调度器的说法让我觉得很不舒服，因此最终采用进程调度器或者任务调度器的说法。为了节省字，本文有些地方也直接简称调度器，此外，除非特别说明，本文中的“进程”指的是task struct代表的那个实体，毕竟这是一篇讲调度器的文档。

任务调度器是操作系统一个很重要的部件，它的主要功能就是把系统中的task调度到各个CPU上去执行满足如下的性能需求：

1、对于time-sharing的进程，调度器必须是公平的

2、快速的进程响应时间

3、系统的throughput要高

4、功耗要小

当然，不同的任务有不同的需求，因此我们需要对任务进行分类：一种是普通进程，另外一种是实时进程。对于实时进程，毫无疑问快速响应的需求是最重要的，而对于普通进程，我们需要兼顾前三点的需求。相信你也发现了，这些需求是互相冲突的，对于这些time-sharing的普通进程如何平衡设计呢？这里需要进一步将普通进程细分为交互式进程（interactive processs）和批处理进程（batch process）。交互式进程需要和用户进行交流，因此对调度延迟比较敏感，而批处理进程属于那种在后台默默干活的，因此它更注重throughput的需求。当然，无论如何，分享时间片的普通进程还是需要兼顾公平，不能有人大鱼大肉，有人连汤都喝不上。功耗的需求其实一直以来都没有特别被调度器重视，当然在linux大量在手持设备上应用之后，调度器不得不面对这个问题了，当然限于篇幅，本文就不展开了。

为了达到这些设计目标，调度器必须要考虑某些调度因素，比如说“优先级”、“时间片”等。很多RTOS的调度器都是priority-based的，官大一级压死人，调度器总是选择优先级最高的那个进程执行。而在Linux内核中，优先级就是实时进程调度的主要考虑因素。而对于普通进程，如何细分时间片则是调度器的核心思考点。过大的时间片会严重损伤系统的响应延迟，让用户明显能够感知到延迟，卡顿，从而影响用户体验。较小的时间片虽然有助于减少调度延迟，但是频繁的切换对系统的throughput会造成严重的影响。因为这时候大部分的CPU时间用于进程切换，而忘记了它本来的功能其实就是推动任务的执行。

由于Linux是一个通用操作系统，它的目标是星辰大海，既能运行在嵌入式平台上，又能在服务器领域中获得很好的性能表现，此外在桌面应用场景中，也不能让用户有较差的用户体验。因此，Linux任务调度器的设计是一个极具挑战性的工作，需要在各种有冲突的需求中维持平衡。还好，经过几十年内核黑客孜孜不倦的努力，Linux内核正在向着最终目标迈进。

三、2.4时代的O（n）调度器

网上有很多的linux内核考古队，挖掘非常古老内核的设计和实现。虽然我对进程调度器历史感兴趣，但是我只对“近代史”感兴趣，因此，让我们从2.4时代开始吧，具体的内核版本我选择的是2.4.18版本，该版本的调度器相关软件结构可以参考下面的图片：

在runqueue队列中的全部进程时间片被耗尽之前，系统总会处于这样一个状态：最后的一组尚存时间片的进程分分别调度到各个CPU上去。我们以4个CPU为例，T0～T3分别运行在CPU0~CPU3上。随着系统的运行，CPU2上的T2首先耗尽了其时间片，但是这时候，其实CPU2上也是无法进行调度的，因为遍历runqueue链表，找不到适合的进程调度运行，因此它只能是处于idle状态。也许随后T0和T3也耗尽其时间片，从而导致CPU0和CPU3也进入了idle状态。现在只剩下最后一个进程T1仍然在CPU1上运行，而其他系统中的处理器处于idle状态，白白的浪费资源。唯一能改变这个状态的是T1耗尽其时间片，从而启动一个重新计算时间片的过程，这时候，正常的调度就可以恢复了。随着系统中CPU数目的加大，资源浪费会越来越严重。

（4）task bouncing issue

一般而言，一个进程最好是从一而终，假如它运行在系统中的某个CPU中，那么在其处于可运行状态的过程中，最好是一直保持在该CPU上运行。不过在O（n）调度器下，很多人都反映有进程在CPU之间跳来跳去的现象。其根本的原因也是和时间片算法相关。在一个新的周期开后，runqueue中的进程时间片都是满满的，在各个CPU上调度进程的时候，它可选择的比较多，再加上调度器倾向于调度上次运行在本CPU的进程，因此调度器有很大的机会把上次运行的进程调度到同一个处理器上。但是随着runqueue中的进程一个个的耗尽其时间片，cpu可选择的余地在不断的压缩，从而导致进程执行在一个和它亲和性不大的处理器（例如上次该进程运行在CPU0，但是这个将其调度到CPU1执行，但是实际上该进程和CPU0的亲和性更大些）。

（5）RT进程调度性能问题

实时调度的性能一般。通过上一节的介绍，我们知道，实时进程和普通进程挂在一个链表中。当调度实时进程的时候，我们需要遍历整个runqueue列表，扫描并计算所有进程的调度指数，从而选择出心仪的那个实时进程。按理说实时进程和普通进程位于不同的调度空间，两不相干，但是现在调度实时进程还需要扫描计算普通进程，这样糟糕的算法让那些关注实时性的工程师不能忍受。

当然，上面的这些还不是关键，最重要的是整个linux内核不是抢占式内核，在整个内核态都不能被抢占。对于一些比较耗时（可能几个毫秒）的系统调用或者中断处理，必须返回用户空间才启动调度是不可接受的。除了内核抢占性之外，优先级翻转问题也需要引起调度器的重视，否则即便一个rt进程变成runnable状态了，但是也只能眼睁睁的看着比它优先级低的进程运行，直到该rt进程等待的资源被释放。

（6）交互式普通进程的调度延迟问题

O（n）并不区分交互式进程和批处理进程，它只是奖励经常睡眠的那些进程。但是有些批处理进程也属于IO-bound进程，例如数据库服务进程，它本身是一个后台进程，对调度延迟不敏感，但是由于它需要和磁盘打交道，因此也会经常阻塞在disk IO上。对这样的后台进程进行动态优先级的升高其实是没有意义的，会增大其他交互式进程的调度延迟。另外一方面，用户交互式进程也可能是CPU-bound的，而这时候调度器不会正确的了解到该进程的调度需求并对其进行补偿。

（7）时间片粒度问题。

用户感知到的响应延迟是和系统负载相关，我们可以用runnable进程数目来粗略的描述系统的负载。当系统负载高的时候，runqueue中的进程数目会比较多，一次调度周期的时间就会比较长，例如在HZ=100的情况下，runqueue上有5个runnable进程，nice value是0，每个时间片配额是60ms，那么一个调度周期就是300ms。随着runnable进程增大，调度周期也变大。当一个进程耗尽其时间片之后，只能等待下一个调度周期到来。因此随着调度周期变大，系统响应也会变的较差。

虽然O（n）调度器存在不少的issue，但是社区的人还是基本认可这套算法的，因此在设计新的调度器的时候并不是完全推翻O（n）调度器的设计，而是针对O（n）调度器的问题进行改进。在本章中我们选择2.6.11版本的内核来描述O（1）调度器如何运作。鉴于O（1）调度器和O（n）调度器没有本质区别，因此我们只是描述它们之间不同的地方。

2、O（1）调度器的软件功能划分

下图是一个O（1）调度器的软件框架：

O（n）调度器中只有一个全局的runqueue，严重影响了扩展性，因此在O（1）调度器中引入了per-CPU runqueue的概念。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue，然后由主调度器和tick调度器驱动该CPU上的调度行为。由于篇幅的原因，我们在本文中不讲解负载均衡模块，把重点放在单个CPU上的任务调度算法。

由于引入了per-CPU runqueue，O（1）调度器删除了全局runqueue的spin lock，而是把这个spin lock放入到per-CPU runqueue数据结构中（rq->lock），通过把一个大锁细分成小锁，可以大大降低调度延迟，提升系统响应时间。这种方法在内核中经常使用，是一个比较通用的性能优化方法。

通过上面的软件结构划分可以解决O（n）调度的SMP扩展性问题和CPU空转问题。此外，好的复杂均衡算法也可以解决O（n）调度器的task bouncing 问题。

3、O（1）调度器的runqueue结构

O（1）调度器的基本优化思路就是把原来runqueue上的单链表变成多个链表，即每一个优先级的进程被挂入不同链表中。相关的软件结构可以参考下面的图片：

在调度器中，runqueue是一个很重要的数据结构，它最重要的作用是管理那些处于可运行状态的进程。O（1）调度器引入了优先级队列的概念来管理task，具体由struct prio_array抽象：

struct prio_array {

unsigned int nr_active;

unsigned long bitmap[BITMAP_SIZE];

struct list_head queue[MAX_PRIO];

};

由于支持140个优先级，因此queue成员中有140个分别表示各个优先级的链表头，不同优先级的进程挂入不同的链表中。bitmap 是表示各个优先级进程链表是空还是非空。nr_active表示这个队列中有多少个task。在这些队列中，100～139是普通进程的优先级，其他的是实时进程的优先级。因此，在O（1）调度器中，RT进程和普通进程被区分开了，普通进程根本不会影响RT进程的调度。

Runqueue中有两个优先级队列（struct prio_array）分别用来管理active（即时间片还有剩余）和expired（时间片耗尽）的进程。Runqueue中有两个优先级队列的指针，分别指向这两个优先级队列。随着系统的运行，active队列的task一个个的耗尽其时间片，挂入到expired队列。当active队列的task为空的时候，切换active和expired队列，开始一轮新的调度过程。

虽然在O（1）调度器中task组织的形式发生了变化，但是其核心思想仍然和O（n）调度器一致的，都是把CPU资源分成一个个的时间片，分配给每一个runnable的进程。进程用完其额度后被抢占，等待下一个调度周期的到来。

4、核心调度算法

主调度器（就是schedule函数）的主要功能是从该CPU的runqueue找到一个最合适的进程调度执行。其基本的思路就是从active优先级队列中寻找，代码如下：

idx = sched_find_first_bit(array->bitmap);

queue = array->queue + idx;

next = list_entry(queue->next, task_t, run_list);

首先在当前active优先级队列的bitmap寻找第一个非空的进程链表，然后从该链表中找到的第一个节点就是最适合下一个调度执行的进程。由于没有遍历整个链表的操作，因此这个调度器的算法复杂度是一个常量，从而解决了O（n）算法复杂度的issue。

如果当前active优先级队列中“空无一人”（nr_active等于0），那么这时候就需要切换active和expired优先级队列了：

if (unlikely(!array->nr_active)) {

rq->active = rq->expired;

rq->expired = array;

array = rq->active;

}

切换很快，并没有一个遍历所有进程重新赋default时间片的操作（大大缩减了runqueue临界区的size）。这些都避免了O（n）调度器带来的种种问题，从而提高了调度器的性能。

5、静态优先级和动态优先级

在前面的小节中，我们有意的忽略了优先级队列中“优先级”的具体含义，现在是需要澄清的时候了。其实优先级队列中“优先级”指的是动态优先级，从这个角度看，O（1）和O（n）调度器的调度算法又统一了，都是根据动态优先级进行调度。

O（1）的静态优先级的概念和O（n）是类似的，对于实时进程保存在进程描述符的rt_priority成员中，取值范围是1（优先级最低）～99（优先级最高）。对于普通进程，静态优先级则保存在static_prio成员中，取值范围是100（优先级最高）～139（优先级最低），分别对应nice value的-20 ～ 19。

了解了静态优先级之后，我们一起来看看动态优先级（保存在进程描述符的prio成员中）。鉴于在实际调度的时候使用的是动态优先级，我们必须要保证它是单调的（静态优先级未能保持单调，rt的99和普通进程的100都是静态优先级的最高点，也就是说在静态优先级数轴上，rt段是单调上升，而在普通进程段是单调下降的）。为了解决这个问题，在计算实时进程动态优先级的时候进行了一个简单的映射：

p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;

通过这样的转换，rt的动态优先级在数轴上也是单调下降的了。普通进程的动态优先级计算没有那么简单，除了静态优先级，还需要考虑进程的平均睡眠时间（保存在进程描述符的sleep_avg成员中），并根据该值对进程进行奖惩。具体代码可以参考effective_prio函数，这里不再详述，最终普通进程的动态优先级是100（优先级最高）～139（优先级最低），和静态优先级的取值范围是一致的。

在本小节的最后，我们一起来对比普通进程在O（1）和O（n）调度器的动态优先级算法。这个两个调度器的基本思路是一致的：考虑静态优先级，辅以对该进程的“用户交互指数”的评估，用户交互指数高的，调升其动态优先级，反之则降低。不过在评估用户交互指数上，O（1）显然做的更好。O（n）调度器仅仅考虑了睡眠进程的剩余时间片，而O（1）的“平均睡眠时间”算法显然考虑更多的因素：在cpu上的执行时间、在runqueue中的等待时间、睡眠时间、睡眠时候的进程状态（是否可被信号打断），什么上下文唤醒（中断上下文唤醒还是在进程上下文中唤醒）……因此O（1）调度器更好的判断了进程是属于interactive process还是batch process，从而精准的为interactive process打call。

6、时间片处理

缺省时间片的计算是通过task_timeslice完成的，在O（1）调度器中，缺省时间片已经和HZ无关了，无论如何设置HZ，静态优先级为[ -20 … 0 … 19 ]的普通进程其缺省时间片为[800ms … 100ms … 5ms]。

在tick到来的时候，当前task的时间片会递减（–p->time_slice），当时间片等于0的时候，会将该task从active优先级列表中摘下，设定resched标记，并且重置时间片，代码如下：

dequeue_task(p, rq->active);

set_tsk_need_resched§;

p->time_slice = task_timeslice§;

task_timeslice函数就是用来计算进程时间片的配额的。对于O（1）调度器，时间片的重新赋值是分散处理的，在各个task耗尽其时间片之后立刻进行的。这样的改动也修正了O（n）调度器一次性的遍历系统所有进程，重新为时间片赋值的过程。

6、识别用户交互式进程

一般而言，时间片耗尽之后，该task会被挂入到expired优先级队列，这时候如果想要被调度只能等到下次active和expired切换了。不过，有些特殊的场景需要特殊处理：

if (!TASK_INTERACTIVE§ || EXPIRED_STARVING(rq)) {

enqueue_task(p, rq->expired);

if (p->static_prio < rq->best_expired_prio)

rq->best_expired_prio = p->static_prio;

} else

enqueue_task(p, rq->active);

这里TASK_INTERACTIVE是用来判断一个进程是否是一个用户交互式进程（也是和平均睡眠时间相关，由此可见，平均睡眠时间不仅用于计算动态优先级，还用来决定一个进程是否回插入active队列），如果是的话，说明该进程对用户响应比较敏感，这时候不能粗暴的挂入expired队列，而是重新挂入active队列，继续有机会获取调度执行的机会。由此可见，O（1）调度器真是对用户交互式进程非常的照顾，一旦被判断是用户交互型进程，那么它将获取连续执行的机会。当然，调度器也不能太过分，如果用户交互型进程持续占用CPU，那么在expired队列中苦苦等待进程怎么办？这时候就要看看expired队列中的进程的饥饿状态了，这也就是EXPIRED_STARVING这个宏定义的功能。如果expired队列中的进程等待了太长的时间，那么说明调度器已经出现严重不公平的现象，因此这时候即便是判断当前耗尽时间片的进程是用户交互型进程，也把它挂入expired队列，尽快的完成本次调度周期，让active和expired发生切换。

O（1）调度器使用非常复杂的算法来判断进程的用户交互指数以及进程是否是交互式进程，hardcode了很多的不知其所以然的常数，估计也是通过各种大量的实验场景总结出来的。这部分的设计概念我是在是没有勇气去探索，因此这里就略过了。但是无论如何，它总是比仅仅考虑睡眠时间的O（n）调度器性能要好。

7、抢占式内核

2.4时代，大部分的Linux应用都集中在服务器领域，因此非抢占式内核的设计选择也无可厚非。不过随着Linux在桌面和嵌入式上的渗透，系统响应慢慢的称为用户投诉的主要方面，因此，在2.5的开发过程中，Linux引入了抢占式内核的概念（CONFIG_PREEMPT），如果没有配置该选项，那么一切和2.4内核保持一致，如果配置了该选项，那么不需要在返回用户空间的时候才苦苦等到调度点，大部分的内核执行路径都是可以被抢占的。同样的，限于篇幅，这里不再展开描述。

五、公平调度思想的引入

1、传统调度器时间片悖论

在O（n）和O（1）调度器中，时间片是固定分配的，静态优先级高的进程获取更大的time slice。例如nice value等于20的进程获取的default timeslice是5ms，而nice value等于0的进程获取的是100ms。直观上，这样的策略没有毛病（高优先级的获取更多的执行时间），但是，这样的设定潜台词就是：高优先级的进程会获得更多的连续执行的机会，这是CPU-bound进程期望的，但是实际上，CPU-bound进程往往在后台执行，其优先级都是比较低的。

因此，假设我们调度策略就是根据进程静态优先级确定一个固定大小的时间片，这时候我们在如何分配时间片上会遇到两难的状况：想要给用户交互型进程设定高优先级，以便它能有更好的用户体验，但是分配一个大的时间片是毫无意义的，因为这种进程多半是处于阻塞态，等待用户的输入。而后台进程的优先级一般不高，但是根据其优先级分配一个较小的时间片往往会影响其性能，这种类型的进程最好是趁着cache hot的时候狂奔。

怎么办？或者传统调度器固定分配时间片这个设计概念就是错误的。

2、传统调度器的卡顿问题

在Linux 2.5版本的开发过程中，Ingo Molnar设计的O（1）调度器替换掉了原始的、简陋的O（n）调度器，从而解决了扩展性很差，性能不佳的问题。在大部分的场景中，该调度器都获得了满意的性能，在商用的Linux 2.4发行版中，O（1）调度器被很多厂商反向移植到Linux 2.4中，由此可见O（1）调度器性能还是优异的。

然而O（1）并非完美，在实际的使用过程中，还是有不少的桌面用户在抱怨用户交互性比较差。当一个相当消耗CPU资源的进程启动的时候，现存的那些用户交互程序（例如你在通过浏览器查看网页）都可以感觉到明显的延迟。针对这些issue，很多天才工程师试图通过对用户交互指数算法的的修改来解决问题，这里面就包括公平调度思想的提出者Con Kolivas。不过无论如何调整算法，总是有点拆东墙补西墙的感觉，一个场景的issue修复了，另外一个场景又冒出来交互性不好的issue，刁钻的客户总是能够在边边角角的场景中找到让用户感觉到的响应延迟。

在反反复复修复用户卡顿issue的过程中，工程师最容易烦躁，而往往这时候最需要冷静的思考。Con Kolivas仔细的检视了调度器代码，他发现出问题的是评估进程用户交互指数的代码。为何调度器要根据进程的行为猜测其对交互性的需求？这根本是一项不可能完成的任务，因为你总是不会100％全部猜中，就好像你去猜测你喜欢的女孩子的心事一样，你细心的收集了关于这个女孩子的性格特点，业余爱好，做事风格，逻辑思维水平，星座……甚至生理周期，并期望着能总是正确的猜中其心中所想，坦率的讲这是不可能的。在进程调度这件事情上为何不能根据实实在在确定的东西来调度呢？一个进程的静态优先级已经完成的说明了其调度需求了，这就足够了，不需要猜测进程对交互性的需求，只要维持公平就OK了，而所谓的公平就是进程获取和其静态优先级匹配的CPU执行时间。在这样的思想指导下，Con Kolivas提出了RSDL（Rotating Staircase Deadline）调度器。

3、RSDL调度器

RSDL调度器仍然沿用了O（1）调度的数据结构和软件结构，当然删除了那些令人毛骨悚然的评估进程交互指数的代码。我们这一小节不可能详细描述RSDL算法，不过只要讲清楚Rotating、Staircase和Deadline这三个基本概念，大家就应该对RSDL有基本的了解了。

首先看Staircase概念，它更详细表述应该是priority staircase，即在进程调度过程中，其优先级会象下楼梯那样一点点的降低。在传统的调度概念中，一个进程有一个和其静态优先级相匹配的时间片，在RSDL中，同样也存在这样的时间片，但是时间片是散布在很多优先级中。例如如果一个进程的优先级是120，那么整个时间片散布在120～139的优先级中，在一个调度周期，进程开始是挂入120的优先级队列，并在其上运行6ms（这是一个可调参数，我们假设每个优先级的时间配额是6ms），一旦在120级别的时间配额使用完毕之后，该进程会转入121的队列中（优先级降低一个level），发生一次Rotating，更准确的说是Priority minor rotating。之后，该进程沿阶而下，直到139的优先级，在这个优先级上如果耗尽了6ms的时间片，这时候，该进程所有的时间片就都耗尽了，就会被挂入到expired队列中去等待下一个调度周期。这次rotating被称为major rotating。当然，这时候该进程会挂入其静态优先级对应的expired队列，即一切又回到了调度的起点。

Deadline是指在RSDL算法中，任何一个进程可以准确的预估其调度延迟。一个简单的例子，假设runqueue中有两个task，静态优先级分别是130的A进程和139的B进程。对于A进程，只有在进程沿着优先级楼梯从130走到139的时候，B进程才有机会执行，其调度延迟是9 x 6ms ＝ 54ms。

多么简洁的算法，只需要维持公平，没有对进程睡眠/运行时间的统计，没有对用户交互指数的计算，没有那些奇奇怪怪的常数……调度，就是这么简单。

六、CFS调度器

Con Kolivas的RSDL调度器始终没有能够进入kernel mainline，取而代之的是同样基于公平调度思想的CFS调度器，在CFS调度器并入主线的同时，仍然提供了模块化的设计，为RSDL或者其他的调度器可以进入内核提供了方便。然而Con Kolivas带着对内核开发模式的不满永远的退出了社区，正所谓有人的地方就有江湖，其中的是非留给后人评说吧。

CFS的设计理念就是一句话：在真实的硬件上实现理想的、精准、完全公平的多任务调度。当然，这样的调度器不存在，在实际设计和实现的时候还是需要做一些折衷。其实CFS调度器的所有的设计思想在上一章都已经非常明晰，本章我们唯一需要描述的是Ingo Molnar如何把完全公平调度的理想照进现实。

1、模块化思想的引入

从2.6.23内核开始，调度器采用了模块化设计的思想，从而把进程调度的软件分成了两个层次，一个是core scheduler layer，另外一个是specific scheduler layer：

从功能层面上看，进程调度仍然分成两个部分，第一个部分是通过负载均衡模块将各个runnable task根据负载情况平均分配到各个CPU runqueue上去。第二部分的功能是在各个CPU的Main scheduler和Tick scheduler的驱动下进行单个CPU上的调度。调度器处理的task各不相同，有RT task，有normal task，有Deal line task，但是无论哪一种task，它们都有共同的逻辑，这部分被抽象成Core scheduler layer，同时各种特定类型的调度器定义自己的sched_class，并以链表的形式加入到系统中。这样的模块化设计可以方便用户根据自己的场景定义specific scheduler，而不需要改动Core scheduler layer的逻辑。

2、关于公平

和RSDL调度器一样，CFS调度器追求的公平是CPU资源分配的公平，即CPU的运算资源被精准的平均分配给在其上运行的task。例如：如果有2个静态优先级一样的task运行在某一个CPU上，那么每一个task都消耗50％的CPU计算资源。如果静态优先级不一样，那么，CPU资源是根据其静态优先级来具体分配。具体如何根据优先级来分配CPU资源呢？这里就需要引入一个load weight的概念。

在CFS中，我们是通过一个常量数组（sched_prio_to_weight）可以把进程静态优先级映射成进程权重，而所谓的权重就是进程应该占有cpu资源的比重。例如：系统中有3个runnable thread A、B和C，权重分别是a、b、c，那么A thread应该分配到的CPU资源是a/(a+b+c)。因此CFS调度器的公平就是保证所有的可运行状态的进程按照权重分配其CPU资源。

3、时间粒度

CPU资源分配是一个抽象的概念，最终在实现调度器的时候，我们需要把它具体化。一个最简单的方法就是把CPU资源的分配变成CPU时间片的分配。看到“时间片”这个术语，你可能本能的觉得CFS和O（1）也没有什么不同，不都是分配时间片吗？其实不然，Linux内核的CFS调度器已经摒弃了传统的固定时间片的概念了。O（1）调度器会为每一个进程分配一个缺省的时间片，当进程使用完自己的时间片之后就会被挂入expire队列，当系统中的所有进程都耗光了自己的时间片，那么一切从来，所有的进程又恢复了自己的时间片，进入active队列。CFS调度器没有传统的静态时间片的概念，她的时间片是动态的，和当前CPU的可运行状态的进程以及它们的优先级相关，因此CFS调度器中，时间片是动态变化的。

对于理想的完全公平调度算法，无论观察的时间段多么短，CPU的时间片都是公平分配的。以100ms的粒度来观察，那么两个可运行状态的进程A和B（静态优先级一样）各分50ms。当然，也不是一定是A执行50ms，切换到B，然后再执行50ms，在观察过程中，A和B可能切换了很多次，但是A进程总共占用CPU的时间和就是50ms，B进程亦然。如果用1ms的粒度来观察呢？是否A和B个运行500us？如果继续缩减观察时间，在一个微秒的时间段观察呢？显然，不太可能每个进程运行500ns，如果那样的话，CPU的时间大量的消耗在了进程切换上，真正做事情的CPU时间变得越来越少了。因此，CFS调度器是有一个时间粒度的定义，我们称之调度周期。也就是说，在一个调度周期内，CFS调度器可以保证所有的可运行状态的进程平均分配CPU时间。下一小节我们会详细描述调度周期的概念。

4、如何保证有界的调度延迟？

传统的调度器无法保证调度延迟，为了说明这个问题我们设想这样一个场景：CPU runqueue中有两个nice value等于0的runnable进程A和B，传统调度器会为每一个进程分配一个固定的时间片100ms，这时候A先运行，直到100ms的时间片耗尽，然后B运行。这两个进程会交替运行，调度延迟就是100ms。随着系统负荷的加重，例如又有两个两个nice value等于0的runnable进程C和D挂入runqueue，这时候，A、B、C、D交替运行，调度延迟就是300ms。因此，传统调度器的调度延迟是和系统负载相关的，当系统负载增加的时候，用户更容易观察到卡顿现象。

CFS调度器设计之初就确定了调度延迟的参数，我们称之targeted latency，这个概念类似传统调度器中的调度周期的概念，只不过在过去，一个调度周期中的时间片被固定分配给了runnable的进程，而在CFS中，调度器会不断的检查在一个targeted latency中，公平性是否得到了保证。下面的代码说明了targeted latency的计算过程：

static u64 __sched_period(unsigned long nr_running)

{

if (unlikely(nr_running > sched_nr_latency))

return nr_running * sysctl_sched_min_granularity;

else

return sysctl_sched_latency;

}

当runqueue中的runnable进程的数目小于sched_nr_latency（8个）的时候，targeted latency就是sysctl_sched_latency（6ms），当runqueue中的runnable进程的数目大于等于sched_nr_latency的时候，targeted latency等于runnable进程数目乘以sysctl_sched_min_granularity（0.75ms）。显然sysctl_sched_min_granularity这个参数就是一段一个进程被调度执行，它需要至少执行的时间片大小，设立这个参数是为了防止overscheduling而产生的性能下降。

CFS调度器保证了在一个targeted latency中，所有的runnable进程都会至少执行一次，从而保证了有界的、可预测的调度延迟。

5、为何引入虚拟时间？

虽然Con Kolivas提出了精采绝伦的设计思想，但是在具体实现的时候相对保守。CFS调度器则不然，它采用了相对激进的方法，把runqueue中管理task的优先级链表变成了红黑树结构。有了这样一颗runnable进程的红黑树，在插入操作的时候如何确定进程在红黑树中的位置？也就是说这棵树的“key”是什么？

CFS的红黑树使用vruntime（virtual runtime）作为key，为了理解vruntime，这里需要引入一个虚拟时间轴的概念。在上一章中，我们已经清楚的表述了公平的含义：按照进程的静态优先级来分配CPU资源，当然，CPU资源也就是CPU的时间片，因此在物理世界中，公平就是分配和静态优先级匹配的CPU时间片。但是红黑树需要一个单一数轴上的量进行比对，而这里有两个度量因素：静态优先级和物理时间片，因此我们需要把它们映射到一个虚拟的时间轴上，屏蔽掉静态优先级的影响，具体的计算公式如下：

Virtual runtime ＝ （physical runtime） X （nice value 0的权重）/进程的权重

通过上面的公式，我们构造了一个虚拟的世界。二维的（load weight，physical runtime）物理世界变成了一维的virtual runtime的虚拟世界。在这个虚拟的世界中，各个进程的vruntime可以比较大小，以便确定其在红黑树中的位置，而CFS调度器的公平也就是维护虚拟世界vruntime的公平，即各个进程的vruntime是相等的。

根据上面的公式，我们可以看出：实际上对于静态优先级是120（即nice value等于0）的进程，其物理时间轴等于虚拟时间轴，而其他的静态优先级的虚拟时间都是根据其权重和nice 0的权重进行尺度缩放。对于更高优先级的进程，其虚拟时间轴过的比较慢，而对于优先级比较低的进程，其虚拟时间轴过的比较快。

我们可以举一个简单的例子来描述虚拟世界的公平性：例如在时间点a到b之间（虚拟时间轴），如果有两个可运行状态的进程A和B，那么从a到b这个时间段上去观察，CPU的时间是平均分配到每个一个进程上，也就是说A和B进程各自运行了（b-a）/2的时间，也就是各占50％的时间片。在b时间点，一个新的可运行状态的进程C产生了，直到c时间点。那么从b到c这个时间段上去观察，进程A、B和进程C都是执行了（c-b）/3的时间，也就是各占1/3的CPU资源。再强调一次，上面说的时间都是虚拟时间。

6、如何计算virtual runtime

想要计算时间我们必须有类似手表这样的计时工具，对于CFS调度器，这个“手表”保存在runqueue中（clock和clock_task成员）。Runqueue戴两块表，一块记录实际的物理时间，另外一块则是记录执行task的时间（clock_task）。之所以有clock_task是为了更准确的记录进程执行时间。实际上一个task执行过程中不免会遇到一些异步事件，例如中断。这时候，进程的执行被打断从而转入到对异步事件的处理过程。如果把这些时间也算入该进程的执行时间会有失偏颇，因此clock_task会把这些异步事件的处理时间去掉，只有在真正执行任务的时候，clock_task的counter才会不断累加计时。

有了clock进程计时变得比较简单了，当进程进入执行状态的时候，看一下clock_task这块“手表”，记录数值为A。在需要统计运行时间的时候，再次看一下clock_task这块“手表”，记录数值为B。B-A就是该进程已经运行的物理时间。当然，CFS关心的是虚拟时间，这时候还需要通过calc_delta_fair函数将这个物理时间转换成虚拟时间，然后累积的该进程的virtual runtime中（sched_entity中的vruntime），而这个vruntime就是红黑树的key。

7、CFS调度器的运作

对于CFS调度器，没有固定分配时间片的概念，只有一个固定权重的概念，是根据进程静态优先级计算出来的。CFS调度器一旦选择了一个进程进入执行状态，会立刻开启对其virtual runtime的跟踪过程，并且在tick到来时会更新这个virtual runtime。有了这个virtual runtime信息，调度器就可以不断的检查目前系统的公平性（而不是检查是否时间片用完），具体的方法是：根据当前系统的情况计算targeted latency（调度周期），在这个调度周期中计算当前进程应该获得的时间片（物理时间），然后计算当前进程已经累积执行的物理时间，如果大于当前应该获得的时间片，那么更新本进程的vruntime并标记need resched flag，并在最近的一个调度点发起调度。

在进行进程调度时候，调度器需要选择下一个占用CPU资源的那个next thread。对于CFS而言，其算法就是从红黑树中找到left most的那个task并调度其运行。这时候，失去CPU执行权的那个task会被重新插入红黑树，其在红黑树中的位置是由task的vruntime值决定的。

本文来源于蜗牛科技 http://www.wowotech.net/process_management/scheduler-history.html