湖州做网站推广的公司,wordpress easydigital,求会wordpress的人,网络规划设计师报考陕西时间轮 简述
顾名思义#xff0c;时间轮就像一个轮子#xff0c;在转动的时候外界会指向轮子不同的区域#xff0c;该区域就可以被使用。因此只要将不同时间的定时器按照一定的方法散列到时间轮的不同槽#xff08;即时间轮划分的区域#xff09;之中#xff0c;就可以实…时间轮 简述
顾名思义时间轮就像一个轮子在转动的时候外界会指向轮子不同的区域该区域就可以被使用。因此只要将不同时间的定时器按照一定的方法散列到时间轮的不同槽即时间轮划分的区域之中就可以实现在运转到某个槽时进行判断该定时器是否已经到达运行时间需要判断是由于有的定时器并非在这一圈就需要运行可能需要后面几圈才会运行。 从图中也可以看出每个槽中的定时器是以双向链表形式存储的每次添加的时候直接插入到链表的开始头插法。值得注意的是由于使用头插法因此在运行到某个槽时需要遍历一遍链表已检查是否有到达时间的计时器有的话就运行并删除结点。
至于在每转到一个槽时都要检查是否到达运行时间可以这样理解时间轮进行散列的方法就是取余运算假设每个槽的间隔为1s共有n个槽当前转到了第cur个槽那么一个定时在 t s以后运行的定时器就要放在第 cur t % n % n个槽并在运行t / n圈后到达该槽时才会运行。因此一个槽中的定时器运行的时间是相差ii 0个周期的。
所以时间轮简单来说就是散列 链表这样与使用升序链表相比散列可以直接定位要插入的槽所在位置可以提高添加定时器的效率由O(N)到了O(1)。
对实现时间轮来说最主要的还是链表的操作是否熟练当然也主要是双向链表的添加与删除。 代码分析
记录定时器的时间信息从而获取在时间轮中槽的位置以及在多少圈之后被触发。在定时时间不足槽之间切换的时间时要将t/n记为1否则记录t/n的整除结果。 // timeout为定时时间SI为槽之间切换的时间int ticks;if( timeout SI ) {ticks 1;} else {ticks timeout / SI;}int rotation ticks / N; // 被触发的圈数int ts ( cur_slot ticks % N ) % N; // 被插入的槽为提高定时器的添加效率使用头插法将定时器添加在槽的开始位置。使用双向链表需要注意将后面的结点的pre指向前一个结点。删除链表时要注意结点是否是第一个结点 代码实现含注释
#ifndef _TIMEWHEEL_H_
#define _TIMEWHEEL_H_#include time.h
#include netinet/in.hconst int BUFFER_SIZE 64;class TwTimer;// 用户数据绑定socket和定时器
struct client_data {sockaddr_in address;int sock_fd;char buf[BUFFER_SIZE];TwTimer* timer;
};// 定时器类时间轮采用双向链表
class TwTimer {
public:int rotation; // 定时器转多少圈后生效int time_slot; // 记录定时器属于时间轮的哪个时间槽client_data* user_data; // 客户数据TwTimer* next; // 指向下一个定时器TwTimer* pre; // 指向上一个定时器
public:TwTimer( int rot, int ts ) : rotation(rot), time_slot(ts), next(NULL), pre(NULL) {}void (*cb_func)( client_data * ); // 回调函数
};class TimeWheel {
private: static const int N 60; // 槽的数目static const int SI 1; // 定时器槽之间时间间隔TwTimer* slot[ N ]; // 时间轮的槽指向一个定时器链表链表无序int cur_slot; // 当前槽
public:TimeWheel() : cur_slot(0) {for( int i 0; i N; i ) {slot[i] NULL;}}~TimeWheel() {for( int i 0; i N; i ) {TwTimer* tmp;while( tmp slot[i], tmp ) {slot[i] tmp-next;delete tmp;}}}TwTimer* add_timer( int timeout ); // 根据定时值创建定时器并插入槽中void del_timer( TwTimer* timer );void tick();
};TwTimer* TimeWheel::add_timer( int timeout ) {if( timeout 0 ) {return NULL;}// 记录多少个tick后被触发不足最小单位SI的记为1其余为timeout/SIint ticks 0;if( timeout SI ) {ticks 1;} else {ticks timeout / SI;}int rotation ticks / N; // 被触发的圈数int ts ( cur_slot ticks % N ) % N; // 被插入的槽TwTimer* timer new TwTimer( rotation, ts );// 如果链表为空则放到头否则插入到第一个位置if( !slot[ts] ) {slot[ts] timer;} else {timer-next slot[ts];slot[ts]-pre timer;slot[ts] timer;}return timer;
}// 删除定时器
void TimeWheel::del_timer( TwTimer* timer ) {if( !timer ) {return;}// 注意链表为双向的int ts timer-time_slot;if( timer slot[ts] ) {slot[ts] slot[ts]-next;if( slot[ts] ) {slot[ts]-pre NULL;}} else {timer-pre-next timer-next;if( timer-next ) {timer-next-pre timer-pre;}}delete timer;
}// SI时间到后条用该函数时间轮向前滚动一个槽的间隔
void TimeWheel::tick() {TwTimer* tmp slot[cur_slot];while( tmp ) {if( tmp-rotation 0 ) { // 定时时间未到tmp-rotation--;tmp tmp-next;} else { // 定时时间已到tmp-cb_func( tmp-user_data );if( tmp slot[cur_slot] ) { // tmp位于链表首slot[cur_slot] tmp-next;if( slot[cur_slot] ) {slot[cur_slot]-pre NULL;}delete tmp;tmp slot[cur_slot];} else { // tmp位于链表中tmp-pre-next tmp-next;if( tmp-next ) {tmp-next-pre tmp-pre;}TwTimer* tmp2 tmp-next;delete tmp;tmp tmp2;}}}cur_slot ( cur_slot 1 ) % N;
}#endif
