計(jì)時(shí)

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

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

封裝timer

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

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

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

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

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

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

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

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

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

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

代碼請(qǐng)看參考資料[1]

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

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

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

代碼:參考資料[1]

最小堆實(shí)現(xiàn)

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

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

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

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

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

紅黑樹(shù)實(shí)現(xiàn)

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

紅黑樹(shù)對(duì)比堆查找特定的timer速度會(huì)快一點(diǎn)(參考[1]說(shuō)的)

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

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

時(shí)間輪

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

前文沒(méi)有分清定時(shí)器的概念,晚點(diǎn)再改TODO

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

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

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

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

添加:插入操作是對(duì)時(shí)間進(jìn)行取模放入那個(gè)槽中,時(shí)間復(fù)雜度也是O(1)

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

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

使用IO復(fù)用