于廣良 楊孟飛

1.北京控制工程研究所，北京100191

2.中國空間技術(shù)研究院，北京100094

航天器控制系統(tǒng)要求具有很高的實(shí)時(shí)性和可預(yù)測(cè)性［1-2］。當(dāng)處理器采用SPARC體系結(jié)構(gòu)時(shí)，由于其采用了寄存器窗口機(jī)制，隨時(shí)出現(xiàn)的窗口上下溢陷阱處理引起的時(shí)間開銷對(duì)任務(wù)程序的最差執(zhí)行時(shí)間(WCET，Worst Case Execution Time)［3］有顯著影響，這對(duì)于驗(yàn)證系統(tǒng)的實(shí)時(shí)性約束造成困難。WCET主要用來驗(yàn)證硬實(shí)時(shí)系統(tǒng)中實(shí)現(xiàn)任務(wù)的軟件能否在給定的時(shí)間內(nèi)或給定的時(shí)間點(diǎn)之前執(zhí)行完畢，多數(shù)調(diào)度算法和可調(diào)度性分析算法都需要已知任務(wù)的最差執(zhí)行時(shí)間［4］。對(duì)于提高嵌入式實(shí)時(shí)系統(tǒng)軟件的可靠性來說，WCET有著非常重要的作用。

文獻(xiàn)［5］分析了一個(gè)衛(wèi)星子系統(tǒng)星載軟件的靜態(tài)WCET，其中特別分析了SPARC寄存器窗口機(jī)制的時(shí)間建模方法，給出了如何在任務(wù)的最差執(zhí)行時(shí)間分析中加入窗口上下溢陷阱處理時(shí)間。Bound-T［6］是一個(gè)靜態(tài)WCET分析工具，其針對(duì)SPARC結(jié)構(gòu)提出了一個(gè)建模寄存器窗口的方法，它不僅提供了每個(gè)CALL和RESTORE指令可能產(chǎn)生的上溢和下溢，也提供了在每個(gè)例程入口點(diǎn)可能用到的寄存器窗口數(shù)。但在實(shí)際的系統(tǒng)中，寄存器窗口的上下溢次數(shù)不僅僅取決于任務(wù)程序本身，而且與操作系統(tǒng)和外部中斷等因素緊密相關(guān)，這些因素的變化增加了最差執(zhí)行時(shí)間分析的復(fù)雜性。

本文針對(duì)上述問題，通過分析任務(wù)的函數(shù)調(diào)用關(guān)系圖和系統(tǒng)的中斷嵌套關(guān)系，有效地找出任務(wù)運(yùn)行期間寄存器窗口上下溢陷阱發(fā)生的次數(shù)界限，從而為精確地分析任務(wù)WCET提供幫助。

1 預(yù)備知識(shí)

1.1 SPARC的寄存器窗口機(jī)制

SPARC體系結(jié)構(gòu)［7］定義了2種類型的寄存器:通用寄存器和控制/狀態(tài)寄存器。整數(shù)單元(IU)的通用寄存器又叫做r寄存器，其個(gè)數(shù)與具體實(shí)現(xiàn)相關(guān)，最少為40個(gè)(2組)，最多為520個(gè)(32組)。這些寄存器進(jìn)一步分成8個(gè)全局寄存器和實(shí)現(xiàn)相關(guān)的包含16個(gè)寄存器的寄存器組，1個(gè)寄存器組又分成8個(gè)輸入寄存器和8個(gè)局部寄存器。在某一時(shí)刻，用戶可以訪問8個(gè)全局寄存器和1個(gè)包含24個(gè)寄存器的寄存器窗口，每個(gè)寄存器窗口實(shí)際包含了8個(gè)輸入寄存器和8個(gè)局部寄存器的寄存器組，以及與相鄰窗口的輸入寄存器共用的8個(gè)輸出寄存器。寄存器窗口的結(jié)構(gòu)如圖1所示。

SPARC結(jié)構(gòu)的當(dāng)前寄存器窗口通過當(dāng)前窗口指針CWP來標(biāo)識(shí)，CWP通過RESTORE或者RETT指令遞增，通過SAVE指令或者發(fā)生trap遞減。窗口的上下溢通過窗口無效標(biāo)志寄存器WIM來檢測(cè)。如果嵌套的深度足夠，一系列調(diào)用后，被調(diào)用者可能沒有空閑窗口可用，在那種情況下，SAVE指令試圖使CWP指向WIM中標(biāo)記為無效的窗口，寄存器窗口上溢(overflow)陷阱出現(xiàn)，運(yùn)行的內(nèi)核trap管理程序負(fù)責(zé)提供1個(gè)新的寄存器窗口給例程。同樣，當(dāng)一系列調(diào)用返回時(shí)，原來的窗口也可能不可用，RESTORE或RETT指令試圖使CWP指向WIM中標(biāo)記為無效的窗口，這導(dǎo)致了寄存器窗口下溢(underflow)陷阱產(chǎn)生，內(nèi)核 trap管理程序則進(jìn)行類似處理。

圖1 SPARC寄存器窗口圖解［7］

1.2 最差執(zhí)行時(shí)間分析

程序的最差執(zhí)行時(shí)間(WCET)［8］是指在所有可能的情況中，程序在對(duì)應(yīng)的硬件平臺(tái)上執(zhí)行時(shí)花費(fèi)的最長(zhǎng)時(shí)間。相應(yīng)有程序的最好執(zhí)行時(shí)間(BCET)和平均執(zhí)行時(shí)間(ACET)的概念。WCET給出了某段程序執(zhí)行的時(shí)間上限，評(píng)判其分析方法或者工具好壞的2個(gè)準(zhǔn)則是安全性和精確性:如果分析得到的時(shí)間大于程序的實(shí)際WCET值，稱這種分析結(jié)果是“安全(Safe)”的;分析結(jié)果越接近實(shí)際 WCET 值，稱其越“精確(Precision)”［8］，如圖2所示。尋找程序的WCET有2種主流的方法:靜態(tài)分析方法和基于測(cè)量的方法，代表性的商業(yè)工具有aiT和RapiTime等，在這里不展開闡述。對(duì)于任務(wù)的最差執(zhí)行時(shí)間可以通過上面任意一種方法或工具獲得。

在實(shí)際系統(tǒng)中，程序的最壞情況執(zhí)行時(shí)間是很多因素綜合作用的結(jié)果，影響程序WCET的主要因素有2類:1)是軟件特性，包括程序的循環(huán)界限、執(zhí)行路徑空間和可行性等;2)是平臺(tái)特性，流水線、分支預(yù)測(cè)和寄存器窗口等處理器加速部件及存儲(chǔ)器體系結(jié)構(gòu)等［9］。寄存器窗口陷阱屬于第2類因素，本文考慮的是其對(duì)于任務(wù)WCET的影響。

圖2 最差執(zhí)行時(shí)間定義

1.3 系統(tǒng)模型

本文研究的系統(tǒng)為實(shí)時(shí)系統(tǒng)，假定系統(tǒng)采用固定優(yōu)先級(jí)搶占式調(diào)度，任務(wù)和中斷都具有唯一優(yōu)先級(jí)。系統(tǒng)包含多個(gè)任務(wù)和多級(jí)中斷時(shí)，高優(yōu)先級(jí)任務(wù)可以通過搶占低優(yōu)先級(jí)任務(wù)優(yōu)先運(yùn)行。同時(shí)系統(tǒng)允許中斷嵌套，即在低優(yōu)先級(jí)中斷響應(yīng)期間，如有高優(yōu)先級(jí)的中斷到來，如果此時(shí)中斷被允許，則系統(tǒng)會(huì)響應(yīng)高優(yōu)先級(jí)的中斷，等待高優(yōu)先級(jí)中斷處理完畢再返回到低優(yōu)先級(jí)中斷處理。所有中斷都優(yōu)先于任務(wù)，即任務(wù)運(yùn)行期間，如果有中斷到來，則系統(tǒng)會(huì)首先響應(yīng)中斷，進(jìn)行中斷處理，完畢后再返回到任務(wù)執(zhí)行。中斷可能會(huì)喚醒處于睡眠或掛起狀態(tài)的任務(wù)，使其加入到就緒隊(duì)列，這種情況下，當(dāng)中斷處理結(jié)束后，系統(tǒng)將會(huì)根據(jù)優(yōu)先級(jí)進(jìn)行重調(diào)度。如果中斷響應(yīng)前運(yùn)行的任務(wù)的優(yōu)先級(jí)低于被喚醒的任務(wù)的優(yōu)先級(jí)，操作系統(tǒng)將進(jìn)行任務(wù)上下文切換，高優(yōu)先級(jí)任務(wù)得到優(yōu)先運(yùn)行，其運(yùn)行完畢后再回到被中斷的任務(wù)繼續(xù)運(yùn)行。

2 上下溢陷阱時(shí)間分析

在計(jì)算上下溢陷阱數(shù)目時(shí)有2個(gè)問題必須考慮:1)對(duì)于上下溢陷阱的處理;2)對(duì)于任務(wù)上下文切換的處理。SPARC體系結(jié)構(gòu)允許2到32個(gè)寄存器窗口，當(dāng)上下溢陷阱出現(xiàn)時(shí)可以選擇保存或恢復(fù)1個(gè)到所有的窗口，當(dāng)任務(wù)上下文切換時(shí)也是如此。這樣對(duì)所有情況的詳細(xì)討論將非常復(fù)雜，故本文假定的處理策略是:

1)每次上下溢陷阱出現(xiàn)時(shí)只保存或恢復(fù)1個(gè)窗口。

2)每次任務(wù)上下文切換時(shí)保存所有舊任務(wù)的寄存器窗口，而只恢復(fù)1個(gè)新任務(wù)的寄存器窗口，其他窗口通過下溢陷阱恢復(fù)。

2.1 問題闡述

通過分析每個(gè)任務(wù)可能使用的最大寄存器窗口深度和系統(tǒng)中斷的嵌套深度來計(jì)算最大的上下溢陷阱數(shù)目和切換時(shí)需要保存的最多寄存器窗口數(shù)目。需要說明:

1)優(yōu)化的葉子函數(shù):分析要先抽取任務(wù)函數(shù)調(diào)用圖，其形式可參考圖3。圖中的子函數(shù)4即為優(yōu)化的葉子函數(shù)。葉子函數(shù)是程序調(diào)用圖中的葉結(jié)點(diǎn)，即其不再調(diào)用任何其他函數(shù)。而優(yōu)化的葉子函數(shù)不包含SAVE和RESTORE指令，即其沒有獨(dú)立的寄存器窗口，而是使用其調(diào)用者的堆棧結(jié)構(gòu)和寄存器。在計(jì)算任務(wù)的最大可能調(diào)用深度時(shí)，需要剔除優(yōu)化的葉子函數(shù)，故計(jì)算可得圖3中的函數(shù)調(diào)用深度應(yīng)為4層(包含任務(wù)2自身)，而不應(yīng)計(jì)算為5層。

圖3 任務(wù)2的函數(shù)調(diào)用圖示例

2)最差路徑:任務(wù)程序可能沿著不同的路徑執(zhí)行，而最大上下溢陷阱出現(xiàn)的路徑并不一定是任務(wù)的最差執(zhí)行時(shí)間出現(xiàn)的路徑。為了簡(jiǎn)化分析同時(shí)保證分析結(jié)果的安全性，假設(shè)最大上下溢陷阱出現(xiàn)的路徑和任務(wù)WCET發(fā)生的路徑為同一條路徑。由于本文的分析與任務(wù)的WCET分析是獨(dú)立進(jìn)行的，故分析有效，但分析結(jié)果會(huì)略顯悲觀，一體化的分析將留做后續(xù)工作。

3)任務(wù)可用的寄存器窗口數(shù):通常情況下寄存器窗口中有1個(gè)窗口是供操作系統(tǒng)使用，同時(shí)由于寄存器窗口是環(huán)形結(jié)構(gòu)，最后1個(gè)窗口與第1個(gè)有交疊，所以任務(wù)程序?qū)嶋H可用而不發(fā)生上溢的寄存器窗口個(gè)數(shù)比系統(tǒng)的寄存器窗口總數(shù)少2個(gè)。例如處理器有8個(gè)寄存器窗口，則任務(wù)程序可以使用的窗口數(shù)為6個(gè)。不同的操作系統(tǒng)可能會(huì)有不同，需要根據(jù)具體情況確定，本文設(shè)定為上述情況。

4)中斷服務(wù)程序:發(fā)生中斷時(shí)，將使用1個(gè)寄存器窗口，對(duì)于單純中斷沒有任務(wù)切換發(fā)生時(shí)，假設(shè)中斷服務(wù)程序不再調(diào)用子程序而只用1個(gè)寄存器窗口。而用戶的中斷服務(wù)程序使用的窗口個(gè)數(shù)則是與具體應(yīng)用相關(guān)的，發(fā)生中斷嵌套時(shí)亦是如此。

2.2 無任務(wù)上下文切換時(shí)的界限分析

設(shè)上溢陷阱的處理時(shí)間為to，下溢陷阱的處理時(shí)間為tu，則可得任務(wù)的上下溢處理的時(shí)間開銷為woh=noto+nutu。

2.3 包含任務(wù)上下文切換時(shí)的界限分析

當(dāng)有任務(wù)切換發(fā)生時(shí)，切換到新任務(wù)將保存被中斷任務(wù)的所有寄存器窗口，保存的寄存器個(gè)數(shù)越多，所花費(fèi)時(shí)間越長(zhǎng)，最長(zhǎng)切換時(shí)間出現(xiàn)在任務(wù)調(diào)用深度最大時(shí)。精確地分析需要計(jì)算每層調(diào)用可能出現(xiàn)的任務(wù)切換數(shù)，進(jìn)而確定任務(wù)切換時(shí)間，一個(gè)簡(jiǎn)單的處理辦法是任務(wù)切換時(shí)間全部取任務(wù)調(diào)用深度最大時(shí)的值。新任務(wù)運(yùn)行完畢后，再次切換回被打斷任務(wù)將只恢復(fù)1個(gè)寄存器窗口，其他寄存器窗口的恢復(fù)利用下溢陷阱來完成。故被中斷的任務(wù)恢復(fù)運(yùn)行后每次執(zhí)行RESTORE指令返回都會(huì)發(fā)生1次下溢，最差的情況下，下溢處理程序執(zhí)行完成后再次執(zhí)行任務(wù)切換，則下溢陷阱剛剛恢復(fù)的窗口將被保存，再次切換回來后執(zhí)行RESTORE指令將再次產(chǎn)生下溢。依然采用任務(wù)2為例進(jìn)行說明，如圖4所示。

圖4 窗口下溢圖示

圖中子函數(shù)2運(yùn)行過程中，有中斷產(chǎn)生并喚醒高優(yōu)先級(jí)的任務(wù)1，當(dāng)中斷退出后將切換到任務(wù)1執(zhí)行，任務(wù)1執(zhí)行完畢后再切換回到任務(wù)2，從斷點(diǎn)繼續(xù)執(zhí)行。這種情況下，在子函數(shù)2的運(yùn)行過程中發(fā)生了任務(wù)切換，此時(shí)系統(tǒng)將只有1個(gè)可用的寄存器窗口，當(dāng)子函數(shù)2運(yùn)行到返回指令(RESTORE)時(shí)，將發(fā)生下溢陷阱，運(yùn)行下溢陷阱處理程序，極端情況下，在下溢陷阱處理過程中，中斷再次到來并伴隨高優(yōu)先級(jí)任務(wù)1的釋放，則此時(shí)當(dāng)下溢陷阱處理結(jié)束后，系統(tǒng)將首先響應(yīng)中斷而不會(huì)執(zhí)行子函數(shù)2的返回指令。當(dāng)中斷和任務(wù)1執(zhí)行完畢，再次切換回子函數(shù)2斷點(diǎn)運(yùn)行返回指令時(shí)，由于又進(jìn)行了任務(wù)切換，故將再次發(fā)生下溢，在該情況下子函數(shù)2在返回過程中發(fā)生了2次下溢陷阱。

3 仿真驗(yàn)證

利用開源的LEON3處理器和Modelsim仿真軟件來仿真驗(yàn)證我們的方法。LEON3處理器采用了SPARC V8的體系結(jié)構(gòu)，設(shè)置寄存器窗口數(shù)目為8個(gè)，另外系統(tǒng)包含有5個(gè)中斷，優(yōu)先級(jí)由高到低分別為 TIMER1，EXINT2，EXINT1，UART2 和 UART1，在任務(wù)運(yùn)行時(shí)全部使能。前4個(gè)中斷并不喚醒任務(wù)。UART1中斷設(shè)置為2種情形:一種情形下和其他4種中斷一樣，沒有喚醒任務(wù);另一種情形下如前所述將喚醒高優(yōu)先級(jí)任務(wù)，則在中斷退出后切換到新的高優(yōu)先級(jí)任務(wù)運(yùn)行，高優(yōu)先級(jí)任務(wù)運(yùn)行結(jié)束后再切換回原被中斷的任務(wù)繼續(xù)運(yùn)行。中斷 EXINT2、EXINT1、UART2的用戶中斷處理函數(shù)全部不占用單獨(dú)的寄存器窗口，而中斷TIMER1用戶中斷處理函數(shù)調(diào)用深度為1，即其將占用1個(gè)寄存器窗口。UART1的用戶中斷處理函數(shù)在不進(jìn)行任務(wù)切換時(shí)不占用單獨(dú)的寄存器窗口，當(dāng)其進(jìn)行任務(wù)切換時(shí)則包含有2層調(diào)用，即占用2個(gè)寄存器窗口。

表1 仿真結(jié)果

從表1中可以看出，仿真結(jié)果均小于分析結(jié)果，這說明分析是安全的。同時(shí)也可以看出，對(duì)于存在任務(wù)切換時(shí)窗口上溢的數(shù)量比分析結(jié)果小得多，說明實(shí)際系統(tǒng)中任務(wù)與中斷并不一定會(huì)滿足最差情況，另一方面也可能是通過仿真測(cè)試也難以覆蓋到所有情形，還需要依據(jù)具體情況進(jìn)行分析。對(duì)于存在任務(wù)切換時(shí)窗口下溢的仿真結(jié)果與分析結(jié)果非常接近，說明分析是精確的。當(dāng)然這只是提供一種分析的方法，具體應(yīng)用中還需要根據(jù)系統(tǒng)的實(shí)際情況設(shè)定約束條件以便得到更加精確的結(jié)果。

4 結(jié)論

研究了采用SPARC體系結(jié)構(gòu)的實(shí)時(shí)系統(tǒng)的WCET分析中寄存器窗口的溢出的時(shí)間開銷。提出了系統(tǒng)中存在多級(jí)中斷嵌套，采用某一溢出陷阱處理策略時(shí)，寄存器窗口的溢出陷阱次數(shù)界限的計(jì)算方法。結(jié)果表明，本文的方法可以有效地給出寄存器溢出陷阱的次數(shù)界限，但是其分析精度還可根據(jù)系統(tǒng)的約束條件進(jìn)一步提高，后續(xù)也將針對(duì)其他陷阱處理策略進(jìn)行分析。

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

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

［3］ Wilhelm R，Engblom J，Ermedahl A，et al.The worstcase execution-time problem-overview of methods and survey of tools［J］.ACM Transactions on Embedded Computing Systems，2008，7(3):1-53.

［4］ Layland L J.Seheduling Algorithms for Multi-Programing in a Hard Real-Time Environment［J］.Journal of ACM，1973，20(1):46-61.

［5］ Garrido J，Zamorano J，Juan A de la Puente.Static Analysis of WCET in a Satellite Software Subsystem［C］.The 13th International Workshop on Worst-Case Execution Time Analysis.Paris，F(xiàn)rance，OASICS，2013:87-96.

［6］ Bound-T time and stack analyzer reference manual Issue 6.4［Z］.Tidorum Ltd.，2013.

［7］ The SPARC ArchitectureManualVersion 8［Z］.SPARC International Inc.，1992.

［8］ Engblom J，Ermedahl A，Sj?din M，Gustafsson J，Hansson H.Worst-case execution-time analysis for embedded real-time systems［J］.Int J Softw Tools Technol Transfer.2003，4:437-455.

［9］ Lee E A，Seshia S A.Introduction to Embedded Systems-A Cyber-Physical Systems Approach［M］.LeeS-eshia.org，2011.