brose:Linux中定时器的实现算法

来源:百度文库 编辑:偶看新闻 时间:2024/03/28 20:02:12

定时器的作用

       定时器在操作系统中起到了举足轻重的作用。在做IO操作时,需要超时机制保证任务不处于无休止的等待状态;在延时处理时,可以通过“闹表”进行相对准点的唤醒操作。在多任务操作系统中,定时器是一种非常常用的资源。

对于熟悉硬件的工程师,定时器一般是芯片中的硬件定时器资源,实际上在操作系统中指的定时器资源并非局限于硬件资源,更重要的是软件定时器资源。硬件定时器资源通常实现操作系统的心跳,在uc/os中心跳频率默认值为200Hz,也就是5ms产生一次操作系统心跳。软件定时器是在操作系统心跳的基础上实现的。

       下面对Linux中的定时器实现算法作详细分析。

 

Linux中定时器的实现

       Linux中的定时器实现有点意思,在定时器较多的情况下实现效率较高,并且该算法思想可以在其它嵌入式系统中得以应用。

       定时器实现的核心思想是采用了多级hash链表,并且每级hash的长度都不一样,多级hash链表可以类比为秒、分、时、天、月,每级的时间跨度都不一样。Linux中实现的五级hash链表关系如下图所示:

  如上图所示为5hash链表,V1为最低层的hash链表,V5为最顶层的hash链表。V1~V5 hash table的每一项为一条定时器链表,新添加的定时器会通过expire(定时时间值)和base->timer_jiffies(当前定时值)的差值expire_time来索引应该挂接到哪一层hash table中,并且索引到hash table中的具体项,然后将新增加的定时器加入到该项的timer list中。hash长度从V1V5变得越来越大。V1hash长度为1jiffies,也就是说V1hash table每一项为同一jiffies的定时器链表;V5hash长度为64M jiffies,也就是hash table的每一项会链接连续64M jiffies定时长度的timer。不同层次的hash table具有不同的hash长度,离当前时间点越远的timer位于hash长度越长的table中,因为这些定时器还需要等待较长时间才能得以处理,所以可以采用大块分类的方法,离当前时间点越近的timer需要细粒度的切分,因为jiffies每变化一次都需要处理timer,所以最低层的table按一个jiffies进行切分。随着时间点的后移,不断的对最底层的hash table进行处理,并且通过当前时间点索引上层hash table,将定时器分配到下几级的hash table中。每个hash table与定时器之间的关系如下图所示。