多級時(shí)間輪定時(shí)器的原理及編程實(shí)現(xiàn)方案

一. 多級時(shí)間輪實(shí)現(xiàn)框架

上圖是5個(gè)時(shí)間輪級聯(lián)的效果圖。中間的大輪是工作輪，只有在它上的任務(wù)才會被執(zhí)行；其他輪上的任務(wù)時(shí)間到后遷移到下一級輪上，他們最終都會遷移到工作輪上而被調(diào)度執(zhí)行。

多級時(shí)間輪的原理也容易理解：就拿時(shí)鐘做說明，秒針轉(zhuǎn)動一圈分針轉(zhuǎn)動一格；分針轉(zhuǎn)動一圈時(shí)針轉(zhuǎn)動一格；同理時(shí)間輪也是如此：當(dāng)?shù)图壿嗈D(zhuǎn)動一圈時(shí)，高一級輪轉(zhuǎn)動一格，同時(shí)會將高一級輪上的任務(wù)重新分配到低級輪上。從而實(shí)現(xiàn)了多級輪級聯(lián)的效果。

1.1 多級時(shí)間輪對象

多級時(shí)間輪應(yīng)該至少包括以下內(nèi)容：

每一級時(shí)間輪對象

輪子上指針的位置關(guān)于輪子上指針的位置有一個(gè)比較巧妙的辦法：那就是位運(yùn)算。比如定義一個(gè)無符號整型的數(shù)：

通過獲取當(dāng)前的系統(tǒng)時(shí)間便可以通過位操作轉(zhuǎn)換為時(shí)間輪上的時(shí)間，通過與實(shí)際時(shí)間輪上的時(shí)間作比較，從而確定時(shí)間輪要前進(jìn)調(diào)度的時(shí)間，進(jìn)而操作對應(yīng)時(shí)間輪槽位對應(yīng)的任務(wù)。

為什么至少需要這兩個(gè)成員呢？

定義多級時(shí)間輪，首先需要明確的便是級聯(lián)的層數(shù)，也就是說需要確定有幾個(gè)時(shí)間輪。

輪子上指針位置，就是當(dāng)前時(shí)間輪運(yùn)行到的位置，它與真實(shí)時(shí)間的差便是后續(xù)時(shí)間輪需要調(diào)度執(zhí)行，它們的差值是時(shí)間輪運(yùn)作起來的驅(qū)動力。

多級時(shí)間輪對象的定義

?

//實(shí)現(xiàn)5級時(shí)間輪?范圍為0~?(2^8?*?2^6?*?2^6?*?2^6?*2^6)=2^32
struct?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í)間輪對象

?

我們知道每一個(gè)輪子實(shí)際上都是一個(gè)哈希表，上面我們只是實(shí)例化了五個(gè)輪子的對象，但是五個(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ù)對象

定時(shí)器的主要工作是為了在未來的特定時(shí)間完成某項(xiàng)任務(wù)，而這個(gè)任務(wù)經(jīng)常包含以下內(nèi)容：

任務(wù)的處理邏輯(回調(diào)函數(shù))

任務(wù)的參數(shù)

雙向鏈表節(jié)點(diǎn)

到時(shí)時(shí)間

定時(shí)任務(wù)對象的定義

?

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í)間輪上的效果圖：

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è)萬能的雙向鏈表操作框架，我們只需要在自定義的結(jié)構(gòu)中定義一個(gè)struct list對象即可使用它的標(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é)方式

多級時(shí)間輪效果圖：

二. 多級時(shí)間輪C語言實(shí)現(xiàn)

2.1 雙向鏈表頭文件: list.h

提到雙向鏈表，很多的源碼工程中都會實(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ù)，終于湊夠了多級時(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?void
list_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?void
list_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?void
list_del(struct?list_head?*entry)
{
????__list_del(entry->prev,?entry->next);
}
static?inline?void
list_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?int
list_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?*/

?

這里面一般會用到一個(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)??"33[;"?#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????"33[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í)器??采用多級時(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???(1>?(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級時(shí)間輪?范圍為0~?(2^8?*?2^6?*?2^6?*?2^6?*2^6)=2^32
struct?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?tv1.vec?+?(base->current_index?&?TVR_MASK);/*放到第一個(gè)輪的當(dāng)前槽*/
????}
?else?if?(?idx?tv1.vec?+?i;
????}
????else?if(?idx?>?TVR_BITS)?&?TVN_MASK;
????????vec?=?base->tv2.vec?+?i;
????}
????else?if(?idx?>?(TVR_BITS?+?TVN_BITS))?&?TVN_MASK;
????????vec?=?base->tv3.vec?+?i;
????}
????else?if(?idx?>?(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
");
????????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
");
????????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í)間輪級聯(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í)，級聯(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?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?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
",para->val);
????mod_timer(para->timer,3000);??//進(jìn)行再次啟動定時(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)行

?

peng@ubuntu:/mnt/hgfs/timer/4.?timerwheel/2.?多級時(shí)間輪$?ls
a.out??list.h??log.h??mutiTimeWheel.c
toney@ubantu:/mnt/hgfs/timer錄/4.?timerwheel/2.?多級時(shí)間輪$?gcc?mutiTimeWheel.c?-lpthread
toney@ubantu:/mnt/hgfs/timer/4.?timerwheel/2.?多級時(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ù)也會被阻塞，可能一直到超時(shí)，甚至一直阻塞下去，這個(gè)取決于當(dāng)前任務(wù)是否耗時(shí)。

這個(gè)理論上是絕不能接受的：一個(gè)任務(wù)不應(yīng)該也不能去影響其他的任務(wù)吧。但是目前沒有對此問題進(jìn)行改進(jìn)和完善，以后有機(jī)會再繼續(xù)完善吧。

編輯：黃飛

?