以最开始从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中;不再赘述。
给出两张好图,方便理解:
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详解
如果对该算法的复杂度,内存使用有一般的分析,或者该算法和其他算法的对比,可以参考文章:
kernel/timer.c designIngo Molnar 对 linux 中的时间轮的实现做了最好的解释。
Linux的动态定时器从本质上是single-shottimer,也就是说timer到期了,调用回调函数后,这个timer就会删掉。如果要实现repeatingtimer,可以在回调函数中再次注册自己,这样该定时器就成了一个周期性的定时器。理解了定时器的算法,做一个周期性的定时器就很容易了~~