上两篇文章介绍了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;
}
当定时器到期,调用回调函数时,传入的数据是字段data
。data
可以是简单的数据,也可以是复杂数据结构的地址。
由于动态定时器是以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_t
和tvec_t
是二维hash list,主list上有若干个节点,每个节点上是独立的list。
tv1
有256个节点,在tv1中的动态定时器在接下来的255(2^8-1)个tick将会逐一到期。
tv2
、tv3
、tv4
是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
激活,
这个函数在激活后会执行一段时间。
因此,一般无法保证定时器的回调函数在指定的时刻被执行。
动态定时器只能保证在到期后的一个短暂延迟范围内执行回调函数。
所以,如果是严格的实时程序,需要用其他方法来保证更高精度的定时器。
综上,我们看到基于时间轮的动态定时器精度偏低,影响精度的三个方面分别是
- jiffies的时间精度为100毫秒
- 不是每次
TIMER_SOFTIRQ
都会激活检查函数 run_timer_softirq()
处理定时器list时, 靠list后面的定时器会有延迟
在smp处理器上,每个CPU有各自的时间轮,有效的避免了竞态。