|
|
定时器应用场景
（1）心跳检测。
（2）游戏中的技能冷却。
（3）倒计时。
（4）其他需要延迟处理的功能。
红黑树
红黑树是绝对有序的数据结构。
利用红黑树实现定时器
在c++中，set、map、multiset、multimap使用的是红黑树管理数据。可以利用这几个类实现定时器方案，以set为例，使用C++ 14特性。
实现接口
获取当前时间的接口GetTick()
C++ 11时间库chrono
（1）steady_clock：系统启动到当前的时间，可以用来计算程序运行时间。
（2）system_clock：时间戳，可以修改。
（3）high_resolution_clock：高精度版本的steady_lock。
int64_t GetTick()
{
auto sc=chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());
auto temp=chrono::duration_cast<milliseconds>(sc.time_since_epoch());
return temp.count();
}相同触发时间的定时任务处理方案
（1）越后面插入的节点，插入位置放在红黑树越右侧。
（2）使用C++的set容器；内部是红黑树管理数据。
（3）定时器节点设计，使用触发时间和ID唯一标识定时节点。
struct TimeNodeBase{
int64_t id; // 描述插入的先后顺序
time_t expire; // 触发时间
}（4）比较仿函数，确定数据插入红黑树的位置。利用C++14的特性，find时只需要等价key比较，无需构建key对象比较。利用基类的多态特性，只需要一个比较仿函数即可。
bool operator < (const TimeNodeBase *lhd,const TimeNodeBase *rhd)
{
if(lhd->expire < rhd->expire)
return true;
else if(lhd->expire > rhd->expire)
return false;
return lhd->id < rhd->id;
}（5）尽量减少函数对象赋值、移动等操作，提高性能。
// TimerNode 继承 TimerNodeBase
struct TimerNode:public TimerNodeBase
{
// C++ 11特性，使用函数对象。降低拷贝消耗，提高效率
using Callback = std::function<void(const TimerNode &node)>;
Callback func;
// 构造函数，只构造一次
TimerNode(int64_t id,time_t expire,Callback func):func(func){
this->id = id;
this->expire = expire;
}
};相关视频推荐
红黑树、最小堆、时间轮、跳表多种方式实现定时器
王者荣耀（游戏开发）如何处理海量定时任务
linux内核中，红黑树的4种应用场景，每一种都很实用
学习地址：c/c++ linux服务器开发/后台架构师
需要C/C++ Linux服务器架构师学习资料加qun812855908获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享
驱动定时器方式
可以采用IO时间和定时器事件在同一个线程执行的方案，利用epoll的epoll_wait()第四个参数做定时延时。
示例：
int main()
{
int epfd=epoll_wait(1);
epoll_event evs[64]={0};
while(1)
{
int n=epoll_wait(epfd,evs,64,delaytime);
int i=0;
for(i=0;i<n;i++)
{
/*处理IO事件*/
}
// 处理定时任务事件
}
return 0;
}示例代码
（1）创建定时器驱动，epoll_create、epoll_wait。
（2）创建timer类，实现AddTimer()、CheckTimer()、DelTimer()等接口。
（3）选择数据结构，set容器，本质使用红黑树数据结构。
（4）定义节点的结构。
demo代码：
#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;
};
// TimerNode 继承 TimerNodeBase
struct TimerNode:public TimerNodeBase
{
// C++ 11特性，使用函数对象。降低拷贝消耗，提高效率
using Callback = std::function<void(const TimerNode &node)>;
Callback func;
// 构造函数，只构造一次
TimerNode(int64_t id,time_t expire,Callback func):func(func){
this->id = id;
this->expire = expire;
}
};
// 基类引用，多态特性
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()
{
/* C++ 11时间库chrono */
//表示一个具体时间
auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());
auto tmp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch());
return tmp.count();
}
TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func)
{
time_t expire = GetTick() + msec;
//避免拷贝、移动构造
auto ele = timermap.emplace(GenID(), expire, func);
return static_cast<TimerNodeBase>(*ele.first);
}
bool DelTimer(TimerNodeBase &node)
{
// C++ 14新特性，不在需要传一个key对象，传递一个key的等价值
auto iter = timermap.find(node);
if (iter != timermap.end())
{
timermap.erase(iter);
return true;
}
return false;
}
bool CheckTimer()
{
auto iter = timermap.begin();
if (iter != timermap.end() && iter->expire <= GetTick())
{
iter->func(*iter);
timermap.erase(iter);
return true;
}
return false;
}
time_t TimeToSleep()
{
auto iter = timermap.begin();
if (iter == timermap.end())
return -1;//没有定时任务，设置epoll一直阻塞。
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<>> timermap;
};
int64_t Timer::gid = 0;
#define EPOLL_EV_LENFTH 1024
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() << &#34;node id:&#34; << node.id << &#34; revoked times:&#34; << ++i << endl;
});
timer->AddTimer(1000, [&](const TimerNode &node) {
cout << Timer::GetTick() << &#34;node id:&#34; << node.id << &#34; revoked times:&#34; << ++i << endl;
});
timer->AddTimer(3000, [&](const TimerNode &node) {
cout << Timer::GetTick() << &#34;node id:&#34; << node.id << &#34; revoked times:&#34; << ++i << endl;
});
auto node = timer->AddTimer(2100, [&](const TimerNode &node) {
cout << Timer::GetTick() << &#34;node id:&#34; << node.id << &#34; revoked times:&#34; << ++i << endl;
});
timer->DelTimer(node);
cout << &#34;now time:&#34; << Timer::GetTick() << endl;
epoll_event evs[EPOLL_EV_LENFTH] = { 0 };
while (1)
{
int nready = epoll_wait(epfd, evs, EPOLL_EV_LENFTH, timer->TimeToSleep());
for (int i = 0; i < nready; i++)
{
/*处理IO事件*/
}
// timer检测和处理
while (timer->CheckTimer());
}
return 0;
}总结
设计一个定时器时，先确定时间精度；选择驱动定时器的方式；选择合适的数据接口（不要选择优先队列）；设计定时器基本接口 { AddTimer()、DelTimer()、CheckTimer() } 和扩展接口 { Tick()等 } ；考虑相同触发时间的定时任务处理。
 |
|
发表于 2023-1-8 14:12:24