OSEK/VDX规范是欧洲汽车行业在20世纪90年代中期开发的、一个用于汽车电子的开放式系统及接口，现在已经成为分布式实时系统的一组工业标准。该标准应用于汽车电子控制系统软件的开发，能够解决相关产品的重复性开发、系统的扩展性及移植性等问题，具有良好的应用前景，对整个嵌入式软件开发行业具有借鉴意义。

1 OSEK实时系统任务调度概述

OSEK/VDX规范将任务分为基本任务和扩展任务，两者的根本区别是任务可能具有的状态数。基本任务具有运行态、就绪态、挂起态、中断4种状态，而扩展任务另外还有等待状态。任务自建立直至被删除，始终在各状态间转换，以实现任务的同步或异步执行。

在上述几种状态中，就绪态意味着任务已经准备好，可以运行，但由于该任务的优先级比正在运行的任务的优先级低，因此暂时不能运行。通过调度，就会将处于就绪态的具有最高优先级的任务启动，使其获得CPU的使用权进入运行态。运行态指任务获得CPU的使用权，正在执行中。处于运行状态的任务可以被更高优先级的任务占先而让出CPU的使用权，进入就绪态。另外，处于运行态的任务可以调用系统服务函数TerminateTask而进入挂起态。挂起态即任务驻留在内存中，但并不被内核所调度，被挂起的任务可以通过调用ActivateTask激活而进入就绪态。只有扩展任务才有等待状态，当运行中的扩展任务须等待某一事件或者某些事件发生时则进入等待状态。它可以通过系统服务函数GetEvent获得事件而进入就绪状态。中断优先级比所有任务的都高，因此其可以中断任何处于运行态的任务。其调度如图1所示。

图1 任务调度图

为了使OSEK操作系统便于理解、实现、升级，适应各种应用的软件和硬件环境，满足不同用户的需求，OSEK/VDX规范定义了4种一致类： BCC1(Basic Conformance Classes 1)，ECC1(Extended Conformance Classes 1)，BCC2(Basic Conformance Classes 2)以及ECC2(Extended Conformance Classes 2)。其中，BCC1、 BCC2实现基本任务，ECC1、ECC2实现扩展任务，BCC1和ECC1定义操作系统每个优先级上一个任务，BCC2和ECC2定义操作系统每个优先级上可以有多个任务。前者的任务调度简单，运行效率高，易实现；而后者是前者的超集，即ECC2满足BCC1、BCC2、ECC1。相对于其他一致类，ECC2调度复杂，会牺牲一些实时性。本文针对一致类ECC2对其调度算法进行优化实现。

2 调度算法优化实现

大多数实时系统采用基于优先级的占先式调度算法。该算法调度灵活，对任务集的限制小，适应范围广，但是其不能保证低优先级的任务得到运行，对于同一优先级有多个任务的情况更是无能为力。

2.1 同优先级任务间的调度优化

在分时操作系统中，各个任务之间没有优先级或重要程度之分。所有任务放入等待队列中，将CPU的执行时间分成时间片，为队首的任务分配一个时间片，开始执行。当一个时间片结束后，若任务还未执行完，任务被重新放入任务等待队列，让出CPU，等待下一次调度，这就是所谓的“时间片轮转调度法”。

对OSEK操作系统中同一优先级的多个任务之间的协调处理可借鉴时间片轮转调度法。在基于优先级调度方式的基础上，为每一个优先级增加FIFO队列。在一个时间片结束后，进行优先级占先式调度。若处于就绪态的最高优先级为当前任务的优先级，而且该优先级有多个任务处于就绪态，则将该任务放入FIFO队尾，为该优先级FIFO队首的任务分配一个时间片开始执行。否则，将该任务放回就绪表，取具有最高优先级任务的FIFO队首任务，开始运行。

2.2 不同优先级任务间的调度优化

对于不同优先级任务之间的调度，为了保证低优先级的任务能够得到运行，采用单处理器最优算法——最早时限优先（Early Deadline First）调度优化基于指定优先级的调度法，可简称“优先级时限优化调度法”。在最早时限优先调度法中，系统根据各任务距离其绝对时限的接近程度给任务分配优先级，任务的截止期越早，其优先级越高，反之亦然。

最早时限优先（EDF）调度法理论上有3个假设条件：

① 任务总可以被抢占，抢占的代价可以忽略不计；

② 只考虑任务的处理器需求，内存、I/O和其他资源请求忽略不计；

③ 任务间相互独立，不存在先后关系。

假设①表明任务可以在任何时间被抢占，并可以被恢复，此过程对CPU的负担可以忽略。由假设②可知，需忽略内存、I/O和其他资源的约束，防止问题变得复杂。假设③表明不存在优先约束，任务的释放和结束相互独立，互不影响。

基于上述假设，若一个实时系统中有n个任务，对应于每个任务的任务周期为ti，运行时间为Ri，时限为Di。忽略任务的切换带来的CPU消耗。该系统可以使用EDF算法调度的充分必要条件是：

对于非周期任务亦是如此，非周期任务大多是随机事件，其任务TI发生的时间间隔在区间[0,ti]上服从于参数为(λ,ti)的泊松分布，λ为单位时间内发生次数的期望，则非周期任务可以看作平均周期为1/λ的周期任务进行分析。同样，可以利用式（1）进行可调度性判断。

实际情况下，任务的调度对CPU所带来的负担不可忽略，假设任务调度消耗CPU时间为Δt，则式（1）变为：

可见，实时系统对调度算法的要求是： 在保证系统中所有任务在其时限内得到处理的前提下，尽可能地减小Δt。

实际系统总会有一些优先级较高，能够在时限内被处理完或者没有时限要求的任务。这种情况下，给这些任务运用EDF算法调度是没有必要的，徒增系统负担。因此，对于一个任务，首先尽可能通过单纯的优先级调度法调度执行，当其执行时间接近时限时，采取最早时限优先调度法进行调度，使任务能够在时限内得到处理。这样可大大减少任务超时的现象，使低优先级的任务也能得到处理，同时也尽可能地体现了高优先级先执行的原则。

该算法需要在调用调度程序时，首先更新每个任务的时限，而后检测是否有任务临近时限。逐一为每个任务进行时限更新和检测将耗费较长时间，系统中任务数越多，所需时间越长；而且调度程序不能被抢占，该段代码要以临界资源处理，需提前关中断。因此，任务调度时巨大的时间开销是实时系统所不能容忍的，否则将严重影响系统的响应。

采用差分时限链结构更新、检测每个任务的时限可以很方便地解决上述问题。差分时限链为链表结构，其中的每一个元素均为结构体变量。结构体成员由前向指针、后向指针和时间限3个变量组成。当一个任务建立后，根据其时间限，将其插入时限链的相应位置。在任务调度时，首先根据系统时钟计时，更新时限链。鉴于差分时限链的特殊结构，只需将时限链首元素的时限减去计时时钟。该方法节省了为每个任务逐一进行时间更新的巨大时间开销。然后检测时限链首元素对应的任务是否临近其时限。若是，则将该任务优先级相应提高，而后进行基于优先级的占先调度；否则，直接进行优先级调度。

图2（a）为系统中存在的时限链；图2（b）为时限为37的任务Tb建立后，其时限元素的插入过程；图2（c）为时限为18的任务Tc建立后，其时限元素的插入过程。

图2 差分时限链

在一次任务调度的开始，需用系统时钟对时限链更新。当满足下式时，表明时限链首任务接近时限，需将其优先级相应提高。

其中，t′i为更新后时限链首元素的时限；r1为任务执行所需时间;Δ为每次优先级更新检测及任务上下文切换时间；td为定义的判断系数，表示任务距时限的接近程度。

算法流程如图3所示。

图3 算法流程

当任务被抢占时，任务控制块中由执行时间变量记录任务执行时间，并更新其对应任务在时限链中的时限值，以备下一次检测。若任务在时限临近之前已被处理完，则在结束任务时将其时限块从时限链中断开。

3 有效性分析

下面对改进算法与EDF算法、基于指定优先级的占先调度法作对比分析。设存在表1所列的任务集S。

表1 任务集S

若采用单纯的指定优先级调度法调度表1中的任务，则当任务T1释放时，系统中只存在任务T1等待运行。因此，T1一旦释放即开始执行；当到达时刻4时，T2释放且优先级高于T1，T2开始运行；在时刻5，T3释放，但其优先级低于T2，T2继续执行，当T2执行完时，T3早已超出时限，如图4所示。

图4 基于指定优先级的任务调度示意图

若采用EDF调度法，对任务集S进行调度，任务T1运行到时刻4，T2释放，则根据此时距时限的接近程度为T1和T2分配优先级，由于D2<D1，所以T2优先级高于T1，T2开始运行。在时刻5，T3释放，由于D3<D2，所以T3优先级高于T2，T3获得CPU，开始运行，直至3运行结束，T2继续运行，最后运行T1。其中任务切换4次，每次切换时间包括查询就绪表和任务优先级更新时间、任务上下文切换时间，其中任务上下文切换时间对所有调度法是共有的，可省去不计。设查询就绪表和任务优先级更新时间为Δt。调度过程如图5所示。

图5 EDF任务调度示意图

设当检测到任务的时限临近时，将该任务提高两个优先级。下面介绍采用改进算法——优先级时限优化调度法对任务集S调度的过程。

任务T1运行到时刻4，T2释放，由于T2指定的优先级高于T1，且此时没有任务临近时限，则T2抢占T1开始执行。在时刻5，T3被释放，由于T3的指定优先级低于T2且没有任务临近时限，T2继续执行。当到达时刻10，任务T临近时限，将T3的优先级相应提高（设提高到9），高于T2的优先级，因此T3开始执行。在时刻15，T3结束运行，T2高于T1的优先级，开始运行。到时刻19，T2运行结束，T1继续运行。整个调度过程如图 6所示。

10

图6 改进后的任务调度示意图

可见，采用改进后的算法调度任务集S，避免了任务T3在基于指定优先级调度时的超时现象，使其在时限内得到处理。在图6所示的4次任务切换中，只有在时刻10有任务临近时限，需要对临近时限任务的优先级进行调整，设处理时间为Δp。在时刻4，(13+Δp）和（17+Δp)没有任务临近时限，因此均采用基于优先级的占先式调度方法进行任务切换，只进行了基本的任务上下文切换，相对于EDF算法，改进后系统节省时间为（4Δt-Δp）。

综上所述，优先级时限优化调度法能够根据系统繁忙程度对优先级较低、时限较短的一类任务进行优先级优化，相应提高其优先级别，使其尽可能及时地得到处理。使用EDF调度法时，每次任务调度过程中，任务优先级的调整都给CPU带来较大的负担，不可忽略，而且这种负担还会随着系统中任务的增多而急剧增大。该改进调度算法不仅具有EDF调度算法调度量大的优点，同时也考虑了任务的优先级和重要性，并尽可能地减轻给CPU带来的负担。

结语

在优先级时限优化调度法中，最大限度的节省了CPU的处理时间，大大缩短了系统的响应时间，使任务超时现象大幅度减少，由此进一步放宽了EDF理论的第一个假设条件，即承认任务被抢占的次数会加大处理器的总工作负载，尽可能地缩减了任务切换消耗的CPU处理时间，最终达到了改进的目的。