http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛实时操作系统任务调度策略的研究与设计王新政程小辉周华茂（桂林工学院电子与计算机系，广西桂林541004）中图分类号：TP316.2文献标识码：A摘要：实时操作系统的调度策略是影响系统实时性和稳定性的一个重要因素，通过对抢占调度和分时调度的研究，设计了一个可分级抢占和分时调度的实时操作系统。用抢占调度方式来保证系统的实时性，用分时调度来减少进程饥饿现象的发生，提高系统的稳定性，更易于使用。关键字：实时操作系统，时间片轮转，优先级检索，嵌入式操作系统1．引言嵌入式系统是一种面向应用的系统，与传统计算机系统相比，它更注重系统的体积、功耗、实时性、可靠性等问题，而传统的采用前/后台方式的系统实时性不高，其响应时间在任务级，最坏的情况下取决于整个循环的执行时间[1]，如果循环修改了，则其响应时间也会随之变化。如今嵌入式系统做得越来越复杂，要控制的外设和运行的应用程序也越来越多，甚至还需要与各类网络互联，传统设计模式变得越来越不适应，用操作系统来进行资源的调度和管理就显得十分必要，但嵌入式系统与广泛应用的PC机比起来具有的硬件资源相对要少得多，因此不可能也没必要把操作系统做得很大，基于此，专家们提出了微内核结构技术，即只把那些最本质、最基本的功能留在内核中，而其它的操作系统功能以单独的服务器进程形式存在[2]。操作系统的性能很大程度上取决于内核的任务调度机制[3]，实时操作系统内核可分为：非抢占式内核和抢占式内核两种，这两种内核都由中断服务程序来处理异步事件。在非抢占式内核中，中断服务程序可以使一个高优先级的任务就绪，但中断完成后仍返回到被中断的任务，直到其主动放弃CPU的使用权方可调度高优先级的就绪任务，这种系统的性能比前/后台方式的要好，但实时性还是不高，因为高优先级的任务就绪了也不能马上得到执行，见图1。在可抢占型内核中，中断服务程序退出时会有两种情况，如果中断服务程序使高优先级任务就绪，则内核挂起被中断了的低优先级任务，使高优先级的任务执行；如果中断服务程序没有使高优级任务就绪，则中断后仍返回被中断了的任务[4]，见图2。任务在运行过程中也可以动态的创建任务，如果优先级比当前任务的要高也要抢占当前任务。图1非抢占式内核任务调度图2可抢占内核任务调度2．任务队列的快速检索在抢占式系统中如何快速的找到优先级最高的就绪任务是系统所要解决的一个重要问题，当就绪任务里有比当前任务优先级高的任务时，当前任务就要被高优先级的就绪任务抢占，很多主流的操作系统（如Linux）是通过遍历就绪任务队列来检索高优先级的任务的，其时间复杂度为O(N)，当N增大时遍历的时间也会增大[5]，影响实时性。查表法[6]是美国嵌入式系统专家JeanJ.Labrosse在其设计的uc/osII操作系统中使用的一种检索最高优先级就绪任务的方法。用查表法来寻找优先级最高的任务，简单、快速并且与当前系统的任务数1http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛无关，具有时间可确定性。在大多数的基于优先级的抢占式多任务实时操作系统中，采用的都是固定优先级方式，每个任务在创建的时候由系统的设计者赋予一个明确的与其它任务不同的优先级，用任务的优先级即可唯一的标志任务，任务和优先级之间是一一对应的关系，而在本设计中的一个优先级对应着一个任务队列，不同的任务可以具有相同的优先级，但必需具有唯一的任务ID号。查表法的关键是要建立查找表，查找表可以看作一个预先设计好的常量数组SearchTable[]，数组有256个元素从SearchTable[0]到SearchTable[255]，各元素的值通过计算得到，这样每次可对一个8位数进行查表，确定最高优先级任务所在位置。SearchTable[]表的设计方法为首先把数组下标（0~255）用8位二进制来表示（最低位为第0位，最高位为第7位），再看为1的最低位在第几位，然后把其值填入到数组下标所指定的元素中。例如SearchTable[86]，其下标为86，转换成二进制为01010110b，为1的最低位在第1位，所以把1填到下标为86的元素中。系统最多可支持64个优先级，把这64个优先级分为8组，每组8个，通过两次查表即可当前就绪表中的最高优先级。用ReadyGroup中的位来指示任务的优先级组，ReadyGroup的定义为INT8UReadyGroup（INT8U为无符号的8位整数）。数组ReadyPrioTbl[]来指示优先级，R