2021-11-10
創(chuàng)新互聯(lián)主營(yíng)策勒網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,App定制開發(fā),策勒h5微信小程序搭建,策勒網(wǎng)站營(yíng)銷推廣歡迎策勒等地區(qū)企業(yè)咨詢
列表是一種非連續(xù)的存儲(chǔ)容器，有多個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)通過一些變量記錄彼此之間的關(guān)系
單鏈表和雙鏈表就是列表的兩種方法。
原理：A、B、C三個(gè)人，B懂A的電話，C懂B的電話只是單方知道號(hào)碼，這樣就形成了一個(gè)單鏈表結(jié)構(gòu)。
如果C把自己的號(hào)碼給B，B把自己的號(hào)碼給A，因?yàn)槭请p方都知道對(duì)方的號(hào)碼，這樣就形成了一個(gè)雙鏈表結(jié)構(gòu)
如果B換號(hào)碼了，他需要通知AC，把自己的號(hào)碼刪了，這個(gè)過程就是列表的刪除操作。
在Go語(yǔ)言中，列表使用 container/list 包來實(shí)現(xiàn)，內(nèi)部的實(shí)現(xiàn)原理是雙鏈表，列表能夠高效地進(jìn)行任意位置的元素插入和刪除操作。
列表初始化的兩種辦法
列表沒有給出具體的元素類型的限制，所以列表的元素可以是任意類型的，
例如給列表中放入了一個(gè) interface{} 類型的值，取出值后，如果要將 interface{} 轉(zhuǎn)換為其他類型將會(huì)發(fā)生宕機(jī)。
雙鏈表支持從隊(duì)列前方或后方插入元素，分別對(duì)應(yīng)的方法是 PushFront 和 PushBack。
列表插入函數(shù)的返回值會(huì)提供一個(gè) *list.Element 結(jié)構(gòu)，這個(gè)結(jié)構(gòu)記錄著列表元素的值以及與其他節(jié)點(diǎn)之間的關(guān)系等信息，從列表中刪除元素時(shí)，需要用到這個(gè)結(jié)構(gòu)進(jìn)行快速刪除。
遍歷完也能看到最后的結(jié)果
學(xué)習(xí)地址：
基本設(shè)計(jì)思路：
類型轉(zhuǎn)換、類型斷言、動(dòng)態(tài)派發(fā)。iface，eface。
反射對(duì)象具有的方法：
編譯優(yōu)化：
內(nèi)部實(shí)現(xiàn)：
實(shí)現(xiàn) Context 接口有以下幾個(gè)類型（空實(shí)現(xiàn)就忽略了）：
互斥鎖的控制邏輯：
設(shè)計(jì)思路：
（以上為寫被讀阻塞，下面是讀被寫阻塞）
總結(jié)，讀寫鎖的設(shè)計(jì)還是非常巧妙的：
設(shè)計(jì)思路：
WaitGroup 有三個(gè)暴露的函數(shù):
部件：
設(shè)計(jì)思路：
結(jié)構(gòu)：
Once 只暴露了一個(gè)方法：
實(shí)現(xiàn)：
三個(gè)關(guān)鍵點(diǎn)：
細(xì)節(jié)：
讓多協(xié)程任務(wù)的開始執(zhí)行時(shí)間可控（按順序或歸一）。（Context 是控制結(jié)束時(shí)間）
設(shè)計(jì)思路： 通過一個(gè)鎖和內(nèi)置的 notifyList 隊(duì)列實(shí)現(xiàn)，Wait() 會(huì)生成票據(jù)，并將等待協(xié)程信息加入鏈表中，等待控制協(xié)程中發(fā)送信號(hào)通知一個(gè)（Signal()）或所有（Boardcast()）等待者（內(nèi)部實(shí)現(xiàn)是通過票據(jù)通知的）來控制協(xié)程解除阻塞。
暴露四個(gè)函數(shù)：
實(shí)現(xiàn)細(xì)節(jié)：
部件：
包： golang.org/x/sync/errgroup
作用：開啟 func() error 函數(shù)簽名的協(xié)程，在同 Group 下協(xié)程并發(fā)執(zhí)行過程并收集首次 err 錯(cuò)誤。通過 Context 的傳入，還可以控制在首次 err 出現(xiàn)時(shí)就終止組內(nèi)各協(xié)程。
設(shè)計(jì)思路：
結(jié)構(gòu)：
暴露的方法：
實(shí)現(xiàn)細(xì)節(jié)：
注意問題：
包： "golang.org/x/sync/semaphore"
作用：排隊(duì)借資源（如錢，有借有還）的一種場(chǎng)景。此包相當(dāng)于對(duì)底層信號(hào)量的一種暴露。
設(shè)計(jì)思路：有一定數(shù)量的資源 Weight，每一個(gè) waiter 攜帶一個(gè) channel 和要借的數(shù)量 n。通過隊(duì)列排隊(duì)執(zhí)行借貸。
結(jié)構(gòu)：
暴露方法：
細(xì)節(jié)：
部件：
細(xì)節(jié)：
包： "golang.org/x/sync/singleflight"
作用：防擊穿。瞬時(shí)的相同請(qǐng)求只調(diào)用一次，response 被所有相同請(qǐng)求共享。
設(shè)計(jì)思路：按請(qǐng)求的 key 分組（一個(gè) *call 是一個(gè)組，用 map 映射存儲(chǔ)組），每個(gè)組只進(jìn)行一次訪問，組內(nèi)每個(gè)協(xié)程會(huì)獲得對(duì)應(yīng)結(jié)果的一個(gè)拷貝。
結(jié)構(gòu)：
邏輯：
細(xì)節(jié)：
部件：
如有錯(cuò)誤，請(qǐng)批評(píng)指正。
準(zhǔn)備好linux編程環(huán)境,現(xiàn)場(chǎng)手撕定時(shí)器實(shí)現(xiàn)【linux服務(wù)器開發(fā)】
工程師的圣地—Linux內(nèi)核， 談?wù)剝?nèi)核的架構(gòu)
c/c++ linux服務(wù)器開發(fā)學(xué)習(xí)地址：C/C++Linux服務(wù)器開發(fā)/后臺(tái)架構(gòu)師【零聲教育】-學(xué)習(xí)視頻教程-騰訊課堂
上圖是5個(gè)時(shí)間輪級(jí)聯(lián)的效果圖。中間的大輪是工作輪，只有在它上的任務(wù)才會(huì)被執(zhí)行；其他輪上的任務(wù)時(shí)間到后遷移到下一級(jí)輪上，他們最終都會(huì)遷移到工作輪上而被調(diào)度執(zhí)行。
多級(jí)時(shí)間輪的原理也容易理解：就拿時(shí)鐘做說明，秒針轉(zhuǎn)動(dòng)一圈分針轉(zhuǎn)動(dòng)一格；分針轉(zhuǎn)動(dòng)一圈時(shí)針轉(zhuǎn)動(dòng)一格；同理時(shí)間輪也是如此：當(dāng)?shù)图?jí)輪轉(zhuǎn)動(dòng)一圈時(shí)，高一級(jí)輪轉(zhuǎn)動(dòng)一格，同時(shí)會(huì)將高一級(jí)輪上的任務(wù)重新分配到低級(jí)輪上。從而實(shí)現(xiàn)了多級(jí)輪級(jí)聯(lián)的效果。
1.1 多級(jí)時(shí)間輪對(duì)象
多級(jí)時(shí)間輪應(yīng)該至少包括以下內(nèi)容：
每一級(jí)時(shí)間輪對(duì)象
輪子上指針的位置
關(guān)于輪子上指針的位置有一個(gè)比較巧妙的辦法：那就是位運(yùn)算。比如定義一個(gè)無(wú)符號(hào)整型的數(shù)：
通過獲取當(dāng)前的系統(tǒng)時(shí)間便可以通過位操作轉(zhuǎn)換為時(shí)間輪上的時(shí)間，通過與實(shí)際時(shí)間輪上的時(shí)間作比較，從而確定時(shí)間輪要前進(jìn)調(diào)度的時(shí)間，進(jìn)而操作對(duì)應(yīng)時(shí)間輪槽位對(duì)應(yīng)的任務(wù)。
為什么至少需要這兩個(gè)成員呢？
定義多級(jí)時(shí)間輪，首先需要明確的便是級(jí)聯(lián)的層數(shù)，也就是說需要確定有幾個(gè)時(shí)間輪。
輪子上指針位置，就是當(dāng)前時(shí)間輪運(yùn)行到的位置，它與真實(shí)時(shí)間的差便是后續(xù)時(shí)間輪需要調(diào)度執(zhí)行，它們的差值是時(shí)間輪運(yùn)作起來的驅(qū)動(dòng)力。
多級(jí)時(shí)間輪對(duì)象的定義
//實(shí)現(xiàn)5級(jí)時(shí)間輪 范圍為0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_base{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadID; struct tvec_root tv1; /*第一個(gè)輪*/ struct tvec tv2; /*第二個(gè)輪*/ struct tvec tv3; /*第三個(gè)輪*/ struct tvec tv4; /*第四個(gè)輪*/ struct tvec tv5; /*第五個(gè)輪*/};
1.2 時(shí)間輪對(duì)象
我們知道每一個(gè)輪子實(shí)際上都是一個(gè)哈希表，上面我們只是實(shí)例化了五個(gè)輪子的對(duì)象，但是五個(gè)輪子具體包含什么，有幾個(gè)槽位等等沒有明確(即struct tvec和struct tvec_root)。
#define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1
此外，每一個(gè)時(shí)間輪都是哈希表，因此它的類型應(yīng)該至少包含兩個(gè)指針域來實(shí)現(xiàn)雙向鏈表的功能。這里我們?yōu)榱朔奖闶褂猛ㄓ玫膕truct list_head的雙向鏈表結(jié)構(gòu)。
1.3 定時(shí)任務(wù)對(duì)象
定時(shí)器的主要工作是為了在未來的特定時(shí)間完成某項(xiàng)任務(wù)，而這個(gè)任務(wù)經(jīng)常包含以下內(nèi)容：
任務(wù)的處理邏輯(回調(diào)函數(shù))
任務(wù)的參數(shù)
雙向鏈表節(jié)點(diǎn)
到時(shí)時(shí)間
定時(shí)任務(wù)對(duì)象的定義
typedef void (*timeouthandle)(unsigned long ); struct timer_list{ struct list_head entry; //將時(shí)間連接成鏈表 unsigned long expires; //超時(shí)時(shí)間 void (*function)(unsigned long); //超時(shí)后的處理函數(shù) unsigned long data; //處理函數(shù)的參數(shù) struct tvec_base *base; //指向時(shí)間輪};
在時(shí)間輪上的效果圖：
【文章福利】需要C/C++ Linux服務(wù)器架構(gòu)師學(xué)習(xí)資料加群812855908（資料包括C/C++，Linux，golang技術(shù)，內(nèi)核，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK，ffmpeg等）
1.4 雙向鏈表
在時(shí)間輪上我們采用雙向鏈表的數(shù)據(jù)類型。采用雙向鏈表的除了操作上比單鏈表復(fù)雜，多占一個(gè)指針域外沒有其他不可接收的問題。而多占一個(gè)指針域在今天大內(nèi)存的時(shí)代明顯不是什么問題。至于雙向鏈表操作的復(fù)雜性，我們可以通過使用通用的struct list結(jié)構(gòu)來解決，因?yàn)殡p向鏈表有眾多的標(biāo)準(zhǔn)操作函數(shù)，我們可以通過直接引用list.h頭文件來使用他們提供的接口。
struct list可以說是一個(gè)萬(wàn)能的雙向鏈表操作框架，我們只需要在自定義的結(jié)構(gòu)中定義一個(gè)struct list對(duì)象即可使用它的標(biāo)準(zhǔn)操作接口。同時(shí)它還提供了一個(gè)類似container_of的接口，在應(yīng)用層一般叫做list_entry，因此我們可以很方便的通過struct list成員找到自定義的結(jié)構(gòu)體的起始地址。
關(guān)于應(yīng)用層的log.h, 我將在下面的代碼中附上該文件。如果需要內(nèi)核層的實(shí)現(xiàn)，可以直接從linux源碼中獲取。
1.5 聯(lián)結(jié)方式
多級(jí)時(shí)間輪效果圖：
二. 多級(jí)時(shí)間輪C語(yǔ)言實(shí)現(xiàn)
2.1 雙向鏈表頭文件: list.h
提到雙向鏈表，很多的源碼工程中都會(huì)實(shí)現(xiàn)一系列的統(tǒng)一的雙向鏈表操作函數(shù)。它們?yōu)殡p向鏈表封裝了統(tǒng)計(jì)的接口，使用者只需要在自定義的結(jié)構(gòu)中添加一個(gè)struct list_head結(jié)構(gòu)，然后調(diào)用它們提供的接口，便可以完成雙向鏈表的所有操作。這些操作一般都在list.h的頭文件中實(shí)現(xiàn)。Linux源碼中也有實(shí)現(xiàn)（內(nèi)核態(tài)的實(shí)現(xiàn)）。他們實(shí)現(xiàn)的方式基本完全一樣，只是實(shí)現(xiàn)的接口數(shù)量和功能上稍有差別?？梢哉f這個(gè)list.h文件是學(xué)習(xí)操作雙向鏈表的不二選擇，它幾乎實(shí)現(xiàn)了所有的操作：增、刪、改、查、遍歷、替換、清空等等。這里我拼湊了一個(gè)源碼中的log.h函數(shù)，終于湊夠了多級(jí)時(shí)間輪中使用到的接口。
#if !defined(_BLKID_LIST_H) !defined(LIST_HEAD)#define _BLKID_LIST_H#ifdef __cplusplus extern "C" {#endif/* * Simple doubly linked list implementation. * * Some of the internal functions ("__xxx") are useful when * manipulating whole lists rather than single entries, as * sometimes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */struct list_head { struct list_head *next, *prev;};#define LIST_HEAD_INIT(name) { (name), (name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)#define INIT_LIST_HEAD(ptr) do { \ (ptr)-next = (ptr); (ptr)-prev = (ptr); \} while (0)static inline void__list_add(struct list_head *entry, struct list_head *prev, struct list_head *next){ next-prev = entry; entry-next = next; entry-prev = prev; prev-next = entry;}/** * Insert a new element after the given list head. The new element does not * need to be initialised as empty list. * The list changes from: * head → some element → ... * to * head → new element → older element → ... * * Example: * struct foo *newfoo = malloc(...); * list_add(newfoo-entry, bar-list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */static inline voidlist_add(struct list_head *entry, struct list_head *head){ __list_add(entry, head, head-next);}/** * Append a new element to the end of the list given with this list head. * * The list changes from: * head → some element → ... → lastelement * to * head → some element → ... → lastelement → new element * * Example: * struct foo *newfoo = malloc(...); * list_add_tail(newfoo-entry, bar-list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */static inline voidlist_add_tail(struct list_head *entry, struct list_head *head){ __list_add(entry, head-prev, head);}static inline void__list_del(struct list_head *prev, struct list_head *next){ next-prev = prev; prev-next = next;}/** * Remove the element from the list it is in. Using this function will reset * the pointers to/from this element so it is removed from the list. It does * NOT free the element itself or manipulate it otherwise. * * Using list_del on a pure list head (like in the example at the top of * this file) will NOT remove the first element from * the list but rather reset the list as empty list. * * Example: * list_del(foo-entry); * * @param entry The element to remove. */static inline voidlist_del(struct list_head *entry){ __list_del(entry-prev, entry-next);}static inline voidlist_del_init(struct list_head *entry){ __list_del(entry-prev, entry-next); INIT_LIST_HEAD(entry);}static inline void list_move_tail(struct list_head *list, struct list_head *head){ __list_del(list-prev, list-next); list_add_tail(list, head);}/** * Check if the list is empty. * * Example: * list_empty(bar-list_of_foos); * * @return True if the list contains one or more elements or False otherwise. */static inline intlist_empty(struct list_head *head){ return head-next == head;}/** * list_replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * If @old was empty, it will be overwritten. */static inline void list_replace(struct list_head *old, struct list_head *new){ new-next = old-next; new-next-prev = new; new-prev = old-prev; new-prev-next = new;}/** * Retrieve the first list entry for the given list pointer. * * Example: * struct foo *first; * first = list_first_entry(bar-list_of_foos, struct foo, list_of_foos); * * @param ptr The list head * @param type Data type of the list element to retrieve * @param member Member name of the struct list_head field in the list element. * @return A pointer to the first list element. */#define list_first_entry(ptr, type, member) \ list_entry((ptr)-next, type, member)static inline void list_replace_init(struct list_head *old, struct list_head *new){ list_replace(old, new); INIT_LIST_HEAD(old);}/** * list_entry - get the struct for this entry * @ptr: the struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(((type *)0)-member)))/** * list_for_each - iterate over elements in a list * @pos: the struct list_head to use as a loop counter. * @head: the head for your list. */#define list_for_each(pos, head) \ for (pos = (head)-next; pos != (head); pos = pos-next)/** * list_for_each_safe - iterate over elements in a list, but don't dereference * pos after the body is done (in case it is freed) * @pos: the struct list_head to use as a loop counter. * @pnext: the struct list_head to use as a pointer to the next item. * @head: the head for your list (not included in iteration). */#define list_for_each_safe(pos, pnext, head) \ for (pos = (head)-next, pnext = pos-next; pos != (head); \ pos = pnext, pnext = pos-next)#ifdef __cplusplus}#endif#endif /* _BLKID_LIST_H */
這里面一般會(huì)用到一個(gè)重要實(shí)現(xiàn)：container_of, 它的原理這里不敘述
2.2 調(diào)試信息頭文件: log.h
這個(gè)頭文件實(shí)際上不是必須的，我只是用它來添加調(diào)試信息(代碼中的errlog(), log()都是log.h中的宏函數(shù))。它的效果是給打印的信息加上顏色，效果如下：
log.h的代碼如下：
#ifndef _LOG_h_#define _LOG_h_#include #define COL(x) "\033[;" #x "m"#define RED COL(31)#define GREEN COL(32)#define YELLOW COL(33)#define BLUE COL(34)#define MAGENTA COL(35)#define CYAN COL(36)#define WHITE COL(0)#define GRAY "\033[0m"#define errlog(fmt, arg...) do{ \ printf(RED"[#ERROR: Toeny Sun:"GRAY YELLOW" %s:%d]:"GRAY WHITE fmt GRAY, __func__, __LINE__, ##arg);\}while(0)#define log(fmt, arg...) do{ \ printf(WHITE"[#DEBUG: Toeny Sun: "GRAY YELLOW"%s:%d]:"GRAY WHITE fmt GRAY, __func__, __LINE__, ##arg);\}while(0)#endif
2.3 時(shí)間輪代碼: timewheel.c
/* *毫秒定時(shí)器 采用多級(jí)時(shí)間輪方式 借鑒linux內(nèi)核中的實(shí)現(xiàn) *支持的范圍為1 ~ 2^32 毫秒(大約有49天) *若設(shè)置的定時(shí)器超過最大值 則按最大值設(shè)置定時(shí)器 **/#include #include #include #include #include #include #include "list.h"#include "log.h" #define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1current_index (TVR_BITS + (N) * TVN_BITS)) TVN_MASK) typedef void (*timeouthandle)(unsigned long ); struct timer_list{ struct list_head entry; //將時(shí)間連接成鏈表 unsigned long expires; //超時(shí)時(shí)間 void (*function)(unsigned long); //超時(shí)后的處理函數(shù) unsigned long data; //處理函數(shù)的參數(shù) struct tvec_base *base; //指向時(shí)間輪}; struct tvec { struct list_head vec[TVN_SIZE];}; struct tvec_root{ struct list_head vec[TVR_SIZE];}; //實(shí)現(xiàn)5級(jí)時(shí)間輪 范圍為0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_base{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadID; struct tvec_root tv1; /*第一個(gè)輪*/ struct tvec tv2; /*第二個(gè)輪*/ struct tvec tv3; /*第三個(gè)輪*/ struct tvec tv4; /*第四個(gè)輪*/ struct tvec tv5; /*第五個(gè)輪*/}; static void internal_add_timer(struct tvec_base *base, struct timer_list *timer){ struct list_head *vec; unsigned long expires = timer-expires; unsigned long idx = expires - base-current_index;#if 1 if( (signed long)idx 0 ) /*這里是沒有辦法區(qū)分出是過時(shí)還是超長(zhǎng)定時(shí)的吧?*/ { vec = base-tv1.vec + (base-current_index TVR_MASK);/*放到第一個(gè)輪的當(dāng)前槽*/ } else if ( idx TVR_SIZE ) /*第一個(gè)輪*/ { int i = expires TVR_MASK; vec = base-tv1.vec + i; } else if( idx 1 (TVR_BITS + TVN_BITS) )/*第二個(gè)輪*/ { int i = (expires TVR_BITS) TVN_MASK; vec = base-tv2.vec + i; } else if( idx 1 (TVR_BITS + 2 * TVN_BITS) )/*第三個(gè)輪*/ { int i = (expires (TVR_BITS + TVN_BITS)) TVN_MASK; vec = base-tv3.vec + i; } else if( idx 1 (TVR_BITS + 3 * TVN_BITS) )/*第四個(gè)輪*/ { int i = (expires (TVR_BITS + 2 * TVN_BITS)) TVN_MASK; vec = base-tv4.vec + i; } else /*第五個(gè)輪*/ { int i; if (idx 0xffffffffUL) { idx = 0xffffffffUL; expires = idx + base-current_index; } i = (expires (TVR_BITS + 3 * TVN_BITS)) TVN_MASK; vec = base-tv5.vec + i; }#else /*上面可以優(yōu)化吧*/;#endif list_add_tail(timer-entry, vec);} static inline void detach_timer(struct timer_list *timer){ struct list_head *entry = timer-entry; __list_del(entry-prev, entry-next); entry-next = NULL; entry-prev = NULL;} static int __mod_timer(struct timer_list *timer, unsigned long expires){ if(NULL != timer-entry.next) detach_timer(timer); internal_add_timer(timer-base, timer); return 0;} //修改定時(shí)器的超時(shí)時(shí)間外部接口int mod_timer(void *ptimer, unsigned long expires){ struct timer_list *timer = (struct timer_list *)ptimer; struct tvec_base *base; base = timer-base; if(NULL == base) return -1; expires = expires + base-current_index; if(timer-entry.next != NULL timer-expires == expires) return 0; if( NULL == timer-function ) { errlog("timer's timeout function is null\n"); return -1; } timer-expires = expires; return __mod_timer(timer,expires);} //添加一個(gè)定時(shí)器static void __ti_add_timer(struct timer_list *timer){ if( NULL != timer-entry.next ) { errlog("timer is already exist\n"); return; } mod_timer(timer, timer-expires); } /*添加一個(gè)定時(shí)器 外部接口 *返回定時(shí)器 */void* ti_add_timer(void *ptimewheel, unsigned long expires,timeouthandle phandle, unsigned long arg){ struct timer_list *ptimer; ptimer = (struct timer_list *)malloc( sizeof(struct timer_list) ); if(NULL == ptimer) return NULL; bzero( ptimer,sizeof(struct timer_list) ); ptimer-entry.next = NULL; ptimer-base = (struct tvec_base *)ptimewheel; ptimer-expires = expires; ptimer-function = phandle; ptimer-data = arg; __ti_add_timer(ptimer); return ptimer;} /* *刪除一個(gè)定時(shí)器 外部接口 * * */void ti_del_timer(void *p){ struct timer_list *ptimer =(struct timer_list*)p; if(NULL == ptimer) return; if(NULL != ptimer-entry.next) detach_timer(ptimer); free(ptimer);}/*時(shí)間輪級(jí)聯(lián)*/ static int cascade(struct tvec_base *base, struct tvec *tv, int index){ struct list_head *pos,*tmp; struct timer_list *timer; struct list_head tv_list; /*將tv[index]槽位上的所有任務(wù)轉(zhuǎn)移給tv_list,然后清空tv[index]*/ list_replace_init(tv-vec + index, tv_list);/*用tv_list替換tv-vec + index*/ list_for_each_safe(pos, tmp, tv_list)/*遍歷tv_list雙向鏈表，將任務(wù)重新添加到時(shí)間輪*/ { timer = list_entry(pos,struct timer_list,entry);/*struct timer_list中成員entry的地址是pos, 獲取struct timer_list的首地址*/ internal_add_timer(base, timer); } return index;} static void *deal_function_timeout(void *base){ struct timer_list *timer; int ret; struct timeval tv; struct tvec_base *ba = (struct tvec_base *)base; for(;;) { gettimeofday(tv, NULL); while( ba-current_index = (tv.tv_sec*1000 + tv.tv_usec/1000) )/*單位：ms*/ { struct list_head work_list; int index = ba-current_index TVR_MASK;/*獲取第一個(gè)輪上的指針位置*/ struct list_head *head = work_list; /*指針指向0槽時(shí)，級(jí)聯(lián)輪需要更新任務(wù)列表*/ if(!index (!cascade(ba, ba-tv2, INDEX(0))) ( !cascade(ba, ba-tv3, INDEX(1))) (!cascade(ba, ba-tv4, INDEX(2))) ) cascade(ba, ba-tv5, INDEX(3)); ba-current_index ++; list_replace_init(ba-tv1.vec + index, work_list); while(!list_empty(head)) { void (*fn)(unsigned long); unsigned long data; timer = list_first_entry(head, struct timer_list, entry); fn = timer-function; data = timer-data; detach_timer(timer); (*fn)(data); } } }} static void init_tvr_list(struct tvec_root * tvr){ int i; for( i = 0; ivec[i]);} static void init_tvn_list(struct tvec * tvn){ int i; for( i = 0; ivec[i]);} //創(chuàng)建時(shí)間輪 外部接口void *ti_timewheel_create(void ){ struct tvec_base *base; int ret = 0; struct timeval tv; base = (struct tvec_base *) malloc( sizeof(struct tvec_base) ); if( NULL==base ) return NULL; bzero( base,sizeof(struct tvec_base) ); init_tvr_list(base-tv1); init_tvn_list(base-tv2); init_tvn_list(base-tv3); init_tvn_list(base-tv4); init_tvn_list(base-tv5); gettimeofday(tv, NULL); base-current_index = tv.tv_sec*1000 + tv.tv_usec/1000;/*當(dāng)前時(shí)間毫秒數(shù)*/ if( 0 != pthread_create(base-threadID,NULL,deal_function_timeout,base) ) { free(base); return NULL; } return base;} static void ti_release_tvr(struct tvec_root *pvr){ int i; struct list_head *pos,*tmp; struct timer_list *pen; for(i = 0; i TVR_SIZE; i++) { list_for_each_safe(pos,tmp,pvr-vec[i]) { pen = list_entry(pos,struct timer_list, entry); list_del(pos); free(pen); } }} static void ti_release_tvn(struct tvec *pvn){ int i; struct list_head *pos,*tmp; struct timer_list *pen; for(i = 0; i TVN_SIZE; i++) { list_for_each_safe(pos,tmp,pvn-vec[i]) { pen = list_entry(pos,struct timer_list, entry); list_del(pos); free(pen); } }} /* *釋放時(shí)間輪 外部接口 * */void ti_timewheel_release(void * pwheel){ struct tvec_base *base = (struct tvec_base *)pwheel; if(NULL == base) return; ti_release_tvr(base-tv1); ti_release_tvn(base-tv2); ti_release_tvn(base-tv3); ti_release_tvn(base-tv4); ti_release_tvn(base-tv5); free(pwheel);} /************demo****************/struct request_para{ void *timer; int val;}; void mytimer(unsigned long arg){ struct request_para *para = (struct request_para *)arg; log("%d\n",para-val); mod_timer(para-timer,3000); //進(jìn)行再次啟動(dòng)定時(shí)器 sleep(10);/*定時(shí)器依然被阻塞*/ //定時(shí)器資源的釋放是在這里完成的 //ti_del_timer(para-timer);} int main(int argc,char *argv[]){ void *pwheel = NULL; void *timer = NULL; struct request_para *para; para = (struct request_para *)malloc( sizeof(struct request_para) ); if(NULL == para) return 0; bzero(para,sizeof(struct request_para)); //創(chuàng)建一個(gè)時(shí)間輪 pwheel = ti_timewheel_create(); if(NULL == pwheel) return -1; //添加一個(gè)定時(shí)器 para-val = 100; para-timer = ti_add_timer(pwheel, 3000, mytimer, (unsigned long)para); while(1) { sleep(2); } //釋放時(shí)間輪 ti_timewheel_release(pwheel); return 0;}
2.4 編譯運(yùn)行
toney@ubantu:/mnt/hgfs/em嵌入式學(xué)習(xí)記錄/4. timerwheel/2. 多級(jí)時(shí)間輪$ lsa.out list.h log.h mutiTimeWheel.ctoney@ubantu:/mnt/hgfs/em嵌入式學(xué)習(xí)記錄/4. timerwheel/2. 多級(jí)時(shí)間輪$ gcc mutiTimeWheel.c -lpthreadtoney@ubantu:/mnt/hgfs/em嵌入式學(xué)習(xí)記錄/4. timerwheel/2. 多級(jí)時(shí)間輪$ ./a.out [#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100[#DEBUG: Toeny Sun: mytimer:370]:100
從結(jié)果可以看出：如果添加的定時(shí)任務(wù)是比較耗時(shí)的操作，那么后續(xù)的任務(wù)也會(huì)被阻塞，可能一直到超時(shí)，甚至一直阻塞下去，這個(gè)取決于當(dāng)前任務(wù)是否耗時(shí)。這個(gè)理論上是絕不能接受的：一個(gè)任務(wù)不應(yīng)該也不能去影響其他的任務(wù)吧。但是目前沒有對(duì)此問題進(jìn)行改進(jìn)和完善，以后有機(jī)會(huì)再繼續(xù)完善吧。
重慶分公司
重慶分公司
