手撕定时器：从零开始

embedded/2024/9/24 20:44:21/

目录

1. 定时器概述

1.1 容器

1.2 检测触发机制

2. 定时任务的执行

2.1 异步执行

2.2 触发时间

2.3 回调函数

3. 定时任务的容器结构

3.1 按触发时间排序的结构

3.1.1 红黑树（如 map、set、multimap、multiset）

3.1.2 最小堆

3.2 按执行序排列的结构：时间轮（Timing Wheel）

4. 检测和触发机制

4.1 基于IO多路复用的检测

4.1.1 阻塞时间

4.1.2 应用实例

4.2 timerfd

4.2.1 将定时任务转化为IO

4.2.2 Workflow

4.3 解决的核心问题

4.3.1 阻塞与调度

4.3.2 内核级检测

5. 定时器的实现

5.1 封装

5.2 实现

5.2.1 容器

5.2.2 检测触发机制

5.3 测试

5.4 优化

5.4.1 针对大量间隔时间相同的任务的优化

5.4.2 拆分思想

 5.5 代码实践

5.5.1 epoll_wait第4个参数驱动

1. 定义基本定时器节点

2. 定义定时器节点

3. 定义比较运算符 

4. 定义定时器类

5. 添加定时器

6. 删除定时器

7. 处理定时器

8. 计算休眠时间

9. ID 生成器

10. 主函数

11. 添加定时任务

12. 删除定时任务

13. 进入事件循环

总结

1. 定时器概述

定时器就像一个小助手，负责管理和安排许多定时任务。它的工作主要依赖于两个核心部分：容器和检测触发机制。

1.1 容器

想象一下，容器就像一个储物箱，里面放着所有的定时任务。一个设计良好的容器可以快速添加、删除或查找任务，确保即使有很多任务在进行，系统依然运行顺畅。

1.2 检测触发机制

这个机制就像一个监视器，负责查看哪些任务快到期了，并及时触发它们。它需要快速准确地找出即将到来的任务，确保它们能优先被处理。

2. 定时任务的执行

定时任务的执行通常是异步的，意思是这些任务不会阻塞其他操作。这样，当任务被触发时，可以高效地执行相关的回调函数，而不影响系统的整体表现。

2.1 异步执行

异步执行让我们的程序在等待任务完成时，依然可以处理其他工作，就像在等朋友时，可以先去喝杯咖啡。

2.2 触发时间

每个任务都有一个触发时间，通常是由当前时间加上一个特定的间隔计算得出的。这样能确保任务在预定的时刻被准确执行。

2.3 回调函数

当定时任务到达触发时间时，就会执行一个预先定义好的回调函数。这个函数可以用来处理数据、发送通知或执行其他重要的业务逻辑。

3. 定时任务的容器结构

选择合适的容器结构存储和管理定时任务，对于定时器的表现至关重要。以下是一些常见的容器结构：

3.1 按触发时间排序的结构

  • 红黑树：一种自平衡的二叉查找树，能够高效地插入、删除和查找任务，非常适合频繁变化的任务列表。

    优点：

    • 动态性强，快速查找即将到期的任务。

    缺点：

    • 可能占用更多内存。

  • 最小堆：一个优先队列，可以在常数时间内找到最早触发的任务。

    优点：

    • 插入和删除操作效率高，快速访问最早任务。

    缺点：

    • 中间元素的查找和删除不够高效。
3.2 按执行序排列的结构：时间轮

时间轮就像一个环形的闹钟，适合处理大量定时任务，尤其是那些时间间隔相似的任务。

优点：

  • 内存和计算效率高，能同时处理很多任务。
  • 处理任务的时间复杂度是恒定的。

缺点：

  • 实现相对复杂，长时间间隔的任务可能需要多级时间轮。

4. 检测和触发机制

4.1 基于IO多路复用的检测

IO多路复用允许一个线程同时处理多个输入输出事件。这可以将定时任务的检测与IO事件结合，确保及时唤醒即将到期的任务。

应用实例： 像Redis和Nginx这样的高性能服务器，广泛使用这种机制高效处理网络和定时任务。

4.2 timerfd

timerfd是Linux提供的一种机制，可以将定时器事件转化为文件描述符，与IO多路复用结合使用。

工作流程：

  1. 创建一个timerfd，并设置触发时间。
  2. 将timerfd添加到IO多路复用的监控列表中。
  3. 当定时器到期时，IO多路复用会检测到timerfd的可读事件，触发相应的回调函数。
4.3 解决的核心问题

主要解决如何高效处理当前时间到最近要过期任务之间的操作。

5. 定时器的实现

5.1 封装

定时器的封装使其功能模块化，便于在不同的场景中使用。用户只需关注如何使用接口，而不必了解内部复杂的实现。

封装要点：

  • 接口设计：提供简单易用的API，包括任务的添加、删除、启动和停止等功能。
  • 内部实现：隐藏具体实现细节，简化用户的使用。
  • 错误处理：在任务执行过程中处理异常情况，并提供必要的反馈。
5.2 实现

选择合适的容器结构，如红黑树、最小堆和时间轮等，来实现高效的定时器。

5.2.1 容器

在实现中选择合适的容器结构是关键。可以结合前面提到的红黑树、最小堆和时间轮等结构。具体选择可以基于任务特性和性能需求。

示例结构：

  • 红黑树：适用于需要频繁动态插入和删除的任务。
  • 最小堆：适合任务量较大时快速访问最近要触发的任务。
  • 时间轮：适合处理大量具有相似触发时间间隔的任务。
5.2.2 检测触发机制

实现检测触发机制时，可以采用 IO 多路复用和 timerfd 等技术来高效监控定时任务的触发。确保机制能够及时响应即将到期的任务。

实现思路：

  • 使用 IO 多路复用来等待定时器和其他IO事件。
  • 当定时器到期时，通过回调函数处理任务。

5.3 测试

测试是验证定时器实现是否符合预期的重要环节。可以进行以下类型的测试：

  • 单元测试：针对各个模块（如容器、检测机制）进行单元测试，确保其功能正确。
  • 集成测试：测试定时器的整体功能，包括任务的添加、执行和删除。
  • 性能测试：在高并发和高任务量的情况下测试定时器的性能，验证其响应时间和资源使用情况。

5.4 优化

随着系统负载的增加，定时器的性能可能会受到影响，因此需要考虑优化策略。

5.4.1 针对大量间隔时间相同的任务的优化

在大量定时任务的情况下，可以考虑使用 insert_hint 技术，从 O(log n) 优化到 O(1)。

具体实现：

  • 在任务添加时，可以通过维护一个指向合适插入位置的指针，减少不必要的比较和移动操作。
  • 在插入相同触发时间的任务时，可以直接将任务插入到指针指向的位置，从而降低复杂度。
5.4.2 拆分思想

拆分思想可以有效提升定时器的性能，特别是在高并发场景中。

实现方式：

  • 单线程多容器：在单个线程中使用多个容器来处理不同类型或优先级的定时任务。可以避免一个容器中任务的增加导致性能瓶颈。
  • 多线程多容器：在多线程环境中，每个线程维护自己的容器和检测机制，这样可以并行处理任务，提高整体处理能力。

综合效果：

  • 减少单个容器和线程的负载，提高系统的响应速度。
  • 通过合理的任务分配和资源调度，优化资源利用率，提升系统整体性能。

 5.5 代码实践

5.5.1 epoll_wait第4个参数驱动
#include <sys/epoll.h>
#include <functional>
#include <chrono>
#include <set>
#include <memory>
#include <iostream>using namespace std;struct TimerNodeBase {time_t expire;int64_t id;
};struct TimerNode : public TimerNodeBase {using Callback = std::function<void(const TimerNode &node)>;Callback func;TimerNode(int64_t id, time_t expire, Callback func) : func(func) {this->expire = expire;this->id = id;}
};bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {if (lhd.expire < rhd.expire)return true;else if (lhd.expire > rhd.expire) return false;return lhd.id < rhd.id;
}class Timer {
public:static time_t GetTick() {auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch());return temp.count();}TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) {time_t expire = GetTick() + msec;if (timeouts.empty() || expire <= timeouts.crbegin()->expire) {auto pairs = timeouts.emplace(GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*pairs.first);}auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*ele);}bool DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if (iter != timeouts.end()) {timeouts.erase(iter);return true;}return false;}void HandleTimer(time_t now) {auto iter = timeouts.begin();while (iter != timeouts.end() && iter->expire <= now) {iter->func(*iter);iter = timeouts.erase(iter);}}time_t TimeToSleep() {auto iter = timeouts.begin();if (iter == timeouts.end()) {return -1;}time_t diss = iter->expire - GetTick();return diss > 0 ? diss : 0;}
private:static int64_t GenID() {return gid++;}static int64_t gid;set<TimerNode, std::less<>> timeouts;
};
int64_t Timer::gid = 0;int main() {int epfd = epoll_create(1);unique_ptr<Timer> timer = make_unique<Timer>();int i =0;timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->AddTimer(3000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});auto node = timer->AddTimer(2100, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->DelTimer(node);cout << "now time:" << Timer::GetTick() << endl;epoll_event ev[64] = {0};while (true) {int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());time_t now = Timer::GetTick();for (int i = 0; i < n; i++) {/**/}/* 处理定时事件*/timer->HandleTimer(now);}return 0;
}
1. 定义基本定时器节点
struct TimerNodeBase {time_t expire;int64_t id;
};

TimerNodeBase 结构体存储了定时任务的过期时间和唯一标识符（ID）。

2. 定义定时器节点
struct TimerNode : public TimerNodeBase {using Callback = std::function<void(const TimerNode &node)>;Callback func;TimerNode(int64_t id, time_t expire, Callback func) : func(func) {this->expire = expire;this->id = id;}
};

TimerNode 结构体继承自 TimerNodeBase，并且包含一个回调函数类型 Callback，用于在定时器到期时执行。构造函数初始化过期时间和 ID。

3. 定义比较运算符 
bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {if (lhd.expire < rhd.expire)return true;else if (lhd.expire > rhd.expire) return false;return lhd.id < rhd.id;
}

这个运算符重载用于将 TimerNodeBase 对象进行排序，首先比较过期时间，若相同则比较 ID。这对于在容器中管理定时任务的顺序至关重要。

4. 定义定时器类
class Timer {
public:static time_t GetTick() {auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch());return temp.count();}

Timer 类的 GetTick 方法返回当前时间的毫秒数。使用 chrono 库可以精确获取系统的当前时间。

5. 添加定时器
TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) {time_t expire = GetTick() + msec;if (timeouts.empty() || expire <= timeouts.crbegin()->expire) {auto pairs = timeouts.emplace(GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*pairs.first);}auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*ele);
}
  • 该方法用于添加定时任务，接收任务的延迟时间（毫秒）和回调函数。
  • 计算出过期时间 expire，如果时间容器 timeouts 为空或者新的过期时间早于容器中最后一个任务的过期时间，则直接添加到容器。
  • 否则，使用 emplace_hint 在适当的位置插入新任务，以提高性能。
  • 返回添加的定时任务的基本信息。
6. 删除定时器
bool DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if (iter != timeouts.end()) {timeouts.erase(iter);return true;}return false;
}
  • 此方法用于删除已存在的定时任务。使用 find 方法查找并删除，如果成功，返回 true。
7. 处理定时器
void HandleTimer(time_t now) {auto iter = timeouts.begin();while (iter != timeouts.end() && iter->expire <= now) {iter->func(*iter);iter = timeouts.erase(iter);}
}
  • 遍历定时任务容器，执行所有已到期的定时任务的回调函数，并将其从容器中移除。
8. 计算休眠时间
time_t TimeToSleep() {auto iter = timeouts.begin();if (iter == timeouts.end()) {return -1;}time_t diss = iter->expire - GetTick();return diss > 0 ? diss : 0;
}
  • 计算下一个定时任务的到期时间，与当前时间的差值，如果没有定时任务，返回 -1，表示可以一直阻塞。
9. ID 生成器
private:static int64_t GenID() {return gid++;}static int64_t gid;set<TimerNode, std::less<>> timeouts;
};int64_t Timer::gid = 0;
  • 生成唯一的 ID，使用静态变量 gid 进行自增。定时任务存储在 set 中，以确保按过期时间自动排序。
10. 主函数
int main() {int epfd = epoll_create(1);unique_ptr<Timer> timer = make_unique<Timer>();
  • 创建一个 epoll 实例，用于事件通知和处理。
  • 使用 unique_ptr 动态分配 Timer 对象。
11. 添加定时任务
    int i = 0;timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});
  • 添加多个定时任务，每个任务在 1000 毫秒后触发，打印信息并增加计数。
12. 删除定时任务
    auto node = timer->AddTimer(2100, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->DelTimer(node);
  • 添加一个定时任务并立即删除它，确保不会执行。
13. 进入事件循环
    cout << "now time:" << Timer::GetTick() << endl;epoll_event ev[64] = {0};while (true) {int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());time_t now = Timer::GetTick();for (int i = 0; i < n; i++) {/**/}/* 处理定时事件*/timer->HandleTimer(now);}
  • 进入一个无限循环，调用 epoll_wait 等待事件。
  • 第四个参数 timer->TimeToSleep() 计算下一个即将到期的定时任务的休眠时间，从而使线程在此时间段内阻塞，降低 CPU 使用率。
  • 当有事件触发（在这里可以添加处理逻辑），同时调用 HandleTimer 方法处理到期的定时任务。

 实现了一个基本的定时器，利用 epoll 处理多路复用，能有效管理定时任务的添加、删除和执行。通过合理设计容器和优化处理逻辑，确保定时器高效且响应迅速。

总结

定时器方案的设计需要在高效管理大量定时任务和及时触发任务之间找到平衡。通过选择合适的容器结构和检测触发机制，可以显著提升系统的性能和响应速度。同时，结合异步执行和内核级优化，可以实现高效、可靠的定时任务管理。在实际应用中，需根据具体需求选择最适合的方案，并结合优化策略不断提升系统的整体表现。

 参考：

0voice · GitHub


http://www.ppmy.cn/embedded/114683.html

相关文章

【项目管理进阶】风险问题

【项目管理进阶】风险问题

前言 各位盆友&#xff0c;你们期待的项目管理进阶系列有新的消息&#xff0c;请注意查收&#xff0c;并反馈哦~ 在参加项目的过程中&#xff0c;你是否面临或参加过类似如下的场面&#xff1a; 为了立项&#xff0c;先调研市场、技术、社会、组织内部的现状为了科学的管理项目…
阅读更多...
Android中如何调用DLL文件

Android中如何调用DLL文件

在 Android 设备上直接调用 DLL&#xff08;动态链接库&#xff09;文件是不可行的&#xff0c;因为 DLL 文件是 Windows 操作系统下的一种可执行文件格式&#xff0c;而 Android 操作系统基于 Linux 内核&#xff0c;两者在底层架构和 API 支持上存在根本差异。不过&#xff0…
阅读更多...
Python模拟鼠标轨迹[Python]

Python模拟鼠标轨迹[Python]

一.鼠标轨迹模拟简介 传统的鼠标轨迹模拟依赖于简单的数学模型&#xff0c;如直线或曲线路径。然而&#xff0c;这种方法难以捕捉到人类操作的复杂性和多样性。AI大模型的出现&#xff0c;能够通过深度学习技术&#xff0c;学习并模拟更自然的鼠标移动行为。 二.鼠标轨迹算法实…
阅读更多...
《线性代数》常用公式定理总结

《线性代数》常用公式定理总结

文章目录 1 行列式1.1 克拉默法则1.2 基本性质1.3 余子式 M i j M_{ij} Mij​1.4 代数余子式 A i j ( − 1 ) i j ⋅ M i j A_{ij} (-1)^{ij} \cdot M_{ij} Aij​(−1)ij⋅Mij​1.5 具体型行列式计算&#xff08;化为基本型&#xff09;1.5.1 主对角线行列式&#xff1a;主…
阅读更多...
ElementUI 用span-method实现循环el-table组件的合并行功能

ElementUI 用span-method实现循环el-table组件的合并行功能

需要把指定列的相同数据合并起来&#xff08;项目中用的是updateTime&#xff09; 后端返回的数据格式&#xff1a; html&#xff1a; <el-tab-pane label"执行记录概览" name"fourth" v-loading"loading"><el-timeline v-if"re…
阅读更多...
【算法】算法思想合集

【算法】算法思想合集

数组分块 将数组分成具有某些特征的段使用双指针算法&#xff08;如果是数组&#xff0c;使用下标充当指针&#xff09;存在信息丢失的问题&#xff0c;可以考虑从后向前进行利用单调性进行定性分析&#xff08;盛最多的水&#xff09; 滑动窗口同向移动的双指针出窗口一般是w…
阅读更多...
09年408考研真题-数据结构

09年408考研真题-数据结构

数据结构 10.【2009统考真题】为解决计算机主机与打印机之间速度不匹配的问题&#xff0c;通常设置一个打印数据缓冲区&#xff0c;主机将要输出的数据依次写入该缓冲区&#xff0c;而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(B&#xff09;。 A.栈 …
阅读更多...
计算机网络：物理层 --- 基本概念、编码与调制

计算机网络：物理层 --- 基本概念、编码与调制

目录 一. 物理层的基本概念 二. 数据通信系统的模型 三. 编码 3.1 基本概念 3.2 不归零制编码 3.3 归零制编码 3.4 曼切斯特编码 3.5 差分曼切斯特编码 ​编辑 四. 调制 4.1 调幅 4.2 调频 4.3 调相 4.4 混合调制 今天我们讲的是物理…
阅读更多...
最新文章

Copyright @ 2022~2023