systemd/.timer 单元与 sd-event 时间事件

在允许的时间误差内合并定时器唤醒

systemd 的 sd-event 为每个时钟维护两个带位置索引的小顶堆，快速找到下一次到期时间，并利用允许的延迟余量合并唤醒。

v257调度与资源分配核验 2026-10-12

工程问题#

多个 .timer 单元需要在不同时间启动任务。每项定时器允许的误差并不相同：最先到期的一项未必最先耗尽延迟余量。事件循环既要找到下一次唤醒的合适时刻，也要支持频繁修改、停用和释放定时器，避免逐项扫描所有事件源。

实际实现#

timer_enter_waiting 将到期时间和精度交给 sd_event_add_time。每个时钟各有 earliest、latest 两个小顶堆：对当前可调度的普通定时器，分别按 next 和 next + accuracy 排序。堆顶给出最早到期时刻 a 与最早耗尽延迟余量的时刻 b，sleep_between 在 [a, b] 内选择唤醒时刻，由该时钟的一个 timerfd 承载。事件源保存两个堆位置，堆交换同步回写索引；改期或启停时重新调整堆序，断开事件源时通过索引删除。

处理流程#

为 .timer 单元计算到期时间，并传入允许的时间误差
按时钟将事件源加入 earliest 与 latest 两个堆，记录各自下标
读取两个堆顶，在最早到期与最早耗尽延迟余量之间选择唤醒时刻
设置该时钟的 timerfd，唤醒后将已到期的事件源标记为待处理
修改时间或启停状态时重排；事件源断开时以末项补位并恢复堆序

源码片段#

固定版本 · 原文摘录

src/core/timer.cv257 · L526–L537

查看原文件

526                        r = sd_event_add_time(527                                        UNIT(t)->manager->event,528                                        &t->monotonic_event_source,529                                        t->wake_system ? CLOCK_BOOTTIME_ALARM : CLOCK_MONOTONIC,530                                        t->next_elapse_monotonic_or_boottime, t->accuracy_usec,531                                        timer_dispatch, t);532                        if (r < 0) {533                                log_unit_warning_errno(UNIT(t), r, "Failed to add monotonic event source: %m");534                                goto fail;535                        }536537                        (void) sd_event_source_set_description(t->monotonic_event_source, "timer-monotonic");

timer_enter_waiting

实际 .timer 单元把下一次到期时间及 AccuracySec 对应的精度传入 sd_event_add_time。普通单调定时使用 CLOCK_MONOTONIC；WakeSystem 选用 CLOCK_BOOTTIME_ALARM，并注册 timer_dispatch 回调。

CLGPL-2.1-or-later

src/libsystemd/sd-event/sd-event.cv257 · L1373–L1388

查看原文件

1373        assert(EVENT_SOURCE_USES_TIME_PRIOQ(s->type));13741375        r = prioq_put(d->earliest, s, &s->earliest_index);1376        if (r < 0)1377                return r;13781379        r = prioq_put(d->latest, s, &s->latest_index);1380        if (r < 0) {1381                assert_se(prioq_remove(d->earliest, s, &s->earliest_index) > 0);1382                s->earliest_index = PRIOQ_IDX_NULL;1383                return r;1384        }13851386        d->needs_rearm = true;1387        return 0;1388}

event_source_time_prioq_put

同一事件源进入 earliest 和 latest 两个堆，分别保存自己的下标。第二次插入失败时会撤销第一次插入，成功后标记该时钟需要重新设定唤醒时间。

CLGPL-2.1-or-later

src/libsystemd/sd-event/sd-event.cv257 · L3614–L3635

查看原文件

3614        b = prioq_peek(d->latest);3615        assert(!b || EVENT_SOURCE_USES_TIME_PRIOQ(b->type));3616        assert(b && b->enabled != SD_EVENT_OFF);36173618        t = sleep_between(e, time_event_source_next(a), time_event_source_latest(b));3619        if (d->next == t)3620                return 0;36213622        assert_se(d->fd >= 0);36233624        if (t == 0) {3625                /* We don't want to disarm here, just mean some time looooong ago. */3626                its.it_value.tv_sec = 0;3627                its.it_value.tv_nsec = 1;3628        } else3629                timespec_store(&its.it_value, t);36303631        if (timerfd_settime(d->fd, TFD_TIMER_ABSTIME, &its, NULL) < 0)3632                return -errno;36333634        d->next = t;3635        return 0;

event_arm_timer

a 已在本函数前文取自 earliest 堆顶，这里取 latest 堆顶 b；sleep_between 在两个端点之间选择唤醒时刻，然后以绝对时间设置该时钟的 timerfd。

CLGPL-2.1-or-later

src/basic/prioq.cv257 · L84–L101

查看原文件

84static unsigned shuffle_up(Prioq *q, unsigned idx) {85        assert(q);86        assert(idx < q->n_items);8788        while (idx > 0) {89                unsigned k;9091                k = (idx-1)/2;9293                if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)94                        break;9596                swap(q, idx, k);97                idx = k;98        }99100        return idx;101}

shuffle_up

数组位置 idx 的父节点位于 (idx - 1) / 2。新元素逐层与父节点比较并交换，直到恢复小顶堆次序，路径长度受完全二叉树高度约束。

CLGPL-2.1-or-later

src/basic/prioq.cv257 · L66–L82

查看原文件

66static void swap(Prioq *q, unsigned j, unsigned k) {67        assert(q);68        assert(j < q->n_items);69        assert(k < q->n_items);7071        assert(!q->items[j].idx || *(q->items[j].idx) == j);72        assert(!q->items[k].idx || *(q->items[k].idx) == k);7374        SWAP_TWO(q->items[j].data, q->items[k].data);75        SWAP_TWO(q->items[j].idx, q->items[k].idx);7677        if (q->items[j].idx)78                *q->items[j].idx = j;7980        if (q->items[k].idx)81                *q->items[k].idx = k;82}

swap

交换元素时连同下标指针一起交换，并把新的位置写回调用方保存的索引。即使堆调整改变了位置，事件源仍能直接找到自己。

CLGPL-2.1-or-later

src/basic/prioq.cv257 · L181–L202

查看原文件

181        l = q->items + q->n_items - 1;182183        if (i == l)184                /* Last entry, let's just remove it */185                q->n_items--;186        else {187                unsigned k;188189                /* Not last entry, let's replace the last entry with190                 * this one, and reshuffle */191192                k = i - q->items;193194                i->data = l->data;195                i->idx = l->idx;196                if (i->idx)197                        *i->idx = k;198                q->n_items--;199200                k = shuffle_down(q, k);201                shuffle_up(q, k);202        }

remove_item

删除末项只减少长度；删除中间项则用末项补位，更新被移动元素的下标，再下滤、上滤恢复堆序。待删除位置由 find_item 根据调用方下标定位。

CLGPL-2.1-or-later

六段源码从 .timer 注册贯穿双堆入队、timerfd 设置、二叉堆上滤、索引同步与删除。sd_event_source_set_enabled 将停用项调整到队列后部，真正断开事件源时才移除时间堆索引。完整源码中的 find_item、prioq_put 与 greedy_realloc 分别支撑下标查找、插入和容量增长的成本分析。

收益与取舍#

工程分析

带来的收益

两个堆顶都能 O(1) 读取，无需为计算下一次唤醒遍历全部时间事件；不同精度的定时器也能共同参与选择
允许延迟的事件可以共享一次唤醒，减少分散定时器造成的重复唤醒；收益取决于任务时间及其允许误差。
事件源保存堆下标，修改和删除无需先线性搜索对象；保留两个堆只增加常数倍的索引条目

付出的代价

以单个时钟堆的当前元素数 n 计，在常数成本比较的前提下，容量足够时插入、按下标删除和重排为 O(log n)；仅查看堆顶为 O(1)
Prioq 的数组按增长需求扩大容量。触发搬移的一次插入可能为 O(n)，连续插入的摊还成本为 O(log n)；未提供下标的通用 prioq_remove 需要先做 O(n) 查找
设两个堆保留的总容量为 C，堆数组占用 O(C) 空间；删除不会主动缩容，大量事件释放后不能仅按当前 n 估计已分配内存。
两个时间堆需要同时维护，精度余量也允许有意延迟；上述复杂度不包含其他待处理队列、系统调用、内存分配器阻塞或用户回调的耗时

可比较的选择

按到期时间维护有序链表取最早项简单，但插入通常要线性查找位置；如果精度各异，仍需另外维护最早的允许延迟上限。

时间轮适合大批量、粒度相对固定的定时任务，但需要选择时间槽与层级，并额外处理每项精度余量；不能直接等同于这里的精确端点比较。

版本与适用范围#

对应 systemd v257。本文以普通、启用且尚未 pending 的 .timer 时间事件解释两个端点；CLOCK_MONOTONIC、CLOCK_BOOTTIME、CLOCK_REALTIME 及两个 ALARM 时钟各自维护时间队列。限流恢复额外使用 CLOCK_MONOTONIC 队列，其两个端点相同。区间 [min(next), min(next + accuracy)] 表示下一次唤醒的选择范围，并非所有定时器允许区间的共同交集。accuracy=0 在 sd_event_add_time 中选择默认 250ms，不表示零误差；实际回调仍可能受内核及调度延迟影响，不能把它当作硬实时截止保证。