linux 内核调度之定时机制

你知道吗，usleep(0)会将进程挂起吗，会挂起多久呢？usleep(1)呢？在2.4内核和2.6内核环境下是一样的吗？
我们先来看一看strace的结果：
2.4内核
//代码
while(1) {
       usleep(0);
}
//strace结果
nanosleep({0, 0}, NULL)                 = 0 <0.002461>
nanosleep({0, 0}, NULL)                 = 0 <0.009985>
nanosleep({0, 0}, NULL)                 = 0 <0.009981>
nanosleep({0, 0}, NULL)                 = 0 <0.009991>
nanosleep({0, 0}, NULL)                 = 0 <0.009978>
…
 
//代码
while(1) {
       usleep(1);
}
//strace结果
nanosleep({0, 1000}, NULL)              = 0 <0.015141>
nanosleep({0, 1000}, NULL)              = 0 <0.019990>
nanosleep({0, 1000}, NULL)              = 0 <0.019981>
nanosleep({0, 1000}, NULL)              = 0 <0.019983>
nanosleep({0, 1000}, NULL)              = 0 <0.019985>
…
 
2.6内核
//代码
while(1) {
       usleep(0);
}
//strace结果
nanosleep({0, 0}, NULL)                 = 0 <0.002598>
nanosleep({0, 0}, NULL)                 = 0 <0.003974>
nanosleep({0, 0}, NULL)                 = 0 <0.003975>
nanosleep({0, 0}, NULL)                 = 0 <0.003979>
nanosleep({0, 0}, NULL)                 = 0 <0.003976>
…
 
//代码
while(1) {
       usleep(1);
}
//strace结果
nanosleep({0, 1000}, NULL)              = 0 <0.002542>
nanosleep({0, 1000}, NULL)              = 0 <0.003975>
nanosleep({0, 1000}, NULL)              = 0 <0.003974>
nanosleep({0, 1000}, NULL)              = 0 <0.003976>
nanosleep({0, 1000}, NULL)              = 0 <0.003978>
…
 
     从strace结果来看，usleep(0)和usleep(1)都会将进程挂起。2.4内核下usleep(0)会将进程挂起不到但又接近10ms；usleep(1) 会将进程挂起不到但又接近20ms。2.6内核下usleep(0)和usleep(1)都会将进程挂起不到但又接近4ms。
 
    对结果觉得不可思议吗？不急，我们先来看看2.4内核和2.6内核的定时机制，了解其实现之后，再来理解这个“怪现象”。
 
2.4内核定时机制的实现
    先来看一个例子
    假设时间最小粒度是精确到天，今天是3月10日。我们可以将接下来需要处理的工作划分到具体的某一天，因此每一天都有一个需要处理的工作队列。到了具体的那一天，依次从工作队列中取出每项工作进行处理即可。
    这个对于最近一段时间需要处理的工作管理是很有效的；但对于距离时间比较远的工作，我们也不怎么关注。例如，3月份的工作，我们会安排到具体的某一天。但4月5月到12月，以及明年后年，甚至是下一两个世纪的事情（如果我们能活那么久的话：），就不怎么关注。这时只需要放到每个月、每年、每个世纪的列表中即可。等到4月1日的时候，可以将整个4月份的一个工作列表再来进行一次安排：将这些事情分发到具体每一天的队列中去。相应的，到了下一年的1月1日，将整年的一个工作列表再来进行一次安排：将这些事情分发到具体每个月的队列，其中1月份的还需要分发到每一天的队列。等等，以此类推。
 
    具体到2.4内核，是按照时钟中断粒度建一个数组，数组的元素就是一个队列头，每个队列中的节点就是该次中断到期需要触发的事件
    假设时钟中断是1s一次（频率为1）；极端情况下，开一个大小为2^32的数组，从系统开机启动后经过的多少s，作为数组下标，就能得到在这一s到期需要触发的事件队列。
    实际上，2.4内核中一般将频率HZ定义为100，即时钟中断间隔为10ms，每10ms时钟芯片产生一次时钟中断；因此，数组粒度就是10ms一个元素。另外，考虑到空间因素，不可能开2^32个元素的数组，内核采用的方法是分级的方式：最近256（2^8）个粒度为10ms的定期事件队列放到最低一级的数组中；接下来64（2^6）个粒度为10ms*256的定期事件则放到第二级的数组中；依此类推，接下来64（2^6）个粒度为10ms*256*64的定期事件则放到第三级的数组中；接下来64（2^6）个粒度为10ms*256*64*64的定期事件则放到第四级的数组中；接下来64（2^6）个粒度为10ms*256*64*64*64的定期事件（其中包括时间接近无限长的事件）则放到第五级（最后一级）的数组中。
    添加定时事件的时候，将事件加入到该事件到期时，时钟中断对应的事件队列中即可，时间复杂度是O（1）的；而判断到期，只需要在每次时钟中断的处理中，将该时钟中断对应的事件队列中的事件都触发超时即可；当然，由于有分级，检查过程中可能涉及到降级的过程，但总体时间复杂度也还是O（1）的。降级的原因：对于第二级数组中队列里的事件来说，当时不是最近256个粒度为10ms的定期事件，但随着时间的推移消逝，其中最近的粒度为10ms*256的一个定期事件，就成了最近256个粒度为10ms的定期事件了。
 
2.6内核定时机制的实现
    2.6内核在定时机制方面，做了较大的调整。2.6内核将所有定时事件排成一个队列，由红黑树来组织的，其插入删除的复杂度为O（logN）。超时判断时，只需要从队列头依次判断时间，如果到期了则触发。这里的时间单位是ns，即10^-9s。设置这个单位的目的是需要实现一个高精度的定时器。当然，实际的精度，还受时钟中断芯片的影响。对实时性要求高的系统，其时钟中断芯片的时间粒度可以做到非常精确。另外，一般情况下，时钟中断芯片，还是定期发出时钟中断信号的，一般是设置为4ms，即将频率HZ定义为250。 但当精确度要求很高时，时钟中断频率非常高，对中断的处理会严重影响系统性能。为了应对这个问题，内核对时钟中断芯片进行动态设置，在本次中断处理例程完 成时，将下一个定时事件的时间点设置为时钟中断芯片下次发出时钟中断的时间点。这样，当定时事件很少时，时钟中断的次数就很少。这种机制带来的另外一个好 处就是，时钟中断次数少，能够降低对电能的消耗，针对当前移动设备流行趋势情况，也是非常有用武之地的。
 
 
现象分析
    了解了定时机制之后，我们就容易解释文章开头处提到的“怪现象”了。
    2.4内核下，usleep(0)和usleep(1)，进程分别挂起了接近10ms和接近20ms。这是由于usleep(0)，内核将唤醒的定时事件挂在了1个时钟中断之后（即下个时钟中断）的队列中；而usleep(1)则是将唤醒的定时事件挂在了2个时钟中断之后的队列中。因此它们分别是在下个时钟中断和第2个时钟中断处理例程中唤醒恢复的。而下个时钟中断距现在是不足一个时钟中断周期的，特别的是，如果循环中仅调用usleep(0)的话，上一个usleep在对应的时钟中断处理例程恢复时立刻调用usleep，则下个时钟中断周期距这个usleep调用的时间肯定是不到但又非常接近一个时钟周期，也就是挂起接近10ms；同理，如果循环中仅调用usleep(1)的话，挂起不到但又接近20ms。
    而2.6内核下，usleep(0)和usleep(1)，肯定是插入到定期事件不是前一就是前二；然后普通系统还是使用的固定4ms一个时钟中断情况下，它们都是在下个时钟中断的处理例程中恢复的（时间检查时，肯定发现都到期了）。如果循环中仅调用usleep(0)或usleep(1)的话，都是挂起不到但又接近4ms。