按到期顺序维护虚拟设备定时器
QEMU 的 QEMUTimerList 用有序单链表维护定时器，链表头就是下一到期项。
相关概念
工程问题#
设备模型与主循环需要在不同 QEMU 时钟上登记回调；定时器更新可能改变最早到期时刻。
实际实现#
timer_mod_ns_locked 从头扫描 expire_time，找到插入位置。若头部改变则请求重新安排唤醒；执行时依次移除到期项。
处理流程#
- 选择对应时钟的定时器列表
- 修改前先移除已有节点
- 扫描并插入新的有序位置
- 从链表头取出到期回调
源码片段#
固定版本 · 原文摘录util/qemu-timer.cv9.2.0 · L389–L408
389static bool timer_mod_ns_locked(QEMUTimerList *timer_list,390 QEMUTimer *ts, int64_t expire_time)391{392 QEMUTimer **pt, *t;393394 /* add the timer in the sorted list */395 pt = &timer_list->active_timers;396 for (;;) {397 t = *pt;398 if (!timer_expired_ns(t, expire_time)) {399 break;400 }401 pt = &t->next;402 }403 ts->expire_time = MAX(expire_time, 0);404 ts->next = *pt;405 qatomic_set(pt, ts);406407 return pt == &timer_list->active_timers;408}timer_mod_ns_locked
pt 是指向链表链接位置的指针，循环沿 next 找到合适的到期位置，再把定时器接入。返回值表示是否成为新表头，供调用者决定重新安排唤醒。函数要求调用路径持有锁；单次插入最坏需要扫描整个列表。
CMIT
收益与取舍#
工程分析带来的收益
- 头部查询与到期出队直接
- 节点结构和顺序关系容易维护
付出的代价
- 工程分析：插入与取消可能扫描整个列表
- 列表规模增大时，更新成本可能明显上升
可比较的选择
红黑树或带位置索引的堆可降低大规模更新的渐进成本，但需要更多维护逻辑。
Linux 普通时间轮大量允许较粗时间粒度的普通超时可按槽组织，固定层数下挂入不用扫描全部定时器；时间精度与 QEMU 有序链表不同，不能直接替换其时钟语义。
版本与适用范围#
对应 QEMU v9.2.0 QEMUTimerList；源码事实能说明实现，不能单凭代码断言维护者选择链表的动机。
参考来源#
源码、官方文档与原始论文01
qemu · timer_mod_ns_locked / timer_del_locked / timerlist_run_timers
源码v9.2.0util/qemu-timer.c · timer_mod_ns_locked / timer_del_locked / timerlist_run_timers
相关实现与比较#
4 个相关案例hrtimer 通过 timerqueue 的红黑树维护到期顺序，并缓存最早到期节点。
附源码片段 · 调度与资源分配
Linux 普通定时器把较近超时放进细粒度槽，远期超时放进粗粒度槽，使用位图寻找待处理槽。v6.12 的这套时间轮不再逐层级联迁移。
附源码片段 · 调度与资源分配
nginx 事件定时器以到期时间为键放入红黑树，事件循环读取最小键确定等待上限。
附源码片段 · 调度与资源分配
伙伴分配器把空闲物理页组织为不同 order 的连续块，并用空闲链表管理同阶块。
附源码片段 · 内存管理