高速緩存影響的航天器控制軟件調度設計方法*

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

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

高速緩存影響的航天器控制軟件調度設計方法*

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

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

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

高速緩存;時間分析;調度設計;航天器控制軟件

0 引言

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

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

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

1 問題分析

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

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

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

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

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

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

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

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

對比表1的“使能”與“禁止”兩列，可以看出，使能cache后程序規模較小的中斷服務程序的執行時間抖動明顯加大，最大抖動已經達兩倍以上.究其原因，一方面其程序規模較小，自身執行很難將cache預熱;另一方面，其到達的隨機性較高，每次到達時處理器狀態相差較大，這點從UART中斷與Timer中斷的對比可以看出，相比于 Timer中斷，UART中斷到達隨機性更高，抖動也更大.使能cache后程序規模較大的任務執行時間抖動很小，是因為循環調度任務間無搶占，而且相對執行順序固定，減小了對cache的擾動.但不能說明cache對任務程序執行時間影響小，這點從表2的“使能”一列仿真結果可以證明，任務在使能cache后最差執行時間明顯減小，已降低到禁止cache時最差執行時間的一半以內.

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

任務執行時間的抖動變大使得最差執行時間與平均執行時間相差變大，由于航天器控制系統多采用最差情況進行調度設計，那么它將導致系統運行時的資源利用率變小.

2 系統模型

2.1 任務模型

采用文獻［8］的衛星控制系統時序模型，控制周期T是系統級設計目標，分解為

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

我們定義任務的最差執行時間為所有可能的情況中，任務程序在對應的硬件平臺上執行時花費的最長時間.最優情況下的執行時間定義為任務的最優執行時間，平均情況下的執行時間定義為任務的平均執行時間.任務的最差響應時間定義為任務從釋放到執行結束的最長時間，其中包含了其他任務或中斷的搶占時間.類似的，我們定義中斷的最差響應時間為從中斷觸發到處理結束所需要的最長時間.

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

2.2 調度模型

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

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

圖1 循環調度策略示意圖Fig.1 Example of CE

3 時間分析

固定優先級搶占式調度下，任務τi最差響應時間的計算使用如下公式［10］:

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

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

關于γ的計算可以參考相關文獻［4-5，10-11］，本文不展開討論.利用上述公式，可以推導出本文所述模型的響應時間計算公式.

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

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

系統在任何時候cache都使能，則中斷1搶占中斷2后，將伴隨有CRPD產生，在時間分析時需要考慮在內，兩個中斷的最差響應時間分別為

任務程序最差響應時間的計算應該考慮中斷的搶占，禁止cache時，任務的最差響應時間為

使能cache，但是在中斷時凍結cache，任務的最差響應時間為

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

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

4 調度設計

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

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

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

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

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

表3 系統的任務和中斷參數Tab.3 Task and interrupt parameters of the system

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

表4 時間計算結果Tab.4 Time calculation results

利用表4中的q1和q0.95可以計算得到第一種模式下，控制周期，任務不發生超時的概率P1=100%;第二種模式下，控制周期，任務不發生超時的概率為P2≥0.953×100%≥85.74%.假設滿足控制精度要求的控制周期范圍是 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，滿足設計要求.第二種模式和第一種模式相比，CPU利用率提高了(U2-U1)/U1=(T1-T2)/T2=31.25%.

5 結論

本文給出了一種高速緩存影響的航天器控制軟件任務調度設計方法.該方法基于循環調度策略，利用任務程序執行時間的概率分布，設計具有不同可靠性的系統模式，在保證系統較高資源利用率的同時，提供一定的可靠性保障.

［1］楊孟飛，顧斌，郭向英，等.航天嵌入式軟件可信保障技術及應用研究［J］.中國科學:技術科學，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］呂鳴松，關楠，王義.面向WCET估計的Cache分析研究綜述［J］.軟件學報，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］王磊，袁利，戴居峰.衛星控制系統時序建模分析方法研究［J］.空間控制技術與應用，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］于廣良，楊孟飛，徐建，姜宏.面向多級中斷系統的任務最差響應時間分析［J］.中國空間科學技術，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—)，男，工程師，研究方向為航天嵌入式系統可信軟件;楊孟飛(1962—)，男，研究員，研究方向為空間飛行器總體設計、控制系統和控制計算機;姜 宏(1975—)，男，工程師，研究方向為航天器控制計算機的軟硬件協同設計;徐 建(1987—)，男，工程師，研究方向為高可信操作系統.

*國家自然科學基金資助項目(91118007).

2016-04-10