計時

在linux中,一般由文件下的alarm函數(shù)和setitimer來設(shè)置定時器,到時間則發(fā)出SIGALARM,并調(diào)用指定的到期信號處理函數(shù),

signal(SIGALRM, handler);函數(shù)來設(shè)置到期事件處理函數(shù),而這個到期事件處理函數(shù)在游雙的書例子里可以看到,是定時器類里的tick函數(shù),即每隔一個周期調(diào)用tick()一次,注意要區(qū)分timer到期的回調(diào)函數(shù)和SIGALARM的回調(diào)函數(shù)

封裝timer

在服務(wù)器編程里,要處理定時事件,會封裝個定時器timer類,其中一般會包含到期時間和回調(diào)函數(shù),如muduo中timer.h的實現(xiàn),和l游雙書中的定時器那一章的種種例子,并根據(jù)不同實現(xiàn)方式增加額外的數(shù)據(jù)如鏈表的節(jié)點

而定時器應(yīng)該給出的用戶接口有注冊定時器,注銷定時器;注冊定時器應(yīng)增加區(qū)分重復(fù)定時器和一次性定時器

還應(yīng)該給出定期觸發(fā)的函數(shù),即上面提到的tick(),在tick函數(shù)里判斷timer里哪些是已經(jīng)過期的,觸發(fā)定時事件,根據(jù)定時器是否是重復(fù)的刪除或者重新設(shè)置此定時器

定時器實現(xiàn)類型

定時器會用到什么操作呢?它的插入,指定注銷,注銷到期的定時器,根據(jù)這幾點看一下如何設(shè)計定時器,ps.注意區(qū)分指定注銷和注銷到期,因為以下的實現(xiàn)大多是已經(jīng)排序好的,注銷到期的一般是從頭開始往下找,而指定注銷是注銷當(dāng)中某個節(jié)點的定時器

先說明libevent中的實現(xiàn)是最小堆,muduo是采用了紅黑樹來實現(xiàn),以下列出幾種類型的定時器實現(xiàn)

最簡單的實現(xiàn):雙向鏈表

直接利用鏈表實現(xiàn),每一個定時器作為一個鏈表的節(jié)點，這樣做最直觀,而幾種操作的復(fù)雜度是:

添加的時候就直接插入到鏈表末端，時間復(fù)雜度O(1)

找到到期timer,則需要遍歷全部,時間復(fù)雜度為O(n)

代碼請看參考資料[1]

優(yōu)化的鏈表:排序雙向鏈表

優(yōu)化操作:每次插入按到期時間進行排序,時間復(fù)雜度是:

插入為O(n),找到到期timer時間復(fù)雜度是O(1)的操作,指定timer刪除操作,是O(1)的復(fù)雜度,這也是為什么要用雙向鏈表的原因,直接傳入一個鏈表節(jié)點進行刪除,,ps:這里排序鏈表判斷到期雖然會有個while循環(huán),是為了找到地一個非過期并執(zhí)行前面過期的所有回調(diào)函數(shù),平均下來還是個O(1)的操作

代碼:參考資料[1]

最小堆實現(xiàn)

優(yōu)化點:最小堆的插入操作是log(n),參考下堆的插入操作:插入到堆最后面以后,進行上浮調(diào)整,最大調(diào)整次數(shù)為樹的高度,即log(n),

到期觸發(fā)的時間復(fù)雜度為O(1),及取最值,而堆這個結(jié)構(gòu)最適合做這個,在游雙的書中能看到,最小堆的實現(xiàn)alarm信號發(fā)送的時間設(shè)置成堆中最近的觸發(fā)時間,每次取完后其實還有個log(n)的heapify調(diào)整時間,估計參考資料[1]和游雙都把這個操作延后到平時(即延遲銷毀,游雙的書第11章第215頁)了,

,指定刪除操作則略微麻煩,這也是為什么muduo不采用這個方法的原因

(如果del_timer函數(shù)的參數(shù),傳入timer作參數(shù)直接刪除再堆化一下就行,如果傳入?yún)?shù)為定時器序號,則遍歷到再刪除為O(n),用一個map來存序號到定時器在堆中位置,則為時間O(1))(但是每次變換都)

代碼:參考資料[1]或者游雙的書

紅黑樹實現(xiàn)

muduo的實現(xiàn),順便提下,heap比起紅黑樹的好處是,像陳碩書中說的:內(nèi)存的局部性更好,參考資料[1]說的內(nèi)存使用率更好,且性能會相差一點,

紅黑樹對比堆查找特定的timer速度會快一點(參考[1]說的)

有時間復(fù)雜度就不分析了,muduo書中還提到了了一下set,map,multiset,multimap的選擇

代碼:參考muduo(直接用了現(xiàn)成的數(shù)據(jù)結(jié)構(gòu))或者參考資料[1]或者游雙的書

時間輪

時間輪的介紹先略過TODO在游雙的書中和陳碩的書中示例代碼部分都有提到,

前文沒有分清定時器的概念,晚點再改TODO

首先要把socket fd和定時器的指針加以封裝,以便刪除使用,即可以通過這個類來訪問fd和timer*,要刪除時間輪中的某個fd對應(yīng)的timer*我們直接訪問這個數(shù)據(jù)結(jié)構(gòu),在游雙的書里取名為client_data

封裝timer類,包括時間,到期執(zhí)行的回調(diào)函數(shù),這個類是以便時間輪使用,在時間輪中,我們是直接用timer*來排序使用的,

分析下各種操作的時間復(fù)雜度

插入:直接調(diào)用API傳入timer*,而時間輪里每個輪里的是鏈表,鏈表刪除直接O(1)

添加:插入操作是對時間進行取模放入那個槽中,時間復(fù)雜度也是O(1)

刪除:直接傳入timer*,O(1)

到期觸發(fā):是n個定時器,p個槽,根據(jù)哈希函數(shù)不同值均勻分布的特點,大概時間復(fù)雜度是O(n/p),游雙的書中稱之為:比O(n)好很多

使用IO復(fù)用