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 runqueue 和 expired 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))。
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调度已经足以应对了，但有一些任务的需求是必须在规定的时间内完成，这就需要更适合它们的调度策略，详情请看下文分解。
参考：
- 点滴汇聚 – 进程调度
- 郭健： Linux进程调度技术的前世今生
- http:// jake.dothome.co.kr/rt-s cheduler/
- 陈天：谈谈调度 – Linux O(1)
- http:// jake.dothome.co.kr/cfs/
- LWN – CFS group scheduling
原创文章，转载请注明出处。
About The Author
