uCOS II 内核调度分析
一. 内核概述:
多任务系统中,内核负责管理各个任务,或者说为每个任务分配 CPU 时间,并且负责任务
之间的通讯。内核提供的基本服务是任务切换。之所以使用实时内核可以大大简化应用系统的设
计,是因为实时内核允许将应用分成若干个任务,由实时内核来管理它们。内核本身也增加了应
用程序的额外负荷,代码空间增加 ROM 的用量,内核本身的数据结构增加了 RAM 的用量。但更主
要的是,每个任务要有自己的栈空间,这一块吃起内存来是相当厉害的。内核本身对 CPU 的占用
时间一般在 2 到 5 个百分点之间。uCOS II 有一个精巧的内核调度算法,实时内核精小,执行效
率高,算法巧妙,代码空间很少。
二. uCOS II 内核调度特点:
只支持基于优先级的抢占式调度算法,不支持时间片轮训;
64 个优先级,只能创建 64 个任务,用户只能创建 56 个任务;
每个任务优先级都不相同。
不支持优先级逆转;
READY 队列通过内存映射表实现快速查询。效率非常高;
支持时钟节拍;
支持信号量,消息队列,事件控制块,事件标志组,消息邮箱任务通讯机制;
支持中断嵌套,中断嵌套层数可达 255 层,中断使用当前任务的堆栈保存上下文;
每个任务有自己的堆栈,堆栈大小用户自己设定;
支持动态修改任务优先级;
任务 TCB 为静态数组,建立任务只是从中获得一个 TCB,不用动态分配,释放内存;
任务堆栈为用户静态或者动态创建,在任务创建外完成,任务创建本身不进行动态
内存分配;
任务的总个数(OS_MAX_TASKS)由用户决定;
0 优先级最高,63 优先级最低;
有一个优先级最低的空闲任务,在没有用户任务运行的时候运行.
三. 任务控制块 OS_TCB 描述:
uCOS II 的 TCB 数据结构简单,内容容易理解,保存最基本的任务信息,同时还支持裁减
来减小内存消耗,TCB 是事先根据用户配置,静态分配内存的结构数组,通过优先级序号进行添
加,查找,删除等功能。减少动态内存分配和释放。因为依靠优先级进行 TCB 分配,每个任务必
须有自己的优先级,不能和其他任务具有相同的优先级。
typedef struct os_tcb
{
OS_STK
*OSTCBStkPtr;
#if OS_TASK_CREATE_EXT_EN
void
OS_STK
INT32U
INT16U
INT16U
*OSTCBExtPtr;
*OSTCBStkBottom;
OSTCBStkSize;
OSTCBOpt;
OSTCBId;
#endif
struct os_tcb *OSTCBNext;
struct os_tcb *OSTCBPrev;
#if (OS_Q_EN && (OS_MAX_QS >= 2)) || OS_MBOX_EN || OS_SEM_EN
OS_EVENT
*OSTCBEventPtr;
#endif
#if (OS_Q_EN && (OS_MAX_QS >= 2)) || OS_MBOX_EN
void
*OSTCBMsg;
#endif
INT16U
INT8U
INT8U
INT8U
INT8U
INT8U
INT8U
OSTCBDly;
OSTCBStat;
OSTCBPrio;
OSTCBX;
OSTCBY;
OSTCBBitX;
OSTCBBitY;
#if OS_TASK_DEL_EN
BOOLEAN
OSTCBDelReq;
#endif
} OS_TCB;
.OSTCBStkPtr 是指向当前任务栈顶的指针。
.*OSTCBExtPtr;:任务扩展模块使用;
.*OSTCBStkBottom;
.OSTCBStkSize; .
.OSTCBOpt;
.OSTCBId;
.OSTCBNext 和.OSTCBPrev 用于任务控制块 OS_TCBs 的双重链接,
.OSTCBEventPtr 是指向事件控制块的指针
.OSTCBMsg 是指向传给任务的消息的指针。
.OSTCBDly 当需要把任务延时若干时钟节拍时要用到这个变量,或者需要把任务挂起一段时间以
等待某事件的发生,
.OSTCBStat 是任务的状态字。
.OSTCBPrio 是任务优先级。
.OSTCBX, .OSTCBY, .OSTCBBitX 和 .OSTCBBitY 用于加速任务进入就绪态的过程或进入等待事件
发生状态的过程
OSTCBY = priority >> 3;
OSTCBBitY = OSMapTbl[priority >> 3];
OSTCBX = priority & 0x07;
OSTCBBitX = OSMapTbl[priority & 0x07];
.OSTCBDelReq 是一个布尔量,用于表示该任务是否需要删除
四. 就绪表(Ready List):
uCOS II 采用内存映射的方式来实现 READY 队列的加入,查找,删除功能,效率非常高。
但是也因此只能支持 64 个任务,每个任务都有自己的优先级,不能和其他任务优先级相同。
每个任务的就绪态标志都放入就绪表中的,就绪表中有两个变量 OSRdyGrp 和 OSRdyTbl[]。
在 OSRdyGrp 中,任务按优先级分组,8 个任务为一组。OSRdyGrp 中的每一位表示 8 组任务中每
一组中是否有进入就绪态的任务。任务进入就绪态时,就绪表 OSRdyTbl[]中的相应元素的相应
位也置位。就绪表 OSRdyTbl[]数组的大小取决于 OS_LOWEST_PRIO(见文件 OS_CFG.H)。
为确定下次该哪个优先级的任务运行了,内核调度器总是将 OS_LOWEST_PRIO 在就绪表
中相应字节的相应位置 1。OSRdyGrp 和 OSRdyTbl[]的关系见图 3.3,是按以下规则给出的:
当 OSRdyTbl[0]中的任何一位是 1 时,OSRdyGrp 的第 0 位置 1,
当 OSRdyTbl[1]中的任何一位是 1 时,OSRdyGrp 的第 1 位置 1,
当 OSRdyTbl[2]中的任何一位是 1 时,OSRdyGrp 的第 2 位置 1,
当 OSRdyTbl[3]中的任何一位是 1 时,OSRdyGrp 的第 3 位置 1,
当 OSRdyTbl[4]中的任何一位是 1 时,OSRdyGrp 的第 4 位置 1,
当 OSRdyTbl[5]中的任何一位是 1 时,OSRdyGrp 的第 5 位置 1,
当 OSRdyTbl[6]中的任何一位是 1 时,OSRdyGrp 的第 6 位置 1,
当 OSRdyTbl[7]中的任何一位是 1 时,OSRdyGrp 的第 7 位置 1,
程序清单 3.5 中的代码用于将任务放入就绪表。Prio 是任务的优先级。
程序清单 L3.5 使任务进入就绪态 (这两行代码简直是神来之笔啊!!!)
/*
这行代码功能是找到列, 把列上的值置为 1
不妨假设 prio 的值为 13, 即优先级为 13. prio>>3 右移 3 位后值为 1, 可以查表 T3.1 找出
OSMapTbl[1] 的值为 0000 0010. 再用 0000 0010 和 OSRdyGrp 进行异或运算
*/
OSRdyGrp |= OSMapTbl[prio >> 3];
/*
*/
OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07];
任务优先级的低三位用于确定任务在总就绪表 OSRdyTbl[]中的所在位。接下去的三位用于确定
是在 OSRdyTbl[]数组的第几个元素。 OSMapTbl[]是在 ROM 中的(见文件 OS_CORE.C)屏蔽字,
用于限制 OSRdyTbl[]数组的元素下标在 0 到 7 之间,见表 3.1
Index Bit Mask (Binary)
0 00000001
1 00000010
2 00000100
3 00001000
4 00010000
5 00100000
6 01000000
7 10000000
如果一个任务被删除了,则用程序清单 3.6 中的代码做求反处理。
程序清单 L3.6 从就绪表中删除一个任务
if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)
OSRdyGrp &= ~OSMapTbl[prio >> 3];
以上代码将就绪任务表数组 OSRdyTbl[]中相应元素的相应位清零,而对于 OSRdyGrp,只有当被
删除任务所在任务组中全组任务一个都没有进入就绪态时,才将相应位清零。也就是说
OSRdyTbl[prio>>3]所有的位都是零时,OSRdyGrp 的相应位才清零。为了找到那个进入就绪态的
优先级最高的任务,并不需要从 OSRdyTbl[0]开始扫描整个就绪任务表,只需要查另外一张表,
即优先级判定表 OSUnMapTbl ([256])(见文件 OS_CORE.C)。OSRdyTbl[]中每个字节的 8 位代表这
一组的 8 个任务哪些进入就绪态了,低位的优先级高于高位。利用这个字节为下标来查
OSUnMapTbl 这张表,返回的字节就是该组任务中就绪态任务中优先级最高的那个任务所在的位
置。这个返回值在 0 到 7 之间。确定进入就绪态的优先级最高的任务是用以下代码完成的。
找出进入就绪态的优先级最高的任务
y
x
= OSUnMapTbl[OSRdyGrp];
= OSUnMapTbl[OSRdyTbl[y]];
prio = (y << 3) + x;
例如,如果 OSRdyGrp 的值为二进制 01101000,查 OSUnMapTbl[OSRdyGrp]得到的值是
3,它相应于 OSRdyGrp 中的第 3 位 bit3,这里假设最右边的一位是第 0 位 bit0。类似地,如果
OSRdyTbl[3]的值是二进制 11100100,则 OSUnMapTbl [OSRdyTbc[3]]的值是 2,即第 2 位。于是
任务的优先级 Prio 就等于 26(3*8+2)。利用这个优先级的值。查任务控制块优先级表
OSTCBPrioTbl[],得到指向相应任务的任务控制块 OS_TCB 的工作就完成了。
五. 任务状态:
uCOS II 主要有五种任务状态,睡眠态就是挂起态,阻塞态和延时态这里统一为等待状态。
增加了一个被中断状态。UC/OS-Ⅱ总是建立一个空闲任务,这个任务在没有其它任务进入就绪态
时投入运行。这个空闲任务[OSTaskIdle()]永远设为最低优先级空闲任务 OSTaskIdle()什么也
不做,只是在不停地给一个 32 位的名叫 OSIdleCtr 的计数器加 1,统计任务使用这个计数器以
确定现行应用软件实际消耗的 CPU 时间。空闲任务不可能被应用软件删除。
睡眠态(DORMANT)指任务驻留在程序空间之中,还没有交给μC/OS-Ⅱ管理,把任务交给
μC/OS-Ⅱ是通过调用下述两个函数之一:OSTaskCreate()或 OSTaskCreateExt()。当任务一旦
建立,这个任务就进入就绪态准备运行。任务的建立可以是在多任务运行开始之前,也可以是动
态地被一个运行着的任务建立。如果一个任务是被另一个任务建立的,而这个任务的优先级高于
建立它的那个任务,则这个刚刚建立的任务将立即得到 CPU 的控制权。一个任务可以通过调用
OSTaskDel()返回到睡眠态,或通过调用该函数让另一个任务进入睡眠态。
调用 OSStart()可以启动多任务。OSStart()函数运行进入就绪态的优先级最高的任务。
就绪的任务只有当所有优先级高于这个任务的任务转为等待状态,或者是被删除了,才能进入运
行态。
正在运行的任务可以通过调用两个函数之一将自身延迟一段时间,这两个函数是
OSTimeDly()或 OSTimeDlyHMSM()。这个任务于是进入等待状态,等待这段时间过去,下一个优
先级最高的、并进入了就绪态的任务立刻被赋予了 CPU 的控制权。等待的时间过去以后,系统服
务函数 OSTimeTick()使延迟了的任务进入就绪态(见 3.10 节,时钟节拍)。
正在运行的任务期待某一事件的发生时也要等待,手段是调用以下 3 个函数之一:
OSSemPend(),OSMboxPend(),或 OSQPend()。调用后任务进入了等待状态(WAITING)。当任务
因等待事件被挂起(Pend),下一个优先级最高的任务立即得到了 CPU 的控制权。当事件发生了,
被挂起的任务进入就绪态。事件发生的报告可能来自另一个任务,也可能来自中断服务子程序。
正在运行的任务是可以被中断的,除非该任务将中断关了,或者μC/OS-Ⅱ将中断关了。被中断
了的任务就进入了中断服务态(ISR)。响应中断时,正在执行的任务被挂起,中断服务子程序
控制了 CPU 的使用权。中断服务子程序可能会报告一个或多个事件的发生,而使一个或多个任务
进入就绪态。在这种情况下,从中断服务子程序返回之前,μC/OS-Ⅱ要判定,被中断的任务是
否还是就绪态任务中优先级最高的。如果中断服务子程序使一个优先级更高的任务进入了就绪
态,则新进入就绪态的这个优先级更高的任务将得以运行,否则原来被中断了的任务才能继续运
行。
当所有的任务都在等待事件发生或等待延迟时间结束,μC/OS-Ⅱ执行空闲任务(idle
task),执行 OSTaskIdle()函数。
六. 任务切换:
Context Switch
在有的书中翻译成上下文切换,实际含义是任务切换,或 CPU 寄存器
内容切换。当多任务内核决定运行另外的任务时,它保存正在运行任务的当前状态(Context),
即 CPU 寄存器中的全部内容。这些内容保存在任务的当前状况保存区(Task’s Context Storage
area),也就是任务自己的栈区之中。(见图 2.2)。入栈工作完成以后,就是把下一个将要运
行的任务的当前状况从该任务的栈中重新装入 CPU 的寄存器,并开始下一个任务的运行。这个过
程叫做任务切换。任务切换过程增加了应用程序的额外负荷。CPU 的内部寄存器越多,额外负荷
就越重。做任务切换所需要的时间取决于 CPU 有多少寄存器要入栈。实时内核的性能不应该以
每秒钟能做多少次任务切换来评价。
七. 任务调度分析:
uCOS II 提供最简单的实时内核任务调度,算法简单,因此也只支持优先级抢占任务调度,
不支持时间片轮训调度算法,不支持优先级逆转。
uCOS II 总是运行进入就绪态任务中优先级最高的那一个。确定哪个任务优先级最高,下
面该哪个任务运行了的工作是由调度器(Scheduler)完成的。任务级的调度是由函数 OSSched()
完成的。中断级的调度是由另一个函数 OSIntExt()完成的,这个函数将在以后描述。
uCOS II 任务调度所花的时间是常数,与应用程序中建立的任务数无关。
在 uCOS 中曾经是先得到 OSTCBHighRdy 然后和 OSTCBCur 做比较。因为这个比较是两个指
针型变量的比较,在 8 位和一些 16 位微处理器中这种比较相对较慢。而在μC/OS-Ⅱ中是两个整
数的比较。并且,除非用户实际需要做任务切换,在查任务控制块优先级表 OSTCBPrioTbl[]时,
不需要用指针变量来查 OSTCBHighRdy。综合这两项改进,即用整数比较代替指针的比较和当需
要任务切换时再查表,使得 uCOS II 比 uCOS 在 8 位和一些 16 位微处理器上要更快一些。
为实现任务切换,OSTCBHighRdy 必须指向优先级最高的那个任务控制块 OS_TCB,这是通
过将以 OSPrioHighRdy 为下标的 OSTCBPrioTbl[]数组中的那个元素赋给 OSTCBHighRdy 来实现的
[L3.8(4)]。最后宏调用 OS_TASK_SW()来完成实际上的任务切换[L3.8(6)]。
任务切换很简单,由以下两步完成,将被挂起任务的微处理器寄存器推入堆栈,然后
将较高优先级的任务的寄存器值从栈中恢复到寄存器中。在 uCOS II 中,就绪任务的栈结构总是
看起来跟刚刚发生过中断一样,所有微处理器的寄存器都保存在栈中。换句话说,μC/OS-Ⅱ运
行就绪态的任务所要做的一切,只是恢复所有的 CPU 寄存器并运行中断返回指令。为了做任务切
换,运行 OS_TASK_SW(),人为模仿了一次中断。多数微处理器有软中断指令或者陷阱指令 TRAP
来实现上述操作。中断服务子程序或陷阱处理(Trap hardler),也称作事故处理(exception
handler),必须提供中断向量给汇编语言函数 OSCtxSw()。 OSCtxSw()除了需要 OS_TCBHighRdy
指向即将被挂起的任务,还需要让当前任务控制块 OSTCBCur 指向即将被挂起的任务。
OSSched ()的所有代码都属临界段代码。在寻找进入就绪态的优先级最高的任务过程
中,为防止中断服务子程序把一个或几个任务的就绪位置位,中断是被关掉的。为缩短切换时间,
OSSched()全部代码都可以用汇编语言写。为增加可读性,可移植性和将汇编语言代码最少化,
OSSched()是用 C 写的。
任务切换的相关函数:与 CPU 体系相关,汇编完成。
1. OSStartHighRdy() 执行优先级最高的任务
2. OSCtxSw()
完成任务的上下文切换
3. OSIntCtxSw()
中断后的上下文切换
4. OSTickISR()
中断服务程序启动
八. uCOS II 的初始化:
OSInit()建立空闲任务 idle task,这个任务总是处于就绪态的。空闲任务 OSTaskIdle
()的优先级总是设成最低。
这两个任务的任务控制块(OS_TCBs)是用双向链表链接在一起的。OSTCBList 指向这个
链表的起始处。当建立一个任务时,这个任务总是被放在这个链表的起始处。换句话说,OSTCBList
总是指向最后建立的那个任务。链的终点指向空字符 NULL(也就是零)。
因为这两个任务都处在就绪态,在就绪任务表 OSRdyTbl[]中的相应位是设为 1 的。还有,
因为这两个任务的相应位是在 OSRdyTbl[]的同一行上,即属同一组,故 OSRdyGrp 中只有 1 位是
设为 1 的。
uCOS II 还初始化了 4 个空数据结构缓冲区,如图 F3.8 所示。每个缓冲区都是单向链表,
允许 uCOS II 从缓冲区中迅速得到或释放一个缓冲区中的元素。控制块 OS_TCB 的数目也就自动
确定了。当然,包括足够的任务控制块分配给统计任务和空闲任务。
uCOS II 内核调度分析
vxWorks 内核调度分析:
1.只支持基于优先级的抢占式调度算法,不支持时间片轮训; 采用工作队列 workQword 的方
式调度;
2.64 个优先级,只能创建 64 个任务,用户只能创建 56 个任务; 根据用户指定,动态分配堆栈,
可以创建任意多个任务;
3.每个任务优先级都不相同。
4.不支持优先级逆转; 支持优先级逆转,TCB 保存两个优先级;
5.READY 队列通过内存映射表实现快速查询。效率非常高; 支持抢占与时间片轮训的任务调度
方式;
6.支持时钟节拍; 通过编译开关实现对多 cpu 体系结构的支持。
7.支持信号量,消息队列,事件控制块,事件标志组,消息邮箱任务通讯机制; 队列采用 FIFO
或者优先级的双向链表实现;
8.支持中断嵌套,中断嵌套层数可达 255 层,中断使用当前任务的堆栈保存上下文; 支持中断
嵌套,中断使用专用的堆栈保存上下文;