专栏首页TencentOS-tinyRTOS内功修炼记(二)—— 优先级抢占式调度到底是怎么回事?

RTOS内功修炼记(二)—— 优先级抢占式调度到底是怎么回事?

内容导读:

本文从任务如何切换开始讲起,引出RTOS内核中的就绪列表、优先级表,一层一层为你揭开RTOS内核优先级抢占式调度方法的神秘面纱,只有对内核的深入了解,才能创造出更好的应用。


1.知识点回顾

1.1. 上文回顾

上篇文章讲述了任务的三大元素:任务控制块、任务栈、任务入口函数,并讲述了编写RTOS任务入口函数时三个重要的注意点。

如果你还没有阅读上一篇文章,请先阅读,这有助于对本文的理解:

  • RTOS内功修炼记(一)—— 任务到底应该怎么写?

1.2. 双向循环链表

双向链表是链表的一种,区别在于每个节点除了后继指针外,还有一个前驱指针,双向链表的节点长下面这样:

如果你对双向循环列表的实现及使用还不熟悉,请一定要先阅读这篇文章:

2. 任务是如何切换的

在RTOS内核中,一个任务切换到下一个任务的原理是:

「手动触发PendSV异常,在PendSV异常服务函数中实现任务切换」

2.1. 如何触发PendSV异常

stm32中,将中断及状态控制寄存器ICSR(Interrupt control and state register)的第28位置1,即可手动触发 PendSV 异常,如图:

tos中触发异常的底层函数为port_context_switch,实现在 arch\arm\arm-v7m\cortex-m4\armcc\port_s.S 中,如下:

    GLOBAL port_context_switch
port_context_switch
    LDR     R0, =NVIC_INT_CTRL
    LDR     R1, =NVIC_PENDSVSET
    STR     R1, [R0]
    BX      LR

上面这段汇编猛一看有点难,再看看两个值具体是多少:

NVIC_INT_CTRL   EQU     0xE000ED04
NVIC_PENDSVSET  EQU     0x10000000

所以上面这段汇编代码,不正是完成了将寄存器 ICSR(代码中是NVIC_INT_CTRL) 的第28位置1的操作吗?

2.2. 异常服务中实现任务切换

在 stm32 中 PendSV 的异常服务函数名为 PendSV_Handler,默认在stm32l4xx_it.c中提供了一个弱定义,所以tos中的实现直接重定义此函数即可,源码在 arch\arm\arm-v7m\cortex-m4\armcc\port_s.S中,主要步骤有四个:

「关闭全局中断」(NMI 和 HardFault 除外),防止任务切换过程被中断:

CPSID   I

「保存上文环境」:保存当前CPU寄存器组的值、PSP栈顶指针的值到任务栈中;

「加载下文环境」:加载当前任务栈中的值到CPU寄存器组、PSP栈顶指针中;

「打开全局中断」,实时响应系统所有中断:

CPSIE   I

记住任务切换的这四个过程即可,深入研究每行汇编指令是什么意思,没有太大的作用和帮助。

2.3. CPU何时响应PendSV异常

我们都知道,「高优先级的中断会打断低优先级的中断」,这也是系统实时性的一个重要保障,所以就引入了一个问题:

相比起GPIO中断、定时器中断、串口中断这些外部中断,PendSV异常的优先级更高呢?还是更低呢?

想象这样一种情况:

① CPU正在开心的运行着任务1……

② 此时你按下了按键,产生了一个GPIO中断,CPU收到后马上跑去执行中断处理函数……

③ 处理过程中,此时系统产生了一个PendSV异常,CPU收到后,嘲讽了一句:“我就是从普通任务跑来处理中断的,还没处理完,现在又让我执行下一个普通任务,脑子抽风了?”,说完继续处理中断……

所以说,无论任务的优先级有多高,它都没有中断高,「系统的PendSV异常优先级必须设为最低的」,以避免在外部中断服务函数中产生任务切换。

设置PendSV异常优先级的寄存器如下,值可以为0-255:

tos中在启动调度时设定pendsv异常的优先级,源码如下:

NVIC_SYSPRI14   EQU     0xE000ED22
NVIC_PENDSV_PRI EQU     0xFF

同样,设置pendSV异常优先级为最低的汇编代码如下:

; set pendsv priority lowest
; otherwise trigger pendsv in port_irq_context_switch will cause a context switch in irq
; that would be a disaster
MOV32   R0, NVIC_SYSPRI14
MOV32   R1, NVIC_PENDSV_PRI
STRB    R1, [R0]

3. 就绪列表

3.1. 就绪列表长啥样

就绪列表其实就是好多条双向链表+一张优先级表,它的类型定义在tos_sched.h,如下:

typedef struct readyqueue_st
{
    k_list_t    task_list_head[TOS_CFG_TASK_PRIO_MAX];
    uint32_t    prio_mask[K_PRIO_TBL_SIZE];
    k_prio_t    highest_prio;
} readyqueue_t;

「给每个优先级都分配了一个双向链表的首节点,用于挂载该优先级的任务」

TOS_CFG_TASK_PRIO_MAX 是最大任务优先级,在tos_config.h中配置,默认是10:

#define TOS_CFG_TASK_PRIO_MAX           10u

节点类型 k_list_t 是一个双向链表节点类型:

typedef struct k_list_node_st
{
    struct k_list_node_st *next;
    struct k_list_node_st *prev;
} k_list_t;

所有双向链表节点初始化完毕之后,每一个双向结点的next指针指向自己(橙色线),prev指针也指向自己,如图:

「用于指示系统目前所使用优先级的优先级表」

优先级表的大小由宏定义 K_PRIO_TBL_SIZE 决定:

#define K_PRIO_TBL_SIZE         ((TOS_CFG_TASK_PRIO_MAX + 31) / 32)

这儿定义的时候比较讲究,如果最大优先级不大于32,则该宏的值为1,使用一个uint32_t类型的变量即可,每个优先级的表示占一位。

初始化后的优先级表长下面这个样子:

「最高优先级指示成员」

就绪列表中的 highest_prio 成员是 k_prio_t 类型,其实就是一个uint8_t类型:

typedef uint8_t             k_prio_t;

该成员表示系统中当前所存在任务的最高优先级,默认是系统定义的最大优先级。

3.2. 系统中的就绪列表

系统中有多少条就绪列表呢?

对了,答案当然是:「仅有唯一的一条就绪列表」

tos_global.h中声明,便于在整个内核的所有文件中使用:

/* ready queue of tasks                         */
extern readyqueue_t         k_rdyq;

tos_global.c中定义:

readyqueue_t        k_rdyq;

「记住它的名字,它叫k_rdyq」,k就是kernel,rdyq就是ready queue的缩写,后面会经常出现。

3.3. 初始化就绪列表

知道了就绪列表长啥样,就绪列表的初始化就变得非常简单了,都是常规操作,在tos_sched.c文件中实现:

__KNL__ void readyqueue_init(void)
{
    uint8_t i;

    k_rdyq.highest_prio = TOS_CFG_TASK_PRIO_MAX;

    for (i = 0; i < TOS_CFG_TASK_PRIO_MAX; ++i) {
        tos_list_init(&k_rdyq.task_list_head[i]);
    }

    for (i = 0; i < K_PRIO_TBL_SIZE; ++i) {
        k_rdyq.prio_mask[i] = 0;
    }
}

第①步是设置最高优先级成员的初始值,为系统当前配置的最高优先级;

第②步是遍历初始化每个双向链表节点;

第③步就是初始化优先级表的所有值,为0。

4. 任务如何挂载到就绪列表

在任务创建API的最后,会调用 readyqueue_add_tail 函数将任务加入到就绪列表中,那么,任务究竟是被如何挂载上去的呢?

此函数的源码实现如下:

__KNL__ void readyqueue_add_tail(k_task_t *task)
{
    k_prio_t task_prio;
    k_list_t *task_list;

    task_prio = task->prio;
    task_list = &k_rdyq.task_list_head[task_prio];

    if (tos_list_empty(task_list)) {
        readyqueue_prio_mark(task_prio);
    }

    tos_list_add_tail(&task->pend_list, task_list);
}

「获取该任务的优先级在就绪列表中所对应的首节点」

「在优先级表中记录此优先级」

判断系统中该优先级是否第一次出现,如果是,则将优先级表中此优先级的标志位置1,表示系统中存在此优先级的任务,并重新赋值就绪列表中的最高优先级指示成员(注:优先级值越小,表示优先级越高):

__STATIC_INLINE__ void readyqueue_prio_insert(k_prio_t prio)
{
    k_rdyq.prio_mask[K_PRIO_NDX(prio)] |= K_PRIO_BIT(prio);
}

__STATIC_INLINE__ void readyqueue_prio_mark(k_prio_t prio)
{
    readyqueue_prio_insert(prio);

    if (prio < k_rdyq.highest_prio) {
        k_rdyq.highest_prio = prio;
    }
}

举个例子,当我们创建了一个优先级为2的任务后,则优先级表如下:

「将该任务的任务控制块的pendlist节点,挂载到第一步获取到的首节点所指示的链表尾部」

任务控制块中的pend_list成员也是一个双向链表节点:

/**
 * task control block
 */
struct k_task_st {
 //……
 
    k_list_t pend_list; /**< when we are ready, our pend_list is in readyqueue; when pend, in a certain pend object's list. */

 //……
};

使用双向链表将此pendlist节点添加到第①步获取到的链表尾部,添加之后如图:

5. 优先级抢占式调度

5.1. 调度规则

理解了上面的三节内容,再来看优先级抢占式调度,简直就是水到渠成。

同样,先放上优先级抢占式调度的源码,在tos_syc.c中:

__KNL__ void knl_sched(void)
{
    TOS_CPU_CPSR_ALLOC();

    if (unlikely(!tos_knl_is_running())) {
        return;
    }

    if (knl_is_inirq()) {
        return;
    }

    if (knl_is_sched_locked()) {
        return;
    }

    TOS_CPU_INT_DISABLE();
    k_next_task = readyqueue_highest_ready_task_get();
    if (knl_is_self(k_next_task)) {
        TOS_CPU_INT_ENABLE();
        return;
    }

    cpu_context_switch();
    TOS_CPU_INT_ENABLE();
}

在源码中可以看到,优先级抢占式调度其实就是两个步骤:

① 获取就绪列表中的最高优先级的任务控制块指针;

② 启动上下文切换;

总结一下,优先级抢占式调度的规则就是:

「每当符合调度条件时时,就切换到就绪列表中优先级最高的任务开始运行」

5.2. 如何获取最高优先级的任务

别忘了就绪列表中有一个成员叫highest_prio,该成员指示出了系统当前存在的最高优先级,可以很方便的获取到挂载最高优先级的任务链表,函数源码如下:

__KNL__ k_task_t *readyqueue_highest_ready_task_get(void)
{
    k_list_t *task_list;

    task_list = &k_rdyq.task_list_head[k_rdyq.highest_prio];
    return TOS_LIST_FIRST_ENTRY(task_list, k_task_t, pend_list);
}

但是需要注意,在就绪列表上挂载的是任务控制块中的pend_list节点,如图:

已知任务控制块中pend_list节点地址,如何知道它所在任务控制块的基地址呢?

其实它是通过 TOS_LIST_FIRST_ENTRY 这个宏来获取的,具体的使用方法,请阅读我在文章开头提出的第二篇文章。

6. 优先级表有什么用?

优先级表的作用是:

「在将任务从就绪列表中移出时,用来获取当前就绪列表中的最高优先级」

优先级抢占式调度器可是六亲不认的,才不管任务当前状态是什么,反正就是永远寻找调度列表中最高优先级的任务。

所以当任务调用要主动挂起时,必须要从就绪列表中移出,源码如下:

__API__ k_err_t tos_task_suspend(k_task_t *task)
{
    TOS_CPU_CPSR_ALLOC();

 //一堆参数判断,省略了

    TOS_CPU_INT_DISABLE();

    if (task_state_is_ready(task))
    { 
     // kill the good kid
        readyqueue_remove(task);
    }
    task_state_set_suspended(task);

    TOS_CPU_INT_ENABLE();
    knl_sched();

    return K_ERR_NONE;
}

其中核心的就绪列表移出函数 readyqueue_remove 源码如下:

__KNL__ void readyqueue_remove(k_task_t *task)
{
    k_prio_t task_prio;
    k_list_t *task_list;

    task_prio = task->prio;
    task_list = &k_rdyq.task_list_head[task_prio];

    tos_list_del(&task->pend_list);

    if (tos_list_empty(task_list)) {
        readyqueue_prio_remove(task_prio);
    }

    if (task_prio == k_rdyq.highest_prio) {
        k_rdyq.highest_prio = readyqueue_prio_highest_get();
    }
}

① 获取任务当前优先级在就绪列表中的首节点;

② 将该任务控制块与该条双向链表断开(并没有删除任务);

③ 如果断开后该链表变空,则表示就绪列表中不存在该优先级的任务,在优先级表中将该位清零;

「重新获取就绪列表中的最高优先级」

这个时候优先级表的作用就体现出来了,之前讲到,优先级表中记录了当前就绪列表中所存在任务的优先级,所以可以通过遍历查找优先级表,来获取到最高优先级,最后赋值给就绪列表中的指示成员。

源码如下:

__STATIC__ k_prio_t readyqueue_prio_highest_get(void)
{
    uint32_t *tbl;
    k_prio_t prio;

    prio    = 0;
    tbl     = &k_rdyq.prio_mask[0];

    while (*tbl == 0) {
        prio += K_PRIO_TBL_SLOT_SIZE;
        ++tbl;
    }
    prio += tos_cpu_clz(*tbl);
    return prio;
}

7. 总结

讲述了这么多内容,非常有必要来总结出值得注意的点:

「RTOS内核中通过手动触发PendSV异常来启动一次切换,任务切换在PendSV异常服务函数中实现」

「RTOS内核中PendSV异常的优先级被设为最低,避免在外部中断处理函数中产生任务切换」

「RTOS内核所谓的优先级抢占式调度规则就是永远从就绪队列中找出最高优先级的任务来运行」

当然,有了优先级抢占式调度规则,才勉强撑起来了一个RTOS内核的肉体,什么时候进行调度,才是一个RTOS内核的灵魂,接下来的文章与大家再会。

本文分享自微信公众号 - Mculover666(Mculover666),作者:mculover666

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LiteOS内核教程03 | 任务管理

    Huawei LiteOS 内核提供任务的创建、删除、延迟、挂起、恢复等功能,以及锁定和解锁任务调度,支持任务按优先级高低的抢占调度及同优先级时间片轮转调度。

    Mculover666
  • Matlab上位机开发(三)波形显示(幅度和频率可调节)

    波形显示控件可以用于绘制各种波形,拖动控件到画布中即可,然后根据需要调整控件大小:

    Mculover666
  • STM32Cube-19 | 使用SDMMC接口读写SD卡数据

    本篇详细的记录了如何使用STM32CubeMX配置STM32L431RCT6的硬件SDMMC外设读取SD卡数据。

    Mculover666
  • Microsoft 线性回归分析算法

    前言 在此系列中涵盖了微软在商业智能(BI)模块系统所能提供的所有挖掘算法,当然此框架完全可以自己扩充,可以自定义挖掘算法,不过目前此系列中还不涉及,只涉及微...

    机器学习AI算法工程
  • 游戏服务器压力测试总结

    游戏服务器压力测试总结 从游戏内测开始到现在做了所有服务器压力相关的测试.现在进行总结.暂时还不方便说游戏架构,所以不上图了。 一.首先明确需要测试压力的内...

    李海彬
  • 机器学习必备的数学基础有哪些?

    对于机器学习给出了这样一个定义,机器学习是由三个部分组成,分别是表示、评价,还有优化。这样的三个步骤,实际上也就对应着在机器学习当中所需要的数学。

    刀刀老高
  • Redis系列(6)——RedisTemplate操作模板

    转载地址: http://blog.csdn.net/hotdust/article/details/51832926

    逝兮诚
  • 明亮解我“工厂模式无用”之惑

    明亮,是我的大学同学,我们一个在北京,一个在深圳,昨晚两人视频关于工厂模式聊到深夜。

    草捏子
  • 通俗理解Kubernetes中Service、Ingress与Ingress Controller的作用与关系

    Kubernetes 并没有自带 Ingress Controller,它只是一种标准,具体实现有多种,需要自己单独安装,常用的是 Nginx Ingress ...

    imroc
  • 通俗理解Kubernetes中Service、Ingress与Ingress Controller的作用与关系

    Kubernetes 并没有自带 Ingress Controller,它只是一种标准,具体实现有多种,需要自己单独安装,常用的是 Nginx Ingress ...

    imroc

扫码关注云+社区

领取腾讯云代金券