3.5.4 k_tickq_init 函数详解

学习阁2026/4/29大约 7 分钟启动流程初始化滴答队列延时超时

3.5.4 k_tickq_init 函数详解

📚 本节导读

学习时长: 约 20 分钟

难度级别: ⭐⭐⭐☆☆（进阶级）

前置知识:

3.5.3 _k_show_sys_info 函数详解
双向链表基本概念
哈希表基本概念

🎯 学习目标

理解滴答队列（Tick Queue）的设计目的
掌握哈希桶 + 增量排序的数据结构
理解 k_tickq_init 的初始化过程
了解滴答队列在任务延时和超时中的应用

一、函数概述

1.1 函数定位

k_tickq_init 是 os_kernel_init() 中执行的第 3 步，负责初始化滴答队列（Tick Queue）——这是管理系统延时和超时的核心数据结构。

1.2 基本信息

属性	值
函数名	`k_tickq_init`
源文件	`kernel/source/os_clock.c`（第 48-58 行）
调用位置	`os_kernel_init()` 第 264 行
全局变量	`gs_os_tickq_bucket[8]`、`gs_os_tick`

1.3 什么是滴答队列？

滴答队列是 OneOS 中管理所有需要延时等待的任务的数据结构。当任务调用 os_task_tsleep()、os_task_msleep() 或带超时的阻塞操作（如 os_sem_wait(100)）时，该任务会被放入滴答队列。每个系统节拍（SysTick）到来时，内核检查滴答队列，唤醒超时到期的任务。

二、函数详解

2.1 完整代码

来源: kernel/source/os_clock.c（第 48-58 行）

#define TICK_Q_BUCKETS 8
static os_list_node_t gs_os_tickq_bucket[TICK_Q_BUCKETS];
static os_tick_t      gs_os_tick = 0;

void k_tickq_init(void)
{
    os_size_t i;

    for (i = 0; i < TICK_Q_BUCKETS; i++)
    {
        os_list_init(&gs_os_tickq_bucket[i]);
    }

    return;
}

2.2 分步详解

第一步：全局变量定义

#define TICK_Q_BUCKETS 8
static os_list_node_t gs_os_tickq_bucket[TICK_Q_BUCKETS];
static os_tick_t      gs_os_tick = 0;

变量	类型	说明
`TICK_Q_BUCKETS`	宏（值为 8）	哈希桶数量，必须为 2 的幂
`gs_os_tickq_bucket`	`os_list_node_t[8]`	8 个双向链表头节点，每个桶是一个链表
`gs_os_tick`	`os_tick_t`	系统节拍计数器，从 0 开始递增

第二步：初始化 8 个哈希桶

for (i = 0; i < TICK_Q_BUCKETS; i++)
{
    os_list_init(&gs_os_tickq_bucket[i]);
}

os_list_init 将每个链表头节点的 next 和 prev 都指向自身，表示空链表：

// kernel/include/os_list.h 第 57-60 行
OS_INLINE void os_list_init(os_list_node_t *node)
{
    node->next = node;
    node->prev = node;
}

初始化后的内存布局：

gs_os_tickq_bucket[0]  ←→ 自身（空链表）
gs_os_tickq_bucket[1]  ←→ 自身（空链表）
gs_os_tickq_bucket[2]  ←→ 自身（空链表）
gs_os_tickq_bucket[3]  ←→ 自身（空链表）
gs_os_tickq_bucket[4]  ←→ 自身（空链表）
gs_os_tickq_bucket[5]  ←→ 自身（空链表）
gs_os_tickq_bucket[6]  ←→ 自身（空链表）
gs_os_tickq_bucket[7]  ←→ 自身（空链表）

三、数据结构设计

3.1 哈希桶设计

滴答队列采用哈希桶 + 增量排序（Delta Sort）的双重优化策略。

3.1.1 哈希桶映射

bidx = task->tick_absolute & (TICK_Q_BUCKETS - 1U);  // 即 & 0x7

任务根据其绝对到期时刻的低 3 位映射到对应桶：

tick_absolute 低 3 位	映射桶
0b000 (0)	bucket[0]
0b001 (1)	bucket[1]
0b010 (2)	bucket[2]
0b011 (3)	bucket[3]
0b100 (4)	bucket[4]
0b101 (5)	bucket[5]
0b110 (6)	bucket[6]
0b111 (7)	bucket[7]

3.1.2 为什么是 8 个桶？

TICK_Q_BUCKETS = 8（2³），掩码操作用 & 0x7 代替 % 8，效率更高
每个节拍只需要检查 1 个桶（当前 gs_os_tick 对应的桶），而不是全部 8 个
8 个桶在分散性和查找开销之间取得平衡

3.1.3 增量排序（Delta Sort）

每个桶内的任务按剩余等待时间从小到大排序，而非按绝对时间。插入时：

// os_clock.c 第 69 行
if (task->tick_timeout < (task_iter->tick_absolute - gs_os_tick))

排序方式	插入复杂度	优势
绝对时间排序	O(n)	每次 tick 需更新所有节点
增量排序	O(n)	只比较一次，无需更新

因为 gs_os_tick 单调递增，所有任务的剩余时间等比例减少，相对顺序不变，无需每次 tick 重新排序。

3.2 任务结构体中的相关字段

定义位置: kernel/source/os_prototypes.h 第 70-72 行

os_list_node_t tick_node;     /* Node in tick queue */
os_tick_t      tick_timeout;  /* Timeout */
os_tick_t      tick_absolute; /* Absolute time of timeout */

字段	说明
`tick_node`	双向链表节点，用于挂入滴答队列
`tick_timeout`	延时/超时长度（相对值，单位：tick）
`tick_absolute`	到期时刻（绝对值）= `gs_os_tick + tick_timeout`

3.3 数据结构图示

gs_os_tick = 1000

bucket[0] → [Task A: timeout=5, absolute=1000] → [Task B: timeout=13, absolute=1008]
bucket[1] → [Task C: timeout=3, absolute=1001]
bucket[2] → (空)
bucket[3] → (空)
bucket[4] → (空)
bucket[5] → [Task D: timeout=50, absolute=1045]
bucket[6] → (空)
bucket[7] → [Task E: timeout=10, absolute=1007]

当前 tick=1000，检查 bucket[0]（1000 & 0x7 = 0）
  → Task A 到期（absolute=1000），唤醒
  → Task B 未到期（absolute=1008 > 1000），停止遍历

四、完整工作流程

4.1 任务进入滴答队列

当任务调用 os_task_tsleep(50) 延时 50 个 tick 时：

os_task_tsleep(50)
    ↓
k_tickq_put(current_task, 50)
    ↓
task->tick_timeout  = 50
task->tick_absolute = gs_os_tick + 50       // 计算绝对到期时刻
    ↓
bidx = task->tick_absolute & 0x7            // 选择桶
    ↓
_k_tickq_delta_insert(bucket[bidx], task)   // 按剩余时间插入

源码（os_clock.c 第 95-108 行）：

void k_tickq_put(struct os_task *task, os_tick_t timeout)
{
    os_list_node_t *tickq_head;
    os_ubase_t      bidx;

    task->tick_timeout  = timeout;
    task->tick_absolute = gs_os_tick + timeout;

    bidx       = task->tick_absolute & (TICK_Q_BUCKETS - 1U);
    tickq_head = &gs_os_tickq_bucket[bidx];

    _k_tickq_delta_insert(tickq_head, task);
}

4.2 节拍中断处理（os_tick_increase）

每个 SysTick 中断调用 os_tick_increase()，核心流程：

os_tick_increase()
    ↓
gs_os_tick++                                // 节拍计数器 +1
    ↓
bidx = gs_os_tick & 0x7                     // 确定当前桶
    ↓
遍历 bucket[bidx]，找到所有到期的任务
    ↓
k_tickq_remove(task)                        // 从滴答队列移除
task->state &= ~OS_TASK_STATE_SLEEP       // 清除睡眠状态
    ↓
k_readyq_put(task)                          // 放入就绪队列
    ↓
触发调度

源码（os_clock.c 第 136-282 行，核心部分）：

void os_tick_increase(void)
{
    // ...
    gs_os_tick++;

    bidx       = gs_os_tick & (TICK_Q_BUCKETS - 1U);
    tickq_head = &gs_os_tickq_bucket[bidx];

    while (1)
    {
        if (os_list_empty(tickq_head))
            break;

        iter_task = os_list_first_entry(tickq_head, os_task_t, tick_node);

        if ((os_base_t)(iter_task->tick_absolute - gs_os_tick) > 0)
            break;  // 增量排序：第一个未到期，后面的都不会到期

        k_tickq_remove(iter_task);
        iter_task->state &= ~OS_TASK_STATE_SLEEP;
        // ... 唤醒任务 ...
    }
}

4.3 任务离开滴答队列

有两种离开方式：

方式	触发条件	函数
超时到期	tick 到达 `tick_absolute`	`os_tick_increase()` 中自动移除
提前唤醒	阻塞的资源可用（如信号量被释放）	`k_tickq_remove()` 主动移除

提前唤醒的源码（os_clock.c 第 120-125 行）：

void k_tickq_remove(struct os_task *task)
{
    os_list_del(&task->tick_node);
}

4.4 使用滴答队列的场景

场景	API	说明
任务延时	`os_task_tsleep(tick)`	当前任务延时指定 tick 数
毫秒延时	`os_task_msleep(ms)`	内部调用 `os_task_tsleep`
信号量等待	`os_sem_wait(sem, timeout)`	带超时的信号量等待
互斥锁等待	`os_mutex_lock(mutex, timeout)`	带超时的互斥锁获取
消息队列接收	`os_mq_recv(mq, buf, size, timeout)`	带超时的消息接收
事件等待	`os_event_recv(ev, set, opt, timeout)`	带超时的事件接收

所有这些带超时的操作，最终都通过 os_block.c 中的 k_tickq_put() 将任务放入滴答队列。

五、在启动流程中的位置

5.1 执行顺序

os_kernel_init()                               ← 3.5
    ↓
_k_run_init_call(OS_INIT_LEVEL_PRE_KERNEL_1)   ← 3.5.2
    ↓
_k_show_sys_info()                             ← 3.5.3
    ↓
k_tickq_init()                                 ← 这里（3.5.4）
    ↓
k_sched_init()                                 ← 调度器初始化
    ↓
...

5.2 为什么放在调度器之前？

滴答队列是调度器的基础组件：任务延时后需要从滴答队列中被唤醒，再放入就绪队列
调度器初始化（k_sched_init）只负责就绪队列和调度策略，不涉及延时管理
如果滴答队列未初始化，os_task_tsleep 等 API 将无法正常工作
因此滴答队列必须在调度器之前初始化

5.3 与调度器的关系

SysTick 中断
    ↓
os_tick_increase()          ← 处理滴答队列，唤醒到期任务
    ↓
k_readyq_put(task)          ← 将唤醒的任务放入就绪队列
    ↓
OS_KERNEL_EXIT_SCHED()      ← 触发调度器
    ↓
k_sched()                   ← 调度器选择最高优先级任务运行

💡 本节总结

重点回顾

函数作用：初始化 8 个哈希桶，为滴答队列管理做准备
数据结构：哈希桶 + 增量排序（Delta Sort），每个桶是一个双向链表
哈希映射：tick_absolute & 0x7 映射到 8 个桶
增量排序：桶内按剩余等待时间排序，避免每次 tick 重新排序
核心流程：SysTick → os_tick_increase → 检查当前桶 → 唤醒到期任务 → 触发调度

关键符号说明

符号	来源	说明
`TICK_Q_BUCKETS`	`os_clock.c`	哈希桶数量，值为 8
`gs_os_tickq_bucket`	`os_clock.c`	8 个桶的链表头数组
`gs_os_tick`	`os_clock.c`	系统节拍计数器
`OS_TICK_PER_SECOND`	`oneos_config.h`	每秒节拍数，STM32F103 为 100

📚 扩展阅读

下一步

接下来请学习：

3.5.5 k_sched_init 函数详解 - 调度器初始化