沈玲玲 李曉明

摘?要：

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

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

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

0?引言（Introduction）

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

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

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

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

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

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

2.1?任務(wù)分解

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

2.2?算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

3?實(shí)驗(yàn)驗(yàn)證（Experimental?validation）

3.1?實(shí)驗(yàn)環(huán)境

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

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

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

3.2?實(shí)驗(yàn)結(jié)果與分析

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

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

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

4?結(jié)論（Conclusion）

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

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

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

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

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

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

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

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

［7］?李欣，白興武.?基于Linux的嵌入式實(shí)時(shí)操作系統(tǒng)任務(wù)調(diào)度算法優(yōu)化［J］.?自動(dòng)化與儀器儀表，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.

作者簡(jiǎn)介：

沈玲玲（1999＼|），女，碩士生。研究領(lǐng)域：嵌入式軟件開發(fā)。

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