ucos 优先级调度算法

保证调度延迟的确定性

普通查表法会从头开始遍历数组，这样就绪态最高优先级的 task 会比就绪态优先级低的 task 先被查找到，造成不同优先级 task 在调度上花费时间不一致的情况，这违背了实时性的原则。

ucos 调度原理

为了确保调度延迟一致性，ucos 采用了空间换取时间的算法在相同时间里查找到不同优先级 task，具体算法如下。 整个算法由两个变量、两个表格和三个程序组成：两个变量是 OSRdyGrp 和 OSRdyTbl[]; 两个表格是位掩码表 OSMapTbl[] 和优先级判定表 OSUnMap[]，三个程序分别是使 task 进入就绪、脱离就绪、寻找就绪态最高优先级 task。

使 task 进入就绪态的程序如下：

1
2
3
/* 将 prio 优先级放入就绪态优先级表中 */
OSRdyGrp = OSMapTbl[prio>>3];               //设置就绪态优先级组标志
OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07];   //设置就绪态优先级组内的位标志

就是将 OSRdyTbl 相应元素的相应位置位，使 task 脱离就绪状态就是将相应位置零，程序如下：

1
2
3
/* 将 prio 优先级从就绪态优先级表中删除 */
if(OSRdyTbl[prio>>3] &=~OSMapTbl[prio & 0x07]) == 0)
    OSRdyGrp &=~ OSMapTbl[prio>>3];

变量 OSRdyGrp 的每一位就代表一个组。

查找最高优先级 task

task 优先级计算公式 \(prio=y*8+x\) ，其中 y=OSRdyGrp 最高优先级的 task 在 OSRdyGrp 的最低不为 0 的位的那个组，在这个组里优先级最高的 task 在组内最低不为 0 的位，因此寻找最高优先级 task 就相当于寻找这两个变量里最低不为 0 的位。接下来就是通过 OSUnMapTbl[] 数组来查找最低位不为 0 的位的数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
INT8U const OSUnMapTbl[256] = {
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0  /* 0xF0 to 0xFF */
}；

这个表格里的数据很奇怪，好像没什么规律，其实这些数据是 0x00-0xff 这些数据中最低位不为 0 的位数详细如下：

1
2
3
4
5
6
0x00 ==00000000b 最低位为 1 的位数为 bit0；
0x01 ==00000001b 最低位为 1 的位数为 bit0；
0x02 ==00000010b 最低位为 1 的位数为 bit1；
0x03 ==00000011b 最低位为 1 的位数为 bit0；
0x04 ==00000100b 最低位为 1 的位数为 bit2；
0x05 ==00000101b 最低位为 1 的位数为 bit0；

以此类推就得到 OSUnMapTbl 表格。最高优先级 task 就是在优先级组和位里找到最低位不为 0 的位并组合位一个完整的优先级，计算如下：

1
2
3
4
/* 计算就绪态最高优先级 */
y = OSUnMapTbl[OSRdyGrp];
x = OSUnMapTbl[OSRdyTbl[y]];
OSPrioHighRdy = (INT8U)((y << 3) + x);

这就是用空间换时间的算法，可以保障寻找到最高优先级 task 的时间相同。

调度过程

操作系统提供的一个基本功能就是多 task 运行，而多 task 运行实质上是轮询占用 CPU。task 的调度就是利用中断来进行 task 之间的切换，周期性进入中断函数，然后选择一个合适的 task 运行就是操作系统的 task 调度算法。调度算法是操作系统的一项核心功能，ucos 操作系统是基于优先级的可剥夺内核调度，即 task 的调度基于 task 的优先级，同时高优先级 task 可以抢占低优先级 task 运行，因此，每个 task 在运行完需要一个延时以将 cpu 资源让给其他低优先级 task。ucos 的 task 调度分为两种方式：一种是 task 级的调度由函数 OS_SChed() 函数完成，另一种是中断级的调度由函数 OSIntExt() 函数完成，本文只分析 task 级调度：

OS_Sched 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void  OS_Sched (void)
{
#if OS_CRITICAL_METHOD == 3
    OS_CPU_SR  cpu_sr = 0;
#endif
    OS_ENTER_CRITICAL();
    if (OSIntNesting == 0) {
        if (OSLockNesting == 0) {
            OS_SchedNew();
            if (OSPrioHighRdy != OSPrioCur) {
                OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy];
#if OS_TASK_PROFILE_EN > 0
                OSTCBHighRdy->OSTCBCtxSwCtr++;
#endif
                OSCtxSwCtr++;
                OS_TASK_SW();
        }
    }
    OS_EXIT_CRITICAL();
}

函数主要完成以下工作：

  • 定义关中断方式：

    1
    2
    #if OS_CRITICAL_METHOD == 3
    OS_CPU_SR cpu_sr = 0;

    定义第三种方法开关中断，这里插入讲解一下 os 开关中断的三种方式，

    • 第一种是利用 cpu 自带的总中断寄存器来实现开关全局中断，优点是实现方便缺点是总中断有可能原本就是关着的，在调用完会将全局中断打开。
    • 第二种开关全局中断的方式是利用堆栈保存中断的状态，关中断后恢复之前的中断状态，解决了第一种中断的弊端。
    • 第三种方法是定义一个局部变量 cpu_sr 来保存 PSW 再关中断之后再恢复 cpu_sr 到 PSW 程序状态寄存器中。

  • 关中断：

    1
    OS_ENTER_CRITICAL();

  • 判断是否在中断里或调度器是否上锁，是就执行一次调度：

    1
    2
    if (OSIntNesting == 0) {
        if (OSLockNesting == 0) {

  • 判断当前 task 是否是就绪的最高优先级 task 以减少 task 调度带来的额外开销：

    1
    if (OSPrioHighRdy != OSPrioCur)

  • 将准备就绪的最高优先级 task 指向该该 task 的 task 控制块：

    1
    OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy];

  • task 切换统计计数器加一：

    1
    OSCtxSwCtr++;

  • task 切换：

    1
    OS_TASK_SW();

  • 开中断：

    1
    OS_EXIT_CRITICAL();

OS_TASK_SW 函数

下面介绍 OS_TASK_SW() 函数，task 级调度其实就是认为模拟一次中断分两步进行，第一步是将被挂起 task 的 CPU 寄存器压入堆栈，第二步是将准备就绪的最高优先级 task 的寄存器从 task 堆栈中恢复到寄存器中。

1
2
3
4
5
OSCtxSw
LDR R0, =NVIC_INT_CTRL ; Trigger the PendSV exception (causes context switch)
LDR R1, =NVIC_PENDSVSET
STR R1, [R0]
BX LR

OS_TASK_SW() 是一个宏定义他实际上是 OSCtxSw 汇编代码的宏定义：

1
2
3
NVIC_INT_CTRL EQU 0xE000ED04

NVIC_PENDSVSET EQU 0x10000000

这段汇编代码是为了触发 PendSV 异常，进入异常指令代码去执行，通过查询我们发现跳转到 OS_CPU_PendSVHandler 处执行，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
OS_CPU_PendSVHandler
CPSID I ; Prevent interruption during context switch
MRS R0, PSP ; PSP is process stack pointer
CBZ R0, OS_CPU_PendSVHandler_nosave ; Skip register save the first time

SUBS R0, R0, #0x20 ; Save remaining regs r4-11 on process stack
STM R0, {R4-R11}

LDR R1, =OSTCBCur ; OSTCBCur->OSTCBStkPtr = SP;
LDR R1, [R1]
STR R0, [R1] ; R0 is SP of process being switched out; At this point, entire context of process has been saved
OS_CPU_PendSVHandler_nosave
PUSH {R14} ; Save LR exc_return value
LDR R0, =OSTaskSwHook ; OSTaskSwHook();
BLX R0
POP {R14}

LDR R0, =OSPrioCur ; OSPrioCur = OSPrioHighRdy;
LDR R1, =OSPrioHighRdy
LDRB R2, [R1]
STRB R2, [R0]

LDR R0, =OSTCBCur ; OSTCBCur = OSTCBHighRdy;
LDR R1, =OSTCBHighRdy
LDR R2, [R1]
STR R2, [R0]

LDR R0, [R2] ; R0 is new process SP; SP = OSTCBHighRdy->OSTCBStkPtr;
LDM R0, {R4-R11} ; Restore r4-11 from new process stack
ADDS R0, R0, #0x20
MSR PSP, R0 ; Load PSP with new process SP
ORR LR, LR, #0x04 ; Ensure exception return uses process stack
CPSIE I
BX LR ; Exception return will restore remaining context
END

总结起来就是将当前寄存器保存到当前查询堆栈中。

1
OSTCPHightRdy->OSTCBsTKpTR

获取到就绪态最高优先级 task 的 SP 并将其恢复到 CPU SP 寄存器中，将其他寄存器弹出执行中断返回，当前寄存器环境 sp，pc 等就是要切换 task 的环境值，运行代码就是切换后的 task，操作系统实现了 task 调度。

同步的实现

同步的手段有很多这里以事件控制块及其处理函数为例来说明，其他同步手段实现原理是相同的只是根据不同的需求做了响应的设计。

事件控制块

事件同步和资源同步都是通过事件控制块 ECB 结构来管理的，对于事件或者资源的请求或者释放伴随着 task 的挂起和恢复。

1
2
3
4
5
6
7
8
9
10
11
typedef struct os_event {
    INT8U    OSEventType;                    /*事件类型 Type of event control block (see OS_EVENT_TYPE_xxxx)    */
    void    *OSEventPtr;                     /*指向消息或者消息队列的指针 Pointer to message or queue structure     */
    INT16U   OSEventCnt;                     /*计数器 Semaphore Count (not used if other EVENT type)          */
    OS_PRIO  OSEventGrp;                     /*等待 task 所在的组 Group corresponding to tasks waiting for event to occur */
    OS_PRIO  OSEventTbl[OS_EVENT_TBL_SIZE];  /*等待 task 列表 List of tasks waiting for event to occur                */

#if OS_EVENT_NAME_EN > 0u
    INT8U   *OSEventName;
#endif
} OS_EVENT;
  • OSEventPtr 指针，只有在所定义的事件是邮箱或者消息队列时才使用。当所定义的事件是邮箱时，它指向一个消息，而当所定义的事件是消息队列时，它指向一个数据结构。
  • OSEventTbl[] 和 OSEventGrp 很像前面讲到的 OSRdyTbl[] 和 OSRdyGrp，只不过前两者包含的是等待某事件的 task，而后两者包含的是系统中处于就绪状态的 task。
  • OSEventCnt 当事件是一个信号量时，.OSEventCnt 是用于信号量的计数器。
  • OSEventType 定义了事件的具体类型。它可以是信号量（OS_EVENT_SEM）、邮箱（OS_EVENT_TYPE_MBOX）或消息队列（OS_EVENT_TYPE_Q）中的一种。用户要根据该域的具体值来调用相应的系统函数，以保证对其进行的操作的正确性。

对于等待事件任务的记录，uC/OS-II 又使用了与任务就绪表类似的位图，即定义了一个 UINT8 类型的数组 OSEventTbl[] 来作为等待事件任务的记录表，即等待任务表。

等待任务表仍然以任务的优先级别为顺序为每个任务分配一个二进制位，并用该位为 1 来表示这一位对应的任务为事件的等待任务，否则不是等待任务。同样，为了加快对该表的访问速度，也定义了一个 UINT8 类型的变量 OSEventGrp 来表示等待任务表中的任务组。等待任务表 OSEventTbl[] 与变量 OSEventGrp 的示意图如图所示：

至于等待任务的等待时限，则记录在等待任务的任务控制块 TCB 的成员 OSTCBDIy 中并在每个时钟节拍中断服务程序中对该数据进行维护。每当有任务的等待时限到时，将该务从等待任务表中删除，并使它进入就绪状态。

空事件控制块链表

在μC/OS-II 初始化时，系统在初始化函数 OSnit() 中创建 OS_MAX_EVEINTS 个空事件控制块并借用成员 OSEventPtr 作为链接指针，把这些空事件控制块链接成一个如图 5-11 所示的单向链表。由于链表中的所有控制叫做空事件控制块且尚未与具体事件相关联，因此该链表叫空事件控制块链表。以后，每当应用程序创建一个事件时，系统就会从链表中取出一个事件控制块，并对事件控制块进行初始化以描述该事件。而当用程序删除一个事件时，就会将该事件控制块归还给空事件控制块链表。

操作函数

当 task 请求一个事件的时候（OS_EventTaskWait()），而该事件正好被另一个 task 持有，那么当前 task 就会挂起放到 OSEventTbl 和 OSEventGrp 里。在持有事件的 task 释放事件的时候会再将请求该事件的 task 唤醒 (OS_EventTaskRdy())。从而实现两个 task 之间的同步（事件或资源）。

其他信号量、互斥信号量、消息队列、消息邮箱等实现原理是相同的，这里不再一一列出了。

统计 task

ucos 计算 CPU 利用率的实现方法是：

  • 在运行 task 之前计算出空闲 task 运行的最大速率 OSIdleCtrMax。
  • 求出 task 运行时空闲 task 计数器的计数速率 OSIdleCtr。
  • 利用公式求出 CPU 利用率就是 OSIdleCtr/OSIdleCtrMax * 100%。

就是通过计算 cpu 进入空闲 task 的比例来推算出 cpu 利用率。

1
OSCPUUsage   = (INT8U)(100L - OSIdleCtrRun / OSIdleCtrMax);

参考文献

《嵌入式实时操作系统 ucos-ii 教程》
《周慈航-基于嵌入式实时操作系统的程序设计技术》
《嵌入式实时操作系统μCOS-II原理及应用-任哲》