时间轮设计

目录

基本概念

函数定义

函数实现与测试

测试1结果如下

测试2结果如下

---

基本概念

时间轮 是一种 实现延迟功能（定时器） 的 巧妙算法。如果一个系统存在大量的任务调度，时间轮可以高效的利用线程资源来进行批量化调度。把大批量的调度任务全部都绑定时间轮上，通过时间轮进行所有任务的管理，触发以及运行。能够高效地管理各种延时任务，周期任务，通知任务等。

这几张图是了解了解用的，可能看不懂，用以解决mudo服务器中高并发性能的要求的

weak_ptr了解一下下

函数定义

#include <iostream>
#include <stdint.h>
#include <functional>
#include <vector>
#include <memory>
#include <unordered_map>

using TaskFunc = std::function<void()>;
using ReleaseFunc = std::function<void()>;
class TimerTask
{
private:
    uint64_t _id;         // 定时器任务对象
    uint32_t _timeout;    // 定时任务的超时时间
    TaskFunc _task_cb;    // 定时器要执行的定时任务
    ReleaseFunc _release; // 用于删除TimerWheel中保存的定时器对象信息
public:
    TimerTask(uint64_t id, uint32_t delay, const TaskFunc &cb) : _id(id), _timeout(delay), _task_cb(cb) {}
    ~TimerTask()
    {
        _task_cb();
        _release();
    }
    void SetRelease(const ReleaseFunc &cb) { _release = cb; }
};

class TimerWheel
{
private:
    using WeakTask = std::weak_ptr<TimerTask>;
    using PtrTask = std::shared_ptr<TimerTask>;
    int _tick;                                      // 当前的的秒针，走到哪里哪里就释放执行
    int _capacity;                                  // 表盘最大数量 -- 其实就是最大延迟时间
    std::vector<std::vector<PtrTask>> _wheel;
    std::unordered_map<uint64_t, WeakTask> _timers; // 用weak_ptr来构造出新的shared_ptr用来计数，不过后续要记得释放
public:
    TimerWheel() : _capacity(60), _tick(0), _wheel(_capacity) {}
    void TimerAdd(uint64_t id, uint32_t delay, const TaskFunc &cb); // 添加定时任务
    void TimerRefresh(uint64_t id);                                 // 刷新/延迟定时任务
};

函数实现与测试

#include <iostream>
#include <stdint.h>
#include <functional>
#include <vector>
#include <memory>
#include <unordered_map>
#include <unistd.h>

using TaskFunc = std::function<void()>;
using ReleaseFunc = std::function<void()>;
class TimerTask
{
private:
    uint64_t _id;         // 定时器任务对象
    uint32_t _timeout;    // 定时任务的超时时间
    bool _canceled;       // false-表示没有被取消，true-表示被取消
    TaskFunc _task_cb;    // 定时器要执行的定时任务
    ReleaseFunc _release; // 用于删除TimerWheel中保存的定时器对象信息
public:
    TimerTask(uint64_t id, uint32_t delay, const TaskFunc &cb) : _id(id), _timeout(delay), _task_cb(cb), _canceled(false) {}
    ~TimerTask()
    {
        if (_canceled == false)
            _task_cb();
        _release();
    }
    void Cancel() { _canceled = true; }
    void SetRelease(const ReleaseFunc &cb) { _release = cb; }
    uint32_t DelayTime() { return _timeout; } // 返回时间
};

class TimerWheel
{
private:
    using WeakTask = std::weak_ptr<TimerTask>;
    using PtrTask = std::shared_ptr<TimerTask>;
    int _tick;     // 当前的的秒针，走到哪里哪里就释放执行
    int _capacity; // 表盘最大数量 -- 其实就是最大延迟时间
    std::vector<std::vector<PtrTask>> _wheel;
    std::unordered_map<uint64_t, WeakTask> _timers; // 用weak_ptr来构造出新的shared_ptr用来计数，不过后续要记得释放
private:
    void RemoveTimer(uint64_t id)
    {
        auto it = _timers.find(id);
        if (it != _timers.end())
        {
            _timers.erase(it);
        }
    }

public:
    TimerWheel() : _capacity(60), _tick(0), _wheel(_capacity) {}
    void TimerAdd(uint64_t id, uint32_t delay, const TaskFunc &cb) // 添加定时任务
    {
        PtrTask pt(new TimerTask(id, delay, cb));                      // 实例化定时任务对象
        pt->SetRelease(std::bind(&TimerWheel::RemoveTimer, this, id)); // 第0个位置是隐藏的this指针。再把任务id绑定进去
        int pos = (_tick + delay) % _capacity;
        _wheel[pos].push_back(pt);
        _timers[id] = WeakTask(pt);
    }
    // 刷新/延迟定时任务
    void TimerRefresh(uint64_t id)
    {
        // 通过保存的定时器对象的weak_ptr构造一个shared_ptr出来, 添加到轮子中
        auto it = _timers.find(id);
        if (it == _timers.end())
        {
            return; // 没找到定时任务, 没法刷新，没法延迟
        }
        PtrTask pt = it->second.lock(); // lock获取weak_ptr管理的对象对应的shared_ptr
        int delay = pt->DelayTime();    // 获取到了初始的延迟时间
        int pos = (_tick + delay) % _capacity;
        _wheel[pos].push_back(pt);
    }
    void TimerCancel(uint64_t id)
    {
        auto it = _timers.find(id);
        if (it == _timers.end())
        {
            return; // 没找到定时任务, 没法刷新，没法延迟
        }
        PtrTask pt = it->second.lock(); // 当还没有过期才进行取消
        if(pt) pt->Cancel();
    }
    // 这个函数应该每秒钟被执行一次，相当于秒钟向后走了一步
    void RunTimerTask()
    {
        _tick = (_tick + 1) % _capacity;
        _wheel[_tick].clear(); // 清空指定位置的数组，就会把数组中保存的所有管理定时器对象的shared_ptr释放掉.从而执行函数
    }
};

// 以下是测试
class Test
{
public:
    Test() { std::cout << "构造" << std::endl; }
    ~Test() { std::cout << "析构" << std::endl; }
};

void DelTest(Test *t)
{
    delete t;
}

int main()
{
    TimerWheel tw;
    Test *t = new Test();

    tw.TimerAdd(888, 5, std::bind(DelTest, t));

    for (int i = 0; i < 5; i++)
    {
        sleep(1);
        tw.TimerRefresh(888); // 刷新定时任务
        tw.RunTimerTask();    // 向后移动秒针
        std::cout << "刷新了一下定时任务，重新需要5s钟后才会销毁\n";
    }
    // tw.TimerCancel(888); // 取消定时任务的测试
    while (1)
    {
        sleep(1);
        std::cout << "------------------------\n";
        tw.RunTimerTask(); // 向后移动秒钟
    }

    return 0;
}

测试1结果如下

达到预期

测试2结果如下

将下列代码放开

测试2结果如下

取消成功，达到预期