O(1) Scheduler Notes

23 Sep 2012 by fleuria

上周发觉看文件系统到了一个小瓶颈,不如转移下注意力,先看下内核的调度算法好了。而且手头正好有Robert Love的书,zet君每提到这本书都对它的调度算法部分赞不绝口,值得仔细看看。

但是一下子又没看懂 :(

不如回头从O(1) Scheduler开看好了,记一点笔记在这里。

需要注意的是,O(1) Scheduler是在2.5中引入,距今已十年多了。


调度的不同情景

操作系统提供的多任务支持,很大程度上就是调度算法本身了。然而多个任务并非生而平等:有的任务希望响应时间尽可能短,有的任务希望整体性能尽可能高。有的任务对IO密集(IO bound),有的任务对计算密集(CPU bound),也有的任务对实时有所要求。

对调度算法而言,如何才能做到公正,其实是个两难的问题:

  • 如果追求第一时间的响应速度,那么进程切换的开销将降低任务的整体性能。
  • 如果追求任务的整体性能,那么用户可能需要等待很久才能看到任务的结果。

就实际场景而言:

  • 应用程序会更想得到响应速度:用户点击了按钮,应该尽可能地给个反馈,不然用户会觉得”死机”了1。至于运算的性能则通常不是大问题,时间长一点没关系,给用户看一个进度条就行了。
  • 超级计算机会想要得到更高的整体性能:尽快的算出来结果就好,几乎没有用户交互。
  • Web Server的期望则介于两者之间:必须重视整体性能,不然会被高负载压垮;用户不会频繁地交互,但是用户依然希望及时得到响应:假如100个用户同时想下载文件,正确的做法该是同时响应这些用户的下载请求,而非为了整体性能而传完一个传下一个2
  • 此外,实时应用比如音乐播放器,则希望定时往声卡的buffer中填上后几秒的音频数据,哪怕系统再忙,音乐被打断终究是不好的。

此外,SMP与NUMA的存在又让问题更加复杂了一分。

在这个时代,Linux已无法打出Keep It Simple的旗号去躲避问题——它必须面对所有的问题:低端Android手机也需要跑计算密集的垃圾收集;超级计算机也需要有一个终端来交互。

哪怕问题之间有矛盾,哪怕舍此不能及彼,Linux也需要有一个四海皆通的方案,给上述的所有情景提供一个较好的支持,允执厥中。Linux不是一个Do one thing and do it well的内核,这点很重要。

数据结构

O(1) Scheduler中核心的数据结构只有两个,runqueue与优先级数组(priority array)。

每个CPU对应一个runqueue,每个runqueue包含两个优先级数组,一个是active priority array,装有还没跑完时间片的活跃任务;另一个是expired priority array,装有跑完时间片的任务。当active priority array中的任务跑光了时间片,就把它移动到expired priority,同时重新计算时间片。当active priority array中没有任务了,就简单地将active priority array与expired priority array的指针交换过来。

优先级数组是一组链表的数组,长度为140,每个优先级对应一条链表,也就是最多可以有140条链表了。相同优先级的任务链在同一条链表中,按照Round Robin调度。此外,优先级数组维护着一个bitmap,用以表示某一优先级对应的链表是否为空。这一来查找当前最高优先级的任务时,只需遍历固定大小的bitmap即可,最坏为常数时间。

由此可见,O(1) Scheduler设定了140个优先级。其中的前100个优先级皆为实时任务保留,后40个优先级供一般任务使用,保证实时任务的优先级永远比一般任务更高。

优先级

O(1) Scheduler将优先级分为静态优先级(static priority)与动态优先级(或者_有效优先级_,effective priority),使得时间片的计算与静态优先级相关,而进程的抢占与动态优先级相关。

静态优先级就是平时的nice值了,默认为0,用户可以设置为-20到19之间。保存于t->static_prio

动态优先级则根据nice值以及一些统计信息计算而来,目标是奖励IO密集型任务,而惩罚CPU密集型任务。保存于t->prio

动态优先级的计算:启发式方法3

O(1) Scheduler会将一个任务平时的睡眠时间与执行时间统计在sleep_avg中:

  • 当任务唤醒时,将它刚刚的睡眠时间(纳秒)加在sleep_avg中;
  • 当任务放弃CPU控制权时,使sleep_avg减去任务刚刚的执行时间;

这一来,理论上任务的sleep_avg越高越IO密集,由此即可作为奖励还是惩罚的一个参照。

动态优先级由effective_prio()函数计算得出,它会首先判断任务的类型,若为实时任务,则直接返回任务的静态优先级不做处理;否则,依据sleep_avg计算bonus值(-5~5),进而与静态优先级相加得出动态优先级,最后保证动态优先级在-19~20之间,公式如下:

bonus = CURRENT_BONUS(p) - MAX_BONUS / 2
prio = p->static_prio - bonus
prio = max(min(prio, 20), -19)

其中:

MAX_BONUS = 10 
MAX_SLEEP_AVG = 1000
CURRENT_BONUS(p) = NS_TO_JIFFIES(p->sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG

反馈:Interactivity Credit

CPU密集的任务偶尔也会产生大量IO,但是据这一段时间的IO就将它当作IO密集型任务就上当了。对此,O(1) Scheduler额外统计了一个interactive_credit,作为避免这种误判的一个参照。

平时任务若睡眠了较长时间,则interactive_credit加14;任务若执行了较长时间,则使interactive_credit减15

interactive_credit的值仅当大于100或者小于-100时才会发挥作用。若大于100,则认为是高Credit,进而被认为是IO密集而获得奖励;若小于-100,则认为是低Credit,进而被认为是CPU密集而得到惩罚。而奖励与惩罚的手段,就是在计算sleep_avg时,影响运行时间与睡眠时间的统计:

  • 若为高Credit,将任务的执行时间减少6
  • 若为低Credit,则:

    • 在进程从较长时间的不可中断睡眠中唤醒时,忽略这段睡眠时间;
    • 睡眠时间最多只能计入一个时间片的时间。

时间片的计算

时间片的计算只与静态优先级相关:静态优先级越高,时间片越长。

时间片由time_slice()函数计算而来,公式大致如下:

MIN_TIMESLICE = 10ms
MAX_TIMESLICE = 200ms
time_slice(p) = (MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO - 1 - p->static_prio) / (MAX_USER_PRIO - 1) + MIN_TIMESLICE

p->static_prio为0,计算可得时间片的默认长度为100ms。

跑完时间片的任务会被移入expired priority array等待下一次调度。

不过,100ms已经是相当长的一段时间了,对于同一优先级中交互频繁7的任务,无端等待100ms是不可接受的。对此,策略是约定任务跑完TIMESLICE_GRANULARITY(默认50ms)时进行一次Round Robin8,将当前任务移动到队列的尾部。从某种意义上讲,时间片并非O(1) Scheduler中最小的时间单位。

scheduler_tick()

scheduler_tick()函数是O(1) Scheduler的心跳,由do_timer()触发,每1ms执行一次。它会将当前进程的time_slice值减一,并在必要时将进程放入expired priority array或者Round Robin,并设置TIF_NEED_RESCHED

这里有个例外情况,对于交互频繁的任务,跑完时间片就将它放进expired priority array等待猴年马月的再次活跃将是不可接受的。跑完时间片并非意味着它不再活跃、不再关心交互的响应。

这里的Workaround是,如果是交互频繁7的任务跑完时间片,则尽可量将它重新插回active priority array。代价是有可能会饿到expired priority array中的任务,对此引入了一个宏EXPIRED_STARVING(rq)来判断expired priority array是否感到饥饿,如果已经饿了,再将跑完时间片的任务插入expired priority array。

需要留意的是,scheduler_tick()并不会直接调用schedule()进行任务切换,schedule()将在返回用户态时被调用9

schedule()

schedule()才是O(1) Scheduler中最主要的函数,这里放到最后,但不打算记太多关于它本身行为的内容了。而它所做的也十分简单:选出下一个任务,并切换。

相比之下,它被调用的情景则更值得记一下:

  1. 主动放弃控制权,如mutex, semaphore, waitqueue等;
  2. 若设置TIF_NEED_RESCHED并开启抢占,则在返回用户态时调用schedule()发生抢占;

Footnotes

  1. 事实上,我们常说的’死机’正是调度算法失败的场景。
  2. 就像12306那个排队一样。
  3. 启发式方法,即依照过往的统计数据作为经验,在下次求解中推测出一个较好的结果。
  4. recalc_task_prio(),”较长时间”通过一个宏INTERACTIVE_SLEEP(p)来比较
  5. schedule()
  6. schedule() [ref]
  7. “交互是否频繁”通过一个宏TASK_INTERACTIVE(p)来判断
  8. LWN: sched-2.5.66-A2, scheduler enhancements
  9. scheduler_tick()正位于中断上下文,如果发现有更高优先级的进程,一般都会立即执行schedule(),除非内核关闭了抢占

References

  • Understanding the Linux 2.6.8.1 CPU Scheduler
  • Understanding Linux Kernel
  • Linux Kernel Development
  • LWN
  • http://permalink.gmane.org/gmane.linux.kernel/1337629 (or http://wangcong.org/blog/archives/2076)