Skynet定時(shí)器實(shí)現(xiàn)方案

skynet中定時(shí)器數(shù)據(jù)結(jié)構(gòu)

采用時(shí)間輪方式，hash表+鏈表實(shí)現(xiàn)，

struct timer_node {  //時(shí)間節(jié)點(diǎn)
 struct timer_node *next;
    uint32_t expire; //到期滴答數(shù)
};
struct link_list {  // 鏈表
  struct timer_node head;
  struct timer_node *tail;
};
struct timer {
 struct link_list near[256];  // 即將到來(lái)的定時(shí)器
    struct link_list t[4][64]; // 相對(duì)較遙遠(yuǎn)的定時(shí)器
    struct spinlock lock;
    uint32_t time;  // 記錄當(dāng)前滴答數(shù)
    uint64_t starttime;
    uint64_t current;
    uint64_t current_point;
};

其中time為32位無(wú)符號(hào)整數(shù)， 記錄時(shí)間片對(duì)應(yīng)數(shù)組near[256] ，表示即將到來(lái)的定時(shí)任務(wù)， t[4][64]，表示較為遙遠(yuǎn)的定時(shí)任務(wù)。

定時(shí)器執(zhí)行流程

skynet_time_wheel

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

以下為具體實(shí)現(xiàn)，僅貼出主要接口，具體細(xì)節(jié)請(qǐng)參考skynet源代碼。

定時(shí)器初始化

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

添加定時(shí)器

通過(guò)skynet_server.c中的cmd_timeout調(diào)用skynet_timeout添加新的定時(shí)器

// TI為全局的定時(shí)器指針
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;
    // 添加新的定時(shí)器節(jié)點(diǎn)
    timer_add(TI, &event, sizeof(event), time);
    return session;
}
// 添加新的定時(shí)器節(jié)點(diǎn)
static void timer_add(struct timer *T, void 8arg, size_t sz, int time) {
    // 給timer_node指針?lè)峙淇臻g，還需要分配timer_node + timer_event大小的空間，
    // 之后通過(guò)node + 1可獲得timer_event數(shù)據(jù)
    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);
}

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

驅(qū)動(dòng)方式

skynet啟動(dòng)時(shí)，會(huì)創(chuàng)建一個(gè)線程專門(mén)跑定時(shí)器，每幀(0.0025s)調(diào)用skynet_updatetime()

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

每個(gè)定時(shí)器設(shè)置一個(gè)到期滴答數(shù)，與當(dāng)前系統(tǒng)的滴答數(shù)(啟動(dòng)時(shí)為0，1滴答1滴答往后跳，1滴答==0.01s ) 比較得到差值interval;

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

// 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(mén)->near是否位空，有就處理到期定時(shí)器
    timer_shift(T);  // 時(shí)間片time++，移動(dòng)高24位的鏈表
    timer_execute(T);
    SPIN_UNLOCK(T);
}
// 每幀從T->near中觸發(fā)到期得定時(shí)器
static inline void
timer_execute(struct timer *T) {
  ...
}
// 遍歷處理定時(shí)器鏈表中所有的定時(shí)器
static inline void
dispatch_list(struct timer_node *current) {
    ...
}
// 將高24位對(duì)應(yīng)的4個(gè)6位的數(shù)組中的各個(gè)元素的鏈表往低位移
static void
timer_shift(struct timer *T) {
    ...
}
// 將level層的idx位置的定時(shí)器鏈表從當(dāng)前位置刪除，并重新add_node
static void move_list(struct timer *T, int level, int idx) {

}

最小堆實(shí)現(xiàn)定時(shí)器

最小堆實(shí)現(xiàn)例子：boost.asio采用二叉樹(shù)，go采用四叉樹(shù)， libuv

具體實(shí)現(xiàn)略。

總結(jié)

本文主要介紹定時(shí)器作用，實(shí)現(xiàn)定時(shí)器數(shù)據(jù)結(jié)構(gòu)選取，并詳細(xì)介紹了跳表，紅黑樹(shù)，時(shí)間輪實(shí)現(xiàn)定時(shí)器的思路和方法。

Python人工智能編程分享 Python 相關(guān)的技術(shù)文章、工具資料、視頻教程等。專注Python編程開(kāi)發(fā)學(xué)習(xí)以及人工智能、機(jī)器學(xué)習(xí)、自然語(yǔ)言處理、深度學(xué)習(xí)、圖像識(shí)別、語(yǔ)音識(shí)別、無(wú)人駕駛等前沿AI技術(shù)學(xué)習(xí)！

公眾號(hào)