evil0knight's Blog

链表和调度

7分钟阅读

链表和调度

← 任务(线程)的定义 | ← FreeRTOS内核实现与应用开发实战指南

任务的插入

双向链表,就绪任务按优先级挂到就绪链表 pxReadyTasksLists[] 上，调度器从链表里挑最高优先级任务运行(调度看下面的)

就绪链表 List_t
  └─ xListEnd（哨兵） ⇄ xStateListItem（任务A）
                       ⇄ xStateListItem（任务B）
                              │ pvOwner 指向
                              ▼
                          TCB（任务B）
                              ├─ pxTopOfStack → 栈顶（保存的 16 个寄存器现场）
                              └─ pxStack      → 栈底（任务栈起始地址）
  • pvOwner 是从链表节点找回 TCB 的桥梁：链表里存的是 xStateListItem 节点，调度器通过 pvOwner 拿到任务本体，再取 pxTopOfStack 恢复现场。
  • 一个任务有两个链表项：xStateListItem 管「就绪/阻塞」状态，xEventListItem 管「等队列/信号量」事件，让任务能同时挂在两个链表上。
  • pxTopOfStack（栈顶）和 pxStack（栈底）一高一低框出整个任务栈，切换任务时从 pxTopOfStack 恢复现场。

就绪任务的调度

任务切换在pendsv中断中

  1. 在 1.延时函数, 2.systick硬件中断, 3.while末尾 调用 taskYIELD()

  2. taskYIELD() :PendSV的悬起位置

    PendSV设置成最低优先级,因为不能打断其他的中断

  3. PendSV:调用 xPortPendSVHandler

  4. xPortPendSVHandler : 现在的任务即将结束,把cpu通用寄存器组和特殊寄存器的值进栈中(硬件自动+软件手动)

    调用 vTaskSwitchContext()，从就绪链表中遍历找出下一个最高优先级的任务，更新全局指针 pxCurrentTCB 指向新任务。

    pxReadyTasksLists[] 本质是链表头数组：configMAX_PRIORITIES（默认 32）个元素，每个元素是一个优先级链表的链表头，同优先级任务 FIFO 挂在同一链表上

    pxReadyTasksLists[31] → 优先级31链表头：哨兵 ⇄ ...
pxReadyTasksLists[30] → 优先级30链表头：（空）
          ⋮
pxReadyTasksLists[0]  → 优先级0链表头：哨兵 ⇄ 任务A ⇄ 任务B

    朴素查找（taskSELECT_HIGHEST_PRIORITY_TASK 默认实现）：从最高优先级向下逐个检查链表是否为空，找到第一个非空链表取任务——最坏情况遍历 32 个链表，O(32)

    位图加速：打开宏 configUSE_PORT_OPTIMISED_TASK_SELECTION（置 1）后，改用位图 O(1) 定位：

    • 全局位图 uxTopReadyPriority：bit n = 1 表示优先级 n 有就绪任务

      • 任务插入就绪链表 → 置位（portSET_READY_PRIORITY）
      • 该优先级最后一个任务移出 → 清位（portRESET_READY_PRIORITY）

    • 找最高优先级 = 找位图最高置位位，Cortex-M 用一条 __clz（数前导零）指令：

      uxTopPriority = 31U - __clz( uxTopReadyPriority );   // 一条指令搞定，O(1)

    通过 pxCurrentTCB获取栈顶指针,恢复通用寄存器组和特殊寄存器,更新到PSP实现无感切换

  5. FreeRTOS-Kernel port.c — xPortPendSVHandler 原码

  6. 同优先级任务的时间片轮转（每次 SysTick 轮询同优先级链表）见 时间片调度

信号任务的调度

信号任务的调度在信号量/队列的 API 中

  1. 在 1. 信号获取超时阻塞 （xQueueReceive / xSemaphoreTake）， 2. 信号发送唤醒等待任务 （xQueueSend / xSemaphoreGive / xTaskNotifyGive）， 3. 中断中发送信号 （xQueueSendFromISR / xSemaphoreGiveFromISR） 中处理信号等待与就绪链表

  2. 信号等待链表（xTasksWaitingToReceive / xTasksWaitingToSend） ： 每个队列/信号量内部自带两个事件链表，严格按照任务优先级从高到低排序（同优先级按 FIFO）。表头永远是等待该信号中优先级最高的任务

  3. 获取信号（Take / Receive 阻塞） ：

    • 检查资源计数值：若无资源且设置了超时时间，调用 vTaskPlaceOnEventList()
    • 将当前任务的 xEventListItem（事件节点）插入信号量的 xTasksWaitingToReceive（等待接收链表）
    • 同时将当前任务的 xStateListItem（状态节点）插入系统的 pxDelayedTaskList（延时链表，按超时时间戳排序），实现双重挂载
    • 任务移出就绪链表，在 API 末尾调用 portYIELD_WITHIN_API() 悬起 PendSV，主动让出 CPU 进入阻塞

  4. 释放/发送信号（Give / Send 唤醒） ：

    • 写入数据或增加计数值后，检查 xTasksWaitingToReceive 是否为空
    • 若有任务在等，调用 xTaskRemoveFromEventList()：直接从等待链表表头取出最高优先级的任务
    • 将该任务同时从信号等待链表和系统延时链表中拔除，调用 prvAddTaskToReadyList() 重新插入对应优先级的就绪链表
    • 比对优先级：若唤醒的任务优先级高于当前正在运行的任务，调用 queueYIELD_IF_USING_PREEMPTION() 悬起 PendSV 请求立即抢占

延时任务的调度

任务调用 vTaskDelay() 或等信号量/队列超时时，按唤醒时刻挂进延时链表，SysTick 到期后回就绪链表（信号量的唤醒路径见上面信号任务的调度，这里只讲延时这条路径）

挂入（阻塞时）：

  • xStateListItem 按唤醒时刻升序插入 pxDelayedTaskList（延时链表）——表头永远是最早到期的任务
  • 任务移出就绪链表，主动让出 CPU；等信号的任务还会双重挂载到信号等待链表

到期（SysTick 时）：

  1. xTaskIncrementTick()：xTickCount 加 1，达到 xNextTaskUnblockTime 时处理延时链表
  2. 从表头依次取出唤醒时刻 ≤ 当前 tick 的任务（按时间排序，取到超过当前时刻为止）
  3. 若任务还挂在信号等待链表上（没被 Give 抢走），一并从事件链表拔出
  4. prvAddTaskToReadyList() 重新插入对应优先级就绪链表
  5. 被唤醒任务优先级更高 → taskYIELD_IF_USING_PREEMPTION() 悬起 PendSV 抢占

tick 溢出轮换：xTickCount 是 32 位会回绕，系统用双链表：pxDelayedTaskList 与 pxOverflowDelayedTaskList（溢出链表），溢出时 prvSwitchTimerLists() 互换，保证唤醒时刻始终按当前时间排序

关系图谱

反向链接