首页 > 其他分享 >多层时间轮原理以及使用

多层时间轮原理以及使用

时间：2024-09-29 13:50:03浏览次数：3  
标签：wheel timePos pos 多层 int 任务 使用 原理 event

文章目录

背景

在软件开发中，定时器是一个极为常用的组件，它发挥着至关重要的作用。通过定时器，开发者能够精确地控制程序中的时间流程，实现诸如定时任务执行、周期性执行、资源延迟释放、状态定时更新等功能。关于定时器的实现方式，存在多种高效且灵活的途径。

常用定时器实现

  • 操作系统级定时器：利用操作系统提供的定时器API，如Linux下的timer_create、timer_settime等，这些API提供了精确的时间控制和事件通知机制，适合需要高精确度控制的场景。
  • 多线程/多进程定时器：通过创建专门的线程或进程来管理定时器任务，这些线程/进程可以独立运行，使用系统时间或自定义的时间管理逻辑来触发定时事件。这种方式在并发处理上有优势，但需注意线程/进程间的同步与资源竞争问题。
  • 事件循环中的定时器：在基于事件循环的编程模型中（epoll_wait），定时器是事件的一种，通过事件循环机制定期检查并执行。这种方式简化了并发控制，但定时精度可能受到事件循环中其他任务执行时间的影响。
  • 时间轮算法：时间轮是一种高效的时间管理算法，通过将时间划分为多个层级和槽位，以轮转的方式管理定时任务。多层时间轮定时器结合了时间轮的高效性和灵活性，能够处理大量定时任务而不引入显著的性能开销。
  • 定时任务队列：使用优先队列（如最小堆）来管理定时任务，每个任务根据其执行时间排序。当有新任务加入或当前时间推进时，队列会自动调整，确保最早到期的任务始终位于队列前端。这种方法适合需要频繁添加和删除任务的场景。

任务队列

  • 1 启动一个定时器线程，线程中有任务队列。
  • 2 其他线程将所有的定时任务放到队列中并进行排序,每个任务都保存一份自己的定时信息,
  • 3 定时器每隔一个周期轮询一遍队列中的所有任务,如果任务的超时时间已到,则执行该任务,如果超时时间还没到,则将该任务的定时信息减掉一个定时器的时间间隔,等到完全减为0时,该任务就可以被执行了
  • 4 根据优先级不同或者定时任务过多 可以拆分为多个定时器

时间轮介绍

在这里插入图片描述

模拟时钟的运作机制，将时间划分为多个固定的时间间隔（称为槽位），并将定时任务存储在相应槽位中，随着时间的推进，时间轮会周期性地转动，执行到达时间点的任务。

基本结构

  • 槽位（Slots）：时间轮上的一系列位置，每个位置代表一个时间间隔。
  • 指针（Pointer）：指向当前时间所在槽位的指针。
  • 链表（Lists）：每个槽位关联一个链表，用于存储在该时间间隔内需要执行的任务。
  • 时间间隔（Tick）：每个槽位代表的时间长度，例如1秒、1分钟等。
    在这里插入图片描述
    在时间轮中，指针的移动和任务的插入方式取决于时间轮的设计和配置

指针移动

在时间轮中，指针通常代表当前的时间点。在每次“tick”（即时间轮的基本时间单位，如1秒）发生时，指针会向前移动一个槽位。因此，如果您的时间轮是以秒为单位设计的，并且每个槽位代表1秒，那么每次时间推进1秒时，指针就会移动到下一个槽位。

定时任务插入

插入一个定时任务时，需要计算该任务应该在哪个槽位被触发。这通常是通过将任务的延迟时间（从当前时间开始计算）除以时间轮的基本时间单位（即tick的长度）来完成的。然后，将结果对时间轮的槽位总数取模，以找到正确的槽位。

示例 1：1秒间隔，5秒后执行的任务
如果时间轮每个槽位代表1秒，并且您想插入一个5秒后执行的任务，可以这样做：

  • 当前时间（指针位置）为 current
  • 延迟时间为 5 秒
  • 计算目标槽位：(current + 5) % WHEEL_SIZE
    然后，将任务插入到计算出的槽位中。如果 current 是 0，并且 WHEEL_SIZE 是 60，那么目标槽位将是 5。

循环任务插入

时间轮本身并不直接支持“周期性任务”，可以通过在任务回调中重新添加任务来实现这一点

  • 首次插入：与上面相同，计算首次执行的槽位，并插入任务。
  • 回调中重新添加：在任务的回调函数中，计算下一次执行的槽位，并再次将任务添加到时间轮中

代码示例

#include <stdio.h>  
#include <stdlib.h>  
#include <stdint.h>  
#include <stdbool.h>  
  
#define WHEEL_SIZE 60 // 假设时间轮有60个槽位，每个槽位代表1秒  
  
// 定时任务结构体  
typedef struct TimerTask {  
    struct TimerTask *next; // 指向下一个任务的指针  
    uint32_t expire;        // 任务到期时间（秒）  
    void (*callback)(void*); // 任务到期时调用的回调函数  
    void *arg;               // 传递给回调函数的参数  
} TimerTask;  
  
// 时间轮结构体  
typedef struct {  
    TimerTask *slots[WHEEL_SIZE]; // 槽位数组，每个槽位指向一个链表头  
    uint32_t current;              // 当前时间（秒），指向当前槽位  
    uint32_t tick;                 // 每个槽位的时间间隔（秒）  
} TimeWheel;  
  
// 初始化时间轮  
void time_wheel_init(TimeWheel *wheel, uint32_t tick)
 { 
    int i =0; 
    for (i = 0; i < WHEEL_SIZE; i++) {  
        wheel->slots[i] = NULL;  
    }  
    wheel->current = 0;  
    wheel->tick = tick;  
}  
  
// 添加定时任务  
void time_wheel_add_task(TimeWheel *wheel, TimerTask *task, uint32_t delay) {  
    uint32_t target = wheel->current + delay; // 计算目标槽位  
    target = target % WHEEL_SIZE; // 循环回到起点  
  
    // 将任务添加到对应槽位的链表头部  
    task->next = wheel->slots[target];  
    wheel->slots[target] = task;  
}  
  
// 模拟时间推进并执行任务（需要外部定时器或线程驱动）  
void time_wheel_tick(TimeWheel *wheel) {  
    TimerTask *task, *temp;  
    uint32_t current = wheel->current;  
  
    // 遍历当前槽位及其后续槽位（因为可能有之前因为溢出而延迟的任务）  
    while (wheel->slots[current] != NULL || (current + 1) % WHEEL_SIZE == wheel->current) {  
        task = wheel->slots[current];  
  
        // 清理当前槽位  
        while (task != NULL) {  
            temp = task;  
            task = task->next;  
  
            // 如果任务已过期（或恰好到期），则执行  
            if (temp->expire <= wheel->current) {  
                temp->callback(temp->arg);  
  
                // 实际应用中，可能需要从链表中删除已执行的任务  
                // 这里为了简化，不进行删除操作  
            }  
        }  
  
        wheel->slots[current] = NULL; // 清空当前槽位  
  
        current = (current + 1) % WHEEL_SIZE; // 移动到下一个槽位  
  
        // 如果回到了起点，说明已经遍历完一轮  
        if (current == wheel->current) {  
            break;  
        }  
  
        // 更新当前时间  
        wheel->current = current;  
    }  
}  
  
// 示例：回调函数  
void example_callback(void *arg) {  
    printf("Task executed with argument: %s\n", (char*)arg);  
}  
  
int main() {  
    TimeWheel wheel;  
    time_wheel_init(&wheel, 1); // 每个槽位代表1秒  
  
    // 创建并添加任务（这里只是示例，实际中需要动态分配内存）  
    TimerTask task1 = {0, 5, example_callback, "Hello"};  
    TimerTask task2 = {0, 10, example_callback, "World"};  
  
    time_wheel_add_task(&wheel, &task1, 5);  
    time_wheel_add_task(&wheel, &task2, 10);  
  
    // 模拟时间推进（这里用循环代替实际的时间推进机制）  
    for (int i = 0; i < 15; i++) {  
        time_wheel_tick(&wheel);  
        printf("Tick %d\n", i + 1);  
    }  
  
    return 0;  
}

多层时间轮

单层时间轮的性能上限很低,一旦精度和时间跨度要求上来,就无法达到期望的目标了
.比如

  • 一个具有10个槽的时间轮,wheel size = 10,每两个槽之间的间隔为1s,这个间隔称为tick,即最小的时间间隔,那么这个时间轮的跨度就是10*1 = 10s,也就是所支持能设置的最大周期为10s,如果一个任务每隔11秒执行一次.就无法使用
  • 内存空间浪费问题：时间尺度密集，任务数量少，大部分时间尺度占用的内存空间没有意义

多层时间轮
在这里插入图片描述

它通过模拟时钟的运作机制，将时间划分为多个层级（如秒、分、时等），并在每个层级上使用一个或多个时间轮来管理定时任务

多层时间轮定时器将时间划分为多个层级，每个层级代表不同的时间单位（如秒、分、时等）。每个层级都有一个时间轮，时间轮上的每个槽位代表一个时间间隔。定时任务根据其超时时间被分配到不同层级的时间轮上，并存储在相应槽位的链表中。随着时间的推移，时间轮转动，当某个槽位的时间到达时，该槽位上的所有定时任务都将被执行。
在这里插入图片描述

使用

  • 秒级时间轮上,设有60个槽, 每两个槽之间的时间为1s.
  • 分钟级时间轮上,设有60s个槽,每两个槽之间的时间为1min
  • 小时级时间轮上,设有24个槽,每两个槽之间的时间为1h.

流程

添加 一个 1分钟 5秒后执行的任务
  • 计算总延迟：首先，计算任务的总延迟时间（以秒为单位），这里是65秒（1分钟 + 5秒）。
  • 确定分层槽位：将总延迟除以分层的时间间隔（60秒），得到分层槽位的索引。对于65秒，这将是 65 / 60 = 1（取整数部分），意味着任务将在分层的第2个槽位触发（索引从0开始）。注意：分层槽位仅代表分钟的开始，并不精确到秒。
  • 确定秒层槽位：计算剩余的秒数（65 % 60 = 5），这表示在分层槽位对应的时间点之后，任务还需要在秒层等待5秒才能执行。
  • 添加任务到秒层并分层：
    如果任务仅在当前分钟内执行：可以将任务添加到秒层的第5个槽位（假设时间轮当前指针在0秒位置，并且它会在下一轮中移动到正确的槽位）。但是，由于时间轮是周期性的，如果当前时间接近分钟结束，您可能需要将任务添加到下一轮的秒层中，并设置标记来指示它应该在上一个分层的下一个周期执行。

代码

#include <memory>
#include <list>
#include <vector>
#include <mutex>

typedef struct TimePos{
    int pos_ms;
    int pos_sec;
    int pos_min;
}TimePos_t;

typedef struct Event {
    int id;
    void(*cb)(void);
    void* arg;
    TimePos_t timePos;
    int interval;
}Event_t;


class TimeWheel {
    typedef std::shared_ptr<TimeWheel> TimeWheelPtr;
    typedef void (*EventCallback_t)(void );
    typedef std::vector<std::list<Event_t>> EventSlotList_t;
public:
    TimeWheel();
    
    void initTimeWheel(int steps, int maxMin);
    void createTimingEvent(int interval, EventCallback_t callback);

public:
    static void* loopForInterval(void* arg);
    
private:
    int getCurrentMs(TimePos_t timePos);
    int createEventId();
    int processEvent(std::list<Event_t> &eventList);
    void getTriggerTimeFromInterval(int interval, TimePos_t &timePos);
    void insertEventToSlot(int interval, Event_t& event);

    EventSlotList_t m_eventSlotList;
    TimePos_t m_timePos;
    pthread_t m_loopThread;

    int m_firstLevelCount;
    int m_secondLevelCount;
    int m_thirdLevelCount; 
    
    int m_steps;
    int m_increaseId;  // not used
    std::mutex m_mutex;
};
TimeWheel.cpp

#include "TimeWheel.h"

#include <iostream>
#include <memory.h>
#include <chrono>
#include <thread>

TimeWheel::TimeWheel() : m_steps(0), m_firstLevelCount(0), m_secondLevelCount(60), m_thirdLevelCount(0),
                         m_increaseId (0){
                            memset(&m_timePos, 0, sizeof(m_timePos));
                         }

void* TimeWheel::loopForInterval(void* arg)
{
    if(arg == NULL) {
        printf("valid parameter\n");
        return NULL;
    }
    TimeWheel* timeWheel = reinterpret_cast<TimeWheel*>(arg);
    while(1) {
       std::this_thread::sleep_for(std::chrono::milliseconds(timeWheel->m_steps));
        // printf("wake up\n");
        TimePos pos = {0};
        TimePos m_lastTimePos = timeWheel->m_timePos;
        //update slot of current TimeWheel
        timeWheel->getTriggerTimeFromInterval(timeWheel->m_steps, pos);
        timeWheel->m_timePos = pos;
        {
            std::unique_lock<std::mutex> lock(timeWheel->m_mutex);
            // if minute changed, process in integral point (minute)
            if (pos.pos_min != m_lastTimePos.pos_min)
            {
                // printf("minutes changed\n");
                std::list<Event_t>* eventList = &timeWheel->m_eventSlotList[timeWheel->m_timePos.pos_min + timeWheel->m_firstLevelCount + timeWheel->m_secondLevelCount];
                timeWheel->processEvent(*eventList);
                eventList->clear();
           }
            else if (pos.pos_sec != m_lastTimePos.pos_sec)
            {
                //in same minute, but second changed, now is in this integral second
                // printf("second changed\n");
                std::list<Event_t>* eventList = &timeWheel->m_eventSlotList[timeWheel->m_timePos.pos_sec + timeWheel->m_firstLevelCount];
                timeWheel->processEvent(*eventList);
                eventList->clear();
            }
            else if (pos.pos_ms != m_lastTimePos.pos_ms)
            {
                //now in this ms
                // printf("ms changed\n");
                std::list<Event_t>* eventList = &timeWheel->m_eventSlotList[timeWheel->m_timePos.pos_ms];
                timeWheel->processEvent(*eventList);
                eventList->clear();
            }
            // printf("loop over\n");
        }
     
    }

    return nullptr;
}

//init TimeWheel's step and maxmin, which detemine the max period of this wheel
void TimeWheel::initTimeWheel(int steps, int maxMin)
{
    if (1000 % steps != 0){
        printf("invalid steps\n");
        return;
    }
    m_steps = steps;
    m_firstLevelCount = 1000/steps;
    m_thirdLevelCount = maxMin;

    m_eventSlotList.resize(m_firstLevelCount + m_secondLevelCount + m_thirdLevelCount);
    int ret = pthread_create(&m_loopThread, NULL, loopForInterval, this);
    if(ret != 0) {
        printf("create thread error:%s\n", strerror(errno));
        return;
    }
    // pthread_join(m_loopThread, NULL);
}

void TimeWheel::createTimingEvent(int interval, EventCallback_t callback){
    if(interval < m_steps || interval % m_steps != 0 || interval >= m_steps*m_firstLevelCount*m_secondLevelCount*m_thirdLevelCount){
        printf("invalid interval\n");
        return;
    }
    printf("start create event\n");
    Event_t event = {0};
    event.interval = interval;
    event.cb = callback;
    //set time start
    event.timePos.pos_min = m_timePos.pos_min;
    event.timePos.pos_sec = m_timePos.pos_sec;
    event.timePos.pos_ms = m_timePos.pos_ms;
    event.id = createEventId();
    // insert it to a slot of TimeWheel
     std::unique_lock<std::mutex> lock(m_mutex);
    insertEventToSlot(interval, event);
    printf("create over\n");
}


int TimeWheel::createEventId() {
    return m_increaseId++;  
}


void TimeWheel::getTriggerTimeFromInterval(int interval, TimePos_t &timePos) {
    //get current time: ms
    int curTime = getCurrentMs(m_timePos);
    // printf("interval = %d,current ms = %d\n", interval, curTime);

    //caculate which slot this interval should belong to 
    int futureTime = curTime + interval;
    // printf("future ms = %d\n", futureTime);
    timePos.pos_min =  (futureTime/1000/60)%m_thirdLevelCount;
    timePos.pos_sec =  (futureTime%(1000*60))/1000;
    timePos.pos_ms = (futureTime%1000)/m_steps;

    // printf("next minPos=%d, secPos=%d, msPos=%d\n", timePos.pos_min, timePos.pos_sec, timePos.pos_ms);
    return;
}

int TimeWheel::getCurrentMs(TimePos_t timePos) {
    return m_steps * timePos.pos_ms + timePos.pos_sec*1000 +  timePos.pos_min*60*1000;
}

int TimeWheel::processEvent(std::list<Event_t> &eventList){
    // printf("eventList.size=%d\n", eventList.size());

    //process the event for current slot
    for(auto event = eventList.begin(); event != eventList.end(); event ++) {
        //caculate the current ms
        int currentMs = getCurrentMs(m_timePos);
        //caculate last  time(ms) this event was processed
        int lastProcessedMs = getCurrentMs(event->timePos);
        //caculate the distance between now and last time(ms)
        int distanceMs = (currentMs - lastProcessedMs + (m_secondLevelCount+1)*60*1000)%((m_secondLevelCount+1)*60*1000);

        //if interval == distanceMs, need process this event
        if (event->interval == distanceMs)
        {
            //process event
            event->cb();
            //get now pos as this event's start point
            event->timePos = m_timePos;
            //add this event to slot
            insertEventToSlot(event->interval, *event);
        }
        else
        {
            //this condition will be trigger when process the integral point 
            printf("event->interval != distanceMs\n");
            // although this event in this positon, but it not arriving timing, it will continue move to next slot caculate by distance ms.
            insertEventToSlot(distanceMs, *event);
        }
    }
    return 0;
}

void TimeWheel::insertEventToSlot(int interval, Event_t& event)
{
    printf("insertEventToSlot\n");

    TimePos_t timePos = {0};

    //caculate the which slot this event should be set to
    getTriggerTimeFromInterval(interval, timePos);
     {
        // printf("timePos.pos_min=%d, m_timePos.pos_min=%d\n", timePos.pos_min, m_timePos.pos_min);
        // printf("timePos.pos_sec=%d, m_timePos.pos_sec=%d\n", timePos.pos_sec, m_timePos.pos_sec);
        // printf("timePos.pos_ms=%d, m_timePos.pos_ms=%d\n", timePos.pos_ms, m_timePos.pos_ms);

        // if minutes not equal to current minute, first insert it to it's minute slot
        if (timePos.pos_min != m_timePos.pos_min)
        {
            printf("insert to %d minute\n", m_firstLevelCount + m_secondLevelCount + timePos.pos_min);
                m_eventSlotList[m_firstLevelCount + m_secondLevelCount + timePos.pos_min]
                    .push_back(event);
        }
        // if minutes is equal, but second changed, insert slot to this  integral point second
        else if (timePos.pos_sec != m_timePos.pos_sec)
        {
            printf("insert to %d sec\n",m_firstLevelCount + timePos.pos_sec);
            m_eventSlotList[m_firstLevelCount + timePos.pos_sec].push_back(event);
        }
        //if minute and second is equal, mean this event will not be trigger in integral point, set it to ms slot
        else if (timePos.pos_ms != m_timePos.pos_ms)
        {
            printf("insert to %d ms\n", timePos.pos_ms);
            m_eventSlotList[timePos.pos_ms].push_back(event);
        }
     }
    return;
}

测试


#include <iostream>
#include "TimeWheel.h"
using namespace std;

void funccc(void) {
    cout << "exec function" << endl;
}

int main()
{
    TimeWheel wheel;
    wheel.initTimeWheel(100, 10);
    wheel.createTimingEvent(200, funccc);
    while (1)
    {
       
    }
}

标签：wheel,timePos,pos,多层,int,任务,使用,原理,event
From： https://blog.csdn.net/zhangdonghuirjdd/article/details/142630513

相关文章

  • 最强AI绘画大模型Flux可以在SDWebUI 上使用了！超便捷的Flux模型使用教程
    大家好，我是画画的小强目前最强的AI绘画大模型Flux.1横空出世有段时间了，模型效果也得到了广泛的认可，但是StableDiffusionWebUI官方迟迟没有跟进，据说是因为要修改很多底层的处理机制，加之ComfyUI如火如荼，可能AUTOMATIC1111大佬的心气也不是很高，选择了躺平，又或者是在秘密......
  • EasyExcel导出文件基本流程以及原理分析 学习笔记（持续更新）
    EasyExcel导出文件基本流程导出文件基本流程获取数据首先获得需要导出的文件的数据内容，用一个list保存List<SysStudent>list=sysStudentService.queryList(sysStudent);定义文件名给导出的文件定义一个名字，可以添加日期或者根据输入添加其他信息，保证文件名唯一S......
  • 【数据库】Java 中 MongoDB 使用指南：步骤与方法介绍
    MongoDB是一个流行的NoSQL数据库，因其灵活性和高性能而广泛使用。在Java中使用MongoDB，可以通过MongoDB官方提供的Java驱动程序来实现。本文将详细介绍在Java中使用MongoDB的步骤以及相关方法。1.环境准备1.1安装MongoDB首先，确保你的系统中安装了Mongo......
  • Lemon Beta 安装&使用 保姆级教程
    准备食材LemonBeta（点击此处下载）Mingw-w64（点击此处下载）安装1)安装LemonBeta把LemonBeta压缩包下载下来解压，注意lemon.exe要设置以管理员身份打开。如果想永久设置，可以右键lemon.exe，依次点击属性——兼容性选项卡——勾选以管理员身份运行此程序——确定。可......
  • 确保所有域名都能正常使用 PBootCMS 的功能
    在PBootCMS中，如果您的站点需要绑定多个域名，并且每个域名都需要有独立的授权码，实际上并不直接支持在单一授权码输入框内用逗号分隔的方式来输入多个授权码。PBootCMS的授权机制通常是一个授权码对应一个站点绑定。但是，如果你有特殊需求或场景确实需要在不同域名间共用一个后台系统，......
  • 生产数据恢复系列之使用my2sql恢复MySQL8 误删数据
    生产数据恢复系列之使用my2sql恢复MySQL8误删数据原创 我科绝伦 小周的数据库进阶之路  2024年09月25日00:00 重庆热衷于分享各种干货知识，大家有想看或者想学的可以评论区留言，秉承着“开源知识来源于互联网，回归于互联网”的理念，分享一些日常工作中能用到或者频率......
  • 使用WebClient 快速发起请求（不使用WebClientUtils工具类）
    使用WebClient发起网络请求_webclient工具类-CSDN博客文章浏览阅读717次，点赞9次，收藏8次。使用WebClient发起网络请求_webclient工具类https://blog.csdn.net/qq_43544074/article/details/137044825这个是使用工具类发起的，下面就不使用工具类进行快速发起。同样的导入依赖<......
  • python 使用 pyinstaller 打包
    python使用pyinstaller打包1、下载pyinstallerpipinstallpyinstaller2、在当前目录下生成.spec文件注意，这行命令在生成文件的时候，也打包了输出物pyinstaller--name=pytaskermain.py--onefile--specpath=.2.1、生成的目录结构D:.│main.py│pytasker.spe......
  • Windows开发工具使用技巧
    Windows开发工具使用技巧涵盖了多个方面，从基本的界面操作到高级的调试与插件扩展，都对提升开发效率有着至关重要的作用。以下将详细探讨Windows开发工具（如VisualStudio、IntelliJIDEA等）的多种使用技巧一、基础操作与界面优化1.桌面图标随意排列在Windows系统中，桌面图标......
  • .NET常见的几种项目架构模式，你知道几种？（附带使用情况投票）
    .NET常见的几种项目架构模式，你知道几种？（附带使用情况投票） 思维导航前言三层架构MVC架构DDD分层架构整洁架构CQRS架构最后总结参考文章DotNetGuide技术社区前言项目架构模式在软件开发中扮演着至关重要的角色，它们为开发者提供了一套组织和管理代码的指导原则，以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99