定时器的原理。定时器的实现方式一般有以下几种：基于排序链表的方法：通过对链表进行排序来保存定时器。由于链表是有序的，最小的（最早到周期）定时器的时间复杂度是O(1)。但是插入需要遍历整个链表，所以时间复杂度是O(n)。如下图所示：图片是基于最小堆的方法：定时器是通过最小堆保存的，在最小堆中获取最小定时器的时间复杂度为O(1)，但是时间复杂度为插入计时器是O(logn)。如下图所示：图片是基于平衡二叉树的方法：使用平衡二叉树（如红黑树）保存定时器，平衡二叉中获取最小定时器的时间复杂度tree是O(logn)(也可以缓存最小值。达到O(1))，插入一个timer的时间复杂度是O(logn)。如下图所示：图片时间轮：但是对于Linux这样高度依赖定时器的操作系统（网络子模块的TCP协议使用了大量的定时器），上述数据结构无法满足要求.所以Linux使用了一种更高效的定时器算法：时间轮。时间轮类似于日常生活中的时钟，如下图所示：图日常生活中的时钟，秒针每转一圈，分针走一格，当分针转一圈时圈，时针将移动一格。时间轮的实现类似于时钟，就是把过期时间看成一个轮子，然后把定时器挂在轮子上，时间每走一秒，时针就会走动，并且时针上的定时器被执行，如下图：图中一般的定时器范围是32位整数大小，即0~4294967295。如果存储在数组中，一个数组有4294967296元素是必需的，这是一种内存浪费。这时候可以用类似于钟表的方式存储：通过多级数组。时钟按小时、分钟和秒分级。当然我们也可以这样做，但是对于计算机来说，时分秒的分级并不是很友好。因此，在Linux内核中，32位整数分为5级。第一级存储0~255秒定时器，第二级为256秒~256*64秒，第三级为256*64秒~256*64*64秒，第四级为256*64*64秒~256*64*64*64秒，第五关为256*64*64*64秒~256*64*64*64*64秒。如下图所示：图注：第二至第五级阵列的第一个槽位不接任何定时器。每一层数组都有一个指针，指向当前要执行的定时器。时间每经过一秒，Linux就会先移动第一层的指针，然后在当前位置执行定时器。当指针变为0时，会移动下一层的指针，重新计算该位置的定时器并插入时间轮，其他层以此类推。如下图所示：当图片需要执行过期定时器时，只需要移动一级数组上的指针，在该位置执行定时器链表即可，所以时间复杂度为O(1)，并且插入一个定时器定时器也很简单，先计算定时器的到期时间范围在第几级数组，在这个位置连接链表，时间复杂度也是O(1)。Linux时间轮的实现接下来我们看看Linux内核是如何实现时间轮算法的。定义一个五级数组#defineTVN_BITS6#defineTVR_BITS8#defineTVN_SIZE(1<expires;unsignedlongidx=expires-timer_jiffies;structlist_head*vec;if(idx>TVR_BITS)&TVN_MASK;vec=tv2.vec+i;}elseif(idx<1<<(TVR_BITS+2*TVN_BITS)){inti=(expires>>(TVR_BITS+TVN_BITS))&TVN_MASK;vec=tv3.vec+i;}elseif(idx<1<<(TVR_BITS+3*TVN_BITS)){inti=(expires>>(TVR_BITS+2*TVN_BITS))&TVN_MASK;vec=tv4.vec+i;}elseif((signedlong)idx<0){/*canhappenifyouaddatimerwithexpires==jiffies,*oryousetatimertogooffinthepast*/vec=tv1.vec+tv1.index;}elseif(idx<=0xffffffffUL){inti=(expires>>(TVR_BITS+3*TVN_BITS))&TVN_MASK;vec=tv5.vec+i;}else{/*Canonlygethereonarchitectureswith64-bitjiffies*/INIT_LIST_HEAD(&timer->list);return;}/**添加到链接表中*/list_add(&timer->list,vec->prev);}internal_add_timer()函数的主要工作是计算定时器超时的级别范围，然后将定时器添加到链表中执行到期的定时器staticinlinevoidcascade_timers(structtimer_vec*tv){/*cascadeallthetimersfromtvuponelevel*/structlist_head*head,*curr,*next;head=tv->vec+tv->index;curr=head->next;/**我们正在从列表中删除_all_timers，所以我们不必*单独分离它们，之后只需清除列表。*/while(curr!=head){structtimer_list*tmp;tmp=list_entry(curr,structtimer_list,list);next=curr->next;list_del(curr);internal_add_timer(tmp);curr=next;}INIT_LIST_HEAD(head);tv->index=(tv->index+1)&TVN_MASK;}staticinlinevoidrun_timer_list(void){spin_lock_irq(&timerlist_lock);while((long)(jiffies-timer_jiffies)>=0){structlist_head*head,*curr;if(!tv1.index){//完成了一个轮回，移动到一个单位的定时器intn=1;do{cascade_timers(tvecs[n]);}while(tvecs[n]->index==1&&++nnext;if(curr!=head){structtimer_list*timer;void(*fn)(unsignedlong);unsignedlongdata;timer=list_entry(curr,structtimer_list,list);fn=timer->function;data=timer->data;detach_timer(timer);timer->list.next=timer->list.prev=NULL;timer_enter(timer);spin_unlock_irq(&timerlist_lock);fn(data);spin_lock_irq(&timerlist_lock);timer_exit();gotorepeat;}++timer_jiffies;tv1.index=(tv1.index+1)&TVR_MASK;}spin_unlock_irq(&timerlist_lock);}过期定时器主要由run_timer_list()函数完成，它首先比较当前的run_timer_list()函数的时间和上次运行时间的差值，然后循环这个差值的次数，在当前指针位置执行timer，每次对一级数组的指针加1循环，当一级数组指针变为0时（即所有定时器都执行完毕），再移动下一级的指针，将这个位置的定时器重新计算到时间轮中，通过重新计算定时器cascade_timers()函数。
