|
linux下多定時器的實(shí)現(xiàn) 原文參見my blog:http://blog./u3/94771/showart_2000555.html 一、已有的定時器接口 時空管理是計(jì)算機(jī)系統(tǒng)的主要任務(wù)。在時間管理中，我們經(jīng)常利用定時器處理事情：比如tcp協(xié)議中利用定時器管理包超時，視頻顯示中利用定時器來定時顯示視頻幀，web服務(wù)中利用定時器來管理用戶的超時。windows系統(tǒng)提供了SetTimer和timeSetEvent等定時器接口，linux中則提供了setitimer等接口。這些函數(shù)的接口很類似，大體上都是用戶提供回調(diào)函數(shù)和超時時間向OS注冊一個定時器事件，OS在超時時間到了的時候，調(diào)用用戶提供的回調(diào)函數(shù)來完成用戶想要做的事情。windows下的接口支持單進(jìn)程中擁有多個定時器，而linux則只允許單進(jìn)程擁有一個定時器，因此在linux下的單進(jìn)程中要使用多個定時器，則需要自己維護(hù)管理，這是本文寫作的出發(fā)點(diǎn)。另外，OS提供的定時器管理算法在大規(guī)模定時器的管理方面可能還不盡人意，這時候就需要用戶去優(yōu)化管理算法了，本文在這方面提供了一點(diǎn)素材。 二、一個最簡單的多定時器的實(shí)現(xiàn)（linux版） 1、實(shí)現(xiàn)細(xì)節(jié) 這個實(shí)現(xiàn)允許用戶使用多個自定義的定時器，每個自定義的定時器將周期地被觸發(fā)直到其被刪除。實(shí)現(xiàn)的主要思路是： i）首先在初始化多定時器（init_mul_timer）時利用setitimer注冊一個基本的時間單位（如1s）的定時事件； ii）用戶需要set_a_timer注冊自定義定時器時，在timer_manage管理結(jié)構(gòu)中記錄這個定時器的回調(diào)函數(shù)和定時周期等參數(shù)； iii）當(dāng)基本的時間單位到期后（如SIGALRM信號到達(dá)時），遍歷整個timer_manage，如果有自定義定時器的超時時間到了，就執(zhí)行相應(yīng)的回調(diào)函數(shù)，并將自定義定時器的超時時間置為最初值；否則將自定義定時器的超時時間相應(yīng)地減一個基本的時間單位； iv）用戶通過del_a_timer來刪除某個定時器，通 過destroy_mul_timer來刪除整個多定時器。 2、代碼 見附件 3、缺陷 i)新建定時器、遍歷定時器和刪除定時器（查找哪個定時器超時）時時間復(fù)雜度都為O(n)（n是定時器的個數(shù)）; ii)適用環(huán)境是單線程環(huán)境，如要用于多線程，需添加同步操作。 iii)程序中有些小bug，如對新建超時時間為0的定時器沒有妥善的處理。 三、多定時器的改進(jìn)版 1、思路 改進(jìn)定時器的實(shí)現(xiàn)，即是改善二種所指出的幾個缺陷，如下是一個改進(jìn)版,主要是將遍歷超時時間的時間復(fù)雜度降為了O(1). 改善思路:各定時器以一個鏈表的形式組織起來,除鏈表頭定時器的超時時間是用絕對時間紀(jì)錄的外,其它定時器的超時時間均用相對時間(即超時時間-前一個定時器的超時時間)紀(jì)錄. 注意,各定時器都是一次性的,當(dāng)定時器的超時被處理后,定時器將被自動刪除.另外如果將定時器的結(jié)點(diǎn)改為雙向結(jié)構(gòu),可以將刪除定時器的時間復(fù)雜度降為O(1). 2、數(shù)據(jù)結(jié)構(gòu) 每個定時器都有一個唯一的ID,這個ID是如下的結(jié)構(gòu)體:
ptr紀(jì)錄的是定時器結(jié)點(diǎn)的地址,entry_id則是一個自多定時器初始化后自增的id.ptr和entry_id一起組成定時器結(jié)點(diǎn)的key ,一方面使得新建定時器時生成key的過程大為簡化,另一方面使得刪除定時器的時間復(fù)雜度降為O(1)（前提是定時器結(jié)點(diǎn)采用雙向結(jié)構(gòu)）。 定時器結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
其中的is_use是用來防止這樣一種情況：用戶在回調(diào)函數(shù)中調(diào)用kill_timer來刪除定時器，這個時候kill_timer和遍歷定時器中都有刪除結(jié)點(diǎn)的操作，有可能將整個鏈表搞混亂。所以在調(diào)用用戶的回調(diào)函數(shù)前先將is_use置1，在kill_timer中需檢查is_use，只有在is_use為0的情況下，才執(zhí)行清理定時器結(jié)點(diǎn)的操作。 3、代碼（windows版） 見附件。 3、缺陷 i)新建定時器的時間復(fù)雜度為O(n),刪除定時器的時間復(fù)雜度也為O(n)(簡單地將定時器結(jié)點(diǎn)改為雙向結(jié)構(gòu),可將復(fù)雜度降為O(1)); ii)不能用于多線程環(huán)境 四 、多定時器的工業(yè)級實(shí)現(xiàn) 1、time wheelz算法 以前的BSD內(nèi)核以及現(xiàn)在的linux內(nèi)核的實(shí)現(xiàn)與三中所用算法相似（未實(shí)證，只是據(jù)說），據(jù)說現(xiàn)在的BSD內(nèi)核已采用了較好的time wheelz算法。 time wheez算法的優(yōu)點(diǎn)： i)將新建定時器的時間復(fù)雜度降近似為O(1)。它根據(jù)定時器的超時值，將新定時器散列到hash桶中； ii)遍歷檢查定時器的時間復(fù)雜度也近似為O(桶大小)，如果散列均勻。 iii)刪除定時器的時間復(fù)雜度近似為O(1)，通過hash算法或臨時存儲（空間換時間的算法）。 2、time wheelz的實(shí)現(xiàn) 請參考文末給出的兩個論文，慚愧得很，文章我也只是稍微瞄了下，以后有用得著的時候再深究吧。 五、參考文章 1、Adam M. Costello and George Varghess, "Redesigning the BSD Callout andTimer Facilities". 1995.11,這篇文章實(shí)現(xiàn)了用timewheelz算法改善BSD內(nèi)核的定時器算法，google一下，有免費(fèi)下載； 2、George Varghess, AnthonyLauch, "Hashed and Hierarchical Timing Wheels: Efficient DataStructures for Implementing a Timer Facility". IEEE:1997.12，這個看作者有沒有提供免費(fèi)下載了，否則是要從IEEE那里獲取了~~ [ 本帖最后由 bripengandre 于 2009-7-19 17:49 編輯 ] |
|
|
