定时器两种实现方式
第一种：网络事件和时间事件在一个线程当中处理，例如nginx,redis（无序单链表）
while (!quit) {
int now = get_now_time();// 单位：ms
int timeout = get_nearest_timer() - now;
if (timeout < 0) timeout = 0;
int nevent = epoll_wait(epfd, ev, nev, timeout);
for (int i=0; i<nevent; i++) {
//... ?络事件处理
}
update_timer(); // 时间事件处理
}
第二种：网络事件和时间事件在不同的线程当中处理，例如skynet
//在其他线程添加定时器任务
void* thread_timer(viud* arg)
{
init_timer();
while(!quit){
update_timer();//定时器任务触发的时候，就放到消息队列中
sleep(t);
}
clear_timer();
return NULL;
}
定时器设计
接口设计
//初始化定时器,就是初始化一些数据结构
void init_timer();
数据结构选择
1.红黑树(平衡二叉搜索树)
- 定义：采用中序遍历的时候是一个有序的结构，大量删除的时候容易退化成单链表搜索效率会变成O(n)，所以红黑树的黑节点的高度要一致。
- 对于增删查，时间复杂度为O(log2n )
代码实现：
/*
* Copyright (C) Igor Sysoev
* Copyright (C) Nginx, Inc.
*/
#ifndef _NGX_RBTREE_H_INCLUDED_
#define _NGX_RBTREE_H_INCLUDED_
typedef unsigned int ngx_rbtree_key_t;
typedef unsigned int ngx_uint_t;
typedef int ngx_rbtree_key_int_t;
typedef unsigned char u_char;
#ifndef NULL
#define NULL ((void*)0)
#endif
typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;
struct ngx_rbtree_node_s {
ngx_rbtree_key_t key;
ngx_rbtree_node_t *left;
ngx_rbtree_node_t *right;
ngx_rbtree_node_t *parent;
u_char color;
u_char data;
};
typedef struct ngx_rbtree_s ngx_rbtree_t;
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
struct ngx_rbtree_s {
ngx_rbtree_node_t *root;
ngx_rbtree_node_t *sentinel;
ngx_rbtree_insert_pt insert;
};
#define ngx_rbtree_init(tree, s, i) \
ngx_rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i
void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void
ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel);
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree,
ngx_rbtree_node_t *node);
#define ngx_rbt_red(node) ((node)->color = 1)
#define ngx_rbt_black(node) ((node)->color = 0)
#define ngx_rbt_is_red(node) ((node)->color)
#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
/* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
static ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
while (node->left != sentinel) {
node = node->left;
}
return node;
}
#endif /* _NGX_RBTREE_H_INCLUDED_ */
/*
* Copyright (C) Igor Sysoev
* Copyright (C) Nginx, Inc.
*/
#include "rbtree.h"
/*
* The red-black tree code is based on the algorithm described in
* the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
*/
static inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
static inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t **root, *temp, *sentinel;
/* a binary tree insert */
root = &tree->root;
sentinel = tree->sentinel;
if (*root == sentinel) {
node->parent = NULL;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_black(node);
*root = node;
return;
}
tree->insert(*root, node, sentinel);
/* re-balance tree */
while (node != *root && ngx_rbt_is_red(node->parent)) {
if (node->parent == node->parent->parent->left) {
temp = node->parent->parent->right;
if (ngx_rbt_is_red(temp)) {
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->right) {
node = node->parent;
ngx_rbtree_left_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
}
} else {
temp = node->parent->parent->left;
if (ngx_rbt_is_red(temp)) {
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
ngx_rbtree_right_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
}
}
}
ngx_rbt_black(*root);
}
void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel)
{
ngx_rbtree_node_t **p;
for ( ;; ) {
p = (node->key < temp->key) ? &temp->left : &temp->right;
if (*p == sentinel) {
break;
}
temp = *p;
}
*p = node;
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_red(node);
}
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel)
{
ngx_rbtree_node_t **p;
for ( ;; ) {
/*
* Timer values
* 1) are spread in small range, usually several minutes,
* 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
* The comparison takes into account that overflow.
*/
/* node->key < temp->key */
p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
? &temp->left : &temp->right;
if (*p == sentinel) {
break;
}
temp = *p;
}
*p = node;
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_red(node);
}
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_uint_t red;
ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
/* a binary tree delete */
root = &tree->root;
sentinel = tree->sentinel;
if (node->left == sentinel) {
temp = node->right;
subst = node;
} else if (node->right == sentinel) {
temp = node->left;
subst = node;
} else {
subst = ngx_rbtree_min(node->right, sentinel);
if (subst->left != sentinel) {
temp = subst->left;
} else {
temp = subst->right;
}
}
if (subst == *root) {
*root = temp;
ngx_rbt_black(temp);
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
return;
}
red = ngx_rbt_is_red(subst);
if (subst == subst->parent->left) {
subst->parent->left = temp;
} else {
subst->parent->right = temp;
}
if (subst == node) {
temp->parent = subst->parent;
} else {
if (subst->parent == node) {
temp->parent = subst;
} else {
temp->parent = subst->parent;
}
subst->left = node->left;
subst->right = node->right;
subst->parent = node->parent;
ngx_rbt_copy_color(subst, node);
if (node == *root) {
*root = subst;
} else {
if (node == node->parent->left) {
node->parent->left = subst;
} else {
node->parent->right = subst;
}
}
if (subst->left != sentinel) {
subst->left->parent = subst;
}
if (subst->right != sentinel) {
subst->right->parent = subst;
}
}
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
if (red) {
return;
}
/* a delete fixup */
while (temp != *root && ngx_rbt_is_black(temp)) {
if (temp == temp->parent->left) {
w = temp->parent->right;
if (ngx_rbt_is_red(w)) {
ngx_rbt_black(w);
ngx_rbt_red(temp->parent);
ngx_rbtree_left_rotate(root, sentinel, temp->parent);
w = temp->parent->right;
}
if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
ngx_rbt_red(w);
temp = temp->parent;
} else {
if (ngx_rbt_is_black(w->right)) {
ngx_rbt_black(w->left);
ngx_rbt_red(w);
ngx_rbtree_right_rotate(root, sentinel, w);
w = temp->parent->right;
}
ngx_rbt_copy_color(w, temp->parent);
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->right);
ngx_rbtree_left_rotate(root, sentinel, temp->parent);
temp = *root;
}
} else {
w = temp->parent->left;
if (ngx_rbt_is_red(w)) {
ngx_rbt_black(w);
ngx_rbt_red(temp->parent);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
w = temp->parent->left;
}
if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
ngx_rbt_red(w);
temp = temp->parent;
} else {
if (ngx_rbt_is_black(w->left)) {
ngx_rbt_black(w->right);
ngx_rbt_red(w);
ngx_rbtree_left_rotate(root, sentinel, w);
w = temp->parent->left;
}
ngx_rbt_copy_color(w, temp->parent);
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->left);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
temp = *root;
}
}
}
ngx_rbt_black(temp);
}
static inline void
ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t *temp;
temp = node->right;
node->right = temp->left;
if (temp->left != sentinel) {
temp->left->parent = node;
}
temp->parent = node->parent;
if (node == *root) {
*root = temp;
} else if (node == node->parent->left) {
node->parent->left = temp;
} else {
node->parent->right = temp;
}
temp->left = node;
node->parent = temp;
}
static inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t *temp;
temp = node->left;
node->left = temp->right;
if (temp->right != sentinel) {
temp->right->parent = node;
}
temp->parent = node->parent;
if (node == *root) {
*root = temp;
} else if (node == node->parent->right) {
node->parent->right = temp;
} else {
node->parent->left = temp;
}
temp->right = node;
node->parent = temp;
}
ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t *root, *sentinel, *parent;
sentinel = tree->sentinel;
if (node->right != sentinel) {
return ngx_rbtree_min(node->right, sentinel);
}
root = tree->root;
for ( ;; ) {
parent = node->parent;
if (node == root) {
return NULL;
}
if (node == parent->left) {
return parent;
}
node = parent;
}
}
红黑树的方法由于自己没有实现，就直接将代码贴在这里，以后再钻研。
2.最小堆
-
定义：
满二叉树：所有层的节点数都是该层能容纳的最大数量
完全二叉树：若二叉树深度为h，除了h层外，其它层节点数都是该层所能容纳节点的最大数，且h层都集中在最左侧。
最小堆：
? 1.是一颗完全二叉树
? 2.某一个节点的值总是小于等于它的子节点的值（限定父子节点的关系，左右子节点的关系没有限定）
? 3.堆中每个子节点的子树都是最小堆
-
增加操作时间复杂度O(log2n)，删除操作时间复杂度O(n)。
思路：往堆上添加节点删除节点，维护小根堆。此时堆顶就是即将执行的第一个任务，在执行任务的时候，从堆顶开始，判断时间是否到了，执行回调函数。删除堆顶，调整堆结构，再执行堆顶直到任务时间未到的节点退出此次执行。
维护堆，就是下沉或者上升操作，熟悉堆操作即可
代码实现：
#ifndef __HEAD_HPP__
#define __HEAD_HPP__
#include<vector>
#include<map>
using std::vector;
using std::map;
typedef void(*TimerHandler)(struct TimerNode* node);
struct TimerNode{
int idx;//索引
int id;
unsigned int expire;//任务时限
TimerHandler cb;//函数指针
};
class MinHeapTimer{
public:
MinHeapTimer()
{
_heap.clear();
_map.clear();
}
static inline int Count() {
return ++_count;
}
int AddTimer(uint32_t expire,TimerHandler cb);//传入超时时间和执行函数
bool DelTimer(int id);
void ExpireTimer();//执行到期任务
private:
inline bool _lessThan(int lhs,int rhs){//比较
return _heap[lhs]->expire < _heap[rhs]->expire;
}
void _shiftUp(int pos);//上升操作
bool _shiftDown(int pos);//下降操作
void _delNode(TimerNode* node);//删除节点
private:
vector<TimerNode*> _heap;//堆
map<int,TimerNode*> _map;//便于定位节点进行删除
static int _count;
};
int MinHeapTimer::_count = 0;
#endif
#include"head.hpp"
#include<time.h>
#include<sys/time.h>
#include<unistd.h>
#include<iostream>
uint64_t current_time(){//当前时间
uint32_t t;
#if 0
struct timespec spc;
clock_gettime(CLOCK_MONOTONIC,&spc);
t = spc.tv_sec * 1000;
t += spc.tv_nsec / 1000000;
#else
struct timeval tv;
gettimeofday(&tv,nullptr);
t = (uint32_t)tv.tv_sec * 1000;
t += tv.tv_usec / 1000;
#endif
return t;
}
int MinHeapTimer::AddTimer(uint32_t expire,TimerHandler cb){
int64_t timeout = current_time() + expire;
TimerNode* node = new TimerNode;
node->cb = cb;
node->id = Count();//map中的位置
node->idx = (int)_heap.size();//先加入到堆的尾部
node->expire = timeout;
_heap.push_back(node);//堆尾
_shiftUp(_heap.size() - 1);//上升操作，维护小根堆
_map.insert(std::make_pair(node->id,node));
return node->id;
}
void MinHeapTimer::_shiftUp(int pos){
for(;;){
int parent = (pos - 1) / 2;
if(!_lessThan(pos,parent) || parent == pos){//已经有序了
break;
}
std::swap(_heap[pos],_heap[parent]);//比父节点小，交换
_heap[parent]->idx = parent;//索引改掉
_heap[pos]->idx = pos;
pos = parent;
}
}
bool MinHeapTimer::_shiftDown(int pos){
int last = (int)_heap.size() - 1;
int idx = pos;
for(;;){
int left = 2 * idx+ 1;
if((left >= last) || (left) < 0){
break;
}
int min = left;//子节点中的小节点
int right = left + 1;
if(right < last && !_lessThan(left,right)){
min = right;
}
if(!_lessThan(min,idx)){//子节点都比父节点大
break;
}
//交换
std::swap(_heap[min],_heap[idx]);
_heap[idx]->idx = idx;
_heap[min]->idx = min;
idx = min;
}
return idx > pos;
}
void MinHeapTimer::ExpireTimer(){
if(_heap.empty()) return;
uint32_t now = current_time();
do{
TimerNode* node = _heap.front();//拿到当前执行的任务
if(now < node->expire){
break;//未到时间
}
for(int i = 0;i < (int)_heap.size();++i){
std::cout << "touch idx: " << _heap[i]->idx
<< " id: " << _heap[i]->id << " expire: "
<< _heap[i]->expire << std::endl;
}
if(node->cb) node->cb(node);
_delNode(node);
}while(!_heap.empty());
}
void MinHeapTimer::_delNode(TimerNode* node)//删除节点
{
int last = (int)_heap.size() - 1;
int idx = node->idx;
if(idx != last){//删除节点后维护小根堆
std::swap(_heap[idx],_heap[last]);
_heap[idx]->idx = idx;
if(!_shiftDown(idx)){
_shiftUp(idx);
}
}
_heap.pop_back();//删除尾节点
_map.erase(node->id);//删除节点
delete node;
}
bool MinHeapTimer::DelTimer(int id){
auto iter = _map.find(id);
if(iter == _map.end()) return false;
_delNode(iter->second);
return true;
}
void print_hello(TimerNode *te) {
std::cout << "hello world time = " << te->idx << "\t" << te->id << std::endl;
}
int main(){
MinHeapTimer mht;
mht.AddTimer(0, print_hello);
mht.AddTimer(1000, print_hello);
mht.AddTimer(7000, print_hello);
mht.AddTimer(2000, print_hello);
mht.AddTimer(9000, print_hello);
mht.AddTimer(10000, print_hello);
mht.AddTimer(6000, print_hello);
mht.AddTimer(3000, print_hello);
for (;;) {
mht.ExpireTimer();
usleep(10000);
}
return 0;
}
运行结果：
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MPnh2wGe-1646235292422)(C:\Users\HASEE\AppData\Roaming\Typora\typora-user-images\image-20220302130038333.png)]](https://img-blog.csdnimg.cn/453f5fd17c0c4955bae78d0dd6f0bc4c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATGl0dGxlX21vbnN0ZXJzXw==,size_10,color_FFFFFF,t_70,g_se,x_16)
时间轮
从时钟表盘出发，如何用数据结构描述
单层时间轮
背景：心跳检测
客户端每5S发送心跳包，服务器若10s内没有收到心跳包，则清除连接
解决办法：
假设使用map<int,conn*>来存储所有连接，每秒检测map结构。那么每秒需要遍历所有的连接，如果map中存了大量的连接，就会做很多无效的检测；考虑极端情况，刚添加进来的连接，下一秒也要检测。实际上只需要10s后驱检测即可。故此考虑时间轮来检测。
设计
1.准备一个数组存储连接数据，那么数组长度是多少？
2.考虑一秒内多个连接，参考hash结构处理冲突，用链表连接起来。
3.如果想2中链表稀疏一些，将数组长度设置大一点；如果想紧凑些，则将数组长度设置小些。
4.假设我们设置数组长度为11；检测指针的移动可描述为++point % 11;优化之后就是m & (n - 1);
5.对于每个连接需要一个计数used，每次接收一个心跳包就++，每检测依次就–，当used == 0，则踢掉连接
代码实现
添加时间任务的函数add_conn()：功能是向当前数组[tick]位置添加任务节点到链表中
检测时间任务的函数check_out()：取出当前数组[tick]位置的链表进行遍历，执行到期任务后销毁
#include<string.h>
#include <unistd.h>
#include<stdint.h>
#include<time.h>
#include <sys/time.h>
#include<stdlib.h>
#include<stdio.h>
#define MAX_TIMER ((1 << 17) - 1)
//数组的长度，时间轮的长度
#define TW_SIZE 16
#define TW_MASK (TW_SIZE - 1)
//超时时间，或者间隔检测时间
#define EXPIRE 10
//最大连接数
#define MAX_CONN ((1 << 16) - 1)
typedef struct conn_node{
uint8_t used;//引用计数
int id;//表示连接fd
}conn_node_t;
typedef struct timer_node{//节点
struct timer_node* next;//链表
struct conn_node* node;//保存连接的信息
uint32_t idx;//表示该节点是否被使用
}timer_node_t;
//依次申请出足够的空间，避免多次malloc
static timer_node_t timer_nodes[MAX_TIMER] = {0};
static conn_node_t conn_nodes[MAX_CONN] = {0};
//两个指针
static uint32_t t_iter = 0;
static uint32_t c_iter = 0;
static uint32_t tick = 0;//计时数
typedef struct link_list{//定时器
timer_node_t head;
timer_node_t *tail;
}link_list_t;
//相当于malloc
timer_node_t* get_timer_node()//没有检测定时任务超多MAX_TIMER的情况
{
t_iter++;
while(timer_nodes[t_iter & MAX_TIMER].idx > 0){//表示该节点被使用，往后遍历
t_iter++;
}
timer_nodes[t_iter].idx = t_iter;
return &timer_nodes[t_iter];
}
void add_conn(link_list_t* tw,conn_node_t* conde,int delay){
//将连接放到数组对应的位置，等待检测
link_list_t* list = &tw[(tick + EXPIRE + delay) & TW_MASK];
timer_node_t* tnode = get_timer_node();//取出已经申请空间的任务节点
conde->used++;
tnode->node = conde;
list->tail->next = tnode;
list->tail = tnode;
tnode->next = NULL;
}
//相当于malloc，取出已经申请好空间的空闲节点
conn_node_t* get_conn_node(){
c_iter++;
while(conn_nodes[c_iter & MAX_CONN].used > 0){//表示节点被使用，往后遍历
c_iter++;
}
return &conn_nodes[c_iter];
}
//得到当前时间
static time_t current_time(){
time_t t;
struct timeval tv;
gettimeofday(&tv,NULL);
t = (time_t)tv.tv_sec;
return t;
}
void link_clear(link_list_t* link){
link->head.next = NULL;
link->tail = &(link->head);
}
void check_conn(link_list_t* tw){
int32_t itick = tick;
tick++;
link_list_t* list = &tw[itick & TW_MASK];//取出当前链表
timer_node_t* current = list->head.next;//当前链表下第一个任务
while(current){
timer_node_t* temp = current;
current = current->next;//提前保存下一个检测的节点
conn_node_t* cn = temp->node;//当前连接
cn->used--;
temp->idx = 0;//idx=0表示被回收
if(cn->used == 0){
printf("fd: %d kill down\n",cn->id);
temp->next = NULL;//回收
}
printf("fd : %d used :%d\n",cn->id,cn->used);
}
link_clear(list);//遍历完该链表后将其回收
}
int main(){
memset(timer_nodes,0,MAX_TIMER * sizeof(timer_node_t));
memset(conn_nodes,0,MAX_CONN * sizeof(conn_node_t));
link_list_t tw[TW_SIZE];
memset(tw,0,TW_SIZE * sizeof(link_list_t));
for(int i = 0;i < TW_SIZE;++i){
link_clear(&tw[i]);
}
{
conn_node_t* node = get_conn_node();
node->id = 10001;
add_conn(tw,node,0);
add_conn(tw,node,5);
}
{
conn_node_t* node = get_conn_node();
node->id = 10002;
add_conn(tw,node,3);
}
{
conn_node_t* node = get_conn_node();
node->id = 10003;
add_conn(tw,node,2);
}
time_t start = current_time();
for(;;){
time_t now = current_time();
if(now - start > 0){
for(int i = 0;i < now - start;++i){
check_conn(tw);
}
start = now;
printf("check conn tick: %d\n",tick);
}
usleep(20000);
}
return 0;
}
运行结果：
---------------------------------------------（以上整理自零声学院课程）