『壹』 c語言等待一定時間輸入自動結束
准備好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_base{ 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<
此外,每一個時間輪都是哈希表,因此它的類型應該至少包含兩個指針域來實現雙向鏈表的功能。這里我們為了方便使用通用的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_base *base; //指向時間輪};
在時間輪上的效果圖:
【文章福利】需要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 聯結方式
多級時間輪效果圖:
二. 多級時間輪C語言實現
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 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 */
這裡面一般會用到一個重要實現:container_of, 它的原理這里不敘述
2.2 調試信息頭文件: log.h
這個頭文件實際上不是必須的,我只是用它來添加調試信息(代碼中的errlog(), log()都是log.h中的宏函數)。它的效果是給列印的信息加上顏色,效果如下:
log.h的代碼如下:
#ifndef _LOG_h_#define _LOG_h_#include #define COL(x) "