利用C语言实现经典多级时间轮定时器-北京尧图网络

前言时间轮timer wheel是一种用来管理大量定时任务的数据结构。最朴素的做法是把所有定时器放进一个按到期时间排序的链表或最小堆每次取最早到期的那个。最小堆的插入与删除是 O(log n)对几万个定时器已经够用但当定时器数量达到百万级、且大量定时器集中在相近的到期时间时堆的常数开销与缓存不友好会成为瓶颈。时间轮把「时间」本身离散成槽位插入与删除接近 O(1)因此被网络库、操作系统内核广泛采用。「多级」是时间轮的关键。单级时间轮如果要有很长的覆盖范围槽位数量必须很大例如每秒一个槽、要覆盖一天就需要 86400 个槽。多级时间轮用「时、分、秒」式的分层低级轮转一圈就推动高级轮走一格用很少的槽位覆盖很长的时间范围。需要说明本文给出的是一个教学用的简化实现借鉴了 Linux 内核时间轮的分层思想但槽位数、层数、级联细节都做了简化不声称与任何内核版本一致。代码用 C11 编写不依赖平台 API。定时器的触发依赖外部周期调用wheel_tick本文不涉及真实时钟源。一、单级时间轮的局限单级时间轮是一个环形数组每个槽挂一条定时器链表。维护一个当前槽指针每过一个时间单位指针前进一格处理该槽里的定时器。设槽数为 N时间粒度为 1 秒则单级时间轮能表达的最大延迟是 N 秒。要支持 1 小时的延迟N 至少为 3600要支持 1 天N 为 86400。槽位越多内存占用越大而且大部分槽在任意时刻都是空的空间利用率低。多级时间轮用「进位」解决这个问题。以 3 位一级、共 4 级为例每级 8 个槽级别覆盖范围槽位含义08 个 tick每个 tick 一格164 个 tick每 8 个 tick 一格2512 个 tick每 64 个 tick 一格34096 个 tick每 512 个 tick 一格总共 32 个槽就能表达 4096 个 tick 的延迟。定时器按「延迟落在哪一级的范围」放到对应层等到低级轮转一圈、把时间推进到那一格时再把高级的定时器「降级」重新挂到低级轮上这个过程叫级联cascade。二、放置规则设当前时间为now定时器到期时间为expires延迟delta expires - now。若delta 8放在第 0 层槽号为expires 7若delta 64放在第 1 层槽号为(expires 3) 7若delta 512放在第 2 层槽号为(expires 6) 7否则放在第 3 层槽号为(expires 9) 7。槽号用「到期时间的低位」而不是「延迟的低位」是因为这样同一槽内的定时器在时间轴上是连续的级联时只要把整槽取出重新分配即可。用位运算而不是除法是因为级数与位宽都是 2 的幂移位比除法便宜。第 3 层覆盖 4096 个 tick超过这个范围的定时器要么被拒绝要么被截断到最大范围会延迟触发。工程实现里通常还会在最外层加一个「溢出链表」本文从简选择拒绝。三、完整实现// 适用于 C11#include stddef.h#include stdio.h#define WHEEL_BITS 3#define WHEEL_SIZE (1 WHEEL_BITS) /* 每级 8 个槽 */#define WHEEL_LEVELS 4#define WHEEL_RANGE (1UL (WHEEL_BITS * WHEEL_LEVELS)) /* 4096 */typedef struct timer {unsigned long expires; /* 绝对到期 tick */void (*fn)(void *arg);void *arg;struct timer *next; /* 同一槽内的链表指针 */} timer_t;typedef struct {timer_t *slots[WHEEL_LEVELS][WHEEL_SIZE];unsigned long current;} wheel_t;static void wheel_insert(wheel_t *w, timer_t *t, unsigned long now);static void wheel_init(wheel_t *w) {int level;int slot;for (level 0; level WHEEL_LEVELS; level) {for (slot 0; slot WHEEL_SIZE; slot) {w-slots[level][slot] NULL;}}w-current 0;}/* 把定时器挂到合适的层与槽 */static void wheel_insert(wheel_t *w, timer_t *t, unsigned long now) {unsigned long delta t-expires - now;int level 0;int shift;int slot;while (level WHEEL_LEVELS - 1 delta (1UL (WHEEL_BITS * (level 1)))) {level;}shift WHEEL_BITS * level;slot (int)((t-expires shift) (WHEEL_SIZE - 1));t-next w-slots[level][slot];w-slots[level][slot] t;}int wheel_add(wheel_t *w, timer_t *t, unsigned long delay) {if (delay WHEEL_RANGE) {return -1; /* 超出可表达范围 */}if (delay 0) {delay 1; /* 最早在下一个 tick 触发 */}t-expires w-current delay;wheel_insert(w, t, w-current);return 0;}/* 把某一层的某一槽整体取出重新分配到合适的层 */static void wheel_cascade(wheel_t *w, int level, int slot, unsigned long now) {timer_t *t w-slots[level][slot];w-slots[level][slot] NULL;while (t ! NULL) {timer_t *next t-next;wheel_insert(w, t, now);t next;}}/* 处理第 0 层的当前槽到期的执行未到期的重新挂 */static void wheel_fire(wheel_t *w, int slot, unsigned long now) {timer_t *t w-slots[0][slot];w-slots[0][slot] NULL;while (t ! NULL) {timer_t *next t-next;if (t-expires now) {t-fn(t-arg);} else {wheel_insert(w, t, now);}t next;}}void wheel_tick(wheel_t *w) {unsigned long now w-current;int idx0 (int)(now (WHEEL_SIZE - 1));/* 低级轮走完一圈先级联高级轮再从高到低降级 */if (idx0 0) {int idx1 (int)((now WHEEL_BITS) (WHEEL_SIZE - 1));if (idx1 0) {int idx2 (int)((now (2 * WHEEL_BITS)) (WHEEL_SIZE - 1));if (idx2 0) {int idx3 (int)((now (3 * WHEEL_BITS)) (WHEEL_SIZE - 1));wheel_cascade(w, 3, idx3, now);}wheel_cascade(w, 2, idx2, now);}wheel_cascade(w, 1, idx1, now);}wheel_fire(w, idx0, now);}逐段说明。timer_t是调用方分配的结构体时间轮只保存指针不负责malloc/free。这样插入与删除都不会触发堆分配适合在中断上下文或实时系统中使用。wheel_insert从第 0 层开始根据delta逐级判断是否超过当前层的覆盖范围。条件delta (1UL (WHEEL_BITS * (level 1)))表示「延迟已经装不进这一层」需要升到下一层。循环上限是WHEEL_LEVELS - 1保证不会越界。槽号取(expires shift) (WHEEL_SIZE - 1)。以第 1 层为例shift 3槽号是expires的第 3 到第 5 位第 2 层取第 6 到第 8 位。这与「每 8 个 tick 推进一格」的语义一致。wheel_add接收的是相对延迟内部转换成绝对时间expires。使用绝对时间的好处是级联时不需要修改定时器的字段重新插入时只需用expires - now重新计算层级。wheel_cascade先摘下整条链再逐个重新插入。重新插入时now是当前时间expires - now变小了定时器会落到更低的层。wheel_tick的顺序很关键先级联再处理第 0 层。原因在下一节展开。四、为什么必须先级联后触发假设当前now 8一个定时器的expires 8。它在插入时假设now 0delta 8被放到了第 1 层槽号(8 3) 7 1。到了now 8第 0 层走完一圈idx0 0第 1 层的idx1 1wheel_cascade(w, 1, 1, 8)把它取出。此时delta 0重新插入会落到第 0 层槽8 7 0。如果先执行wheel_fire(w, 0, 8)再级联这个定时器会在级联后才被放进第 0 层的槽 0而槽 0 刚刚处理过它要等到 8 个 tick 之后now 16才会被再次处理整整晚了一个轮转周期。同理级联必须从最高层开始逐级向下。考虑now 64第 1 层idx1 0、第 2 层idx2 1。如果先级联第 1 层再级联第 2 层那么第 2 层里expires 64的定时器会被降到第 1 层的槽 0而槽 0 刚刚级联过它要等到now 128才被处理晚了 64 个 tick。正确顺序是「第 3 层、第 2 层、第 1 层」代码里通过嵌套的if保证了这一点。wheel_fire里还有一个t-expires now的判断。理论上第 0 层当前槽里的定时器都应该到期但级联与重新插入可能带来边界情况加一层防御更稳妥。如果expires now就重新插入让它在正确的槽位等待。五、复杂度与工程注意插入的复杂度取决于层级判断最多WHEEL_LEVELS次比较可以视为 O(1)。触发一个槽时槽内链表长度决定了处理成本平均下来每个定时器只被处理常数次因此总成本是 O(1) 摊还。相比最小堆的 O(log n)时间轮在大规模定时器场景下更有优势。但时间轮也有代价。第一精度固定为一个 tick无法表达比 tick 更细的延迟。第二删除定时器不如堆方便时间轮通常不提供「按句柄删除」而是给定时器加一个cancelled标志触发时检查并跳过这叫惰性删除。第三回调函数执行期间如果有新定时器插入可能修改正在遍历的链表需要把「待触发的定时器」先摘成独立链表再逐个执行本文的wheel_fire已经先摘下整槽避免了这个问题的常见形态。如果要支持取消可以在timer_t里加int cancelled;在wheel_fire中判断或者额外维护一个哈希表从定时器地址映射到所在层与槽但删除时仍要遍历链表找前驱复杂度 O(槽内长度)。常见坑点坑点一先触发后级联导致定时器晚一个周期。// ❌ 错误先处理第 0 层再级联刚降级的定时器错过本轮wheel_fire(w, idx0, now);if (idx0 0) { wheel_cascade(w, 1, idx1, now); }// ✅ 正确先级联再触发if (idx0 0) { wheel_cascade(w, 1, idx1, now); }wheel_fire(w, idx0, now);坑点二级联顺序从低到高。// ❌ 错误先级联第 1 层第 2 层降下来的定时器错过本轮wheel_cascade(w, 1, idx1, now);wheel_cascade(w, 2, idx2, now);// ✅ 正确从最高层开始逐级向下wheel_cascade(w, 2, idx2, now);wheel_cascade(w, 1, idx1, now);坑点三槽号用延迟而不是绝对时间计算。// ❌ 错误级联后延迟改变槽号与原有位置不一致int slot (int)(delta (WHEEL_SIZE - 1));// ✅ 正确用绝对到期时间的低位int slot (int)((t-expires shift) (WHEEL_SIZE - 1));坑点四层级判断没有上限数组越界。// ❌ 错误delay 超过最大范围时 level 继续增加while (delta (1UL (WHEEL_BITS * (level 1)))) level;// ✅ 正确限制在最大层并在入口拒绝超范围延迟while (level WHEEL_LEVELS - 1 delta (1UL (WHEEL_BITS * (level 1)))) level;坑点五在遍历槽内链表时直接插入新定时器。// ❌ 错误回调里添加定时器可能修改当前链表遍历指针失效while (t ! NULL) { t-fn(t-arg); t t-next; }// ✅ 正确先摘下整槽再逐个处理timer_t *list w-slots[0][slot];w-slots[0][slot] NULL;while (list ! NULL) { timer_t *next list-next; /* ... */ list next; }坑点六时间轮负责释放定时器内存。// ❌ 错误定时器可能是栈上对象或由调用方复用不能由时间轮 freefree(t);// ✅ 正确时间轮只保存指针生命周期由调用方管理坑点七用有符号数存 tick溢出后变成负数。// ❌ 错误有符号溢出是 UBint current 0;current;// ✅ 正确用无符号类型回绕行为有定义unsigned long current 0;坑点八忘记处理delay 0。// ❌ 错误delay 为 0 时 expires 等于 current该槽本轮已处理过要等下一圈t-expires w-current delay;// ✅ 正确把 0 延迟提升为 1保证下一个 tick 触发if (delay 0) delay 1;t-expires w-current delay;总结要点说明结构每级 N 个槽槽内链表低级轮转推动高级轮放置按延迟选层级按绝对到期时间的低位选槽号级联低级走完一圈从最高层向最低层逐级降级顺序必须先级联后触发否则晚一个轮转周期复杂度插入 O(1)触发摊还 O(1)边界延迟上限、零延迟、回调中的并发修改多级时间轮的精髓不在代码量而在「用空间换时间」的分层思想把长延迟拆成「高位」与「低位」低位用密集的槽快速推进高位只在进位时处理。写实现时盯住三点——按绝对时间选槽、从高到低级联、先级联后触发——定时器就不会出现「晚一拍」或「永不触发」的问题。

利用C语言实现经典多级时间轮定时器

相关推荐

WSL常用命令全解析：配置、迁移、网络与性能排错

人工智能导论五条主线：从符号推理到博弈对抗的复习地图

大理州区县行政区划shp文件：GIS矢量底图使用与避坑指南

更多资讯

Java开发者转型大模型的优势与实践路线

Pixverse视频生成API成本优化方案与中文场景实践

K8s控制器实战：ReplicaSet副本控制与Deployment滚动更新

STM32F407+LWIP+DP83848以太网移植与排障指南

Transformer核心逻辑与魔改实践：注意力、残差与位置编码的细节

信息学奥赛排名题解析：Dense Rank与Ordinal Rank双解法

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？