基于時空隔離原則的列車控制軟件集成方法的研究

景 浩，馬連川

（1. 北京交通大學 軌道交通運行控制系統國家工程研究中心，北京 100044；2. 北京交通大學 電子信息工程學院，北京 100044）

基于時空隔離原則的列車控制軟件集成方法的研究

景 浩1,2，馬連川1,2

（1. 北京交通大學 軌道交通運行控制系統國家工程研究中心，北京 100044；2. 北京交通大學 電子信息工程學院，北京 100044）

針對CTCS-3設備硬件資源浪費、通信復雜和容易出故障的問題，參考ARINC 653標準中時空隔離的思想，目的是實現一臺設備集成多臺設備的功能，提高設備效率和可靠性。文中運用兩級調度結構，根據VXWORKS操作系統的特性計算程序運行時間，確定隔離時間和周期；運用開發平臺工具測量單個任務所需內存，確定隔離內存大小。用實例驗證本方法的正確性。

時空隔離；RM調度算法；隔離時間；隔離內存；CTCS-3

現在的CTCS-3級列車控制系統（以下簡稱：列控系統）基于疊加原則實現完整功能，有降低工作量和費用的優點，但也會導致整個系統結構復雜、設備量多，設備間的通信和連接復雜，造成系統平均無故障時間（MTBF）降低，會導致比較頻繁地出現故障而使系統恢復時間變長，不僅降低系統運行效率，而且還容易誘發其它重大事故。

此外，CPU正朝著多核化、低功耗化和支持虛擬化等方向發展，其處理速度和綜合處理能力越來越強，同時，隨著內存、磁盤和網絡等技術的飛速發展，以前需要多個計算機處理的功能現在已經可以由單個計算機完成。因此，傳統的基于疊加原則實現列控系統的方法實際上也造成了硬件處理能力和資源的浪費。

要解決上述問題，可參考航空電子行業為解決航空電子設備集成問題所制定的ARINC 653標準。它在高安全性的實時操作系統中提出了分區的概念，原有的子系統概念已由硬件實體變為軟件。分區是運行于一個處理機模塊上的多個應用程序（或子系統），它們在時間和空間上彼此隔離，互不影響，當一個分區內的應用發生錯誤時，在時間和空間上都不會影響到其它分區[1][8]。

ARINC 653標準需要特定軟硬件的配合，實現難度和成本都很高。本文借鑒其思想，以較低成本在安全計算機平臺上實現子系統之間的時（間）空（間）隔離以保證安全，同時子系統內部使用優先級調度算法以提高效率，重點在于如何實現時空隔離。針對時間參數確定基本靠經驗和不斷試驗的現狀，結合軟件測試、調度算法、系統應用等多方面的方法，利用實時操作系統精確測量軟件運行時間，從而準確確定時間參數。針對軟件內存保護方面的不足[1]，通過與時間參數結合實現內存的靜態分配，從而在時間域和存儲空間域對安全計算機平臺所集成的多套列控軟件實現確定性安全保護。

1 兩級調度結構

本文使用兩級調度結構[1]，在操作系統之上，用時間觸發來分離各子系統模塊，如臨時限速服務器（TSRS）、無線閉塞中心、列控中心等。這樣，各個子系統在時間上實現了隔離，一個子系統的內部錯誤（如單個任務長時間占用處理器）只會影響自己內部，不會對其它子系統造成影響。在子系統模塊內部，各任務用RM算法來調度。如無線閉塞中心（RBC）中的列車注冊、列車注銷和行車許可（MA）生成3個任務，每個任務可能不會每個周期都要運行一次，用RM調度算法[2]可提高資源的利用率。這樣既實現了設備的集成，又保證了安全性，同時提高了資源的利用率。

當時間上具有確定性以后，為了提高系統的安全性和可靠性，需要在空間上也具有確定性，即對內存分配進行管理[7]。時間確定性表示方法如圖1所示。

本文將內存分為系統內存區、任務代碼區、任務結果保留區、內存分塊區和I/O內存區。

基于時間觸發機制的安全相關軟件內存分配模型如圖2所示。

對本文來說，重點在于內存分塊區的分配，采用一種循環分配法，可以在滿足任務正常運行的內存需要的同時，有效提高內存利用率。

下面本文將分別闡述時間參數（總周期和各子系統隔離時間）和空間參數（各子系統隔離內存大小）的確定方法。

圖1 時空確定性

圖2 安全相關軟件內存分配模型圖

2 時間參數的確定方法

時間參數有兩個，即分配給每個子系統的隔離時間和每個程序執行所需時間，前者可以通過后者計算出來，而后者可利用軟件測試的方法和VXWORKS的特性來確定。由于VXWORKS操作系統具有良好的實時性、優秀的集成開發環境，是功能強大的分析工具，在本文中選用它作為開發平臺。

2.1 程序執行時間的確定

在以前的時間觸發方法中，分配給各任務的時間是由主觀經驗或不斷試驗得到的，沒有統一的方法。本文使用軟件測試中的方法，可較精確地測得各任務的執行時間，按此分配時間可提高系統的效率。

軟件測試中有一種基于路徑的測試，重點在于研究出一組輸入，使得可遍歷一條指定的路徑。在本文的研究中，由于程序比較簡單，可列出程序中所有的路徑，得出各自的輸入，再在VXWORKS系統中得到執行每條路徑所需的時間，從中選取最大值作為分配給程序的時間。若程序復雜，不能列出所有路徑，也可只測試最重要的幾條路徑，同時在程序中加入超時處理機制。

面向路徑的測試數據自動生成方法有隨機法，靜態法，動態法和試探法等。其中隨機法又包括符號執行，區間算術法；動態法包括直線式程序法，松弛迭代法，試探法包括遺傳算法，模擬退火算法等。比較約束完備性、實現復雜性、效率和工具支持等方面后，選定松弛迭代法[4]作為本文使用的方法。

2.2 VXWORKS中測量指定路徑的執行時間

在VXWORKS中提供了豐富的時間操作功能，獲得時間的方法主要有系統時鐘，看門狗定時器，時間戳，tickGet()函數等方法[5]，經過方便性和準確性各方面的衡量，如表1所示，選擇tickGet()函數測量系統時鐘來確定時間。

表1 時間測量方法比較

在VXWORKS中，tick指的是時鐘中斷的頻率，tick為100表示每秒鐘時鐘中斷100次。通過sysClkRateGet()函數可以得到當前的tick數，如果不滿意可以使用sysClkRateSet()函數來修改，系統中默認的是60，即1/60=16.67 ms為一個tick，若設為1 000則一個tick剛好為1 ms。

通過上述方法可知指定路徑的輸入，在路徑入口處加入tickGet()函數來得到當前值tick1，出口再加入tickGet()來得到一個值tick2，加上此前由sysClkRateGet()得到的值clkRate，計算(tick2-tick1)/clkRate即可得到經過測試路徑所需的時間。對每條路徑反復執行上述步驟即可得到所有路徑各自所需的時間，從中選擇最大值作為任務的最壞執行時間。

2.3 隔離時間的確定

設有一個任務集S＝{t1, t2, t3,……, tn}，其中ti（1≤i≤n）都是周期任務，每個任務可用式（1）表示：

其中，Ci表示任務的最大計算時間，Di表示任務的時限，Ti表示任務的周期[6]。

假設分配給子系統k的處理器能力是αk，此時各任務的處理時間變為

定義1：

表示此時[0,t]時間內處理優先級高于或等于i的所有任務的時間。

定義2：

表示[0,Di]時間內運行完優先級大于等于i的任務所剩余的時間，其中Ei={kTj|j=1, 2,…, |Ti/ Tj|}。

定義3：

關鍵參數αk和ηk可用式（5）、式（6）求出：

這里求出的ηk就是子系統k的周期，αk是分配給子系統k的處理器能力。取min(k)ηk作為隔離時間，乘以αk就是分配給子系統k的時間[3]。

3 內存管理機制

對任務集R={γi|1≤i≤m}（m表示系統含有m個任務，γi表示第i個任務）的內存集 {Mi|1≤i≤m}，該內存集主要是用于存儲任務運行過程中的一些中間數據和程序或者用于存儲需要進行通信的數據。Min{Mi|1≤i≤m}取出最小的任務內存Mmin，以Mmin大小為內存塊的基本單位，將內存劃分為若干內存塊，以后系統分配內存時都是以該內存塊大小為基本單位進行連續的分配。當分配到最后時再返回頭部重新開始。

內存分配算法描述：

（1）已知任務內存集合{Mi|1≤i≤m}為任務正常運行時所需要的內存大小，已經經過適當的放大處理，使得每個任務都能在對應大小的內存中正常運行。

（2）令?M=Min{Mi|1≤i≤m}，取出最小任務內存記為?M。

（3）以?M為基準對內存集{Mi|1≤i≤m}進行歸一化處理，任務τi的內存Mi進行歸一化處理后的結果是ni。定義ni=[Mi/?M]，處理后的結果為{ni|1≤i≤m} 。

（4）計算

取最大值N=Max{ni+ni+1}。

（5）計算出所需內存的總大小為L=?M·N，劃分成N個?M大小的內存塊。

根據該算法，可以減少對內存的浪費。例如某安全設備具有4個任務，所需內存分別為100 k，150 k，50 k，200 k。根據循環內存分配法，只需要300 k的內存，而傳統的靜態內存分配法則需要500 k，由此可以看到該內存分配法可以減少內存的使用。

4 在CTCS-3列控軟件中的應用

為了說明問題，本文僅使用簡化的RBC、列車控制中心（TCC）、TSRS進行集成。其中RBC由3個任務組成：列車注冊、列車注銷和MA生成。TCC有一個任務：發送調度信息。TSRS由兩個任務組成：臨時限速提示激活和重復提示。

根據文獻[9]，若RBC從CTC接受的消息包含反饋請求，則RBC應在1 000 ms內向CTC發送一條包含反饋碼的反饋消息。若RBC接受一條CTC命令，則RBC應在1 000 ms內響應該命令。而最壞情況是上一周期剛開始接收到的命令要在下一周期才能進行處理，因此選取RBC的周期為1 000/2=500 ms。

根據文獻[10]，臨時限速服務器應根據臨時限速調度命令提前一定時間（30 min）提示調度員進行激活，并可間隔一定時間（10 min）重復提示直至確認或超出該限速命令計劃結束時間。相比其他任務，10 min的周期太長，為簡便起見，設定為1 s（不代表實際情況，只是為了說明問題）。類似的，設定列控中心的周期為600 ms。

用前文所述的方法測得各個任務的最壞執行時間，得到表2。

表2 子系統任務執行時間

為了在RM算法中區分優先級（Ti越小優先級越高），表2中子系統中的各任務周期適當縮小。

根據RM可調度性判定[2]，若滿足：

則任務集S可由RM算法調度。

根據表2：

ρ1=20/400+20/450+60/500≈0.22，L(3)=0.78，ρ2=8/600≈0.02，L(1)=1，ρ3=5/900+8/1000≈0.02，L(2)=0.83，各子系統可用RM調度。

由式（8）：

計算α1min=0.22/(3×(21/3-1))=0.28，α2min=0.02，α3min=0.02。

在保證Σαk＜1的情況下，可適當放大α，這里取α1=0.5，α2=0.1，α3=0.1。計算出αk，即可算出相應的ηk。

取ηk中的最小值可知周期是440 ms，一個周期內分配給RBC的時間為440×0.5=220（ms），分配給TCC的時間為440×0.1=44（ms），分配給TSRS的時間為440×0.1=44（ms)。

利用VXWORKS集成開發環境WorkBench的memory analyzer工具，可知每個子系統的最大內存使用情況，測得表3。

表3 子系統內存占用

根據內存分配算法，放大到20 kB，40 kB，10 kB。選取min{Mi}=10 kB，計算ni={2,4,1}，max{ni+ni+1}=max{6,5,3}=6，則所需全部內存為6×10=60(kB)。

從時間和空間兩方面都知道具體分配參數后，就可以編程實現,編程結果如圖3所示。

圖3 編程結果

5 結束語

本文利用時空分區的原則，提出了一套列控軟件的集成方法：（1）確定程序的最壞執行時間；（2）計算出總周期和各子系統的隔離時間；（3）按照所需內存安排靜態內存分配。這樣，處理后的程序在時間和空間上都有良好的確定性，保證了較好的安全性。

需要進一步研究的工作是：（1）需要研究對多核處理器的優化方法；（2）當程序很大、分支很多的時候測試每條路徑的執行時間幾乎是不可能的，需要一種更先進的方法；（3）本文計算執行時間依賴于VXWORKS操作系統的實時性，需要研究平臺通用的方法。

[1]謝克嘉.ARINC653規范與機載實時操作系統發展趨勢[C].全國抗惡劣環境計算機第十四屆學術年會論文集，2004：56-58.

[2]王永吉，陳秋萍. 單調速率及其擴展算法的可調度性判定[J]. 軟件學報，2004，15（6）.

[3]楊仕平.分布式任務關鍵實時系統的防危（Safety）技術研究[D].成都：電子科技大學，2004.

[4]Gupta N, Mathur A P, Soffa M L. Automated test data genera tion using an iterative relaxation method[J]. ACM SIGSOFT Software Engineering Notes. ACM, 1998, 23(6): 231-244.

[5]程敬原. VxWorks 軟件開發項目實例完全解析[M]. 北京：中國電力出版社，2005.

[6]Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM (JACM), 1973, 20(1): 46-61.

[7]李慧璐.對VxWorks中內存管理和定時器模塊的改進[D].西安：西安電子科技大學，2009.

[8]徐曉光，葉 宏.分區間通信在航空電子系統中的設計與實現[J].航空計算技術，2005，35（1）： 45-47.

[9]中華人民共和國鐵道部. 無線閉塞中心(RBC)技術規范[S]. 北京：中華人民共和國鐵道部，2009，10.

[10]中華人民共和國鐵道部. 科技運[2008]151號—客運專線列控系統臨時限速技術規范[S]. 北京：中華人民共和國鐵道部，2008.

責任編輯 楊利明

Method of train control software integration based on principle of temporal and spatial isolation

JING HAO1,2, MA Lianchuan1,2
( 1. National Engineering Research Center of Rail Transportation Operation and Control System, Beijing Jiaotong University, Beijing 100044, China; 2. School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing 100044, China )

This paper discussed the problem that CTCS-3 devices faced about hardware resources waste, communication complexity and fault-prone. The thought of temporal and spatial isolation in ARINC 653 was referenced. The aim was to perform that a single device integrated the fuction of multiple devices, improved eff i ciency and reliability. The paper used two-level scheduling structure in the discussion, calculated routine running time according to characteristics of VXWORKS Operation System, determined the isolating time, implemented IDE tools to calculate memory size, then determin the size of isolating space. An example was used to prove the correctness of the method.

temporal and spatial isolation; Rate Monotonic(RM) Dispatching Algorithm; isolating time; isolating space; CTCS-3

U84.482∶TP39

：A

1005-8451（2014）06-0001-05

2013-11-26

景 浩，在讀碩士研究生；馬連川，副教授。