linux定時器(Linux定時器實現)

推薦視頻：

準備好linux編程環境,現場手撕定時器實現【linux服務器開發】

工程師的圣地—Linux內核， 談談內核的架構

c/c++ linux服務器開發學習地址：C/C++Linux服務器開發/后臺架構師【零聲教育】-學習視頻教程-騰訊課堂

上圖是5個時間輪級聯的效果圖。中間的大輪是工作輪，只有在它上的任務才會被執行；其他輪上的任務時間到后遷移到下一級輪上，他們最終都會遷移到工作輪上而被調度執行。

多級時間輪的原理也容易理解：就拿時鐘做說明，秒針轉動一圈分針轉動一格；分針轉動一圈時針轉動一格；同理時間輪也是如此：當低級輪轉動一圈時，高一級輪轉動一格，同時會將高一級輪上的任務重新分配到低級輪上。從而實現了多級輪級聯的效果。

1.1 多級時間輪對象

多級時間輪應該至少包括以下內容：

關于輪子上指針的位置有一個比較巧妙的辦法：那就是位運算。比如定義一個無符號整型的數：

通過獲取當前的系統時間便可以通過位操作轉換為時間輪上的時間，通過與實際時間輪上的時間作比較，從而確定時間輪要前進調度的時間，進而操作對應時間輪槽位對應的任務。

為什么至少需要這兩個成員呢？

多級時間輪對象的定義

//實現5級時間輪 范圍為0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_ba{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadID; struct tvec_root tv1; /*第一個輪*/ struct tvec tv2; /*第二個輪*/ struct tvec tv3; /*第三個輪*/ struct tvec tv4; /*第四個輪*/ struct tvec tv5; /*第五個輪*/};

1.2 時間輪對象

我們知道每一個輪子實際上都是一個哈希表，上面我們只是實例化了五個輪子的對象，但是五個輪子具體包含什么，有幾個槽位等等沒有明確(即struct tvec和struct tvec_root)。

#define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1<<TVN_BITS)#define TVR_SIZE (1<<TVR_BITS)struct tvec { struct list_head vec[TVN_SIZE];/*64個格子*/}; struct tvec_root{ struct list_head vec[TVR_SIZE];/*256個格子*/};

此外，每一個時間輪都是哈希表，因此它的類型應該至少包含兩個指針域來實現雙向鏈表的功能。這里我們為了方便使用通用的struct list_head的雙向鏈表結構。

1.3 定時任務對象

定時器的主要工作是為了在未來的特定時間完成某項任務，而這個任務經常包含以下內容：

定時任務對象的定義

typedef void (*timeouthandle)(unsigned long ); struct timer_list{ struct list_head entry; //將時間連接成鏈表 unsigned long expires; //超時時間 void (*function)(unsigned long); //超時后的處理函數 unsigned long data; //處理函數的參數 struct tvec_ba *ba; //指向時間輪};

在時間輪上的效果圖：

【文章福利】需要C/C++ Linux服務器架構師學習資料加群812855908（資料包括C/C++，Linux，golang技術，內核，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等）

1.4 雙向鏈表

在時間輪上我們采用雙向鏈表的數據類型。采用雙向鏈表的除了操作上比單鏈表復雜，多占一個指針域外沒有其他不可接收的問題。而多占一個指針域在今天大內存的時代明顯不是什么問題。至于雙向鏈表操作的復雜性，我們可以通過使用通用的struct list結構來解決，因為雙向鏈表有眾多的標準操作函數，我們可以通過直接引用list.h頭文件來使用他們提供的接口。

struct list可以說是一個萬能的雙向鏈表操作框架，我們只需要在自定義的結構中定義一個struct list對象即可使用它的標準操作接口。同時它還提供了一個類似container_of的接口，在應用層一般叫做list_entry，因此我們可以很方便的通過struct list成員找到自定義的結構體的起始地址。

關于應用層的log.h, 我將在下面的代碼中附上該文件。如果需要內核層的實現，可以直接從linux源碼中獲取。

1.5 聯結方式

多級時間輪效果圖：

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

提到雙向鏈表，很多的源碼工程中都會實現一系列的統一的雙向鏈表操作函數。它們為雙向鏈表封裝了統計的接口，使用者只需要在自定義的結構中添加一個struct list_head結構，然后調用它們提供的接口，便可以完成雙向鏈表的所有操作。這些操作一般都在list.h的頭文件中實現。Linux源碼中也有實現（內核態的實現）。他們實現的方式基本完全一樣，只是實現的接口數量和功能上稍有差別。可以說這個list.h文件是學習操作雙向鏈表的不二選擇，它幾乎實現了所有的操作：增、刪、改、查、遍歷、替換、清空等等。這里我拼湊了一個源碼中的log.h函數，終于湊夠了多級時間輪中使用到的接口。

#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 uful 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;}/** * Inrt a new element after the given list head. The new element does not * need to be initialid 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 ret * the pointers to/from this element so it is removed from the list. It does * NOT free the element itlf or manipulate it otherwi. * * 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 ret 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 Fal otherwi. */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 inrt * * 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 u 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 ca it is freed) * @pos: the &struct list_head to u as a loop counter. * @pnext: the &struct list_head to u 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 */

這里面一般會用到一個重要實現：container_of, 它的原理這里不敘述

2.2 調試信息頭文件: log.h

這個頭文件實際上不是必須的，我只是用它來添加調試信息(代碼中的errlog(), log()都是log.h中的宏函數)。它的效果是給打印的信息加上顏色，效果如下：

log.h的代碼如下：

#ifndef _LOG_h_#define _LOG_h_#include <stdio.h>#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 時間輪代碼: timewheel.c

/* *毫秒定時器 采用多級時間輪方式 借鑒linux內核中的實現 *支持的范圍為1 ~ 2^32 毫秒(大約有49天) *若設置的定時器超過最大值 則按最大值設置定時器 **/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <unistd.h>#include <pthread.h>#include <sys/time.h>#include "list.h"#include "log.h" #define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1<<TVN_BITS)#define TVR_SIZE (1<<TVR_BITS) #define TVN_MASK (TVN_SIZE - 1)#define TVR_MASK (TVR_SIZE - 1) #define SEC_VALUE 0#define USEC_VALUE 2000 struct tvec_ba;#define INDEX(N) ((ba->current_index >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK) typedef void (*timeouthandle)(unsigned long ); struct timer_list{ struct list_head entry; //將時間連接成鏈表 unsigned long expires; //超時時間 void (*function)(unsigned long); //超時后的處理函數 unsigned long data; //處理函數的參數 struct tvec_ba *ba; //指向時間輪}; struct tvec { struct list_head vec[TVN_SIZE];}; struct tvec_root{ struct list_head vec[TVR_SIZE];}; //實現5級時間輪 范圍為0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_ba{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadID; struct tvec_root tv1; /*第一個輪*/ struct tvec tv2; /*第二個輪*/ struct tvec tv3; /*第三個輪*/ struct tvec tv4; /*第四個輪*/ struct tvec tv5; /*第五個輪*/}; static void internal_add_timer(struct tvec_ba *ba, struct timer_list *timer){ struct list_head *vec; unsigned long expires = timer->expires; unsigned long idx = expires - ba->current_index;#if 1 if( (signed long)idx < 0 ) /*這里是沒有辦法區分出是過時還是超長定時的吧?*/ { vec = ba->tv1.vec + (ba->current_index & TVR_MASK);/*放到第一個輪的當前槽*/ } el if ( idx < TVR_SIZE ) /*第一個輪*/ { int i = expires & TVR_MASK; vec = ba->tv1.vec + i; } el if( idx < 1 << (TVR_BITS + TVN_BITS) )/*第二個輪*/ { int i = (expires >> TVR_BITS) & TVN_MASK; vec = ba->tv2.vec + i; } el if( idx < 1 << (TVR_BITS + 2 * TVN_BITS) )/*第三個輪*/ { int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK; vec = ba->tv3.vec + i; } el if( idx < 1 << (TVR_BITS + 3 * TVN_BITS) )/*第四個輪*/ { int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK; vec = ba->tv4.vec + i; } el /*第五個輪*/ { int i; if (idx > 0xffffffffUL) { idx = 0xffffffffUL; expires = idx + ba->current_index; } i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK; vec = ba->tv5.vec + i; }#el /*上面可以優化吧*/;#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->ba, timer); return 0;} //修改定時器的超時時間外部接口int mod_timer(void *ptimer, unsigned long expires){ struct timer_list *timer = (struct timer_list *)ptimer; struct tvec_ba *ba; ba = timer->ba; if(NULL == ba) return -1; expires = expires + ba->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);} //添加一個定時器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); } /*添加一個定時器 外部接口 *返回定時器 */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->ba = (struct tvec_ba *)ptimewheel; ptimer->expires = expires; ptimer->function = phandle; ptimer->data = arg; __ti_add_timer(ptimer); return ptimer;} /* *刪除一個定時器 外部接口 * * */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);}/*時間輪級聯*/ static int cascade(struct tvec_ba *ba, struct tvec *tv, int index){ struct list_head *pos,*tmp; struct timer_list *timer; struct list_head tv_list; /*將tv[index]槽位上的所有任務轉移給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雙向鏈表，將任務重新添加到時間輪*/ { timer = list_entry(pos,struct timer_list,entry);/*struct timer_list中成員entry的地址是pos, 獲取struct timer_list的首地址*/ internal_add_timer(ba, timer); } return index;} static void *deal_function_timeout(void *ba){ struct timer_list *timer; int ret; struct timeval tv; struct tvec_ba *ba = (struct tvec_ba *)ba; for(;;) { gettimeofday(&tv, NULL); while( ba->current_index <= (tv.tv_c*1000 + tv.tv_uc/1000) )/*單位：ms*/ { struct list_head work_list; int index = ba->current_index & TVR_MASK;/*獲取第一個輪上的指針位置*/ struct list_head *head = &work_list; /*指針指向0槽時，級聯輪需要更新任務列表*/ 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; i<TVR_SIZE; i++ ) INIT_LIST_HEAD(&tvr->vec[i]);} static void init_tvn_list(struct tvec * tvn){ int i; for( i = 0; i<TVN_SIZE; i++ ) INIT_LIST_HEAD(&tvn->vec[i]);} //創建時間輪 外部接口void *ti_timewheel_create(void ){ struct tvec_ba *ba; int ret = 0; struct timeval tv; ba = (struct tvec_ba *) malloc( sizeof(struct tvec_ba) ); if( NULL==ba ) return NULL; bzero( ba,sizeof(struct tvec_ba) ); init_tvr_list(&ba->tv1); init_tvn_list(&ba->tv2); init_tvn_list(&ba->tv3); init_tvn_list(&ba->tv4); init_tvn_list(&ba->tv5); gettimeofday(&tv, NULL); ba->current_index = tv.tv_c*1000 + tv.tv_uc/1000;/*當前時間毫秒數*/ if( 0 != pthread_create(&ba->threadID,NULL,deal_function_timeout,ba) ) { free(ba); return NULL; } return ba;} static void ti_relea_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_relea_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); } }} /* *釋放時間輪 外部接口 * */void ti_timewheel_relea(void * pwheel){ struct tvec_ba *ba = (struct tvec_ba *)pwheel; if(NULL == ba) return; ti_relea_tvr(&ba->tv1); ti_relea_tvn(&ba->tv2); ti_relea_tvn(&ba->tv3); ti_relea_tvn(&ba->tv4); ti_relea_tvn(&ba->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); //進行再次啟動定時器 sleep(10);/*定時器依然被阻塞*/ //定時器資源的釋放是在這里完成的 //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)); //創建一個時間輪 pwheel = ti_timewheel_create(); if(NULL == pwheel) return -1; //添加一個定時器 para->val = 100; para->timer = ti_add_timer(pwheel, 3000, &mytimer, (unsigned long)para); while(1) { sleep(2); } //釋放時間輪 ti_timewheel_relea(pwheel); return 0;}

2.4 編譯運行

toney@ubantu:/mnt/hgfs/em嵌入式學習記錄/4. timerwheel/2. 多級時間輪$ lsa.out list.h log.h mutiTimeWheel.ctoney@ubantu:/mnt/hgfs/em嵌入式學習記錄/4. timerwheel/2. 多級時間輪$ gcc mutiTimeWheel.c -lpthreadtoney@ubantu:/mnt/hgfs/em嵌入式學習記錄/4. timerwheel/2. 多級時間輪$ ./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

從結果可以看出：如果添加的定時任務是比較耗時的操作，那么后續的任務也會被阻塞，可能一直到超時，甚至一直阻塞下去，這個取決于當前任務是否耗時。這個理論上是絕不能接受的：一個任務不應該也不能去影響其他的任務吧。但是目前沒有對此問題進行改進和完善，以后有機會再繼續完善吧。