一個高效的定時器分析及設計

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

一：分析Ace庫定時器實現(xiàn)方式

1.Ace種定時器實現(xiàn)有4種，這里不具體介紹實現(xiàn)細節(jié)，主要介紹實現(xiàn)數(shù)據(jù)結構，性能。

具體的4種定時器都是從ACE_Timer_Queue_T繼承，每種定時器用不同的數(shù)據(jù)結構來實現(xiàn)具體Timer的算法。

1)ACE_Timer_Heap定時器，根據(jù)觸發(fā)時間建立一個優(yōu)先級隊列(一個最小堆數(shù)據(jù)結構)來維護所有的定時器，代價就是刪除和插入過程為O(logn),代價比較高。

2)ACE_Timer_List定時器，根據(jù)觸發(fā)時間建立一個有序的雙向鏈表，代價就是插入定時器代價較高。

3)ACE_Timer_Hash定時器，采用開鏈的Hash方式每一個桶為一個單鏈表，在檢查所有桶超時的時候會遍歷鏈表所有的元素。為了提高效率這里所用的Hash桶應該足夠 大，而對于定時器一般是頻繁的超時響應定時器，已經插入和刪除，響應會采用迭代的方式。所以效率并不是那么高效。

4)ACE_Timer_Wheel定時器，采用的一種時間輪的方式，具體實現(xiàn)就好象一個輪子上面有很多插槽，每一個插槽下面包括一個有序雙向鏈表，在Ace中把輪子叫做Wheel,插槽叫做Spoke，每一個定時器被Hash到Spoke中，而Spoke也可以理解為timer的分辨率，而Spoke的計算公式為 :( 觸發(fā)時間 >> 分辨率的位數(shù))&(spoke大小-1).然后在根據(jù)觸發(fā)時間把定時器插入到每一個Spoke的有序雙向鏈表中， 與Ace_timer_Hash的實現(xiàn)類似，只是這里用戶可以指定Spoke大小。這里代價就是插入的時候可能最壞為O(n).

我們公司現(xiàn)在CTimer就是采用Ace的ACE_Timer_Wheel原理設計的。

這里有一個圖更能直觀的描述這種思想:

實現(xiàn)方式為Vector,list組合。

二: 本文介紹一種采用linux中斷處理的定時器設計方式

此定時器的查找，刪除，插入都是O(1)

1) 介紹設計原理

定時器是基于時間的中斷函數(shù)，即是根據(jù)觸發(fā)時間來超時響應。所以只要我們設計一個基于時間的Hash算法。只要我們能我們把一個函數(shù)觸發(fā)時間全部Hash到此Hash算法的桶中，就實現(xiàn)了查找，插入，刪除O(1)的操作了，其實不然基于時間的hash算法好像挺復雜，而且桶的數(shù)量太大，內存消耗太多，所以把一個時間直接Hash代價太大。是否有一種其他的方式呢，linux中斷處理采用一種類似水表計算水量的方式，方式就是生活中的水表，第一個指針轉一圈后一個轉一格，假設每一個圈都是10個刻度，第一個圈能表示10，那么第二圈沒一個刻度表示第一個圈的1圈，就能表示10*10, 二個圈一共就能表示10*10 + 10。 以此類推，5個圈就能表示10^5+10^4+10^3+10^2+10...

一個32bits的整數(shù)，如果精確到1毫秒，則2^32位可以表示49.3天，而一般服務器應該不會直接運行49.3天，這里我們采用5個輪子(即圈), 輪子大小分別為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, 假設這里精度為n毫秒，第一個輪子表示n*256秒時間內觸發(fā)函數(shù)，第二個輪子的第二個插孔則表示n*256*2時間范圍內的，

2)一些定義:

A. 輪子，這里采用的輪子與上面介紹的Ace輪子大概一樣，一個循環(huán)列隊，每一個插槽你們有一個雙向鏈表，注意這里鏈表不需要排序，所以在插入的是O(1)的操作。輪子為5個。

3) 操作：

A. Hash算法:這里Hash算法根據(jù)他的多少時間后觸發(fā)，直接Hash得到輪子以及插槽，然后插入到某個插槽雙向的鏈表中。

B.定時器觸發(fā): 定時器觸發(fā)只會觸發(fā)第一個輪子超時的所有定時器，因為后面4個輪子定時器表示都在前1輪子觸發(fā)完了才會觸發(fā)，所以這里讓后面4個輪子維護表示將要發(fā)生的定時。這里會根據(jù)當?shù)谝粋€輪子轉第幾圈后，第二個輪子會把第幾插槽的所有定時器全部插入到第一個輪子中，依次類推，第二個輪子轉一個第三個輪子某個插槽又會插入到第二個輪子中。。。

4)注意的地方:

A.將一個定時器插入到它應該所處的定時器輪子插槽中。

B.定時器的遷移，也即將一個定時器從它原來所處的輪子插槽遷移到另一個輪子插槽中。

C.超時響應執(zhí)行當前已經到期的定時器。

三：編碼實現(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ù)結構

1/**//// 定時器指針結點

2struct ListNode

3{

4 ListNode *next,*prev;

5};

6

7/**////

8/// 定時器類型

9///

10enum eTimerType

11{

12 eTimer1 = 10,

13 eTimer2 ,

14 eTimer3

15};

16

17/**////

18/// 定時器結點,tlist表示結點的指針,expires循環(huán)周期時間

19/// etime 觸發(fā)周期時間,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/// 一個輪子,一個循環(huán)隊列

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é)點

43 ///

44 void list_del( ListNode* list);

45

46 /**////

47 /// 得到改輪子轉到第幾個插槽

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 /// 輪子當前轉到的索引

69 ///

70 int m_index;

71

72 /**////

73 /// 輪子大小

74 ///

75 int m_Size;

76

77};4)定時器管理類

定時器管理類

1/**////

2/// 定時器管理類,管理定時器的五個輪子

3///

4class CTimer

5{

6public:

7 /**////

8 /// 構造函數(shù)如下

9 ///

10 CTimer(void);

11

12 CTimer( int second);

13

14 ~CTimer(void);

15

16public:

17 /**////

18 /// 初始化定時器管理類

19 ///

20 void Init(int Second = 0);

21

22 /**////

23 /// 增加一個定時器

24 ///

25 void add_timer(timernode *times );

26

27 /**////

28 /// 檢測定時器是否存在

29 ///

30 /// @return 如果存在返回true,否則為false

31 ///

32 bool check_timer(timernode* times);

33

34 /**////

35 /// 刪除定時器

36 ///

37 /// @return 如果刪除成功返回true,否則為false

38 ///

39 bool delete_timer(CLinkList* list, timernode *times);

40

41 /**////

42 /// 重新初始化一個定時器

43 ///

44 void init_timer(timernode* timers);

45

46 /**////

47 /// 定時器的遷移，也即將一個定時器從它原來所處的定時器向量遷移到另一個定時器向量中。

48 ///

49 void cascade_timer(CLinkList* timers);

50

51 /**////

52 /// 執(zhí)行當前已經到期的定時器,所有小于jeffies的定時器

53 ///

54 void Expires( ulong jeffies);

55

56 /**////

57 /// 重新初始化一個定時器

58 ///

59 void Cancel(timernode* timers);

60

61 /**////

62 /// 重新計算一個定時器

63 ///

64 void Mod_timer(timernode* timers);

65

66private:

67 /**//// 5個輪子

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 /**//// 定時器全局tick

76 ulong m_jeffies;

77 /**//// 上次運行時間

78 ulong m_Lasttime;

79 /**//// 精確到毫秒

80 ulong m_mSecond;

81};

82

四： 測試

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

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

class CGameEvent

{

public:

virtual long TimeOut( eTimerType type) = 0;

};

測試例子：

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 /**//// 運行所有的定時器

54 mytimer.Expires( GetCurrSystemTime() );

55 }

56

57 std::cout << " sum1 = " << Sum1

58 << " sum2 = " << Sum2

59 << " sum3 = " << Sum3

60 << " sum = " << Sum ;

61 return 0;

62}