可配置型调度器的需求为了避免小手段,那就要彻底抛弃“鱼与熊掌可兼得”的思想,采用“一种调度器只适用于一种场景”的新思路。如此我们可以设计多种调度器,在安装操作系统的时候可以由管理员进行配置,比如我们将其用于桌面,那么就使用“交互调度器”,如果用于路由器,那就使用“大吞吐调度器”...消除了兼顾的要求,调度器设计起来就更佳简单和纯粹了。
面对需要大吞吐量的网络操作系统,我们有传统的UNIX调度器,然而面对日益桌面化的操作系统比如Android手机,我们是否能摒弃那种大而全的调度策略呢?Con Kolivas老大设计出的BFS调度器就是为桌面交互式应用量身打造的。
问题在哪?Linux 2.6内核实现了那么多的调度器,然而其效果总是有美中不足的地方,到底问题出在哪里?事实上,Linux 2.6的各种调度器的实现都不是完全按照理论完成的,其中都添加了一些小手段。比如虽然CFS号称支持大于2048的CPU个数,然而实际应用中,效果未必好,因为CFS调度器继承了O(1)调度器的load_balance特性,因此在那么多处理器之间进行基于调度域的load_balance,锁定以及独占的代价将会十分大,从而抵消了每CPU队列带来的消除锁定的优势。
总之,这些调度器太复杂了,而且越来越复杂,将80%的精力消耗在了20%的场景中。实际上,做设计不要联想,完全依照我们目前所知道的和所遇到的来,在可用性和效率上被证明是明智的,当然不考虑太多的可扩展性。
回到O(n)调度器BFS调度器用一句话来总结就是“回到了O(n)调度器”,它在O(n)调度器的基础上进行了优化,而没有引入看起来很好的O(1)调度器,这就是其实质。O(n)调度器有什么不好么?有的。大不了就是遍历的时间太长,BFS根据实际的测试数据忽略之;每个处理器都要锁定整个队列,BFS改之,做到这些既可,这才叫基于O(n)调度器的优化而不是彻底颠覆O(n)调度器而引入O(1)调度器-当然前提是桌面环境。如果说能回到原始的O(n)调度器进行修改使之重新发挥其作用而不是彻底抛弃它,这才是最佳的做法,反之,如果我们把问题的解决方案搞的越来越复杂,最终就是陷入一个泥潭而不可自拔。要知道方案复杂性的积累是一个笛卡儿积式的积累,你必须考虑到每一种排列组合才能,当你做不到这一点的时候,你就需要返璞归真。
BFS调度器的原理BFS的原理十分简单,其实质正是使用了O(1)调度器中的位图的概念,所有进程被安排到103个queue中,各个进程不是按照优先级而是按照优先级区间被排列到各自所在的区间,每一个区间拥有一个queue,如下图所示:
内核在pick-next的时候,按照O(1)调度器的方式首先查找位图中不为0的那个queue,然后在该queue中执行O(n)查找,查找到virtual deadline(如下所述)最小的那个进程投入执行。过程很简单,就像流水一样。之所以规划103个队列而不是一个完全是为了进程按照其性质而分类,这个和每CPU没有任何关系,将进程按照其性质(RT?优先级?)分类而不是按照CPU分类是明智之举。内核中只有一个“103队列”,m个CPU和“103队列”完全是一个“消费者-生产者”的关系。O(1)调度器,内核中拥有m(CPU个数)个“消费者-生产者”的关系,每一个CPU附带一个“生产者(140队列组)”。
只有统一的,单一的“消费者-生产者”的关系才能做到调度的公平,避免了多个关系之间踢皮球现象,这是事实。在结构单一,功能确定且硬件简单的系统中,正确的调度器架构如下图所示:
在结构单一,功能确定且硬件简单的系统中,不正确的调度器架构如下图所示: