时间轮算法设计实现

时间轮算法基本思想

• 参照时钟运转的思路，每个相同刻度下的时间是相同的，将所有相同时间的时间放在一个槽中，通过用一个指针每过一个刻度指向时间轮的槽，取出槽中链表，循环遍历相同刻度下的事件。（liunx内核就是这么做的）。
  
• 如图所示的是一个时间轮的基本结构。时间轮分为N个时间槽slot，每时间槽指向一个定时器链表，这个链表里包含多个定时器，这个链表的定时器Timeout时间相同，因此链表里的定时器无须排序。

简单时间轮的实现

#include <unistd.h>
#include <iostream>
#include <vector>
#include <list>
using namespace std;

#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif

class CTimerNode {
public:
    CTimerNode(int fd) : id(fd), ref(0) {}

	// 由于在时间轮中,如果数量过多,查找麻烦,因此要离线直接置为引用为0即可.
    void Offline() {
        this->ref = 0;
    }

    bool TryKill() {
        DecrRef();
        if (this->ref == 0) {
            cout << id << " is killed down" << endl;
            return true;
        }
        cout << id << " ref is " << ref << endl;
        return false;
    }
	// 通过增加引用计数，避免了删除节点的时候去查找
	// 只要引用计数为0，则说明该节点需要删除
    void IncrRef() {
        this->ref++;
    }

protected:
    void DecrRef() {
        this->ref--;
    }

private:
    int ref;
    int id;
};

const int TW_SIZE = 16;
const int EXPIRE = 10;
const int TW_MASK = TW_SIZE - 1;
static size_t iRealTick = 0;
typedef list<CTimerNode*> TimeList;
typedef TimeList::iterator TimeListIter;
typedef vector<TimeList> TimeWheel;

void AddTimeout(TimeWheel &tw, CTimerNode *p) {
    if (p) {
        p->IncrRef();
		// 当前事件加上要EXPIRE秒后要执行
        TimeList &le = tw[(iRealTick+EXPIRE) & TW_MASK];
        le.push_back(p);
    }
}

// 用来表示delay时间后调用 AddTimeout
void AddTimeoutDelay(TimeWheel &tw, CTimerNode *p, size_t delay) {
    if (p) {
        p->IncrRef();
        TimeList &le = tw[(iRealTick+EXPIRE+delay) & TW_MASK];
        le.push_back(p);
    }
}

// 每过一个时间刻度，执行一次
void TimerShift(TimeWheel &tw)
{
    size_t tick = iRealTick;
    iRealTick++;
    TimeList &le = tw[tick & TW_MASK];
    TimeListIter iter = le.begin();
    for (; iter != le.end();) {
		// 取出结点
        CTimerNode *p = *iter;
        if (p && p->TryKill()) {
            delete p;
            le.erase(iter++);
        } else {
			// 此处执行定时任务即可
			// 定时任务可以绑定再timenode结点中。
			iter++;
		}
    }
}

static time_t
current_time() {
	time_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
	struct timespec ti;
	clock_gettime(CLOCK_MONOTONIC, &ti);
	t = (time_t)ti.tv_sec;
#else
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = (time_t)tv.tv_sec;
#endif
	return t;
}

int main ()
{
    TimeWheel tw(TW_SIZE);

    CTimerNode *p = new CTimerNode(10001);

    AddTimeout(tw, p);

    AddTimeoutDelay(tw, p, 5);

    time_t start = current_time();
    for (;;) {
        time_t now = current_time();
        if (now - start > 0) {
            for (int i=0; i<now-start; i++)
                TimerShift(tw);
            start = now;
            cout << "check timer shift " << iRealTick <<  endl;
        }
        usleep(2500);
    }

    return 0;
}

复杂时间轮(linux内核时间轮的思路)

• 只要低层的指针刻度走完，就将高一层的指针刻度前进一格，并将那一格的数据释放到低一层的时间轮中。思想就和时钟的时分秒三种刻度的运转差不多。只是这个时间轮，每个刻度里面带了一长串的链表。