計時

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

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

封裝timer

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

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

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

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

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

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

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

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

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

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

代碼請看參考資料[1]

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

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

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

代碼:參考資料[1]

最小堆實現(xiàn)

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

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

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

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

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

紅黑樹實現(xiàn)

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

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

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

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

時間輪

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

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

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

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

分析下各種操作的時間復雜度

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

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

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

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

使用IO復用