一個(gè)高效的定時(shí)器分析及設(shè)計(jì)

對(duì)于一個(gè)游戲而言，定時(shí)器是必須的，而它一般作為一個(gè)游戲基本公共組件，而定時(shí)器在游戲邏輯中運(yùn)用是非常明顯的(比如吃藥回血，每幾秒回血多少)，而對(duì)于游戲邏輯而言需要開發(fā)一個(gè)高效率高精度(毫秒級(jí)別)的定時(shí)器。

一：分析Ace庫定時(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)來實(shí)現(xiàn)具體Timer的算法。

1)ACE_Timer_Heap定時(shí)器，根據(jù)觸發(fā)時(shí)間建立一個(gè)優(yōu)先級(jí)隊(duì)列(一個(gè)最小堆數(shù)據(jù)結(jié)構(gòu))來維護(hù)所有的定時(shí)器，代價(jià)就是刪除和插入過程為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í)間來超時(shí)響應(yīng)。所以只要我們設(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，那么第二圈沒一個(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í)器從它原來所處的輪子插槽遷移到另一個(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};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 /// 檢測定時(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í)器從它原來所處的定時(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

四： 測試

通過本文的介紹可以理解次定時(shí)器的的查找，刪除，插入都是O(1)的復(fù)雜度。

/**//// 游戲事件基類

class CGameEvent

{

public:

virtual long TimeOut( eTimerType type) = 0;

};

測試?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}