實現時間輪定時器
- 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);}
}
