嵌入式自動測試系統實時調度研究

沈玲玲 李曉明

摘?要：

在嵌入式自動測試平臺的開發中，為保證測試過程中系統實時調度的穩定性與及時性，文章提出了一種基于最優優先級分配（OPA）算法的調度改進算法。首先通過任務建模和任務分解，將任務轉化為線程形式，并應用基于OPA算法的調度改進算法根據任務截止期等對任務隊列迭代任務排序，得到最佳調度排序以實現高效的調度狀態。改進算法對比實驗結果驗證了該算法相較于原算法具有更好的性能，包括提高系統的利用情況及任務平均計算時間，滿足系統測試過程的實時性需求。

關鍵詞：實時系統；調度算法；OPA算法；自動測試系統

中圖分類號：TP316??文獻標志碼：A

0?引言（Introduction）

隨著信息化時代的不斷發展，計算機技術已經深入滲透各個領域，其中實時系統［1］作為一項重要的技術，在航空航天、工業控制、交通管理等領域得到廣泛的應用。實時系統的重要性在于它能夠確保任務在特定時間范圍內得到及時響應和完成，而不同于一般的操作系統，實時系統的主要關注點不是高吞吐量，而是對任務響應時間和截止期的嚴格控制。

本文的嵌入式自動測試系統［2＼|3］是一種高效且靈活的測試系統，它由硬件和軟件兩部分組成，旨在實現自動化測試。嵌入式自動測試系統的主機運行的Linux操作系統是非實時的操作系統，為了達到實時性要求，以往都是采用給操作系統打補丁的方式改進其實時性，通過實時搶占補丁改善實時性問題。實時搶占補丁是通過中斷線程化、高精度時鐘、臨界區可搶占以及優先級繼承等方法改善Linux內核的實時性［4］。但是，隨著測試任務的復雜程度逐漸增大，為確保系統滿足實時性要求，需要選擇合適的調度算法應用于嵌入式自動測試系統。目前，實時調度算法有最早截止期優先（EDF）算法、最高優先級優先（HPF）算法、最低松弛度優先（LLF）算法及最優優先級分配（OPA）算法等。陳國良等［5］基于EDF算法實現了最小松弛度優先調度算法，并對其進行了改進，包括降低任務上下文切換頻率和最小化松弛度計算，以減輕調度過程中的顛簸現象。同時，李輝等［6］同樣基于EDF算法引入了半劃分調度的概念。經過改進的算法在實時任務處理器利用率存在較大差異時仍能調度成功，增強了Linux實時任務的可調度性，同時降低了上下文切換頻率，進而減少了系統開銷。

然而，鑒于所研究的實時系統［7］中存在任務間的依賴關系及相關優先級，最早截止期優先、最高優先級及最低松弛度優先3個算法與目前系統調度切換條件不匹配，綜合考慮多個因素后，決定采用最優優先級分配算法［8］進行擴展，達到提升系統的實時性目的。應用改進的OPA算法，期望能夠有效地管理測試任務的優先級，優化任務的執行順序，確保測試任務在其截止期前得到及時響應和完成，同時提高測試系統的可調度性和性能。

1?任務建模（Task?modelling）

在本文研究的系統中，任務的運行由系統中的組件［9］完成。每個組件代表一個獨立的執行單元，在其內部完成特定的任務或功能，并與其他組件協同工作，實現系統的整體功能。因此，組件在系統中起到類似線程的作用，通過并發執行有效地提高了系統的整體效率和性能。在此背景下，研究人員將對這些組件類型進行詳細分類，以便全面理解其在系統中的功能和起到的作用。

作業組件類型可根據數據傳輸方式分為5類。第一類組件僅接收輸入數據并進行處理；第二類組件專門負責數據輸出，無外部輸入，它將內部處理后的數據輸出至指定目標；第三類組件需接收外部輸入數據，并在內部處理后輸出結果；第四類組件（虛擬連接組件）結合了第一類組件和第二類組件的功能，兩個作業共享內存地址，使輸入數據可直接傳遞給另一組件，實現了連續的數據流動；第五類組件（TCPClient）雖然有輸入、輸出屬性，但是二者無直接關聯，輸入數據在運行時保持獨立，不影響輸出結果。根據組件屬性構成的任務集合模型如圖1所示。

2.1?任務分解

根據任務集合模型，每個節點代表一個線程τi，各線程之間的相互依賴關系可以通過有向邊表示。研究人員將任務進行分解，形成多個子任務集合，然后根據線程之間的依賴性，為每個線程分配適當的偏移值和截止期［10］。Di表示任務的相對截止期，即任務在每個周期內必須完成的時間范圍。故可將線程τi表示為（Ci，Di，αi）。其中：Ci和Di分別對應線程的最壞運行時間與截止期，αi表示線程對應的偏移量，初始任務偏移量為0。ri為任務開始時間，如果τi在ri點運行，那么依賴于τi的下一個作業τp將在rp=ri+Di點運行，其絕對截止期dp=rp+Dp，任務τp的執行時間窗口是（rp，dp］。任務分解示意圖如圖2所示。

2.2?算法設計

基于所提供的任務集合，在分解任務后，各個線程被賦予了適當的偏移時間和截止期，而不需要考慮線程之間的依賴關系，下一步的研究目標是為每個線程τi分配優先級。為了實現該目標，本研究采用改進的OPA算法。在OPA算法中，每個任務都有一個截止期，表示任務必須在截止時間之前完成。此外，每個任務還有一個執行時間，表示任務完成所需的時間。OPA算法的核心是為每個任務分配一個合適的優先級，以便滿足其截止時間的要求。這個分配過程是在考慮任務的截止時間和執行時間等因素的基礎上進行的。通常，截止時間緊迫的任務，會被分配更高的優先級，確保它們在截止時間之前執行。

改進后算法的核心思想是按優先級遞增的順序對所有線程進行迭代，并為它們分配優先級。初始狀態下，任務集合τ中的所有任務均未分配優先級。經過第i次迭代后，將任務集合τ劃分為兩個子集合O（i）和R（i）。其中，O（i）包含在進行到第i步之前已經成功分配優先級的任務，而R（i）則包含尚未被分配優先級的任務。

在進行任務的優先級分配之前，必須確保各線程的截止期早于任務的整體截止期，并評估任務集合的可調度性。目前，系統的處理器為雙核處理器，根據作業調度算法，當每個線程τi滿足以下不等式時，任務集合將具備可調度性，可以用如下公式表示：

∑αi≠αkWi（Di）+WK（Dk）<2×（Dk-Ck+1）[JZ）][JY]（1）

其中：WK（Dk）為任務集αk中優先級高于線程τk的其他所有線程的最大負載，Wi（Di）為在任務集αi中優先級高于線程τk的其他所有線程工作負載之和。

WK（Dk）=∑min（WK（Dk，Ok），Dk-Ck+1）[JZ）][JY]（2）

算法的總體設計思路如下：利用算法1分配線程優先級。若此分配未能成功，則隨之調整部分線程的偏移與截止期，確保某些線程可以成功獲得優先級分配。如果這樣的調整方法能夠找到可分配優先級的線程，那么繼續運用算法1進行優先級分配，否則，將此情況視為分配失敗。最終，算法的輸出結果為成功分配優先級的調度狀態。線程的富余時間則被定義為線程結束時間與截止期之間的最小間隔，可以用如下公式表示：

Si=Dk-Ck-∑αi≠αkWi（Di）+WK（Dk）2[JZ）][JY]（3）

定義線程的歸一化富余時間S′[KG-1mm]i=Si/Dk。在本研究中，對任務模型進行了更全面的考慮，將線程的截止期調節變換為線程的富余時間調節，富余時間較多的線程將部分富余時間贈予時間緊缺的線程。在這一機制下，富余時間充裕的線程被稱為贈予線程，而接收富余時間的線程則被稱為受贈線程。

3?實驗驗證（Experimental?validation）

3.1?實驗環境

本文介紹的嵌入式自動測試系統在3個獨立的工作環境中進行了部署，分別為上位機環境、主機環境和前端環境，整體軟件采用Java技術及Eclipse?RCP平臺框架搭建而成。系統提供了用戶創建、編輯和部署上位機測試應用、主機測試應用和前端數字信號處理（DSP）程序等功能。實驗室自主研發的通用嵌入式測試儀器系統如圖3所示。測試系統平臺結構如圖4所示。

此外，該系統還負責對前端資源進行管理，執行測試流程、監督測試過程、顯示測試結果。實驗任務集的生成通常由上位機實現，在上位機環境中，用戶可以通過交互式界面創建任務。系統采用圖形化的編程方法，通過將各種功能組件進行組合，以拖放和連線的方式實現測試功能。所有的功能組件按照時間片的方式并行運行，同時根據端口之間的連線確定數據交互的內容。每個任務組件的執行過程類似于一個線程任務，這些任務組件可以自由地拖放以構建所需的任務集合。任務集的生成示例如圖5所示。編輯得到的應用程序同樣基于XML文件存儲，并可以被運行平臺加載運行。

在每次實驗運行中，將生成的任務集加載到系統中，并執行這些任務，模擬任務執行期間資源工作條件，包括可能的競爭條件、資源爭用等。任務應按照其屬性和生成順序依次執行。對于每個任務，記錄其完成時間，即任務開始執行到任務完成的時間。為了獲得可靠的結果，可以實驗運行多次，每次運行需要使用不同的隨機任務集。

3.2?實驗結果與分析

為了充分評估本文所提算法的性能，研究人員將其與基本的OPA算法、原系統調度算法的性能進行橫向比較，以全面觀察所提出算法的優越性和改進效果，以便研究人員深入理解算法的性能，并進行合理評估。

為了綜合評估本文所提算法對任務性能的影響，設計了兩個測試指標，分別是算法性能和任務計算時間。進行多次隨機實驗對算法在不同情境下的調度性能進行評估與比較。在第一組實驗中，研究人員通過系統利用情況（U*）評估算法的調度性能。分別采用原系統調度算法、基本的OPA算法及改進的算法對系統利用情況進行測試，在測試平臺上隨機生成任務，圖6中的結果顯示改進的算法檢測率上升明顯，得出改進的調度算法的性能得以提升的結論。

使用改進算法后，隨著節點數量增加，運行速率明顯比改進前有大幅上升，表示改進算法性能明顯高于原系統算法。

4?結論（Conclusion）

本研究基于實驗室自行研發的嵌入式自動化測試平臺，針對其運行過程中的調度問題提出了一種基于優先級分配算法的改進算法。通過任務建模和算法設計，將系統的任務進行細致的分解，將其轉化為線程級別的調度問題，并采用優先級迭代策略生成最終的調度狀態。實驗結果表明，改進的算法在兩個關鍵性能指標，即系統利用率和節點總數量方面，都取得了顯著的提升。總的來看，本文提出的改進算法在不同情境下均表現出良好的性能，為提升實時系統的任務調度效率提供了有益的思路和方法。這項研究不僅在理論層面豐富了實時系統調度領域的知識體系，還在實際應用中展示出了較高的實用價值。

參考文獻（References）

［1］?王穎潔，周寬久，李明楚.?實時嵌入式系統的WCET分析與預測研究綜述［J］.?計算機科學，2019，46（S1）：16＼|22.

［2］?齊永龍，宋斌，劉道煦.?國外自動測試系統發展綜述［J］.?國外電子測量技術，2015，34（12）：1＼|4，7.

［3］?曹晟.?面向嵌入式智能設備的多核操作系統任務調度算法的研究與實現［D］.?北京：北京郵電大學，2021.

［4］?王樸，周晴.?基于龍芯1E的嵌入式Linux實時性的優化與可靠性設計［J］.?微電子學與計算機，2019，36（11）：11＼|15.

［5］?陳國良，朱艷軍.?基于Linux的多核實時任務調度算法改進［J］.?計算機測量與控制，2020，28（11）：238＼|241，246.

［6］?李輝，劉志紅.?基于半劃分調度的Linux實時調度算法改進［J］.?計算機與數字工程，2022，50（7）：1615＼|1619.

［7］?李欣，白興武.?基于Linux的嵌入式實時操作系統任務調度算法優化［J］.?自動化與儀器儀表，2020（9）：48＼|51.

［8］?DAVIS?R?I，BURNS?A.?Improved?priority?assignment?for?global?fixed?priority?pre＼|emptive?scheduling?in?multiprocessor?real＼|time?systems［J］.?Real＼|time?systems，2011，47（1）：1＼|40.

［9］?葉可欣.?儀器功能組件可視化管理及應用編程方法研究［D］.?杭州：浙江大學，2017.

［10］?[ZK（]EKBERG?P，YI?W.?Bounding?and?shaping?the?demand?of?generalized?mixed＼|criticality?sporadic?task?systems［J］.?Real＼|time?systems，2014，50（1）：48＼|86.

作者簡介：

沈玲玲（1999＼|），女，碩士生。研究領域：嵌入式軟件開發。

李曉明（1976＼|），男，博士，副教授。研究領域：機電系統集成，軟件開發。