【实战指南】用最小堆实现通用的高效定时器组件

本文涉及的产品
任务调度 XXL-JOB 版免费试用,400 元额度,开发版规格
Serverless 应用引擎免费试用套餐包,4320000 CU,有效期3个月
服务治理 MSE Sentinel/OpenSergo,Agent数量 不受限
简介: 本文介绍了如何使用最小堆实现高效的定时器组件,以解决Linux应用开发中定时器资源有限的问题。文章详细描述了最小堆方式的实现原理,包括系统定时器、定时器任务和定时器任务管理三个类的设计与源码实现。测试结果显示,该方法能够准确触发定时任务,有效利用系统资源。总结部分强调了使用最小堆的优势,以及通过抽象类实现清晰的业务逻辑。

用最小堆实现通用的高效定时器组件

开篇

  在程序开发过程中,定时器会经常被使用到。而在Linux应用开发中,系统定时器资源有限,进程可创建的定时器数量会受到系统限制。假如随便滥用定时器,会导致定时器资源不足,其他模块便无法申请到定时器资源。

  如上,假如同一进程中多个模块,需要同时申请不同周期定时器,就会导致模块创建定时器失败。

解决方案

  为解决定时器资源紧缺的问题,通常有以下几种方案:

  • 最小堆方式
    ① 首先创建一个系统定时器,设置为一次性触发。
    ② 其次基于二叉堆数据结构,将每个定时任务按照时触发时间戳先后顺序依次排列。
    ③ 每次取堆顶定时器任务时间戳,计算出触发时间,启动并更新系统定时器触发时间。
    ④ 定时器触发后,检查堆顶部的定时任务是否超时,超时触发对应事件,将定时器任务移除堆顶,重复③。(若定时任务为周期任务,则将其按照下次触发时间戳插入至二叉堆)
  • 时间轮方式
    ① 首先创建一个系统定时器,设置为周期性触发,周期为多个定时任务可共用的最小颗粒度。
    ② 定义环形数组,将时间划分为多个槽,每个槽放多个定时任务。
    ③ 定时器按照周期触发,触发后遍历每个槽的定时任务,并触发对应事件。

两者相比,各有优劣。最小堆方式精度更高,时间轮方式则胜在效率。在定时任务数量不庞大的情况下,最小堆方式更合适。本篇主要介绍最小堆的实现。

类图

  通过对定时器功能的理解,可以将其抽象为三个类:系统定时器,定时器任务,定时器任务管理。其类图如下:

定时器管理组件

  • 系统定时器(SystemTimer)
    负责封装Linux 定时器接口,向外提供系统定时器的使用接口。主要包含如下功能:
    ① 创建定时器
    ② 启动定时器
    ③ 停止定时器
    ④ 销毁定时器资源
  • 定时器任务(Timer)
    负责缓存定时任务属性的数据结构。主要包含如下数据:
    ① 触发时间间隔
    ② 下次触发时间戳
    ② 触发次数
    ③ 已触发次数计数
    ④ 定时器触发响应事件
    ⑤ 预定定时器的模块ID
  • 定时器任务管理(TimerManager)
    负责持有系统定时器和定时任务的管理。主要包含如下功能:
    ① 初始化、启动、结束、销毁系统定时器
    ② 接收和缓存定时任务预约事件
    ③ 维护定时任务容器,按照定时任务容器时间序更新系统定时器触发时间

源码实现

编程环境

  1. 编译环境: Linux环境
  2. 语言: C++语言

接口定义

  • 系统定时器(SystemTimer)
class SprSystemTimer : public SprObserver
{
public:
    SprSystemTimer(ModuleIDType id, const std::string& name, std::shared_ptr<SprMediatorProxy> mediatorPtr);
    ~SprSystemTimer();
    SprSystemTimer(const SprSystemTimer&) = delete;
    SprSystemTimer& operator=(const SprSystemTimer&) = delete;
    SprSystemTimer(SprSystemTimer&&) = delete;
    SprSystemTimer& operator=(SprSystemTimer&&) = delete;
    int ProcessMsg(const SprMsg& msg);
    int Init();
    int InitTimer();
    int StartTimer(uint32_t intervalInMilliSec);
    int StopTimer();
    int DestoryTimer();
private:
    bool mTimerRunning;
    int  mTimerFd;
};
  • 定时器任务(Timer)
class SprTimer
{
public:
    SprTimer(uint32_t moduleId, uint32_t msgId, uint32_t repeatTimes, uint32_t delayInMilliSec, uint32_t intervalInMilliSec);
    SprTimer(const SprTimer& timer);
    ~SprTimer();
    bool operator < (const SprTimer& t) const;
    bool IsExpired() const;
    uint32_t GetTick() const;
    uint32_t GetModuleId() const { return mModuleId; }
    uint32_t GetMsgId() const { return mMsgId; }
    uint32_t GetIntervalInMilliSec() const { return mIntervalInMilliSec; }
    uint32_t GetExpired() const { return mExpired; }
    uint32_t GetRepeatTimes() const { return mRepeatTimes; }
    uint32_t GetRepeatCount() const { return mRepeatCount; }
    void SetExpired(uint32_t expired) { mExpired = expired; }
    void RepeatCount() const { mRepeatCount++; }
private:
    uint32_t mModuleId;
    uint32_t mMsgId;
    uint32_t mIntervalInMilliSec;
    uint32_t mExpired;
    uint32_t mRepeatTimes;
    mutable uint32_t mRepeatCount;
};
  • 定时器任务管理(TimerManager)
class SprTimerManager : public SprObserver
{
public:
    virtual ~SprTimerManager();
    int Init();
    static SprTimerManager* GetInstance(ModuleIDType id, const std::string& name, std::shared_ptr<SprMediatorProxy> mediatorPtr, std::shared_ptr<SprSystemTimer> systemTimerPtr);
private:
    SprTimerManager(ModuleIDType id, const std::string& name, std::shared_ptr<SprMediatorProxy> mediatorPtr, std::shared_ptr<SprSystemTimer> systemTimerPtr);
    int DeInit();
    int InitSystemTimer();
    int ProcessMsg(const SprMsg& msg) override;
    int PrintRealTime();
    // --------------------------------------------------------------------------------------------
    // - Module's timer book manager functions
    // --------------------------------------------------------------------------------------------
    int AddTimer(uint32_t moduleId, uint32_t msgId, uint32_t repeatTimes, int32_t delayInMilliSec, int32_t intervalInMilliSec);
    int AddTimer(const SprTimer& timer);
    int DelTimer(const SprTimer& timer);
    int UpdateTimer();
    int CheckTimer();
    uint32_t NextExpireTimes();
    // --------------------------------------------------------------------------------------------
    // - Message handle functions
    // --------------------------------------------------------------------------------------------
    void MsgRespondStartSystemTimer(const SprMsg &msg);
    void MsgRespondStopSystemTimer(const SprMsg &msg);
    void MsgRespondAddTimer(const SprMsg &msg);
    void MsgRespondDelTimer(const SprMsg &msg);
    void MsgRespondSystemTimerNotify(const SprMsg &msg);
    void MsgRespondClearTimersForExitComponent(const SprMsg &msg);
private:
    bool mEnable;                                       // Component init status
    std::set<SprTimer> mTimers;                         // sort by SprTimer.mExpired from smallest to largest
    std::shared_ptr<SprSystemTimer> mSystemTimerPtr;    // SysTimer object
};

TimerManager

中存储定时任务的容器用的std::set<Timer>,可以自定义按照时间戳从小到大排序,就不用自己实现二叉堆结构了。

如下是TimerManager中定时器触发的业务逻辑代码:

① 定时器触发后,从头遍历任务容器。

② 若当前任务已超时且任务未失效,通知定时器触发事件。将当前任务缓存至失效容器,若为重复定时器,更新时间戳,再次插入任务容器。

③ 若当前任务未到期(说明后续任务都未到期),退出容器遍历。与②互斥。

④ 从任务容器中,删除②中缓存的失效容器

⑤ 当前任务容器若为空,停止系统定时器。

void SprTimerManager::MsgRespondSystemTimerNotify(const SprMsg &msg)
{
    set<SprTimer> deleteTimers;
    // loop: Execute the triggered timers, timers are sorted by Expired value from smallest to largest
    for (auto it = mTimers.begin(); it != mTimers.end(); ++it) {
        if (it->IsExpired()) {
            if (it->GetRepeatTimes() == 0 || (it->GetRepeatCount() + 1) < it->GetRepeatTimes()) {
                SprTimer t(*it);
                // loop: update timer valid expired time
                uint32_t tmpExpired = t.GetExpired();
                do {
                    tmpExpired += t.GetIntervalInMilliSec();
                    t.RepeatCount();
                } while (tmpExpired < it->GetTick());
                if (it->GetRepeatTimes() == 0 || (it->GetRepeatCount() + 1) < it->GetRepeatTimes()) {
                    t.SetExpired(tmpExpired);
                    AddTimer(t);
                }
            }
            // Notify expired timer event to the book component
            SprMsg msg(it->GetModuleId(), it->GetMsgId());
            NotifyObserver(msg);
            it->RepeatCount();
            deleteTimers.insert(*it);
        } else {
            break;
        }
    }
    // Delete expired timers
    for (const auto& timer : deleteTimers) {
        DelTimer(timer);
    }
    // Set next system timer
    uint32_t msgId = mTimers.empty() ? SIG_ID_TIMER_STOP_SYSTEM_TIMER : SIG_ID_TIMER_START_SYSTEM_TIMER;
    SprMsg sysMsg(msgId);
    SendMsg(sysMsg);
    // SPR_LOGD("Current total timers size = %d\n", (int)mTimers.size());
}

测试

测试一个2s的定时器:

56 DebugCore D: msg id: SIG_ID_DEBUG_TIMER_TEST_2S 2024-03-03 19:26:16.586
56 DebugCore D: msg id: SIG_ID_DEBUG_TIMER_TEST_2S 2024-03-03 19:26:18.586
56 DebugCore D: msg id: SIG_ID_DEBUG_TIMER_TEST_2S 2024-03-03 19:26:20.586
56 DebugCore D: msg id: SIG_ID_DEBUG_TIMER_TEST_2S 2024-03-03 19:26:22.585

总结

  • 对于定时器容器,本篇用到了STL接口的std::set<Timer>容器,通过重载Timer运算符<,实现按照时间戳(mExpired)从小到大排序。
  • 将定时器任务抽象处三个类,各自负责自己的业务,逻辑上更加清晰明了。
  • 使用一个系统定时器资源,完成所有定时任务的响应。实现基础功能的同时,降低对系统定时资源的消耗。
目录
打赏
0
13
15
26
85
分享
相关文章
灵活时隙符号配比 | 带你读《5G 空口设计与实践进阶 》之十八
通过不同时隙格式的选择或不同时隙格式的聚合,NR 可以动态适配当前场景下的业务需求。
灵活时隙符号配比 | 带你读《5G 空口设计与实践进阶 》之十八
|
8月前
|
高效定时器设计方案——层级时间轮
高效定时器设计方案——层级时间轮
108 2
揭秘前端高手的秘密武器:深度解析递归组件与动态组件的奥妙,让你代码效率翻倍!
【10月更文挑战第23天】在Web开发中,组件化已成为主流。本文深入探讨了递归组件与动态组件的概念、应用及实现方式。递归组件通过在组件内部调用自身,适用于处理层级结构数据,如菜单和树形控件。动态组件则根据数据变化动态切换组件显示,适用于不同业务逻辑下的组件展示。通过示例,展示了这两种组件的实现方法及其在实际开发中的应用价值。
62 1
深度解析Unity游戏开发:从零构建可扩展与可维护的游戏架构,让你的游戏项目在模块化设计、脚本对象运用及状态模式处理中焕发新生,实现高效迭代与团队协作的完美平衡之路
【9月更文挑战第1天】游戏开发中的架构设计是项目成功的关键。良好的架构能提升开发效率并确保项目的长期可维护性和可扩展性。在使用Unity引擎时,合理的架构尤为重要。本文探讨了如何在Unity中实现可扩展且易维护的游戏架构,包括模块化设计、使用脚本对象管理数据、应用设计模式(如状态模式)及采用MVC/MVVM架构模式。通过这些方法,可以显著提高开发效率和游戏质量。例如,模块化设计将游戏拆分为独立模块。
303 3
|
9月前
|
高效操作数组:掌握这些常见技巧,让你的编程事半功倍!
高效操作数组:掌握这些常见技巧,让你的编程事半功倍!
73 0
【芯片前端】保持代码手感——握手型同步fifo的进一步拓展
【芯片前端】保持代码手感——握手型同步fifo的进一步拓展
114 1
在编写RTOS代码时,如何设计一个简单、优雅、可拓展的任务初始化结构?
在编写RTOS代码时,如何设计一个简单、优雅、可拓展的任务初始化结构?
168 0
入门篇2:如何系统高效的学习算法与数据结构
入门篇2:如何系统高效的学习算法与数据结构
探索Java数组:基础、特性与灵活应用
在Java编程中,数组是一种基础而重要的数据结构,它能够以紧凑的方式存储多个元素。无论是在简单的数据存储还是复杂的算法实现中,数组都扮演着不可或缺的角色。本文将引导您深入了解Java数组,包括数组的基本概念、特性、用法以及常见应用场景。