调度器

XWOS的调度器
Categories:

  3 分钟阅读  

概述

  • XWOS调度器最基本的调度单位是 线程 ，暂时不支持 MMU虚拟内存 与 进程 ；
  • 每个 线程 都有自己独立的 栈 内存，但所有内存对所有线程都可见，除非使用MPU增加限制；
  • 每个 线程 都有调度优先级；
  • 调度器可以冻结线程，支持电源管理；
  • 每个CPU都有自己独立的调度器，线程只能在自身CPU的调度器中调度，如果需要在CPU间移动，需要进行 迁移 操作；

优先级

XWOS的优先级，用类型 xwpr_t 表示：

调度算法

数据类型

  • 每个优先级都有一个先进先出(FIFO)的 就绪 队列；
  • 使用一个位图标记每个优先级队列是否为空；非空的队列对应的位被置1，否则被清0。

XWOS调度器就绪队列
Photo: xwos.tech / CC-BY-SA-4.0

调度流程

  • 定义操作fls：从最高位起查找第一个被置1的位，并返回其序号， 如果所有位都为0，返回-1。此操作需要CPU的相关指令来实现，例如ARM的clz， DEC Alpha的ctlz，x86的lzcnt，PowerPC的cntlz等。

  • 流程图

flowchart TB
    start --> fls
    fls --> idx
    idx --否--> idle
    idx --是--> q
    q --> t
    t --> skd
    skd --> e
    idle --> e

    start("开始")
    fls["idx = fls(bitmap)"]
    idx{"idx >= 0 ?"}
    idle["调度空闲任务"]
    q["选择优先级为idx的就绪队列"]
    t["从就绪队列头部选择第一个线程"]
    skd["调度选择的线程"]
    e("结束")

启动调度器

当 启动流程 进入 xwos_main() 后，可调用 xwos_skd_start_lc() 启动调度器，此时上下文(Context)将由 启动 切换为 线程 。

抢占

调度器始终选择优先级最高的线程，高优先级的线程可以抢占低优先级的线程。

相同的优先级的线程，调度器按照 先进先出 的方法调度，同优先级线程之间 不能 相互抢占。

用户可以关闭抢占： xwos_skd_dspmpt_lc() ， 也可以打开抢占： xwos_skd_enpmpt_lc() 。

调度器中的特殊任务

空闲任务

  • 当调度器中没有任何线程就绪，调度器会调度空闲任务；
  • 空闲任务比较特殊，属于 最低优先级 的线程上下文，但不能使用任何会导致睡眠与阻塞的函数。
  • 用户可在空闲任务中HOOK用户代码，方法：
    • 在配置文件 xwbd/电路板/cfg/board.h 中定义配置 BRDCFG_XWSKD_IDLE_HOOK 为 1 ；
    • 定义函数 board_xwskd_idle_hook() 并在其中增加用户代码。

中断底半部任务

  • 当调度器配置 XWOSCFG_SD_BH 为 1 时， 调度器会为系统预留一个 最高优先级 线程；
  • 中断底半部任务比较特殊，属于线程上下文，但不能使用任何会导致睡眠、阻塞的函数；
  • 中断底半部任务可抢占任何线程；
  • 当开启中断底半部时，调度器的滴答定时器任务运行在中断底半部中；
  • XWOS的中断底半部并未完全开发完成，目前只开放给滴答定时器任务使用。

用户可以关闭中断底半部： xwos_skd_dsbh_lc() ， 也可以打开中断底半部： xwos_skd_enbh_lc() 。

滴答定时器任务

  • 操作系统内核通常都会包含一个定时器，用于产生固定周期的 滴答 （或称为 节拍 ）中断；
  • 滴答定时器任务也即是在此定时器中断中执行的周期性任务；
  • 如果 中断底半部任务 配置为 1 ，滴答定时器任务运行在中断底半部任务内部；
  • 如果 中断底半部任务 配置为 0 ，滴答定时器任务运行在中断上下文中；
  • 用户可以在滴答定时器任务中HOOK自己的代码，方法：
    • 在配置文件 电路板目录/cfg/board.h 中定义配置 BRDCFG_XWSKD_SYSHWT_HOOK 为 1 ；
    • 定义函数 board_xwskd_syshwt_hook() 并在其中增加用户代码。

调度器的中断

切换上下文的中断

  • 调度器用于切换正在执行的线程的中断
  • 中断优先级： 最低
  • 用户可在切换上下文时，Hook自己的代码：
    • 在切换上下文开始之前：
      • 在配置文件 电路板目录/cfg/board.h 中定义配置 BRDCFG_XWSKD_PRE_SWCX_HOOK 为 1 ；
      • 定义Hook函数 board_thd_preinit_hook() 。
    • 在切换上下文开始之后：
      • 在配置文件 电路板目录/cfg/board.h 中定义配置 BRDCFG_XWSKD_POST_SWCX_HOOK 为 1 ；
      • 定义Hook函数 board_thd_postinit_hook() 。

滴答定时器的中断

  • 用于产生固定周期的 滴答 （或称为 节拍 ）的定时器中断，滴答定时器任务由此中断触发执行。
  • 中断优先级： 切换上下文的中断 <= 滴答定时器的中断 <= 调度器服务中断

调度器服务中断

  • 用于执行调度器特殊操作的软中断，包括：
    • 调度器休眠 xwosplcb_skd_suspend_lic()
    • 线程退出 xwosplcb_thd_exit_lic()
    • 线程冻结 xwosplcb_thd_freeze_lic()
    • 线程迁移 xwosplcb_thd_immigrate_lic() 和 xwosplcb_thd_outmigrate_lic()
  • 中断优先级：切换上下文的中断 <= 滴答定时器的中断 <= 调度器服务中断

硬件定时器

  • XWOS内核要求每个CPU都有一个私有的滴答定时器，产生固定频率的中断；
  • 通常配置为 1000HZ ，可参考配置文件 xwbd/电路板/cfg/xwos.h 中的配置 XWOSCFG_SYSHWT_PERIOD ；
  • XWOS的滴答定时器会产生三个变量：
    • tickcount 滴答计数
      • 在每次滴答定时器中断时，tickcount 都会自增1；
      • tickcount 可以表示滴答定时器中断了多少次；
      • tickcount 是一个每CPU变量，代码运行在哪个CPU上，访问的就是哪个CPU的 tickcount ；
      • 通过CAPI xwtm_nowtc() 可以获取当前CPU的 tickcount 。
    • timetick 系统时间
      • XWOS内核使用 纳秒(ns) 作为时间的基本单位，假设滴答器频率 1000HZ ， tickcount 每1ms增加一次，即每1ms增加 1000000 ；
      • timetick 与 tickcount 的关系： timetick = tickcount * 1000000 ；
      • timetick 是一个每CPU变量，代码运行在哪个CPU上，访问的就是哪个CPU的 timetick ；
      • 通过CAPI xwtm_now() 可以获取当前CPU的 timetick 。
      • timestamp 系统时间戳
      • timestamp 是以纳秒为单位的系统时间戳；
      • timestamp 是通过把滴答定时器到下一次中断还剩多少时间计算出来，再累加到 timetick 上获取的，其精度由SOC的主频与计数器的位宽决定；
      • timestamp 是一个每CPU变量，代码运行在哪个CPU上，访问的就是哪个CPU的 timestamp ；
      • 通过CAPI xwtm_nowts() 可以获取当前CPU的 timestamp 。

超时管理

时间树

XWOS内核中，每个需要超时管理的对象（线程、软件定时器）都是以 时间树节点 组织到时间树中。 时间树节点 中包含了超时的 系统时间点 ，调度器每次进入滴答定时器任务时，都会检测时间树中是否有节点超时。 在时间树中，所有节点的 系统时间点 都是未来的时间。最先超时的节点一定是 系统时间点 最小的节点。 因此时间树的超时问题就是寻找最小值的问题。XWOS使用红黑树解决此最小值的问题，因此算法被称为 时间树 。

  • 使用一个 leftmost 指针指向最小值，超时可直接从 leftmost 快速获取最小值，时间复杂度为 O(1) ；
  • 超时后， leftmost 从红黑树中被删除，按照二叉树的性质，下一任 leftmost 是前任的右孩子（即后继）。 如果前任的后继为叶子，下一任 leftmost 一定是前任的父节点，算法时间复杂度为 O(1) ；
  • 删除 leftmost 在系统中是一个高频次的操作，但由于 leftmost 缺少左子树，根据红黑树性质，右子树也不可能太复杂， 意味着删除 leftmost 后，调整红黑树的代价不会太大；
  • 插入操作需要遍历树，时间复杂度为 O(logn) ；
  • 红黑树中不允许存在关键字相同的节点，因此拥有相同 系统时间点 的节点组成链表，超时后它们全部被唤醒。

XWOS时间树
Photo: xwos.tech / CC-BY-SA-4.0

超时函数的统一形式

XWOS所有带超时管理的CAPI函数，都是以后缀 _to 结尾，超时的参数都为 xwtm_t to ：

/* 睡眠 */
xwer_t xwos_cthd_sleep_to(xwtm_t to);

/* 等待信号量 */
xwer_t xwos_sem_wait_to(struct xwos_sem * sem, xwtm_t to);

/* 等待条件量 */
xwer_t xwos_cond_wait_to(struct xwos_cond * cond,
                         union xwlk_ulock lock, xwsq_t lktype,
                         void * lkdata, xwtm_t to, xwsq_t * lkst);

/* 等待互斥锁 */
xwer_t xwos_mtx_lock_to(struct xwos_mtx * mtx, xwtm_t to);


/* 等待信号旗 */
xwer_t xwos_flg_wait_to(struct xwos_flg * flg, xwsq_t trigger, xwsq_t action,
                        xwbmp_t origin[], xwbmp_t msk[],
                        xwtm_t to);

/* 等待信号选择器 */
xwer_t xwos_sel_select_to(struct xwos_sel * sel, xwbmp_t msk[], xwbmp_t trg[], xwtm_t to);

/* 等待线程同步 */
xwer_t xwos_br_wait_to(struct xwos_br * br, xwsq_t pos, xwbmp_t sync[], xwtm_t to);

参数 to 表明线程期望在未来的某个时间点被唤醒。

当用户实现了一个具有超时功能的接口，写接口时发现其中需要调用多个具有超时功能的CAPI， 更糟糕的是这些CAPI内部可能又调用了其他具有超时功能的CAPI。

计算每个CAPI花费了多少时间，然后将他们从超时时间中减去，显然很难实现。 最简单的方式就是只看结果，即 只关注未来什么时间点要唤醒 。 将这个 未来时间点 在内部CAPI中传递，无论这些带有超时功能的CAPI调用多少层，只要发生超时就唤醒。

例如：

xwer_t my_api(..., xwtm_t to)
{
        xwer_t rc;

        ...省略...
        rc = xwos_mtx_lock_to(mtx, to);
        ...省略...
        rc = xwos_sem_wait_to(sem, to);
        ...省略...
        return rc;
}

无论 xwos_mtx_lock_to() 等待了多少时间，也不会影响 xwos_sem_wait_to() 在 to 这个时间点唤醒。 当 xwos_mtx_lock_to() 把时间用尽， to 就变成 过去的时间点 ， xwos_sem_wait_to() 会立即返回 -ETIMEDOUT 。

获取上下文

XWOS提供CAPI xwos_skd_get_context_lc() 可以获取上下文：

  • XWOS_SKD_CONTEXT_INIT_EXIT ：初始化与反初始化
  • XWOS_SKD_CONTEXT_THD ：线程
  • XWOS_SKD_CONTEXT_ISR ：中断
  • XWOS_SKD_CONTEXT_BH ：中断底半部
  • XWOS_SKD_CONTEXT_IDLE ：空闲任务

暂停和继续调度器

  • xwos_skd_pause_lc() ：暂停本地CPU调度器

    • 暂停调度器包括几个操作：
        1. 关闭本地CPU调度器的抢占；
        1. 关闭本地CPU调度器的中断底半部；
        1. 关闭本地CPU的系统定时器。

  • xwos_skd_continue_lc() ：继续运行本地CPU调度器

    • 继续运行调度器包括几个操作：
        1. 启动本地CPU的系统定时器；
        1. 打开本地CPU调度器的中断底半部；
        1. 打开本地CPU调度器的抢占。

CAPI参考

最后修改 July 15, 2024: chore: :tade: 创建玄武操作系统网站 (3cdce99)