UCOS之任务调度机制

一． 内核概述：

    多任务系统中，内核负责管理各个任务，或者说为每个任务分配CPU时间，并且负责任务之间的通讯。内核提供的基本服务是任务切换。之所以使用实时内核可以大大简化应用系统的设计，是因为实时内核允许将应用分成若干个任务，由实时内核来管理它们。内核本身也增加了应用程序的额外负荷，代码空间增加ROM的用量，内核本身的数据结构增加了RAM的用量。但更主要的是，每个任务要有自己的栈空间，这一块吃起内存来是相当厉害的。内核本身对CPU的占用时间一般在 2到5个百分点之间。uCOS II有一个精巧的内核调度算法,实时内核精小，执行效率高，算法巧妙,代码空间很少。

二． uCOS II内核调度特点：

1. 只支持基于优先级的抢占式调度算法，不支持时间片轮训；
2. 64个优先级,只能创建64个任务,用户只能创建56个任务；
3. 每个任务优先级都不相同。
4. 不支持优先级逆转；
5. READY队列通过内存映射表实现快速查询。效率非常高；
6. 支持时钟节拍；
7. 支持信号量，消息队列，事件控制块，事件标志组，消息邮箱任务通讯机制；
8. 支持中断嵌套，中断嵌套层数可达255层，中断使用当前任务的堆栈保存上下文；
9. 每个任务有自己的堆栈，堆栈大小用户自己设定；
10. 支持动态修改任务优先级；
11. 任务TCB为静态数组，建立任务只是从中获得一个TCB，不用动态分配，释放内存；
12. 任务堆栈为用户静态或者动态创建，在任务创建外完成，任务创建本身不进行动态内存分配；
13. 任务的总个数（OS_MAX_TASKS）由用户决定；
14. 0优先级最高，63优先级最低；
15. 有一个优先级最低的空闲任务,在没有用户任务运行的时候运行.

三． 任务控制块 OS_TCB描述：

    uCOS II的TCB数据结构简单，内容容易理解，保存最基本的任务信息，同时还支持裁减来减小内存消耗，TCB是事先根据用户配置，静态分配内存的结构数组，通过优先级序号进行添加，查找，删除等功能。减少动态内存分配和释放。因为依靠优先级进行TCB分配，每个任务必须有自己的优先级，不能和其他任务具有相同的优先级。

typedef struct os_tcb

{

    OS_STK        *OSTCBStkPtr;

#if OS_TASK_CREATE_EXT_EN

    void          *OSTCBExtPtr;

    OS_STK        *OSTCBStkBottom;

    INT32U         OSTCBStkSize;

    INT16U         OSTCBOpt;

    INT16U         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         OSTCBDly;

    INT8U          OSTCBStat;

    INT8U          OSTCBPrio;

    INT8U          OSTCBX;

    INT8U          OSTCBY;

    INT8U          OSTCBBitX;

    INT8U          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位，每位代表一个优先级组；OSRdyTbl[]占8个字节，共64位，每位代表一个优先级）在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，

    以些类推。。。。。

任务就绪的掩码表：
       INT8U const OSMapTbl[]   = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};//定位优先级所用

任务优先级的低三位用于确定任务在总就绪表OSRdyTbl[]中的所在位。接下去的[5：3]三位用于确定是在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.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];   //先根据高3位[5：3]找到所在的组
OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07]; //再由低3位把该组的具体某一位置1

 

如果一个任务被删除了，则用程序清单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这张表，返回的字节就是该组任务中就绪态任务中优先级最高的那个任务所在的位置（即该字节的中最低位1的所在位）。这个返回值在0到7之间。确定进入就绪态的优先级最高的任务是用以下代码完成的。

找出进入就绪态的优先级最高的任务 

y    = OSUnMapTbl[OSRdyGrp];

x    = OSUnMapTbl[OSRdyTbl[y]];

prio = (y << 3) + x;

  优先级查询表：
INT8U const OSUnMapTbl[] = {
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};//定位最高优先级用（即查找一个字节的最低位1所在的位置）

     例如，如果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任务调度所花的时间是常数，与应用程序中建立的任务数无关

    为实现任务切换，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的数目也就自动确定了。当然，包括足够的任务控制块分配给统计任务和空闲任务。

附：调度机制

进程调度是计算机的灵魂。在实时系统里，要使重要紧急的进程一经唤醒使被优先调度运行，系统就必须有基于进程优先级的实时调度策略。通过深入考察和对比μC／OS-II对实时调度算法的实现，可以深刻理解实时操作系统。
　    如果说CPU是计算机系统的心脏，那么进程调度就是计算机系统的灵魂，因为它决定了如何使用CPU。例如，Linux是一个多任务操作系统，它的理想状况是保持CPU有效运行。如果某个正在运行的进程转入等待系统资源，操作系统就调度其他进程运行，从而保证CPU的最大利用率。如何使系统能够保证较短的响应时间和较高的吞吐量，使得多个进程竞争CPU时保持公平、高效，是通用操作系统所追求的目标。但对于实时操作系统而言，它的调度算法是基于POSIX规定的基于事件驱动优先级的调度算法，为了及时响应高优先级进程，它宁愿牺牲整体效率。   　     调度的实现可以分为2步来完成：
  　      ①何时启动调度，即解决调度启动时机的问题；
    　    ②怎么调度，按优先级调度就是要找到系统当前优先级最高的进程，然后进行上下文切换。    　 

   在实时系统中，只有当就绪进程集合发生变动时才有调度的需要，而就绪进程集合的变动只可能发生在几种情况下：
  　      ①运行中的进程受阻或自动放弃CPU；
   　     ②系统中新建了进程；
   　     ③运行中的进程“自杀”或“被杀”；
   　     ④运行中的进程唤醒了某个线程；
    　    ⑤中断服务子程序结束时唤醒了其他进程。   　  

   理想情况下，实时系统在有高优先级的进程转入就绪态时，就应该立即启动调度程序，响应高优先级进程。但实际上却存在着不可调度的时隙，称为不可调度窗口：
  　      ①正在进行进程切换，不能进行调度；
  　      ②中断响应期间，不能进行调度；
 　       ③进入临界区，不能进行调度；
  　      ④DMA期间CPU已被挂起，不可能进行调度。 在实时系统里，必须努力缩小不可调度窗口。在调度启动的时机上，所有的实时操作系统基本一致。 

http://tianwaike1.blog.163.com/blog/static/351366792009911101830325/