uc/OS 任务调度机制

                   uc/OS 任务调度机制
 
内核的核心任务是任务调度机制，为了对uC/OS进行分析，我们从任务调度开始。在uC/OS中，一个任务通常是一个无限循环，程序具有如下的结构，后面我将解释为什么会有这种结构。从下面的结构可以看出一个任务就像其他C函数一样；而且，既然任务是一个无限循环，我们可以想象到它一定不会返回任何的数据，所以返回类型应该定义为void。

程序：

------------------------------------------------------------
void mytask(void *pdata)
{
for (;;) {
do something;
waiting;
do something;
}
}
uC/OS可以管理64个任务，但目前的版本系统占用了两个任务，还保留了其他六个任务，故用户可以使用56个任务。每个任务必须赋予一定的优先级，优先级数越高，优先级越低，所以0级优先级的任务有最高的优先级。通过在OS_CFG.H文件中定义宏OS_LOWEST_PRIO可以决定系统的任务的个数。系统目前占用的两个任务为空闲任务IDLE TASK和统计任务STAT TASK。当没有其他任务进入就绪状态时空闲任务投入运行，空闲任务什么也不做，只是简单的将计数器加1，这个计数器可以用来统计CPU的利用率。

uC/OS下每个任务可以有如下五种状态。

休眠态(dormant)：指任务驻留在程序空间中，还没有交给内核管理。把任务交给内核是通过调用OSTaskCreate( )或OSTaskCreatExt( )实现的。

就绪(Ready)：当任务一旦建立，这个任务就处于就绪态准备运行。任务可以动态的被另一个程序建立，也可以在系统运行开始之前建立。通过调用OSTaskDel( )使任务返回到休眠态。就绪态的任务都放在就绪列表中。在任务调度时，指针OSTCBHighRdy指向优先级最高的就绪任务，也就是立刻就要运行的任务。
运行(Running)：准备就绪的最高优先级的任务获得CPU的控制权，从而处于运行态。指针OSTCBCur指向正在运行的任务。

等待或挂起(Pending)：正在运行的任务由于调用延时函数OSTimeDly( )或等待事件信号量的来临而将自身挂起，因而处于等待或挂起态。因为等待某事件而被挂起的任务注册在该事件的等待列表中。

中断态(Interrupt)：正在运行的任务可以被中断，除非是该任务将中断关闭。被中断的任务进入中断服务程序(ISR)。如果中断服务程序使一个更高优先级的任务准备就绪，这中断服务程序结束后，则更高优先级的任务开始运行程序。

任务被创建后，其状态用8位字节变量OSTCBStat表示，目前只用了低四位如下所示(图4.1)。如果某位置为1，表示任务正在等待该位表示的事件；可以复合使用这些标志，表示任务在同时等待多个事件的发生；如果所有位均为0，表示任务处于就绪状态，一旦符合条件(优先级最高)，即可投入运行。

 

 

 

uC/OS下任务的状态转移如下(图4.2)所示。每个任务在被创建的时候，一个称为任务控制块(task control blocks)的数据结构将被赋值。

 

内核在初始化的时候将所有可用的任务控制块通过指针*OSTCBNext和*OSTCBPrev连成一个可用任务双向链表，并将指针OSTCBFreeList指向第一个TCB。以后每当一个任务创建时，就根据OSTCBFreeList从可用任务双向链表获取一个TCB同时将OSTCBFreeList指向下一个TCB，如图4.3所示。

 

 

 

uC/OS是剥夺型实时多任务内核，优先级最高的任务一旦准备就绪，则拥有CPU的所有权开始投入运行。uC/OS中不支持时间片轮转法，每个任务的优先级要求不一样且是唯一的，所以任务调度的工作就是：查找准备就绪的最高优先级的任务并进行上下文切换。函数OSSched(void)进行任务调度。其程序结构如下(程序4.2)。
如果某个任务在某段代码的执行期间不能被其他任务所抢占，可以调用OSSchedlock( )函数来给调度器上锁以禁止调度，之后再调用OSSchedUnlock( )开锁允许调度。例如低优先级的任务要发给其他任务邮箱、消息队列时，用户不希望高优先级的任务还没有得到消息就取得了CPU的使用权，就可以使用OSSchedlock( )。

程序4.2 任务调度原理
------------------------------------------------------------

 

 

 

如前所述，uC/OS是通过查表法找到准备就绪的优先级最高的任务，下面将说明查表的过程。为了实现就绪任务的快速查找，uC/OS采用了一种奇特的方式。既然uC/OS中每一个任务的优先级是唯一的，不存在相同优先级的两个任务，所以可以根据优先级来唯一的确定任务。uC/OS支持64个任务，也就是由64个优先级0-63,二进制中可以用6位来表示，然后根据高三位将64个任务分为8个准备就绪表数组OSRdyTbl[7]，每组又根据低3位包含8个任务，若每组有任务处于就绪态，则相应的比特置1；假设任务3和任务5处于就绪态，则OSRdyTbl[0]=0x28；任务17和任务20处于就绪态，则OSRdyTbl[2]=0x12。 uC/OS还定义了一个8比特字节变量，OSRdyGrp准备就绪组。OSRdyGrp中的每一位表示8组任务中每一组是否有准备就绪的任务，其相互关系见下（图4.4）。

图4.4 uC/OS任务查表原理

假设优先级为12的任务进入就绪状态，12=1 100b,则OSRdyTbl[1]的第4位置1，且OSRdyGrp的第1位置1，相应的数学表达式为:

OSRdyGrp |=0x02；
OSRdyTbl[1] |=0x10;

而优先级为21的任务就绪21=10 101b，则OSRdyTbl[2]的第5位置1，且OSRdyGrp的第2位置1,相应的数学表达式为：

OSRdyGrp |=0x04；
OSRdyTbl[2] |=0x20;

从上面的计算我们可以得到:若第n位置1，则应该与2n 相或。uC/OS中，把2n的n=0-7的8个值 先计算好存在数组OSMapTbl[7]中,也就是：
OSMapTbl[0] =20=0x1;
OSMapTbl[1] =21=0x2;

OSMapTbl[7] =27=0x80;

利用OSMapTbl，通过任务的识别号-优先级prio来设置任务在就绪组和就绪表数组中相应位置的数学式为：
OSRdyGrp |=OSMapTbl[prio>>3];
OSRdyTbl[prio>>3] |=OSMapTbl[prio & 0x07];
因为64个优先级可用6位来表示，所以高三位可用prio>>3得到，低三位通过prio & 0x07获得。但我一直存在这样的疑问：2n运算只需通过简单的移位即可获得，通过查表来获得能够真正节约时间吗？

下面我们说明如何利用就绪组和就绪表数组来获得优先级最高的就绪任务识别号即优先级数。前面我们把优先级数分解为高三位和低三位，从而决定任务在就绪组和就绪表数组中相应位置，这里我们先想办法先分别求出高三位和低三位即可。假设OSRdyGrp值为0x24=100 100b,表明OSRdyTbl[2]和OSRdyTbl[5]存在准备就绪的任务，根据图4.4，显然OSRdyTbl[2]中的任务优先级比OSRdyTbl[5]要高，所以最高优先级就绪任务的高3位一定是2；再通过OSRdyTbl[2]的值来确定低3位，假设为0x12=010 010b,表明第1个和第4个任务处于就绪态，优先级高的任务是第1个，所以最高优先级就绪任务的低3位一定是1；最后可以得到最高优先级的就绪任务的优先级为010 010b=18。

上面我们通过观察法利用OSRdyGrp和OSRdyTbl值求出最高优先级的就绪任务的优先级，接下来推导一般方法。推导的关键在于这个事实：高优先级有着最小的优先级号，所以不管对于求高3位还是低3位，都是将已知的数展开成8位的二进制数，最低为1的位数即为相应的欲获得的数,即：

1=00000001b->0 (最低为1的位是第0位),
2=00000010b->1 (最低为1的位是第1位),
3=00000011b->0 (最低为1的位是第1位),

可以用算法这样实现：令n=0,将已知数与2n相与，若不为0，则n即为所求，否则n++,进行下一个循环。程序结构如下(程序4.3)：

程序4.3 查找最高优先级的算法
---------------------------------------------------------------------------
n=0;
do {
if (OSRdyGrp & 2n)
break;
n++;
} while(n<8)
利用上述程序，

(1 & 20)=1, 最低为1的位是第0位;
(2 & 21)=1, 最低为1的位是第1位;
(3 & 20)=1, 最低为1的位是第0位;

显然，用程序实现不但复杂，更重要的是执行时间是不确定的，因为有时只需一个循环即可，而有时需要8个循环，不符合实时系统的确定性原则。所以在uC/OS中，仍然采用查表的方法实现，这个表为数组OSUnMapTbl[255],利用该表，计算最高优先级任务的优先级的算法如下：

程序4.4 计算最高优先级任务的优先级的算法
------------------------------------------------------------
High3 =OSUnMapTbl[OSRdyGrp];
Low3 =OSUnMapTbl[OSRdyTbl][High3]];
Prio =(Hign3<<3)+Low3;
至此，我们已经把uC/OS任务调度机制较为详细分析了一遍；