HRRF任务调度在汽车仪表中的改进与实现

韩琛 刘斌 谢斌 蒋峥

关键词： 汽车仪表; 高响应比优先; 任务调度; 任务优先特性分类; 等待时间; 服务时间; 截止期错失

中图分类号： TN919?34; TP216+.2                    文献标识码： A                  文章编号： 1004?373X（2019）05?0090?05

Improvement and implementation of task scheduling with high response

ratio first in automobile instrument

HAN Chen1， LIU Bin1， XIE Bin2， JIANG Zheng1

（1. MOE Engineering Research Center of Metallurgical Automation and Detecting Technology， College of Information Science and Engineering， Wuhan University of Science and Technology， Wuhan 430081， China; 2. Wuhan Baohua Display Technology Co.， Ltd.， Wuhan 430082， China）

Abstract： The foreground and background cycle mode is frequently used in the design of automotive instrument embedded system， by which the execution frequency of each system task is compulsive the same， the execution sequence can′t be changed， and each waiting time of the task fluctuates greatly， so it is difficult to guarantee the real?time performance of system task. In order to solve these problems， the task scheduling algorithm with highest response ratio first （HRRF） is optimized according to its advantages， and applied to the software design of automobile instrument. The periodic tasks are classified according to the priority characteristics. The waiting time and service time of each task are updated in real time. Considering the deadline missing of the task， the task with highest response ratio is selected in the same class for execution in every work period. The practical application result shows that the method has small scheduling overhead and high real?time performance， and is easy to maintenance and transplant.

Keywords： automobile instrument; highest response ratio first; task scheduling; task priority characteristics classification; waiting time; service time; deadline missing

0  引  言

随着电子技术在汽车产品上的广泛应用，功能越来越多样化的嵌入式智能车载仪表受到了广泛的关注和研究。目前，车载仪表软件基本采用传统的嵌入式前后台循环设计开发模式。与之相比，多任务调度技术可以实现系统各任务的规律调度，提高了任务的实时性，具有调度开销小、方便维护和移植等优点。

多任务调度技术已经广泛应用于社会生活的各个领域[1?2]。文献[3]在时间触发系统基础上，把任务分为抢占式任务和周期性任务，增加了抢占式内核的特性，明显提高了抢占式任务处理的实时性，并将其成功应用于智能电表中。但在该系统中，周期性任务的实时性没有得到明显改善。文献[4]提出基于分类和多优先级队列的调度方案，将非实时图形任务和通用计算任务按照优先级在各自队列中排队，实时图形任务按照截止期（周期性任务各周期内执行的结束时刻）排队。该调度方法专注于提升实时图形任务的帧率，并未对其他两种任务的实时性以及任务的调度开销做优化。文献[5]实现了静态优先级和动态优先级调度。其中，基于静态优先级调度的单调速率调度（Rate Monotonic Scheduling，RMS） 算法根据任务执行周期的长短来决定调度优先级，为短执行周期的任务赋予较高的优先级，为长执行周期的任务设定较低的优先级。动态优先级调度的最早截止期优先（Earliest Deadline First，EDF）算法，根据任务的截止期动态分配任务的优先级。截止期越近，优先级越高。但这两种调度算法仅考虑单一因素对任务优先级的影响，不利于处理器更加准确地分配任务优先级。Rehana等人在RMS和EDF基础上提出了PPA（Preference Priority Assignment）算法[6]和 POFP（Preference Oriented Fixed Priority）算法[7]。这两种算法根据任务执行优先顺序将周期性实时任务分类为ASAP（As Soon As Possible）类和ALAP（As Late As Possible）类。与RMS算法相比，PPA算法支持给ASAP类任务更高的优先级。相反，给ALAP类任务更低的优先级。POFP算法在RMS算法和PPA算法基础上，将任务分为就绪队列和延迟队列两个队列。ASAP类任务由延迟队列触发后，立即进入就绪队列，系统将尽快的调用;而ALAP类任务在延迟队列中触发后，会有一个触发时间限制，只有当ALAP类任务在延迟队列中触发之后，等待时间大于该任务的触发时间时，ALAP类任务才可以进入就绪队列，等待系统调用。文献[6?7]分别对周期性实时任务的优先级划分和任务执行顺序给出了具体的方法，但却未对任务的截止期做过多考虑。文献[8]提出SEED（ASAP?Ensured Earliest Deadline）算法和POED（Preference? Oriented Earliest Deadline）算法，以容错系统为应用背景，考虑任务截止期错失问题，给出了系统满载（CPU利用率100%）下的SEED算法和非满载下的POED算法。这两种算法过于复杂，不适用也不必用于单处理器上的任务调度。文献[9]中的先来先服务算法（First Come First Service，FCFS），任务按触发时间先后顺序执行。采用这种算法，如果先触发的任务执行时间过长，则后触发的任务实时性得不到保证。而短作业优先算法（Shortest Job First，SJF）按执行时间长短给任务分配优先级，执行时间越短，优先级越高。此算法中，如果短作业过多，则长作业等待时间可能会过长，影响调度性能。文献[10]将高响应比优先（Highest Response Ratio First，HRRF）调度应用于网络地理信息系统中，缩短所有用户并发请求的平均响应时间，解决并发访问产生的响应滞后问题。该文提升了全局的负载均衡效果，但对于响应比优先算法本身没有明显改进。文献[11]针对传感器网络操作系统Tiny OS采用非剥夺的先来先服务调度策略，针对系统紧急任务不能得到及时响应及节点吞吐量下降的情况，提出一种可抢占的HRRF任务调度策略。该策略在不影响Tiny OS原有性能的基础上极大改善了传感器网络承担实时性任务的运行效率，但其也没有考虑实时性任务截止期错失问题。

为了提高任务的响应速度，减小平均等待时间，本文同时兼顾任务的等待时间和服务时间，结合ASAP和ALAP性质以及截止期错失问题，对HRRF进行改进，并将改进后的HRRF算法应用于汽车仪表软件设计中。结果表明，相比于嵌入式前后台循环软件设计模式，本设计有效降低了任务的平均等待时间，各任务都能在更快的时间内得到响应，且调度开销小，方便维护和移植，提升了调度性能。

1  汽车仪表开发研究现状

图1中，KL.30是汽车电子控制单元（Electronic Control Unit，ECU）的电源供电信号;KL.15是发动机点火信号，也表示车钥匙扭动，启动汽车的信号。在KL.30给汽车仪表供电后，汽车仪表会根据触发条件判断接下来的仪表工作状态，仪表工作状态包括点火（Ignition，IGN）、充电（CHARGE）和STANDBY。点火和充电状态不难理解，STANDBY表示汽车仪表处于车钥匙关闭但仍然有CAN报文传输的工作状态。汽车仪表进入到某工作状态后，先进行该工作状态的初始化，然后开始在该工作状态下按照固定的顺序重复遍历执行任务，直到仪表工作状态改变。图1中相关术语及含义见表1。

图1中给出的仪表软件结构，优点是处理起来比较简单方便，不需考虑各任务的周期性和截止期丢失，将各任务按一定的逻辑依次放在循环中即可。但其缺点也很明显，随着用户对汽车仪表要求的功能种类不断增加，需要处理的任务量不断上升时，该开发模式下，处理器处理相同仪表工作状态下各任务的频率相同，需要反复处理较多不必要的任务，导致处理器利用率较低。因此，在汽车仪表软件设计中，使用多任务调度技术来解决上述问题是必然的发展趋势。

2  任务管理

2.1  任务状态

在本文设计系统中，仪表中的每个功能任务均具有如下四个任务状态：

就绪（Ready）：任务周期时间开始，准备就绪，相关数据结构已经建立，可以随时调度运行时的状态。

运行 （Running）：任务处于占用CPU运行时的状态。

挂起 （Suspend）：任务由一次运行结束到下一次就绪中间这段时间所处的状态。

未激活 （Unactive）：任一仪表工作状态下，如果某任务在此种仪表工作状态下不需执行，则该任务为此种仪表工作状态下的未激活态。例如仪表处于充电下，不需要显示汽车速度，此时速度显示任务处于未激活。未激活之外的任务处于相对应仪表工作状态下的激活（Active）。

仪表功能任务的各状态之间切换关系如图2所示。

其中，条件1：任务被调度;条件2：该次任务执行结束;条件3：任务新周期到来;条件4：仪表工作状态改变。

2.2  任务结构

为方便任务管理，需要创建一个用于描述单个任务的数据结构，本系统中，单个任务描述结构如下：

typedef  struct

{

uint8_t   Type;       //類型：根据性质把任务分为ASAP类和ALAP类

uint16_t  Period;    //周期：任务的调度周期，即任务由一次Suspend开始到下一次Suspend开始中间的这段时间

float   Start_Time;   //开始时刻：任务在一个调度周期内开始执行的时刻，下文公式中用[Tstart]表示

float End_Time;    //结束时刻：任务在一个调度周期内结束执行的时刻，下文公式中用[Tend]表示

float Wait_Time;   //等待时间：任务从触发到开始执行的时间，下文公式中用[Twait]表示

float Service_Time;   //服务时间：任务从开始执行到结束执行的时间，下文公式中用[Tservice]表示

float Response_Rate;   //响应比：任务优先级的衡量标准，下文公式中用RR表示

uint8_t  State;   //状态：任务状态

uint8_t  Period_Count;  //周期计时：任务每一个周期的计时

uint8_t  Wait_Time_Flag;  //等待时间标识：任务是否开始计算等待时间的标识

float WCET;   //最差执行时间，任务单次执行所需最长时间

}Task_Control_Block;

3  任务调度算法改进及应用

3.1  HRRF任务调度算法

HRRF任务调度算法是将CPU分配给就绪任务中响应比最高任务的一种算法。HRRF基于先来先服务算法与短作业优先算法，既考虑任务等待时间又考虑任务服务时间，既照顾短作业又不使长作业等待时间过长，从而改进了调度性能。

任务等待时间的定义如下：

[Twait=Tstart-Tperiod] （1）

式中：[Twait]为任务等待时间，单位为ms;[Tstart]为任务在一个周期内开始执行的时刻，单位为ms;[Tperiod]为该周期的起始时刻，单位为ms。

任务服务时间定义如下：

[Tservice=Tend-Tstart] （2）

式中：[Tservice]为任务服务时间，单位为ms;[Tend]为任务在一个周期内结束执行的时刻，单位为ms;[Tstart]为任务在该周期内开始执行的时刻，单位为ms。

任务响应比定义为任务等待时间和任务服务时间的和与任务服务时间的比值，即：

[RR=Twait+TserviceTservice=1+TwaitTservice] （3）

式中：[RR]为任务响应比;[Twait]为任务等待时间，单位为ms;[Tservice]为任务服务时间，单位为ms。HRRF任务调度算法按式（3）定义任务的响应比大小来确定任务的执行顺序。

3.2  改进HRRF及在汽车仪表中的应用

3.2.1  HRRF的改进

结合电动汽车仪表的实际需求，对HRRF任务调度算法做如下改进：

1） 根据任务实时性要求的程度，将任务根据实际情况分为ASAP类和ALAP类。目前的HRRF任务调度算法在CPU选择任务分配时，对所有的任务没有性质上的优先，都要重新计算响应比，然后选择响应比最高的任务执行。本文改进的HRRF算法，在实际情况中根据任务的周期大小将任务分为ASAP类和ALAP类。当有ASAP类任务就绪时，只计算ASAP类就绪任务的响应比，选择最高响应比的任务。没有ASAP类任务就绪时，再计算ALAP类就绪任务的响应比，选择最高响应比的任务。

2） 在1）的基础上选出最高响应比的任务后，判断在该任务执行期间是否有其他任务截止期错失。若有，则强制选择截止期丢失的任务中响应比最高的任务执行;若没有，则执行1）中最高响应比的任务。

3.2.2  改进后的HRRF在汽车仪表软件设计中的应用

以电动汽车仪表处于IGN工作状态为例，改进后的HRRF在汽车仪表软件设计中的流程如图3所示。

1） 各任务的初始化与更新

系统在IGN初始化之后，将IGN下激活任务按一定逻辑顺序执行一次，这样测得每个任务的第一次服务时间。在各个任务之后每次执行时，均测量其服务时间，并实时记录服务时间最长的一次WCET（Worst Case Execution Time）。每次调用HRRF算法时，任務的服务时间用上一次测得的任务服务时间近似代替。在激活任务全部执行一次完毕之后，任务均处于Suspend状态，开始给任务按各自周期计时。任务周期到了，该任务状态由Suspend变为Ready状态，开始等待时间计时。

2） 改进HRRF算法的执行

调用HRRF算法时，先判断是否有ASAP类任务处于Ready等待执行。若有，则在处于Ready的ASAP类任务中选择响应比最高的任务为接下来执行的任务;若没有，则在处于Ready的ALAP类任务中选择响应比最高的任务接下来执行。同时，系统会判断是否有任务截止期错失，若有多个任务截止期丢失，则任务的优先级会发生转换，接下来强制执行截止期丢失任务中响应比最高的任务;否则，执行ASAP类或ALAP类响应比最高的任务。若系统某时刻执行调度时，所有任务响应比均为0，则接下来执行空操作，即此次调度系统不执行任务。任务执行时，其状态变为Running。执行结束后，任务状态变为Suspend。

4  性能验证及说明

将所提出的改进HRRF任务调度算法应用于某公司自主研发的某车型仪表，对系统各项指标进行实际测量，并进行了分析。

以汽车仪表处于IGN工作状态为例，将汽车仪表IGN工作状态下任务分为10个，分别为段码屏显示速度控制、信号灯控制、CAN数据接收处理、按键状态检测、电机指针控制、蜂鸣器控制、界面显示、数据丢失处理、故障报警弹窗逻辑控制和蓄电池电压检测。

4.1  调度开销

调度开销指在任务切换之间的时间间隔，即调用HRRF进行任务调度所花费的时间，其计算公式如下：

[TOverhead=TNext_start-TLast_end] （4）

式中：[TOverhead]表示调度开销;[TNext_start]表示下一任务开始执行时刻;[TLast_end]表示上一任务结束时刻。分别设定ASAP类任务占全部任务的比例为0%，20%，40%，60%，80%，相应的进行多次调度开销测量，测算结果见表2。

由表2可知，基于本文提出的调度算法，汽车仪表系统根据ASAP类任务占比不同，每次任务调度开销约为10～50 μs不等。当ASAP类任务占比为0%，即任务没有设定上的优先属性时，系统进行任务调度，实质上就是传统HRRF任务调度算法。此时，调度开销明显大于任务有设定优先属性时。当ASAP类任务占比不为0%时，ASAP类任务占比越多，调度开销越大。在汽车仪表系统中，与各任务的周期相比较，这种调度开销完全可以忽略。在实际设计中，可以根据任务的实际性质，配置各任务的优先属性和周期，尽可能优化系统。

4.2  任务平均等待时间

任务平均等待时间定义为各任务多次等待时间的平均值。设前5个为ASAP类任务，后5个为ALAP类任务，多次测量各任务的等待时间，得到其平均等待时间见表3。

由表3分析可得，ASAP类任务的平均等待时间明显小于ALAP类任务。原嵌入式前后台循环软件设计模式下，任务无论何时触发，都将在系统下次循环到该任务时才可以执行，因此平均等待时间可以近似为整个循环时间的[12]，而在嵌入式前后台循环软件设计模式中，为了控制系统运行的速度，整个系统循环控制在100 ms，这就是说，各任务的平均等待时间近似可以认为是50 ms。显然，系统采用改进后的HRRF任务调度，无论任务是ASAP类还是ALAP类，均减小了其平均等待时间，任务响应时间变短，提高了实时性。相比于ALAP类任务，ASAP类任务实时性提高的更多。

4.3  其他优点

相比于嵌入式前后台循环软件设计模式，系统采用HRRF任务调度，各任务的执行频率不再强行一致，而是根据各自优先属性决定各自的执行频率。当系统需要增加任务或者减少任务时，只需将相对应的任务添加到任务队列中或者从任务队列中删除，方便了系统的维护和移植。并且考虑任务的截止期错失，周期性任务调度的时限会更加规律。随着汽车的不断发展，汽车仪表要执行的任务会更多，采用多任务调度的优势会更加明显。

5  结  语

本文分析了传统的嵌入式前后台循环软件设计模式的缺点，以汽车仪表为载体，提出将改进后的HRRF任务调度算法应用于汽车仪表的软件设计中，解决了目前汽车仪表系统实时性不强，响应时间较慢的问题，并通过实际开发，对设计算法的实时性及实用性进行了验证。结果表明，本文设计的调度开销可以忽略，实时性优于原设计模式，且方便维护和移植。

参考文献

[1] 周鹏.管道流量泄漏在线监测中的模糊调度設计[J].计算机工程与应用，2009，45（27）：231?236.

ZHOU Peng. Fuzzy scheduling design in computer on?line mo?nitoring system based on pipeline flux leak [J]. Computer engineering and applications， 2009， 45（27）： 231?236.

[2] 郑英治，焦哲勇.基于OSEK标准的嵌入式实时操作系统在汽车电子中的应用[J].现代电子技术，2011，34（3）：148?150.

ZHENG Yingzhi， JIAO Zheyong. Application of embedded RTOS in automotive electronics based on OSEK [J]. Modern electronics technique， 2011， 34（3）： 148?150.

[3] 朱德良，吴国强，陈新春.一种单片机多任务操作系统的设计与应用[J].自动化与仪表，2014，29（1）：50?52.

ZHU Deliang， WU Guoqiang， CHEN Xinchun. Design and application of microcontroller based on multi?tasking operating system [J]. Automation & instrumentation， 2014， 29（1）： 50?52.

[4] 丑文龙，梅魁志，高增辉，等.ARM GPU的多任务调度设计与实现[J].西安交通大学学报，2014，48（12）：87?92.

CHOU Wenlong， MEI Kuizhi， GAO Zenghui， et al. Design and implementation of multitask scheduling for embedded ARM GPU [J]. Journal of Xian Jiaotong University， 2014， 48（12）： 87?92.

[5] 邢群科，郝红卫，温天江.两种经典实时调度算法的研究与实现[J].计算机工程与设计，2006，27（1）：117?119.

XING Qunke， HAO Hongwei， WEN Tianjiang. Research and implementation of two classical real?time scheduling algorithms [J]. Computer engineering and design， 2006， 27（1）： 117?119.

[6] BEGAM R， XIA Qin， ZHU Dakai， et al. Preference?oriented fixed?priority scheduling for periodic real?time tasks [J]. Journal of systems architecture， 2016， 69（C）： 1?14.

[7] BEGAM R， ZHU Dakai， AYDIN H. Preference?oriented fixed?priority scheduling for real?time systems [C]// 2014 IEEE International Conference on Dependable， Autonomic and Secure Computing. Dalian： IEEE， 2014： 159?165.

[8] GUO Yifeng， SU Hang， ZHU Dakai， et al. Preference?oriented real?time scheduling and its application in fault?tolerant systems [J]. Journal of systems architecture， 2015， 61（2）： 127?139.

[9] ALHUSAINY M A F. Best?job?first CPU scheduling algorithm [J]. Information technology journal， 2010， 6（2）： 288?293.

[10] 郭明强，黄颖，谢忠.基于响应比优先调度的WebGIS动态负载均衡算法[J].地理与地理信息科学，2013，29（2）：36?39.

GUO Mingqiang， HUANG Ying， XIE Zhong. A WebGIS dynamic load balancing algorithm based on response ratio priority scheduling [J]. Geography and geo?information science， 2013， 29（2）： 36?39.

[11] 李海成.基于TinyOS的HRRF调度策略[J].计算机科学，2010，37（4）：80?81.

LI Haicheng. Research on HRRF scheduling strategy based on TinyOS [J]. Computer science， 2010， 37（4）： 80?81.