嵌入式OSEK/VDX操作系统的优化与应用*

2016076

嵌入式OSEK/VDX操作系统的优化与应用*

李 静1,邢国成1,张家旭1,2

(1.吉林大学，汽车仿真与控制国家重点实验室，长春 130022; 2.中国第一汽车集团技术中心，长春 130011)

[摘要] 为了解决嵌入式OSEK/VDX操作系统在高负载、抢占模式下低优先级任务长时间得不到执行的问题，利用 OSEK/VDX标准中的报警机制提出了一种优化的最小空闲时间优先调度算法来完善嵌入式OSEK/VDX操作系统的调度策略。给出了该算法的具体实现方案，在理论上分析了该算法的可行性，最后将该算法应用于汽车简单和复杂的电控系统。测试结果表明：在高负载、抢占模式下，使用该算法能够明显改善低优先级任务的执行。

关键词：OSEK/VDX；最小空闲时间优先；调度算法；优化；应用

前言

针对复杂的汽车电子控制系统，欧洲汽车行业开发了OSEK/VDX标准[1]。文献[2]中对OSEK/VDX标准进行了详细解析。

基于OSEK/VDX标准的嵌入式实时操作系统在发动机管理系统(engine management system, EMS)、电子稳定性程序(electronic stability program，ESP)等汽车电子控制系统中有着广泛的应用[3-4]。但是在实际应用中，当操作系统工作在抢占模式而且系统负载较大时，低优先级任务可能长时间得不到执行，任务的执行周期可能较大程度地偏离用户的期望值[5-6]。

针对上述问题，文献[5]中提出了一种基于时间片轮转调度算法的补偿调度策略。文献[6]中用抢占式的最早截止期优先(earliest deadline first，EDF)调度算法对嵌入式OSEK/VDX操作系统进行了优化，实现了优先级的动态分配，使系统的实时性得到提高。EDF算法可以实现最优调度，但是在实际应用中抢占式EDF调度算法的抢占次数多，额外开销大，一旦系统过载EDF算法的调度能力将急剧下降[7-8]。

最小空闲时间优先(least slack first，LSF)调度算法是一种典型的动态优先级实时调度算法，同样能实现最优调度[9-10]。本文中在LSF算法的基础上，利用嵌入式OSEK/VDX操作系统的报警机制实现了A-LSF(alarm-based least slack first，A-LSF)算法，在理论上分析了算法的合理性，并且给出了算法的应用方案，进行了实验测试，结果表明：A-LSF算法能够有效解决低优先级任务长时间得不到执行的问题，而且应用非常灵活。

1 LSF算法的优化

1.1 LSF算法简介

LSF算法用空闲时间来描述任务的“紧急程度”，在每次任务调度之前都要重新分配所有任务的优先级，空闲时间越小的任务获得的优先级越高。当两个任务的空闲时间接近时，会出现任务“紧急程度”相互超越的情况，任务之间会频繁相互抢占，每次抢占都会发生一次任务切换，这种频繁切换的现象称为颠簸现象[11]。

频繁的任务切换会显著增加任务的切换时间，而任务的切换时间是评价一个实时操作系统最重要的技术指标之一，因此颠簸现象大大降低了系统调度性能，也制约了LSF算法的应用[12]。现有的优化策略都是通过设置抢占阈值的方法来减轻颠簸现象，文献[9]中提出了一种动态分配抢占阈值的方案，文献[12]中提出了一种动态分配模糊阈值的方案，这些改进算法提高了LSF算法的性能，但是也明显增加了系统的额外负载，降低了系统的实时性。

1.2 优化方案

本文中对LSF算法优化后得到A-LSF算法。A-LSF算法在本质上是对LSF算法的简化，优化之后无须引入抢占阈值就能够避免LSF算法的颠簸现象，同时可以解决抢占模式下系统负载较高时，低优先级任务长时间得不到执行的问题。

A-LSF算法是利用OSEK/VDX的报警机制来实现的。报警机制是嵌入式OSEK/VDX操作系统特有的一个概念，它可以在计数器的基础上实现一系列的定时操作，当报警发生时可以激活任务、设置事件等。本文中通过设置报警和处理报警实现了A-LSF算法。

A-LSF算法是对OSEK/VDX调度算法的一个补充，只有当用户需要时，为特定任务设置了相应报警，A-LSF算法才会起作用，而且只对指定的任务起作用。A-LSF算法主要分为报警设置和报警处理两部分。报警处理中的优先级分配算法是整个算法的核心。图1为A-LSF算法流程图。

图1 A-LSF算法流程

1.2.1 报警的设置

设置报警是启用A-LSF算法的前提。这需要为嵌入式OSEK/VDX操作系统添加“分配优先级”报警，即当报警发生时分配任务的优先级。

设置报警的API函数除了要设置“分配任务优先级”这种报警之外，还须检测该任务是否有尚未发生的同类报警，如果有，则清除该报警。因为虽然在优化前，该任务长时间得不到执行，但仍然有可能凭借原来较低的静态优先级被系统所调度，在这种情况下须将之前设置的“分配任务优先级”报警清除，否则该任务有可能会过于频繁地执行而干扰其它任务的正常运行。在设置报警之后API函数还要恢复该任务的静态优先级，以避免该任务凭借上一次报警发生后获得的较高优先级而过多地执行。

1.2.2 报警的处理

报警的处理是A-LSF算法的核心内容。在每次报警发生时，都必须执行“优先级分配算法”来分配任务的优先级。如果此时该任务处于挂起状态，必须马上激活该任务；在完成上述操作的基础上，对执行嵌入式OSEK/VDX操作系统的任务调度算法进行一次任务调度。

1.2.3 优先级分配算法

优先级分配算法是报警处理的核心内容，分为两步，第一步完成优先级的初步分配，第二步在第一步的基础上完成优先级分配的优化。

(1)“任务优先级的初步分配”应满足“优先级限制条件”和“先报警先得到”的原则。前者能确保具有严格时限要求的任务不被干扰，后者能按照报警发生的先后顺序合理分配任务的优先级。算法的参数定义如表1所示。

表1 优先级分配算法的参数定义

参数含义pm优先级上限,为低优先级任务分配的优先级不得超过由用户设定的pm值pis任务τi的静态优先级pjs任务τj的静态优先级

优先级限制条件：假设此时只有任务τj的“优先级分配”报警发生，则任务τj的新优先级pj=pm。在实际的系统中，某些高优先级任务可能有严格的时间要求，不允许被干扰，此时pm的值应该低于这类任务的优先级。

先报警先得到原则：先发生“分配优先级”报警的任务会获得较高的优先级。假设任务τi的报警先发生，而且将优先级提高到了pi，紧接着任务τj的报警发生，则τj的新优先级pj取小于pi的最大值。

(2)“优先级分配的优化”目的在于使得所有使用A-LSF算法的任务尽量获得较高的优先级。因此需要检查是否有任务使用了A-LSF算法而且已经执行完毕，如果有，则该任务已经释放了它的优先级，此时应该按照(1)中的条件尽量提升其它任务的优先级。

按照该算法来为任务分配优先级会出现整个系统中多个任务共享一个优先级的情况。在OSEK/VDX标准中，当操作系统的符合类为BCC2和ECC2时，系统允许多任务共享一个优先级，符合类为BCC1和ECC1时不允许这种情况发生。因此，只当符合类为BCC2或ECC2时才可以使用A-LSF算法。

2 A-LSF算法的理论分析

定义一个任务集：τi={Ti,ri,Di,di,t,ta1,i,tad,i,ts1,i,talarm,i}，i=0,1,2,3…。任务集中各参数定义如下：Ti为任务τi的周期(本文中的研究仅限于由周期性任务构成的实时系统)；ri为任务τi剩余的执行时间；Di为任务τi的空闲时间；di为任务τi的截止期限；ta1,i为任务τi第一次被激活的时刻；t为当前时刻；talarm,i为任务τi的报警时刻；tad,i为任务τi的剩余报警时间；ts1,i为任务τi第一次设置报警的时刻。

针对LSF算法中di的计算有多种研究，文献[12]中以任务周期Ti的结束时刻作为LSF算法的截止期限，在此基础上开发了针对多处理器调度的LSFR算法。实际中di的取值与Ti紧密相关，为了计算方便仍将任务在执行周期Ti结束的时刻作为di。

图2为A-LSF算法的时序简图。由图可知，在A-LSF算法中，当任务τi的第k次设置报警结束时，本次任务τi的截止期限为

di=ts1,i+k·Ti

(1)

图2 A-LSF时序简图

根据嵌入式OSEK/VDX操作系统中的报警机制，计算在t时刻任务τi的剩余报警时间：

tad,i=di-t-ri

(2)

tad,i=ts1,i+k·Ti-t-ri

(3)

得 k=

(4)

tad,i=ts1,i+·Ti-t-ri

(5)

由于ts1,i可以视为常数，故在给定时刻t，任务的剩余报警时间tad,i是任务周期Ti和任务剩余时间ri的函数。

对LSF算法采用相同的思路计算可得：

di=ta1,i+k·Ti

(6)

Di=di-t-ri

(7)

Di=ta1,i+·Ti-t-ri

(8)

式(5)和式(8)只有常数项ts1,i与ta1,i不同，A-LSF算法中tad,i的概念等同于LSF算法中Di的概念。在A-LSF算法中，报警发生时意味着任务剩余报警时间tad,i=0，即Di=0，此时才会提升该任务的优先级，否则任务只能拥有原来相对较低的静态优先级，这正是LSF算法中“最小空闲时间优先”的思想。

A-LSF算法中报警发生之前，每个任务的空闲时间都是严格递减的，报警发生之后将不再变化，因此不会出现LSF算法中任务的紧急程度交替超越的情况。这实际上是LSF算法运行过程中的一种特殊情况，A-LSF算法只有在这种情况下才会为任务分配优先级，而且优先级分配算法遵循“先报警先得到”的原则，避免了“颠簸现象”。

LSF算法在每次调度之前都要更新所有任务的空闲时间和优先级，以此来实现最优调度。但是本文中的目的在于解决低优先级任务得不到执行的问题，低优先级任务的执行周期本身就较长，没有必要在每次任务调度之前都重新分配任务的优先级，如果不对LSF算法进行简化，系统分配优先级的频率会大大增加，而且必须添加其它算法来避免“颠簸现象”，这会额外增加系统负荷。所以，A-LSF算法相当于简化了LSF算法，满足了当前的需求。

3 优化后操作系统的应用

A-LSF调度策略是可选项，用户可以根据具体情况决定是否使用A-LSF算法。如果在测试过程中发现某些低优先级任务需要使用A-LSF算法，只须针对这些任务进行简单的配置即可；如果不使用该算法，不会对操作系统的运行产生任何影响，这大大增强了操作系统的灵活性。一般来说，只有当汽车电控系统较为复杂时才有必要在系统中配置该调度策略。本节分别介绍优化后的嵌入式OSEK/VDX操作系统在复杂系统和简单系统中的应用。

3.1 复杂的汽车电控系统

在实时性要求较高的复杂汽车电控系统中，传感器和执行器数量较多，控制算法也很复杂。因此，系统的任务数量多，负载较大。假设现有控制系统中，包含任务τ0,τ1，…,τ9，任务优先级由1到10逐次升高，均配置为抢占模式。此时用户需要根据具体的测试数据来配置系统的调度策略。假设测得任务τ0,τ1较长时间得不到执行，运行周期严重偏离用户预期，此时需要使用A-LSF算法，按照表2来配置系统的调度策略。

表2 调度策略配置方案

参数任务0任务1任务2-任务9调度策略A-LSFA-LSFDefaultpm值44Default

按照表2的配置方案，各个任务的调度策略如图3所示。

图3 任务调度策略配置结果

任务1和任务2配置为A-LSF，即使用A-LSF算法，任务3-任务10配置为Default，即不使用A-LSF算法。pm值设置为4，意味着在A-LSF算法运行时，任务1和任务2的优先级最多升高至4。在决定了系统的调度策略之后，最重要的是完成报警的设置和处理。

(1)任务τ1和任务τ2中在应用层代码结束的位置设置基于系统计数器的“分配优先级”报警，因为设置报警的API函数具有恢复任务静态优先级的功能，所以放到用户代码之后算法才有意义。由图2可知，设置报警的时长由任务的周期和执行时间决定，但是图2仅仅是理想的情况，实际中当报警发生之后，任务仍然可能被更高优先级任务抢占，不会连续执行至结束。因此报警发生的时刻应该比图2中的时刻提前一些，具体的提前量须由用户实际测试后确定。

(2)在系统时钟的中断服务程序中调用处理报警的API函数。

3.2 简单的汽车电控系统

在相对简单的汽车电控系统中，任务数量一般较少，系统负载较小。任务的实时性比较容易满足要求。因此，在这类系统中无须为任何任务配置A-LSF算法，调度策略配置结果如图4所示，操作系统与优化前相比没有任何区别,这也体现了A-LSF算法的灵活性。

图4 任务调度策略配置结果

4 实验测试与结果分析

以飞思卡尔公司的微控制器MC9S12XS128和Dspace公司的MicroAutoBox搭建实验平台。合理安排τ0-τ9共10个抢占式周期性任务，优先级从1到10逐次升高。每个任务的执行时间是固定的，分别在优化前和优化后的嵌入式OSEK/VDX操作系统上运行，其中高优先级任务的代码执行时间和执行周期都较短，低优先级任务的代码执行时间和执行周期都较长。

为了能直观地观察任务的运行状态，安排τ0-τ9各个任务分别控制一个IO口。当任务运行时相应IO口为高电平，任务退出或者被抢占后IO为低电平。利用ControlDesk的plotter工具，分别显示两个最高优先级和两个最低优先级任务的运行状态，优化前、后任务的运行状态分别如图5和图6所示。4个波形由上到下分别代表任务τ0，τ1，τ8和τ9，优化后任务τ0和τ1使用了ALSF算法。

图5 优化前的任务运行状态

图6 优化后的任务运行状态

对比图5和图6可知：优化前后高优先级任务的运行周期和执行时间基本稳定，没有明显变化；优化前低优先级任务的运行周期和执行时间很不稳定，可能很长时间才执行一次，优化后低优先级任务的运行状态虽然没有高优先级任务稳定，但是得到了非常明显的改善，能够满足用户的需求。

5 结论

(1)A-LSF算法可以实现对嵌入式OSEK/VDX操作系统的优化，能够解决系统在高负载抢占模式下低优先级任务得不到及时执行的问题。

(2)A-LSF算法克服了LSF算法原有的颠簸现象，而且与EDF或LSF算法相比，结构更加简单，容易实现。A-LSF算法作为可选项也增加了整个操作系统的灵活性。

参考文献：

[1] KIENCKE U , THIERER C. The OSEK/VDX Standard for Automotive Applications-Current Status[C]. SAE Transactions, March, 2000: 140-146.

[2] 罗克露，等. OSEK/VDX汽车电子嵌入式软件编程技术[M]. 北京：北京航空航天大学出版社，2004.

[3] Mircea Popa, Anca Sorana Popa, Titus Slavici, et al. On the Implementation of the OSEK/VDX Operating System on Advanced Microcontrollers[C]. The International Conference on Computer as a Tool, IEEE, 2007:419-426.

[4] 郜文,李继来,梁华为. OSEK/VDX 嵌入式实时操作系统在汽车稳定性控制器中的应用[J]. 计算机系统应用, 2010, 19(4):148-151.

[5] 蒋建春，张慧.基于OSEK 标准的任务调度算法的改进[J]. 计算机工程,2009,35(20)：228-230.

[6] 马明礼,等. OSEK实时操作系统任务调度的优化[J]. 单片机与嵌入式系统, 2007,10:17-53.

[7] LIU C L，James W Laykand.Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment[J]. Journal of the Association for Computing Machinery，1973,20(1)：46-61.

[8] 王济勇,林涛,王金东,等. EDF调度算法抢占行为的研究及其改进[J].电子学报，2004,32(1):64-68.

[9] BA Wei, ZHANG Dabo. A Novel Least Slack First Scheduling Algorithm Optimized by Threshold[C]. Proceedings of the 26th Chinese Control Conference， Zhangjiajie, July 26-31, 2007. Beijing: Beihang University Press, 2007.

[10] HWANG Myunggwon, CHOI Dongjin, KIM Pankoo. Least Slack Time Rate first:New Scheduling Algorithm for Multi-Processor Environment[C].IEEE Computer Society,Feb,2010:806-811.

[11] PARK S, KIM Jai-Hoon, FOX G. Effectivereal-time Scheduling Algorithm for Cyber Physical Systems Society[J]. Future Generation Computer Systems, 2014,32:253-259.

[12] 金宏, 王宏安, 王强, 等. 改进的最小空闲时间优先调度算法[J]. 软件学报, 2004,15(8):1116-1123.

Optimizationand Application of Embedded OSEK/VDX Operating System

Li Jing1, Xing Guocheng1 & Zhang Jiaxu1,2

1. Jilin University, State Key Laboratory of Automotive Simulation and Control, Changchun 130022；2. Research and Development Center, China FAW Group Corporation, Changchun 130011

[Abstract] For solving the problem that the low-priority tasks are hard to be executed under high load and preemption mode with embedded OSEK/VDX operating system, an optimized least slack first algorithm is proposed by utilizing the alarm mechanism of OSEK/VDX standard to improve the scheduling strategy of embedded OSEK/VDX operating system. The specific implementation scheme of the algorithm is presented, its feasibility is theoretically analyzed, and finally the algorithm is applied to both simple and complex electric control systems of vehicle. The results of test show that the algorithm proposed can significantly improve the excitation of low-priority tasks under the condition of high load and preemption mode.

Keywords：OSEK/VDX； LSF; scheduling algorithm; optimization; application

*国家自然科学基金(51275206)资助。

原稿收到日期为2015年3月16日，修改稿收到日期为2015年5月28日。