原理

定时器的精度

假设每一格为2.5 ms

0.0025 * 256 * 63 * 63 *63 *63 = 10,081,895.04 sec

10,081,895.04 / 60 / 60 /24 = 116.6886 day

定时器有效时间最大范围unsigned int 2^32

拆分为5个时间轮

2^8 2^6 2^6 2^6 2^6

0~255 0~63 0~63 0~63 0~63

首先对第一个时间轮进行 时长%时间轮长度(优化用&替代%运算符 时长&(时间轮长度-1))

 未超过就将定时任务放入对应格子链表

第一轮盘每一格代表(1) 范围256

超过时就往下面找

第二轮盘每一格代表(256) 范围 16,384‬

第三轮盘每一格代表(64 * 256) 范围 1,048,576‬

第四轮盘每一格代表(64 * 64 * 256) 范围  67,108,864‬

第五轮盘每一格代表(64 * 64 * 64 * 256) 范围 4,294,967,296‬

时间轮的映射

例如256的时候,就将第二轮盘的0位置的一堆元素取出,每一个元素对&256-1 放入第一轮盘

锁采用自旋锁,因为这种简单切换映射如果用互斥锁 线程切换会陷入到内核态 得不偿失

实现

define.h

#pragma once
// 使用位运算符提高效率
// 时间轮定义
#define TVR_BITS 8                // 第1个轮占得位数
#define TVR_SIZE (1 << TVR_BITS)  // 第1个轮长度256
#define TVN_BITS 6                // 第N个轮占的位数
#define TVN_SIZE (1 << TVN_BITS)  // 第N个轮长度64
#define TVN_MASK (TVN_SIZE - 1)   // 取模或整除用
#define TVR_MASK (TVR_SIZE - 1)   // 取模或整除用

// 求第N轮盘所在初始位置 第一个轮盘大小 + (第几个轮盘 * 轮盘长度)
#define OFFSET(N) (TVR_SIZE + (N)*TVN_SIZE)
// 求expires所在第N个轮盘中的某个位置 (用当前expires右移 (第一个轮盘所占位数+(第N个轮盘*第N个轮盘所占位数) &
// 第N轮盘长度-1 得到第N个轮盘中的位置
#define INDEX(V, N) (((V) >> (TVR_BITS + (N)*TVN_BITS)) & TVN_MASK)

common_func.h

#pragma once
#include <chrono>
#include <thread>

namespace sunny::common_func {
static unsigned long long get_tick_count() {
    unsigned long long tick_count = 0;
    struct timespec on {};
    if (0 == clock_gettime(CLOCK_MONOTONIC, &on)) {
        tick_count = on.tv_sec * 1000 + on.tv_nsec / 1000000;
    }

    return tick_count;
}

static void sleep_microseconds(std::size_t microseconds) {
    std::this_thread::sleep_for(std::chrono::microseconds(microseconds));
}
}  // namespace sunny::common_func

timer_event.h

#pragma once

#include <functional>
#include <memory>

namespace sunny {
struct timer_event final {
    using ptr = std::shared_ptr<timer_event>;

    timer_event() = default;

    ~timer_event() = default;

    void init(std::function<void()> call_back, unsigned int expires, unsigned int interval, unsigned int count);

    bool execute(unsigned long long now);

    unsigned long long interval_{};
    unsigned long long expires_{};
    unsigned int slot_pos_{};
    unsigned int count_{};
    std::function<void()> call_back_{};
};
}  // namespace sunny

timer_event.cc

#include "timer_event.h"

#include "common_func.h"

namespace sunny {
void timer_event::init(std::function<void()> call_back, unsigned int expires, unsigned int interval, unsigned int count) {
    expires_ = expires + common_func::get_tick_count();
    interval_ = interval;
    count_ = count;
    slot_pos_ = -1;
    call_back_ = call_back;
}

bool timer_event::execute(unsigned long long now) {
    if (call_back_) {
        call_back_();
    }

    if (--count_ > 0) {
        expires_ = interval_ + now;
        return true;
    }

    return false;
}
}  // namespace sunny

time_wheel.h

#pragma once

#include <list>
#include <memory>
#include <utility>
#include <vector>

#include "define.h"
#include "timer_event.h"

namespace sunny {
class time_wheel final {
public:
    time_wheel();

    ~time_wheel() = default;

public:
    void add_timer_event(std::function<void()> func, unsigned int delay, unsigned int interval, unsigned int count);

    void remove_timer_event(timer_event::ptr event);

    void update();

private:
    void add_timer_event(timer_event::ptr event);

    int cascade(int offset, int index);

private:
    using time_list = std::list<timer_event::ptr>;
    std::vector<time_list> times_{};
    uint64_t check_time_{};
};
}  // namespace sunny

time_wheel.cc

#include "time_wheel.h"

#include "common_func.h"

namespace sunny {
time_wheel::time_wheel()
    : check_time_(common_func::get_tick_count()) {
    times_.resize(TVR_SIZE + 4 * TVN_SIZE);
}

void time_wheel::add_timer_event(std::function<void()> func, unsigned int delay, unsigned int interval, unsigned int count) {
    auto event = std::make_shared<timer_event>();
    event->init(func, delay, interval, count);
    add_timer_event(event);
}

void time_wheel::update() {
    unsigned long long now = common_func::get_tick_count();
    while (check_time_ <= now) {
        unsigned int index = check_time_ & TVR_MASK;
        if (!index && !cascade(OFFSET(0), INDEX(check_time_, 0)) && !cascade(OFFSET(1), INDEX(check_time_, 1)) && !cascade(OFFSET(2), INDEX(check_time_, 2))) {
            cascade(OFFSET(3), INDEX(check_time_, 3));
        }
        ++check_time_;

        time_list& timers = times_[index];
        if (timers.empty()) {
            continue;
        }

        time_list temp;
        temp.splice(temp.end(), timers);

        for (const auto& itr : temp) {
            if (itr->execute(now)) {
                add_timer_event(itr);
            }
        }
    }
}

void time_wheel::add_timer_event(timer_event::ptr event) {
    unsigned long long expires = event->expires_;
    long long idx = expires - check_time_;

    if (idx < TVR_SIZE) {
        event->slot_pos_ = expires & TVR_MASK;
    } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
        event->slot_pos_ = OFFSET(0) + INDEX(expires, 0);
    } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
        event->slot_pos_ = OFFSET(1) + INDEX(expires, 1);
    } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
        event->slot_pos_ = OFFSET(2) + INDEX(expires, 2);
    } else if (idx < 0) {
        event->slot_pos_ = check_time_ & TVR_MASK;
    } else {
        if (idx > 0xffffffffUL) {
            idx = 0xffffffffUL;
            expires = idx + check_time_;
        }
        event->slot_pos_ = OFFSET(3) + INDEX(expires, 3);
    }

    time_list& list = times_[event->slot_pos_];
    list.push_back(event);
}

void time_wheel::remove_timer_event(timer_event::ptr event) {
    time_list& list = times_[event->slot_pos_];
    list.remove(event);
}

int time_wheel::cascade(int offset, int index) {
    time_list& list = times_[offset + index];
    time_list temp;
    temp.splice(temp.end(), list);

    for (auto& itr : temp) {
        add_timer_event(itr);
    }

    return index;
}
}  // namespace sunny

main.cc

#include <iostream>

#include "common_func.h"
#include "time_wheel.h"

using namespace sunny;
int main() {
    time_wheel timer;
    timer.add_timer_event(
        []() {
            std::cout << "hello world" << std::endl;
        },
        1 * 1000, 2 * 1000, 10);
    while (true) {
        timer.update();
        common_func::sleep_microseconds(2500);
    }
    return 0;
}