uC/OS-II学习笔记—任务就绪表和就绪组

ID:51773 · 发表于 2013-7-14 16:08

内核在进行任务调度时，必须知道哪个任务在运行、哪个任务是就绪的最高优先级的任务。实时任务调度的关键在于速度，要求无论系统的运行情况如何，调度的时间是确定的，不能把时间都用在调度上。因此就需要设计高效的多任务调度方法。查找高优先级的任务，与正在运行的任务的优先级进行比较以确定是否进行任务切换是内核在每个时钟中断都需要做的事情。为满足这样的需要，uC/OS-II的开发者采用了就绪表和就绪组这样的数据结构，围绕它们又定义了两张查找表。
就绪组和就绪表的相关定义如下所示：

已经知道，OS_LOWEST_PRIO是最低优先级任务的优先级，因为uC/OS-II最多可以同时有64个就绪任务，而优先级是从0开始，因此最大可以设置为63.如果设置为63，则OS_RDY_TBL_SIZE就为8，那么OSRdyTbl最多有8个元素。
OSRdyGrp是就绪组，类型是INT8U，INT8U等同于无符号的字符型，也就是8位无符号数。OSRdyTbl就是每个元素都为8位无符号数的数组，数组中元素的个数是OS_RDY_TBL_SIZE。
如果把OSRdyTbl直接定义为INT8U OSRdyTbl[8]是不是也可以呢？答案是肯定的，但是如果任务数没有那么多，没有必要把OS_LOWEST_PRIO设置为63，假设是3，那么只要定义为INT8U OSRdy[1]就可以了，这样做可以节约内存空间。
uC/OS-II规定，每个就绪的任务在就绪表中的对应位置为1，反之为0。只要就绪表OSRdyTbl[n]所有的位都为0，OSRdyGrp的第n位才为0。
在操作系统还没有创建任务的时候，就绪表和就绪组如下图所示：

在上图中，因为没有就绪任务，所以就绪表中所有位都是0，即从OSRdyTbl[0]到OSRdyTbl[7]都是0，所以OSRdyGrp也是0。当创建了空闲任务和统计任务后，就绪表和就绪组如下图所示：

在上图中，创建了优先级最小的两个任务——空闲任务和统计任务。空闲任务的优先级是63，空闲任务就绪，那么OSRdyTbl[7]的最高位为1.统计任务的优先级是62，统计任务也就绪，那么OSRdyTbl[7]的次高位为1。OSRdyTbl[7]不是0，所以OSRdyGrp的第7位为1。如果我们再创建一个优先级是11的任务，创建后就绪表和就绪组就应该如下图所示。

通过上面3个任务的创建过程可以看出，如果有新的就绪任务，就需要将就绪表中与该任务优先级对应的项置1.如果该就绪任务在第n行，就将OSRdyGrp的第n位置1。
于是，如果有一个优先级为prio的任务就绪，应执行如下的代码：

在任务调度的时候，要查找优先级最高的任务。采用分组管理的方法就是为了使查找的时候时间是确定的，速度是最快的。如果不采用分组管理的方法，那么就要从OSRdyTbl[0]开始查找，如果一直找不到，就要查找到OSRdyTbl[7]，所以时间比较长，且不能确定。采用就绪组后，查找程序代码如下所示：

可见，获取就绪任务中的最高优先级的方法是以OSRdyGrp的值为依据查优先级判定表OSUnMapTbl获得最高优先级任务的高5位，然后将其赋值给y。然后，以OSRdyTbl[y]的值再一次查表，得到低3位，再将高5位左移3位与低3位相或，得到优先级。这样的查找方法是迅速的，查找时间也是恒定的。但是这样做的依据是什么呢？
如果我们要找到优先级最高的任务，那么应该先分析OSRdyGrp。假设OSRdyGrp中最低的为1的位为y号位，决定了我们在就绪表中的哪一行来查找优先级最高的任务。也就是说，先查找到就绪表中的行号。有了行号，接下来再找是哪一列，这样就知道最低优先级的任务是多少了。OSUnMapTbl这张表就是为了达到这样的目的而设计的！
OSUnMapTbl的定义如下所示：

首先根据OSRdyGrp查找优先级判定表，原理是根据优先级立即查找到OSRdyTbl[]中对应元素，即OSRdyGrp中从低位到高位第一个为1的位的位置（从0到7）。例如，如果OSRdyGrp为11001000B，那么最低的为1的位是3号位，于是查表得到3，就是说最高优先级在OSRdyTbl[3]中。如果是01001000B，同样查找到3，这就是程序中为什么有那么多列是相同的原因。
假设OSRdyGrp为0，那么没有任务就绪，但是在多任务启动后没有任务就绪是不可能的，因为至少空闲任务是就绪的，所以我们添一个0占一个位置。假设OSRdyGrp的最低位为1，那么就绪表中的0行有任务就绪，也就是优先级为0~7的任务有就绪的，我们应该去查看OSRdyTbl[0]中是哪一位为1了。OSRdyGrp的最低位为1的情况有很多，但是所有这些情况下查找得到的值都是0.
优先级判定表OSUnMapTbl就是根据一个8位的无符号数的数值来确定最低的为1的位的位置的，OSUnMapTbl[n]就是n的最低的为1的位的位号。
y=OSUnMapTbl[OSRdyGrp]是将就绪组中最低为1的位的位号取出来放在y中，是就绪表中的行号。OSRdyTbl[y]是取得就绪表中对应行的值，OSUnMapTbl[OSRdyTbl[y]]是该行中最低的为1的位的位号，也就是就绪表中的列号。然后(y<<3)是将y左移3位，再加上行号，正好就是最高优先级的任务的优先级。
查找最高优先级的任务也是用了两条语句，时间快且确定。
最后举例验证一下，就绪表和就绪组如下所示：

由图可知，OSRdyGrp为10000010B(十进制130)，应对应OSRdyTbl[1]，而OSRdyTbl[1]为00001000，故最高优先级任务为8+3=11。用程序代码计算，OSUnMapTbl[130]为1，y值为1，表示对应1号行，OSRdyTbl[1]的值为00001000B，OSUnMapTbl[OSRdyTbl[y]]的值为3，于是OSPrioHighRdy=1<<8+3=11，验证成功。

帐号		自动登录	找回密码
密码			立即注册

uC/OS-II学习笔记—任务就绪表和就绪组

浏览过的版块