文獻(xiàn)標(biāo)識碼: A
文章編號: 0258-7998(2012)12-0114-03
定時(shí)器(timer)是Linux提供的一種定時(shí)服務(wù)的機(jī)制[1],。在使用定時(shí)器時(shí),預(yù)先設(shè)置一個(gè)定時(shí)時(shí)間,,并給定時(shí)時(shí)間到達(dá)時(shí)執(zhí)行預(yù)先設(shè)定的任務(wù),。目前Linux系統(tǒng)本身提供了多種用戶級定時(shí)器接口,其中精度較低的如Alarm函數(shù),,精度為秒級,,能夠滿足一些定時(shí)精度低的應(yīng)用場合。但由于同一進(jìn)程中不能同時(shí)調(diào)用多個(gè)Alarm函數(shù),,因此應(yīng)用場合有限,。Setitimer克服不能重復(fù)使用的缺點(diǎn),同時(shí)將精度提高到毫秒級,,但是同一個(gè)進(jìn)程中只能設(shè)置一個(gè)這種定時(shí)器,。Timerfd是Linux為用戶程序提供的另一個(gè)定時(shí)器接口,這個(gè)接口基于文件描述符,,能夠被用于select/poll的應(yīng)用場景,,其精度可以達(dá)到納秒級,是用戶空間高精度定時(shí)器的理想選擇,。本設(shè)計(jì)的定時(shí)器池基于時(shí)間輪原理,設(shè)定一個(gè)時(shí)間片大小作為時(shí)間間隔的基本單位,,將時(shí)間輪分為固定時(shí)間片數(shù),,只需要一個(gè)Timerfd來管理該定時(shí)器池,設(shè)定超時(shí)時(shí)間間隔為時(shí)間片的大小,,每次當(dāng)超過一個(gè)時(shí)間片的時(shí)間時(shí),系統(tǒng)將會(huì)通知定時(shí)器池的管理線程,,管理線程做出相應(yīng)的動(dòng)作。綜合以上優(yōu)劣,,本文提出一種定時(shí)器池的算法,,用于管理大量定時(shí)器[2-3]。
1 設(shè)計(jì)原理以及工作流程
1.1 定時(shí)器池的結(jié)構(gòu)
本定時(shí)器池選用Timerfd作為添加和刪除定時(shí)器的接口,,使用Linux提供的函數(shù)timerfd_settime來設(shè)定定時(shí)的間隔時(shí)間大小,。本定時(shí)器池的時(shí)間間隔為一個(gè)時(shí)間片time_slot大小。設(shè)定之后,管理線程等待系統(tǒng)的信號通知,,系統(tǒng)每隔一個(gè)時(shí)間片就給定時(shí)器池發(fā)送一個(gè)信號,,當(dāng)收到此信號時(shí),管理線程輪詢定時(shí)器池,,查看池中是否有超時(shí)的定時(shí)器,,若有則按用戶需求執(zhí)行相關(guān)動(dòng)作。定時(shí)器池的結(jié)構(gòu)如圖1所示,。
當(dāng)用戶想要添加或者刪除定時(shí)器時(shí),,可直接調(diào)用添加或者刪除函數(shù),定時(shí)器池內(nèi)部的管理線程將自動(dòng)處理用戶的需求,,將用戶所需的定時(shí)器加到定時(shí)器池相應(yīng)的時(shí)間片鏈表中統(tǒng)一管理,。定時(shí)器池中定時(shí)器的組織形式如圖2所示。
圖2中模擬了時(shí)間輪原理:用一個(gè)結(jié)構(gòu)體來保存一個(gè)時(shí)間片,,以時(shí)間片作為定時(shí)器粒度的最小單位,,以及該時(shí)間片下定時(shí)器的數(shù)量,同時(shí)該結(jié)構(gòu)體包含該時(shí)間片下的定時(shí)器鏈表的鏈表頭部,,用來鏈接雙向鏈表,,鏈表選用Linux內(nèi)核所采用的嵌入式雙向鏈表結(jié)構(gòu),如式(1)所示:
struct list_head{
struct list_head *next, *prev} (1)
1.2 定時(shí)器的添加
用戶根據(jù)其需求在定時(shí)器池中加入定時(shí)器,,插入定時(shí)器之前所要做的工作有:
(1)計(jì)算定時(shí)器插入時(shí)間片,,每個(gè)定時(shí)器的插入時(shí)間片計(jì)算公式為:
timer->slot =(pool->cur_slot+timer->interval/
pool->time_slot )% pool->slot_num; (2)
式(2)中timer為要插入的定時(shí)器結(jié)構(gòu),其中的timer->slot為定時(shí)器插入的時(shí)間片,,pool->cur_slot為定時(shí)器池當(dāng)前所輪詢到的時(shí)間片,,time->interval為所要添加的定時(shí)器的定時(shí)時(shí)間間隔,pool->time_slot為每個(gè)時(shí)間片的長度,,pool->slot_num為定時(shí)器池的時(shí)間片總數(shù),。
(2)計(jì)算定時(shí)器的時(shí)間輪數(shù),每個(gè)定時(shí)器的時(shí)間輪數(shù)計(jì)算公式為:
timer->round=timer->interval/
(pool->time_slot*pool->slot_num) (3)
其中的timer->round為該定時(shí)器的時(shí)間輪數(shù),,通過式(3)得出定時(shí)器的時(shí)間輪數(shù),。
(3)用戶在添加定時(shí)器到定時(shí)器池中時(shí),需要指定定時(shí)器的超時(shí)時(shí)間,以及超時(shí)時(shí)間到達(dá)后所需要執(zhí)行的函數(shù),。同時(shí),,必須指定該定時(shí)器是一次性定時(shí)還是周期性定時(shí),以便管理線程刪除或者重新添加該定時(shí)器,。
1.3 定時(shí)器池的工作流程
創(chuàng)建并初始化定時(shí)器池,,此時(shí)內(nèi)存中保存著一個(gè)定時(shí)器池動(dòng)態(tài)管理單元,用戶通過相應(yīng)接口請求定時(shí)器池按其要求增加或者刪除定時(shí)器,。定時(shí)器池工作流程如圖3所示,。工作時(shí),內(nèi)部的定時(shí)器管理線程一直監(jiān)聽用戶請求,,同時(shí)管理線程等待系統(tǒng)的信號通知,,當(dāng)有信號通知到來時(shí),管理線程輪詢定時(shí)器池,查看池中已有的定時(shí)器池中是否有超時(shí)的定時(shí)器,,若有則按照用戶指定的動(dòng)作來執(zhí)行,。原因是:(1)可直接調(diào)用函數(shù),這種方法的優(yōu)點(diǎn)是不用產(chǎn)生線程的開銷;缺點(diǎn)是將占用定時(shí)器的時(shí)間,,并且若該函數(shù)執(zhí)行時(shí)間較長,,將嚴(yán)重影響定時(shí)器的性能。(2)產(chǎn)生線程來執(zhí)行該任務(wù),,這種方法的優(yōu)點(diǎn)是不占用定時(shí)器池的時(shí)間,,缺點(diǎn)是需要產(chǎn)生線程開銷[4]。
管理線程還將檢查定時(shí)器的屬性,,即該定時(shí)器是一次性定時(shí)還是周期性定時(shí),,如果是一次性定時(shí),當(dāng)定時(shí)器超時(shí)后,,管理線程將該定時(shí)器從鏈表結(jié)構(gòu)中移除,;如果是周期性定時(shí),當(dāng)超時(shí)后,,管理線程首先將定時(shí)器從鏈表結(jié)構(gòu)中移除,,然后計(jì)算該定時(shí)器池再次插入的時(shí)間片以及時(shí)間輪數(shù),得到以上數(shù)據(jù)后,,按照時(shí)間片數(shù)將定時(shí)器重新插入到相應(yīng)的鏈表中,,實(shí)現(xiàn)用戶的需求。
1.4 定時(shí)器的刪除
當(dāng)定時(shí)器時(shí)間到時(shí),,若為一次性定時(shí),,當(dāng)定時(shí)器超時(shí)后,管理線程自動(dòng)地將定時(shí)器從鏈表中移除,,釋放相關(guān)內(nèi)存,。但是,,當(dāng)用戶因?yàn)槟撤N需要在中途刪除未超時(shí)的一次性定時(shí)器或者刪除周期性定時(shí)器時(shí),此時(shí)需要調(diào)用定時(shí)器刪除函數(shù)來刪除定時(shí)器,。但是從定時(shí)器鏈表中尋找特定的定時(shí)器并非一件容易的事情,本文采用基于紅黑樹的形式,相應(yīng)的結(jié)構(gòu)體設(shè)計(jì)如下:
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)
在添加定時(shí)器時(shí),,會(huì)給每個(gè)定時(shí)器分配一個(gè)唯一的id來標(biāo)記定時(shí)器,該id存放在一張位圖表中,,將以O(shè)(1)的速度索取未用的id或者存儲到期回收的定時(shí)器id,。將該定時(shí)器id作為紅黑樹的鍵值key,將指向定時(shí)器的內(nèi)存結(jié)構(gòu)指針作為紅黑樹的data 數(shù)據(jù),。管理線程同時(shí)維護(hù)紅黑樹,。當(dāng)需要非正常刪除某個(gè)定時(shí)器時(shí),通過定時(shí)器的id找出其在紅黑樹中的位置,獲取定時(shí)器結(jié)構(gòu)在內(nèi)存中所在位置的指針,以便從定時(shí)器鏈表中刪除該定時(shí)器,。紅黑樹的查找性能保持在O(logn),,從而快速找出定時(shí)器指針?biāo)诩t黑樹的單元。
2 定時(shí)器池算法的實(shí)現(xiàn)
采用面向?qū)ο蟮乃枷?,頭文件.h中只包含用戶可以查看到基本的結(jié)構(gòu),,.c文件中包含實(shí)際的定時(shí)器池的內(nèi)部數(shù)據(jù)結(jié)構(gòu),這樣可以避免用戶操作結(jié)構(gòu)體中的數(shù)據(jù)成員[7],。
2.1 定時(shí)器池的函數(shù)接口
定時(shí)器的結(jié)構(gòu)數(shù)據(jù)如下:
struct timer_pool_s {
bool(*init)(struct timer_pool_s *pool, struct timer_pool_
conf *conf ); //初始化定時(shí)器結(jié)構(gòu)
timer_id(*add)(sturct timer_pool_s *this, struct timer
*timer, TIMER_TYPE type); //添加定時(shí)器
bool(*del )(struct timer_pool_s *pool, timer_id id);
//刪除定時(shí)器
void( *enable )( struct timer_pool_s *pool );
//使能定時(shí)器池
void(*disable )( struct timer_pool_s *pool);
//禁用定時(shí)器池
void(*start )(struct timer_pool_s *pool); //開啟定時(shí)器池
void ( *stop )( struct timer_pool_s *pool);
//關(guān)閉定時(shí)器池
};
2.2 定時(shí)器池的使用方法
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代表用戶想要添加的定時(shí)器,在該定時(shí)器結(jié)構(gòu)中設(shè)置了當(dāng)定時(shí)器超時(shí)后所要執(zhí)行的函數(shù)地址以及是用線程啟動(dòng)執(zhí)行該函數(shù),或是直接調(diào)用啟動(dòng)該函數(shù),。
3 性能測試
本定時(shí)器池使用雙向鏈表來管理各個(gè)定時(shí)器,,每次輪詢所有時(shí)間片所鏈接的定時(shí)器鏈表下的定時(shí)器將占用一些系統(tǒng)時(shí)間,故定時(shí)器池的最小時(shí)間片應(yīng)該大于輪詢鏈表中所有定時(shí)器的時(shí)間,,以及到期的定時(shí)器執(zhí)行相關(guān)動(dòng)作所需要的時(shí)間的總和,,因此定時(shí)器池不能無限地加入定時(shí)器。對于一個(gè)給定的時(shí)間片大小,,通過不斷對比測試可以找出該時(shí)間片大小下,,定時(shí)器池中最佳的定時(shí)器數(shù)量,定時(shí)器池中定時(shí)器的數(shù)量最少不應(yīng)少于5個(gè),,否則就與定時(shí)器池設(shè)計(jì)的初衷相左,。
(1)測試環(huán)境: Intel(R) Core(TM) i3-2100 CPU @ 2.8 GHz,2 GB內(nèi)存; Fedora 14(內(nèi)核2.6.35.14-106.fc14.i686 ),。
(2)測試設(shè)計(jì):測試時(shí)采用時(shí)間片粒度分別為40 ms, 80 ms,、200。每次測試時(shí),在系統(tǒng)尚未執(zhí)行timer_pool->start前將定時(shí)器加入到定時(shí)器池中,,在定時(shí)器池開啟后,,立刻獲取當(dāng)前時(shí)間,定時(shí)器超時(shí)后,,觸發(fā)超時(shí)執(zhí)行函數(shù)獲取當(dāng)時(shí)的時(shí)間,,記錄保存,。對于每個(gè)時(shí)間片都記錄兩組數(shù)據(jù),分別為定時(shí)器數(shù)目為5個(gè),、10個(gè),,每個(gè)定時(shí)器的定時(shí)時(shí)間分別為定時(shí)器時(shí)間片大小的1~N倍,N代表定時(shí)器數(shù)目,。測試的結(jié)果為某個(gè)時(shí)間片下定時(shí)器的相對誤差以及按時(shí)響應(yīng)的概率,其中按時(shí)響應(yīng)概率為準(zhǔn)時(shí)響應(yīng)的定時(shí)器個(gè)數(shù)占定時(shí)器總數(shù)(測試次數(shù)100次)的百分比,,相對誤差代表前后兩次定時(shí)任務(wù)的絕對誤差的差值,,體現(xiàn)定時(shí)器的穩(wěn)定性。每種情況測試100次,,同時(shí)包括了本文90%以上的測試結(jié)果,,并剔除了某些因?yàn)橄到y(tǒng)原因?qū)е陆Y(jié)果偏差太大的數(shù)據(jù)。定時(shí)器觸發(fā)方式分為部分周期性觸發(fā),、部分一次性觸發(fā),,定時(shí)器超時(shí)后,超時(shí)執(zhí)行方式為直接調(diào)用執(zhí)行[5-7],。測試結(jié)果如表1所示,。
由表1可見,當(dāng)定時(shí)器池的時(shí)間片較小時(shí),,池中定時(shí)器數(shù)目越少,,定時(shí)器池性能越好。隨著定時(shí)器數(shù)目的增加,,管理線程輪詢所需要的時(shí)間可能會(huì)超過一個(gè)時(shí)間片的長度,,造成定時(shí)器池在接收下一個(gè)時(shí)間片超時(shí)的信號延遲,從而導(dǎo)致定時(shí)器的性能急劇下降,。從表1中可以看到,,當(dāng)定時(shí)器池時(shí)間片≥40 ms時(shí),能夠較好地滿足性能需求,。因此選擇該定時(shí)器池的時(shí)間片最小不能低于40 ms,,并且定時(shí)器個(gè)數(shù)要控制在5個(gè)以內(nèi),否則定時(shí)器將不能保證及時(shí)被管理線程輪詢,,從而影響定時(shí)器池的效率,。另外,對于一些執(zhí)行時(shí)間特別長的執(zhí)行函數(shù),,此時(shí)應(yīng)該選用的執(zhí)行方式為線程執(zhí)行,,即定時(shí)器到時(shí)后,產(chǎn)生一個(gè)線程來執(zhí)行超時(shí)執(zhí)行函數(shù),。如果執(zhí)行函數(shù)需要較長時(shí)間,,則應(yīng)選用線程方式執(zhí)行,;如果時(shí)間相對較短,則可以采用直接調(diào)用方式,,但前提是不能影響到定時(shí)器池的性能,。
本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于時(shí)間輪以及紅黑樹的定時(shí)器池算法,可方便用戶統(tǒng)一管理大量的定時(shí)器,。對于定時(shí)器的添加,、刪除、查找,,以及輪詢等技術(shù)進(jìn)行了細(xì)致地分析,,提高了定時(shí)器池的響應(yīng)速度,以滿足不同場合的需求,。
參考文獻(xiàn)
[1] 趙汝聰,,謝維信. 一種新的嵌入式Linux高性能定時(shí)器實(shí)現(xiàn)方法[J].信號處理,2009,25(3):439-443.
[2] 趙紅武,,金瑜,,劉云生.一種改進(jìn)的定時(shí)器實(shí)現(xiàn)算法及其性能分析[J].微計(jì)算機(jī)應(yīng)用,2006,27(3):343-345.
[3] 唐靚. Linux 2.6細(xì)粒度定時(shí)器的設(shè)計(jì)[J].電腦知識與技術(shù), 2009,36(5):10259-10261.
[4] 晉磊,陳昌鵬,,陳凱,,等.Linux平臺下增強(qiáng)型定時(shí)器服務(wù)的研究[J]. 微型電腦應(yīng)用,2005,21(11):41-43.
[5] 林紹太,張會(huì).Linux定時(shí)器及其在網(wǎng)絡(luò)安全中的應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2004(10):63-64.
[6] 楊焓,,毛玉明. Linux用戶空間一種微秒級定時(shí)器的實(shí)現(xiàn)[C]. 2007中國西部青年通信學(xué)術(shù)會(huì)議,2007.
[7] STEVENS W R. UNIX網(wǎng)路編程(第2卷)[M].北京:人民郵電出版社,2010.