第 32 卷 第 12 期 Vol.32 № 12 ·软件技术与数据库· 计 算 机 工 程 Computer Engineering 文章编号：1000—3428(2006)12—0082—03 2006 年 6 月 June 2006 文献标识码：A 中图分类号：TN919.2 基于 OSEK/VDX 操作系统的任务管理机制设计 陈 卓 1，熊忠阳 1，李银国 2,3 (1. 重庆大学计算机学院，重庆 400044; 2. 重庆邮电学院自动化学院，重庆 400065; 3. 重庆长安汽车股份有限公司，重庆 400023) 摘 要：在汽车电子仿真控制平台开发领域，通常需要遵循 OSEK/VDX 规范集，而该规范集的核心之一便是 OSEK/VDX 操作系统规范。 要设计一个符合该规范的微实时操作系统，任务管理机制是保证其实时性的重要方面。该文提出一种符合 OSEK/VDX 操作系统规范的任 务管理机制，以满足 OSEK/VDX 操作系统的需要。 关键词：OSEK/VDX；实时操作系统；嵌入式系统 Design of Task Management Based on OSEK/VDX OS CHEN Zhuo1, XIONG Zhongyang1, LI Yinguo 2,3 (1. College of Computer, Chongqing University, Chongqing 400044; 2. College of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065; 3. Chongqing Changan Automobile Company Limited, Chongqing 400023) 【Abstract】In the automobile electronic control platform field, the design and implementation of control system commonly accord with the specification unit of OSEK/VDX, and the core specification of this unit is operating system specification. The mechanism of task management is very vital to design a RTOS which is accorded with this OS specification. This paper provides a scheme of task management, and it can meet the need of OSEK/VDX operating system. 【Key words】OSEK/VDX; Real time operating system (RTOS); Embedded system μc/OSII 中同一个优先级别的任务只能有一个，而这个限制恰 好不符合 OSEK/VDX 操作系统规范，该规范要求操作系统能 够处理同一优先级的多个任务，并对同一优先级的任务按 FIFO 的原则进行调度。所以，对μc/OSII 的任务管理数据结 构加以修改是实现新的调度机制的核心。这里借鉴了μc/OSII 的任务管理机制。 OSTcbPrioTbl[ ] os_tcb{} 1(1) [1] [2] [3] os_tcb{} 2(1) os_tcb{} 3(1) OSEK/VDX 规范集是由德国汽车工业界于 1993 年联合 推出的汽车电子的开放式系统与接口 OSEK(Open Systems and Corresponding Interfaces For Automotive Electronics)及由 法 国 汽 车 工 业 界 的 相 似 规 范 VDX (Vehicle Distributed eXecutive) 合并而成。制定该规范集的目的是从实时操作系 统(Real Time Operating System)、软件接口、通信和网络管理 等方面对汽车电子控制软件开发平台作了较为全面的定义与 规定。该规范为集中的操作系统子规范定义了一个小的、可 伸缩的实时操作系统，对于存储容量有限和功能专用的嵌入 式系统是非常理想的，从具有 8kB ROM 到具有 512kB ROM 的微处理器上均可使用这样的嵌入式操作系统，该操作系统 可管理实时任务，强化定时器的功能，共享资源等工作。本 文提出了一种满足 OSEK/VDX 操作系统规范的任务管理机 制，通过仿真实验，该机制能够较好地保证任务调度实时性。 1 任务管理机制 1.1 任务管理的数据结构 先分析任务管理数据结构。在操作系统中常以一个任务 描述符数据结构来表示一个任务。例如：在μc/OSII 操作系统 中以一个 OS_TCB{ }[3]来表示一个任务，在任务描述符里， 详细地定义了和一个任务相关的各种属性，如在 OS_TCB{ } 中 定 义 了 和 任 务 相 关 的 任 务 链 表 （ 以 O S T C B N e x t 和 OSTCBPrev 表示指向在任务链表中当前任务的后一个任务 和前一个任务）、代表任务占用的堆栈的 OSTCBStkSize、代 表任务优先级的 OSTCBPrio 等。其结构如图 1，在该图中省 略了 OS_TCB{ }结构和其它数据结构，如事件控制块、消息 等的连接关系。在μc/OSII 中为了方便用位图的方式来实现 O ( 1 ) 的 任 务 调 度 算 法 ， 用 一 个 O S _ T C B { } 结 构 数 OSTCBPrioTbl[ ]来管理多个任务的优先级别，也就是说在 —82— 图 1 μc/OSII 的任务链接关系 需 要 对 任 务 描 述 符 数 据 结 构 加 以 修 改 ， 可 以 考 虑 在 OS_TCB{ }数据结构中增加链接到同优先级别的任务的指 针，使同一优先级别的任务(如果有同优先级的任务)能够链 接成一个新的链表结构。这样，当在 OSTCBPrioTbl[]检索到 某一时候优先级最高的优先级时，能够依 FIFO 的原则使调 度器调度同一优先级下的多个任务，而位图中的 OSRdyTbl[] 数组表示优先级的置位，当同一优先级的任务全部被调度完 以后，才将该优先级的置位清零。这种新的任务管理机制对μ 基金项目：国家“863”计划基金资助项目(2004AA1Z2380) 作者简介：陈 卓(1980—) 男，硕士生，主研方向: 操作系统，嵌 入式系统，网络协议栈；熊忠阳、李银国，教授 收稿日期：2005-06-20 E-mail：rakechen2000@163.com 

c/OSII 基本的任务管理机制的扩充。修改后的任务管理数据 结构如图 2 所示(图中，表示当前的操作系统中只有等级为 1、 2、3 级别的任务，而在 1 和 2 优先级分别有 3 个和 2 个同优 先级别的任务)，新的任务管理数据结构，在 OS_TCB{ }中增 加了能够实现同优先级别任务链表的单向指针变量 struct os_tcb *OSTCBEqu。另外，当同优先级任务链表中位于最前 面的任务在被调度后，需要从链表中移出，但就绪位图中代 表该任务优先级的位置暂时不清除，这需要改进调度算法， 在 1.3 节和 1.4 节将就这一问题进行讨论。 OSTcbPrioTbl[ [1] [2] [3] ] OSTcbList os_tcb{} 1(1) os_tcb{} 1(2) os_tcb{} 1(3) NULL os_tcb{} 2(1) os_tcb{} 2(2) NULL os_tcb{} 3(1) 图 2 新的任务链接关系 1.2 就绪算法的实现 以下是任务就绪算法的实现，其中，对于新任务的初始 化以及根据优先级 prio 把 OSRdyGrp 和 OSRdyTbl[]置位的操 作已经省略。 Input: 进 入 就 绪 态 的 任 务 的 优 先 级 prio ， OSTCBPrioTbl[] ， OSTCBList（其中，OSTCBList 指向任务链表的表头，如果是不同 优先级的任务进入链表，都是利用 OSTCBList 指针加入到链表的表 头，而对于同优先的任务则不需要使用。） Output: void （该算法主要是使同优先级和不同优先级的任务能 加入不同的链表，不需要返回任何变量） Body: OS_TCB *ptcb; /*指向当前任务 */ OS_TCB *ntcb; /*指向某优先级下同优先级任务链表 的表头*/ /*判别同优先级别置位没有，如果没有置位，就是该优先级 的第一个任务*/ if (!OSTCBPrioTbl[prio]){ /*没有 prio 优先级的任务，直接置位*/ ptcb = OSTCBPrioTbl[prio] ; ptcb->OSTCBNext = OSTCBList; /*把任务加入到任务链表，利 用 OSTCBList 把任务加入到链表的表头*/ ptcb->OSTCBPrev=(OS_TCB)0; if (OSTCBList != (OS_TCB *)0) OSTCBList->OSTCBPrev = ptcb; OSTCBList = ptcb; OSRdyGrp |= ptcb->OSTCBBitY; /*根据已经在任务初始化的 时候设置好的*/ OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX; /*OSTCBBitX 和 OSTCBBitY 对就绪表置位*/ OSTaskCtr++; } /*已经有同优先级别的任务，找到同优先级别的 任务链表的末尾，因为是 FIFO，因此要加到链表尾 部*/ else{ ntcb = OSTCBPrioTbl[prio]; /*对 于 优 先 级 prio，先找到与该优先级相关的同优先级任务链表头 */ while(ntcb->OSTCBEqu != NULL) /*利用 OSTCBEqu 指针遍历该同优先级链表直到表尾*/ ntcb=ntcb->OSTCBEqu; /*在同优先级任务链表中插入该任务*/ ntcb->OSTCBEqu = ptcb; /*利用在 1.1 节中新增加的指针把当 前任务链接到同优先级链表*/ ptcb->OSTCBEqu = NULL; ptcb->OSTCBNext = NULL; ptcb->OSTCBPrev = NULL; /*这里只需要对当前任务 ptcb 没有 使用的指针初始化为 NULL*/ OSTaskCtr++; /*而不对就绪表进行置位，其原因在于对于同一 优先级 prio 在*/ } /*就绪表中已经被置位。*/ 1.3 任务脱离就绪队列算法 由于引入了同优先级的任务链表，当任务脱离开链表时， 不能简单地对就绪表清零，必须对同优先级是否存在多个任 务加以判断：(1)当满足条件在 prio 优先级下只有一个任务； (2)对于 OSRdyTbl[prio]所表示的 8 个优先级下均为空，才会 将 OSRdyGrp 的某位清零，即表示在该位所表示的一组优先 级下没有任务，而在同一优先级下有多个任务时，需要把指 向同优先级链表头的指针后移一个节点，指向同优先级的下 一个任务，以使当新一次调度的时候调度器也是以 O(1)的时 间复杂度选取下一个任务，如以下代码所述： /*根据μc/OSII 的两个就绪表变量计算出当前优先级最高的优先 级*/ y = OSUnMapTbl[OSRdyGrp]; prio = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]); if (!OSTCBPrioTbl[prio]->OSTCBEqu &&((OSRdyTbl [prio>>3] &= ~OSMapTbl[prio&0x07])==0)) OSRdyGrp &= ~OSMapTbl[prio>>3]; else{ if (OSTCBPrioTbl[prio]->OSTCBEqu != NULL){ /*同优先级下有多个任务的情况*/ ntcb = OSTCBPrioTbl[prio]->OSTCBEqu; OSTCBPrioTbl[prio] = ntcb; } 1.4 任务调度算法 任务调度器的效率对操作系统的实时性能有较大影响， 如 Linux 2.4.X 的进程调度算法的时间复杂度为 O(n)，其实时 性能不甚理想，而在 Linux 2.6.X 内核中引入了全新的 O(1) 调度算法，其实时性能有了显著的改善[4]。同样，对于主要 应用于汽车电子领域的 OSEK/VDX 操作系统作为一种实时 的操作系统，也需要有设计良好的任务调度机制，μc/OSII 的任务调度算法的时间复杂度 O(1)，在引入了同等优先级下 的多任务机制后，利用改进后的任务管理数据结构（图 2 所 示）仍然可以保证 O(1)的效率，新的调度算法的效率同时也 是衡量任务管理数据结构设计得是否合理的重要标准。 同优先级的第 1 次调度 同优先级的第 2 次调度 OSTcbPrioTbl[ ] os_tcb{} 1(1) os_tcb{} 1(2) os_tcb{} 1(3) NULL [1] [2] [3] os_tcb{} 2(1) os_tcb{} 2(2) NULL OSTcbList os_tcb{} 3(1) 图 3 新的任务调度描述 —83— 

如图 3，当优先级 1 下的任务 1(1)被调度后，OSTCBPrio Tbl[1]就会指向下一个同优先级的任务 1(2)，而当任务调度器 再次调度该优先级下的任务时，仍能在 O(1)找到该任务，这 样会调度图 3 中的编号为 1(2)的任务。由于该调度器利用了 比较复杂的任务管理数据结构，并没有出现通常的调度算法 会遍历任务链表的操作，也就没有循环语句，所以整个算法 的时间复杂度仍然保持在 O(1)，能够保证良好的实时性。具 体的算法实现如下： void OS_Sched (void) { INT8U y; cpu_sr = 0; OS_ENTER_CRITICAL(); if (OSIntNesting == 0 && OSLockNesting == 0) { y = OSUnMapTbl[OSRdyGrp]; OSPrioHighRdy=(INT8U)((y<<3)+ OSUnMapTbl[OSRdyTbl[y]]); if (OSPrioHighRdy != OSPrioCur) {/*优先级不同*/ OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy]; OSCtxSwCtr++; OS_TASK_SW(); } else{/*优先级相同*/ if (OSTCBPrioTbl[OSPrioHighRdy]->OSTCBId != OSPrioCur->OSTCBId){ OSTCBHighRdy=OSTCBPrioTbl[OSPrioHighRdy]; OSEQU[OSPrioHighRdy]++; OSCtxSwCtr++; OS_TASK_SW(); } } } } 2 实验与仿真 类型的实时内核，因此有这样的等价关系：任务响应时间 = 调度器寻找最高优先级任务所耗时间 + 任务切换时间。具 体的测试方法是设计一个测试任务，分别把该任务的就绪时 候的和被调度器调度时候的系统时钟 tick 值保存到定义好的 两个变量中，并利用操作系统的 HOOK 例程(在μc/OSII 和 OSEK/VDX 操作系统中都支持有“钩子”例程)读出这两个变 量后比较，经过 5 000 次任务调度测试后，统计如表 1。 表 1 调度测试统计 μc/OSII OSEK/VDX 系统 最大任 务响应 1.3ms 调度延时 <0.1ms 调度延时 <0.2ms 调度延时 < 0.5ms 99.841 311 % 99.908 121 % 99.932 217 % 5.9ms 98.645 313 % 98.952 861 % 99.109 973 % 3 结束语 本文提出了一种满足 OSEK/VDX 操作系统规范的任务 管理机制，如表 1 所示，改进后的调度机制，在取得对同优 先级多任务调度支持的同时牺牲了部分任务响应效率，增加 了部分延时。在多次测试中，最差的任务响应时间有较大差 别。但基本能够满足汽车电子对实时性的需要。 参考文献 1 OSEK/VDX Specifications [Z]. http://www.OSEK-VDX.org. 2 OSEK/VDX Operation System Specification 2.1[Z]. http://www. OSEK-VDX.org. 3 Labrosse J J. 邵贝贝译. 嵌入式实时操作系统 UC/OS-II(第 2 版)[M]. 北京: 北京航空航天大学出版社, 2003. 4 Love R. Linux Kernel Development[M]. Sams Publishing, 2004. 5 Abbott R, Garcia-Molina H. Scheduling Real-time Transactions[J]. ACM SIGMOD Record, 1988,17(1): 71-81. 6 Haritsa J R, Livny M, Carey M J. Earliest Deadline Scheduling for Real-time Database Systems[C]. Proceedings of the 12th IEEE Real-time Systems Symposium, Los Alamitos, CA, 1991: 232-234. 由于本文所讨论的是和任务管理相关（任务就绪，任务 调度等）的一系列机制，因此实验仿真的主要目的是测试改 进后的任务响应时间，实验中分别对在同一优先级下多个任 务的情况做了压力测试。由于 OSEK/VDX 操作系统是可剥夺 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 81 页) 答案的分布情况，而且还考察了 50 个查询的整体分布情况， 如图 4 所示，其中横轴和纵轴的定义和图 3 类似，只是这里 是 50 个查询相关文档个数叠加后的结果，其中系列 1 为基于 主题的方法答案在文档集合中的分布，系列 2 是参考下限中 答案的分布情况。从上面的实验可以看出，通过对主题的划 分可以使一个查询的相关文档集中在少数的几个文档集合 中，这样就为文档集合的选择提供了前提条件，也就是说如 果采用好的文档集合选择算法，只要选中那些包含相关文档 最多的文档集合来进行检索，就可以取得比较好的检索效果。 如何合理的组织文档集合，如何选择出最合适的集合进行检 索是非常重要的。本文通过文本聚类方法，把文档按照主题 的方式来划分，经过实验发现查询答案明显地汇聚在少数的 文档集合中，为进一步的文档集合选择创造了先决条件。通 过和人们经常采用的按照信息的出版时间、信息来源等划分 方式对比，该方法在检索的效果上也有了明显的提高。 参考文献 3000 2000 1000 0 系列 1 系列1 系列 2 系列2 1 11 21 31 41 51 61 71 81 91 图 4 50 个查询在不同的集合中的分布图 5 结论 在网络信息不断丰富的今天，分布式信息检索为人们迅 速查找到所需要的信息提供了一个很好的解决方案。在分布 式信息检索中，由于不是对全部的文档集合同时检索，因此 —84— 1 Callan J P, Lu Z, Croft W B. Searching Distributed Collections with Inference Networks[C]. Proceedings of the ACM SIGIR, 1995: 21-28. 2 Jay M, Ponte W, Croft B. A Language Modeling App roach to Information Retrieval[C]. Proceedings of the ACM SIGIR, 1998: 275-281. 3 Ogilvie P, Callan J P. Experiments Using the Lemur Toolkit[C]. Proceedings of the TREC’01, 2001: 103-108. 4 Xu Jinxi, Croft W B. Cluster-based Language Models for Distributed Information[C]. Proceedings of the 22th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1999: 254-261. 5 Callan J. Distributed Information Retrieva[M]. Advances Informational Retrieval. USA: Kluwer Academic Publishes, 2001. in