Linux2.26动态定时器的设计

上两篇文章介绍了Linux2.26中的计时架构,包括底层硬件和软件的基本模块。 这一篇文章要说的是动态定时器。 为什么说是动态呢? 首先,需要区别与前两篇文章介绍的硬件定时器;其次,这类定时器可以动态的创建和销毁。 我们知道硬件定时器发起定时中断,调用timer_interrupt()函数,更新jiffies,上墙时间,CPU资源等。 动态定时器通过软件程序实现,允许函数在未来的某个时刻调用。 所以动态定时器的基本原理相当简单。 动态定时器有一个expire字段,值为当前jiffies加上一定数额的ticks。 之后,每次检查动态定时器,用当前jiffies与这个字段的值对比。 如果当前jiffies大于或者等于expire,则这个定时器到期,调用相关回调函数。

即动态定时器的数据结构:

struct timer_list {
    struct list_head entry;
    unsigned long expires;
    spinlock_t lock;
    unsigned long magic;
    void (*function)(unsigned long);
    unsigned long data;
    tvec_base_t *base; 
}

当定时器到期,调用回调函数时,传入的数据是字段datadata可以是简单的数据,也可以是复杂数据结构的地址。

由于动态定时器是以jiffies为时间标准,即精度为1ms。

动态定时器间是用list组织,但是如果只用一个list组织动态定时器,那么检查动态定时器遍历整个list就非常耗时。 因此这里用了多级二维hash list,即时间轮,组织整个动态定时器。

动态定时器管理器(时间轮)结构

typedef struct tvec_t_base_s {
    spinlock_t lock;
    unsigned long timer_jiffies;
    struct timer_list *running_timer;
    tvec_root_t tv1;
    tvec_t tv2;
    tvec_t tv3;
    tvec_t tv4;
    tvec_t tv5;
} tvec_base_t;

tvec_root_ttvec_t是二维hash list,主list上有若干个节点,每个节点上是独立的list。 tv1有256个节点,在tv1中的动态定时器在接下来的255(2^8-1)个tick将会逐一到期。 tv2tv3tv4是64个节点的list,到期节点分别是(2^14)-1,(2^20)-1,(2^26)-1。 tv5也是64个节点的list,存储到期时间大于(2^26)-1的动态定时器。 与前几个list不同的是,tv5不会从其他list迁移,而且tv5的最后一个链表存储到期时间最大的定时器。 timer_jiffies指示最早的一个已到期还未被检查的动态定时器。 如果timer_jiffies和jiffies一致则表示没有被积压的动态定时器。 如果timer_jiffies小于jiffies则表示还有未处理的动态定时器。 需要注意的是,jiffies是异步更新,在检查动态定时器的过程中,全局jiffies仍在不断的增加。 由于延迟处理函数处理时间轮需要较长的时间,导致timer_jiffies可能远远小于jiffies。

那么时间轮的性能如何呢? 在tv1中,通过index = base->timer_jiffies & 255取出到期的节点的list。 这个操作的时间复杂度是O(1)。 如果index等于0则遍历上一级即tv2的链表,把到期时间小于255的定时器迁移到tv1。 同理后面的链表,只有当本级的链表size为0时,才遍历上一级链表做迁移操作。 迁移操作的时间复杂度时O(N)。 对于整个时间轮,假设每次tick都检查定时器,则99.6%的操作都会在tv1完成。 遍历tv2,tv3,tv4,tv5的时间间隔分别是255毫秒、16.4秒、17分28秒、18小时38分。 故时间轮的平均时间复杂度小于O(N)。

虽然时间轮是一个非常好的用来处理动态定时器的数据结构,但是检查动态定时器是一个非常耗时耗性能的操作。 检查动态定时器是通过一个延迟函数,在linux2.6中,动态定时器检查函数run_timer_softirq()由软中断TIMER_SOFTIRQ激活, 这个函数在激活后会执行一段时间。 因此,一般无法保证定时器的回调函数在指定的时刻被执行。 动态定时器只能保证在到期后的一个短暂延迟范围内执行回调函数。 所以,如果是严格的实时程序,需要用其他方法来保证更高精度的定时器。

综上,我们看到基于时间轮的动态定时器精度偏低,影响精度的三个方面分别是

  1. jiffies的时间精度为100毫秒
  2. 不是每次TIMER_SOFTIRQ都会激活检查函数
  3. run_timer_softirq()处理定时器list时, 靠list后面的定时器会有延迟

在smp处理器上,每个CPU有各自的时间轮,有效的避免了竞态。

Tags: 定时器 服务端技术