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

这篇具有很好参考价值的文章主要介绍了用最小堆实现通用的高效定时器组件。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

开篇

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

解决方案

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

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

  • 时间轮方式
    ① 首先创建一个系统定时器,设置为周期性触发,周期为多个定时任务可共用的最小颗粒度。
    ② 定义环形数组,将时间划分为多个槽,每个槽放多个定时任务。
    ③ 定时器按照周期触发,触发后遍历每个槽的定时任务,并触发对应事件。

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

类图

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

用最小堆实现通用的高效定时器组件,服务器,linux,定时器,嵌入式Linux,架构设计,C++,C/C++

  • 系统定时器(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的定时器:文章来源地址https://www.toymoban.com/news/detail-843189.html

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)从小到大排序。
  • 将定时器任务抽象处三个类,各自负责自己的业务,逻辑上更加清晰明了。
  • 使用一个系统定时器资源,完成所有定时任务的响应。实现基础功能的同时,降低对系统定时资源的消耗。

到了这里,关于用最小堆实现通用的高效定时器组件的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • STM32通用定时器的使用

    (1)使能定时器时钟 本章定时器实验,我们使用的是通用定时器 TIM4,我们知道 TIM4 是挂接在 APB1 总线上的,所以可以使用 APB1 总线时钟使能函数来使能 TIM4 RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM4,ENABLE);//使能 TIM4 时钟 (2)初始化定时器参数,包含自动重装值,分频系数,计数方式

    2024年02月10日
    浏览(41)
  • STM32标准库通用定时器输入捕获

    输入捕获为STM32定时器的一个功能,可以用来测量输入信号的频率和占空比。 具体原理:当输入信号经过比较捕获通道时,STM32会依据通道的极性设置决定是否触发捕获中断TIM_IT_CCx。此时定时器会将当前计数值TIMx-CNT的值保存在TIMx-CCRx中,通过计算两次捕获中断的时间差便可

    2024年03月11日
    浏览(46)
  • STM32标准库通用定时器PWM生成

    STM32通用定时器生成的PWM波形周期为 (STM32主频)/((TIM_Period+1)*(TIM_Prescaler+1)) TIM_OCMode:PWM的模式,有两种模式:TIM_OCMode_PWM1和TIM_OCMode_PWM2 TIM_OCMode_PWM1。向上计数时,一旦TIMx_CNT TIMx_CCR1时通道1为有效电平,否则为无效电平;在向下计数时,一旦TIMx_CNT TIMx_CCR1时通道1为无效电平(

    2024年03月09日
    浏览(64)
  • STM32学习----通用定时器的应用(PWM)

    STM32单片机的通用定时器,有TIM2、TIM3、TIM4、TIM5这4个。 通用定时器的功能,用的比较多的有下面几种: 计数功能:向上计数,向下计数,向上/向下计数; 输入捕获:测量信号的周期和占空比; 输出比较: PWM生成: 通用定时器功能多了,框图也就复杂起来了 时钟来源有很

    2024年02月04日
    浏览(53)
  • 机器人是怎么计时的(通用定时器 - 时基单元)

    目录 一,引言 二,机器人的“大脑” 三,时基单元介绍 1,定时器框图 2,时基单元 (1)预分频器 (2)CNT计数器 (3)自动重装载寄存器 四,结尾 一,引言         技术的迅猛发展,赋予了越来越多科技产品“智能化”的标签。如智能洗碗机,智能冰箱,智能电饭煲……

    2024年04月14日
    浏览(39)
  • STM32 第20讲 通用定时器(简介/框图/时钟源)

    对于STM32F407有10个通用定时器,TIM2 ~ TIM5 和 TIM9 ~ TIM14。 主要特性: 16位递增、递减、中心对齐计数器(计数值:0~65535) 16位预分频器(分频系数:1~65536) 可用于触发DAC、ADC 在更新事件、触发事件、输入捕获、输出比较时,会产生中断/DMA请求 4个独立通道,可用于:输入捕

    2024年02月09日
    浏览(39)
  • QT--day4(定时器事件、鼠标事件、键盘事件、绘制事件、实现画板、QT实现TCP服务器)

     QT实现tcpf服务器代码:(源文件) 头文件:

    2024年02月15日
    浏览(53)
  • STM32CubeMX教程8 TIM 通用定时器 - 输出比较

    开发板(STM32F407G-DISC1) STM32CubeMX软件(Version 6.10.0) keil µVision5 IDE(MDK-Arm) ST-LINK/V2驱动 逻辑分析仪nanoDLA 使用STM32CubeMX软件配置STM32F407 通用定时器的输出比较通道 ,并将其输出到四个LED灯引脚实现LED灯流水灯效果 STM32F407的定时器通道均可以实现输出比较功能, 输出比较功

    2024年02月03日
    浏览(79)
  • stm32f407关于通用定时器各种函数——PWM(二)

            定时器产生PWM:在计数器频率固定时,PWM 频率由 自动重载寄存器(TIMx_ARR) 的值决定,其占空比由 捕获/比较寄存器(TIMx_CCRx) 的值决定         定时器工作在递增计数模式,纵轴是计数器的计数值 CNT,横轴表示时。当 CNT=CCRx 时,IO 输出高电平(逻辑 1);

    2024年02月08日
    浏览(84)
  • STM32CubeMX教程6 TIM 通用定时器 - 生成PWM波

    开发板(STM32F407G-DISC1) STM32CubeMX软件(Version 6.10.0) keil µVision5 IDE(MDK-Arm) ST-LINK/V2驱动 逻辑分析仪nanoDLA 使用STM32CubeMX软件配置STM32F407 通用定时器生成可变占空比PWM波形,并将其输出到LED灯引脚实现呼吸灯效果 STM32F407有10个通用定时器,其中TIM2、TIM3、TIM4和TIM5有4个捕获

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包