優先級置頂算法在FlexRay線控轉向系統中的應用研究

石志國　張鳳登

摘 要：為解決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-），男，博士，上海理工大學光電信息與計算機工程學院教授、博士生導師，研究方向為分布式系統、過程控制與現場總線技術。