4.5.2 哈希桶定时器

📚 本节导读

学习时长: 约 25 分钟
难度级别: ⭐⭐⭐☆☆
前置知识: 哈希表基础、系统时钟概念、双向链表

🎯 学习目标

• 理解哈希桶定时器的设计思想和 O(1) 插入原理
• 掌握哈希桶定时器的内部数据结构
• 理解哈希桶定时器的 tick 处理流程
• 明确哈希桶定时器的适用场景

一、哈希桶定时器概念

1.1 设计思想

哈希桶定时器（Hash Bucket Timer）是一种以空间换时间的设计。它将定时器按超时时间的哈希值分散到多个桶中，使得插入操作只需计算哈希值并放入对应桶，无需遍历所有定时器，从而实现 O(1) 时间复杂度的插入。

1.2 为什么需要哈希桶

传统的单链表定时器在插入时需要遍历链表找到合适位置，时间复杂度为 O(n)。当定时器数量较多时（如数百个），插入操作的开销会显著增加。哈希桶定时器通过将定时器分散存储，避免了遍历开销，特别适合定时器数量较多的场景。

二、内部数据结构

哈希桶定时器的核心数据结构定义在 kernel/source/ 下的定时器实现文件和 kernel/include/os_dummy.h 中：

/* 定时器控制块（通过 os_dummy.h 暴露） */
struct dummy_timer
{
    void (*timeout_func_dummy)(void *timeout_param); /* 超时回调函数 */
    void     *parameter_dummy;                       /* 回调函数的参数 */
    uint32_t  init_tick_dummy;                       /* 初始超时 tick 数 */
    uint32_t  timeout_tick_dummy;                    /* 当前超时 tick 数 */
#ifdef OS_USING_HASH_BUCKET_TIMER
    uint32_t  index_dummy;                           /* 定时器所在桶索引 */
#endif
    os_list_node_t            list_dummy;            /* 链表节点 */
    dummy_timer_active_node_t active_node_dummy;     /* 活跃节点 */
    char                      name_dummy[OS_NAME_MAX + 1]; /* 定时器名称 */
};

/* 活跃节点 */
struct dummy_timer_active_node
{
    os_list_node_t active_list_dummy; /* 环形双向链表节点 */
    os_tick_t      timeout_ticks;     /* 超时 tick 数 */
    uint8_t        flag_dummy;        /* 定时器标志 */
};

三、哈希桶工作原理

3.1 哈希桶结构

定时器列表（环形数组，每个位置是一个桶）
┌──────────────────────────────────────────────────────────┐
│  index 0  │  index 1  │  index 2  │ ... │  index N-1   │
│  ┌─┐┌─┐   │  ┌─┐      │  ┌─┐┌─┐┌─┐│     │  ┌─┐         │
│  │T1││T5│  │  │T3│     │  │T2││T6││T8││     │  │T4│        │
│  └─┘└─┘   │  └─┘      │  └─┘└─┘└─┘│     │  └─┘         │
└──────────────────────────────────────────────────────────┘
             ↑
    gs_os_timer_list_current（当前正在处理的桶）

• 定时器数组是一个环形缓冲区，每个位置对应一个"桶"
• 每个桶是一个双向链表，存储所有超时时间落在该桶的定时器
• 全局指针 gs_os_timer_list_current 指向当前正在处理的桶

3.2 插入操作（O(1)）

当创建并启动一个定时器时：

1. 计算目标桶索引：index = (current_index + timeout) % bucket_count
   • current_index 是当前指针位置
   • timeout 是定时器超时 tick 数
2. 插入定时器：将定时器节点直接插入目标桶的链表中，无需遍历
3. 时间复杂度：O(1)

3.3 Tick 处理

每次 tick 中断时，os_tick_increase() 调用哈希桶定时器的处理函数：

#ifdef OS_USING_HASH_BUCKET_TIMER
/* 检查是否有定时器需要处理 */
if (k_timer_need_handle())
{
    is_sched = OS_TRUE;
}
/* 将当前桶指针向前移动一步 */
k_move_timer_list_one_step();
#endif

核心函数（声明在 kernel/source/os_kernel_internal.h）：

void      k_timer_module_init(void);           /* 初始化哈希桶定时器模块 */
os_bool_t k_timer_need_handle(void);           /* 检查当前桶是否有到期定时器 */
void      k_move_timer_list_one_step(void);    /* 推进当前桶指针 */

#ifdef OS_HASH_BUCKET_TIMER_SORT
os_tick_t k_timer_get_next_remain_ticks(void); /* 获取下一个到期定时器的剩余 tick */
void      k_timer_update_active_list(os_tick_t ticks); /* 更新活跃列表（tickless 模式） */
#endif

处理流程：

每 tick 中断:
  1. k_timer_need_handle():
     └─ 检查 gs_os_timer_list_current 指向的桶
        └─ 如果桶中有定时器且已到期 → 执行回调，返回 OS_TRUE

  2. k_move_timer_list_one_step():
     └─ gs_os_timer_list_current = (current + 1) % bucket_count

四、哈希桶定时器的优势

优势	说明
O(1) 插入	插入定时器无需遍历，直接计算索引并放入对应桶
适合大量定时器	定时器数量多时，性能优势明显
确定性	插入时间恒定，不受现有定时器数量影响
内存开销可控	桶的数量固定，每个定时器只占用一个链表节点

五、配置与使用

5.1 配置选项

在 oneos_config.h 中启用哈希桶定时器：

#define OS_USING_KERNEL_TIMER     /* 必须启用内核定时器 */
#define OS_USING_HASH_TIMER       /* 启用哈希桶定时器 */

/* 可选：启用排序功能（低功耗 tickless 模式需要） */
#define OS_HASH_BUCKET_TIMER_SORT

5.2 使用限制

• 不支持硬件定时器：哈希桶定时器只有软件定时器，回调在定时器任务上下文中执行
• 不支持 OS_TIMER_FLAG_HARD_TIMER 和 OS_TIMER_FLAG_SOFT_TIMER 标志：这些标志仅在单链表定时器中有意义
• 低功耗模式需要排序：若使用 OS_USING_TICKLESS_LPMGR，必须同时启用 OS_HASH_BUCKET_TIMER_SORT

六、适用场景

哈希桶定时器适合以下场景：

• 系统中存在大量定时器（数十个甚至上百个）
• 定时器频繁创建和销毁，插入性能要求高
• 不需要硬件定时器（不需要在 ISR 中执行回调）
• 需要确定性的定时器插入时间

对于定时器数量较少（如 10 个以内）的场景，单链表定时器可能更合适，因为其实现更简单，内存开销更小。

📝 本节小结

哈希桶定时器是 OneOS 提供的高效定时器实现方案，通过将定时器按超时时间分散到多个桶中，实现了 O(1) 时间复杂度的插入操作。它特别适合定时器数量较多的场景，能够保证插入时间的确定性。每个 tick 中断只需处理当前桶中的定时器，处理效率高。但哈希桶定时器不支持硬件定时器，不适合需要在 ISR 中执行回调的场景。

🔗 相关链接

• 4.5.1 系统时钟
• 4.5.3 单链表定时器
• 4.5.4 定时器 API