上一章学习了O(n)调度器的设计，以及它的核心算法，其主要思路如下：

• O(n)调度器采用一个Runqueue运行队列来管理所有可运行的进程，在主调度schedule函数中选择一个优先级最高，也就是时间片最大的进程来运行，同时也会对喜欢睡眠的进程做奖励，去增加此类进程的时间片
• 当Runqueue运行队列中无进程可选择时，则会对系统中所有的进程进行依次重新计算时间片的操作

针对这个调度，虽然简单，但是也存在缺点：

• 时间复杂度为O(n)，当系统中就绪队列中的进程数目增多，那么调度器的运算量就会线性增长，为每个进程计算其时间片的过程太耗费时间
• 多核处理器扩展问题，多核处理器的进程在同一个就绪队列中，因此调度器对它的所有操作都会因为全局自旋锁而导致系统各个处理器之间的等待，使的就绪队列称为明显的瓶颈
• 实时进程不能及时调度，内核不可抢占，如果某个进程，一旦进入内核状态，那么再高优先级的进程都无法剥夺，只有等进程返回用户态的时候才可以被调度。

针对以上问题，Linux2.6做了较大的改进，针对多处理器问题，为每个CPU设置一个就绪队列，实现了时间复杂度为O(1)的调度算法，本章重点学习以下内容：

• O(1)调度器是什么？
• O(1)调度算法如何实现？

O(1)调度算法介绍

Ingo Molnar在linux2.6版本的内核中加入了全新的调度算法，它能够在常数时间内调度任务，因此被称为O(1)调度器，它主要引入了一些新的特性：

• 全局优先级，范围为0~139，数值越低，优先级越高
• 将进程拆分成实时进程(0 ~ 99)和普通进程(100 ~ 139)，更高优先级任务获得更多的时间片
• 支持抢占，当任务状态变成TASK_RUNNING时，内核会检查其优先级是否比当前任务的优先级更高，如果是的话，则抢占当前正在运行的任务，切换到该任务
• 实时进程使用静态优先级
• 普通进程使用动态优先级，任务优先级会在其使用完自己的时间片后重新计算，内核会考虑它过去的行为，决定它的交互等级，交互型任务更容易得到调度

更多Linux内核视频教程文档资料免费领取后台私信【内核】自行获取。

对于O(n)调度器会在所有进程的时间片用完后，才会重新计算任务的优先级。而O(1)调度器则是在每个进程时间片用完后，就重新计算优先级。对于O(1)调度器为每个CPU维护了两个队列

• active队列：存放的是时间片尚未用完的任务
• expired队列：**存放的是时间片已经耗尽的任务

当一个队列的时间片用完后，就会被转到expired队列，而且会重新计算它的优先级，当active队列任务全部转移到expired队列后，会交换二者，使得active队列指向expired队列，expired队列指向active队列。可以看到，优先级的计算，队列切换都和任务数量多寡无关，能够在O(1)的时间复杂度下完成。其基本的思路如下图所示：

1. 当 active 中的任务时间片用完，那么就会被移动到 expired 中。
2. 当 active 中已经没有任务可以运行，就把 expired 与 active 交换，从而 expired 中的任务可以重新被调度。

O(1)调度算法数据结构

为了减小多核CPU之间的竞争，所以每个CPU都需要维护一份本地的优先级队列，因为如果使用全局的优先级，那么多核CPU就需要对全局优先队列进行上锁，从而导致性能下降。runqueue结构主要维护调度相关的信息，其定义如下：

接下来，我们看看prio_array_t

• nr_active：所有优先级队列中的数任务数
• bitmap：位图，每个位对应一个优先级的任务队列，用于记录哪个任务队列不为空，能通过Bitmap快速找到不为空的任务队列
• queue：优先级队列数组，每个元素维护一个优先级队列，比如索引为0的元素维护着优先级为0的任务队列

对于以上的，每个优先级是一个链表，同时还维护了一个由101 bit组成的Bitmap，其中实时进程的优先级是0~00，占100bit，当某个优先级上有进程被插入链表时，响应的比特位就被置位。在进度算法中通常用sched_find_first_bit来查询该bitmap，它返回当前被置位的最高优先级的数组下表，由于使用位图，查找一个任务来执行所需的时间并不依赖于任务的个数，而是依赖于优先级的数量，所以该调度器是一个O(1)调度器

bitmap 的第2位和第6位为1（红色代表为1，白色代表为0），表示优先级为2和6的任务队列不为空，也就是说 queue 数组的第2个元素和第6个元素的队列不为空。

实时进程和普通进程

O(1)调度算法 把140个优先级的前100个（0 ~ 99）作为 实时进程优先级，而后40个（100 ~ 139）作为 普通进程优先级。实时进程被放置到实时进程优先级的队列中，而普通进程放置到普通进程优先级的队列中。

实时进程

实时进程分为FIFO(先进先出)和RR(时间片轮转)两种算法，其调度算法比较简单，如下：

• 先进先出实时进程调度：如果调度器在执行某个先进先出的实时进程，那么调度器就会一直运行这个进程，直到其主动放弃运行权(退出进程或者sleep等)
• 时间片轮转实时进程调度：如果调度器在执行某个时间片轮询的实时进程，那么调度器会判断当前进程的时间片是否用完，如果用完的话，那么重新分配时间片给它，并且重新放置会active队列中，然后调度其他同优先级或者优先级跟高的实时进程

普通进程

每个进程都有一个动态优先级和静态优先级，静态优先级不会变化，进程创建时被设置；而动态优先级会随着进程的睡眠时间而发生变化。

调度算法实现

与之前的内核一样，内核会设置一个时钟tick，在时钟tick中会进入时钟中断，最终会触发调用scheduler_tick函数

由于前面的理论知识，那么我们可以猜想在里面可能会做如下的工作

如果时间片用完，那么把进程从active队列移动到expired队列中

如果当前 runqueue 的 active 队列为空，那么把 active 队列与 expired 队列进行交换

对于实时进程和普通进程优先级的处理

重点看一下scheduler_tick的实现

重点的工作来了

该函数后面的就开始做进程切换了，不在本文的考虑范围之内，我们重点来看看O(1)的核心算法，我们可以直接看

这三行就是算法的核心，首先去从runqueue的active队列中的bitmap找到一个下标，这个下标就是对应的优先级，然后获取到对应优先级的链表，然后从中获取一个next进程。后面的操作就是执行进程切换，调度了。

当系统中无可运行进程时，也就是进程的时间片都耗光了，则需要重新给进程设置时间片，只需要切换active和expried的指针即可

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

进程的优先级分为静态优先级和动态优先级。普通优先级是进程创建时默认设置的优先级，动态优先级会在进程运行时经过动态的调整。

对于O(1)的静态优先级，其定义如下：

• 实时进程保存在进程描述符rt_priority成员中，取值范围是1(优先级最低) ~ 99(优先级最高)
• 普通进程保存在static_pro成员中，取值范围是100(优先级最高) ~ 139(优先级最低)，分别对应ncice值为-20~19

O(1)调度器中所有进程的动态优先级为p->prio

在系统运行中，会通过此函数来重新计算进程的动态优先级，实时进程值需要返回对应的p->prio。而普通进程则需要进行赏罚分明，通过进程的睡眠时间sleep_avg来计算进程是否需要赏罚。当一个进程经常睡眠，则会增加它的优先级，当一个进程常占用CPU，则需要惩罚，降低其优先级。

总结

O(1)调度器的引入主要是为了解决O(n)调度器的不足，O(1)调度器比O(n)调度器考虑的因素更多，更复杂，不像O(n)调度器那样直接考虑时间片的大小来调度，同时也有共同点，那就是爱睡眠进程增大优先级，增大时间片的机制来获取更多的运行时间。

O(1)调度器，为了减小锁的竞争，每个CPU维护一个自己的就绪队列。就绪队列由两个优先级组成，分别是active优先级数组和expired优先级数组，每个优先级数组包含140个优先级，就是每个优先级对应一个队列，其中前100个对应于实时进程，后40个对应普通进程。

但是单论效率，似乎已经没有能够超过O(1)的了，不过O(1)调度器在根据"nice"值确定时间片的算法上，存在一些瑕疵。它所使用的的规则大致是这样的："nice"为0的任务可以运行100ms，"nice"值每增加1，可运行时间将减少5ms，照此推算，"nice"为+19的任务可以运行5ms。

如果一个任务"nice"是0，另一个是1，那么可运行时间分别是100ms和95ms，差别不大，但如果一个是18，另一个是19，那么可运行时间分别是10ms和5ms，差了一倍。此外，前一种场景的任务切换每105ms发生一次，而后一种场景则是每15ms一次，调度周期的长度并不固定。内核演变就出现了完全公平的调度算法，后面继续学习中…