景 浩，馬連川

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

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

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

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

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

時空隔離；RM調(diào)度算法；隔離時間；隔離內(nèi)存；CTCS-3

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

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

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

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

1 兩級調(diào)度結(jié)構(gòu)

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

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

本文將內(nèi)存分為系統(tǒng)內(nèi)存區(qū)、任務代碼區(qū)、任務結(jié)果保留區(qū)、內(nèi)存分塊區(qū)和I/O內(nèi)存區(qū)。

基于時間觸發(fā)機制的安全相關(guān)軟件內(nèi)存分配模型如圖2所示。

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

下面本文將分別闡述時間參數(shù)（總周期和各子系統(tǒng)隔離時間）和空間參數(shù)（各子系統(tǒng)隔離內(nèi)存大?。┑拇_定方法。

圖1 時空確定性

圖2 安全相關(guān)軟件內(nèi)存分配模型圖

2 時間參數(shù)的確定方法

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

2.1 程序執(zhí)行時間的確定

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

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

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

2.2 VXWORKS中測量指定路徑的執(zhí)行時間

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

表1 時間測量方法比較

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

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

2.3 隔離時間的確定

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

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

假設分配給子系統(tǒng)k的處理器能力是αk，此時各任務的處理時間變?yōu)?/p>

定義1：

表示此時[0,t]時間內(nèi)處理優(yōu)先級高于或等于i的所有任務的時間。

定義2：

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

定義3：

關(guān)鍵參數(shù)αk和ηk可用式（5）、式（6）求出：

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

3 內(nèi)存管理機制

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

內(nèi)存分配算法描述：

（1）已知任務內(nèi)存集合{Mi|1≤i≤m}為任務正常運行時所需要的內(nèi)存大小，已經(jīng)經(jīng)過適當?shù)姆糯筇幚?，使得每個任務都能在對應大小的內(nèi)存中正常運行。

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

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

（4）計算

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

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

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

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

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

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

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

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

表2 子系統(tǒng)任務執(zhí)行時間

為了在RM算法中區(qū)分優(yōu)先級（Ti越小優(yōu)先級越高），表2中子系統(tǒng)中的各任務周期適當縮小。

根據(jù)RM可調(diào)度性判定[2]，若滿足：

則任務集S可由RM算法調(diào)度。

根據(jù)表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，各子系統(tǒng)可用RM調(diào)度。

由式（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，一個周期內(nèi)分配給RBC的時間為440×0.5=220（ms），分配給TCC的時間為440×0.1=44（ms），分配給TSRS的時間為440×0.1=44（ms)。

利用VXWORKS集成開發(fā)環(huán)境WorkBench的memory analyzer工具，可知每個子系統(tǒng)的最大內(nèi)存使用情況，測得表3。

表3 子系統(tǒng)內(nèi)存占用

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

從時間和空間兩方面都知道具體分配參數(shù)后，就可以編程實現(xiàn),編程結(jié)果如圖3所示。

圖3 編程結(jié)果

5 結(jié)束語

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

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

[1]謝克嘉.ARINC653規(guī)范與機載實時操作系統(tǒng)發(fā)展趨勢[C].全國抗惡劣環(huán)境計算機第十四屆學術(shù)年會論文集，2004：56-58.

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

[3]楊仕平.分布式任務關(guān)鍵實時系統(tǒng)的防危（Safety）技術(shù)研究[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 軟件開發(fā)項目實例完全解析[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中內(nèi)存管理和定時器模塊的改進[D].西安：西安電子科技大學，2009.

[8]徐曉光，葉 宏.分區(qū)間通信在航空電子系統(tǒng)中的設計與實現(xiàn)[J].航空計算技術(shù)，2005，35（1）： 45-47.

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

[10]中華人民共和國鐵道部. 科技運[2008]151號—客運專線列控系統(tǒng)臨時限速技術(shù)規(guī)范[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

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