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

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

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

O(1)调度算法介绍

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

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

linux定时调度耗资源吗(O1调度器)(1)

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

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

linux定时调度耗资源吗(O1调度器)(2)

  1. 当 active 中的任务时间片用完,那么就会被移动到 expired 中。
  2. 当 active 中已经没有任务可以运行,就把 expired 与 active 交换,从而 expired 中的任务可以重新被调度。
O(1)调度算法数据结构

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

linux定时调度耗资源吗(O1调度器)(3)

接下来,我们看看prio_array_t

linux定时调度耗资源吗(O1调度器)(4)

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

linux定时调度耗资源吗(O1调度器)(5)

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

实时进程和普通进程

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

实时进程

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

普通进程

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

调度算法实现

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

linux定时调度耗资源吗(O1调度器)(6)

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

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

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

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

重点看一下scheduler_tick的实现

linux定时调度耗资源吗(O1调度器)(7)

linux定时调度耗资源吗(O1调度器)(8)

linux定时调度耗资源吗(O1调度器)(9)

重点的工作来了

linux定时调度耗资源吗(O1调度器)(10)

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

linux定时调度耗资源吗(O1调度器)(11)

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

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

linux定时调度耗资源吗(O1调度器)(12)

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

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

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

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

linux定时调度耗资源吗(O1调度器)(13)

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

总结

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

linux定时调度耗资源吗(O1调度器)(14)

linux定时调度耗资源吗(O1调度器)(15)

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一次,调度周期的长度并不固定。内核演变就出现了完全公平的调度算法,后面继续学习中…

,