許 健,于鴻洋

（電子科技大學(xué) 電子科學(xué)技術(shù)研究院，四川 成都 611731)

定時(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)本身提供了多種用戶級(jí)定時(shí)器接口，其中精度較低的如Alarm函數(shù)，精度為秒級(jí)，能夠滿足一些定時(shí)精度低的應(yīng)用場(chǎng)合。但由于同一進(jìn)程中不能同時(shí)調(diào)用多個(gè)Alarm函數(shù)，因此應(yīng)用場(chǎng)合有限。Setitimer克服不能重復(fù)使用的缺點(diǎn)，同時(shí)將精度提高到毫秒級(jí)，但是同一個(gè)進(jìn)程中只能設(shè)置一個(gè)這種定時(shí)器。Timerfd是Linux為用戶程序提供的另一個(gè)定時(shí)器接口，這個(gè)接口基于文件描述符，能夠被用于select/poll的應(yīng)用場(chǎng)景，其精度可以達(dá)到納秒級(jí)，是用戶空間高精度定時(shí)器的理想選擇。本設(shè)計(jì)的定時(shí)器池基于時(shí)間輪原理,設(shè)定一個(gè)時(shí)間片大小作為時(shí)間間隔的基本單位，將時(shí)間輪分為固定時(shí)間片數(shù)，只需要一個(gè)Timerfd來(lái)管理該定時(shí)器池，設(shè)定超時(shí)時(shí)間間隔為時(shí)間片的大小，每次當(dāng)超過(guò)一個(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來(lái)設(shè)定定時(shí)的間隔時(shí)間大小。本定時(shí)器池的時(shí)間間隔為一個(gè)時(shí)間片time_slot大小。設(shè)定之后,管理線程等待系統(tǒng)的信號(hào)通知，系統(tǒng)每隔一個(gè)時(shí)間片就給定時(shí)器池發(fā)送一個(gè)信號(hào)，當(dāng)收到此信號(hào)時(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í)器池中的定時(shí)器組織形式

圖2中模擬了時(shí)間輪原理：用一個(gè)結(jié)構(gòu)體來(lái)保存一個(gè)時(shí)間片，以時(shí)間片作為定時(shí)器粒度的最小單位，以及該時(shí)間片下定時(shí)器的數(shù)量，同時(shí)該結(jié)構(gòu)體包含該時(shí)間片下的定時(shí)器鏈表的鏈表頭部，用來(lái)鏈接雙向鏈表，鏈表選用Linux內(nèi)核所采用的嵌入式雙向鏈表結(jié)構(gòu)，如式(1)所示：

1.2 定時(shí)器的添加

用戶根據(jù)其需求在定時(shí)器池中加入定時(shí)器，插入定時(shí)器之前所要做的工作有：

(1)計(jì)算定時(shí)器插入時(shí)間片，每個(gè)定時(shí)器的插入時(shí)間片計(jì)算公式為：

式(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í)間片的長(zhǎng)度，pool-＞slot_num為定時(shí)器池的時(shí)間片總數(shù)。

(2)計(jì)算定時(shí)器的時(shí)間輪數(shù)，每個(gè)定時(shí)器的時(shí)間輪數(shù)計(jì)算公式為：

其中的timer-＞round為該定時(shí)器的時(shí)間輪數(shù)，通過(guò)式(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)管理單元，用戶通過(guò)相應(yīng)接口請(qǐng)求定時(shí)器池按其要求增加或者刪除定時(shí)器。定時(shí)器池工作流程如圖3所示。工作時(shí)，內(nèi)部的定時(shí)器管理線程一直監(jiān)聽(tīng)用戶請(qǐng)求，同時(shí)管理線程等待系統(tǒng)的信號(hào)通知，當(dāng)有信號(hào)通知到來(lái)時(shí)，管理線程輪詢定時(shí)器池,查看池中已有的定時(shí)器池中是否有超時(shí)的定時(shí)器，若有則按照用戶指定的動(dòng)作來(lái)執(zhí)行。原因是：(1)可直接調(diào)用函數(shù)，這種方法的優(yōu)點(diǎn)是不用產(chǎn)生線程的開(kāi)銷;缺點(diǎn)是將占用定時(shí)器的時(shí)間，并且若該函數(shù)執(zhí)行時(shí)間較長(zhǎng)，將嚴(yán)重影響定時(shí)器的性能。(2)產(chǎn)生線程來(lái)執(zhí)行該任務(wù)，這種方法的優(yōu)點(diǎn)是不占用定時(shí)器池的時(shí)間，缺點(diǎn)是需要產(chǎn)生線程開(kāi)銷[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ù)來(lái)刪除定時(shí)器。但是從定時(shí)器鏈表中尋找特定的定時(shí)器并非一件容易的事情,本文采用基于紅黑樹(shù)的形式,相應(yīng)的結(jié)構(gòu)體設(shè)計(jì)如下：

圖3 定時(shí)器池工作流程圖

在添加定時(shí)器時(shí)，會(huì)給每個(gè)定時(shí)器分配一個(gè)唯一的id來(lái)標(biāo)記定時(shí)器，該id存放在一張位圖表中，將以O(shè)(1)的速度索取未用的id或者存儲(chǔ)到期回收的定時(shí)器id。將該定時(shí)器id作為紅黑樹(shù)的鍵值key，將指向定時(shí)器的內(nèi)存結(jié)構(gòu)指針作為紅黑樹(shù)的data數(shù)據(jù)。管理線程同時(shí)維護(hù)紅黑樹(shù)。當(dāng)需要非正常刪除某個(gè)定時(shí)器時(shí),通過(guò)定時(shí)器的id找出其在紅黑樹(shù)中的位置，獲取定時(shí)器結(jié)構(gòu)在內(nèi)存中所在位置的指針,以便從定時(shí)器鏈表中刪除該定時(shí)器。紅黑樹(shù)的查找性能保持在O(logn)，從而快速找出定時(shí)器指針?biāo)诩t黑樹(shù)的單元。

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ù)如下：

2.2 定時(shí)器池的使用方法

其中的your_timer代表用戶想要添加的定時(shí)器，在該定時(shí)器結(jié)構(gòu)中設(shè)置了當(dāng)定時(shí)器超時(shí)后所要執(zhí)行的函數(shù)地址以及是用線程啟動(dòng)執(zhí)行該函數(shù),或是直接調(diào)用啟動(dòng)該函數(shù)。

3 性能測(cè)試

表1 定時(shí)器池對(duì)比測(cè)試結(jié)果

本定時(shí)器池使用雙向鏈表來(lái)管理各個(gè)定時(shí)器，每次輪詢所有時(shí)間片所鏈接的定時(shí)器鏈表下的定時(shí)器將占用一些系統(tǒng)時(shí)間，故定時(shí)器池的最小時(shí)間片應(yīng)該大于輪詢鏈表中所有定時(shí)器的時(shí)間，以及到期的定時(shí)器執(zhí)行相關(guān)動(dòng)作所需要的時(shí)間的總和，因此定時(shí)器池不能無(wú)限地加入定時(shí)器。對(duì)于一個(gè)給定的時(shí)間片大小，通過(guò)不斷對(duì)比測(cè)試可以找出該時(shí)間片大小下，定時(shí)器池中最佳的定時(shí)器數(shù)量，定時(shí)器池中定時(shí)器的數(shù)量最少不應(yīng)少于5個(gè)，否則就與定時(shí)器池設(shè)計(jì)的初衷相左。

(1)測(cè)試環(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)測(cè)試設(shè)計(jì)：測(cè)試時(shí)采用時(shí)間片粒度分別為40 ms,80 ms、200。每次測(cè)試時(shí),在系統(tǒng)尚未執(zhí)行 timer_pool-＞start前將定時(shí)器加入到定時(shí)器池中，在定時(shí)器池開(kāi)啟后，立刻獲取當(dāng)前時(shí)間，定時(shí)器超時(shí)后，觸發(fā)超時(shí)執(zhí)行函數(shù)獲取當(dāng)時(shí)的時(shí)間，記錄保存。對(duì)于每個(gè)時(shí)間片都記錄兩組數(shù)據(jù)，分別為定時(shí)器數(shù)目為 5個(gè)、10個(gè)，每個(gè)定時(shí)器的定時(shí)時(shí)間分別為定時(shí)器時(shí)間片大小的1～N倍，N代表定時(shí)器數(shù)目。測(cè)試的結(jié)果為某個(gè)時(shí)間片下定時(shí)器的相對(duì)誤差以及按時(shí)響應(yīng)的概率，其中按時(shí)響應(yīng)概率為準(zhǔn)時(shí)響應(yīng)的定時(shí)器個(gè)數(shù)占定時(shí)器總數(shù) （測(cè)試次數(shù)100次）的百分比，相對(duì)誤差代表前后兩次定時(shí)任務(wù)的絕對(duì)誤差的差值，體現(xiàn)定時(shí)器的穩(wěn)定性。每種情況測(cè)試100次，同時(shí)包括了本文90%以上的測(cè)試結(jié)果，并剔除了某些因?yàn)橄到y(tǒng)原因?qū)е陆Y(jié)果偏差太大的數(shù)據(jù)。定時(shí)器觸發(fā)方式分為部分周期性觸發(fā)、部分一次性觸發(fā)，定時(shí)器超時(shí)后，超時(shí)執(zhí)行方式為直接調(diào)用執(zhí)行[5-7]。測(cè)試結(jié)果如表1所示。

由表1可見(jiàn)，當(dāng)定時(shí)器池的時(shí)間片較小時(shí)，池中定時(shí)器數(shù)目越少，定時(shí)器池性能越好。隨著定時(shí)器數(shù)目的增加，管理線程輪詢所需要的時(shí)間可能會(huì)超過(guò)一個(gè)時(shí)間片的長(zhǎng)度，造成定時(shí)器池在接收下一個(gè)時(shí)間片超時(shí)的信號(hào)延遲，從而導(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í)器池的效率。另外，對(duì)于一些執(zhí)行時(shí)間特別長(zhǎng)的執(zhí)行函數(shù)，此時(shí)應(yīng)該選用的執(zhí)行方式為線程執(zhí)行，即定時(shí)器到時(shí)后，產(chǎn)生一個(gè)線程來(lái)執(zhí)行超時(shí)執(zhí)行函數(shù)。如果執(zhí)行函數(shù)需要較長(zhǎng)時(shí)間，則應(yīng)選用線程方式執(zhí)行；如果時(shí)間相對(duì)較短，則可以采用直接調(diào)用方式，但前提是不能影響到定時(shí)器池的性能。

本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于時(shí)間輪以及紅黑樹(shù)的定時(shí)器池算法，可方便用戶統(tǒng)一管理大量的定時(shí)器。對(duì)于定時(shí)器的添加、刪除、查找，以及輪詢等技術(shù)進(jìn)行了細(xì)致地分析，提高了定時(shí)器池的響應(yīng)速度，以滿足不同場(chǎng)合的需求。

[1]趙汝聰，謝維信.一種新的嵌入式Linux高性能定時(shí)器實(shí)現(xiàn)方法[J].信號(hào)處理，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í)與技術(shù),2009,36(5):10259-10261.

[4]晉磊，陳昌鵬，陳凱，等.Linux平臺(tái)下增強(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用戶空間一種微秒級(jí)定時(shí)器的實(shí)現(xiàn)[C].2007中國(guó)西部青年通信學(xué)術(shù)會(huì)議,2007.

[7]STEVENS W R.UNIX網(wǎng)路編程(第 2卷)[M].北京：人民郵電出版社,2010.