馬維綱 馬建峰 黑新宏 曹 源

(1西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,西安 710071)

(2西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,西安 710048)

(3北京交通大學(xué)電子信息工程學(xué)院,北京 100044)

列車運(yùn)行控制系統(tǒng)(列控系統(tǒng))是安全苛求系統(tǒng).列車測速定位系統(tǒng)是列控系統(tǒng)的重要組成部分,其向列控系統(tǒng)輸入的位置和速度參數(shù)需要具備嚴(yán)格的精度、可靠性和實(shí)時(shí)性.多傳感器融合的測速定位是利用不同傳感器的優(yōu)勢,為系統(tǒng)提供更可靠精確的信息.傳感器包括陀螺、電子羅盤、加速度計(jì)、速度傳感器、慣性測量單元、多普勒雷達(dá)、GPS接收機(jī)等.

多傳感器融合系統(tǒng)中傳感器信號(hào)輸入由外部環(huán)境實(shí)時(shí)狀態(tài)觸發(fā).對(duì)于多傳感器融合系統(tǒng)需采用多任務(wù)實(shí)時(shí)調(diào)度.實(shí)時(shí)調(diào)度有事件觸發(fā)和時(shí)間觸發(fā)2種方式.在測速定位系統(tǒng)中時(shí)間觸發(fā)有確定性的優(yōu)勢,能更好地保證實(shí)時(shí)系統(tǒng)安全性,在列車測速定位系統(tǒng)中得到了廣泛的應(yīng)用.時(shí)間觸發(fā)機(jī)制是將時(shí)間軸分割成若干窗口,采用人為分配方式,已知任務(wù)執(zhí)行時(shí)間、截止時(shí)間等信息進(jìn)行時(shí)間窗分配,得到靜態(tài)時(shí)間調(diào)度表,并在靜態(tài)表中分配一定時(shí)間窗來調(diào)度非實(shí)時(shí)任務(wù),在時(shí)標(biāo)間隔到達(dá)時(shí)進(jìn)行超時(shí)檢測并進(jìn)行超時(shí)處理.人為分配具有不確定性,故時(shí)間觸發(fā)機(jī)制的調(diào)度分析尤為重要.

文獻(xiàn)[1]基于單處理器的嵌入式系統(tǒng),提出基于能效和公平的調(diào)度算法,結(jié)果顯示該算法能夠減少能量消耗,但降低了處理器的運(yùn)算速度.文獻(xiàn)[2]提出一種基于調(diào)度表的自適應(yīng)任務(wù)分配調(diào)度算法,結(jié)果顯示該算法能夠提高系統(tǒng)的響應(yīng).文獻(xiàn)[3]提出一種基于CTCS-3列控系統(tǒng)的高層數(shù)據(jù)融合方法,實(shí)現(xiàn)了列控系統(tǒng)關(guān)鍵數(shù)據(jù)的融合,提高了列控的安全性.

Liu等[4]提出一種適用于搶占式實(shí)時(shí)周期任務(wù)調(diào)度的調(diào)度算法,并對(duì)其可調(diào)度性判定進(jìn)行研究.Nicolau[5]針對(duì)固定優(yōu)先級(jí)可搶占任務(wù)調(diào)度給出了任務(wù)請(qǐng)求調(diào)度時(shí)間計(jì)算公式,公式計(jì)算量小,計(jì)算結(jié)果誤差較大.Henderson等[6]給出了截止時(shí)間不大于調(diào)度周期約束下實(shí)時(shí)任務(wù)調(diào)度響應(yīng)時(shí)間的計(jì)算方法,此方法復(fù)雜度較高.Lehoczky等[7]提出了一種通用的實(shí)時(shí)任務(wù)響應(yīng)時(shí)間分析方法,該方法通過時(shí)間需求分析對(duì)調(diào)度模型作了一系列理想的假設(shè),使理想的調(diào)度模型比現(xiàn)實(shí)情況要簡單.Katcher等[8]提出的可調(diào)度分析方法利用最壞響應(yīng)時(shí)間進(jìn)行分析,能作為充分判定條件,不能用于相同優(yōu)先級(jí)任務(wù)在初始執(zhí)行順序確定約束條件下的調(diào)度分析.伍微等[9]在此基礎(chǔ)上提出了優(yōu)先級(jí)相同的任務(wù)在初始執(zhí)行順序確定的條件下的調(diào)度算法.

以上研究均考慮了任務(wù)搶占的情況,但是時(shí)間觸發(fā)機(jī)制采用固定優(yōu)先級(jí),故本文研究的是在任務(wù)調(diào)度順序確定的約束下采用的調(diào)度方法.首先,實(shí)時(shí)系統(tǒng)必須具備處理外部事件的功能,這些外部事件隨機(jī)發(fā)生;其次,為避免任務(wù)因掛起導(dǎo)致未完成執(zhí)行,需要在每個(gè)時(shí)標(biāo)間隔到達(dá)時(shí)進(jìn)行超時(shí)檢測.

因此,本文在簡化假設(shè)條件下,考慮到調(diào)度系統(tǒng)應(yīng)具備處理外部事件的功能和執(zhí)行超時(shí)檢測的功能,提出多傳感器融合測速定位系統(tǒng)的調(diào)度模型,并在任務(wù)時(shí)間需求函數(shù)基礎(chǔ)上計(jì)算系統(tǒng)消耗時(shí)間和CPU利用率,提出了關(guān)于時(shí)間觸發(fā)機(jī)制可調(diào)度性的判定定理,從而為時(shí)間觸發(fā)靜態(tài)調(diào)度表的分配提供合適的參數(shù),在保證時(shí)間觸發(fā)機(jī)制安全性基礎(chǔ)上,提高系統(tǒng)利用率.

1 基于時(shí)間觸發(fā)機(jī)制的多傳感器融合系統(tǒng)模型

調(diào)度器通過硬件定時(shí)器實(shí)現(xiàn),硬件定時(shí)器被設(shè)置為產(chǎn)生一個(gè)周期中斷信號(hào),中斷周期又稱作時(shí)標(biāo)間隔.列車測速定位系統(tǒng)包括2個(gè)部分:數(shù)據(jù)采集和數(shù)據(jù)處理.數(shù)據(jù)采集通過不同串口完成多個(gè)傳感器數(shù)據(jù)采集任務(wù);數(shù)據(jù)處理將采集數(shù)據(jù)融合處理,得到速度和定位信息.系統(tǒng)對(duì)傳感器信號(hào)有不同的需求,大部分傳感器的信號(hào)獲取、數(shù)據(jù)處理與輸出均是實(shí)時(shí)周期任務(wù),少量傳感器信號(hào)的獲取是軟實(shí)時(shí)非周期任務(wù).

1.1 實(shí)時(shí)周期任務(wù)模型

設(shè)多傳感器融合系統(tǒng)的實(shí)時(shí)周期任務(wù)集為

Γ={τi|1≤i≤n}

式中,n為系統(tǒng)中的周期任務(wù)數(shù);τi為第i個(gè)任務(wù),τi={φi,Ci,Ti,Di},其中,φi為初始就緒時(shí)刻,Ci為任務(wù)i的執(zhí)行時(shí)間,Ti為任務(wù)i的周期,Di為任務(wù)i的截止時(shí)間,即任務(wù)i的最大允許響應(yīng)時(shí)間.

對(duì)于任務(wù)集Γ中的各個(gè)任務(wù)τi,其周期Ti并不相同.系統(tǒng)周期由這些基本循環(huán)周期構(gòu)成,稱為超周期H.時(shí)標(biāo)間隔I選擇為能夠整除系統(tǒng)超周期H,因此I應(yīng)為各任務(wù)周期的公約數(shù),且至少存在i,使I至少可以被任務(wù)Ti的周期Ti整除,即?Ti/I?-Ti/I=0.

1.2 軟實(shí)時(shí)非周期任務(wù)模型

系統(tǒng)中軟實(shí)時(shí)非周期任務(wù)是隨機(jī)發(fā)生的,其在超周期H內(nèi)發(fā)生的概率用分布函數(shù)P(x)模擬.定義軟實(shí)時(shí)非周期任務(wù)為

pj={φj,Cj,Dj}

式中,φj為任務(wù)初始就緒時(shí)刻,由概率分布函數(shù)P(x)決定;Cj為任務(wù)j的執(zhí)行時(shí)間;Dj為軟實(shí)時(shí)非周期任務(wù)j的截止時(shí)間.

超周期中的實(shí)時(shí)周期任務(wù)調(diào)度結(jié)束后,需要預(yù)留一定冗余時(shí)段為動(dòng)態(tài)段,此段定義為l,用于軟實(shí)時(shí)非周期性任務(wù)的調(diào)度.

1.3 超時(shí)檢測模型

時(shí)間觸發(fā)機(jī)制在時(shí)標(biāo)間隔到達(dá)時(shí)進(jìn)行任務(wù)超時(shí)檢測,如果此時(shí)有任務(wù)運(yùn)行,則該任務(wù)由于某些因素未被執(zhí)行完畢,需要進(jìn)行超時(shí)處理.

本文只考慮超時(shí)檢測任務(wù),而不考慮具體的超時(shí)處理方式.定義超時(shí)處理任務(wù)集為

O={ok|1≤k≤n}ok={co,I}

式中,co為超時(shí)檢測需要的時(shí)間;I為定時(shí)器的中斷時(shí)間.

圖1為時(shí)間觸發(fā)機(jī)制調(diào)度算法的實(shí)現(xiàn)框圖.

圖1 基于時(shí)間觸發(fā)機(jī)制的調(diào)度策略

2 時(shí)間觸發(fā)機(jī)制可調(diào)度性分析與驗(yàn)證

首先作如下假設(shè):

1) 實(shí)時(shí)周期任務(wù)請(qǐng)求都具有硬時(shí)限要求,必須在限定的時(shí)限內(nèi)完成.

2) 軟實(shí)時(shí)非周期任務(wù)沒有硬時(shí)限要求,在動(dòng)態(tài)段l調(diào)度,采用固定優(yōu)先級(jí)調(diào)度算法.

3) 任務(wù)在運(yùn)行中不會(huì)被其他任務(wù)打斷,但可被定時(shí)器中斷.

4) 每個(gè)任務(wù)的運(yùn)行時(shí)間恒定.

5) 調(diào)度和任務(wù)切換的時(shí)間忽略不計(jì).

定理1對(duì)實(shí)時(shí)周期任務(wù)集Γ={τi|1≤i≤n}中的任務(wù)Ti,保證其在釋放后能夠在截止時(shí)間前得到調(diào)度,即滿足

φi+Ci≤φi+Di≤φi+1

(1)

則此任務(wù)可以調(diào)度.

證明在基于時(shí)間觸發(fā)機(jī)制的系統(tǒng)中,任務(wù)基于已確定的調(diào)度表調(diào)度,任務(wù)優(yōu)先級(jí)已確定,其釋放時(shí)間到達(dá)就可以得到調(diào)度,任務(wù)的執(zhí)行時(shí)間Ci即任務(wù)響應(yīng)時(shí)間Wi(t),是從任務(wù)釋放到完成的時(shí)間.只需在任務(wù)釋放時(shí)滿足Wi(t)

定理2對(duì)軟實(shí)時(shí)非周期任務(wù)集P={pj|1≤j≤n},任務(wù)釋放并在超周期結(jié)束前完成調(diào)度,則此任務(wù)即可調(diào)度.對(duì)任務(wù)集P,其在動(dòng)態(tài)段內(nèi)按照固定優(yōu)先級(jí)在調(diào)度表中進(jìn)行排列,假設(shè)任務(wù)pj在時(shí)刻t調(diào)度并完成,實(shí)現(xiàn)調(diào)度需滿足t

其中

u′(k)=1的概率為

p(u′(k)=1)=P(φ(k)≤t)

(2)

證明略.

在調(diào)度過程中必須保證實(shí)時(shí)周期任務(wù)能夠滿足時(shí)限約束的條件.任務(wù)調(diào)度處理過程是先調(diào)度實(shí)時(shí)周期任務(wù),再考慮調(diào)度軟實(shí)時(shí)非周期任務(wù).軟實(shí)時(shí)非周期任務(wù)以一定的概率得到調(diào)度.

U=UΓ+UP+Uo+Uc≤1

(3)

定理4對(duì)于實(shí)時(shí)周期任務(wù)集Γ={τi|1≤i≤n},任意時(shí)刻t運(yùn)行的任務(wù)為τi,任務(wù)集在[0,t]間的總響應(yīng)時(shí)間為

其中

對(duì)超時(shí)檢測段,其響應(yīng)時(shí)間為

對(duì)動(dòng)態(tài)段,t時(shí)間內(nèi)動(dòng)態(tài)段占用的時(shí)間為

其中

令W(t)=WΓ(t)+Wo(t)+tl,L(t)=W(t)/t,任務(wù)集可調(diào)度當(dāng)且僅當(dāng)

L(t)≤1

(4)

對(duì)整個(gè)任務(wù)集,保證每個(gè)實(shí)時(shí)周期任務(wù)和超時(shí)檢測任務(wù)在非動(dòng)態(tài)段調(diào)度,則系統(tǒng)即可實(shí)現(xiàn)調(diào)度,即W(t)=WΓ(t)+Wo(t)≤t-tl,令L(t)=W(t)/t,則L(t)≤1,定理得證.

3 多傳感器融合測速定位系統(tǒng)可調(diào)度性判定

為驗(yàn)證基于時(shí)間觸發(fā)機(jī)制的多傳感器融合測速定位系統(tǒng)的可調(diào)度性,在濟(jì)南至連云港鐵路區(qū)段進(jìn)行了現(xiàn)場實(shí)驗(yàn),獲得了有效的數(shù)據(jù)信息,驗(yàn)證了系統(tǒng)的功能.實(shí)驗(yàn)的任務(wù)參數(shù)如表1所示.

表1 系統(tǒng)任務(wù)參數(shù) ms

表1中,任務(wù)1,2,3,4,5,7,8為實(shí)時(shí)周期任務(wù);任務(wù)6為軟實(shí)時(shí)非周期任務(wù);任務(wù)9為超時(shí)檢測任務(wù).系統(tǒng)采用時(shí)間觸發(fā)方式實(shí)現(xiàn)對(duì)任務(wù)的調(diào)度.時(shí)標(biāo)間隔I取50 ms,超周期為1 000 ms.

對(duì)于定理1,各實(shí)時(shí)周期任務(wù)均滿足條件φi+Ci≤φi+Di≤φi+1(1≤i≤9).定理3中,假設(shè)任務(wù)調(diào)度產(chǎn)生的CPU消耗為10%,Uo=c9/I,UP=c6/H,UΓ=U1+U2+U3+U4+U5+U7+U8,則系統(tǒng)總的利用率為U=UΓ+UP+Uo+Uc=0.66≤1,滿足定理3.假設(shè)1 000 ms時(shí)間內(nèi),任務(wù)集總響應(yīng)時(shí)間W(t)=595 ms,L(t)=W(t)/t=595/1 000=0.595<1,滿足定理4.

在軌檢車的數(shù)據(jù)采集和測試過程中,基于時(shí)間觸發(fā)機(jī)制的多傳感器融合測速定位系統(tǒng)能正確獲取傳感器數(shù)據(jù),并在規(guī)定的時(shí)刻能正確輸出列車位置和速度信息,且系統(tǒng)運(yùn)行狀況良好.

4 結(jié)語

本文討論了基于時(shí)間觸發(fā)機(jī)制的多傳感器融合測速定位系統(tǒng)的調(diào)度模型,建立了系統(tǒng)中的實(shí)時(shí)周期任務(wù)、軟實(shí)時(shí)非周期任務(wù)和超時(shí)檢測任務(wù)模型,在任務(wù)時(shí)間需求函數(shù)的基礎(chǔ)上,計(jì)算系統(tǒng)消耗的時(shí)間和CPU利用率,提出了關(guān)于時(shí)間觸發(fā)機(jī)制的可調(diào)度性判定定理.通過判定定理可以改進(jìn)時(shí)間觸發(fā)靜態(tài)調(diào)度表的設(shè)計(jì),為調(diào)度表分配更合理的參數(shù),從而在保證時(shí)間觸發(fā)機(jī)制的可預(yù)測性和安全性基礎(chǔ)上提高系統(tǒng)的利用率.最后通過具體的實(shí)驗(yàn)分析,驗(yàn)證了將時(shí)間觸發(fā)機(jī)制用于此系統(tǒng)中是可行的.后續(xù)工作將考慮優(yōu)化時(shí)間觸發(fā)調(diào)度策略,進(jìn)一步提高系統(tǒng)的利用率.

)

[1] Rukpakavong W, Bull P, Guan Lin,et al. Energy efficient and fairness scheduling of periodic real-time tasks for wireless embedded systems [C]//Computing,CommunicationsandITApplicationsConference. Hong Kong, China, 2013: 111-114.

[2] Ahmed S, Ferri B. Prediction-based asynchronous Cpu-budget allocation for soft-real-time applications[J].IEEETransactionsonComputers. (to appear)

[3] 王俊峰,汪希時(shí). CTCS-3列車控制系統(tǒng)數(shù)據(jù)融合方法研究[J].鐵道學(xué)報(bào), 2012,34(9): 70-74.

Wang Junfeng,Wang Xishi. Research on data fusion of CTCS-3 train control system [J].JournaloftheRailwaySociety, 2012,34(9): 70-74. (in Chinese)

[4] Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real time environment[J].JournalofACM, 1973,20(1): 46-61.

[5] Nicolau G B. Specification and analysis of weakly hard real-time systems [D]. Islas Baleares, Spain: Department de Ciencies Matemaytique I informatica, Universitat delesllles Barlears, 1998.

[6] Henderson W, Kendall D, Robson A. Improving the accuracy of scheduling analysis applied to distributed systems: computing minimal response times and reducing jitter [J].InternationalJournalofReal-TimeSystems, 2001,20(1): 5-25.

[7] Lehoczky J P, Sha L, Ding Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior[C]//Proceedingsofthe10thIEEERealTimeSystemsSymposium. Santa Monica, CA, USA, 1989: 166-171.

[8] Katcher D I, Sathaye S S, Strosnider J K. Fixed priority scheduling with limited priority levels[J].IEEETransactionsonComputers, 1995,44(9): 1140-1144.

[9] 伍微,倪少杰,劉小匯.優(yōu)先級(jí)受限系統(tǒng)中可調(diào)度判定方法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(5):32-35.

Wu Wei, Ni Shaojie, Liu Xiaohui. Schedulability analysis of fixed priority systems with limited priority levels[J].ComputerEngineeringandApplications, 2009,45(5): 32-35. (in Chinese)

[10] Pont M J.Patternsfortimetriggeredembeddedsystems:buildingreliableapplicationswiththe8051familyofmicrocontrollers[M]. Addison-Wesley, 2001: 53-55.