計(jì)時(shí)
在linux中,一般由文件下的alarm函數(shù)和setitimer來設(shè)置定時(shí)器,到時(shí)間則發(fā)出SIGALARM,并調(diào)用指定的到期信號處理函數(shù),
signal(SIGALRM, handler);函數(shù)來設(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)該給出的用戶接口有注冊定時(shí)器,注銷定時(shí)器;注冊定時(shí)器應(yīng)增加區(qū)分重復(fù)定時(shí)器和一次性定時(shí)器
還應(yīng)該給出定期觸發(fā)的函數(shù),即上面提到的tick(),在tick函數(shù)里判斷timer里哪些是已經(jīng)過期的,觸發(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)排序好的,注銷到期的一般是從頭開始往下找,而指定注銷是注銷當(dāng)中某個(gè)節(jié)點(diǎn)的定時(shí)器
先說明libevent中的實(shí)現(xiàn)是最小堆,muduo是采用了紅黑樹來實(shí)現(xiàn),以下列出幾種類型的定時(shí)器實(shí)現(xiàn)
最簡單的實(shí)現(xiàn):雙向鏈表
直接利用鏈表實(shí)現(xiàn),每一個(gè)定時(shí)器作為一個(gè)鏈表的節(jié)點(diǎn)，這樣做最直觀,而幾種操作的復(fù)雜度是:
添加的時(shí)候就直接插入到鏈表末端，時(shí)間復(fù)雜度O(1)
找到到期timer,則需要遍歷全部,時(shí)間復(fù)雜度為O(n)
代碼請看參考資料[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è)非過期并執(zhí)行前面過期的所有回調(diào)函數(shù),平均下來還是個(gè)O(1)的操作
代碼:參考資料[1]
最小堆實(shí)現(xiàn)
優(yōu)化點(diǎn):最小堆的插入操作是log(n),參考下堆的插入操作:插入到堆最后面以后,進(jìn)行上浮調(diào)整,最大調(diào)整次數(shù)為樹的高度,即log(n),
到期觸發(fā)的時(shí)間復(fù)雜度為O(1),及取最值,而堆這個(gè)結(jié)構(gòu)最適合做這個(gè),在游雙的書中能看到,最小堆的實(shí)現(xiàn)alarm信號發(fā)送的時(shí)間設(shè)置成堆中最近的觸發(fā)時(shí)間,每次取完后其實(shí)還有個(gè)log(n)的heapify調(diào)整時(shí)間,估計(jì)參考資料[1]和游雙都把這個(gè)操作延后到平時(shí)(即延遲銷毀,游雙的書第11章第215頁)了,
,指定刪除操作則略微麻煩,這也是為什么muduo不采用這個(gè)方法的原因
(如果del_timer函數(shù)的參數(shù),傳入timer作參數(shù)直接刪除再堆化一下就行,如果傳入?yún)?shù)為定時(shí)器序號,則遍歷到再刪除為O(n),用一個(gè)map來存序號到定時(shí)器在堆中位置,則為時(shí)間O(1))(但是每次變換都)
代碼:參考資料[1]或者游雙的書
紅黑樹實(shí)現(xiàn)
muduo的實(shí)現(xiàn),順便提下,heap比起紅黑樹的好處是,像陳碩書中說的:內(nèi)存的局部性更好,參考資料[1]說的內(nèi)存使用率更好,且性能會(huì)相差一點(diǎn),
紅黑樹對比堆查找特定的timer速度會(huì)快一點(diǎn)(參考[1]說的)
有時(shí)間復(fù)雜度就不分析了,muduo書中還提到了了一下set,map,multiset,multimap的選擇
代碼:參考muduo(直接用了現(xiàn)成的數(shù)據(jù)結(jié)構(gòu))或者參考資料[1]或者游雙的書
時(shí)間輪
時(shí)間輪的介紹先略過TODO在游雙的書中和陳碩的書中示例代碼部分都有提到,
前文沒有分清定時(shí)器的概念,晚點(diǎn)再改TODO
首先要把socket fd和定時(shí)器的指針加以封裝,以便刪除使用,即可以通過這個(gè)類來訪問fd和timer*,要?jiǎng)h除時(shí)間輪中的某個(gè)fd對應(yīng)的timer*我們直接訪問這個(gè)數(shù)據(jù)結(jié)構(gòu),在游雙的書里取名為client_data
封裝timer類,包括時(shí)間,到期執(zhí)行的回調(diào)函數(shù),這個(gè)類是以便時(shí)間輪使用,在時(shí)間輪中,我們是直接用timer*來排序使用的,
分析下各種操作的時(shí)間復(fù)雜度
插入:直接調(diào)用API傳入timer*,而時(shí)間輪里每個(gè)輪里的是鏈表,鏈表刪除直接O(1)
添加:插入操作是對時(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ù)用
下載文檔
