0%

RTOS的设计要点

优先级调度算法

概述

嵌入式实时操作系统对于task调度有着严格的时间要求,即在不同优先级task之间的调度时间应该保持一致,但是普通查表法会从头开始遍历数组,这样就绪态最高优先级的task会比就绪态最高优先级低的task先被查找到,造成不同优先级task在调度上花费时间不一致的情况。为了可以在相同时间里查找到最高就绪态优先级task,ucos采用了空间换取时间的算法在相同时间里查找到优先级最高task,具体算法如下。

设置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的位数详细如下:

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运行就是操作系统的task调度算法,调度算法决定了操作系统的好坏,因此调度算法是操作系统的一项核心功能,ucos操作系统是基于优先级的可剥夺内核调度,即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
21
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. 定义关中断方式:
1
2
#if OS_CRITICAL_METHOD == 3
OS_CPU_SR cpu_sr = 0;

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

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

这句就是关全局中断

  1. 判断是否在中断里或调度器是否上锁,是就执行一次调度:
1
2
if (OSIntNesting == 0) {
if (OSLockNesting == 0) {
  1. 判断当前task是否是就绪的最高优先级task以减少task调度带来的额外开销:
1
if (OSPrioHighRdy != OSPrioCur)
  1. 将准备就绪的最高优先级task指向该该task的task控制块:
1
OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy];
  1. task切换统计计数器加一:
1
OSCtxSwCtr++;
  1. task切换:
1
OS_TASK_SW();
  1. 开中断:
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处执行,代码如下:

PendSV异常代码

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调度。

统计task

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

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

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

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

task调度中存在的问题

优先级反转

使用实时内核,优先级反转问题是实时系统中出现得最多的问题。下图解释优先级反转是如何出现的:

如图,task的优先级为 task1 > task2 > task3

阶段一:task1和task2 处于休眠态,task申请持有锁 阶段二:task1切换到运行态,也要申请该锁,因申请不到而休眠 阶段三:task2切换到运行态,由于优先级高于task3而先运行 阶段四:task2运行结束,task3运行,释放锁、然后task1恢复运行态开始运行

实际task运行的优先级想当于task2 > task1,发生了优先级反转

解决措施:在task3使用共享资源时,提升task3的优先级,task完成时予以恢复。task3的优先级必须升至最高,高于允许使用该资源的任何task优先级。

然而改变task的优先级是很花时间的。如果task3并没有先被task2剥夺CPU使用权,花很多时间在共享资源使用前提升task3的优先级,然后又在资源使用后花时间恢复task3的优先级,则无形中浪费了很多CPU时间。真正需要的是,为防止发生优先级反转,内核能自动变换task的优先级,这叫做优先级继承(Priority inheritance)但uC/OS-Ⅱ不支持优先级继承。

死锁

死锁也称作抱死,指两个task无限期地互相等待对方控制着的资源。设task T1正独享资源R1,task T2在独享资源R2,而此时T1又要独享R2,T2也要独享R1,于是哪个task都没法继续执行了,发生了死锁。最简单的防止发生死锁的方法是让每个task都:

  • 先得到全部需要的资源再做下一步的工作
  • 用同样的顺序去申请多个资源,释放资源时使用相反的顺序

延时误差分析

概述

对于操作系统来讲时间是颗粒性的不是连续的(物理世界也是这样的),就是操作系统有最小时间颗粒,假如操作系统的时钟滴答是1ms那么操作系统是没办法区分小于这个时间的,这就是操作系统延时抖动的一个重要原因,操作系统会把999us到1ms的这个1us当1ms处理,当然也会将1us到1999us这个接近2ms的时间当成1ms计算,这就造成了一定的延时误差,另一个延时误差来自task的运行,task是轮询运行的也就是延时1ms后时间到了,但是高优先级task会先运行,之后再将cpu控制权转交给延时task,这两个延时共同构成了操作系统的延时抖动,对于精确的延时需要采用硬件定时器延时,但是对于精度要求不是那么高利用操作系统提供的延时是非常方便的,其延时误差在时钟颗粒级别非常小。

task调度时机

假设时钟节拍是1ms发生一次,要求task A延时一个时钟节拍下面三种情况体现了延时抖动的原因。

第一种情况下执行延时函数后不到1ms就到来时钟节拍而其他高优先级task又没有多少task可以执行很快轮到task A执行因此task A实际延时小于1ms。

第二种情况当调用延时函数后高优先级task执行时间较长大于上一次时钟节拍到来到调用延时函数的时间,那么延时将大于1ms。

第三种情况是高优先级task执行时间过长超过一个时钟节拍那么那么实际延时可能是2ms因此,采用操作系统延时是不准确的,下图是task调度时机:

延时的实际执行过程是这样的,在每一次时钟周期到来将发生一次中断,调用节拍服务函数OSTimeTick(),该函数主要的功能是给每个用户task控制块OS_TCB中的时钟延时项OSTCBDly减一直到等于0,在减到0之前task是挂起的,而当task延时减到0时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)中的一种。用户要根据该域的具体值来调用相应的系统函数,以保证对其进行的操作的正确性

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

通信手段

用于行为同步的通信手段

  • 二值信号量:二值信号量的使用范围是: 被控制方总能够及时响应控制方发出的信号,完成相应处理task,并在下一次信号来到之前进入等待状态
  • 计数信号量:计数信号量的使用范围是: 被控制方不能保证在下一次信号到来之前处理完本次控制方发出的信号,但总体上可以响应所有信号
  • 事件标志组:“事件标志组”可以实现多个task(包括ISR)协同控制一个task,当各个相关task(包括ISR)先后发出自己的信号后(使事件标志组的对应标志有效),预定的逻辑运算结果有效,触发被控制的task
  • 消息邮箱:由于“消息邮箱”里只能存放一条消息,所以在用“消息邮箱”进行同步控制时,必须满足一个前提:任何时候消息的生产速度都比消息的消费速度慢,即被控制task总是在等待消息。这和二值信号量的情况类似
  • 消息队列:“消息队列”可以存放多个消息,能够有效解决消息的“临时堆积”问题。与计数信号量的情况类似,“消息队列”的使用仍然需要满足一个条件:消息的平均生产时间比消息的平均消费时间长;否则,再长的“消息队列”也会“溢出”

将以上通信手段用于task之间的行为同步时需要根据实际情况来选择:

  • 当同步过程不需要传输具体内容时,可选择信号量类手段(二值信号量、计数信号量和事件标志组)
  • 当同步过程需要传输具体内容时,可选择消息类手段(消息邮箱和消息队列)
  • 当满足“任何时候同步信息的生产速度都比同步信息的消费速度慢”时,可选择简单的通信手段(二值信号量、事件标志组和消息邮箱)
  • 对于非周期性同步信息,当不能保证“任何时候同步信息的生产速度都比同步信息的消费速度慢”时,可选择有缓冲功能的通信手段(计数信号量和消息队列)
  • 当同步信号为多个信号的逻辑运算结果时,采用事件标志组作为同步手段

数据通信

  • 全局变量与内存数据块:在没有行为同步要求的前提下,当传输的数据量不大时,采用全局变量并配合关中断的资源同步揹施是一种经济、有效的方法
  • 消息邮箱:“消息邮箱”就是具有行为同步功能的通信手段,不具备缓存功能,消费必须及时
  • 消息队列:消息队列”是具有行为同步功能和缓冲功能的数据通信手段

参考文献

《嵌入式实时操作系统ucos-ii教程》
《周慈航-基于嵌入式实时操作系统的程序设计技术》