μCOS- Ⅱ内核任务调度的实现.doc

C/OS- 内核任务调度的实现赵二涛，杨春金武汉理工大学信息工程学院，武汉（430063）E-mail：摘 要：任务调度是一个实时操作系统的核心功能，关系到整个操作系统的性能。C /OS-内核采用占先式调度方式,保证最高优先级任务一旦进入就绪态,就能立刻得到CPU的使用权。本文结合C /OS-内核源代码深入研究就绪态中最高优先级查找算法和任务调度原理并给出实例加以分析。关键词：嵌入式实时操作系统，C /OS-，任务调度，就绪表，优先级中图分类号：TP316.21. 引言C /OS-是一个完整的，可移植、可固化、可剪裁的嵌入式实时操作系统。它采用占先式调度方式，即最高优先级的任务一旦就绪，总能立刻得到 CPU 的使用权，从而保证系统的实时性。在任务调度的过程中，C /OS-内核能快速、准确的从众多的就绪态任务中找出优先级最高的任务，减少系统的响应时间，保证系统的实时性。本文首先介绍与任务有关的概念和有关任务调度重要的域，接着详细分析 C /OS-的最高优先级查找算法和任务调度原理并结合实例加以说明。在分析最高优先级查找算法时首先分析将任务置于就绪态的过程，这样更易于理解内核的查找算法。2. C/OS- 的任务调度2.1 C /OS-的任务2.1.1 任务及任务状态任务，也称线程，是一个简单的应用程序。每个任务都被赋予一定的优先级，并有自己的一套CPU 寄存器和栈空间1。实时应用程序的设计过程是如何把问题分割成多个任务。每个任务都是一个无限的循环，都处在以下五种状态之一，即休眠态、就绪态、运行态、挂起态和被中断态。1）休眠态：相当于任务驻留在内存中，但并不能被多任务内核所调度；2）就绪态：意味着任务已经准备好，可以运行，但由于该任务的优先级比正在运行的任务的优先级低，还暂时不能运行；3）运行态：指任务掌握了CPU的使用权，正在运行中；4）挂起态：指任务在等待，等待某一事件的发生；5）被中断态：指发生中断时，CPU提供相应的中断服务，原来正在运行的任务暂不能运行，就进入了中断态。2.1.2 任务控制块（OS_TCB）任务控制块是一个和任务息息相关的重要的结构体。当任务的CPU使用权被剥夺时，C/OS-用它来保存该任务的状态。当任务重新获得CPU的使用权时，任务控制块能确保任务从被中断的那一点丝毫不差的继续执行2。每个任务都拥有自己独立的任务控制块，一旦任务建立，与之相对应的任务控制块就被赋值。任务控制块结构体在uCOS_II.H中定义，以下代码是节选OS_TCB中对本文分析相关的进构体成员。/ File : uCOS_II.H-1-typedef struct os_tcb OS_STK *OSTCBStkPtr;/* 当前任务的栈顶指针 */INT8UINT8UINT8UINT8UINT8UOSTCBPrio;OSTCBX;OSTCBY;OSTCBBitX;OSTCBBitY; OS_TCB;OSTCBStkPtr 是当前任务的栈顶指针，每个任务都有自己的堆栈和指向栈顶指针。在上下文切换时，对于优先级低的任务，要将任务当前状态保存于任务堆栈中（以便以后再次调度到此任务继续执行），然后 OSTCBStkPtr 指向栈顶；对于优先级高的任务，通过OSTCBStkPtr 找到任务的上次被切换时的状态，把保存的状态恢复到 CPU，这样任务就毫无差错的继续执行。OSTCBPrio 是任务的优先级号。OSTCBX，OSTCBBitX，OSTCBY，OSTCBBitY 用于加速任务进入就绪态的过程或等待事件发生状态的过程，这些值在任务建立时调用OS_TCBInit( )进行赋值。2.2 C /OS-最高优先级查找算法在 C /OS-中,每个就绪的任务都放在就绪表(ready list)中，内核通过就绪表找到就绪态最高优先级的任务让其占用 CPU，进入运行态3。C /OS-中最多运行的任务是 64 个，内核把任务优先级分组，八个为一组1，如图 1所示。任务优先级号中 Y 是所属组部分，X 是所在组部分，在就绪表中有 2 个变量 OSRdyGrp和 OSRdyTbl ，OSRdyGrp 表示所属组，每一位代表一个组内是否有进入就绪态的任务，OSRdyTbl 表示所在组，一组八个任务，即一位代表一个任务是否进入就绪态。当任务进入就绪态时，就绪表 OSRdyGrp 和 OSRdyTbl 相应位置 1。OSRdyGrp 和 OSRdyTbl 之间的关系见图 1，OSRdyGrp 的第 n 位对应 OSRdyTbl n ，即 OSRdyTbl n 中任何一位是 1时，OSRdyGrp 的第 n 位要置 1。OSRdyGrp任务优先级号7654321000YYYXXXOSRdyTbl X图 1 任务就绪表任务创建成功后被置于就绪态，这里就以任务被创建时为例来说明内核是如何把任务置-2-7156145134123112101908232221201918171631302928272625243947384637453644354334423341324055545352515049486362616059585756Y于就绪态。首先，建立任务，调用函数 OSTaskCreat( )或 OStaskCreatExt( )，OSTaskCreat( )和 OStaskCreatExt( )都将调用 OS_TCBInit( )来初始化任务控制块，函数 OS_TCBInit( )完成将任务优先级放就绪表中，使任务置于就绪态，函数 OS_TCBInit( )中有关将任务优先级放就绪表的部分如下所示：/ File : OS_CORE.CINT8U OS_TCBInit(INT8U prio,.)OS_TCB* ptcb;/* 初始化 OS_TCB 中 OSTCBX,OSTCBBitX, OSTCBY,OSTCBBitY */ptcb-OSTCBY= prio 3;ptcb-OSTCBBitY = OSMapTblptcb-OSTCBY;ptcb-OSTCBX = prio & 0x07;ptcb-OSTCBBitX = OSMapTblptcb-OSTCBX;OSRdyGrp|= ptcb-OSTCBBitY;/* 将任务加入就绪表 */OSRdyTblptcb-OSTCBY |= ptcb-OSTCBBitX;OS_TCBInit( )对 OSTCBX,OSTCBBitX, OSTCBY,OSTCBBitY 提前做了运算，节约任务调度时间。OSTCBX 和 OSTCBY 都要转换为相应位掩码，这个是通过 OSMapTbl 实现1，如图 2。内核通过按位或运算把 OSRdyGrp 和 OSRdyTbl 的相应位置 1，这样就完成了把任务置于就绪态的工作。图 2OSMapTbl 所有任务置于就绪态的工作都是通过上面的两个或运算完成。最高优先级任务置于就绪态和查找就绪态最高优先级任务是相反的过程，通过把任务置于就绪态的分析知道了就绪表中是如何放置任务优先级信息的，接下来就要把最高优先级的任务从就绪表中查找出来。任务的优先级越高，任务的优先级号越小，在 OSRdyGrp 和 OSRdyTbl 中置 1 的位越低，查找最高优先级的任务就是查出 OSRdyGrp 和 OSRdyTbl 和最低的置 1 位，然后再转换为优先级号，这样就完成了最高优先级的查找工作。内核调度任务时需要查找出最高优先级的任务4。内核调用 OS_Sched( )调度任务。OS_Sched( )找出就绪态最高优先级 OSPrioHighRdy，判断是否需要调度，如果需要则调度任务。函数 OS_Sched( )中有关查找最高优先级的部分如下：/ File : OS_CORE.C-3-下标位掩码000000001100000010200000100300001000400010000500100000601000000710000000voidOS_Sched (void)INT8U y;y = OSUnMapTblOSRdyGrp; /* 找出最高优先级 */OSPrioHighRdy = (INT8U)(y 3) + OSUnMapTblOSRdyTbly);为了找到就绪态的优先级最高的任务，内核并不是从 OSRdyTbl 0 开始扫描整个就绪任务表，只需查另外一张表即优先级判定表 OSUnMapTbl 1，如图 3 所示，这样设计为内核调度节约了时间。优先级判定表 OSUnMapTbl 中的值由 OSRdyGrp 和 OSRdyTbl 的最低置 1 位确定，举例说明。假设 OSRdyGrp0x6C(0b01101100)，OSRdyGrp 的最后一位置1 是第 2 位，OSUnMapTbl0x6C=2（图 3 中红色标注部分），反过来，知道 OSRdyGrp0x6C 就可以通过 OSUnMapTbl0x6C找到 2，这样通过 OSUnMapTbl 把 OSRdyGrp 和OSRdyTbl 最低置 1 位转换为对应优先级号中的 Y 和 X 部分，Y 乘以 8 加上 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/0x00 to 0x0F/0x10 to 0x1F/0x20 to 0x2F/0x30 to 0x3F/0x40 to 0x4F/0x50 to 0x5F/0x60 to 0x6F/0x70 to 0x7F/0x80 to 0x8F/0x90 to 0x9F/0xA0 to 0xAF/0xB0 to 0xBF/0xC0 to 0xCF/0xD0 to 0xDF/0xE0 to 0xEF/0xF0 to 0xFF图 3OSUnMapTbl 2.3 C /OS-任务调度原理C /OS-内核调用函数 OS_Sched( )来完成任务调度。函数 OS_Sched( )首先找出最高优先级任务的任务号，再与当前任务的任务号比较判断是否需要调度，如果两个任务号不相等则说明有更高优先级的任务进入就绪态需要进行任务调度，然后进入上下文切换完成任务调度，反之则说明当前任务具有最高优先级，退出 OS_Sched( )继续执行当前任务。有关内核源码如下：/ File : OS_CORE.Cvoid OS_Sched (void)INT8U y;-4-OS_ENTER_CRITICAL();if (OSIntNesting = 0) & (OSLockNesting = 0) y= OSUnMapTblOSRdyGrp;/* 查找最高优先级 */OSPrioHighRdy = (INT8U)(y 3) + OSUnMapTblOSRdyTbly);if (OSPrioHighRdy != OSPrioCur) /* 判断是否需要任务切换 */OSTCBHighRdy = OSTCBPrioTblOSPrioHighRdy;OSCtxSwCtr+;OS_TASK_SW();/* 进行上下文切换 */OS_EXIT_CRITICAL();首先 OS_Sched( )通过以上分析的最高优先级算法找出就绪最高优先级任务的任务号OSPrioHighRdy，判断是否需要调度，即就绪态最高优先级任务的任务号 OSPrioHighRdy 和当前任务的任务号 OSPrioCur 是否相等，如果相等说明当前任务具有最高的优先级，退出OS_Sched( )接着执行当前任务；如果不相等则说明更高优先级的任务进入就绪态，此时需要开始调度任务。通过就绪态最高优先级任务的任务号 OSPrioHighRdy 使 OSTCBHighRdy指向最高优先级任务的任务控制块，然后内核任务切换次数 OSCtxSwCtr 加 1，调用OS_TASK_SW()进行上下文切换，运行新的任务。上下文切换部分是跟 CPU 紧密相关的，不同的 CPU 这部分代码不同，但所做的事情都是一样的，就是切换任务运行新的任务。本文不针对某一款 CPU 详细分析源代码，只详述操作的步骤。首先，将当前任务的状态需要保存起来，即程序计数器指针 PC，状态寄存器和寄存器压入任务栈加以保存，然后把任务栈栈顶指针存入自己的 OS_TCB 中 OSTCBStkPtr字段，接下来开始切换任务。在切换任务时首先更新 OSPrioCur 和 OSTCBCur（OSPrioCur是内核运行任务的任务号，OSTCBCur 指向内核运行任务的任务控制块），即 OSPrioHighRdy和 OSTCBHighRdy 赋给 OSPrioCur 和 OSTCBCur，然后从 OSTCBCur 中得到任务堆栈指针OSTCBStkPtr，赋给 CPU 堆栈指针，从堆栈中取出最高优先级任务的状态即程序计数器指针 PC，状态寄存器和寄存器，把这些值分别恢复到处理器的 PC，状态寄存器和寄存器，然后就开始新任务的执行，如此便完成了任务的调度。3. 结论C/OS-II 作为一个嵌入式实时操作系统内核已被广泛应用于各种场合。本文引用 C/OS-内核源代码详细分析了内核调度的实现，只有对内核调度原理有深层次的了解后，才能在具体的工程应用中将 C/OS-II 内核移植到各种嵌入式处理器平台。参考文献1 Labrosse J J嵌入式实时操作系统C /OS- 第2版M邵贝贝,等译北京:北京航天航空大学出版社, 20032 周立功,等ARM微控制器基础与实践M北京:北京航空航天大