Linux中的任务和调度 [二]

Linux中的任务和调度 [一]

任务切换

在上文所述的多线程模型中,可以认为进程是资源管理的单位,而线程是CPU调度的基本单位。如果在同一进程的不同 线程之间切换 ,那么同前面文章介绍的RTOS基本相同,包括寄存器的保存和恢复等,开销相对较小。但如果在不同的 进程之间切换 ,那么就需要进行address space和page table的切换,可能造成TLB flush,开销较大。

因为调度是由内核统一负责的,如果是在user space的process之间发生的切换,那么在此过程中,还会涉及到进入以及退出kernel space的开销。

任务调度

任务的切换由 调度 触发,合理的调度对一个系统的高效运行是至关重要的,同时Linux的应用领域又非常广泛,服务器、桌面和嵌入式通吃,这使得Linux的调度器面临着很大的考验。因此,调度的问题在Linux的社区中也非常活跃,据统计,仅2010年,就有323个针对scheduler的patches,平均每27小时一个,足可见大家对改善Linux调度的热情。

即便如此,也没有一种单一的调度策略能够满足Linux所面向的所有场景的需要,因此Linux实际上是同时支持多种不同的调度策略。先来看下原理相对比较简单,和RTOS中普遍采用的策略类似的Real-Time调度。

【实时调度策略】

Real-Time调度分为”SCHED_FIFO” 和 “SCHED_RR”两种,前者同基于FCFS的uC/OS-II的调度策略类似,区别是Linux中的” SCHED_FIFO “支持多个任务具有相同的优先级,同一优先级中“先来”的任务运行完毕后,“后来”的任务才能运行。而” SCHED_RR “则同基于Round-Robin的uC/OS-III和RT-Thread采用的调度策略基本一样。

之所以叫”Real-Time”,是因为在这种调度策略中,使用的是静态/固定优先级,高优先级的任务具有对CPU绝对的优先使用权,适用于要求响应延迟尽可能短的任务。

优先级 的范围从0到99(”MAX_RT_PRIO”的值减1),数值越大,代表优先级越低。在”top”命令的输出中,采用Real-Time调度的任务以”rt”标识。不管优先级如何(公侯伯子男),只要是实时任务(贵族),其优先级总是高于普通任务(庶民)。

实时调度具体的代码实现位于”/kernel/sched/rt.c”,由于其使用的数据结构和普通任务存在很大的关联,因此将放在下一节介绍普通任务的调度时一起讨论。

默认调度策略

普通任务使用的是更体现“公平”原则的” SCHED_NORMAL “策略(在POSIX标准中被叫做”SCHED_OTHER”,意思是除开几种特殊的调度策略,默认就是它)。其原理类似于Proportional Share,即不管优先级如何,总能得到执行的机会,只是优先级低的任务所能获得的CPU时间片(timeslice)相对更少。

在”SCHED_NORMAL”中,任务所能获得的时间片的比例用” nice “表示(源自Unix系统),”nice”的取值范围从-20到19,默认为0。这个值越大,表示越“谦让”,因而优先级越低,-20就是最“自私”的,期待第一个执行,而+19最“大度”的,愿意最后一个执行(逆向权重)。

因为实时任务的优先级总是高于普通任务,所以在内核的实现中,”SCHED_OTHER”中的”nice”值需要加上120,即从100到139。

O(n)调度器

把所有处于就绪态的任务(不管是实时任务还是普通任务),统一放在一个队列里(称为” runqueue “),每次调度时,遍历该队列,根据优先级/nice值和已用时间片,寻找最为合适的任务来执行,这种调度算法因其遍历的 时间复杂度 为O(n),被称为O(n)调度器。

当runqueue中任务的时间片全部用完后,一个调度周期结束,此时需要为runqueue中的任务重新设定时间片,然后一个新的调度周期开始。

O(1)调度器

当runqueue较长时,O(n)调度器的查找将颇为耗时,而且实时任务和普通任务放在同一队列,实时性难以得到真正的保障。一个改进的做法是为每个优先级提供一组 avtive runqueueexpired runqueue ,具有相同优先级的process挂在同一队列上。

每个优先级用1个bit表示,形成一个 bitmap 。如果某个优先级的active runqueue不为空,那么该优先级对应的bit就不为0,这样在挑选任务执行的时候,就能以O(1)的时间复杂度找到bit不为0的最高优先级队列,然后选取该队列的第一个任务。

这就是O(1)调度算法,同样根据其查找的效率而命名。Real-Time任务也适用于这样的算法(由 “rt_rq” 结构体描述),因此整个bitmap一共有140个bits,其中100个bits对应Real-Time任务,另外40个bits对应普通任务。

对于一个普通任务,当它的时间片用完后,就会从所在的active runqueue转移到对应优先级的expired runqueue上。

当active runqueues全部为空后,expired runqueues和active runqueues将发生角色互换( array switch ),周而复始……

此外,在O(n)调度器出现的时候,SMP系统还没有开始盛行,因此如果多核共用一个队列,将会造成严重的竞争,所以为了增加可扩展性,O(1)调度器为每个CPU都提供了一套这样的bitmap和队列机制。

  • 存在的问题

单论效率,似乎已经没有能够超过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一次,调度周期的长度并不固定。

CFS调度器

在2.6.23版本中,O(1)调度器被综合表现更好的CFS所取代(相关的代码实现位于”/kernel/sched/fair.c”),不过这算不上什么改朝换代的颠覆,因为作者都是同一个人,即Ingo Molnár。

Linux中CFS的设计原则是:”nice”值每增加1, weight 增加10%,减1则减少 10% 。基准的nice值为0,对应的weight值是1024(由”NICE_0_LOAD”表示),据此可计算出,nice的值为-1和1时,对应的weight值分别是1277和820,为-20和19时,对应的weight值则分别是87761和15。两者的换算关系近似为:

可见,weight值随nice值的变化是指数级的。不过每次都直接这样计算实在耗时,而且满打满算就40种对应关系,所以选择记录在名为”sched_prio_to_weight”的数组里,以查表的形式获取。

一个任务的CPU占比,由其weight值除以runqueue中所有任务weight值的总和(称为”load”)得到。假设只有2个进程A和B,它们的nice值分别是1和0,那么进程A可获得的CPU份额占45%(820/1844),进程B占55%(1024/1844)。

但份额要换算到时间片上才有实际的意义,这倒不难,将占比乘以调度周期即可:

难的是 如何确定多长时间为一个调度周期。周期太短,会形成频繁切换的开销,太长又可能造成任务的响应不及时。

有两个重要的参数与此相关,一个是 “sched_nr_latency” (默认为18ms),在这个参数定义的调度周期内,每个任务至少可以运行一次,还有一个是 “sysctl_sched_min_granularity” ,它限定了在一个调度周期内,每个任务至少要运行多长时间(低了就划不来)。

假设 “sched_nr_latency” 是8ms,如果runqueue上有2个”nice”值相同的任务,那么每个任务可以运行4ms,4个任务的话则每个任务可以运行2ms。如果是8个任务,那每个任务可运行的时间就只有1ms,假定 “sysctl_sched_min_granularity” 是2ms,那对不起,要保证最小粒度,只能把一个调度周期线性扩增到2*8=16ms。

之前的文章已经介绍过,CFS总是选择vruntime最小的任务执行,这里将以Linux为例,讲解其具体的应用方式。

在Linux的CFS实现中,runnable的任务以” sched_entity “作为节点(暂时不考虑task group的情况),通过 red-black tree 的形式被管理。每个CPU对应一个rbtree(由 “cfs_rq” 结构体描述),其中每个任务的vrumtime(精度为ns)就作为这个rbtree中的key,因此查找的时间复杂度为O(log(n))。

图片来源于http://jake.dothome.co.kr/wp-content/uploads/2017/05/enqueue_entity-1a.png

nice值为0的任务,vruntime等于实际物理时间,其他nice值的任务的vruntime,由实际时间乘以weight的比值得到(对应函数实现为”calc_delta_fair”),nice小于0的时间膨胀(vruntime的值大于物理时间),大于0的时间收缩:

tick发生时,任务的vruntime值被更新,而vruntime值更小的任务,在rbtree中总是被置于vruntime值更大的任务的左侧。任务运行时,其vruntime稳定地增加,它在rbtree中总是向右移动的,weight值越大的任务vruntime增加越慢,其向右移动的速度也越慢。

每当调度发生时,rbtree中最左边节点对应的任务,就被选为下一个要执行的程序体。虽然是time-ordered的树形结构,但换一个角度看,它其实也可以延展为以时间线为依据的数组,里面依次排列了将来要执行的任务,但并没有O(1)调度算法中”array switch”的开销。

对于大多数任务,Real-Time调度加上CFS调度已经足以应对了,但有一些任务的需求是必须在规定的时间内完成,这就需要更适合它们的调度策略,详情请看下文分解。

参考:

原创文章,转载请注明出处。

术道经纬
我还没有学会写个人说明!
上一篇

如何搭建一个内部组件共享平台

下一篇

翻译:《实用的Python编程》01_07_Functions

你也可能喜欢

评论已经被关闭。

插入图片