实现时间轮定时器
- 1.时间轮定时器原理
- 2.项目中实现目的
- 3.实现功能
- 3.1构造定时任务类
- 3.2构造时间轮定时器
- 每秒钟往后移动
- 添加定时任务
- 刷新定时任务
- 取消定时任务
- 4.完整代码
1.时间轮定时器原理
时间轮定时器的原理类似于时钟，比如现在12点，定一个3点的闹钟，那么过了三小时后，闹钟就会响起。
我们就可以定义一个时间数组，并有一个指针tick，指向数组的起始位置，每个元素下位置代表着具体时间，比如第二个元素位置为第一秒(起始位置为0秒)，第三个元素位置表示第二秒,…第60个元素位置代表60秒。而tick指针每秒钟都向后移动一步，代表过了1秒。而走到哪里，就表示 哪里的任务该被执行了。
当我想要实现一个5秒后要执行的定时器，只需要将该定时器放入数组tick+5的位置去。tick指针每秒钟会向后移动一步，当5秒后，会走到对应的位置，这时去执行对应的定时任务即可。
不过同一时间可能会有多个定时任务需要执行，所以可以定一个二维的数组。
每个时间可以存放多个定时任务。
不过这里时间到了需要主动去执行对应的任务，我们有更好的方法可以自动执行对应的任务。
【类的析构】：
我们利用类的析构自动会执行的特性，所以我们可以将定时任务弄成一个类，并将任务放在析构函数中，当对象销毁时，就会自动的执行析构函数里面的定时任务。
2.项目中实现目的
在该项目中需要定时器的主要目的是用来管理每个连接的生命周期的，因为有的连接是恶意的，长时间连接啥也不干，所以为了避免这种情况，规定当一个连接创建时，超过一定时间没有动静的，就主动释放掉该连接。这时候就需要设置一个固定时间后的定时销毁任务。
比如规定时间为30s，当一个连接超过30没有发送数据或接收数据就需要释放掉。
目的：希望非活跃的连接在N秒后被释放掉。
【刷新时长】
不过当一个连接在创建后(定时任务放入30s位置上)第10秒时发送了数据，该连接的存活时间就需要重新更新，在第40秒后再释放。也就是在40s的位置上再把该定时任务插入进去。
需要在一个连接有IO事件产生的时候，延迟定时任务的执行
如何实现呢？
【shared_ptr+weak_ptr】
shared_ptr中有一个计数器，当计数器为0时资源才会真正释放。
只要让时间轮定时器里存储的是指向定时任务对象的智能指针shared_ptr，而不是定时器对象，这样就可以把要更新后的定时任务再插入进去。
这时候shared_ptr的计数器就为2，当tick走过30秒时对应的销毁任务不会执行，只会将计数器–变为1，而走到40s时，对应的销毁任务才会执行，因为这时候shared_ptr的计数器就为0了。
基于这个思想，我们可以使用shared_ptr来管理定时器任务对象
不过要主要需要使用weak_ptr来保存插入到时间轮里的定时任务对象信息。因为weak_ptr是弱引用，它不会增加shared_ptr的计数，还可以获取对应的shared_ptr对象。
- 首先第一个将任务封装起来，让这个任务呢在一个对象析构的
时候再去执行它。
2.而这个对象呢，使用shared_ptr来管理起来，添加定时任务只是添加了我们的一个shared_ptr的一个ptr对象。
3.当要延迟一个任务的执行只需要针对这个任务呢？再去重新生成shared_ptr，添加到时间轮里边。
4.该任务的计数器，就变就会加1，当前面的shared_ptr就算释放的也不会去释放所管理的对象那么，只有到后边的这个shared_ptr释放的时候计数为O了，才会去释放所管理的定时器任务。
3.实现功能
时间轮定时器的主要功能有：添加定时任务；刷新定时任务；取消定时任务；
3.1构造定时任务类
1.将定时任务封装到一个类中，每个定时任务都有自己的的标识id，用它可以在时间轮中找到对应的定时器任务对象。
2.将定时任务的函数放在该类的析构函数中，当对象销毁时自动执行，要定时的任务由由用户指定所以通过回调函数_task_cb设置进去。
3.每个定时任务都有自己的超时时间timeout,当超过该时间就去执行该任务。
4.因为时间轮定时器中还需要保存每个定时器对象的weak_ptr，用来刷新定时任务，使用unordered_map来管理。通过定时器任务id找到对应的定时器weak_ptr对象。而当定时器对象销毁时，还需要将该对象的weak_ptr信息从map表中移除。这个操作是需要在时间轮定时器中实现的，所以是需要使用回调函数_release_cb，在时间轮定时器中设置进去。
5.取消定时任务就是不执行析构函数中的回调函数即可。通过一个布尔值设置。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <memory>
#include <stdint.h>
#include <functional>
#include <unistd.h>
using TaskFunc= std::function<void()>;
using ReleaseFunc=std::function<void()>;
class TimerTask
{
public://构造TimerTask(uint64_t id,uint32_t timeout,TaskFunc &cb):_id(id),_timeout(timeout),_canceled(false),_task_cb(cb){}//析构，当对象释放时执行定时任务，并且从timerwheel中移除该定时任务的信息~TimerTask(){if(!_canceled){_task_cb();_release_cb();}}//获取该定时器的超时时间uint32_t GetTimeout() {return _timeout;}void canceled() { _canceled = true; }/*取消定时器任务*/ void ReleaseTask(ReleaseFunc cb){_release_cb=cb;}
private:uint64_t _id; //标识一个定时器对象uint32_t _timeout; //定时器的超时时间TaskFunc _task_cb; //要执行的定时任务bool _canceled;//定时任务默认是启动的，false为启动，true为终止定时器ReleaseFunc _release_cb;//释放时要从timerwheel中移除该定时器信息};
3.2构造时间轮定时器
1.时间轮定时器我们通过vector来模拟二维数组。
2.而时间轮定时器中存储的是shared_ptr对象(指向定时器任务对象的智能指针)
3.时间轮定时器需要有一个tick，就是一个滴答指针，每秒钟向后移动一步，代表过了一秒。
4.时间轮定时器中还需呀一个哈希表管理着所有插入进来的定时任务对象的weak_ptr对象。通过定时任务的id来映射找到(当添加定时任务时，就会将id和对应的weak_ptr对象插入进去)
每秒钟往后移动
定时器启动后，tick指针每秒钟都要往后移动一步。tick走到哪，就代表对应位置的任务要被执行，执行的原理就是将对应位置管理资源的shared_ptr全部清除，那么shared_ptr销毁后—>定时器对象销毁---->执行析构函数中的任务。
void RunTime(){_tick=(_tick+1)%_capacity;_wheel[_tick].clear();//将当前位置上的所有任务都释放掉，也就是都执行掉。}添加定时任务
1.添加一个定时任务时，外部会给定这个定时器任务的id，超时时间和执行方法。
所以首先要根据这些构造一个shared_ptr对象。然后将释放函数设置到定时任务中。
2.插入的位置是所在tick基础上再向后移动timeout位置。
3.插入到时间轮里
4.将该定时任务信息以WeakPtr形式保存一份在map中。
void SetRelease(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;_timers.erase(it);}//添加定时任务void AddTask(uint64_t id,uint32_t timeout,TaskFunc cb){//首先构建一个shared_ptr类型的定时器任务PtrTask pt(new TimerTask(id,timeout,cb));//将释放函数内置进去pt->ReleaseTask(std::bind(&TimerWheel::SetRelease,this,id));int pos=(_tick+timeout)%_capacity;//插入到时间轮中_wheel[pos].push_back(pt);//再将该定时器任务保存一份信息在timers中_timers[id]=WeakTask(pt);}
刷新定时任务
当需要对定时任务进行延迟时，只需要根据该定时任务的id，去map表里找对应weak_ptr对象，并从weak_ptr对象中获取对应的shared_ptr对象，然后再在tick的基础上加上该定时器的超时时间，插入到时间轮里即可。
//刷新定时任务void RefreshTask(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;PtrTask pt=_timers[id].lock();//获取weakptr保存的shared_ptruint32_t delay=pt->GetTimeout();int pos=(_tick+delay)%_capacity;_wheel[pos].push_back(pt);}
取消定时任务
要取消一个定时任务，只需要根据该定时任务的id到map表中找打它的weak_ptr对象，然后转换为shared_ptr对象，执行对应的终止函数即可。
void CancelTimer(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;PtrTask pt=_timers[id].lock();//获取weakptr保存的shared_ptrpt->canceled();}
4.完整代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include <memory>
#include <stdint.h>
#include <functional>
#include <unistd.h>using TaskFunc= std::function<void()>;
using ReleaseFunc=std::function<void()>;
class TimerTask
{
public://构造TimerTask(uint64_t id,uint32_t timeout,TaskFunc &cb):_id(id),_timeout(timeout),_canceled(false),_task_cb(cb){}//析构，当对象释放时执行定时任务，并且从timerwheel中移除该定时任务的信息~TimerTask(){if(!_canceled){_task_cb();_release_cb();}}//获取该定时器的超时时间uint32_t GetTimeout() {return _timeout;}void canceled() { _canceled = true; }/*取消定时器任务*/ void ReleaseTask(ReleaseFunc cb){_release_cb=cb;} private:uint64_t _id; //标识一个定时器对象uint32_t _timeout; //定时器的超时时间TaskFunc _task_cb; //要执行的定时任务bool _canceled;//定时任务默认是启动的，false为启动，true为终止定时器ReleaseFunc _release_cb;//释放时要从timerwheel中移除该定时器信息};class TimerWheel
{using PtrTask=std::shared_ptr<TimerTask>;using WeakTask=std::weak_ptr<TimerTask>;
public://构造TimerWheel():_tick(0),_capacity(60),_wheel(_capacity){}void SetRelease(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;_timers.erase(it);}//添加定时任务void AddTask(uint64_t id,uint32_t timeout,TaskFunc cb){//首先构建一个shared_ptr类型的定时器任务PtrTask pt(new TimerTask(id,timeout,cb));//将释放函数内置进去pt->ReleaseTask(std::bind(&TimerWheel::SetRelease,this,id));int pos=(_tick+timeout)%_capacity;//插入到时间轮中_wheel[pos].push_back(pt);//再将该定时器任务保存一份信息在timers中_timers[id]=WeakTask(pt);}//刷新定时任务void RefreshTask(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;PtrTask pt=_timers[id].lock();//获取weakptr保存的shared_ptruint32_t delay=pt->GetTimeout();int pos=(_tick+delay)%_capacity;_wheel[pos].push_back(pt);}void CancelTimer(uint64_t id){auto it=_timers.find(id);if(it==_timers.end())return;PtrTask pt=_timers[id].lock();//获取weakptr保存的shared_ptrpt->canceled();}void RunTime(){_tick=(_tick+1)%_capacity;_wheel[_tick].clear();//将当前位置上的所有任务都释放掉，也就是都执行掉。}private:int _tick; //滴答指针，指向哪就执行对应的任务,也就是释放该任务对象int _capacity; //定时器时间轮的容量大小std::vector<std::vector<PtrTask>> _wheel;//时间轮里存的是指向定时器任务对象的智能指针std::unordered_map<uint64_t,WeakTask> _timers;//存储时间轮里的定时器信息
};class Test
{
public:Test(){std::cout<<"构造"<<std::endl;}~Test(){std::cout<<"析构"<<std::endl;}};//测试
void Delete(Test* t)
{delete t;
}
int main()
{Test* t=new Test();TimerWheel tw;tw.AddTask(888,5,std::bind(Delete,t));for(int i=0;i<5;i++){std::cout<<"---------------------"<<std::endl;tw.RefreshTask(888);tw.RunTime();sleep(1);}for(int i=0;i<5;i++){std::cout<<"---------------------"<<std::endl;tw.RunTime();sleep(1);}
}
