面向Web的WCET模式自動分析系統(tǒng)

姬孟洛 舒云星 黃辰林 高 翔

1(洛陽理工學(xué)院計算機與信息工程學(xué)院 河南 洛陽 471023)2(洛陽理工學(xué)院對外合作處 河南 洛陽 471023)3(國防科技大學(xué)計算機學(xué)院 湖南 長沙 410073)

面向Web的WCET模式自動分析系統(tǒng)

姬孟洛1舒云星2黃辰林3高 翔1

1(洛陽理工學(xué)院計算機與信息工程學(xué)院 河南 洛陽 471023)2(洛陽理工學(xué)院對外合作處 河南 洛陽 471023)3(國防科技大學(xué)計算機學(xué)院 湖南 長沙 410073)

針對傳統(tǒng)的WCET(Worst-Case Execution Time)分析方法面臨的精度不高和用戶使用繁瑣問題，提出一種自動分析程序模式的方法并據(jù)此設(shè)計實現(xiàn)了一個面向Web的WCET分析系統(tǒng)。首先在對源程序進(jìn)行分析的基礎(chǔ)上，利用程序控制流程圖，通過數(shù)據(jù)流框架進(jìn)行切片，獲得依賴于輸入變量的無循環(huán)控制流程圖ICFG。然后，通過對ICFG每條路徑求解，獲得程序的模式及其輸入表達(dá)式，并計算其對應(yīng)的WCET。最后，將上述分析方法設(shè)計實現(xiàn)為針對C語言的動態(tài)鏈接庫(DLL)，并利用該DLL實現(xiàn)一個面向Web的WCET自動分析系統(tǒng)——WCET Mode Analyzer。WCET Mode Analyzer對基準(zhǔn)程序的分析結(jié)果，驗證了該方案的有效性和應(yīng)用的簡便性。

實時系統(tǒng) WCET 程序模式 程序分析

0 引 言

實時系統(tǒng)，包括嵌入式實時系統(tǒng)，在進(jìn)行任務(wù)調(diào)度時，需要事先知道每個任務(wù)的執(zhí)行時間。這個時間，指的是最壞情況的執(zhí)行時間WCET[1]。研究獲取WCET值的方法是實時系統(tǒng)的重要研究領(lǐng)域，它不僅應(yīng)用于可調(diào)度性檢測，還應(yīng)用于非實時系統(tǒng)性能分析和嵌入式系統(tǒng)的耗電量分析[2]。

獲取WCET值的主要方法是靜態(tài)分析。WCET靜態(tài)分析根據(jù)程序的執(zhí)行流和運行程序的處理器特性這兩方面的信息來估算程序的WCET。而配置這些信息復(fù)雜、繁瑣且易于出錯。同時，靜態(tài)分析要求安全，也就是給出的估值不能低于任務(wù)可能執(zhí)行時間的最大值。因此，傳統(tǒng)的WCET分析方法通常具有易于高估任務(wù)WCET值和不易使用的缺點[2-3]。

實時系統(tǒng)，尤其是嵌入式實時系統(tǒng)，通常都有模式。系統(tǒng)的一個模式定義了該系統(tǒng)以及其中相關(guān)任務(wù)的一種特殊行為。舉例來說，一個系統(tǒng)通常有啟動模式和正常模式，甚至有正常模式和緊急模式。

利用程序模式能夠更精確地計算任務(wù)WCET。這體現(xiàn)在三個方面。其一，根據(jù)程序不同的模式，分別計算各模式的WCET，取其中最大的WCET，比不加區(qū)分計算出的WCET要精確[4-5]。其二，不同的模式，其要求的WCET往往不同。其三，類似于WCET參數(shù)化分析，每一個模式都有一個由輸入?yún)?shù)值范圍構(gòu)成的表達(dá)式，因此，在任務(wù)執(zhí)行時才確定模式，從而有更精確的WCET值[6-7]。

針對WCET分析的缺點，本文實現(xiàn)一種面向Web的WCET模式自動分析系統(tǒng)——WCET Mode Analyzer。該系統(tǒng)允許用戶通過Web方式上傳被分析的源程序，根據(jù)源程序，能夠自動確定其模式以及模式對應(yīng)的輸入?yún)?shù)值表達(dá)式，然后通過選擇專業(yè)人員配置的程序運行處理器的特征，從而能夠計算每一種模式對應(yīng)的WCET。

1 背景知識

實時系統(tǒng)程序的WCET靜態(tài)分析(以下簡稱WCET分析)通常包括三部分：程序執(zhí)行流分析、處理器特征分析以及基于二者信息的WCET計算。

程序執(zhí)行流分析包括分析循環(huán)的最大迭代范圍、遞歸調(diào)用的深度范圍和不可行路徑等程序流約束信息。不可行路徑是指對任何輸入數(shù)據(jù)都不可能執(zhí)行的程序路徑。

處理器特征分析就是分析程序目標(biāo)代碼的實際執(zhí)行時間，即建立執(zhí)行時間模型，此分析也稱為低層分析。對于無高速緩存、無流水線的傳統(tǒng)CISC(Complex Instruction Set Computer)指令，其每條指令的執(zhí)行時間是固定的。因此，任意兩條指令的執(zhí)行時間，就是其所包含的每條指令的執(zhí)行時間累加。此方法稱為Time schema方法。

流水線的WCET的分析方法通常是利用保留表[8]。此時，兩條指令的執(zhí)行時間就是兩條指令對應(yīng)的兩個保留表連接之后，從第一條指令第一個階(stage)到最后一條指令的最后一個階之間的指令周期(cycle)數(shù)。

高速緩存的WCET典型分析方法是把每條指令的訪問進(jìn)行分類，分為4類：總是丟失(always miss)、總是命中(always hit)、第一次訪問丟失后續(xù)命中(first miss)和第一次訪問命中后續(xù)丟失(first hit)，然后根據(jù)不同訪問類型計算緩存引起WCET[2-3,8]。

WCET計算就是在已知程序執(zhí)行流和執(zhí)行時間模型的情況下，為程序計算WCET估值[2-3]。這里簡單介紹基于樹的方法和基于路徑的方法。

基于樹的方法根據(jù)復(fù)合、條件和循環(huán)語句所形成語法樹，通過遍歷程序的語法分析樹，自底向上逐步計算整個程序的WCET估值。此方法也稱為Time schema方法。常用于CISC指令集的計算。

基于路徑的方法通過計算程序中不同路徑的WCET，從中選擇最大的WCET。對于循環(huán)lp，基于路徑的方法可簡單表示為：

WCETlp=WCETpath×n

(1)

其中，WCETpath是循環(huán)lp中執(zhí)行時間最長的路徑path的WCET值，n為循環(huán)lp的迭代次數(shù)。

2 WCET模式自動分析方法

基于源程序代碼，本分析方法包括七個步驟，其中前六個步驟用于產(chǎn)生模式，最后步驟計算模式對應(yīng)的WCET。

2.1 產(chǎn)生任務(wù)的無循環(huán)控制流圖NLCFG

程序控制流圖CFG(ControlFlowGraph)[9]，是對程序的圖形化表示，由節(jié)點和有向邊組成，它既表示了程序的控制結(jié)構(gòu)信息，也表示了程序語句執(zhí)行的流向。一個結(jié)構(gòu)化程序由三種基本語句構(gòu)成：復(fù)合語句、條件語句和循環(huán)語句，與之對應(yīng)，程序CFG也由三種基本結(jié)構(gòu)組成：順序、分支、循環(huán)。

程序CFG節(jié)點分為賦值節(jié)點、分支點和匯聚點。賦值節(jié)點對應(yīng)于程序的賦值語句，分支節(jié)點對應(yīng)于條件或循環(huán)語句的條件判斷，此條件也稱為分支謂詞。

程序CFG的邊表示程序的執(zhí)行流向，分支節(jié)點的邊稱作分支，對應(yīng)于程序中一段要順序執(zhí)行的語句序列。

無循環(huán)控制流圖NLCFG(NoLoopControlFlowGraph)是一種特殊的控制流圖，其與CFG的區(qū)別在于其循環(huán)語句產(chǎn)生的CFG節(jié)點只包括循環(huán)體節(jié)點而不包括分支謂詞節(jié)點及相應(yīng)的回邊。所以產(chǎn)生程序NLCFG是因為經(jīng)過循環(huán)迭代的依賴輸入變量的值變得無法確定。

按照程序的三種基本語句，分析源程序，能夠產(chǎn)生程序的NLCFG。與程序CFG表示類似，程序NLCFG的節(jié)點可用數(shù)字標(biāo)識，邊可以用節(jié)點的二元組表示，比如邊(m,n)表示從節(jié)點m到節(jié)點n的有向邊。

獲得程序NLCFG的同時，也獲得NLCFG節(jié)點與源程序語句的對應(yīng)關(guān)系，同時，循環(huán)體節(jié)點也得到標(biāo)識。

2.2 利用NLCFG確定依賴輸入變量及其對應(yīng)節(jié)點

依賴輸入變量可以遞歸定義為：由輸入變量定義的變量是依賴輸入變量，由輸入變量和依賴輸入變量定義的變量也是依賴輸入變量。

針對NLCFG，從入口節(jié)點開始，利用通用單調(diào)數(shù)據(jù)流框[10]，依照深度優(yōu)先策略，可以確定每個變量是否是依賴輸入變量。

為了確定依賴輸入變量及其對應(yīng)的NLCFG節(jié)點，為每個節(jié)點設(shè)立兩個狀態(tài)：節(jié)點執(zhí)行前狀態(tài)與執(zhí)行后狀態(tài)。節(jié)點前狀態(tài)由所有流向該節(jié)點的節(jié)點后狀態(tài)確定，而節(jié)點后的狀態(tài)則是該節(jié)點執(zhí)行后改變的狀態(tài)。對于所有流向一個節(jié)點的節(jié)點，如果這些節(jié)點的節(jié)點后狀態(tài)中，該變量是依賴輸入變量，那么，在此節(jié)點的節(jié)點前狀態(tài)中，該變量的狀態(tài)定義為依賴輸入變量。

所謂深度優(yōu)先策略是指，在處理一個節(jié)點后，對該節(jié)點的后續(xù)節(jié)點，按照深度優(yōu)先策略進(jìn)行排隊處理。首先對后續(xù)節(jié)點排隊。排隊之后，對隊列中的第一個節(jié)點同樣處理，只有在第一個節(jié)點及其后續(xù)節(jié)點處理完畢或者無法處理之后，才開始處理該節(jié)點隊列中的第二個節(jié)點。一個節(jié)點無法處理是指，如果該節(jié)點有一個前任節(jié)點的執(zhí)行后狀態(tài)是不確定的。一個節(jié)點m的前任節(jié)點是一個節(jié)點集合，滿足：它們都有一條邊指向節(jié)點m。同理，節(jié)點m的后續(xù)節(jié)點是一個節(jié)點集合，滿足：節(jié)點m有一條邊指向這些節(jié)點。

對于無法處理的節(jié)點，將該節(jié)點重新排在隊列末尾。基于深度優(yōu)先策略確定依賴輸入變量算法可參考圖1所示。

圖1可以分為兩部分，前半部分圍繞隊列Q1，根據(jù)節(jié)點對依賴輸入變量的引用關(guān)系，確定每個變量的節(jié)點后狀態(tài)是否為依賴輸入變量，其中定義引用變量為依賴輸入變量的節(jié)點為依賴輸入節(jié)點。后半部分圍繞隊列Q2，確定該節(jié)點的后續(xù)節(jié)點的節(jié)點前狀態(tài)。

圖1 基于深度優(yōu)先策略的依賴輸入變量確定算法

對于結(jié)構(gòu)化程序，由于NLCFG沒有循環(huán)結(jié)構(gòu)，所以NLCFG為單向有向圖，因此，NLCFG中的節(jié)點是有序的。也因此，所述算法能夠保證快速確定每個節(jié)點的狀態(tài)。

2.3 確定依賴循環(huán)變量、非輸入分支變量及其節(jié)點

一個變量如果在循環(huán)體中定義，則該變量為依賴循環(huán)變量。一個變量如果在定義中引用了依賴循環(huán)變量，則該變量同樣為依賴循環(huán)變量。同樣，一個變量如果在非依賴輸入分支謂詞的分支中定義，則該變量為依賴非輸入分支變量。一個變量如果在定義中引用了依賴非輸入分支變量，則該變量同樣為依賴非輸入分支變量。以上兩類變量統(tǒng)稱為非依賴輸入變量NOINPUT。

針對一個循環(huán)體節(jié)點或非依賴輸入分支節(jié)點，首先確定一個變量在節(jié)點后狀態(tài)中為NOINPUT，然后，利用通用單調(diào)數(shù)據(jù)流框，可以確定所有后續(xù)的NOINPUT變量。

2.4 刪除非依賴輸入節(jié)點產(chǎn)生ICFG

針對NLCFG，刪除圖中非依賴輸入節(jié)點。刪除的方法仍然按照節(jié)點的基本結(jié)構(gòu)進(jìn)行，所不同的是，一個分支節(jié)點或者匯合節(jié)點可以是空節(jié)點。所謂空節(jié)點就是不執(zhí)行任何操作的節(jié)點。空節(jié)點對應(yīng)語句為空語句。

最終形成的無循環(huán)控制流圖NLCFG為輸入變量相關(guān)的NLCFG，標(biāo)記為ICFG(InputdependentControlFlowGraph)。

2.5 產(chǎn)生ICFG的所有路徑

對于ICFG，可產(chǎn)生其所有路徑。由于ICFG是單向圖，可按照深度優(yōu)先策略產(chǎn)生所有路徑。

2.6 針對每條路徑產(chǎn)生其輸入條件

針對ICFG的每一條路徑，在這個路徑上只有兩類節(jié)點，一類是賦值節(jié)點，另一類是分支節(jié)點。對于分支節(jié)點，如果其分支謂詞表達(dá)式是輸入變量的線性表示，則可以構(gòu)造出該分支謂詞針對輸入變量的線性表達(dá)式。

假定輸入表示為X=，m是輸入變量的個數(shù)，假定一個分支謂詞可以表示為X的線性函數(shù)F(X)=d1x1+…+dmxm+c，由于任意給定一個輸入，沿著該路徑執(zhí)行該分支節(jié)點之前的所有輸入和賦值語句，從而能夠計算該謂詞的值，因此能夠計算出謂詞線性表達(dá)式的各參數(shù)dj：

dj=(F(I0+(0,…,△ij,…,0))-F(I0))/△ij

(2)

j=1,2,…,m

其中I0=(i1,…,ij,…,im)為任一輸入，△ij為任一不為0的增量。

對于ICFG上的一條路徑，該路徑上每個分支取向已經(jīng)確定，同時，每個分支謂詞對輸入變量的線性表達(dá)式已知，因此，可以根據(jù)路徑上的分支謂詞構(gòu)造輸入變量的約束組。如果定義目標(biāo)函數(shù)為所有輸入變量累加的最小值，則構(gòu)成一個典型的線性規(guī)劃求解問題。

利用線性規(guī)劃解析器，即可解得輸入變量的值或者是范圍，此即為該ICFG路徑的輸入條件，此條件即為該模式對應(yīng)的輸入條件。如果線性規(guī)劃問題無解，則說明該路徑為不可行路徑。

2.7 模式的WCET分析

假定md是任務(wù)M的一個模式，如果M中路徑P屬于md中路徑，則稱路徑P由模式md支配。如果路徑P由模式md支配，則路徑P上的節(jié)點/基本塊也由模式md支配。即：一個節(jié)點/基本塊由模式md支配，如果M中存在一條路徑P，滿足：md支配路徑P且該節(jié)點/基本塊在P上。

一個語句真值(true)/ 假值(false)控制依賴于b，如果當(dāng)b為true/false時才執(zhí)行該語句[9]。對于模式md的每個謂詞b，有兩個語句集合，它們分別真值和假值控制依賴于b。

根據(jù)模式md支配的路徑P，能夠確定md中每個謂詞b的取值(true/false)。如果b的取值為true，則真值控制依賴于b的節(jié)點由模式md支配，而假值控制依賴于b的節(jié)點模式md不支配。反之亦成立。

對于指定模式下的WCET分析，不應(yīng)當(dāng)考慮模式不支配的節(jié)點，而相應(yīng)的WCET分析方法保持不變。

對于指定模式md下的Timeschema計算，只需考慮md支配的分支或者基本塊即可。流水線的計算按照路徑的方法進(jìn)行。對于指定模式md下的WCET高速緩存分析，只需考慮miss情況。一條指令被劃分miss，只有當(dāng)存在一個md支配的控制流中該位置的其它程序線也可能被緩存，也就是它和另一個md支配的程序線的緩存發(fā)生沖突。否則，它是hit。

對于指定模式md下的基于路徑的計算，式(1)中WCETpath對應(yīng)循環(huán)lp的最長路徑Path有限制，Path應(yīng)當(dāng)是由md支配的路徑。如果循環(huán)lp中最長路徑Path不是由md支配的，則檢查循環(huán)lp中次長路徑。顯然循環(huán)lp中至少有一條模式md支配的路徑，因此最終能夠得到由md支配的最長路徑Path。

本文采用基于路徑的計算方法。

3 WCET模式自動分析的實現(xiàn)

在基于抽象解釋的WCET自動分析工具NPCA-WCET[11]的基礎(chǔ)上，我們實現(xiàn)了面向C語言的WCET程序模式自動分析。該實現(xiàn)稱為處理對象庫 (DLL)，它是一個具有公共語言運行時CLR(CommonLanguageRuntime)特征的動態(tài)連接庫，它還能夠為C語言之外的諸如C#語言所調(diào)用。

3.1 處理過程

處理對象庫 (DLL)的主要處理邏輯包括三部分：詞法和語法分析(parse)、模式分析，以及指定模式的WCET分析，如圖2所示。

圖2 模式分析的處理過程

在圖2中，首先對C源程序進(jìn)行詞法和語法分析，生成程序結(jié)構(gòu)信息的對象表示，其中包括控制流圖、輸入變量表和變量表。對程序結(jié)構(gòu)信息進(jìn)行程序流信息分析即用于獲取WCET分析的流信息。這些信息包括：函數(shù)調(diào)用關(guān)系、遞歸調(diào)用關(guān)系、循環(huán)的界限以及不可行路徑等。程序流分析方法是基于抽象解釋[12]支持的變量值范圍傳播[10]。

ICFG分析即包括前述第2節(jié)的前五個步驟，其結(jié)果產(chǎn)生輸入變量相關(guān)的無循環(huán)控制流圖ICFG以及其對應(yīng)的所有路徑。針對其每一條路徑，構(gòu)造對應(yīng)的線性約束系統(tǒng)，并進(jìn)行求解。求解器采用：如果有解，則該路徑對應(yīng)一個模式，線性約束系統(tǒng)就是它的輸入條件；如果無解，這對應(yīng)一個不可行路徑。

緩存分析利用高速緩存的配置信息以及程序流信息和映射文件提供的指令序列，對每條指令和數(shù)據(jù)緩存操作進(jìn)行分類，已備時間分析使用。

時間分析根據(jù)程序流信息、緩存分類信息和程序流信息對于的指令序列，根據(jù)指令系統(tǒng)信息，計算每個模式以及整個函數(shù)的WCET。

3.2 實現(xiàn)類

WCET模式分析的具體實現(xiàn)可以通過面向?qū)ο蟮姆椒ㄟM(jìn)行設(shè)計實現(xiàn)，其實現(xiàn)類及對象關(guān)系如圖3所示。

圖3 WCET模式分析實現(xiàn)類及對象關(guān)系

WCET模式分析實現(xiàn)主要體現(xiàn)在COneFile類上。COneFile關(guān)聯(lián)源文件類CSrcFile和映射文件類CMapFile。通過COneFile類函數(shù)Analyse對源文件進(jìn)行詞法分析，生成相應(yīng)的Token對象列表。在Token對象列表的基礎(chǔ)上，可以通過其函數(shù)GetFunItem進(jìn)行語法分析從而獲取源文件包含的函數(shù)對象CFunItem，然后，通過類CFunItem的函數(shù)GetModeItem獲取該函數(shù)包含的模式對象CModeItem和節(jié)點CNode對象。

可以通過對CMapFile分析，將源文件對應(yīng)的指令序列映射到相應(yīng)的函數(shù)及其節(jié)點對象CNode上。

以上類以及相關(guān)類，生成為具有CLR特性的動態(tài)鏈接庫。

從對象的組織關(guān)系上講，一個COneFilet對象包含了一個源文件CSrcFile對象，一個可能的映射文件CMapFile對象和函數(shù)對象CFunItem隊列。映射文件是編譯器產(chǎn)生的源文件與機器指令的映射列表文件，一般編譯器都具有生成該文件的功能，WCET模式分析器利用此文件建立源文件與其執(zhí)行指令的對應(yīng)關(guān)系。

函數(shù)對象CFunItem隊列包含了該COneFilet對象的所有函數(shù)。每個CFunItem包含了CFG節(jié)點CNode隊列和分析出來的模式，也使用CModeItem隊列表示。節(jié)點CNode包括分支節(jié)點CBranchNode和賦值節(jié)點CAssignNode，每個節(jié)點對應(yīng)兩個變量表VariableTable，并包含了一個表達(dá)式，一個表達(dá)式用變量CVariable和操作符COperator隊列表示。

4 面向Web的WCET分析系統(tǒng)

利用處理對象庫 (DLL)提供的WCET模式分析功能，可以實現(xiàn)具有模式分析功能的系統(tǒng)。本節(jié)實現(xiàn)一個面向互聯(lián)網(wǎng)的WCET模式分析器——WCETModeAnalyzer。

之所以將WCETModeAnalyzer設(shè)計成面向互聯(lián)網(wǎng)不僅是為了便于訪問，更是為了方便角色劃分，將繁瑣且易于出錯的配置低層分析部分劃歸作為系統(tǒng)管理員的專業(yè)人員去完成，而將對應(yīng)用程序的WCET分析計算使用功能提供給應(yīng)用用戶。

4.1 主要功能

從應(yīng)用的角度看，WCET模式分析器功能比較簡單。該系統(tǒng)分為兩個角色：系統(tǒng)管理員和應(yīng)用用戶。

系統(tǒng)管理員負(fù)責(zé)配置CPU和系統(tǒng)參數(shù)。配置CPU包括配置指令系統(tǒng)、主頻和配置高速緩存。對于CISC指令系統(tǒng)，每條指令對應(yīng)一個處理時間(cycles，節(jié)拍數(shù))。對于RISC指令系統(tǒng)，定義指令的每個階之后，對于每條指令，指定該指令每個階(stage)占用的節(jié)拍數(shù)。可以對每一條指令進(jìn)行定義，也可以通過EXCEL表按照指定格式整體錄入。

對于高速緩存，主要是確定其映射方式和緩存大小。映射方式是指高速緩存與內(nèi)存的映射關(guān)系，有直接映射、全相聯(lián)映射和組相聯(lián)映射三種方式。

4.2 設(shè)計實現(xiàn)

WCET模式分析器主要由三部分組成：網(wǎng)頁響應(yīng)、對象管理器和處理對象庫(DLL)。處理對象庫如前所述。

(1) 網(wǎng)頁設(shè)計

WCET模式分析器的網(wǎng)頁設(shè)計分系統(tǒng)管理員和應(yīng)用用戶。系統(tǒng)管理員頁面比較簡單，僅僅是用來配置CPU。

應(yīng)用用戶的顯示頁面除主題和頁腳，主要由左中右三部分構(gòu)成，左邊為導(dǎo)航樹，中間部分為主顯示區(qū)，右邊為輔助顯示區(qū)。導(dǎo)航樹第一部分為項目配置，后面部分為各個項目不同視角的顯示。

主顯示區(qū)根據(jù)導(dǎo)航樹的選擇項顯示相應(yīng)的內(nèi)容，而輔助顯示區(qū)則可能顯示對應(yīng)的輔助內(nèi)容。比如，當(dāng)導(dǎo)航樹選擇一個源文件的時候，主顯示區(qū)顯示該文件包含函數(shù)的模式及對應(yīng)的WCET，而輔助顯示區(qū)則顯示對應(yīng)的源文件內(nèi)容，如圖4所示。

圖4 面向Web的WCET模式分析系統(tǒng)構(gòu)成

網(wǎng)頁設(shè)計簡單但很瑣細(xì)，網(wǎng)頁設(shè)計的關(guān)鍵在于數(shù)據(jù)存儲和獲取，其由數(shù)據(jù)管理器來完成。

(2) 對象管理器設(shè)計

對象管理器負(fù)責(zé)WCET模式分析器中對象的組織，其頂層組織如圖5所示。

圖5 面向Web的WCET模式分析系統(tǒng)構(gòu)成

COneFile的組織如前所述。CCPU對象包括指令集和高速緩存等，主要用于低層分析。

5 系統(tǒng)分析實例

我們選用基準(zhǔn)集SNU-RTBenchmarkSuite進(jìn)行測試，以Alpha21064為處理器模型，該處理器指令緩存1MB，用戶可以直接選用。SNU-RT基準(zhǔn)集是實時系統(tǒng)領(lǐng)域用于WCET分析的基準(zhǔn)程序集[13]。

通過分析，SNU-RT基準(zhǔn)集有17個程序，其中9個程序包含的程序具有模式。整體上，17個程序中有55個函數(shù)，其中23個具有模式。圖6為adpcm-test.c程序?qū)?yīng)的顯示頁面部分。可以看出，對于有模式的函數(shù)，WCET模式分析系統(tǒng)將給出其模式和模式對應(yīng)的WCET值，對于沒有模式(或者無法判斷其模式)的函數(shù)，WCET模式分析系統(tǒng)將給出其函數(shù)的WCET值。

圖6 面向Web的WCET模式分析系統(tǒng)顯示頁面

6 結(jié) 語

本文提出了一個自動分析程序WCET模式的新方法，并據(jù)此設(shè)計實現(xiàn)一種面向Web的WCET模式分析系統(tǒng)。該系統(tǒng)能夠分析程序模式，計算任務(wù)以及模式的WCET，從而達(dá)到更精確地計算實時任務(wù)WCET的目的。同時，利用Web系統(tǒng)的特點，將繁瑣的配置工作交由專業(yè)的系統(tǒng)管理員，應(yīng)用用戶可以直接使用配置好的處理器，從而使配置工作簡便。通過對基準(zhǔn)程序進(jìn)行分析實驗，驗證了該方案的有效性。

本系統(tǒng)目前僅在RISC類處理器Alpha21064上實現(xiàn)了C語言程序WCET分析，未來還需要擴展到多種類型實時用處理器和語言上，比如ARM類處理器和C++語言。

[1]DavisRI,BurnsA.Asurveyofhardreal-timeschedulingformultiprocessorsystems[J].ACMComputingSurveys(CSUR),2011,43(4):1-41.

[2]WilhelmR,EngblomJ,ErmedahlA,etal.Theworst-caseexecution-timeproblem-overviewofmethodsandsurveyoftools[J].ACMTransactionsonEmbeddedComputingSystems(TECS),2008,7(3):196-206.

[3]PuschnerP,BurnsA.Guesteditorial:areviewofworst-caseexecution-timeanalysis[J].Real-TimeSystems,2000,18(2-3):115-128.

[4]WilhelmR,LucasP,ParshinO,etal.ImprovingtheprecisionofWCETanalysisbyinputconstraintsandmodel-derivedflowconstraints[M]//ChakrabortyS,Ebersp?cherJ.AdvancesinReal-TimeSystems.Berlin:Springer-Verlag,2012:123-143.

[5]JiML,WangJ,LiS,etal.Automatedworst-caseexecutiontimeanalysisbasedonprogrammodes[J].TheComputerJournal,2009,52(5):530-544.

[6]BallabrigaC,ForgetJ,LipariG.Context-sensitiveparametricWCETanalysis[C]//15thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Lund,Sweden,2015:54-64.

[7]ZwirchmayrJ,SotinP,BonenfantA,etal.IdentifyingrelevantparameterstoimproveWCETanalysis[C]//14thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Madrid,Spain,2014:93-102.

[8]HealyCA,ArnoldRD,MuellerF,etal.Boundingpipelineandinstructioncacheperformance[J].IEEETransactionsonComputers,1999,48(1):53-70.

[9]TipF.Asurveyofprogramslicingtechniques[J].JournalofProgrammingLanguages,1995,3(3):121-189.

[10] 姬孟洛,王懷民,李夢君,等.一種基于抽象解釋和通用單調(diào)數(shù)據(jù)流框架的值范圍分析方法[J].計算機研究與發(fā)展,2006,43(11):2020-2026.

[11] 姬孟洛,李軍,王馨,等.一種基于抽象解釋的WCET自動分析工具[J].計算機工程,2006,32(14):54-56.

[12]CousotP,CousotR.Abstractinterpretation:aunifiedlatticemodelforstaticanalysisofprogramsbyconstructionorapproximationoffixpoints[C]//Proceedingsofthe4thACMSymposiumonPrinciplesofProgrammingLanguages,LosAngeles,CA,USA,1977:238-252.

[13]SATABS.SNUReal-TimeBenchmarks[OL].http://www.cprover.org/satabs/examples/SNU_Real_Time_Benchmarks/.

AN AUTOMATIC WCET ANALYSIS SYSTEM FOR WEB

Ji Mengluo1Shu Yunxing2Huang Chenlin3Gao Xiang1

1(SchoolofComputerandInformationEngineering,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)2(DepartmentofForeignCooperation,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)3(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha410073,Hunan,China)

In light of the problems of deficient precision and troublesome usage the traditional WCET analysis systems usual suffer, a new automatic analysis method based on program modes is proposed and a WCET analysis system on the idea of the method for Web is designed. Firstly, a method is presented based on the analysis of source code which produces an acyclic input parameter dependent control flow graph called ICFG by using program control flow graph and a specific program slicing under data flow framework. Secondly, by constructing a solution system for each path in ICFG, a mode and its input parameter expression maybe conducted, and the WCET value of a mode can be computed. Finally,a Dynamic link library (DLL) is implemented based on the method above for C language in order to be used by different systems,and an automated analysis system in the Web by using the DLL is realized, which is called WCET Mode Analyzer. The result for a Benchmark implemented by the analysis system shows the effectiveness of the solution and the characteristics of using conveniently.

Real-time systems WCET Program mode Program analysis

2015-12-25。河南省科技計劃項目(152300410115)。姬孟洛，高級工程師，主研領(lǐng)域：實時系統(tǒng)，中間件技術(shù)，信息系統(tǒng)分析與設(shè)計。舒云星，教授。黃辰林，副教授。高翔，講師。

TP311

A

10.3969/j.issn.1000-386x.2017.02.042