沈玲玲 李曉明

摘?要：

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

關(guān)鍵詞：實時系統(tǒng)；調(diào)度算法；OPA算法；自動測試系統(tǒng)

中圖分類號：TP316??文獻(xiàn)標(biāo)志碼：A

0?引言（Introduction）

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

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

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

1?任務(wù)建模（Task?modelling）

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

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

2.1?任務(wù)分解

根據(jù)任務(wù)集合模型，每個節(jié)點代表一個線程τi，各線程之間的相互依賴關(guān)系可以通過有向邊表示。研究人員將任務(wù)進(jìn)行分解，形成多個子任務(wù)集合，然后根據(jù)線程之間的依賴性，為每個線程分配適當(dāng)?shù)钠浦岛徒刂蛊冢?0］。Di表示任務(wù)的相對截止期，即任務(wù)在每個周期內(nèi)必須完成的時間范圍。故可將線程τi表示為（Ci，Di，αi）。其中：Ci和Di分別對應(yīng)線程的最壞運行時間與截止期，αi表示線程對應(yīng)的偏移量，初始任務(wù)偏移量為0。ri為任務(wù)開始時間，如果τi在ri點運行，那么依賴于τi的下一個作業(yè)τp將在rp=ri+Di點運行，其絕對截止期dp=rp+Dp，任務(wù)τp的執(zhí)行時間窗口是（rp，dp］。任務(wù)分解示意圖如圖2所示。

2.2?算法設(shè)計

基于所提供的任務(wù)集合，在分解任務(wù)后，各個線程被賦予了適當(dāng)?shù)钠茣r間和截止期，而不需要考慮線程之間的依賴關(guān)系，下一步的研究目標(biāo)是為每個線程τi分配優(yōu)先級。為了實現(xiàn)該目標(biāo)，本研究采用改進(jìn)的OPA算法。在OPA算法中，每個任務(wù)都有一個截止期，表示任務(wù)必須在截止時間之前完成。此外，每個任務(wù)還有一個執(zhí)行時間，表示任務(wù)完成所需的時間。OPA算法的核心是為每個任務(wù)分配一個合適的優(yōu)先級，以便滿足其截止時間的要求。這個分配過程是在考慮任務(wù)的截止時間和執(zhí)行時間等因素的基礎(chǔ)上進(jìn)行的。通常，截止時間緊迫的任務(wù)，會被分配更高的優(yōu)先級，確保它們在截止時間之前執(zhí)行。

改進(jìn)后算法的核心思想是按優(yōu)先級遞增的順序?qū)λ芯€程進(jìn)行迭代，并為它們分配優(yōu)先級。初始狀態(tài)下，任務(wù)集合τ中的所有任務(wù)均未分配優(yōu)先級。經(jīng)過第i次迭代后，將任務(wù)集合τ劃分為兩個子集合O（i）和R（i）。其中，O（i）包含在進(jìn)行到第i步之前已經(jīng)成功分配優(yōu)先級的任務(wù)，而R（i）則包含尚未被分配優(yōu)先級的任務(wù)。

在進(jìn)行任務(wù)的優(yōu)先級分配之前，必須確保各線程的截止期早于任務(wù)的整體截止期，并評估任務(wù)集合的可調(diào)度性。目前，系統(tǒng)的處理器為雙核處理器，根據(jù)作業(yè)調(diào)度算法，當(dāng)每個線程τi滿足以下不等式時，任務(wù)集合將具備可調(diào)度性，可以用如下公式表示：

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

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

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

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

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

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

3?實驗驗證（Experimental?validation）

3.1?實驗環(huán)境

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

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

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

3.2?實驗結(jié)果與分析

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

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

使用改進(jìn)算法后，隨著節(jié)點數(shù)量增加，運行速率明顯比改進(jìn)前有大幅上升，表示改進(jìn)算法性能明顯高于原系統(tǒng)算法。

4?結(jié)論（Conclusion）

本研究基于實驗室自行研發(fā)的嵌入式自動化測試平臺，針對其運行過程中的調(diào)度問題提出了一種基于優(yōu)先級分配算法的改進(jìn)算法。通過任務(wù)建模和算法設(shè)計，將系統(tǒng)的任務(wù)進(jìn)行細(xì)致的分解，將其轉(zhuǎn)化為線程級別的調(diào)度問題，并采用優(yōu)先級迭代策略生成最終的調(diào)度狀態(tài)。實驗結(jié)果表明，改進(jìn)的算法在兩個關(guān)鍵性能指標(biāo)，即系統(tǒng)利用率和節(jié)點總數(shù)量方面，都取得了顯著的提升?？偟膩砜?，本文提出的改進(jìn)算法在不同情境下均表現(xiàn)出良好的性能，為提升實時系統(tǒng)的任務(wù)調(diào)度效率提供了有益的思路和方法。這項研究不僅在理論層面豐富了實時系統(tǒng)調(diào)度領(lǐng)域的知識體系，還在實際應(yīng)用中展示出了較高的實用價值。

參考文獻(xiàn)（References）

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

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

［3］?曹晟.?面向嵌入式智能設(shè)備的多核操作系統(tǒng)任務(wù)調(diào)度算法的研究與實現(xiàn)［D］.?北京：北京郵電大學(xué)，2021.

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

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

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

［7］?李欣，白興武.?基于Linux的嵌入式實時操作系統(tǒng)任務(wù)調(diào)度算法優(yōu)化［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］?葉可欣.?儀器功能組件可視化管理及應(yīng)用編程方法研究［D］.?杭州：浙江大學(xué)，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＼|），女，碩士生。研究領(lǐng)域：嵌入式軟件開發(fā)。

李曉明（1976＼|），男，博士，副教授。研究領(lǐng)域：機(jī)電系統(tǒng)集成，軟件開發(fā)。