湖南省建设厅seo搜索优化工具

背景

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

常用定时器实现

• 操作系统级定时器：利用操作系统提供的定时器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 usedstd::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 TimeWheeltimeWheel->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 startevent.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 TimeWheelstd::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: msint 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 slotfor(auto event = eventList.begin(); event != eventList.end(); event ++) {//caculate the current msint currentMs = getCurrentMs(m_timePos);//caculate last  time(ms) this event was processedint 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 eventif (event->interval == distanceMs){//process eventevent->cb();//get now pos as this event's start pointevent->timePos = m_timePos;//add this event to slotinsertEventToSlot(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 togetTriggerTimeFromInterval(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 slotif (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 secondelse 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 slotelse 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){}
}