郭健： Linux进程调度技术的前世今生之“今生”
本文紧接着：
作者简介
郭健，一名普通的内核工程师，以钻研Linux内核代码为乐，热衷于技术分享，和朋友一起创建了蜗窝科技的网站，希望能汇集有同样想法的技术人，以蜗牛的心态探讨技术。
(小编画外音:郭大侠是我最佩服的大侠，他为人低调，技术精湛又虚怀若谷，实为我辈Linuxer之楷模。他的http://www.wowotech.net/网站，有很多精彩的原创文章，已经使得百千万读者获益。侠之大者，为国为民。)
稿件征集
欢迎您给Linuxer投稿，赢得人民邮电异步社区任意在售技术图书。您随便挑，详情：Linuxer-"Linux开发者自己的媒体"第四月稿件录取和赠书名单
走过路过，不要错过Linuxer哦，点击二维码关注Linuxer！
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); p->time_slice = task_timeslice(p); |
task_timeslice函数就是用来计算进程时间片的配额的。对于O（1）调度器，时间片的重新赋值是分散处理的，在各个task耗尽其时间片之后立刻进行的。这样的改动也修正了O（n）调度器一次性的遍历系统所有进程，重新为时间片赋值的过程。
7、识别用户交互式进程
一般而言，时间片耗尽之后，该task会被挂入到expired优先级队列，这时候如果想要被调度只能等到下次active和expired切换了。不过，有些特殊的场景需要特殊处理：
if (!TASK_INTERACTIVE(p) || 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）调度器性能要好。
8、抢占式内核
2.4时代，大部分的Linux应用都集中在服务器领域，因此非抢占式内核的设计选择也无可厚非。不过随着Linux在桌面和嵌入式上的渗透，系统响应慢慢的称为用户投诉的主要方面，因此，在2.5的开发过程中，Linux引入了抢占式内核的概念（CONFIG_PREEMPT），如果没有配置该选项，那么一切和2.4内核保持一致，如果配置了该选项，那么不需要在返回用户空间的时候才苦苦等到调度点，大部分的内核执行路径都是可以被抢占的。同样的，限于篇幅，这里不再展开描述。
五、公平调度思想的引入
1、传统调度器时间片悖论
在O（n）和O（1）调度器中，时间片是固定分配的，静态优先级高的进程获取更大的time slice。例如nice value等于20的进程获取的defaulttimeslice是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（RotatingStaircase 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的Mainscheduler和Tickscheduler的驱动下进行单个CPU上的调度。调度器处理的task各不相同，有RT task，有normal task，有Deal line task，但是无论哪一种task，它们都有共同的逻辑，这部分被抽象成Core schedulerlayer，同时各种特定类型的调度器定义自己的sched_class，并以链表的形式加入到系统中。这样的模块化设计可以方便用户根据自己的场景定义specific scheduler，而不需要改动Core scheduler layer的逻辑。
2、关于公平
和RSDL调度器一样，CFS调度器追求的公平是CPU资源分配的公平，即CPU的运算资源被精准的平均分配给在其上运行的task。例如：如果有2个静态优先级一样的task运行在某一个CPU上，那么每一个task都消耗50％的CPU计算资源。如果静态优先级不一样，那么，CPU资源是根据其静态优先级来具体分配。具体如何根据优先级来分配CPU资源呢？这里就需要引入一个loadweight的概念。
在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调度器设计之初就确定了调度延迟的参数，我们称之targetedlatency，这个概念类似传统调度器中的调度周期的概念，只不过在过去，一个调度周期中的时间片被固定分配给了runnable的进程，而在CFS中，调度器会不断的检查在一个targetedlatency中，公平性是否得到了保证。下面的代码说明了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、如何计算virtualruntime
想要计算时间我们必须有类似手表这样的计时工具，对于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函数将这个物理时间转换成虚拟时间，然后累积的该进程的virtualruntime中（sched_entity中的vruntime），而这个vruntime就是红黑树的key。
7、CFS调度器的运作
对于CFS调度器，没有固定分配时间片的概念，只有一个固定权重的概念，是根据进程静态优先级计算出来的。CFS调度器一旦选择了一个进程进入执行状态，会立刻开启对其virtual runtime的跟踪过程，并且在tick到来时会更新这个virtualruntime。有了这个virtualruntime信息，调度器就可以不断的检查目前系统的公平性（而不是检查是否时间片用完），具体的方法是：根据当前系统的情况计算targeted latency（调度周期），在这个调度周期中计算当前进程应该获得的时间片（物理时间），然后计算当前进程已经累积执行的物理时间，如果大于当前应该获得的时间片，那么更新本进程的vruntime并标记need resched flag，并在最近的一个调度点发起调度。
在进行进程调度时候，调度器需要选择下一个占用CPU资源的那个nextthread。对于CFS而言，其算法就是从红黑树中找到left most的那个task并调度其运行。这时候，失去CPU执行权的那个task会被重新插入红黑树，其在红黑树中的位置是由task的vruntime值决定的。
七、结束语
本文简单的介绍了内核调度器的发展历程，从O（n）到O（1），最后进化成CFS调度器。当然，在调度器的历史中，还有很多的闪光点没有涉及，例如groupscheduling、bandwidthcontrol、Deadlinescheduler……如果有机会我们下回分解吧。
不知道有没有《郭健： Linux进程调度技术的前世今生之来世》啊？
敬请关注Linuer期待来世！
苹果用户打赏
安卓用户打赏