石志国　张凤登

摘 要：为解决FlexRay线控转向系统中常见的死锁问题，采用优先级置顶算法进行多任务动态调度。首先，分析FlexRay线控转向系统多任务动态调度过程中的死锁问题;然后深入研究优先级置顶算法防止死锁问题的原理;最后搭建双通道多冗余的FlexRay线控转向系统，进行重要系统参数配置。运行结果表明，未使用优先级置顶算法的FlexRay线控转向系统出现了死锁现象，使用优先级置顶算法进行动态任务调度之后，系统可正常运行，证明了算法有效性。

关键词：优先级置顶算法;死锁;FlexRay;线控转向;任务调度

DOI：10. 11907/rjdk. 192640

中图分类号：TP319   文献标识码：A                文章編号：1672-7800（2020）003-0145-05

Application Research of Priority Ceiling Algorithm

in FlexRay Steer-by-wire System

SHI Zhi-guo， ZHANG Feng-deng

（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，

Shanghai 200093， China）

Abstract： In order to solve the common deadlock problem in FlexRay Steer-by-wire System， this paper adopts the priority ceiling algorithm for multi-task dynamic scheduling. Firstly， the deadlock problem in the multi-task dynamic scheduling process of FlexRay steer-by-wire system is analyzed. Then， the principle of the priority ceiling algorithm to prevent the deadlock problem is studied in depth. Finally， a dual-channel and multi-redundant FlexRay steer-by-wire system is built， and the important parameters of the system were configured. The running results show that the FlexRay steer-by-wire system without the priority ceiling algorithm has a deadlock phenomenon and the system can run normally after the priority ceiling algorithm is used， which proves the effectiveness of the proposed algorithm.

Key Words： priority ceiling algorithm; deadlock; FlexRay; steer-by-wire; task scheduling

0 引言

随着计算机技术的不断发展，软件结构日趋复杂，但系统资源有限，在多任务系统下往往出现进程受阻现象。具体指在调度系统时，若调度器在运行中作出调度决策，即从多个处于“就绪”状态的任务里选择一个任务，则调度器是动态的（在线的）[1]。在动态调度策略中，大部分或全部调度决策在系统运行时，由任务调度器执行某种调度算法[2]。通常，并行任务为了合作实现系统整体目标，需交换信息、访问公共数据资源。假如任务组由周期性任务组成，采用信号量保护公共资源，所有任务必须独占公共资源。为了协调该类任务对共享资源的访问，需进行任务同步，但在实现任务同步的过程中通常会遭遇死锁问题。

国内外研究者针对该问题提出了多种算法进行改进。文献[3-4]围绕多任务动态调度问题，提出复杂多任务实时系统单处理器或多处理器调度算法;文献[5]研究了基于离散并行系统的资源分配系统的死锁问题，提出了3种解决方案：死锁检测与恢复、死锁避免和死锁预防。死锁检测与恢复策略允许系统出现死锁，一旦检测到系统处于死锁状态，通过重新配置资源，使系统恢复到正常状态。死锁避免策略使用一种在线的资源分配机制，使系统不能进入死锁状态。死锁预防策略通过离线计算，事先建立一种策略控制资源请求，从而保证系统不会进入死锁状态;文献[6]中提出一种可在FlexRay动态段中实现任务调度的递归资格调度算法;文献[7]提出一种考虑了系统公平性的优先级置顶算法，定性研究了在保证一定公平性的前提下，运用优先级置顶算法的方法。

FlexRay线控转向系统是一种新型分布式实时系统，在实际应用中该系统实时性和可靠性面临严格要求。汽车转向系统经历了4个发展阶段：机械式转向（Manual Steering，MS）、液压助力转向系统（Hydraulic Power Steering，HPS）、电控液压助力转向系统（Electronic Hydraulic Power Steering，EHPS）和电动助力转向系统（Electronic Power Steering，EPS）[8]。因系统没有摆脱占据空间较大的机械连接，系统自由设计度有限，汽车舒适、稳定、便捷性能有待进一步提高。针对这些问题，航空Fly-by-wire技术被引入汽车生产中，由此衍生了线控转向技术（Steer-by-wire）[9]，并吸引了众多汽车厂商与研究机构进行开发研究。奔驰（Mercedes-Benz）公司早在1990年着手研发前轮电子转向系统，并将其应用于概念车F400Carving上[10];通用（GM）汽车在2002年9月的巴黎车展上展示了HY-Wire概念车，该车也使用了线控（X-By-Wire）技术[11];同济大学在2004年自主研发了“三驾马车”之一的“春晖三号”汽车，它属于线控转向四轮驱动的微型概念车[12];江苏大学提出了线控转向系统前轮转向模块的动力学方程与基于分数阶微积分理论的PID控制器[13]，用Matlab/SIMULINK工具进行模型仿真验证和分析，证实控制器在频域范围具有很好的鲁棒性;武汉理工大学与东风汽车技术中心合作提出了两种线控转向系统车辆前轮转角控制算法[14];吉林大学基于最优滤波理论自适应渐消Kalman滤波技术的状态估计器，提出了线控转向系统传感器容错控制方法，并在硬件上进行了验证，同时基于假设检验的双自适应渐消Kalman滤波技术，在系统传感器故障诊断方面进行了研究。

优先级置顶算法是一种能有效解决死锁问题的动态调度算法，有助于提升线控转向系统资源调配稳定性，现有方法暂未从该角度进行研究。因此本文通过搭建真实FlexRay线控转向系统，深入研究死锁问题原理与优先级置顶算法可调度性。

1 FlexRay线控转向系统中的死锁问题

在线控转向系统中，主体是系统中的每一个任务，死锁由阻塞引起，当两个任务同时等待被对方锁定的资源（如信号量）时，则两个任务可能均被阻塞，导致死锁问题。图1是一个死锁问题实例。图1中任务[τ2]优先级高于任务[τ1]，信号量S1和信号量S2被用于保护不同的共享资源，死锁问题产生过程为：①[τ2]正在运行，而[τ1]处于就绪状态，[τ2]锁定了S1;②稍后，[τ2]为了等待事件E的發生，自行转入等待状态;③此时，[τ1]得以运行，并在运行中锁定了信号量S2;④接着事件E发生，由于[τ2]的优先级高于[τ1]，[τ2]抢占[τ1]，再次开始运行;⑤现在，假如[τ2]要锁定信号量S2，必然失败，因为S2已经被[τ1]锁定;⑥因此，[τ2]又进入了等待状态，直到S2被释放，任务[τ1]恢复运行;⑦接下来，任务[τ1]试图锁定信号量S1失败，因为S1已经被[τ2]锁定;⑧这时，[τ1]也进入等待状态，直到S1被释放，出现死锁。

在图1中，两个任务都需对方释放一个信号量，均停留在等待状态，即产生死锁。假如没有外力作用，则死锁涉及到的每个任务将一直处于等待状态，导致系统停滞，严重影响系统实时性，甚至可能引发重大事故。

2 优先级置顶算法

优先级置顶算法也称简单优先级置顶算法，优先级置顶指任务控制访问临界资源时，优先级被置为相应信号量的置顶优先级。该算法主要内容包括：

（1）对于控制临界区的信号量，将可能申请该信号量所有任务中具有最高优先级的任务设置为信号量置顶优先级。

（2）假如任务成功申请到信号量，任务优先级将被提升为信号量置顶优先级;当临界区任务执行结束后，将信号量释放后，其优先级将重新恢复到任务最初的优先级。

（3）假如任务不能得到申请的信号量，任务将会被阻塞[17]。

举例说明优先级置顶算法（见图2），总共包括[τ1]-[τ5]5个任务，优先级从[τ1]到[τ5]依次升高。[τ1]和[τ4]共享资源R，保护该资源的信号量为S。其中，任务挂起指任务还未被初始化或任务已执行完成;任务就绪指任务正在等待获得共享资源;任务运行指任务已获得想要的资源，包含的代码正在被执行。

系统运行过程为：①[τ1]正在运行，[τ2]、[τ3]、[τ4]和[τ5]挂起;②[τ1]请求资源R，此时该资源可用， T1锁定信号量S。[τ1]的优先级提升到资源R的置顶优先级。在运行过程中，[τ1]的优先级高于[τ2]、[τ3]、[τ4]，但低于[τ5];③[τ2]、[τ3]、[τ4]进入就绪状态，但不能运行，因为它们的优先级低于提升后的[τ1];④在[τ1]以其提升后的优先级运行期间，[τ5]被激活。由于[τ5]的优先级高于资源R的置顶优先级，[τ5]抢占[τ1]，并运行至结束。然后，[τ1]恢复运行，且仍处于提升后的优先级;⑤[τ1]解除信号量S的锁定，释放资源R，[τ1]的优先级返回其基本优先级;⑥此时，在处于就绪状态的任务中，[τ4]的优先级最高，[τ4]请求资源R，并锁定信号量S，[τ4]的优先级提升到资源R的置顶优先级，抢占[τ1]并开始运行;⑦[τ4]运行一段时间后，[τ4]释放资源R，并返回到它的基本优先级，直至运行结束;⑧接下来，[τ3]和[τ2]是优先级最高的任务，它们顺次获得运行权;⑨最后，[τ1]恢复运行。

在上述实例中，[τ1]获得临界资源后，其优先级被抬升到资源置顶优先级，这样可有效避免死锁，使系统多个任务均可被正常执行。为进一步研究优先级置顶算法对FlexRay线控转向系统多任务调度的影响，本文构建真实的FlexRay线控转向系统。

3 FlexRay线控转向系统构建

在汽车驾驶过程中，转向系统是保证车轮按照驾驶员意向正常转向的重要部件。作为驾驶员和车辆的媒介，转向系统性能好坏直接影响到驾驶路感、舒适性和稳定性[18-19]。线控转向技术（Steer-by-wire）与传统液压助力系统、电控助力系统相比，减少了液压和机械连接装置及轴承等金属装置，减轻了系统整体重量，降低了系统装配复杂性与生产成本。FlexRay线控转向系统可以实现硬件和软件冗余，而且电控单元可采用分布式控制，大幅提高系统可靠性、安全性和舒适性。

3.1 系统架构设计

为保证系统实时性和可靠性，同时满足经济实用性要求，该系统线控转向系统容错架构设计如图3所示，包括电子控制单元（微控制器），即Hand Wheel ECU1（方向盘ECU1）、Hand Wheel ECU2（方向盘ECU2）、Front axle actuator ECU1（前轴ECU1）、Front axle actuator ECU2（前轴ECU2）。每个ECU之间通过支持TDMA媒体访问和双通道通信的FlexRay总线连接。3个转角传感器分布在转向轴上，测量方向盘转角、转矩和转速。另外3个前轴传感器用来测量前轴转动位置。两个路感电机（HW Motor1、HW Motor2）根据转向电机（FAA Motor1、FAA Motor2）反馈控制模拟路感。转角传感器分别与HW ECU1、HW ECU2点对点连接，同样前轴传感器分别与FAA ECU1、FAA ECU2点对点连接。

系统融入全面冗余的概念，设计了ECU冗余、电机冗余、总线传输通道冗余、传感器冗余及电源冗余。HW ECU1/ECU2和FAA ECU1/ECU2实现了ECU冗余，且具有故障静默的属性，实现了双模冗余。双电机实现了电机冗余，可有效应对单个电机失效的状况。双通道的使用保证了FlexRay总线通道冗余。每个通道速度均达到10Mbps，使用双通道，总速度可达到20Mbps，保证数据传输实时性。双电源的使用保障了电源冗余。随着汽车用电设备的增加，传统12V电源已不足用。如果采用42V电源系统，对于相同功率提高电压值、减小电流值，可减小电能损耗，减少线束线芯，降低成本及负载电流并提高电子元件集成度等[20]。3个传感器实现了传感器三模冗余。传感器是数据来源，对于整个系统安全运行起着至关重要的作用，故采用安全性可靠度较高的三模冗余方法。Lamport研究表明，为容忍n个拜占庭错误，至少需要3n+1个冗余单元[21]。例如：容忍1个单元的拜占庭失效，至少需要4个单元。对应的解决办法是四模冗余，但是硬件开销成本很大。根据定理，如果至多有m个叛徒，SM（m）算法可解决m个叛徒的拜占庭问题。故若提供一种表决签名算法，3个传感器可克服1个拜占庭错误或随后的1个连续错误或1个故障静默错误。ECU具有相同算法和传感器测量数据，并且把这些数据在冗余通道及不同的FlexRay帧时隙传输，从而实现全面冗余，保障系统可靠性。从冗余性和多样性来看，该架构设计受系统可靠度、制造成本及元件尺寸限制。但是，从经济性角度看，若系统满足可靠性关键要求，方向盘控制和前轴转向控制功能均使用2个ECU的方案是最优的。

线控转向系统主要由传感器、ECU、电机组成。方向盘转角数据采集来源于转角传感器，经过方向盘ECU处理，再通过总线进行传输到前轴ECU，前轴ECU根据得到的数据对转向电机进行控制;反之，可对路感电机进行控制。因此，线控转向系统每个节点应由电源输入模块、MC9S12XF512单片机、A/D转换电路、PWM输出电路、通信收发器等组成，可实现：①利用传感器信号进行采样;②输出PWM控制相应电机运转;③FlexRay网络通信;④CAN总线通信。

线控转向系统节点结构设计如图4所示。

3.2 FlexRay线控转向系统网络参数与任务配置

本文分布式线控转向系统使用FlexRay网络，其网络参数配置如表1所示。

FlexRay网络使用最高的传输速率10Mbit/s，报文在A、B双通道同时传输，单个周期设为5ms。方向盘节点FAA ECU1和FAA ECU2分别在静态时隙1、2中发送方向盘转角消息，并在每个周期进行发送，周期为5ms。

FlexRay线控转向系统中的每个节点均有任务， FlexRay线控转向系统任务参数如表2所示，表2列出了在FlexRay线控转向系统中4个任务周期、驱动机制、任务传输时间等信息。

表2中，road-motor_task是路感电机任务，steering _task是转向电机任务，corner_task是转角传感器任务，epipodium_task是前轴传感器任务。

系统中含有非周期任务，FlexRay线控转向仿真系统未使用优先级置顶算法的调度分析如图5所示。

图5中[τ4]是corner_task，[τ3]是steering _task，[τ2]是epipodium_task，[τ1]是road-motor_task，d_segment表示动态段资源，Outer表示某一全区变量。

从图5可看出，FlexRay线控转向系统最终会出现死锁状态。为实现优先级置顶算法，在实际应用中，为每个任务设置一个定时器，每隔0.005s监测是否有其它任务申请资源，当监测到有其它优先级的任务申请相同资源时，将正在运行的任务优先级提升至资源置顶优先级。

4 系统运行评估

FlexRay线控转向系统任务模型建立后，先对未使用基于优先级置顶算法的FlexRay线控转向系统多任务动态调度性能进行评估测试。运行系统与网络调度过程如图6所示。

图6中，r代表路感电机任务，u代表转向电机任务，y代表传感器任务。输出结果与图5FlexRay线控转向系统调度分析结果一致，FlexRay线控转向系统中只有传感器节点运行，其它节点任务由于路感电机任务和转向电机任务产生死锁而处于停滞状态。

使用优先级置顶算法的FlexRay线控转向系统运行系统与网络调度过程如图7所示。

图7中r、u、y的代表意义与图6一致。运用优先级置顶算法后，FlexRay线控转向系统的各个任务均正常被系统调度，有效防止了死锁发生。

5 结语

本文对FlexRay线控转向系统中的死锁问题进行了分析，研究了优先级置顶算法防止死锁问题的原理，阐述了优先级置顶算法工作原理和过程，并搭建了FlexRay线控转向系统。通过对比验证可知，未使用优先级置顶算法的FlexRay线控转向系统出现了死锁，使用该算法进行动态任务调度之后，系统可正常运行，验证了优先级置顶算法对避免死锁问题的有效性。

优先级置顶算法虽有效性较高，但本文系统任务数量较少，当任务数量大幅增加时，该算法作用将受到限制，甚至会失去任务调度公平性。因此下一步将围绕优先级置顶算法可调度性进行定量研究，探索改进方法。

参考文献：

[1]KOPETZ H. Real-time systems： design principles for distributed embedded applications[M]. Boston：Springer，1997.

[2]       李祖欣，王万良，雷必成，等. 网络控制系统中的调度问题[J]. 计算机工程与应用，2007，43（16）：241-246.

[3]周平方. 實时控制系统多任务反馈调度研究[D]. 上海：上海交通大学，2006.

[4]同爱丽. 实时多任务调度方法研究与应用[D]. 西安：西北工业大学，2006.

[5]       朱森. 资源分配系统死锁控制及其应用研究[D]. 西安：西安电子科技大学，2006.

[6]       JUNG K H， SONG M G， LEE D I， et al. Priority-based scheduling of dynamic segment in FlexRay network[C]. IEEE International Conference on Control， Automation and Systems，2008：1036-1041.

[7]       KISS D K. Intelligent priority ceiling protocol for scheduling[J].  IEEE International Symposium on Logistics & Industrial Informatics， 2011：105-110.

[8]王常友，董爱杰.  汽车转向系统的现状及发展趋势[J]. 北京汽车，2007（3）：7-10.

[9]许张义. 基于FlexRay总线的线控转向控制系统设计研究[D]. 长沙：湖南大学， 2013.

[10]唐莹. 汽车前轮线控转向系统研究[D]. 上海：上海理工大学，2009.

[11]潘旭临. 全球首辆可驾驶线控燃料电池车在长城揭开面纱[EB/OL]. http：//www.chinanews.com/n/2003-11-15/26/369118.html.

[12]李岳鹏. 国产微型概念车“春晖三号”亮相上海[EB/OL].  http：//auto.enorth.com.cn/system/2004/11/15/000903200.html.

[13]田杰，高翔，陈宁. 基于分数阶微积分的线控转向系统的控制研究[J]. 机械科学与技术，2010，29（9）：1172-1176.

[14]欧阳海，张杜鹃，高岗. 线控转向车辆前轮转角控制算法研究[J]. 技术与应用，2009（11）：30-31.

[15]田承伟，宗长富，王祥，等. 线控转向汽车传感器的容错控制[J]. 吉林大学学报， 2010，40（1）：6-12.

[16]田承伟，宗长富，姜国彬，等. 基于双自适应Kalman滤波的线控转向汽车传感器故障诊断[J]. 中国公路学报，2009，22（4）：115-121.

[17]张凤登. 分布式实时系统[M]. 北京：科学出版社，2014.

[18]余志生，夏群生. 汽车理论[M]. 北京：机械工业出版社，2006.

[19]喻凡，林逸. 汽车系统动力学[M]. 北京：机械工业出版社，2005.

[20]汽车转向系统的技术探讨. 电子产品世界[EB/OL]. http：//www.eepw.com.cn/article/196610.htm.

[21]LAMPORT L，SHOSTAK R，PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Language and Systems，1982，4（3）：382-401.

收稿日期：2019-12-05

基金項目：上海市自然科学基金项目（15ZR1429300）

作者简介：石志国（1995-），男，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为现场总线技术与汽车电子;张凤登（1963-），男，博士，上海理工大学光电信息与计算机工程学院教授、博士生导师，研究方向为分布式系统、过程控制与现场总线技术。