高效定时器设计方案——层级时间轮

2024-05-24 04:52

本文主要是介绍高效定时器设计方案——层级时间轮,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

层级时间轮实现高性能定时器

此篇介绍时间轮,它的时间复杂度是最优的,插入、查找(最小)、删除都是O(1),很恐怖的性能

这里示例一个三层时间轮,模拟时钟表盘的运作方式,便于理解且性能不低

设计思路:

1.根据定时任务的超时时间,按超时时间范围存入不同的链表中,处于同一个链表的任务的超时时间范围相同但无序

2.每一个槽中放入一个链表,可以通过槽访问链表的头尾节点

3.定时任务是否超时的判断依据是,定时任务从创建到即将执行这一过程中,定时器的内部时间time的增长是否大于任务的超时时间,也就是说,在定时器里有内部时间概念,这个时间是由函数调用手动递增的,而不是系统时间

这是定时器以及定时任务的结构

struct timer_node {struct timer_node *next;uint32_t expire;handler_pt callback;uint8_t cancel;
};typedef struct link_list {timer_node_t head;timer_node_t *tail;
} link_list_t;typedef struct timer {link_list_t second[SECONDS]; // 秒槽link_list_t minute[MINUTES]; // 分钟槽link_list_t hour[HOURS]; // 小时槽spinklock_t lock;uint32_t time;time_t current_point;       
} timer_st;

对于一个定时任务 timer_node

1.首先它是一个链表,所以需要next指针

2.expire是自定义的超时时间,这个时间概念是由定时器维护的

3.callback,该定时任务所执行的函数

对于一个定时器 timer

1.second[SECONDS];这是一个结构体数组,数组的每一位存储着一个link_list链表,这个链表存储着一些定时任务节点,根据命名可以看出,SECONDS = 60,

示例:超时时间为1秒的任务存放在second[1]链表中,超时时间为59秒的任务存放在second[59]链表中,此时如果有两个超时时间为2秒的任务,那么它们都将存放在second[2]链表中

2.minute[MINUTES];分钟槽,这里存放着超时时间范围在(1,60]分钟的定时任务

示例:超时时间为65秒和90秒的定时任务都将存放在minute[1]链表中,因为它们都属于60-120s这个时间范围

3.time,这就是定时器维护的内部时间了,一般初始化为0,代表第0秒,在时间轮运行时,会有函数将它递增,因此它区别于系统时间每秒+1,它的秒数增长频率是不固定的

4.time_t current_point;这是一个time_t类型的变量,用于保存一个系统时间,在时间轮中用于time增长的参考

接下来介绍几个核心的函数:

1.添加定时任务:

static void add_node(timer_st *T, timer_node_t *node) {uint32_t time = node->expire;uint32_t current_time = T->time;uint32_t mesc = time - current_time;if (mesc < ONE_MINUTE) {link_to(&T->second[time % SECONDS], node);} else if (mesc < ONE_HOUR) {link_to(&T->minute[(uint32_t)(time/ONE_MINUTE) % MINUTES], node);} else {link_to(&T->hour[(uint32_t)(time/ONE_HOUR) % HOURS], node);}
}timer_node_t *add_timer(int time, handler_pt func) {timer_node_t *node = (timer_node_t *)malloc(sizeof(*node));spinlock_lock(&TI->lock);node->expire = time + TI->time;ptinrf("add timer at %u, expire at %u, now_time at %lu\n", TI->time, node->expire, now_time());node->callback = func;node->cancel = 0;if (time <= 0) {spinlock_unlock(&TI-> lock);node->callback(node);free(node);return NULL;}add_node(TI, node);spinlock_unlock(&TI->lock);return node;
}

逻辑:

1.先根据任务指定的expire确定超时时间点,为expire(超时时间) + TI->time(定时器当前时间)

  1. 设置任务的回调函数(非重点)

  2. 根据超时时间点,将该定时任务添加到正确的时间轮槽中:

    static void add_node(timer_st *T, timer_node_t *node) {uint32_t time = node->expire;  // 相对超时时间uint32_t current_time = T->time;  // 当前的定时器事件uint32_t mesc = time - current_time; // 多少秒后超时(绝对超时时间)if (mesc < ONE_MINUTE) { // 绝对超时时间小于一分钟link_to(&T->second[time % SECONDS], node); // 添加到秒槽中} else if (mesc < ONE_HOUR) { // 大于一分钟,小于60分钟link_to(&T->minute[(uint32_t)(time/ONE_MINUTE) % MINUTES], node);// 添加到分钟槽中} else { // 添加到小时槽中link_to(&T->hour[(uint32_t)(time/ONE_HOUR) % HOURS], node);}
    }
    

重点中的重点

相信你注意到了add_node函数中的**mesc = time - current_time;**,由于定时器的时间推进,一个定时任务的绝对超时时间会随之减少,会导致在某一(定时器)时刻,一些定时任务的位置变得不正确,例如一个65秒的定时任务,在10秒后仍未得到处理,那么它此时的绝对超时时间是55秒,这时,它应该由原来所在的minute分钟槽移动到second秒槽中

由于这种情况会普遍发生,我们需要利用额外的函数处理这些需要重新换槽的任务——remap函数

remap()// 重新映射

remap要做的很简单:将一个槽中的全部或部分节点搬到另一个或几个槽中,简洁的操作是:先将原槽清空,再为这些节点重新匹配合适的槽,这就叫做重新映射

static void remap(timer_st *T, link_list_t *level, int idx) {timer_node_t *current = link_clear(&level[idx]); // 清空当前槽while (current) {  // 将槽中的节点全部重新映射到新槽timer_node_t *temp = current->next;add_node(T, current); // 核心操作,重新匹配并添加到槽中current = temp;}
}

时间轮的推进—定时器内部时间增长

static void
timer_shift(timer_st *T) {uint32_t ct = ++T->time % HALF_DAY;  //  定时器内部时间 + 1秒if (ct % SECONDS == 0) {     // 当前时间为整分钟// 每分钟重新分配一次uint32_t minute_idx = (ct / ONE_MINUTE) % MINUTES;if (minute_idx != 0) {  // 当前时间是整分钟remap(T, T->minute, minute_idx);}// 每小时重新分配一次if (ct % ONE_HOUR == 0) {uint32_t hour_idx = (ct / ONE_HOUR) % HOURS;remap(T, T->hour, hour_idx);}}
}

每推进一秒定时器时间,判断一次是否需要重新分配分钟槽或小时槽

1.每一分钟remap一次分钟槽到秒槽,因为每过一分钟,大于一分钟小于两分钟的任务的绝对超时时间会变为一分钟内

2.每小时remap一次小时槽到分钟槽中,因为每过一小时,大一小时小于两小时的任务的绝对时间会变为一小时内

执行定时任务:

static void timer_execute(timer_st *T) {uint32_t idx = T->time % SECONDS;   // 每一次执行最小时间单位槽-->秒 中的定时器任务while (T->second[idx].head.next) {timer_node_t *current = link_clear(&T->second[idx]);spinklock_unlock(&T->lock);dispatch_list(current);spinlock_lock(&T->lock);}
}static void dispath_list(timer_node_t *current) {do {timer_node_t * temp = current;current = current->next;if (temp->cancel == 0)temp->callback(temp);free(temp);} while (current);
}

每次执行一个槽中链表的所有任务,任务执行后会被移除

值得注意的是

每次只执行秒槽中的任务,因为这是定时器的最小执行精度,并且分钟槽和小时槽中的任务最终也会随定时器的时间推进而重新映射到秒槽中

运行定时器

static void timer_update(timer_st *T) {spinlock_lock(&T->lock);timer_execute(T); // 执行一个秒槽中的任务timer_shift(T);  // 推进定时器内部时间timer_execute(T); spinlock_unlock(&T->lock);
}void check_timer(int *stop) {  //  同步系统时间和定时器的当前时间while (*stop == 0) {    time_t cp = now_time();   // 获取系统当前时间if (cp != TI->current_point) {  // 当前系统时间于上一次获取的系统时间的对比uint32_t diff = (uint32_t)(cp - TI->current_point); // 当前系统时间于上一次获取的系统时间的时间差TI->current_point = cp;  // 更新定时器内暂存的系统时间int i;for (i = 0; i < diff; i++) {  // 推进定时器,补偿时间差timer_update(TI);  // 推动定时器时间增长、处理任务}}usleep(200000); // 循环运行间隔}
}

推荐学习 https://xxetb.xetslk.com/s/p5Ibb

这篇关于高效定时器设计方案——层级时间轮的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/997428

相关文章

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

基于 YOLOv5 的积水检测系统:打造高效智能的智慧城市应用

在城市发展中,积水问题日益严重,特别是在大雨过后,积水往往会影响交通甚至威胁人们的安全。通过现代计算机视觉技术,我们能够智能化地检测和识别积水区域,减少潜在危险。本文将介绍如何使用 YOLOv5 和 PyQt5 搭建一个积水检测系统,结合深度学习和直观的图形界面,为用户提供高效的解决方案。 源码地址: PyQt5+YoloV5 实现积水检测系统 预览: 项目背景

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

批处理以当前时间为文件名创建文件

批处理以当前时间为文件名创建文件 批处理创建空文件 有时候,需要创建以当前时间命名的文件,手动输入当然可以,但是有更省心的方法吗? 假设我是 windows 操作系统,打开命令行。 输入以下命令试试: echo %date:~0,4%_%date:~5,2%_%date:~8,2%_%time:~0,2%_%time:~3,2%_%time:~6,2% 输出类似: 2019_06

利用命令模式构建高效的手游后端架构

在现代手游开发中,后端架构的设计对于支持高并发、快速迭代和复杂游戏逻辑至关重要。命令模式作为一种行为设计模式,可以有效地解耦请求的发起者与接收者,提升系统的可维护性和扩展性。本文将深入探讨如何利用命令模式构建一个强大且灵活的手游后端架构。 1. 命令模式的概念与优势 命令模式通过将请求封装为对象,使得请求的发起者和接收者之间的耦合度降低。这种模式的主要优势包括: 解耦请求发起者与处理者

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR(重复时间,repetition time)是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言,TR 是施加一个 RF(射频)脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位,主要控制后续脉冲之前的纵向弛豫程度(T1 弛豫),使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)