江苏龙网

  1. 主页 > 生活百科 > >

Linux定时器 - 高性能定时器

Linux

时间轮基于排序链表的定时器（Linux定时器 - 定时的方法）存在一个问题：添加定时器的效率偏低 。下面我们要讨论的时间轮解决了这个问题 。下图是一种简单的时间轮：

Linux定时器 - 高性能定时器

文章插图
 
上图时间轮内 ， （实现）指针指向轮子上的一个槽（slot) 。它以恒定的速度顺时针转动 ， 每转动一步就指向下一个槽（虚线指针指向的槽） ， 每次转动称为一个滴答（tick） 。一个滴答的时间称为时间轮的槽间隔si(slot interval) ， 它实际上就是心跳时间 。该时间轮共有N个槽 ， 因此它运转一周的时间是N*si 。每个槽指向一条定时器链表 ， 每条链表上的定时器具有相同的特征：它们的定时时间相差N*si的整数倍 。时间轮正是利用这个关系将定时器散列到不同的链表中 。假如现在指针指向槽cs ， 我们要添加一个定时时间为ti的定时器 ， 则该定时器被插入的槽ts(time slot)对应的链表中：
ts = (cs + ti/si) % N
基于排序链表的定时器使用唯一的一条链表来管理所有定时器 ， 所以插入操作的效率随着定时器数目的增多而降低 。而时间轮使用哈希表的思想 ， 将定时器散列到不同的链表上 。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目 ， 插入操作的效率基本不受定时器数目的影响 。
很显然 ， 对时间轮而言 ， 要提高定时精度 ， 就要使si值足够小；要提高执行效率 ， 则要求N值足够大 。
上图描述的是一种简单的时间轮 ， 因为它只有一个轮子 。而复杂的时间轮可能有多个轮子 ， 不同的轮子拥有不同的粒度 。相邻的两个轮子 ， 精度高的转一圈 ， 精度低的仅往前移动一槽 ， 就像水表一样 。
下面的示例代码展示了一个较为简单的时间轮实现代码：
#ifndef TIME_WHEEL_TIMER_H#define TIME_WHEEL_TIMER_H#include <time.h>#include <netinet/in.h>#include <stdio.h>#define BUFFER_SIZE 64class tw_timer;/*解绑socket和定时器*/struct client_data{sockaddr_in address;int sockfd;char buf[BUFFER_SIZE];tw_timer* timer;};/*定时器类*/class tw_timer{public:tw_timer(int rot, int ts):next(NULL), prev(NULL), rotation(rot), time_slot(ts){}public:int rotation; /*记录定时器在时间轮转多少圈生效*/inttime_slot; /*记录定时器属于时间轮上哪个槽（对应的链表）*/void (*cb_func)(client_data*); /*定时器回调函数*/client_data* user_data; /*客户数据*/tw_timer* next;tw_timer* prev;};class time_wheel{public:time_wheel():cur_slot(0){for(int i = 0; i < N; ++i){slots[i] = NULL;}}~time_wheel(){for(int i = 0; i < N; ++i){tw_timer* tmp = slots[i];while(tmp){slots[i] = tmp->next;delete tmp;tmp = slots[i];}}}tw_timer* add_timer(int timeout){if(timeout < 0){return NULL;}int ticks = 0;/*根据插入定时器的超时时间计算它将在时间轮转动多少个滴答后被触发*并将该滴答数存于变量ticks 。*如果待输入定时器的超时值小于时间轮的槽间隔SI ， 则将ticks向上折为1,*否则就将ticks向下折为timeout/SI*/if (timeout < SI){ticks = 1;}else{ticks = timeout / SI;}/*计算待插入的定时器在时间轮转动多少圈后被触发*/int rotation = ticks/ N;/*计算待插入的定时器应该被插入哪个槽中*/int ts = (cur_slot + ticks%N) % N;/*创建新的定时器 ， 它在时间论转动rotation圈之后触发 ， 且位于ts个槽上*/tw_timer* timer = new tw_timer(rotation, ts);/*如果第ts个槽上尚无任何定时器 ， 则把新建的定时器插入其中 ， *并将该定时器设置为该槽的头节点*/if(!slots[ts]){printf("add timer, rotation is %d, ts is %d, cur_slot is %dn",rotation, ts, cur_slot);slots[ts] = timer;}else{timer->next = slots[ts];slots[ts]->prev = timer;slots[ts] = timer;}return timer;}void del_timer(tw_timer* timer){if(!timer){return;}int ts = timer->time_slot;if(timer == slots[ts]){slots[ts] = slots[ts]->next;if(slots[ts]){slots[ts]->prev = NULL;}delete timer;}else{timer->prev->next = timer->next;if(timer->next){timer->next->prev = timer->prev;}delete timer;}}void tick(){tw_timer* tmp = slots[cur_slot]; /*取得时间轮上当前槽点的头节点*/printf("current slot is %dn", cur_slot);while(tmp){printf("tick the timer oncen");/*如果定时器rotation值大于0, 则它在这一轮不起作用*/if(tmp->rotation > 0){tmp->rotation--;tmp = tmp->next;}/*否则定时器已经到期于是执行任务 ， 然后删除该定时器*/else{tmp->cb_func(tmp->user_data);if(tmp == slots[cur_slot]){printf("delete header in cur_slot");slots[cur_slot] = tmp->next;delete tmp;if(slots[cur_slot]){slots[cur_slot]->prev = NULL;}tmp = slots[cur_slot];}else{tmp->prev->next = tmp->next;if(tmp->next){tmp->next->prev = tmp->prev;}tw_timer* tmp2 = tmp->next;delete tmp;tmp = tmp2;}}}cur_slot = ++cur_slot % N;}private:/*时间轮上槽的数目*/static const int N = 60;/*每1秒时间轮转动一次 ， 即槽间隔1s*/static const int SI = 1;/*时间轮的槽 ， 其中每个元素只想一个定时器链表 ， 链表无序*/tw_timer *slots[N];int cur_slot; /*时间轮的当前槽*/};#endif


推荐阅读


上一篇：红楼梦中的薛宝钗是个怎样的人

下一篇：2020年中国扫地机器人市场现状与发展前景分析