两种驱动系统运行的方式–分时的方式_config_sched_hrtick

引子：哪些是该负责的，哪些是不该负责的

哪些是该负责的，哪些是不该负责的，这是一个问题，hrtimer就能保证所有的timer都可以不延时的被执行吗？不能，很简单，如果你排入10000个timer，每一个哪怕执行1毫秒...这个问题就是用户的使用策略问题了，不是hrtimer机制要负责的，而hrtimer要负责的是它的算法本身不能引入延迟，这也是它能保证的最后壁垒了，就好像再结实的汽车你非要开着它开下悬崖，死了之后变成鬼找到车的设计者抱怨没能保护他的安全，这合理吗？hrtimer用了红黑树数据结构，很高效的实现了timer到期后的处理，并没有引入什么延迟，仅仅就是一个线性出队的时间复杂度罢了，而传统的timer在执行的时候用了cascading算法，该算法的初衷是为了不想每次都轮询所有的timer以检测到期与否，但是该算法虽然减少了轮询的时间延迟，但是算法本身的O(n)时间复杂度也是很可观的，究其原因就在于它是基于jiffies的，而jiffies是一个基于tick的绝对单调递增的值，除此之外别无任何策略可言，因此万恶的tick机制才是罪魁祸首，htimer的回调函数采用了两种触发方式，这样就可以让用户根据需求设置更多的策略，这是一个额外的优势，于是就有了tickless。

开始：

在2.6的早期的内核以及更早的2.4内核中，时钟周期性中断是一个很重要的概念，因为它驱动了系统向前运行，一切的统计几乎都是在时钟中断中进行的，内核中有一个jiffies全局变量，很多的机制依赖这个变量，因此如果时钟的周期中断停止，那么整个系统也将停止，时钟周期中断的意义和心跳的意义类似，是一切的基础，这里面最重要的就是时钟只管周期性的中断系统而不管其余的机制如何去使用这个中断处理，模块分离的很不错。但是有个问题就是时钟中断的周期也就成了度量时间的最基本最小的单位，这个周期就是一个tick的时间，按照配置和cpu频率是不等的，这样的话不管是用户级别还是内核级别的睡眠或超时唤醒间隔就严重受制于一个tick的时间间隔，如果一个tick是10ms，那么10ms以下的睡眠就提供不了了，因为以前的timer是在时钟中断后的软中断上下文进行的，怎样样才能将定时机制和时钟周期心跳机制分离呢？首先我们看看分离的必要性，时钟周期中断是为了推动系统前进的，进程调度等重要操作都在时钟中断中被驱动，而定时机制是进程或者驱动使用的一个必不可少的机制，它们二者不是太有必要绑定在一起的，因此有必要分离，并且定时机制和时钟周期中断分离以后必须可以提供更高的精度让进程或者驱动使用而不是让它们死死依赖住那个可靠但不精确的jiffies变量，于是hrtimer呼之欲出。hrtimer的出现可以说是打开了一个缺口，在哪里打开一个缺口呢？是在驱动系统的方式上打开一个缺口，当clocksource和clock_event_device出现以后，这个缺口越来越大，最终的结果就是完全的tickless，不再需要周期的定时中断了，这种新的驱动系统的方式就是任务驱动的，每个任务绑定一个hrtimer，然后将此hrtimer入队后和所有的hrtimer比较，找出最小的，将其超时时间设置为下一次的时钟中断时间，这样时钟就不会频繁的打断正在运行的任务了，特别是在cfs调度器成为主调度器之后，这种想法更加显得合乎情理，因为cfs做到了一个调度周期内的公平调度，没有驱动任务并且没有抢占的理想情况下在一个调度周期内，tickless的系统只需要和任务数量相等数量的时钟中断就可以了，固定时间内，时钟中断的数量和任务的数量成正比，这正是符合逻辑的，如果是原来的O(1)调度器，那么时间片的分配是固定的，只要优先级确定，同一HZ值情况下分配的时间片是一定的，因此同一时间段内时钟中断的数量和任务的数量没有什么关系，即使同样都是一个进程，其优先级不同，同一时间段内发生的时钟中断也是不同的，这是不符合逻辑的，时钟中断的数量应该不能和进程优先级相关，因为进程分时调度(非抢占)是在时钟中断内发生的，因此为了公平，中断的数量只能和进程的数量相关，至于优先级的体现不能在中断的数量上而应该在中断的间隔上，因此cfs使tickless更加合理化，毕竟系统运行中进程调度是最重要的模块之一。

目前的内核对tickless的实现上还是仅在cpu进入idle的时候才tickless，而正常情况下还是按照HZ进行周期的时钟中断，其实完全可以全局禁用周期中断而全局改用tickless，但是需要做的就是将所有以来jiffies的机制全部用hrtimer实现，这可是一个不小的工程，另外周期中断的另一个作用就是进行记帐，用于统计和评估，如果完全tickless的话，像那些以前基于传统tick的timer就要同样转移到 hrtimer，理论上这也是很简单的，但是实践上可能不太适合linux的开发方式，为何说理论上简单呢？将传统的timer改变成每隔一个tick触发一次的hrtimer就可以了，tick还是根据HZ计算出来，这样我们完全可以把传统的周期中断的timer_interrupt中的各个不同的功能分离成不同的hrtimer，比如为每10ms统计记帐信息的代码提供一个hrtime，里面就做这一件事并且它每10ms触发一次然后再次加入 hrtimer对列，同样负责进程调度的代码也提供一个hrtimer，实际上内核早就这么做了，该hrtimer就是hrtick_timer，它负责进程调度，如此一来进程的运行就不必再受到无休止的时钟中断打扰了，在cfs中，一个进程可以一次性运行完承诺给它的 sched_slice(cfs_rq, se)时间，在一个进程开始运行的时候，将hrtick_timer设置为到sched_slice(cfs_rq, se)之后到期岂不妙哉！cfs的代码正是如此做的

static void hrtick_start_fair(struct rq *rq, struct task_struct *p)

{

struct sched_entity *se = &p->se;

struct cfs_rq *cfs_rq = cfs_rq_of(se);

if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {

u64 slice = sched_slice(cfs_rq, se);

u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;

s64 delta = slice - ran;

if (delta < 0) {

if (rq->curr == p)

resched_task(p);

return;

}

...//避免hrtimer频繁到期的粒度最小化限制处理

hrtick_start(rq, delta); //操作hrtick_timer，排入hrtimer对列

}

}

以上函数在pick_next_task最后调用，其实就是在一个进程刚开始运行的时候调用，代码十分容易理解。上面代码中设置的hrtick_timer到期了以后将会调用它的回调函数，即htick，后者会用queued为1进一步调用task_tick：

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)

{

update_curr(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK

if (queued) { //如果queued为1并且设置CONFIG_SCHED_HRTICK也就是是hrtimer的情况下，直接调度，因为在进程开始运行的时候就设置该hrtimer到这个时间点到期，因此无条件调度

resched_task(rq_of(cfs_rq)->curr);

return;

}

if (!sched_feat(DOUBLE_TICK) && //系统难免还保留着原来的周期中断驱动的进程调度，但是同时也设置了进程调度的hrtimer，如此一来传统的周期中断就不能打扰hrtimer的行为

hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))

return;

#endif

if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))

check_preempt_tick(cfs_rq, curr);

}

现在稍微考虑一下抢占，如果一个进程还没有运行完调度器承诺给它的时间就被抢占了，那怎么办，一切会乱掉吗？不，在cfs上丝毫不会乱掉，另外的一个原因就是每个运行队列只有一个hrtick_timer，如果当前进程被抢占了，那么可想而知它还没有运行完它的sched_slice，剩下的时间怎么办，怎么补偿给它？答案就是不再显式补偿给它，而是隐式补偿，靠的就是cfs的机制原理，被抢占的进程的vruntime不再向前推进，而cfs总是挑选 vruntime最小的进程运行，因此被抢占的进程在抢占它的进程运行完后会接着运行的几率是有的，即使不接着运行它也总是会运行，而且在被抢占的这段时间内它的vruntime没有推进，积攒的差值恰恰成了它的优势。接着说抢占，由于每个运行队列只有一个hrtick_timer，在新进程开始运行的时候会重新hrtick_start，结果就是停掉了原来的hrtick_timer，当抢占进程运行完它的sched_slice后就会发生进程调度，可以说在cfs中不需要刻意补偿被抢占的进程，所有的进程可以随意抢占，交叠抢占，嵌套抢占，cfs的原则使一切变得简单，就是挑选vruntime最小的运行。

还是管不住自己的手，写着写着就拐到cfs调度器了，本来本文是要说系统的驱动方式呢，唉！以往的时钟周期中断机制中，时钟是不了解当前系统的运行情况的，它只是傻傻的周期性中断cpu而已，内核的策略就是提供一个回调函数，该回调函数就是时钟中断处理函数，一切分离的那么清晰，设计多么好，但是它却完全不符合我们的逻辑，设计上虽然有一些的模式，比如遵循高内聚低耦合，避免双向通信等等，但是想想看我们的社会有这么和谐吗？我们不也活得很好吗？有时候好的设计不在于多么和谐，而是在于彼此之间能否相互适应，如果将内核和时钟中断规则想象成我们和社会的话，社会真的是不顾我们的需求而单独运转，而我们按社会的规则活着吗？不，绝非这样，我们和社会有一种互动，因此内核和时钟中断规则之间也需要一种互动，新时钟架构的set_next_event就提供了这么一种互动，内核可以设置下次中断的时间了，既然这样了，那么内核就要尽情地和时钟中断规则互动，于是时钟不再傻傻的按照周期中断cpu了，而是听从内核的建议，内核让它什么时候中断它就什么时候中断，这一切由clock_event_device中的set_next_event提供机制接口，而 hrtimer最为其一个策略，它们的组合就形成了一种tickless的底层。

hrtimer的红黑树实现方式的巧妙体现在hrtimer入队的时候，类似于cfs总是挑选vruntime最小的进程运行，hrtimer挑选离现在最近的设置下一个时钟中断时间点，在hrtimer运行完毕后或者新的hrtimer插入红黑树之后或者一个hrtimer从红黑树删除之后都可能引起最早hrtimer的改变，因此在上述三个地方都要权衡，用红黑树实现会非常高效。最为本文的结束，我总结一下两种分时的方式，一种就是老式系统的固定时间片分配，优先级一旦确定，其时间片就确定了，这种方式在进程比较少的时候还可以，如果随着进程的增多，进程颠簸现象就会很严重，比如一个进程即使其优先级很高，被分配的时间片很大，当它活跃了一定时间后还是要等待很久，在这很久的时间内它不再活跃，给人的感觉就是进程一会很快一会很慢，注意好的调度算法只能保证尽量的公平，但是没有办法缩短进程的不活跃时延；另外一种分时的方式就是动态时间片分配，在一个相对确定的时间段内按比例动态分配时间片，这样会让系统显得更加的公平化，进程的不活跃时延有了最坏的保证，这就是公平，而第一种分时方式仅仅比早期的批处理任务时的一个进程运行完再让另一个运行进步一点点，不再是让其一次性运行完了，而是一次运行x毫秒，这难道叫调度吗？在外部操作相同的前提下，即使是cfs，不管任何调度器，如果将一个进程的所有的运行时间都加在一起的话都是一个确定的值，是和调度器无关的，既然是为了使分时作的更好，那么要点就不是如何让一个进程怎么样高效，而是如何让所有进程公平，使得整个机器看起来更像是多台机器，这就是多道程序设计的精髓，因此最重要的不在于调度算法，而是在于时间片的分配方式。

后记：作为后记，我想谈一下cfs在设计上和hrtimer的相似点，这种相似体现在它们相对应前辈的优势上，传统的timer在cascading算法上引入了O(n)时间复杂度，而这种开销是额外的，是timer的管理开销，用户如果发现自己的timer延时了，他们不会把醉过归结到自己的timer本身，而是会说，看啊，那个该死的cascading算法浪费了那么多时间，事实上可能不是这样，然而用户不会这么想，hrtimer很自然的用到了红黑树，一切变得很平滑，没有了O(n)的开销，也就是说hrtimer的延时只是timer本身的延时而消除了机制算法本身的延时；cfs也是一样，说到调度算法，公平是个重要的指标，然后如果实现公平来的太贵的话，这种公平就是不值得的，其实任何调度算法都是为了公平，然而看看从前的O(n)调度器，为了优先级调度，仅在pick-next算法上就引入了O(n)的开销，后来的O(1)算法虽然消除了pick-next的开销，但它的意义仅在多处理器调度上，饥饿判断，交互判断，优先级调整等等还是带来了很多额外的算法开销，cfs自然地选则了红黑树，消除了机制算法的开销，而hrtimer有着异曲同工之妙，这里的要点就是，不要在机制上浪费太多，机制应该做到简单高效，做到如果有延时，那么99%的问题是策略问题，这才是成功的设计。机制上的开销是额外的开销，不应该让用户为之买单，机制很大意义上是带有公益性质的，而不是收费的，想必大家都希望国家有好的福利保障体系和完善的纯公益性质的机构吧，教育和医疗等机构收费太高是谁都不希望的。