定时器原理通用定时器可以通过以下方式实现：
基于排序的链表模式：
通过对链表进行排序来保存定时器。因为链表是排序的，所以获得最小(最早到期)定时器的时间复杂度为O(1)。但是插入需要遍历整个链表，所以时间复杂度为O(n)。如下图：
基于最小堆模式：
定时器由最小堆保存，在最小堆中获取最小定时器的时间复杂度为O(1)，但插入一个定时器的时间复杂度为O(log n)。如下图：
基于平衡二叉树模式：
使用平衡二叉树(比如红黑树)保存定时器，获得平衡二叉树中最小定时器的时间复杂度为O(log n) (O(1)也可以通过缓存最小值来实现)，而插入一个定时器的时间复杂度为O(log n)。如下图：
时间轮：
但对于Linux这种对定时器依赖性很高的操作系统(网络子模块的TCP协议使用了大量定时器)，上述数据结构并不能满足要求。所以Linux使用了更高效的定时器算法：时间轮。
时间轮类似于日常生活的时钟。
在日常生活的时钟中，每当秒针转一圈，分针就走一格，而分针转一圈，时针就走一格。时间轮类似于时钟，就是把到期时间看成一个轮子，然后把计时器挂在这个轮子上，每一秒钟移动一次时针，执行那个时针上的计时器。
一般定时器范围是32位整数大小，即0 ~ 4294967295。如果通过数组存储，需要一个4294967296个元素的数组，内存浪费很大。这时可以用类似时钟的方式存储：通过多级数组。
时钟按小时、分钟和秒分等级。当然，我们也可以这样做，但是对于计算机来说，以小时和秒为单位的分级就不太友好了。因此，在Linux内核中，32位整数分为五个级别。第一级存储0 ~ 255秒的定时器，第二级256秒~ 256*64秒，第三级256*64秒~ 256 * 64 *。第四级为256*64*64秒~ 256 * 64 * 64秒，第五级为256*64*64*64秒~ 256*64*64*64秒。
注意：二级到五级数组的第一个槽不挂任何定时器。
每一级数组上面都有一个指针，指向当前要执行的定时器。每当时间过去一秒，Linux会先移动第一级的指针，然后在当前位置执行定时器。当指针变为0时，下一级的指针将被移动，该位置的计时器将被重新计算并插入时间轮，其他级别以此类推。
当你想执行已经过期的定时器时，只需要在一级数组上移动指针，在那个位置执行定时器列表，那么时间复杂度为O(1)，插入一个定时器也很简单。先计算定时器到期在哪一级的数组，连接到那个位置的链表，时间复杂度也是O(1)。
Linux时间轮的实现接下来我们来看看Linux内核是如何实现时间轮算法的。
定义五个级别的数组。
#定义TVN _ BITS 6 #定义TVR _ BITS 8 #定义TVN _ SIZE(1《TVN _ BITS)//64 #定义TVR _ SIZE(1《TVR _ BITS)//256 #定义TVN _ MASK(TVN _ SIZE-1)#定义TVR_MASK (TVR_SIZE - 1)结构timer_vec {
int索引；
struct list_head vec[TVN大小]；
};
struct timer_vec_root {
int索引；
struct list_head vec[TVR大小]；
};
静态结构timer _ vec tv5静态结构timer _ vec tv4静态结构timer _ vec tv3静态结构timer _ vec tv2静态结构timer _ vec _ root tv1void init_timervecs (void)
{
int I；
for(I=0；我《TVN _大小；i ) {
INIT _ LIST _ HEAD(tv5 . vec I)；
INIT _ LIST _ HEAD(tv4 . vec I)；
INIT _ LIST _ HEAD(tv3 . vec I)；
INIT _ LIST _ HEAD(tv2 . vec I)；
}
for(I=0；我《TVR _大小；我)
INIT _ LIST _ HEAD(tv1 . vec I)；
}
上面的代码定义第一级数组为计时器_车辆_根类型，其指数成员是当前要执行的定时器指针（对应vec成员的下标),而vec成员是一个链表数组，数组元素个数为256,每个元素上保存了该秒到期的定时器列表，其他等级的数组类似。
插入定时器
静态内联void internal _ add _ timer(结构timer _ list * timer)
{
/*
*调用此时必须经过许可
*/
无符号长过期=计时器-》。过期；
无符号长整型idx=expires-timer _ jiffies；
struct list _ head * vec
如果(idx 《TVR大小》{ //0 ~ 255
int I=过期TVR _掩码；
vec=tv1。vec I；
} else if(idx《1 》( TVR _比特TVN _比特)){ //256 ~ 16191
int I=(expires》TVR _ BITS)TVN _ MASK；
vec=tv2。vec I；
} else if(idx《1 》( TVR _比特2 * TVN比特)){
int I=(expires)》(TVR _比特TVN _比特))TVN _掩码；
vec=tv3。vec I；
} else if(idx《1 》( TVR _比特3 * TVN比特)){
int I=(expires)》(TVR _比特2 * TVN比特))TVN _掩码；
vec=tv4。vec I；
} else if(带符号长整型)idx 《0) {
/*可能发生在添加expires==jiffies的计时器时，
*或者你设置了一个定时器让它过去
*/
vec=tv1。vec tv1。指数；
} else if(idx"=0x ffffffful){
int I=(expires)》(TVR _比特3 * TVN比特))TVN _掩码；
vec=tv5。vec I；
}否则{
INIT _ LIST _ HEAD(timer-》LIST)；
返回；
}
/*
* 添加到链表中
*/
list_add(timer-》list，vec-》prev)；
}
内部添加计时器()函数的主要工作是计算定时器到期时间所属的等级范围，然后把定时器添加到链表中。
执行到期的定时器
静态内嵌void cascade _ timers(结构timer _ vec * TV)
{
struct list_head *head，*curr，* next
head=tv-》vec tv-》指数；
curr=head-》。接下来；
/*
*我们正在从列表中删除所有计时器，所以我们不必这样做
*单独分离它们，之后清除列表即可。
*/
while (curr！=head) {
结构计时器列表* tmp
tmp=list_entry(curr，struct timer_list，list)；
next=curr-》next；
list _ del(curr)；
internal _ add _ timer(tmp)；
curr=下一个
}
初始化列表头(头);
电视-》。指数=(电视-》)指数1)TVN面具；
}
静态内联void运行计时器列表(void)
{
spin _ lock _ IRQ(定时器列表_锁)；
while((long)(jiffies-timer _ jiffies)"=0){
结构列表_头*头，*货币
如果(!tv1.index) { //完成了一个轮回，移动下一个单位的定时器
int n=1；
做{
cascade _ timers(tve cs[n])；
} while(tve cs[n]-"index==1n《NOOF _ tve cs》)；
}
重复：
head=tv1。vec tv1。指数；
curr=head-》。接下来；
if (curr！=head) {
结构计时器列表*计时器
void (*fn)(无符号长整型);
无符号长数据；
timer=list_entry(curr，struct timer_list，list)；
fn=定时器-》。功能；
数据=定时器-》数据；
分离计时器(定时器);
计时器-》列表。下一个=计时器-》列表。prev=NULL
timer_enter(定时器);
spin _ unlock _ IRQ(定时器列表_锁定)；
fn(数据);
spin _ lock _ IRQ(定时器列表_锁)；
time _ exit()；
转到重复；
}
定时器_ jiffies
tv1。index=(tv1。索引1)TVR _掩码；
}
spin _ unlock _ IRQ(定时器列表_锁定)；
}
执行到期的定时器主要通过run_timer_list()函数完成，该函数首先比较当前时间与最后一次运行run_timer_list()函数时间的差值，然后循环这个差值的次数，并执行当前指针位置上的定时器。
每循环一次对第一级数组指针进行加一操作，当第一级数组指针变为0(即所有定时器都执行完),那么就移动下一个等级的指针，并把该位置上的定时器重新计算插入到时间轮中，重新计算定时器通过级联计时器()函数实现。
日本季刊日本季刊
