Linux内核时钟系统和定时器实现( 五 ) _Linux内核

文章插图

简单时间轮还有很多实现方式，此时时间轮的每个spoke的含义不再是时间精度，而是某个hashkey，例如ACE当中采用的简单时间轮，轮子的含义：
( 触发时间 >> 分辨率的位数)&(spoke大小-1)
每个spoke所链接的timer列表可以采用很高效的multimap来实现，让timer的插入时间可以降到O(lgn)，到期处理时间最坏为O(nlgn)，n为每个spoke中的timer个数。

文章插图

多级时间轮
多级时间轮的实现方式被比作经典的”水表实现方式”，一级时间轮只有一个进制，多级时间轮采用了不同的进制，最低级的时间轮每个spoke表示基本的时间精度，次级时间轮每个spoke表示的时间精度为最低级时间轮所能表示时间长度，依次类推。例如内核的时间轮采用5级时间轮，每一级时间轮spoke个数从低级到高级分别为：8,6,6,6,6，所能表达的时间长度为：2^6 * 2^6 * 2^6 * 2^6 * 2^8 = 2^32 ticks，在系统tick精度为10ms时，内核时间轮所能表示的时间跨度为42949672.96s，约为497天。
那么多级时间轮如何工作的呢：

文章插图

Insert：

定时器的插入，首先都要根据定时器的超时时间与每级时间轮所能表示的时长进行比较，来觉得插入到那个轮子中，再根据当前轮子已走的索引，计算出待插入定时器在该轮子中应插入的spoke 。

#define WHEEL_THRESHOLD_LEVEL_1 (0x01 << 8) #define WHEEL_THRESHOLD_LEVEL_2 (0x01 << (8 + 6))#define WHEEL_THRESHOLD_LEVEL_3 (0x01 << (8 + 2 * 6))#define WHEEL_THRESHOLD_LEVEL_4 (0x01 << (8 + 3 * 6))#define WHEEL_THRESHOLD_LEVEL_5 (0x01 << (8 + 4 * 6))

Schedule：

多级时间轮定时器触发机制为周期性tick出发，每个tick到来，最低级的tv1的spoke index都会+1，如果该spoke中有timer，那么就处理该timer list中的所有超时timer 。

Cascade：

Cascade可以翻译成降级处理。每个tick到来，都只会去检测最低级的tv1的时间轮，因为多级时间轮的设计决定了最低级的时间轮永远保存这最近要超时的定时器。
多级时间轮最重要的一个处理流程就是cascade，当每一级(除了最高级)时间轮走到超出该级时间轮的范围时，就会触发上一级时间轮所在spoke+1的cascade过程，如果上一级时间轮也走出来时间轮的范围，也同样会触发cascade过程，这是一个递归过程。
在cascade过程中存在一种极限情况，所有的时间轮都会进行cascade处理，这个时候tv2, tv3, tv4, tv5的hlsit_head[0]都会发送变动，这个过程在定时数量比较大的情况下，会是一个比较耗时的处理流程。