用最小堆实现通用的高效定时器组件
文章目录
- 用最小堆实现通用的高效定时器组件
- 开篇
- 解决方案
- 类图
- 源码实现
- 测试
- 总结
开篇
在程序开发过程中，定时器会经常被使用到。而在Linux应用开发中，系统定时器资源有限，进程可创建的定时器数量会受到系统限制。假如随便滥用定时器，会导致定时器资源不足，其他模块便无法申请到定时器资源。
如上，假如同一进程中多个模块，需要同时申请不同周期定时器，就会导致模块创建定时器失败。
解决方案
为解决定时器资源紧缺的问题，通常有以下几种方案：
-
最小堆方式
① 首先创建一个系统定时器，设置为一次性触发。
② 其次基于二叉堆数据结构，将每个定时任务按照时触发时间戳先后顺序依次排列。
③ 每次取堆顶定时器任务时间戳，计算出触发时间，启动并更新系统定时器触发时间。
④ 定时器触发后，检查堆顶部的定时任务是否超时，超时触发对应事件，将定时器任务移除堆顶，重复③。（若定时任务为周期任务，则将其按照下次触发时间戳插入至二叉堆） -
时间轮方式
① 首先创建一个系统定时器，设置为周期性触发，周期为多个定时任务可共用的最小颗粒度。
② 定义环形数组，将时间划分为多个槽，每个槽放多个定时任务。
③ 定时器按照周期触发，触发后遍历每个槽的定时任务，并触发对应事件。
两者相比，各有优劣。最小堆方式精度更高，时间轮方式则胜在效率。在定时任务数量不庞大的情况下，最小堆方式更合适。本篇主要介绍最小堆的实现。
类图
通过对定时器功能的理解，可以将其抽象为三个类：系统定时器，定时器任务，定时器任务管理。其类图如下：
-
系统定时器(SystemTimer)
负责封装Linux 定时器接口，向外提供系统定时器的使用接口。主要包含如下功能：
① 创建定时器
② 启动定时器
③ 停止定时器
④ 销毁定时器资源 -
定时器任务(Timer)
负责缓存定时任务属性的数据结构。主要包含如下数据：
① 触发时间间隔
② 下次触发时间戳
② 触发次数
③ 已触发次数计数
④ 定时器触发响应事件
⑤ 预定定时器的模块ID -
定时器任务管理(TimerManager)
负责持有系统定时器和定时任务的管理。主要包含如下功能：
① 初始化、启动、结束、销毁系统定时器
② 接收和缓存定时任务预约事件
③ 维护定时任务容器，按照定时任务容器时间序更新系统定时器触发时间
源码实现
编程环境
- 编译环境: Linux环境
- 语言: 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)从小到大排序。 - 将定时器任务抽象处三个类，各自负责自己的业务，逻辑上更加清晰明了。
- 使用一个系统定时器资源，完成所有定时任务的响应。实现基础功能的同时，降低对系统定时资源的消耗。
![每日一题 --- 反转链表[力扣][Go]](https://img-blog.csdnimg.cn/direct/34b6d71706c84ca1850d8e8bba09562c.png)
