一個(gè)高效的定時(shí)器分析及設(shè)計(jì)
對(duì)于一個(gè)游戲而言，定時(shí)器是必須的，而它一般作為一個(gè)游戲基本公共組件，而定時(shí)器在游戲邏輯中運(yùn)用是非常明顯的(比如吃藥回血，每幾秒回血多少)，而對(duì)于游戲邏輯而言需要開發(fā)一個(gè)高效率高精度(毫秒級(jí)別)的定時(shí)器。
一：分析Ace庫(kù)定時(shí)器實(shí)現(xiàn)方式
1.Ace種定時(shí)器實(shí)現(xiàn)有4種，這里不具體介紹實(shí)現(xiàn)細(xì)節(jié)，主要介紹實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，性能。
具體的4種定時(shí)器都是從ACE_Timer_Queue_T繼承，每種定時(shí)器用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)具體Timer的算法。
1)ACE_Timer_Heap定時(shí)器，根據(jù)觸發(fā)時(shí)間建立一個(gè)優(yōu)先級(jí)隊(duì)列(一個(gè)最小堆數(shù)據(jù)結(jié)構(gòu))來(lái)維護(hù)所有的定時(shí)器，代價(jià)就是刪除和插入過(guò)程為O(logn),代價(jià)比較高。
2)ACE_Timer_List定時(shí)器，根據(jù)觸發(fā)時(shí)間建立一個(gè)有序的雙向鏈表，代價(jià)就是插入定時(shí)器代價(jià)較高。
3)ACE_Timer_Hash定時(shí)器，采用開鏈的Hash方式每一個(gè)桶為一個(gè)單鏈表，在檢查所有桶超時(shí)的時(shí)候會(huì)遍歷鏈表所有的元素。為了提高效率這里所用的Hash桶應(yīng)該足夠 大，而對(duì)于定時(shí)器一般是頻繁的超時(shí)響應(yīng)定時(shí)器，已經(jīng)插入和刪除，響應(yīng)會(huì)采用迭代的方式。所以效率并不是那么高效。
4)ACE_Timer_Wheel定時(shí)器，采用的一種時(shí)間輪的方式，具體實(shí)現(xiàn)就好象一個(gè)輪子上面有很多插槽，每一個(gè)插槽下面包括一個(gè)有序雙向鏈表，在Ace中把輪子叫做Wheel,插槽叫做Spoke，每一個(gè)定時(shí)器被Hash到Spoke中，而Spoke也可以理解為timer的分辨率，而Spoke的計(jì)算公式為 :( 觸發(fā)時(shí)間 >> 分辨率的位數(shù))&(spoke大小-1).然后在根據(jù)觸發(fā)時(shí)間把定時(shí)器插入到每一個(gè)Spoke的有序雙向鏈表中， 與Ace_timer_Hash的實(shí)現(xiàn)類似，只是這里用戶可以指定Spoke大小。這里代價(jià)就是插入的時(shí)候可能最壞為O(n).
我們公司現(xiàn)在CTimer就是采用Ace的ACE_Timer_Wheel原理設(shè)計(jì)的。
這里有一個(gè)圖更能直觀的描述這種思想:
實(shí)現(xiàn)方式為Vector,list組合。
二: 本文介紹一種采用linux中斷處理的定時(shí)器設(shè)計(jì)方式
此定時(shí)器的查找，刪除，插入都是O(1)
1) 介紹設(shè)計(jì)原理
定時(shí)器是基于時(shí)間的中斷函數(shù)，即是根據(jù)觸發(fā)時(shí)間來(lái)超時(shí)響應(yīng)。所以只要我們?cè)O(shè)計(jì)一個(gè)基于時(shí)間的Hash算法。只要我們能我們把一個(gè)函數(shù)觸發(fā)時(shí)間全部Hash到此Hash算法的桶中，就實(shí)現(xiàn)了查找，插入，刪除O(1)的操作了，其實(shí)不然基于時(shí)間的hash算法好像挺復(fù)雜，而且桶的數(shù)量太大，內(nèi)存消耗太多，所以把一個(gè)時(shí)間直接Hash代價(jià)太大。是否有一種其他的方式呢，linux中斷處理采用一種類似水表計(jì)算水量的方式，方式就是生活中的水表，第一個(gè)指針轉(zhuǎn)一圈后一個(gè)轉(zhuǎn)一格，假設(shè)每一個(gè)圈都是10個(gè)刻度，第一個(gè)圈能表示10，那么第二圈沒(méi)一個(gè)刻度表示第一個(gè)圈的1圈，就能表示10*10, 二個(gè)圈一共就能表示10*10 + 10。 以此類推，5個(gè)圈就能表示10^5+10^4+10^3+10^2+10...
一個(gè)32bits的整數(shù)，如果精確到1毫秒，則2^32位可以表示49.3天，而一般服務(wù)器應(yīng)該不會(huì)直接運(yùn)行49.3天，這里我們采用5個(gè)輪子(即圈), 輪子大小分別為256,64,64,64,64 ,輪子依次類推表示范圍在0~256, 256~256*64, 256*64~256*64^2, 256*64^2~256*64^3, 256*64^3~256*64^4, 假設(shè)這里精度為n毫秒，第一個(gè)輪子表示n*256秒時(shí)間內(nèi)觸發(fā)函數(shù)，第二個(gè)輪子的第二個(gè)插孔則表示n*256*2時(shí)間范圍內(nèi)的，
2)一些定義:
A. 輪子，這里采用的輪子與上面介紹的Ace輪子大概一樣，一個(gè)循環(huán)列隊(duì)，每一個(gè)插槽你們有一個(gè)雙向鏈表，注意這里鏈表不需要排序，所以在插入的是O(1)的操作。輪子為5個(gè)。
3) 操作：
A. Hash算法:這里Hash算法根據(jù)他的多少時(shí)間后觸發(fā)，直接Hash得到輪子以及插槽，然后插入到某個(gè)插槽雙向的鏈表中。
B.定時(shí)器觸發(fā): 定時(shí)器觸發(fā)只會(huì)觸發(fā)第一個(gè)輪子超時(shí)的所有定時(shí)器，因?yàn)楹竺?個(gè)輪子定時(shí)器表示都在前1輪子觸發(fā)完了才會(huì)觸發(fā)，所以這里讓后面4個(gè)輪子維護(hù)表示將要發(fā)生的定時(shí)。這里會(huì)根據(jù)當(dāng)?shù)谝粋€(gè)輪子轉(zhuǎn)第幾圈后，第二個(gè)輪子會(huì)把第幾插槽的所有定時(shí)器全部插入到第一個(gè)輪子中，依次類推，第二個(gè)輪子轉(zhuǎn)一個(gè)第三個(gè)輪子某個(gè)插槽又會(huì)插入到第二個(gè)輪子中。。。
4)注意的地方:
A.將一個(gè)定時(shí)器插入到它應(yīng)該所處的定時(shí)器輪子插槽中。
B.定時(shí)器的遷移，也即將一個(gè)定時(shí)器從它原來(lái)所處的輪子插槽遷移到另一個(gè)輪子插槽中。
C.超時(shí)響應(yīng)執(zhí)行當(dāng)前已經(jīng)到期的定時(shí)器。
三：編碼實(shí)現(xiàn)
1) 常量定義
/**//// define m
#define lnum 5
#define sbits 6
#define ebits 8
#define sbitsize ( 1 << sbits )
#define ebitsize ( 1 << ebits )
#define sMask ( sbitsize- 1)
#define eMask ( ebitsize -1)
2) 數(shù)據(jù)結(jié)構(gòu)
1/**//// 定時(shí)器指針結(jié)點(diǎn)
2struct ListNode
3{
4 ListNode *next,*prev;
5};
6
7/**////
8/// 定時(shí)器類型
9///
10enum eTimerType
11{
12 eTimer1 = 10,
13 eTimer2 ,
14 eTimer3
15};
16
17/**////
18/// 定時(shí)器結(jié)點(diǎn),tlist表示結(jié)點(diǎn)的指針,expires循環(huán)周期時(shí)間
19/// etime 觸發(fā)周期時(shí)間,pFun觸發(fā)函數(shù).
20///
21struct timernode
22{
23 ListNode tlist;
24 ulong expires;
25 ulong etime;
26 void *pFun;
27 eTimerType eType;
28};
3) 輪子類
1/**////
2/// 一個(gè)輪子,一個(gè)循環(huán)隊(duì)列
3///
4///
5class CLinkList
6{
7
8public:
9
10 CLinkList(void);
11
12 CLinkList( int size );
13
14 ~CLinkList(void);
15
16 /**////
17 /// 初始化
18 ///
19 void init();
20
21 /**////
22 /// 讓指針指向自己
23 ///
24 void init_list_self( int index);
25
26 /**////
27 /// 把news插入到prev,next之間
28 ///
29 void insert_listnode(ListNode *news , ListNode* prev , ListNode* next);
30
31 /**////
32 /// 插入到鏈表頭
33 ///
34 void insert_head( ListNode* news , ListNode* head );
35
36 /**////
37 /// 插入到鏈表尾
38 ///
39 void insert_tail( ListNode* news , ListNode* head );
40
41 /**////
42 /// 刪除節(jié)點(diǎn)
43 ///
44 void list_del( ListNode* list);
45
46 /**////
47 /// 得到改輪子轉(zhuǎn)到第幾個(gè)插槽
48 ///
49 int GetIndex( ) const { return m_index ;}
50
51 /**////
52 /// 更新輪子的插槽
53 ///
54 void SetIndex(int idx) { m_index = idx ;}
55
56 /**////
57 /// 得到輪子插槽的指針
58 ///
59 ListNode* GetNode(int index) const;
60
61private:
62 /**////
63 /// 輪子的插槽數(shù)組
64 ///
65 ListNode *m_List;
66
67 /**////
68 /// 輪子當(dāng)前轉(zhuǎn)到的索引
69 ///
70 int m_index;
71
72 /**////
73 /// 輪子大小
74 ///
75 int m_Size;
76
77};[!--empirenews.page--]
4)定時(shí)器管理類
定時(shí)器管理類
1/**////
2/// 定時(shí)器管理類,管理定時(shí)器的五個(gè)輪子
3///
4class CTimer
5{
6public:
7 /**////
8 /// 構(gòu)造函數(shù)如下
9 ///
10 CTimer(void);
11
12 CTimer( int second);
13
14 ~CTimer(void);
15
16public:
17 /**////
18 /// 初始化定時(shí)器管理類
19 ///
20 void Init(int Second = 0);
21
22 /**////
23 /// 增加一個(gè)定時(shí)器
24 ///
25 void add_timer(timernode *times );
26
27 /**////
28 /// 檢測(cè)定時(shí)器是否存在
29 ///
30 /// @return 如果存在返回true,否則為false
31 ///
32 bool check_timer(timernode* times);
33
34 /**////
35 /// 刪除定時(shí)器
36 ///
37 /// @return 如果刪除成功返回true,否則為false
38 ///
39 bool delete_timer(CLinkList* list, timernode *times);
40
41 /**////
42 /// 重新初始化一個(gè)定時(shí)器
43 ///
44 void init_timer(timernode* timers);
45
46 /**////
47 /// 定時(shí)器的遷移，也即將一個(gè)定時(shí)器從它原來(lái)所處的定時(shí)器向量遷移到另一個(gè)定時(shí)器向量中。
48 ///
49 void cascade_timer(CLinkList* timers);
50
51 /**////
52 /// 執(zhí)行當(dāng)前已經(jīng)到期的定時(shí)器,所有小于jeffies的定時(shí)器
53 ///
54 void Expires( ulong jeffies);
55
56 /**////
57 /// 重新初始化一個(gè)定時(shí)器
58 ///
59 void Cancel(timernode* timers);
60
61 /**////
62 /// 重新計(jì)算一個(gè)定時(shí)器
63 ///
64 void Mod_timer(timernode* timers);
65
66private:
67 /**//// 5個(gè)輪子
68 CLinkList* m_tv1;
69 CLinkList* m_tv2;
70 CLinkList* m_tv3;
71 CLinkList* m_tv4;
72 CLinkList* m_tv5;
73 CLinkList** g_vecs;
74
75 /**//// 定時(shí)器全局tick
76 ulong m_jeffies;
77 /**//// 上次運(yùn)行時(shí)間
78 ulong m_Lasttime;
79 /**//// 精確到毫秒
80 ulong m_mSecond;
81};
82
四： 測(cè)試
通過(guò)本文的介紹可以理解次定時(shí)器的的查找，刪除，插入都是O(1)的復(fù)雜度。
/**//// 游戲事件基類
class CGameEvent
{
public:
virtual long TimeOut( eTimerType type) = 0;
};
測(cè)試?yán)樱?/p>
1long Sum1= 0 ;
2long Sum2= 0 ;
3long Sum3= 0 ;
4long Sum = 0;
5
6class CTimertest : public CGameEvent
7{
8public:
9 long TimeOut( eTimerType type)
10 {
11 switch ( type)
12 {
13 case eTimer1:
14 std::cout <<"Sum1 = "<< Sum1 ++ << std::endl;
15 break;
16 case eTimer2:
17 std::cout <<"Sum2 = "<< Sum2 ++ << std::endl;
18 break;
19 case eTimer3:
20 std::cout <<"Sum3 = "<< Sum3 ++ << std::endl;
21 break;
22 default:
23 std::cout <<"Sum = "<< Sum ++ << std::endl;
24 break;
25 }
26 return 0;
27 }
28};
29
30int _tmain(int argc, _TCHAR* argv[])
31{
32 CTimer mytimer( 40 );
33
34 long n;
35 std::cin >> n;
36 CTimerTest test;
37 for ( int i = 0 ; i < n ; i++ )
38 {
39 timernode* tim = new timernode ;
40 tim->expires = 0;
41 tim->etime = GetCurrSystemTime() + (rand() % 1000 ) * 6;
42 tim->pFun =&test;
43 tim->eType =(eTimerType)( i%3 + 10 );
44
45 mytimer.add_timer( tim );
46 }
47
48 for ( ;; )
49 {
50 if ( (Sum1 + Sum2 + Sum3) == n )
51 break;
52
53 /**//// 運(yùn)行所有的定時(shí)器
54 mytimer.Expires( GetCurrSystemTime() );
55 }
56
57 std::cout << " sum1 = " << Sum1
58 << " sum2 = " << Sum2
59 << " sum3 = " << Sum3
60 << " sum = " << Sum ;
61 return 0;
62}
下載文檔
