日期:2014-05-16  浏览次数:20702 次

linux内核定时器

linux的定时器一般分为两种,一种是timeout类型,也就是在指定时间之前完成相应的任务即可,这种定时器对精度要求较低,晚几毫秒执行不会有很大的影响,而且一般这种类型的定时器要处理的任务在超时之前就已经完成,并且从定时器的队列中删除了,用不着真正的等到timeout然后由定时器模块来处理,这种较低精度要求的定时器一般使用timer wheel定时器。另一种类型的就是timer类型定时器,这就要求必须在指定的时间执行相应的任务,因此精度要求较高,这种场合一般适用高精度的定时器hrtimer。

timer wheel和hrtimer使用两种不同的机制实现定时器,timer wheel使用jiffies为基准来判断任务是否过期,由于jiffies计数系统的节拍,系统每次时钟中断都会将这个值加1,系统每秒的时钟中断的次数为HZ(宏定义的一个常量,一般为100),因此jiffies为timer wheel定时器提供了毫秒级的精度。而hrtimer需要高精度的时钟设备,为系统提供纳秒级的定时器。这两者都通过软中断来驱动,timer wheel定时器通过软中断TIMER_SOFTIRQ, 而hrtimer通过HRTIMER_SOFTIRQ来相应定时器。

1. timer wheel定时器

timer wheel定时器的请求通过struct timer_list来抽象,然后按照定时器的过期时间和基准时间的差值将其组织在双链表中,且相同过期时间的定时器放在同一个链表中,当响应软中断时,则将过期时间在当前时间之前的定时器全部删除,并且执行相应的回调函数。
struct timer_list {
	/*
	 * All fields that change during normal runtime grouped to the
	 * same cacheline
	 */
	struct list_head entry; //双链表的节点
	unsigned long expires; //过期时间
	struct tvec_base *base; /*由于定时器的基准时间不会随着jiffies的值实时更新,这个为定时器提供了基准时间,并且组织所有的在这个base上的timer_list对象,从下面tvec_base定义可以看到是缓冲区对齐,因此base变量的最后一位肯定是0,可以用这一位来表示其他信息,当base最后一位为1表示此定时器是deferrable的,可以延迟一定时间执行*/

	void (*function)(unsigned long); //回调函数和回调函数的参数
	unsigned long data;

	int slack;

#ifdef CONFIG_TIMER_STATS //统计相关
	int start_pid;
	void *start_site;
	char start_comm[16];
#endif
#ifdef CONFIG_LOCKDEP
	struct lockdep_map lockdep_map;
#endif
};
#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)
#define TVN_MASK (TVN_SIZE - 1)
#define TVR_MASK (TVR_SIZE - 1)

struct tvec {
	struct list_head vec[TVN_SIZE];
};

struct tvec_root {
	struct list_head vec[TVR_SIZE];
}; //定时器双链表的表头

struct tvec_base {
	spinlock_t lock;
	struct timer_list *running_timer; //正在执行的timer_list
	unsigned long timer_jiffies; //上文说的基准时间
	unsigned long next_timer; //距离timer_jiffies最近的过期时间
	struct tvec_root tv1; //tv1--tv5根据过期时间的大小将timer_list放入其中,tv1表示过期时间最短的任务
	struct tvec tv2;
	struct tvec tv3;
	struct tvec tv4;
	struct tvec tv5;
} ____cacheline_aligned;


上面的几个结构的关系可以用下图表示出来:


struct timer_list对象是放在tv1--tv5中那个struct tvec上是通过timer_list.expire-tvec_base.timer_jiffies来确定的,也就是说,是通过过期时间和基准时间之间的差值来确定struct timer_list对象在哪个tvX上的。

若上面的差值可以在TVR_BITS位内表示出来,则将相应的timer_list放在tv1上,而TVR_BITS内的数值作为timer_list在tvec数组上的索引,将其串到双链表上,若可以在TVR_BITS + TVN_BITS位内表示差值,则将其放在tv2上,TVN_BITS位段内的值当做tv2数组内部的索引,然后依次类推,若差值大于1<<TVR_BITS+3*TVN_BTS,则将其全部放在tv5内,表示过期时间还很长,一段时间内轮不到其执行,最后的TVN_BITS位作为tv5内的索引。

插入定时器的操作可以清晰的看到上面的过程:
static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
	unsigned long expires = timer->expires;
	unsigned long idx = expires - base->timer_jiffies;
	struct list_head *vec;

	if (idx < TVR_SIZE) { //tv1位段内
		int i = expires & TVR_MASK;
		vec = base->tv1.vec + i;
	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) { //tv2位段内
		int i = (expires >> TVR_BITS) & TVN_MASK;
		vec = base->tv2.vec + i;
	} else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
		int i = (expires >> (TVR_BITS + TVN_BITS)