Shulou(Shulou.com)06/01 Report--

This article introduces the knowledge of "how to use C language to realize the classic multi-level time wheel timer". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations! I hope you can read it carefully and be able to achieve something!

Implementation framework of multi-level time wheel

The picture above is the effect of a cascade of five time rounds. The middle wheel is the work wheel, and only the tasks on it will be carried out; when the time for the tasks on other wheels arrives, they will eventually move to the work wheel and be scheduled for execution.

The principle of the multi-stage time wheel is also easy to understand: take the clock as an explanation, the second hand turns one minute hand and the minute hand turns one frame; the same is true of the time wheel: when the lower wheel turns once, the higher wheel rotates one grid. At the same time, the tasks on the higher wheel will be redistributed to the lower wheel. As a result, the effect of multi-stage wheel cascade is realized.

1 multi-level time wheel object

The multi-level time wheel should include at least the following:

Each level of time wheel object

The position of the pointer on the wheel

There is a more ingenious way to deal with the position of the pointer on the wheel: bit operation. For example, define a number of unsigned integers:

By obtaining the current system time, the time on the time wheel can be converted into the time on the time wheel by bit operation, and by comparing with the time on the actual time wheel, the time to be scheduled in the time wheel can be determined, and then the task corresponding to the slot of the time wheel can be operated.

Why do we need at least these two members?

To define a multi-level time wheel, the first thing you need to make clear is the number of cascading layers, that is to say, how many time wheels there are.

The position of the pointer on the wheel is the position to which the current time wheel is running. the difference between it and the real time is that the subsequent time wheel needs to be scheduled and executed, and their difference is the driving force for the operation of the time wheel.

Definition of multi-level time wheel object

/ / achieve level 5 time wheel range of 0 ~ (2 ^ 8 * 2 ^ 6 * 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; / * first round * / struct tvec tv2; / * second round * / struct tvec tv3 / * third round * / struct tvec tv4; / * fourth round * / struct tvec tv5; / * fifth round * /}; 2 time round object

We know that each wheel is actually a hash table, and above we just instantiate the object of five wheels, but it is not clear what the five wheels contain, how many slots, and so on (that is, struct tvec and struct tvec_root).

# define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1next = 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 * /

There is usually an important implementation: = = container_of==,. If you don't know how it works, you can read another blog post devoted to this function: an introduction to the container of () function.

2 debugging information header file: log.h

This header file is not actually required, I just use it to add debugging information (errlog () and log () in the code are macro functions in log.h). The effect is to add color to the printed message, as follows:

The code for log.h is as follows:

# 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 "% SV% d]:" GRAY WHITE fmt GRAY, _ _ func__, _ LINE__, # # arg);} while (0) # define log (fmt, arg...) Do {printf (WHITE "[# DEBUG: Toeny Sun:" GRAY YELLOW "% SV% d]:" GRAY WHITE fmt GRAY, _ _ func__, _ _ LINE__, # # arg) } while (0) # endif3 time wheel code: timewheel.c/* * millisecond timer uses multiple time wheels to learn from the implementation in the linux kernel * the supported range is 1-2 ^ 32 milliseconds (about 49 days) * if the timer exceeds the maximum value, the timer is set according to the maximum value * * / # include # include "list.h" # include "log.h" # define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1expires Unsigned long idx = expires-base- > current_index;#if 1 if ((signed long) idx

< 0 ) /*这里是没有办法区分出是过时还是超长定时的吧?*/ { vec = base->

Tv1.vec + (base- > current_index & TVR_MASK); / * current slot on the first wheel * /} else if (idx

< TVR_SIZE ) /*第一个轮*/ { int i = expires & TVR_MASK; vec = base->

Tv1.vec + I;} else if (idx

< 1 >

TVR_BITS) & TVN_MASK; vec = base- > tv2.vec + I;} else if (idx

< 1 >

(TVR_BITS + TVN_BITS) & TVN_MASK; vec = base- > tv3.vec + I;} else if (idx

< 1 >

(TVR_BITS + 2 * TVN_BITS) & TVN_MASK; vec = base- > tv4.vec + I;} else / * Fifth wheel * / {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 / * above can be optimized * /; # 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 } / / modify timer timeout external interface 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) } / / add a timer 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) } / * add a timer external interface * return timer * / 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;} / * * Delete a timer external interface * / 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);} / * time wheel cascade * / 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 / * transfer all tasks on the tv [index] slot to tv_list, and then clear tv [index] * / list_replace_init (tv- > vec + index, & tv_list) / * replace tv- > vec + index*/ list_for_each_safe (pos, tmp, & tv_list) / * with tv_list to traverse the tv_list two-way linked list and add the task back to the time wheel * / {timer = list_entry (pos,struct timer_list,entry); / * the address of the member entry in struct timer_list is pos, get the first address of 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 current_index & TVR_MASK / * get the pointer position on the first wheel * / struct list_head * head = & work_list / * when the pointer points to slot 0, the cascade wheel needs to update the task list * / 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]);} / create time wheel external interface 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 / * current time milliseconds * / 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);} / * * release time wheel external interface * / 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); / / restart timer sleep (10); / * timer is still blocked * / / timer resource release is completed here / / 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)); / / create a time wheel pwheel = ti_timewheel_create () If (NULL = = pwheel) return-1; / / add a timer para- > val = 100; para- > timer = ti_add_timer (pwheel, 3000, & mytimer, (unsigned long) para); while (1) {sleep (2);} / release time wheel ti_timewheel_release (pwheel); return 0;} 3.4 compile and run

Toney@ubantu:/mnt/hgfs/em embedded Learning Records / 4. Timerwheel/2. Multi-level time wheel $lsa.out list.h log.h mutiTimeWheel.ctoney@ubantu:/mnt/hgfs/em embedded learning record / 4. Timerwheel/2. Multi-level time wheel $gcc mutiTimeWheel.c-lpthreadtoney@ubantu:/mnt/hgfs/em embedded learning record / 4. Timerwheel/2. Multilevel time wheel $. / 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 "how to implement classic multi-level time wheel timers in C language" ends here. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.