高速緩存影響的航天器控制軟件調(diào)度設(shè)計(jì)方法*

于廣良，楊孟飛，姜 宏，徐 建

(1.北京控制工程研究所，北京100190;2.中國空間技術(shù)研究院，北京100094)

高速緩存影響的航天器控制軟件調(diào)度設(shè)計(jì)方法*

于廣良1，楊孟飛2，姜 宏1，徐 建1

(1.北京控制工程研究所，北京100190;2.中國空間技術(shù)研究院，北京100094)

針對高速緩存引起的程序執(zhí)行時間抖動對航天器控制軟件任務(wù)調(diào)度造成的困難，提出一種基于循環(huán)調(diào)度的調(diào)度設(shè)計(jì)方法，該方法利用任務(wù)程序執(zhí)行時間的概率分布設(shè)計(jì)具有不同可靠性的系統(tǒng)模式，通過模式切換，使處理器得到充分利用，同時能夠提供一定的可靠性保障，為航天器控制軟件的任務(wù)調(diào)度提供參考.

高速緩存;時間分析;調(diào)度設(shè)計(jì);航天器控制軟件

0 引言

目前隨著航天器控制系統(tǒng)集成程度的提高和功能性能要求的不斷增加，對計(jì)算資源的需求也越來越高，控制計(jì)算機(jī)作為控制系統(tǒng)的核心部件，也向著更為復(fù)雜的方向發(fā)展.為解決主存儲器與處理器(CPU)的速度匹配問題，根據(jù)局部性原理，通過速度更快的高速緩存(cache)來提高存儲器的訪問速度越來越重要.但是對航天器控制系統(tǒng)這種對實(shí)時性要求特別高的系統(tǒng)而言，cache的使用增加速度的同時也帶來了很高的時間不確定性，造成設(shè)計(jì)與驗(yàn)證的困難［1］.

Cache對執(zhí)行時間的影響概括為兩方面:一是增大了程序執(zhí)行時間的抖動;二是增加了搶占導(dǎo)致的時間延遲.文獻(xiàn)［2］綜述了程序的最差執(zhí)行時間(worst-case execution time，WCET)分析的方法與工具，其中包含了cache分析的相關(guān)內(nèi)容，呂鳴松等［3］詳細(xì)綜述了WCET分析中的cache分析的方法與進(jìn)展.關(guān)于cache相關(guān)的搶占延遲(cache related preemption delay，CRPD)也有著廣泛的研究［4-5］.

Cache對姿態(tài)和軌道控制系統(tǒng)軟件執(zhí)行時間的影響，在文獻(xiàn)［6］中進(jìn)行了分析，其中指出由于影響cache命中率的因素非常之多，對星載軟件實(shí)時性能的驗(yàn)證是一個難題.文獻(xiàn)［7］設(shè)計(jì)了一種用于航天器使用的LEON3處理器的性能檢測單元，可以用來實(shí)時統(tǒng)計(jì)cache的命中情況，用于cache的設(shè)計(jì)與決策.本文結(jié)合cache的時間特性對調(diào)度設(shè)計(jì)方法進(jìn)行研究，提出應(yīng)對策略，為工程應(yīng)用提供參考.

1 問題分析

在開源的LEON3處理器平臺下分別采用以下幾種cache配置，對某航天器控制軟件的任務(wù)和中斷的執(zhí)行時間進(jìn)行仿真.

Cache的使能:1)禁止cache;2)在第一次控制周期中斷后，將cache中內(nèi)容鎖定，不再更新;3)在每次進(jìn)入中斷時凍結(jié)cache，在中斷退出后重新使能cache;4)完全使能cache.

Cache的大小:A)指令cache為2組，8kbytes大小，每行32bytes，數(shù)據(jù)cache為4組，4kbytes大小，每行16bytes;B)指令cache為2組，4kbytes大小，每行32bytes，數(shù)據(jù)cache為2組，4kbytes大小，每行32bytes.

Cache的替換策略:a)采用偽隨機(jī)策略;b)采用最近最少使用策略(least-recently-used，LRU).

用Task1表示姿態(tài)控制任務(wù)，Task2表示遙測遙控任務(wù)，Timer表示系統(tǒng)定時器中斷，UART表示串口中斷.它們的程序規(guī)模(指令數(shù))大約為Task1是4 000，Task2是20 000，Timer和UART是300.執(zhí)行時間仿真結(jié)果見表1～2所示.

表1 執(zhí)行時間的抖動大小比率Tab.1 Ratios of execution time jitters

表2 最差執(zhí)行時間的相對大小比率Tab.2 Relative ratios of WCETs

表1表示的是執(zhí)行時間的抖動(任務(wù)的執(zhí)行時間中包含了定時器中斷的執(zhí)行時間)的仿真結(jié)果，抖動大小比率的計(jì)算公式采用(Ci-Cbi)/Cbi× 100%，其中Cbi為最優(yōu)執(zhí)行時間，Ci為最差執(zhí)行時間.表2表示的是各情況下的最差執(zhí)行時間與不使能cache的最差執(zhí)行時間的相對比值.兩表中表頭的“禁止”、“鎖定”、“凍結(jié)”、“使能”分別對應(yīng)情況4+情況A+情況a;“LRU”表示的是情況4+情況A+情況b;“大小”表示的是情況4+情況B+情況b.仿真結(jié)果分析如下:

對比表1的“使能”與“禁止”兩列，可以看出，使能cache后程序規(guī)模較小的中斷服務(wù)程序的執(zhí)行時間抖動明顯加大，最大抖動已經(jīng)達(dá)兩倍以上.究其原因，一方面其程序規(guī)模較小，自身執(zhí)行很難將cache預(yù)熱;另一方面，其到達(dá)的隨機(jī)性較高，每次到達(dá)時處理器狀態(tài)相差較大，這點(diǎn)從UART中斷與Timer中斷的對比可以看出，相比于 Timer中斷，UART中斷到達(dá)隨機(jī)性更高，抖動也更大.使能cache后程序規(guī)模較大的任務(wù)執(zhí)行時間抖動很小，是因?yàn)檠h(huán)調(diào)度任務(wù)間無搶占，而且相對執(zhí)行順序固定，減小了對cache的擾動.但不能說明cache對任務(wù)程序執(zhí)行時間影響小，這點(diǎn)從表2的“使能”一列仿真結(jié)果可以證明，任務(wù)在使能cache后最差執(zhí)行時間明顯減小，已降低到禁止cache時最差執(zhí)行時間的一半以內(nèi).

從兩表各自的“鎖定”一列結(jié)果可以看出，cache內(nèi)容鎖定后，經(jīng)常不命中會增加懲罰，使執(zhí)行時間變大.從兩表各自的“凍結(jié)”一列結(jié)果可以看出，采用中斷時凍結(jié)cache可以減小執(zhí)行時間的抖動，但是可能增大中斷的執(zhí)行時間.從兩表各自的“使能”、“LRU”和“大小”幾列的結(jié)果對比可得，cache的不同大小和替換策略都會影響執(zhí)行時間的大小和抖動.

任務(wù)執(zhí)行時間的抖動變大使得最差執(zhí)行時間與平均執(zhí)行時間相差變大，由于航天器控制系統(tǒng)多采用最差情況進(jìn)行調(diào)度設(shè)計(jì)，那么它將導(dǎo)致系統(tǒng)運(yùn)行時的資源利用率變小.

2 系統(tǒng)模型

2.1 任務(wù)模型

采用文獻(xiàn)［8］的衛(wèi)星控制系統(tǒng)時序模型，控制周期T是系統(tǒng)級設(shè)計(jì)目標(biāo)，分解為

式中:t1為所有敏感器信息采集和處理時間;t2為控制算法執(zhí)行時間;t3為所有控制命令發(fā)送時間;t4為單個控制周期內(nèi)所有可能發(fā)生的中斷時間;t5為空閑時間.為了簡化分析過程，忽略了所有的上下文切換和其他非控制任務(wù)，但是它們可以用類似的方法加入到分析和設(shè)計(jì)中.上面各時間還可以進(jìn)一步分解，將與cache相關(guān)的時間提取出來，分別用任務(wù)程序模型τ1，τ2和τ3以及中斷服務(wù)程序模型I1和I2表示.其中τ1代表敏感器信息采集和處理任務(wù)程序，τ2代表控制算法實(shí)現(xiàn)任務(wù)程序，τ3代表控制指令發(fā)送任務(wù)程序，I1代表偶發(fā)性的總線中斷服務(wù)程序，I2代表周期性的時鐘中斷服務(wù)程序.它們的執(zhí)行時間是(1)中相對應(yīng)的時間或者其時間的一部分.

我們定義任務(wù)的最差執(zhí)行時間為所有可能的情況中，任務(wù)程序在對應(yīng)的硬件平臺上執(zhí)行時花費(fèi)的最長時間.最優(yōu)情況下的執(zhí)行時間定義為任務(wù)的最優(yōu)執(zhí)行時間，平均情況下的執(zhí)行時間定義為任務(wù)的平均執(zhí)行時間.任務(wù)的最差響應(yīng)時間定義為任務(wù)從釋放到執(zhí)行結(jié)束的最長時間，其中包含了其他任務(wù)或中斷的搶占時間.類似的，我們定義中斷的最差響應(yīng)時間為從中斷觸發(fā)到處理結(jié)束所需要的最長時間.

特別的，搶占可能會將對任務(wù)或中斷服務(wù)程序有用的高速緩存塊驅(qū)逐出高速緩存，導(dǎo)致重新運(yùn)行任務(wù)或中斷服務(wù)程序時這些高速緩存塊需要從內(nèi)存中重新加載，這段重新填充cache中被驅(qū)逐的存儲塊所需的額外時間稱為cache相關(guān)的搶占延遲［5］.

2.2 調(diào)度模型

航天器控制系統(tǒng)的周期性任務(wù)調(diào)度經(jīng)常采用循環(huán)調(diào)度(cyclic executive，CE)［9］.調(diào)度決策是靜態(tài)的，離線計(jì)算好之后保存在表格之中.以控制周期為主周期被反復(fù)執(zhí)行.控制周期內(nèi)再分為許多小時間段，稱為幀或次周期.每個幀有一個在其內(nèi)部執(zhí)行的任務(wù)列表，幀的起始由時鐘中斷觸發(fā)，并在中斷服務(wù)程序中釋放幀內(nèi)各個任務(wù)依次執(zhí)行，下一幀的起始時刻作為本幀的結(jié)束時刻，它也是本幀內(nèi)任務(wù)的相對截止時間限.本文任務(wù)模型采用循環(huán)調(diào)度如圖1所示.

假定控制計(jì)算機(jī)使用單處理器，使用下述符號定義:控制周期記為T，也是各控制任務(wù)的周期.中斷I1的最小到達(dá)時間間隔記為TI1，中斷I2的周期記為TI2.中斷I1的優(yōu)先級高于中斷I2.我們使用下標(biāo)τ或I來區(qū)分任務(wù)和中斷.定義任務(wù)τi的最差執(zhí)行時間為Cτi，最優(yōu)執(zhí)行時間為Cbτi，平均執(zhí)行時間為Caτi，相對截止時間限為Dτi，最差響應(yīng)時間為Rτi.定義時鐘滴答為tc(兩次時鐘中斷的最小時間間隔)，幀長度是整數(shù)倍時鐘滴答的時間，各任務(wù)的幀長度定義為qi.定義任務(wù)τi執(zhí)行期間任務(wù)τj對其搶占造成的CRPD為γτi，τj，中斷Ij對其搶占造成的CRPD為 γτi，Ij.

圖1 循環(huán)調(diào)度策略示意圖Fig.1 Example of CE

3 時間分析

固定優(yōu)先級搶占式調(diào)度下，任務(wù)τi最差響應(yīng)時間的計(jì)算使用如下公式［10］:

其中·為向上取整運(yùn)算，hp(i)為優(yōu)先級高于i的任務(wù)，上面等式一般通過迭代求解，直到收斂或響應(yīng)時間超過截止時間限()為止，上標(biāo)n為迭代次數(shù).

式(2)中，沒有考慮高優(yōu)先級任務(wù)嵌套搶占時對低優(yōu)先級任務(wù)造成的間接影響.例如優(yōu)先級低于τj但高于τi的任務(wù)也會被τj搶占，搶占后同樣產(chǎn)生CRPD，進(jìn)而對τi響應(yīng)時間有間接影響.文獻(xiàn)［11］采用了γsum代表由于τj搶占造成的總的搶占延遲.改進(jìn)的τi最差響應(yīng)時間計(jì)算公式如下:

關(guān)于γ的計(jì)算可以參考相關(guān)文獻(xiàn)［4-5，10-11］，本文不展開討論.利用上述公式，可以推導(dǎo)出本文所述模型的響應(yīng)時間計(jì)算公式.

為了保證中斷不丟失數(shù)據(jù)，一般要求同一中斷的處理時間要小于其最小到達(dá)時間間隔，即RIi＜TIi.對中斷進(jìn)行時間分析時，重點(diǎn)需要考慮的是中斷嵌套情況［12］.在本文中，由于中斷I1的優(yōu)先級大于中斷I2，故中斷I2在執(zhí)行過程中可能被I1搶占，系統(tǒng)禁止 cache時，兩個中斷的最差響應(yīng)時間分別為:

系統(tǒng)使能 cache時，如果選擇在中斷時凍結(jié)cache，有利于減小中斷的執(zhí)行時間抖動同時避免CRPD，但中斷的最差執(zhí)行時間可能比禁止cache時更長，兩個中斷的最差響應(yīng)時間分別為

系統(tǒng)在任何時候cache都使能，則中斷1搶占中斷2后，將伴隨有CRPD產(chǎn)生，在時間分析時需要考慮在內(nèi)，兩個中斷的最差響應(yīng)時間分別為

任務(wù)程序最差響應(yīng)時間的計(jì)算應(yīng)該考慮中斷的搶占，禁止cache時，任務(wù)的最差響應(yīng)時間為

使能cache，但是在中斷時凍結(jié)cache，任務(wù)的最差響應(yīng)時間為

始終使能cache，需要考慮中斷搶占任務(wù)程序后帶來的CRPD，任務(wù)的最差響應(yīng)時間為

任務(wù)必須滿足可調(diào)度性要求，即它每次釋放的實(shí)例都能在截止時間限之前完成，有Rτi≤Dτi.在設(shè)計(jì)循環(huán)調(diào)度的調(diào)度表時，分配給各個任務(wù)的幀長度應(yīng)該大于等于任務(wù)的最差響應(yīng)時間.由于任務(wù)由時鐘中斷釋放，故幀的長度與時鐘滴答是整數(shù)倍關(guān)系，則任務(wù)τi的幀長度應(yīng)設(shè)計(jì)為.這樣由(1)可得，控制周期為

4 調(diào)度設(shè)計(jì)

任務(wù)對資源的需求體現(xiàn)為對CPU時間的競爭.本文模型在一個控制周期T內(nèi)有3個控制任務(wù)，用ci表示任務(wù)τi的實(shí)際執(zhí)行時間，則系統(tǒng)運(yùn)行時，任務(wù)τi的資源需求可用其實(shí)際的利用率Ui=ci/T來度量.令則所有任務(wù)總的利用率為U= c/T.

任務(wù)的執(zhí)行時間滿足 Cbi≤ci≤Ci，令 cLB=可得任務(wù)總的執(zhí)行時間滿足關(guān)系cLB≤c≤cUB.任務(wù)必須滿足可調(diào)度的要求，這便要求最差情況下，任務(wù)總的利用率必須小于某一上限，即cUB/T≤UUB≤1，則有:

可見，任務(wù)的實(shí)際執(zhí)行時間與最差執(zhí)行時間差距越大，系統(tǒng)的利用率越低.如第1節(jié)所述，使能cache后，最差情況與平均情況相差較大.如果按照最差情況設(shè)計(jì)任務(wù)調(diào)度，那么系統(tǒng)在大部分時間資源利用率很低.如果以平均情況設(shè)計(jì)任務(wù)調(diào)度，可以提高資源利用率，但是可能有任務(wù)超時.綜合這兩種情況，我們利用任務(wù)執(zhí)行時間的概率分布(可以通過統(tǒng)計(jì)或分析的方法得到)，設(shè)計(jì)具有不同資源利用率和可靠性的系統(tǒng)模式，用于調(diào)度選擇.

由于系統(tǒng)沒有按照最差情況進(jìn)行設(shè)計(jì)，那么必須應(yīng)對可能發(fā)生的任務(wù)超時，通過設(shè)計(jì)系統(tǒng)的模式切換來實(shí)現(xiàn).例如設(shè)計(jì)兩種模式，第一種模式下，采用最差情況(Cτi)進(jìn)行設(shè)計(jì)，有概率δτi=1;第二種模式下，采用平均情況(Caτi)進(jìn)行設(shè)計(jì)，有概率δτi＜1.首先令系統(tǒng)運(yùn)行在第二種模式下，如果有任務(wù)超時，則進(jìn)行模式切換，切換到第一種模式.若任務(wù)一直運(yùn)行在平均情況以內(nèi)，將持續(xù)處于第二種模式，從而提高了資源利用率.

舉例說明所述方法，假設(shè)系統(tǒng)中cache始終使能，任務(wù)和中斷的時間參數(shù)如表3所示，單位為處理器的指令周期數(shù)×104，tc=TI2.

表3 系統(tǒng)的任務(wù)和中斷參數(shù)Tab.3 Task and interrupt parameters of the system

利用式(6)和式(9)計(jì)算得到任務(wù)和中斷的最差響應(yīng)時間，然后利用式(10)計(jì)算得到幀大小和控制周期大小.注意對于CRPD的計(jì)算，我們忽略了間接的搶占延遲，采用了式(2).

表4 時間計(jì)算結(jié)果Tab.4 Time calculation results

利用表4中的q1和q0.95可以計(jì)算得到第一種模式下，控制周期，任務(wù)不發(fā)生超時的概率P1=100%;第二種模式下，控制周期，任務(wù)不發(fā)生超時的概率為P2≥0.953×100%≥85.74%.假設(shè)滿足控制精度要求的控制周期范圍是 T=0.1 s～0.15 s，那么令T2=Tmin=0.1 s，可以求得所需CPU的主頻為f=8 MHz，在此主頻下，第一種模式下的控制周期 T1=(1.05×106)/(8×106)s= 0.131 25 s＜0.15 s，滿足設(shè)計(jì)要求.第二種模式和第一種模式相比，CPU利用率提高了(U2-U1)/U1=(T1-T2)/T2=31.25%.

5 結(jié)論

本文給出了一種高速緩存影響的航天器控制軟件任務(wù)調(diào)度設(shè)計(jì)方法.該方法基于循環(huán)調(diào)度策略，利用任務(wù)程序執(zhí)行時間的概率分布，設(shè)計(jì)具有不同可靠性的系統(tǒng)模式，在保證系統(tǒng)較高資源利用率的同時，提供一定的可靠性保障.

［1］楊孟飛，顧斌，郭向英，等.航天嵌入式軟件可信保障技術(shù)及應(yīng)用研究［J］.中國科學(xué):技術(shù)科學(xué)，2015，45 (2):198-203.YANG M F，GU B，GUO X Y，et al.Aerospace embedded software dependability guarantee technology and application［J］.Sci Sin Tech，2015，45(1):198-203.

［2］WILHELM R，ENGBLOM J，ERMEDAHL A，et al.The worst-case execution-time problem-overview of methods and survey of tools［J］.ACM Transactions on Embedded Computing Systems，2008，7(3):1-53.

［3］呂鳴松，關(guān)楠，王義.面向WCET估計(jì)的Cache分析研究綜述［J］.軟件學(xué)報(bào)，2014，25(2):179-199.LYU M S，GUAN N，WANG Y.Survey of cache analysis for worst-case execution time estimation［J］.Journal of Software，2014，25(2):179-199.

［4］LEE C G，HAHN J，SE Y M，et al.Analysis of cacherelated preemption delay in fixed-priority preemptive scheduling［J］.IEEE Transactions on Computers，1998，47(6):700-713.

［5］ALTMEYER S，DAVIS，R I，MAIZA C.Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems［J］.Real-Time System，2012，48:499-526.

［6］BERNAT G，COLIN A，ESTEVES J，et al.Considerations on the LEON cache effects on the timing analysis of on-board applications［C］//Proceedings of the Data Systems in Aerospace Conference，2008.

［7］GUZMáN D，PRIETO M，SáNCHEZ S，ALMENA J.Improving the LEON spacecraft computer processor for real-time performance analysis［J］.Journal of Spacecraft and Rockets，2011，48(4):671-678

［8］王磊，袁利，戴居峰.衛(wèi)星控制系統(tǒng)時序建模分析方法研究［J］.空間控制技術(shù)與應(yīng)用，2014，40(3):31-35.WANG L，YUAN L，DAI J F.Timing modeling and analysis method for satellite control system［J］.Aerospace Control and Application，2014，40(3):31-35.

［9］BAKER T P，SHAW A.The cyclic executive model and ada［C］//IEEE Real-Time Systems Symposium.New Yrok:IEEE，1988.

［10］BUSQUETS-MATAIX J V，SERRANO J J，ORS R，et al.Adding instruction cahe effect to schedulability anal-ysis of preemptive real-time systems［C］//Proceedings of the IEEE Real-Time Technology and Applications Symposium.New York:IEEE，1996.

［11］STASCHULAT J，SCHLIECKER S，ERNST R.Scheduling analysis of real-time systems with precise modeling of cache related preemption delay［C］//Proceedings of the 17thEuromicro Conference on Real-Time Systems.Palma de Mallorca，Spain，2005.

［12］于廣良，楊孟飛，徐建，姜宏.面向多級中斷系統(tǒng)的任務(wù)最差響應(yīng)時間分析［J］.中國空間科學(xué)技術(shù)，2016，36(2):28-36.YU G L，YANG M F，XU J，et al.Worst case response time analysis of multilevel interrupt systems［J］.Chinese Space Science and Technology，2016，36(2):28-36.

Scheduling Design Method for Spacecraft Control Software with Cache

YU Guangliang1，YANG Mengfei2，JIANG Hong1，XU Jian1
(1.Beijing Institute of Control Engineering，Beijing 100190，China; 2.China Academy of Space Technology，Beijing 100094，China)

The task scheduling of spacecraft control software becomes more difficult due to the execution time jitter caused by cache.To deal with this problem，a scheduling design method is proposed based on cyclic executive.The probability distributions of execution times are used to design different system modes with different reliability.Through the mode changes，the processor can be sufficiently utilized and a certain extent degree of reliability is guaranteed.The proposed method can provide useful reference for the task scheduling of spacecraft control software.

cache;timing analysis;scheduling design;spacecraft control software

TP31

A

1674-1579(2017)01-0055-06

10.3969/j.issn.1674-1579.2017.01.009

于廣良(1986—)，男，工程師，研究方向?yàn)楹教烨度胧较到y(tǒng)可信軟件;楊孟飛(1962—)，男，研究員，研究方向?yàn)榭臻g飛行器總體設(shè)計(jì)、控制系統(tǒng)和控制計(jì)算機(jī);姜 宏(1975—)，男，工程師，研究方向?yàn)楹教炱骺刂朴?jì)算機(jī)的軟硬件協(xié)同設(shè)計(jì);徐 建(1987—)，男，工程師，研究方向?yàn)楦呖尚挪僮飨到y(tǒng).

*國家自然科學(xué)基金資助項(xiàng)目(91118007).

2016-04-10