注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

祝灾区人民早日度过难关

努力工作

 
 
 

日志

 
 

[yc]读核感悟-定时器-巧妙的定时器算法  

2008-04-15 14:22:20|  分类: IT传奇 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    内核中经常要用到各种定时器。比如nanosleep()系统调用,让当前进程睡眠一段时间,再把它唤醒。即在expires时刻(以时钟滴答为单位),自动调用wake_up_process。
    最直接的思路是定义一个定时器,里面有function(函数指针),data(函数参数),expires(调用时刻)。然后排成一个链表。每次时钟中断发生时,扫描整个链表,发现有触发的定时器,就调用function(data)。寻找触发的定时器的时间复杂度O(N)。N是定时器数量。明显,这个算法效率太低。
    改进:事实上我们只对最快触发的定时器感兴趣,所以在插入元素时就对元素进行排序。这样,每次时钟中断,只要检查链表中第一个定时器就行。寻找触发的定时器的时间复杂度O(1)。但是每次插入和删除操作的时间复杂度又变成O(N)了。这个算法还是不好。
    继续改进:把数据结构改成优先队列(最小堆),这样插入删除操作的时间复杂度为O(logN)。寻找触发的定时器的时间复杂度O(1)。
    有没有可能继续改进呢?墙上的挂钟给人以灵感。当秒针飞快走动时,分针走的很慢,而时针几乎不动。这提醒我们要区别对待定时器。要把定时器划分成不同区间。对最早可能触发的定时器频繁扫描(就像秒针),而对很晚才触发的定时器隔一段时间再扫描(就像分针)。
    基本思路:2^8-1个时钟滴答内触发的定时器放到第一组,2^8~2^14-1个时钟滴答内触发的定时器放到第二组,依次类推,最后分成五组。第一组每个时钟中断都要检查,第二组则每2^8=256个时钟中断检查一次,依次类推。每组中有256个队列。那么检查每一组是否意味着检查这256个队列?不是的。事实上,根据触发时间,我们可以把定时器放到对应的队列中(如在第一组中,把触发时间为expires的定时器放到第expires%256个队列中)。那么我们在检查每一组时,只要扫描其中一个队列就可以了。对于第一组,被检查到的定时器需要执行定时器函数。对于其它组,则意味着“升级”(跳到前一组,由于临近触发而受到更频繁的检查)。
    可以看出,这个算法中,寻找触发的定时器的时间复杂度接近O(m)(m是第一组每个队列中定时器的个数,其它组的操作几乎可以忽略)。而这个m在绝大部分情况下接近1。插入和删除操作的时间复杂度也为O(1)。这是迄今为止最好的算法。
    更详细的算法解释见ULK第六章timing mesuring。
    从中也可以看出,把一个大队列分割成几个小队列,可以极大的降低算法的时间复杂度,提高效率。2.6内核中,调度算法也采用了类似的思想。
  评论这张
 
阅读(617)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018