高性能定时器
时间论
- 基于排序链表的定时器存在一个问题:添加定时器的效率偏低
时间论解决了这个问题
-
上图所示时间论,(实线)指针指向轮子的一个槽(slot)。
它恒定的速度顺时针转动，每转动一步就指向下一个槽（虚线指向的槽），每次转动称为一个滴答（tick）。 -
一个滴答的时间称为时间论的槽间隔si，它实际上就是心搏时间。
该时间论共有N个槽，因此它转动一周的时间是N*si。 -
每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差N＊si的整数倍。
时间轮正是利用这个关系将定时器散列到不同的链表中。 -
假如现在指针指向槽cs，我们要添加一个定时时间为ti的定时器，则该定时器将被插入槽ts对应的链表中：
ts = (cs + (ti/si))%N（图11-1）- 基于排序链表的定时器使用唯一的一条链表来管理所有定时器，所以插入操作的效率随着定时器数据的增多而降低。
- 而时间轮使用哈希表的思想，将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。
-
显然，对时间轮而言，要提高定时精度，就要使si值足够小；要提高执行效率，则要求N值足够大。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 |
#ifndef TIME_WHEEL_TIMER #define TIME_WHEEL_TIMER #include <time.h> #include <netinet/in.h> #include <stdio.h> #define BUFFER_SIZE 64 class 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; // 记录定时器在时间轮转多少圈后生效 int time_slot; // 记录定时器属于时间轮上哪个槽（对应的链表） void (*cb_func)(client_data*); // 定时器回调函数 client_data* user_data; // 客户数据 tw_timer* next; // 下一个定时器 tw_timer* prev; // 前一个定时器 }; class time_wheel { 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]; } } } // 根据定时值timeout创建一个定时器，并把它插入合适的槽中 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 %d\n", rotation, ts, cur_slot); slots[ts] = timer; } else { // 否则，将定时器插入第ts个槽中 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; // slots[ts]是目标定时器所在槽的头结点 // 如果目标定时器就是该头结点，则需要重置第ts个槽的头结点 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; } } // SI时间到后，调用该函数，时间轮向前滚动一个槽的间隔 void tick() { // 取得时间轮上当前槽的头结点 tw_timer* tmp = slots[cur_slot]; printf("current slot is %d\n", cur_slot); while(tmp) { printf("tick the timer once\n"); // 如果定时器的rotation值大于0，则它在这一轮不起作用 if (tmp->rotation > 0) { tmp = tmp->next; } else { // 否则，就说明定时器已经到期，于是执行任务，然后删除该定时器 tmp->cb_func(tmp->user_data); if (tmp == slots[cur_slot]) { printf("delete header in cur_slot\n"); 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秒时间轮转动一次，槽间隔为1秒 static const int SI= 1; // 时间轮的槽，其中每个元素指向一个定时器链表，链表无序 tw_timer* slots[N]; int cur_slot; // 时间轮的当前槽 }; #endif |
时间堆
- 定时器的另一种思路是：
- 将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。
这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。 - 然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复，就实现了较为准确的定时。
- 将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。
- 最小堆很适合处理这种定时方案。
- 最小堆是指每个节点的指都小于或等于其子节点的值的完全二叉树。
- 最小堆插入：
- 为了将一个元素X插入最小堆，我们可以在树的下一个空闲位置创建一个空穴。
- 如果X可以放在空穴中而不破坏堆序，则插入完成。
- 否则就执行上虑操作，即交互空穴和它的父节点上的元素。
- 不断的执行上述操作，知道X可以被放入空穴，则插入完成。
- 最小堆删除：
- 删除操作指的是删除其根节点上的元素，并且不破坏堆序性质。
- 执行删除操作时，需要先在根节点处创建一个空穴。由于堆现在少了一个元素，因此可以把堆的最后一个元素X移动到该堆的某个地方。
- 如果X可以被放入空穴，则删除操作完成。否则就执行下虑操作，即交换空穴和它的两个儿子节点中的较小者。
- 不断进行上述过程，知道X可以被放入空穴，则删除操作完成。
- 由于最小堆是一颗完全二叉树，所以可以用数组来组织其中的元素。
- 对于数组中的任意一个位置i上的元素，其左儿子节点在位置
2i+1上，其右儿子节点在位置2i+2上，其父节点则在位置[(i-1)/2](i>0)上。 - 与链表来表示堆相比，用数组表示堆不仅节省空间，而且更容易实现堆的插入，删除等操作。
- 对于数组中的任意一个位置i上的元素，其左儿子节点在位置
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 |
#ifndef MIN_HEAP #define MIN_HEAP #include <iostream> #include <netinet/in.h> #include <time.h> using std::exception; #define BUFFER_SIZE 64 class heap_time; // 绑定socket和定时器 struct client_data { sockaddr_in address; int sockfd; char buf[BUFFER_SIZE]; heap_timer* timer; }; // 定时器类 class heap_timer { public: heap_timer(int delay) { expire = time(NULL) +delay; } public: time_t expire; // 定时器生效的绝对时间 void (*cb_func)(client_data*); // 回调函数 client_data* user_data; // 用户数据 }; // 时间堆类 class time_heap { time_heap(int cap) throw(std::exception) : capacity(cap), cur_size(0) { array = new heap_timer*[capacity]; if (!array) { throw std::exception(); } for (int i = 0; i < capacity; ++i) { array[i] = NULL; } } time_heap(heap_timer** init_array, int size, int capacity) throw (std::exception) : cur_size(size),capacity(capacity) { if (capacity < size) { throw std::exception(); } array = new heap_timer*[capacity]; // 创建堆数组 if (!array) { throw std::exception(); } for(int i = 0; i < capacity; ++i) { array[i] = NULL; } if (size != 0) { // 初始化堆数组 for (int i = 0; i < size; ++i) { array[i] = init_array[i]; } for (int i = (cur_size-1)/2; i >= 0; --i) { percolate_down(i); } } } // 销毁时间堆 ~time_heap() { for (int i = 0; i < cur_size; ++i) { delete array[i]; } delete[] array; } public: // 添加目标定时器timer void add_timer(heap_timer* timer) throw (std::exception) { if (!timer) { return; } // 如果当前堆数组容量不够,将其扩大一倍 if (cur_size >= capacity) { resize(); } // 新插入一个元素,当前堆大小增加1,hole是新建空穴的位置 int hole = cur_size++; int parent = 0; // 堆从空穴到根节点的路径上的所有结点执行上虑操作 for (; hole > 0; hole = parent) { parent = (hole-1) / 2; if (array[parent]->expire <= timer->expire) { break; } array[hole] = array[parent]; } array[hole] = timer; } // 删除目标定时器timer void del_timer(heap_timer* timer) { if (!tiemr) { return; } // 仅仅将目标定时器的回调函数设置为空,即所谓的延迟销毁 // 这将节省真正删除该定时器造成的开销,但这样做也容易使堆数组膨胀 timer->cb_func = NULL; } // 获得堆顶部的定时器 heap_timer* top() const { if (empty()) { return NULL; } return array[0]; } // 删除堆顶部的定时器 void pop_timer() { if (empty()) { return; } if (array[0]) { delete array[0]; // 将原来的堆顶元素替换为堆数组中的最后一个元素 array[0] = array[--cur_size]; percolate_down(0); // 对新的堆顶元素执行下虑操作 } } void tick() { heap_timer* tmp = array[0]; time_t cur = time(NULL); while(!empty()) { if (!tmp) { break; } // 如果堆顶定时器没过期,退出循环 if (tmp->expire > cur) { break; } // 否则执行堆顶定时器中的任务 if (array[0]->cb_func) { array[0]->cb_func(array[0]->user_data); } // 将堆顶元素删除,同时生成新的堆顶定时器 pop_timer(); tmp = array[0]; } } bool empty() const { return cur_size == 0}; private: void percolate_down(int hole) { heap_timer* tmp = array[hole]; int child = 0; for (; ((hole*2+1) <= (cur_size-1)); hole = child) { child = hole*2 + 1; if ((child < (cur_size - 1)) && (array[child+1]->expire < array[child]->expire)) { ++child; } if (array[child]->expire < temp->expire) { array[hole] = array[child]; } else { break; } } array[hole] = temp; } // 将堆数组容量扩大1倍 void resize() throw (std::exception) { heap_timer** temp = new heap_timer*[2*capacity]; for(int i = 0; i < 2*capacity; ++i) { temp[i] = NULL; } if (!temp) { throw std::exception(); } capacity = 2*capacity; for(int i = 0; i < cur_size; ++i) { temp[i] = array[i]; } delete[] array; array = temp; } private: heap_timer** array; // 堆数组 int capacity; // 堆数组的容量 int cur_size; // 堆数组当前包含元素的个数 }; #endif |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ Linux_ 命令大全 文档编辑03/16
- ♥ Linux 高性能服务器编程：网络基础编程一11/27
- ♥ 各平台调试方法总结记述一09/25
- ♥ Linux_命令大全 压缩备份03/16
- ♥ Linux下网络及其他配置相关记述08/12
- ♥ 包管理器：各平台安装卸载相关记述09/17