定時器(timer)是Linux提供的一種定時服務的機制[1]。在使用定時器時，預先設置一個定時時間，并給定時時間到達時執行預先設定的任務。目前Linux系統本身提供了多種用戶級定時器接口，其中精度較低的如Alarm函數，精度為秒級，能夠滿足一些定時精度低的應用場合。但由于同一進程中不能同時調用多個Alarm函數，因此應用場合有限。Setitimer克服不能重復使用的缺點，同時將精度提高到毫秒級，但是同一個進程中只能設置一個這種定時器。Timerfd是Linux為用戶程序提供的另一個定時器接口，這個接口基于文件描述符，能夠被用于select/poll的應用場景，其精度可以達到納秒級，是用戶空間高精度定時器的理想選擇。本設計的定時器池基于時間輪原理,設定一個時間片大小作為時間間隔的基本單位，將時間輪分為固定時間片數，只需要一個Timerfd來管理該定時器池，設定超時時間間隔為時間片的大小，每次當超過一個時間片的時間時,系統將會通知定時器池的管理線程，管理線程做出相應的動作。綜合以上優劣，本文提出一種定時器池的算法，用于管理大量定時器[2-3]。

1 設計原理以及工作流程
1.1 定時器池的結構
    本定時器池選用Timerfd作為添加和刪除定時器的接口，使用Linux提供的函數timerfd_settime來設定定時的間隔時間大小。本定時器池的時間間隔為一個時間片time_slot大小。設定之后,管理線程等待系統的信號通知，系統每隔一個時間片就給定時器池發送一個信號，當收到此信號時，管理線程輪詢定時器池，查看池中是否有超時的定時器，若有則按用戶需求執行相關動作。定時器池的結構如圖1所示。

    當用戶想要添加或者刪除定時器時，可直接調用添加或者刪除函數，定時器池內部的管理線程將自動處理用戶的需求，將用戶所需的定時器加到定時器池相應的時間片鏈表中統一管理。定時器池中定時器的組織形式如圖2所示。

    圖2中模擬了時間輪原理：用一個結構體來保存一個時間片，以時間片作為定時器粒度的最小單位，以及該時間片下定時器的數量，同時該結構體包含該時間片下的定時器鏈表的鏈表頭部，用來鏈接雙向鏈表，鏈表選用Linux內核所采用的嵌入式雙向鏈表結構，如式(1)所示：
    struct list_head{
    struct list_head *next, *prev}     (1)
1.2 定時器的添加
    用戶根據其需求在定時器池中加入定時器，插入定時器之前所要做的工作有：
    (1)計算定時器插入時間片，每個定時器的插入時間片計算公式為：
    timer->slot =(pool->cur_slot+timer->interval/
    pool->time_slot )% pool->slot_num;        (2)
式(2)中timer為要插入的定時器結構，其中的timer->slot為定時器插入的時間片，pool->cur_slot為定時器池當前所輪詢到的時間片，time->interval為所要添加的定時器的定時時間間隔，pool->time_slot為每個時間片的長度，pool->slot_num為定時器池的時間片總數。
    (2)計算定時器的時間輪數，每個定時器的時間輪數計算公式為：
    timer->round=timer->interval/
    (pool->time_slot*pool->slot_num)        (3)
其中的timer->round為該定時器的時間輪數，通過式(3)得出定時器的時間輪數。
    (3)用戶在添加定時器到定時器池中時，需要指定定時器的超時時間,以及超時時間到達后所需要執行的函數。同時，必須指定該定時器是一次性定時還是周期性定時，以便管理線程刪除或者重新添加該定時器。
1.3 定時器池的工作流程
    創建并初始化定時器池，此時內存中保存著一個定時器池動態管理單元，用戶通過相應接口請求定時器池按其要求增加或者刪除定時器。定時器池工作流程如圖3所示。工作時，內部的定時器管理線程一直監聽用戶請求，同時管理線程等待系統的信號通知，當有信號通知到來時，管理線程輪詢定時器池,查看池中已有的定時器池中是否有超時的定時器，若有則按照用戶指定的動作來執行。原因是：(1)可直接調用函數，這種方法的優點是不用產生線程的開銷;缺點是將占用定時器的時間，并且若該函數執行時間較長，將嚴重影響定時器的性能。(2)產生線程來執行該任務，這種方法的優點是不占用定時器池的時間，缺點是需要產生線程開銷[4]。

    管理線程還將檢查定時器的屬性，即該定時器是一次性定時還是周期性定時，如果是一次性定時，當定時器超時后，管理線程將該定時器從鏈表結構中移除；如果是周期性定時，當超時后，管理線程首先將定時器從鏈表結構中移除，然后計算該定時器池再次插入的時間片以及時間輪數，得到以上數據后，按照時間片數將定時器重新插入到相應的鏈表中，實現用戶的需求。
1.4 定時器的刪除
    當定時器時間到時，若為一次性定時，當定時器超時后，管理線程自動地將定時器從鏈表中移除，釋放相關內存。但是，當用戶因為某種需要在中途刪除未超時的一次性定時器或者刪除周期性定時器時，此時需要調用定時器刪除函數來刪除定時器。但是從定時器鏈表中尋找特定的定時器并非一件容易的事情,本文采用基于紅黑樹的形式,相應的結構體設計如下：
    typedef int key_t;                    (4)
    typedef void* data_t;                (5)
    struct rb_node_t {
            struct rb_node_t *left, *right, *parent;
            key_t key; data_t data;    
        color_t color;}            (6)
    在添加定時器時，會給每個定時器分配一個唯一的id來標記定時器，該id存放在一張位圖表中，將以O(1)的速度索取未用的id或者存儲到期回收的定時器id。將該定時器id作為紅黑樹的鍵值key，將指向定時器的內存結構指針作為紅黑樹的data 數據。管理線程同時維護紅黑樹。當需要非正常刪除某個定時器時,通過定時器的id找出其在紅黑樹中的位置，獲取定時器結構在內存中所在位置的指針,以便從定時器鏈表中刪除該定時器。紅黑樹的查找性能保持在O(logn)，從而快速找出定時器指針所在紅黑樹的單元。
2 定時器池算法的實現
    采用面向對象的思想，頭文件.h中只包含用戶可以查看到基本的結構，.c文件中包含實際的定時器池的內部數據結構，這樣可以避免用戶操作結構體中的數據成員[7]。
2.1 定時器池的函數接口

    定時器的結構數據如下：
    struct timer_pool_s {
　　bool(*init)(struct timer_pool_s *pool, struct timer_pool_
        conf *conf );  //初始化定時器結構
     timer_id(*add)(sturct timer_pool_s *this, struct timer
        *timer, TIMER_TYPE type);  //添加定時器
        bool(*del )(struct timer_pool_s *pool, timer_id id);
    //刪除定時器
        void( *enable )( struct timer_pool_s *pool );
                                         //使能定時器池
        void(*disable )( struct timer_pool_s *pool);
                                       //禁用定時器池
        void(*start )(struct timer_pool_s *pool);   //開啟定時器池
         void ( *stop )( struct timer_pool_s *pool);
                                       //關閉定時器池
    };
2.2 定時器池的使用方法
    struct timter_pool_s  *timer_pool = create_timer_pool();
    timer_pool->init(timer_pool, timer_conf);
    timer_pool->add(timer_pool, your_timer，timer_type);
    timer_pool->start(timer_pool);
    timer_pool->del(timer_pool, timer_id)l
    destroy_timer_pool( timer_pool );
　    其中的your_timer代表用戶想要添加的定時器，在該定時器結構中設置了當定時器超時后所要執行的函數地址以及是用線程啟動執行該函數,或是直接調用啟動該函數。
3 性能測試
    本定時器池使用雙向鏈表來管理各個定時器，每次輪詢所有時間片所鏈接的定時器鏈表下的定時器將占用一些系統時間，故定時器池的最小時間片應該大于輪詢鏈表中所有定時器的時間，以及到期的定時器執行相關動作所需要的時間的總和，因此定時器池不能無限地加入定時器。對于一個給定的時間片大小，通過不斷對比測試可以找出該時間片大小下，定時器池中最佳的定時器數量，定時器池中定時器的數量最少不應少于5個，否則就與定時器池設計的初衷相左。
    (1)測試環境： Intel(R) Core(TM) i3-2100 CPU @ 2.8 GHz，2 GB內存; Fedora 14(內核2.6.35.14-106.fc14.i686 )。
    (2)測試設計：測試時采用時間片粒度分別為40 ms, 80 ms、200。每次測試時,在系統尚未執行timer_pool->start前將定時器加入到定時器池中，在定時器池開啟后，立刻獲取當前時間，定時器超時后，觸發超時執行函數獲取當時的時間，記錄保存。對于每個時間片都記錄兩組數據，分別為定時器數目為5個、10個，每個定時器的定時時間分別為定時器時間片大小的1~N倍，N代表定時器數目。測試的結果為某個時間片下定時器的相對誤差以及按時響應的概率，其中按時響應概率為準時響應的定時器個數占定時器總數（測試次數100次）的百分比，相對誤差代表前后兩次定時任務的絕對誤差的差值，體現定時器的穩定性。每種情況測試100次，同時包括了本文90%以上的測試結果，并剔除了某些因為系統原因導致結果偏差太大的數據。定時器觸發方式分為部分周期性觸發、部分一次性觸發，定時器超時后，超時執行方式為直接調用執行[5-7]。測試結果如表1所示。

    由表1可見，當定時器池的時間片較小時，池中定時器數目越少，定時器池性能越好。隨著定時器數目的增加，管理線程輪詢所需要的時間可能會超過一個時間片的長度，造成定時器池在接收下一個時間片超時的信號延遲，從而導致定時器的性能急劇下降。從表1中可以看到，當定時器池時間片≥40 ms時，能夠較好地滿足性能需求。因此選擇該定時器池的時間片最小不能低于40 ms，并且定時器個數要控制在5個以內，否則定時器將不能保證及時被管理線程輪詢，從而影響定時器池的效率。另外，對于一些執行時間特別長的執行函數，此時應該選用的執行方式為線程執行，即定時器到時后，產生一個線程來執行超時執行函數。如果執行函數需要較長時間，則應選用線程方式執行；如果時間相對較短，則可以采用直接調用方式，但前提是不能影響到定時器池的性能。
    本文設計并實現了一種基于時間輪以及紅黑樹的定時器池算法，可方便用戶統一管理大量的定時器。對于定時器的添加、刪除、查找，以及輪詢等技術進行了細致地分析，提高了定時器池的響應速度，以滿足不同場合的需求。
參考文獻
[1] 趙汝聰，謝維信. 一種新的嵌入式Linux高性能定時器實現方法[J].信號處理，2009,25(3)：439-443.
[2] 趙紅武，金瑜，劉云生.一種改進的定時器實現算法及其性能分析[J].微計算機應用,2006,27(3)：343-345.
[3] 唐靚. Linux 2．6細粒度定時器的設計[J].電腦知識與技術, 2009,36(5):10259-10261.
[4] 晉磊，陳昌鵬，陳凱，等.Linux平臺下增強型定時器服務的研究[J]. 微型電腦應用,2005,21(11)：41-43.
[5] 林紹太，張會.Linux定時器及其在網絡安全中的應用[J].計算機系統應用,2004(10)：63-64.
[6] 楊焓，毛玉明. Linux用戶空間一種微秒級定時器的實現[C]. 2007中國西部青年通信學術會議,2007.
[7] STEVENS W R. UNIX網路編程(第2卷)[M].北京：人民郵電出版社,2010.