高性能定时器策略之时间轮定时器算法
toyiye 2024-09-16 06:11 3 浏览 0 评论
时间轮定时器是有多个时间槽(slot)组成,每个时间槽代表时间的基本跨度。类似于一个时钟,时钟指针以恒定的速度每往下走一步,代表一个时间跨度。
时间槽的个数是固定的,用SN(Slot Num)表示,每转动一次可称为一个滴答(tick),所以转动一周也就需要个SN滴答。每一个滴答需要的槽间间隔为SI(Slot Interval),则转一周也就共需要(SN * SI)时间单位。
时间轮的每个槽都指向一个定时器链表,每个链表的定时器都有一个相同的特性:相差(SN * SI)的整数倍,也即是一周的整数倍。正是由于时间轮有这样的特性,所以可以根据定时器的触发时间和时间轮的槽数,把定时器hash到对应的链表上。
一个简单的时间轮如下图:
比如我们要插入一个超时时间为TI的定时器,那么计算器应该插入到槽对应的链表的方式如下:
TS = ( CS + (TI / SI) ) % SN
CS 代表当前的槽位,因为时间轮定时器不停的在走。
时间轮采用的是hash的思想,把各个定时器分散到不同槽的链表中,这个避免了单个链表的过长,提高了效率。
从上面的公式可以看出,对时间轮而言,当SI 越小的时候,定时器的精度就越高;当SN槽数越多时,效率越高,因为定时器被分配到不同的链表中,链表的长度也就相对短了,提高了遍历效率。
下面实现一个简单的时间轮,代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <sys/epoll.h>
#include <arpa/inet.h>
#include <time.h>
#define BUFFER_SIZE 64 //缓冲区长度
#define SLOTS_NUM 60 //时间轮上槽的数目
//结构体声明
typedef struct tw_timer tw_timer;
typedef struct client_date client_date;
/* EPOLL回调函数*/
typedef void (*epoll_ callback_ t)(int, int);
struct tw_timer{
int rotation; //记录定时器在时间轮上转多少圈后触发
int time_slot; //记录定时器属于时间轮上的槽位(对应的链表)
void (*cb_func)(client_date *); //定时器回调函数
client_date *user_date; //client数据
tw_timer *prev; //指向前一个定时器
tw_timer *next ; //指向下一个定时器
};
//用户数据
struct client_date{
int sockfd;
char buf[BUFFER_SIZE];
tw_timer *time;
};
//每1秒时间轮转动一次,也即是槽间隔为1秒
static const int SI = 1;
//时间轮的槽, 其中每个元素指向一个定时器链表,链表无序
tw_timer *slots[SLOTS_NUM];
//事件的当前槽
int cur_slot = 0;
tw_timer * malloc_tw_timer(int rotation, int time_slot)
{
tw_timer *timer = (tw timer *)malloc(sizeof(tw_timer));
memset(timer, 0, sizeof(tw_timer));
timer->rotation = rotation;
timer->time_slot = time_slot;
timer->prev = NULL ;
timer->next = NULL ;
timer->cb_func = NULL ;
timer->user_date = NULL;
return timer;
}
void* free_tw_timer(tw_timer *timer)
{
if(NULL == timer)
return NULL;
if(NULL != timer->user_date)
free(timer->user_date);
free(timer);
}
void time_wheel()
{
int i = 0;
for(i = 0; i < SLOTS_NUM; i++)
slots[i] = NULL;
}
//遍历每个槽,销毁定时器
void del_time_wheel()
{
int i = 0;
for(i = 0; i < SLOTS_NUM; i++)
{
tw_timer *tmp = slots[i];
while(tmp)
{
slots[i] = tmp->next;
free_tw_timer(tmp);
tmp = slots[i];
}
}
}
/*根据定时器timeout创建一 个定时器,并把它插入到一个合适的槽中*/
tw_timer * add_timer(int timeout)
{
if(timeout < 0)
return NULL;
int ticks = 0;
/*待插入的超时时间小于时间轮的槽间隔SI,则将ticks向 上调整为1,
否则将ticks向下调整为 timeout/SI
*/
if(timeout < SI)
{
ticks = 1;
}
else
{
ticks = timeout / SI;
}
//计算待插入的定时器在时间轮转动多少圈后被触发
int rotation = ticks / SLOTS_NUM;
//计算待插入的定时器应该被插入到哪个槽中
int ts = (cur_slot + (ticks % SLOTS_NUM)) % SLOTS_NUM;
//创建新的定时器,它在时间轮转动rotation圈后被触发
tw_timer *timer = malloc_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 //否则,将定时器插入其中
{
printf("slots[%d] is not null\n", 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;
}
}
else
{
timer->prev->next = timer->next;
if(timer->next)
{
timer->next->prev = timer->prev;
}
}
free_tw_timer(timer);
}
//SI 时间到后,调用该函数, 时间轮向前滚动一个槽的间隔
void tick()
{
tw_timer *tmp = slots[cur_slot];
//遍历该槽对应链表的所有定时器,查看是否触发
while(tmp)
{
if(tmp->rotation > 0)
{
tmp->rotation--;
tmp = tmp->next;
}
else //到期,执行任务
{
tmp->cb_func(tmp->user_date);
if(tmp == slots[cur_slot])
{
printf("delete head in cur_slot, cur_slot %d\n", cur_slot);
slots[cur_slot] = tmp->next;
free_tw_timer(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;
free_tw_timer(tmp);
tmp = tmp2;
}
}
}
//更新时间轮的当前槽,以反映时间轮的转数
cur_slot = ++cur_slot % SLOTS_NUM;
}
测试如下
int total = 0; //记录1s定时器触发次数
void test (client_date *cd)
{
printf("total = %d\n", total);
}
void test_add_timer(int timeout, void (*cb_func)(client_date *))
{
tw_timer * timer;
timer = add_timer(timeout);
timer->cb_func = cb_func;
}
void test_crete_timer()
{
//创建一一个2秒5秒10秒70秒, 85秒的定时器
test_add_timer(2, test);
test_add_timer(5, test);
test_add_timer(10, test);
test_add_timer(70, test);
test_add_timer(85, test);
time_t now ;
struct tm *tm_now ;
time(&now) ;
tm_now = localtime(&now) ;
printf("test_crete_timer datetime: %d-%d-%d %d:%d:%d\n", tm_now->tm_year+1900,
tm_now->tm_mon+1, tm_now->tm_mday, tm_now->tm_hour, tm_now->tm_min, tm_now->tm_sec);
}
//保存触发定时器相应的fd和回调,在该回调中进行遍历时间轮
typedef struct epoll_callback_info
{
int iFd;
epoll_callback_t pfEpollCallBack;
}epoll_callback_info;
//创建一个触发定时器
int createTimer(long lMSec, int epfd, epoll_callback_t pfEpollCallback)
{
struct itimerspece stTimer;
struct epoll_event event;
int timerfd;
int iSec = (int)(lMSec/1000);
int ret = -1;
memset(&event, 0, sizeof(event));
event.events = EPOLLIN | EPOLLHUP | EPOLLERR;
memset(&stTimer, 0, sizeof(stTimer));
stTimer.it_value.tv_sec = iSec;
stTimer.it_value.tv_nsec = (lMSec%1000)*1000000;
stTimer.it_interval.tv_sec = iSec;
stTimer.it_interval.tv_nsec = (lMSec%1000)*1000000;
timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
if(-1 != timerfd)
{
if(0 == timerfd_settime(timerfd, 0, &stTimer, NULL))
{
epoll_callback_info *p = malloc(sizeof(epoll_callback_info));
p->iFd = timerfd;
p->pfEpollCallback = pfEpollCallback;
event.data.ptr = p;
ret = epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &event);
}
else
{
printf("timerfd_settime Failed");
}
/*定时器时间设定或添加epoll错误时,释放资源*/
if(0 != ret)
{
printf("add to epoll failed or set time failed");
close(timerfd);
timerfd = -1;
}
}
else
{
printf("create timerfd failed");
}
return timerfd;
}
void timer_read_timerFd(int timerfd)
{
uint64_t exp;
(void)read(timerfd, &exp, sizeof(uint64_t));
total++;
return;
}
//epoll上定时器回调,每触发一次则调用一次tick()
void commomTimerCB(int uiEvent, int iTimeFd)
{
timer_read_timerFd(iTimeFd);
tick();
}
int main()
{
struct epoll_event wait_event[100];
int epfd;
int timerfd;
epoll_callback_t pfEpllCallback;
int i = 0;
struct itimerspece stTimer;
long lMSec = 1000; //1s定时器时间
int count;
epfd = epoll_create(1);
if(-1 == epfd)
{
printf("epoll create error\n");
return -1;
}
printf("create epoll fd: %d\n", epfd);
time_wheel();
test_create_timer();
timerfd = createTimer(lMSec, epfd, (epoll_callback_t)commomTimerCB);
if(-1 == timerfd)
{
printf("failed to create timer");
return -1;
}
for(;;)
{
waitfds = epoll_wait(epfd, wait_event, 100, -1);
printf("count %d\n", count++);
for(i = 0; i < waitfds; i++)
{
epoll_callback_info *t = (epoll_callback_info*)wait_event[i].data.ptr;
pfEpllCallback = (epoll_callback_t)(unsigned long)t->pfEpllCallback;
pfEpllCallback(wait_event[i].events, t->iFd);
}
}
return 0;
}
相关推荐
- 为何越来越多的编程语言使用JSON(为什么编程)
-
JSON是JavascriptObjectNotation的缩写,意思是Javascript对象表示法,是一种易于人类阅读和对编程友好的文本数据传递方法,是JavaScript语言规范定义的一个子...
- 何时在数据库中使用 JSON(数据库用json格式存储)
-
在本文中,您将了解何时应考虑将JSON数据类型添加到表中以及何时应避免使用它们。每天?分享?最新?软件?开发?,Devops,敏捷?,测试?以及?项目?管理?最新?,最热门?的?文章?,每天?花?...
- MySQL 从零开始:05 数据类型(mysql数据类型有哪些,并举例)
-
前面的讲解中已经接触到了表的创建,表的创建是对字段的声明,比如:上述语句声明了字段的名称、类型、所占空间、默认值和是否可以为空等信息。其中的int、varchar、char和decimal都...
- JSON对象花样进阶(json格式对象)
-
一、引言在现代Web开发中,JSON(JavaScriptObjectNotation)已经成为数据交换的标准格式。无论是从前端向后端发送数据,还是从后端接收数据,JSON都是不可或缺的一部分。...
- 深入理解 JSON 和 Form-data(json和formdata提交区别)
-
在讨论现代网络开发与API设计的语境下,理解客户端和服务器间如何有效且可靠地交换数据变得尤为关键。这里,特别值得关注的是两种主流数据格式:...
- JSON 语法(json 语法 priority)
-
JSON语法是JavaScript语法的子集。JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔花括号保存对象方括号保存数组JS...
- JSON语法详解(json的语法规则)
-
JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔大括号保存对象中括号保存数组注意:json的key是字符串,且必须是双引号,不能是单引号...
- MySQL JSON数据类型操作(mysql的json)
-
概述mysql自5.7.8版本开始,就支持了json结构的数据存储和查询,这表明了mysql也在不断的学习和增加nosql数据库的有点。但mysql毕竟是关系型数据库,在处理json这种非结构化的数据...
- JSON的数据模式(json数据格式示例)
-
像XML模式一样,JSON数据格式也有Schema,这是一个基于JSON格式的规范。JSON模式也以JSON格式编写。它用于验证JSON数据。JSON模式示例以下代码显示了基本的JSON模式。{"...
- 前端学习——JSON格式详解(后端json格式)
-
JSON(JavaScriptObjectNotation)是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScriptProgrammingLa...
- 什么是 JSON:详解 JSON 及其优势(什么叫json)
-
现在程序员还有谁不知道JSON吗?无论对于前端还是后端,JSON都是一种常见的数据格式。那么JSON到底是什么呢?JSON的定义...
- PostgreSQL JSON 类型:处理结构化数据
-
PostgreSQL提供JSON类型,以存储结构化数据。JSON是一种开放的数据格式,可用于存储各种类型的值。什么是JSON类型?JSON类型表示JSON(JavaScriptO...
- JavaScript:JSON、三种包装类(javascript 包)
-
JOSN:我们希望可以将一个对象在不同的语言中进行传递,以达到通信的目的,最佳方式就是将一个对象转换为字符串的形式JSON(JavaScriptObjectNotation)-JS的对象表示法...
- Python数据分析 只要1分钟 教你玩转JSON 全程干货
-
Json简介:Json,全名JavaScriptObjectNotation,JSON(JavaScriptObjectNotation(记号、标记))是一种轻量级的数据交换格式。它基于J...
- 比较一下JSON与XML两种数据格式?(json和xml哪个好)
-
JSON(JavaScriptObjectNotation)和XML(eXtensibleMarkupLanguage)是在日常开发中比较常用的两种数据格式,它们主要的作用就是用来进行数据的传...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- r语言矩阵 (127)
- browsererror (114)
- exportexcel (119)
- cv2.bitwise_not (137)
- dump命令 (128)
- es6concat (126)
- heapify (127)
- java.security.egd (130)
- javax.annotation (117)
- jsstringsplit (117)
- js数字 (115)
- maven编译 (132)
- mysqlleft (128)
- nodejsbuffer (149)
- org.apache.commons.httpclient (126)
- org.jsoup (141)
- org.springframework.web (128)
- robotframework-ride (115)
- setnocounton (141)
- socket.gethostbyname (122)
- sqlmid (121)
- time.strptime (133)
- vscode格式化 (125)
- win32con (129)
- window.localstorage (126)