Skynet定時器實現方案

skynet中定時器數據結構

采用時間輪方式，hash表+鏈表實現，

struct timer_node {  //時間節點
 struct timer_node *next;
    uint32_t expire; //到期滴答數
};
struct link_list {  // 鏈表
  struct timer_node head;
  struct timer_node *tail;
};
struct timer {
 struct link_list near[256];  // 即將到來的定時器
    struct link_list t[4][64]; // 相對較遙遠的定時器
    struct spinlock lock;
    uint32_t time;  // 記錄當前滴答數
    uint64_t starttime;
    uint64_t current;
    uint64_t current_point;
};

其中time為32位無符號整數， 記錄時間片對應數組near[256] ，表示即將到來的定時任務， t[4][64]，表示較為遙遠的定時任務。

定時器執行流程

skynet_time_wheel

• 首先檢查節點的expire與time的高24位是否相等，相等則將該節點添加到expire低8位值對應數組near的元素的鏈表中，不相等則進行下一步
• 檢查expire與time的高18位是否相等，相等則將該節點添加到expire低第9位到第14位對應的6位二進制值對應數組t[0]的元素的鏈表中，否則進行下一步
• 檢查expire與time的高12位是否相等，相等則將該節點添加到expire低第15位到第20位對應的6位二進制值對應數組t[1]的元素的鏈表中，如果不相等則進行下一步
• 檢查expire與time的高6位是否相等，相等則將該節點添加到expire低第21位到第26位對應的6位二進制值對應數組t[2]的元素的鏈表中，如果不相等則進行下一步
• 將該節點添加到expire低第27位到第32位對應的6位二進制值對應數組t[3]的元素的鏈表中

以下為具體實現，僅貼出主要接口，具體細節請參考skynet源代碼。

定時器初始化

// skynet_start.c
// skynet 啟動入口
void
skynet_start(struct skynet_config * config) {
    ...
    skynet_timer_init();
    ...
}
// skynet_timer.c
void
skynet_timer_init(void) {
    // 創建全局timer結構 TI
    TI  = timer_create_timer();
    uint32_t current = 0;
    systime(&TI->starttime, ¤t);
    TI->current = current;
    TI->current_point = gettime();
}

添加定時器

通過skynet_server.c中的cmd_timeout調用skynet_timeout添加新的定時器

// TI為全局的定時器指針
static struct timer * TI = NULL; 
int skynet_timeout(uint32_t handle, int time, int session) {
    ...
    struct timer_event event;
    event.handle = handle;  // callback
    eveng.session = session;
    // 添加新的定時器節點
    timer_add(TI, &event, sizeof(event), time);
    return session;
}
// 添加新的定時器節點
static void timer_add(struct timer *T, void 8arg, size_t sz, int time) {
    // 給timer_node指針分配空間，還需要分配timer_node + timer_event大小的空間，
    // 之后通過node + 1可獲得timer_event數據
    struct timer_node *node = (struct timer_node *)skynet_malloc(sizeof(*node)+sz);
    memcpy(node+1,arg,sz);
    SPIN_LOCK(T);
    node->expire=time+T->time;
    add_node(T, node);
    SPIN_UNLOCK(T);
}

// 添加到定時器鏈表里，如果定時器的到期滴答數跟當前比較近(<2^8)，表示即將觸發定時器添加到T->near數組里
// 否則根據差值大小添加到對應的T->T[i]中
static void add_node(struct timer *T, struct timer_node *node) {
    ...
}

驅動方式

skynet啟動時，會創建一個線程專門跑定時器，每幀(0.0025s)調用skynet_updatetime()

// skynet_start.c
static void * 
thread_timer(void *p) {
    struct monitor * m = p;
    skynet_initthread(THREAD_TIMER);
    for (;;) {
        skynet_updatetime();  // 調用timer_update
        skynet_socket_updatetime();
        CHECK_ABORT
        wakeup(m,m->count-1);
        usleep(2500);  // 2500微秒 = 0.0025s
        if (SIG) {
            signal_hup();
            SIG = 0;
        }
    }
    ...
}

每個定時器設置一個到期滴答數，與當前系統的滴答數(啟動時為0，1滴答1滴答往后跳，1滴答==0.01s ) 比較得到差值interval;

如果interval比較小(0 <= interval <= 2^8-1)，表示定時器即將到來，保存在第一部分前2^8個定時器鏈表中；否則找到屬于第二部分對用的層級中。

// skynet_timer.c
void 
skynet_updatetime(void) {
    ...
    uint32_t diff = (uint32_t)(cp - TI->current_point); 
    TI->current_point = cp;
    TI->current += diff;
    // diff單位為0.01s
    for (i = 0; i < diff; i++){
        timer_update(TI);        
    }
}
static void
timer_update(struct timer *T) {
    SPIN_LOCK(T);
    timer_execute(T); // 檢查T->near是否位空，有就處理到期定時器
    timer_shift(T);  // 時間片time++，移動高24位的鏈表
    timer_execute(T);
    SPIN_UNLOCK(T);
}
// 每幀從T->near中觸發到期得定時器
static inline void
timer_execute(struct timer *T) {
  ...
}
// 遍歷處理定時器鏈表中所有的定時器
static inline void
dispatch_list(struct timer_node *current) {
    ...
}
// 將高24位對應的4個6位的數組中的各個元素的鏈表往低位移
static void
timer_shift(struct timer *T) {
    ...
}
// 將level層的idx位置的定時器鏈表從當前位置刪除，并重新add_node
static void move_list(struct timer *T, int level, int idx) {

}

最小堆實現定時器

最小堆實現例子：boost.asio采用二叉樹，go采用四叉樹， libuv

具體實現略。

總結

本文主要介紹定時器作用，實現定時器數據結構選取，并詳細介紹了跳表，紅黑樹，時間輪實現定時器的思路和方法。

Python人工智能編程分享 Python 相關的技術文章、工具資料、視頻教程等。專注Python編程開發學習以及人工智能、機器學習、自然語言處理、深度學習、圖像識別、語音識別、無人駕駛等前沿AI技術學習！

公眾號