Linux的动态定时器(4)

以最开始从tv2中的第一个桶搬移到tv1中为例:这时候的INDEX(0)就是1;

list_replace_init(tv->vec+ index, &tv_list);

首先找到这个tv2下这个桶挂着的链表;

list_for_each_entry_safe(timer,tmp, &tv_list, entry) {

BUG_ON(tbase_get_base(timer->base)!= base);

internal_add_timer(base,timer);

}

然后遍历刚才找到的链表,对每一个链表项上的定时器进行添加操作;

举个数据例子:

最开始tv1中包含的还有256节拍以内到期的定时器,而tv2的第一个桶包含的还有256—512节拍到期的定时器,因为时间在流逝,tv1中的定时器都被处理了,这时候tv2中第一个桶中的定时器就变为还有256节拍内到期的定时器了;

因此在internal_add_timer(base,timer);函数中根据idx这个差值来选择具体的tv向量,所以这里的定时器都被插入到tv1中。

后面的搬移是同样的道理,比如tv3中的第一个桶会搬移到tv1和tv2中;不再赘述。

给出两张好图,方便理解:

Linux的动态定时器

Linux的动态定时器

B、++base->timer_jiffies;值加1;

C、list_replace_init(base->tv1.vec+ index, &work_list);//我们始终最关心的还是tv1中的定时器,因为它们很快就要到期了

while(!list_empty(head)) {

……

}

对于用index索引到的base->tv1.vec+ index的那256个桶中的一个,这个while循环遍历该桶中的链表中挂着的每一个定时器:

{

void(*fn)(unsigned long);

unsignedlong data;


timer= list_first_entry(head, struct timer_list,entry);

fn= timer->function;

data= timer->data;


timer_stats_account_timer(timer);


set_running_timer(base,timer);

detach_timer(timer,1);

……

trace_timer_expire_entry(timer);

fn(data);

trace_timer_expire_exit(timer);

timer= list_first_entry(head, structtimer_list,entry);是利用container_of宏定义来根据list_head指针获取定时器的指针;

fn = timer->function;

data= timer->data;

fn和data就是初始化定时器时设定的回调函数;

detach_timer(timer,1);将该定时器从链表中删除;

fn(data); 调用fn(timer->function )函数;

到此,利用软中断机制和特殊设计的hash,linux内核中的动态定时器在算法复杂度和内存上都比较优化。仔细揣摩一下这个动态定时器的设计,就觉得设计的还是相当的巧妙,

利用多级数组+双向链表,用hash的思想做了时间轮的设计。在算法复杂度和内存上都不错。

如果对此不够理解,可以参考下面这篇,写的比较简洁清晰的:

Linux2.6定时器的时间轮算法分析
Linux 内核定时器 timer_list详解

如果对该算法的复杂度,内存使用有一般的分析,或者该算法和其他算法的对比,可以参考文章:

Linux 下定时器的实现方式分析

kernel/timer.c designIngo Molnar 对 linux 中的时间轮的实现做了最好的解释。

Linux的动态定时器从本质上是single-shottimer,也就是说timer到期了,调用回调函数后,这个timer就会删掉。如果要实现repeatingtimer,可以在回调函数中再次注册自己,这样该定时器就成了一个周期性的定时器。理解了定时器的算法,做一个周期性的定时器就很容易了~~

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/pssxw.html