陳勇
【摘 要】在安全關鍵實時系統設計中，為了保證系統的安全運行，實時任務必須在截止期之前完成，否則將產生嚴重的後果。衡量系統實時性的重要指標是任務的最壞場景運行時間（Worst Case Execution Time， WCET）。論文在傳統靜態WCET分析方法的基礎上，提出了將拓撲排序算法應用到WCET的計算中，較大地提升了WCET的計算效率。
【Abstract】In the design of safety-critical real-time system， in order to ensure the safe operation of the system， the real-time task must be completed before the deadline， otherwise serious consequences may happen. Worst Case Execution Time （WCET） of a task is an important indicator of system real-time performance. Based on the traditional static WCET analysis method， this paper puts forward the application of topological sorting algorithm to the calculation of WCET， which greatly improves the calculation efficiency of WCET.
【關鍵詞】安全關鍵;實時系統;WCET
【Keywords】safety-critical; real-time system; WCET
【中圖分類號】TP301.6 【文獻標誌碼】A 【文章編號】1673-1069（2021）04-0158-02
1 引言
實時系統中對軟體運行時間，相對於非實時系統來說有著嚴格的時限要求，非實時系統有較高的運行時限容忍度，軟體偶然的運行超時並不會造成嚴重後果，僅僅是降低了系統的吞吐量。而實時系統有剛性的、嚴格的時間限制，軟體運行超出時限後，會導致系統不能實現它的預期目標，或者帶來損害甚至導致系統失效，對於安全關鍵實時系統，系統失效帶來的後果可能是災難性的，故它不允許任何超出時限的錯誤。實時系統的時間性要求更關注的WCET是在目標環境中的一個給定處理器上，完成一組任務執行的最長可能時間，要求在邏輯結果正確的前提下，WCET在分配的時間範圍之內。
實時任務的WCET與軟體的輸入、採用的算法以及軟體運行的目標環境相關。基於程序的原始碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，並獲取程序可能的執行路徑信息，以便找出最長路徑。底層分析主要考慮處理器體系架構對軟體運行時間的影響，如何對緩存、流水線、亂序執行、分支預測等特性進行建模來提高WCET估計的精度。WCET計算主要研究如何在控制流分析、底層分析的基礎上找出WCET的算法。
2 WCET分析技術
WCET分析方法分為三種：動態測量方法、靜態分析方法和混合方法。
動態測量是在目標硬體環境下，基於需求，通過給定不同的輸入對程序進行測試。通過收集程序每次的運行時間可以獲得程序的最大運行時間。然後對結果增加一定的時間余度以防止測量值低於實際的最壞場景下的運行時間，由於測試不能窮舉，所以不能保證結果是安全的。
靜態分析方法是在分析處理器性能特性的基礎上，分析程序原始碼（或目標碼）以獲取程序運行時特徵（如訪問的內存地址、循環邊界等），最後計算程序所占用的處理器時間。主要過程包括：控制流分析、底層分析、WCET計算。典型WCET靜態分析過程如圖1所示。目前市場上比較成熟的工具有德國Absint公司的aiT[1]。
混合方法是綜合運用靜態分析方法和動態測量方法，但這裡動態測量與上述動態測量方法的內容是不相同的。在對程序中的小程序單位（如基本塊）進行動態測量（即替換了圖1中的底層分析過程）後，再進行靜態分析得到WCET。
本文描述的是WCET靜態分析方法。
3 控制流分析
控制流分析基於程序的原始碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，並獲取程序可能的執行路徑信息（執行流），以找出最長路徑。控制流分析不考慮軟體運行環境的硬體信息，分析研究主要集中在控制流的提取、邏輯結構的表示、控制流的表示與轉換（如確定循環結構）、循環上界及不可達路徑的確定等。控制流的提取主要依據原始碼（或目標碼）的各種語法結構，如if-else、switch-case結構等（或目標碼中的跳轉、條件跳轉等），而確定循環最大次數，不可達路徑，需要更多的語義分析，必要時需要通過註解的方式來獲取。控制流的描述法主要有：語法樹、域樹、時間樹、控制流圖等[2]。本文基於目標碼來生成函數的控制流圖，如圖2所示。
4 底層分析
如果指令是順序執行的，則對順序執行的程序指令，簡單相加指令周期就可以得到程序運行時間的一個估計。而具有CACHE、流水線、亂序執行、分支預測等硬體特性的目標處理器上，這種指令周期相加的計算方法只能得出相當不準確的WCET估計。因此，必須結合處理器各種加速特性對目標碼進行底層分析，才能獲取更為精確的WCET估計。底層分析一般包括：變量值分析、CACHE分析、流水線分析、分支預測分析等。
5 WCET計算
WCET的計算是通過結合控制流分析和底層分析的結果來計算程序的WCET估計值，當前主要有三種計算方法：基於隱藏路徑枚舉的計算方法（地址ET）、基於樹的計算方法及基於路徑的方法。
基於地址ET的計算方法通過建立程序流程和基本塊的疊代模型及用數學約束，建立目標函數，對WCET的計算就是進行最大化求解，一般使用的約束包括：結構約束和功能約束。結構約束與程序的控制流有關，功能約束則與循環邊界、路徑信息和函數調用有關。最大化求解的主要的方法是整數線性規劃ILP（Integer Linear Programming）。本文採用基於地址ET的計算方法，但在最後計算階段未使用ILP，而是引入了一種全新的計算方法，基於拓撲排序的計算方法。
5.1 拓撲排序簡介
拓撲排序（topological-sort）是指由某個集合上的一個偏序得到該集合上的一個全序的操作。拓撲排序常用來確定一個包含依賴關係集合中，事物發生的先後順序。拓撲排序是對有向無環圖中的頂點的一種排序，排序的規則是：如果存在一條從頂點A到頂點B的路徑，那麼在排序中，A排在B的前面。
拓撲排序的典型應用是根據作業或任務的相關性來安排它們的順序。例如，洗衣服時，洗衣機必須先洗出衣服，然後我們才能將衣服放入烘乾機。這個特性可以應用到工程上的施工流程。用頂點表示子工程（活動），用有向邊表示活動間的先後關係，這就形成了一個AOV網絡（activity on vertex network）有向圖。我們要對某個工程的施工流程是否可行進行論證，就是必須檢測相應的AOV網絡是否存在迴路，一個AOV網絡中如果存在迴路，這就意味著某個子工程的開工要以自身的完工為前提條件，這顯然是不可能的。確定AOV網絡是否存在迴路則通過拓撲排序來完成。因此，研究拓撲排序算法是很有實際意義的。
5.2 拓撲排序算法在WCET中的應用
從圖2可以看出，函數的控制流圖就是一個典型的有向圖。頂點表示程序基本塊，有向邊表示基本塊執行的先後順序，如果從基本塊A到基本塊B之間存在一條路徑，則稱基本塊A是基本塊B的前趨，或稱基本塊B是基本塊A的後繼。如果[A， B]是控制流圖中的一條邊，則稱A是B的直接前趨，或稱B是A的直接後繼。拓撲排序的算法如下：
①在控制流圖中選取一個函數入口基本塊（沒有前趨）。
②在控制流圖中刪除該基本塊及其所發出的所有邊。
③重複執行①、②，直至輸出全部沒有前趨的基本塊。
當過程結束時，如果有向圖中的所有基本塊均已輸出，則說明有向圖中不存在迴路，否則說明有向圖存在迴路。
使用拓撲排序可以確定有向圖中是否有迴路，而在控制流圖中，只有循環存在時，才會存在迴路。因此，使用拓撲排序，不僅可以排列出程序基本塊執行的先後順序，還可以準確地確定函數中的循環起點基本塊和循環終點基本塊，通過循環變化後，可以將函數控制流圖變成完整的拓撲結構圖。這樣，計算函數WCET的時間，就轉化成了對拓撲結構中每一個頂點完成時間的計算。函數的WCET實際上就是最後一個頂點完成的時間。
6 結語
本文對目前WCET分析技術進行了詳細的研究討論，並給出了一個基於目標碼分析的WCET分析過程。採用拓撲排序算法，極大地簡化了WCET的計算，WCET計算的時間複雜度為O（n），其中n表示函數基本塊的數目。經過實際測試的驗證，該方法的運算速度快於ILP。
【參考文獻】
【1】AbsInt.The industry standard for static timing analysis[EB/OL].https：//www.absint.com/ait.
【2】Kirner R， Puschner P. Classification of WCET analysis techniques[C]// Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing （ISORC'05）. IEEE， 2005.
【摘 要】在安全關鍵實時系統設計中，為了保證系統的安全運行，實時任務必須在截止期之前完成，否則將產生嚴重的後果。衡量系統實時性的重要指標是任務的最壞場景運行時間（Worst Case Execution Time， WCET）。論文在傳統靜態WCET分析方法的基礎上，提出了將拓撲排序算法應用到WCET的計算中，較大地提升了WCET的計算效率。
【Abstract】In the design of safety-critical real-time system， in order to ensure the safe operation of the system， the real-time task must be completed before the deadline， otherwise serious consequences may happen. Worst Case Execution Time （WCET） of a task is an important indicator of system real-time performance. Based on the traditional static WCET analysis method， this paper puts forward the application of topological sorting algorithm to the calculation of WCET， which greatly improves the calculation efficiency of WCET.
【關鍵詞】安全關鍵;實時系統;WCET
【Keywords】safety-critical; real-time system; WCET
【中圖分類號】TP301.6 【文獻標誌碼】A 【文章編號】1673-1069（2021）04-0158-02
1 引言
實時系統中對軟體運行時間，相對於非實時系統來說有著嚴格的時限要求，非實時系統有較高的運行時限容忍度，軟體偶然的運行超時並不會造成嚴重後果，僅僅是降低了系統的吞吐量。而實時系統有剛性的、嚴格的時間限制，軟體運行超出時限後，會導致系統不能實現它的預期目標，或者帶來損害甚至導致系統失效，對於安全關鍵實時系統，系統失效帶來的後果可能是災難性的，故它不允許任何超出時限的錯誤。實時系統的時間性要求更關注的WCET是在目標環境中的一個給定處理器上，完成一組任務執行的最長可能時間，要求在邏輯結果正確的前提下，WCET在分配的時間範圍之內。
實時任務的WCET與軟體的輸入、採用的算法以及軟體運行的目標環境相關。基於程序的原始碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，並獲取程序可能的執行路徑信息，以便找出最長路徑。底層分析主要考慮處理器體系架構對軟體運行時間的影響，如何對緩存、流水線、亂序執行、分支預測等特性進行建模來提高WCET估計的精度。WCET計算主要研究如何在控制流分析、底層分析的基礎上找出WCET的算法。
2 WCET分析技術
WCET分析方法分為三種：動態測量方法、靜態分析方法和混合方法。
動態測量是在目標硬體環境下，基於需求，通過給定不同的輸入對程序進行測試。通過收集程序每次的運行時間可以獲得程序的最大運行時間。然後對結果增加一定的時間余度以防止測量值低於實際的最壞場景下的運行時間，由於測試不能窮舉，所以不能保證結果是安全的。
靜態分析方法是在分析處理器性能特性的基礎上，分析程序原始碼（或目標碼）以獲取程序運行時特徵（如訪問的內存地址、循環邊界等），最後計算程序所占用的處理器時間。主要過程包括：控制流分析、底層分析、WCET計算。典型WCET靜態分析過程如圖1所示。目前市場上比較成熟的工具有德國Absint公司的aiT[1]。
混合方法是綜合運用靜態分析方法和動態測量方法，但這裡動態測量與上述動態測量方法的內容是不相同的。在對程序中的小程序單位（如基本塊）進行動態測量（即替換了圖1中的底層分析過程）後，再進行靜態分析得到WCET。
本文描述的是WCET靜態分析方法。
3 控制流分析
控制流分析基於程序的原始碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，並獲取程序可能的執行路徑信息（執行流），以找出最長路徑。控制流分析不考慮軟體運行環境的硬體信息，分析研究主要集中在控制流的提取、邏輯結構的表示、控制流的表示與轉換（如確定循環結構）、循環上界及不可達路徑的確定等。控制流的提取主要依據原始碼（或目標碼）的各種語法結構，如if-else、switch-case結構等（或目標碼中的跳轉、條件跳轉等），而確定循環最大次數，不可達路徑，需要更多的語義分析，必要時需要通過註解的方式來獲取。控制流的描述法主要有：語法樹、域樹、時間樹、控制流圖等[2]。本文基於目標碼來生成函數的控制流圖，如圖2所示。
4 底層分析
如果指令是順序執行的，則對順序執行的程序指令，簡單相加指令周期就可以得到程序運行時間的一個估計。而具有CACHE、流水線、亂序執行、分支預測等硬體特性的目標處理器上，這種指令周期相加的計算方法只能得出相當不準確的WCET估計。因此，必須結合處理器各種加速特性對目標碼進行底層分析，才能獲取更為精確的WCET估計。底層分析一般包括：變量值分析、CACHE分析、流水線分析、分支預測分析等。
5 WCET計算
WCET的計算是通過結合控制流分析和底層分析的結果來計算程序的WCET估計值，當前主要有三種計算方法：基於隱藏路徑枚舉的計算方法（地址ET）、基於樹的計算方法及基於路徑的方法。
基於地址ET的計算方法通過建立程序流程和基本塊的疊代模型及用數學約束，建立目標函數，對WCET的計算就是進行最大化求解，一般使用的約束包括：結構約束和功能約束。結構約束與程序的控制流有關，功能約束則與循環邊界、路徑信息和函數調用有關。最大化求解的主要的方法是整數線性規劃ILP（Integer Linear Programming）。本文採用基於地址ET的計算方法，但在最後計算階段未使用ILP，而是引入了一種全新的計算方法，基於拓撲排序的計算方法。
5.1 拓撲排序簡介
拓撲排序（topological-sort）是指由某個集合上的一個偏序得到該集合上的一個全序的操作。拓撲排序常用來確定一個包含依賴關係集合中，事物發生的先後順序。拓撲排序是對有向無環圖中的頂點的一種排序，排序的規則是：如果存在一條從頂點A到頂點B的路徑，那麼在排序中，A排在B的前面。
拓撲排序的典型應用是根據作業或任務的相關性來安排它們的順序。例如，洗衣服時，洗衣機必須先洗出衣服，然後我們才能將衣服放入烘乾機。這個特性可以應用到工程上的施工流程。用頂點表示子工程（活動），用有向邊表示活動間的先後關係，這就形成了一個AOV網絡（activity on vertex network）有向圖。我們要對某個工程的施工流程是否可行進行論證，就是必須檢測相應的AOV網絡是否存在迴路，一個AOV網絡中如果存在迴路，這就意味著某個子工程的開工要以自身的完工為前提條件，這顯然是不可能的。確定AOV網絡是否存在迴路則通過拓撲排序來完成。因此，研究拓撲排序算法是很有實際意義的。
5.2 拓撲排序算法在WCET中的應用
從圖2可以看出，函數的控制流圖就是一個典型的有向圖。頂點表示程序基本塊，有向邊表示基本塊執行的先後順序，如果從基本塊A到基本塊B之間存在一條路徑，則稱基本塊A是基本塊B的前趨，或稱基本塊B是基本塊A的後繼。如果[A， B]是控制流圖中的一條邊，則稱A是B的直接前趨，或稱B是A的直接後繼。拓撲排序的算法如下：
①在控制流圖中選取一個函數入口基本塊（沒有前趨）。
②在控制流圖中刪除該基本塊及其所發出的所有邊。
③重複執行①、②，直至輸出全部沒有前趨的基本塊。
當過程結束時，如果有向圖中的所有基本塊均已輸出，則說明有向圖中不存在迴路，否則說明有向圖存在迴路。
使用拓撲排序可以確定有向圖中是否有迴路，而在控制流圖中，只有循環存在時，才會存在迴路。因此，使用拓撲排序，不僅可以排列出程序基本塊執行的先後順序，還可以準確地確定函數中的循環起點基本塊和循環終點基本塊，通過循環變化後，可以將函數控制流圖變成完整的拓撲結構圖。這樣，計算函數WCET的時間，就轉化成了對拓撲結構中每一個頂點完成時間的計算。函數的WCET實際上就是最後一個頂點完成的時間。
6 結語
本文對目前WCET分析技術進行了詳細的研究討論，並給出了一個基於目標碼分析的WCET分析過程。採用拓撲排序算法，極大地簡化了WCET的計算，WCET計算的時間複雜度為O（n），其中n表示函數基本塊的數目。經過實際測試的驗證，該方法的運算速度快於ILP。
【參考文獻】
【1】AbsInt.The industry standard for static timing analysis[EB/OL].https：//www.absint.com/ait.
【2】Kirner R， Puschner P. Classification of WCET analysis techniques[C]// Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing （ISORC'05）. IEEE， 2005.
收藏