基于離線利用率分析的混合關鍵級任務調度優化研究
2022-12-31 00:00:00柴淞威張鳳登唐瑩
計算機應用研究 2022年11期
摘 要：現主流的混合關鍵級調度算法在系統高關鍵級狀態下主要通過拋棄低關鍵級任務來保證高關鍵級任務的執行，進而保證系統的正確性。此方法常常導致低關鍵級任務無法執行但系統資源卻過剩的問題發生，故基于該問題提出復合型SDU（schedule depend on utilization）調度算法。該方法根據任務集對系統資源需求情況的不同進行利用率區間的劃分，通過對各個區間實際使用情況的分析，設計相應的子算法進行調度，并提出了SDU算法對應的可調度性判據。仿真實驗結果表明，相較于混合關鍵級任務調度領域主流的EDF-VD（earliest deadline first-virtual deadline）算法，所提SDU算法可將系統對任務集的調度率提升30%，并在相同情況下將系統對低關鍵級任務的執行率提升165%，證明了該算法可以極大地提高系統資源使用率，并保證系統服務完整性。
關鍵詞：混合關鍵級；任務調度；資源需求；復合算法
中圖分類號：TP316.2 文獻標志碼：A
文章編號：1001-3695（2022）11-027-3371-07
doi：10.19734/j.issn.1001-3695.2022.04.0188
Research on scheduling optimization of mixed-criticality tasks based on offline utilization analysis
Chai Songwei，Zhang Fengdeng，Tang Ying
（School of Optical-Electrical amp; Computer Engineering，University of Shanghai for Science amp; Technology，Shanghai 200093，China）
Abstract：The current mainstream mixed-criticality scheduling algorithm guarantees the execution of high-criticality tasks by discarding low-critical tasks when the system is in a high-critical state，thereby ensuring the correctness of the system.Since this method often leads to the problem that low-critical tasks cannot execute，but the system resources are excessive.Based on this problem，this paper proposed a composite SDU scheduling algorithm which divided the utilization interval according to the resource requirements of the task set.According to the analysis of actual usage of each interval，it designed the corresponding algorithm for scheduling，and proposed the schedulability criterion corresponding to the SDU algorithm.The simulation results show that，comparing with the mainstream algorithm EDF-VD in the field of mixed-critical task scheduling，the SDU algorithm can improve the system’s scheduling rate by 30% and under the same conditions，the execution rate of low-critical tasks is increased by 165%，which greatly improves the utilization rate of system resources and ensures the integrity of system services.
Key words：mixed-criticality system；task scheduling；source requirement；compound algorithm
基金項目：國家自然科學基金資助項目（71840003）；上海市自然科學基金資助項目（15ZR1429300）
作者簡介：柴淞威（1998-），男，浙江寧波人，碩士研究生，主要研究方向為混合關鍵級任務調度、Linux內核、操作系統功耗性能優化；張鳳登（1963-），男（通信作者），山東青島人，教授，博導，博士，主要研究方向為汽車電子與現場總線、分布式實時系統（fdzhang@usst.edu.cn）；唐瑩（1981-），女，上海人，博士，主要研究方向為實時系統.
0 引言
在工業發展過程中，集成化的出現有效地解決了系統體積增加與設計復雜化的問題，同時也為任務調度帶來了新的挑戰。例如在汽車電子系統中，制動任務執行失敗與娛樂任務執行失敗所產生的后果是截然不同的，故若將其視為具有相同重要性的任務進行調度，可能會產生由于后者搶占前者，而導致前者執行失敗的情況發生，其產生后果的嚴重性是無法估量的［1，2］。
為此Vestal提出了混合關鍵級系統（mixed-criticality system，MCS）的概念，并在傳統實時任務模型的基礎上建立了混合關鍵級任務模型：根據任務執行失敗產生后果的嚴重性為任務賦予不同的關鍵級屬性，同時將任務的WCET（worst case execution time）值擴展為一個矢量，不同的安全等級對應不同的WCET值［3］。基于Vestal所提出的混合關鍵級任務模型，不少學者開始對混合關鍵級任務調度展開研究。然而在Vestal所定義的混合關鍵級系統運行行為中：一旦系統進入高關鍵級狀態，高關鍵級任務的WCET就會從較為樂觀的WCET值變為極為保守的WCET值，增加任務對資源的需求，導致系統資源分配短缺。考慮到系統資源緊缺下對低關鍵級任務的調度會帶來嚴重的算法復雜性問題且無法覆蓋所有可能發生的情況，故目前針對混合關鍵級任務調度的算法一般都是通過在關鍵級提升后直接丟棄低關鍵級任務來保證高關鍵任務的執行，從而保證系統的正確性。然而該處理方式往往會出現在系統資源較為充分情況下，低關鍵任務被舍棄的情況。雖然低關鍵級任務執行的失敗并不會影響系統的正確性，但低關鍵級任務被過多地舍棄仍會對系統執行精確性和用戶體驗造成影響。
故基于系統高關鍵級下調度低關鍵級任務所帶來的算法復雜性和低關鍵級任務所具有意義之間的矛盾，本文基于雙關鍵級系統展開研究，在Vestal所提出任務模型的基礎上，通過離線分析任務集對系統資源的需求情況，提出了復合型SDU算法。SDU算法將任務集對系統資源的需求分為三個等級，根據各個等級的實際情況選用相對應的算法進行任務調度：在任務集對系統資源需求較小時，選用WCR（worst case reservation）算法，直接使用所有任務在高關鍵級下的WCET值進行調度，保證算法的簡潔性；在任務集對系統資源需求較高時，設計EDF-SLOT算法，在保證系統正確性前提下，盡可能地利用系統中零散的計算資源來進行低關鍵級任務的調度；在任務集對系統資源需求非常高時，設計EDF-HOL（high criticality only，HOL）算法，拋棄所有低關鍵級任務來保證高關鍵級任務的執行。同時為了保證算法的簡潔性，EDF-HOL算法直接使用高關鍵級任務在高關鍵級下的WCET值進行調度。
在SDU算法中，通過使用對任務集利用率離線分析并選用相應子算法進行調度的方式，可以在覆蓋雙關鍵級系統所有可能發生情況的同時，有效地減少算法的復雜性，提高任務集可調度率和低關鍵級任務在高關鍵級狀態下的執行率，提高系統資源的使用率，保證系統服務的完整性。
1 相關研究
混合關鍵級系統根據任務執行失敗產生的后果，賦予任務不同的關鍵級，并根據任務各自的關鍵級為其分配相應的WCET值。可見混合關鍵級系統的調度環境相較于傳統實時系統而言是更為復雜的。同時由于在傳統實時系統調度過程中，任務的關鍵級被認為是相等的，該調度思想與混合關鍵級系統的調度思想相悖，故混合關鍵級系統的任務調度并不能直接套用傳統實時系統中的已有調度算法，需要展開專門研究。
2007，Vestal在實時系統領域國際會議RTSS（real-time system symposium）上正式提出了混合關鍵級系統這個概念，并基于Audsley所提出的優先級分配方法提出了適用于混合關鍵級任務調度的固定優先級調度策略［3］。Dorin在其發表的論文中對固定優先級的混合關鍵級任務調度方法進行了可調度性與靈敏度分析，證明了Audsley所提出的OPA（optimal priority assignment）算法對混合關鍵級任務的優先級分配是最優的，同時也證明了在時間要求嚴格的系統中，Vestal所改進的固定優先級調度策略是最優的［2］。Baruah在對混合關鍵級系統任務調度問題經過深入研究后，在其發表的論文中證明了混合關鍵級任務調度是一個NP難問題。同時基于傳統實時任務調度中的EDF算法，Baruah提出了適用于混合關鍵級系統任務調度的EDF-VD算法，其主要思想是通過為高關鍵級任務分配一個相對較小的虛擬時限，使高關鍵級任務能夠基于傳統EDF算法獲得更高的優先級，從而克服了傳統EDF算法中優先級僅僅由任務時限決定而導致關鍵級反轉的缺陷，有效地平衡了任務優先級與關鍵級之間的關系。同時EDF-VD算法在可調度性上所明確的加速因子和可調度性條件，也為后續對混合關鍵級任務調度的研究提供了重要的基礎［4，5］。在國內，針對混合關鍵級系統中任務搶占相較傳統實時系統中任務搶占的特殊性，浙江大學顧宗華教授團隊提出了一種基于啟發式閾值的調度算法，該算法通過提高系統的可調度性、減小任務調度過程中搶占的次數來實現對系統整體資源利用率的有效提升。電子科技大學的熊光澤教授團隊通過采用動態優先級最早時限優先調度和靜態優先級最早時限優先調度的方法，對任務的調度條件進行了深入的理論分析［2］。
從目前國內外學者對混合關鍵級任務調度的研究結果可以看出，混合關鍵級系統所涉及的相關調度方法已經受到了廣泛地關注，且取得了大量的研究成果。但當前多數混合關鍵級任務調度策略仍受到“一旦低關鍵級模式下出現高關鍵級任務執行超時，就完全拋棄低關鍵級任務，且所有的高關鍵級任務都進入高關鍵模式”這個基本思想的局限。雖然該思想保證了高關鍵級任務對處理器的充分使用，但對低關鍵級任務的處理過于消極，忽略了低關鍵級任務對系統服務完整性的意義。
2 背景知識
2.1 任務模型
在雙關鍵級系統中，本文假設其任務集為ψ，它由n個不同關鍵級且相互獨立可搶占的周期任務τi組成，具體可表示為：ψ={τ1，τ2，…，τn}。每個任務實體τi由一個四元組組成τi=（Ti，Di，Li，Ci）［6］。其中：
a）Ti表示任務的周期，即一個任務中相鄰兩個作業釋放的最小時間間隔。
b）Di表示任務的相對截至時間。由于本文主要研究的是具有隱式截止期的任務，故本文中任務的周期Ti與任務的相對截至時限Di相等。
c）Li表示任務τi所具有的關鍵等級，在雙關鍵級系統中，Li∈{LHI，LLO}代表高關鍵級或低關鍵級。同時，本文定義τLii為關鍵級屬性為Li的任務τi。
d）Ci是一個矢量，表示任務τi的最壞執行時間，即WCET值，且Ci=〈ci（1），…，ci（χ）〉。當χ≤Li（χ，Li∈?+），即系統執行關鍵級χ小于或等于任務自身的關鍵級屬性時，本文認為系統執行關鍵級越高，任務的最壞執行時間就越長，即ci（1）lt;ci（2）lt;…lt;ci（χ）；當χgt;Li（χ，Li∈? +），即系統執行關鍵級χ大于任務自身所具有的關鍵級屬性時，本文認為此時隨著系統運行關鍵級的增加，任務的最壞執行時間將保持不變，即ci（Li）=ci（Li+1）=…ci（χ）。
由于本課題針對的是雙關鍵級系統，所以本文將高關鍵級任務的最壞執行時間表示為CLHIi（LLO）與CLHIi（LHI）（CLHIi（LHI）gt;CLHIi（LLO）），將低關鍵級任務的最壞執行時間表示為CLLOi（LLO）與CLLOi（LHI）（CLLOi（LLO）=CLLOi（LHI）），其中CLii（χ）表示具有關鍵級屬性Li的任務τi在系統執行關鍵級為χ（χ∈{LLO，LHI}）下的最壞執行時間。
基于上述任務模型中，本文將任務τi的每一次執行定義為一個作業，作業每次都在任務周期的開始處被釋放。同時將任務τi產生的第k個作業記為Ji，k，作業Ji，k亦由一個四元組組成Ji，k=（ri，k，di，k，li，k，ci，k）
a）ri，k為作業Ji，k的釋放時間，在此設定：每次任務到達就立即釋放一個作業。
b）di，k為作業Ji，k的絕對截至時間，di，k=ri，k+Di。
c）li，k∈{LLO，LHI}為作業Ji，k所具有的關鍵級屬性，該值與作業所屬任務的關鍵級屬性Li相同。
d）ci，k為作業Ji，k的最壞執行時間，該值與其所屬任務的CLii（χ）相同。
該作業模型的含義為：關鍵級為li，k的作業在時間窗口［ri，k，di，k］中獲得一段最長為ci，k的執行時間，其中作業的實際執行時間ei，k滿足ei，k≤ci，k。同時，本文將一個任務所釋放的所有作業執行時間的集合記做一個調度實例I［6］。
2.2 基于動態需求邊界函數的可調度性分析
動態需求邊界函數分析是傳統實時系統中常見的可調度性分析方法。主要通過比較任務集中所有任務釋放作業的響應時間上限和該作業對應的相對截至時限，來判斷任務集中任務是否可被調度。考慮到混合關鍵級任務相較與傳統實時任務，雖在任務模型上進行了擴充，但在某個時間點上，一個任務仍只存在一個WCET值，故該方法也可用于對混合關鍵級任務的可調度性分析。
在傳統實時系統中，Audsley提出了一種基于靜態優先級搶占的可調度性分析方法。其定義動態需求邊界函數為ri=Ci+Bki+Ii，其中：ri是任務τi完成所需的最長時間；Ci表示該任務自身的WCET值；Bi表示優先級高于τi的任務堵塞信號量所產生的時間；Ii表示優先級高于τi的任務τj，在搶占τi運行后，對τi的最長完成時間造成的影響。
在該方法中，Audsley主要分析了優先級高于τi的任務τj，在發生搶占后對τi的最長運行時間造成的影響。其假設該影響為Ii，其中ri為任務τi完成所需的最長時間，Tj為任務τj釋放作業的周期，Cj為τj的最壞運行時間。
最終利用迭代法對任務τi的最長運行ri時間進行求解［7］。
由于在本文調度算法是基于EDF的動態優先級調度算法，所以當發生多級的搶占時，上述公式的迭代深度會變得很高，最終導致對動態需求邊界的運算占據大量屬于任務本身的運行時間［8］。故基于Audsley的想法，本文將針對獨立任務，設計一種基于EDF動態優先級分配的最長運行時間計算函數。
由于本文所研究的均為獨立任務，并不涉及共享資源的訪問，故Bi=0，在此基礎上從單個時間點的角度展開對任務最長執行時間的思考：由于獨立作業Ji，k的最長執行時間ri的主要決定因素為就緒隊列中優先級高于作業Ji，k的作業，而就緒隊列中作業順序的變化發生在作業完成與作業到達這兩個時間點。故為了減少由于迭代計算帶來的額外系統資源消耗，在此設計：當且僅當作業完成或到達時，才對就緒隊列中所有作業的最長執行時間進行計算。同時考慮到作業之間的搶占，在此將ri=Ci+Bi+Ii中的作業最壞執行時間修改為Ri，即作業剩余需要執行時間（remaining time）。由于任務所釋放作業的實際執行時間是在運行時才被確定，而作業已執行的時間是可以記錄的。故對作業剩余所需執行時間作出如下定義：
定義1 作業剩余執行時間Ri等于作業對應任務在當前系統執行關鍵級下的WCET與作業已執行時間的差。
綜上所述可以得出，在某個時間點上，任務的最長運行時間計算函數：
其中：hp（i）表示優先級高于任務τi的任務號。
從式（4）可以發現，對所有任務進行更新所需的時間復雜度為O（1）。同時由于該函數本身的結構就較為簡單，若在有新任務到達或舊任務釋放新作業時調用該函數，可以做到在精確判斷任務到達或作業釋放對已到達任務所釋放作業帶來影響的同時，占用較小的系統計算時間。本文也將利用該函數對任務運行過程中的超時行為進行判斷。
2.3 系統行為
混合關鍵級系統的運行都是從最低關鍵級開始的。在系統運行過程中，任務周期性地釋放混合關鍵級作業。一旦有作業就緒，系統就將該作業加入到就緒隊列，等待調度器的調度。處理器總是選擇位于就緒作業隊列頭部的作業進行執行［9，10］。
在運行過程中，通過比較任務釋放作業的實際執行時間與任務在當前系統關鍵級對應的WCET來判斷是否超時。當有任何比此時系統運行關鍵級高的任務所釋放作業的實際執行時間超過其對應關鍵級下的最壞執行時間時，系統的執行關鍵級別就會提升。系統執行關鍵級提升后，關鍵級屬性小于系統執行關鍵級的任務將不被要求必須完成。當系統運行結束，若無高于系統關鍵級的任務所釋放的作業執行超時，則認為系統行為正確，否則認為系統運行出錯。
在此對系統運行過程中各關鍵級與系統正確性的判斷作出如下定義：
定義2 作業運行關鍵級的確定。在一個實例I中，任一混合關鍵級作業Ji，k的執行關鍵級是滿足ci，k≤Cj（χ）的關鍵級χ的最小值。
定義3 任務執行關鍵級的確定。在混合關鍵級系統的一個調度實例I中，任一混合關鍵級任務的執行關鍵級Lexec是其所釋放所有作業中的最大作業運行關鍵級。
定義4 系統運行關鍵級的確認。在混合關鍵級系統中，系統的執行關鍵級是任務集中所有任務執行關鍵級的最大值。
定義5 系統行為正確性的判斷。混合關鍵級系統在關鍵等級χ上被認為是執行正確的，當且僅當所有大于等于該系統執行關鍵級的任務所釋放的作業能在其時限內完成［11］。
通過以上定義可以發現：任務所釋放作業的實際執行時間決定了其所屬任務的運行關鍵級，而任務集中所有任務的運行關鍵級又決定了系統最終的執行關鍵級。由此可以發現導致關鍵級發生變化的根本原因是作業執行時間的變化，而環境是物理世界決定作業執行長短的主要因素。例如在極端環境通信受阻情況下，作業的運行時間與平時在室內的運行時間相差巨大，由此也就導致了同一任務在不同環境下所呈現的不同關鍵級與運行行為。總結以上論述，本文可以得出：是環境影響了作業執行時間，從而影響了系統的執行關鍵級，而系統的執行關鍵級實際上可以認為是對環境的一種客觀反映。
3 基于利用率的混合關鍵級調度算法優化
3.1 形式化描述符號表
本節所使用的相關符號說明如表1所示。
3.2 SDU算法可調度性判據
混合關鍵級系統與傳統實時系統在調度過程中存在的差異主要體現在對系統行為正確性的判斷上發生了改變，即在混合關鍵級系統中，當且僅當所有大于或等于系統執行關鍵級的任務所釋放的作業能在其時限內完成才算系統執行正確。系統的執行正確性是所有調度機制在設計之初最根本的要求。
利用率是任務對系統資源需求情況最直觀的一個反映，而WCET值作為利用率的決定性因素，可認為是對任務所釋放作業的實際執行時間的評估。在雙關鍵級任務系統中，高關鍵級任務的執行成功與否往往直接影響系統運行的正確性（在實際生活中即與人的生命安全相關），所以為其分配一個較為樂觀的WCET值與極為保守的WCET值，以便結合實際運行環境的好壞來準確地反映該任務在當前執行環境下對系統資源的需求［12］。
基于上述對混合關鍵級系統執行正確性原則以及相關概念的理解，在此認為：在設計雙關鍵級系統任務調度算法過程中，“保證高關鍵級任務即使在最惡劣的環境下依舊有充足的系統資源”是設計混合關鍵級任務調度機制最根本的原則，即UHIHI≤1。
3.3 利用率區間的劃分
給定系統中任一處理器Pi以及分配到其上的任務子集ψi，定義ψLOi與ψHIi分別表示被分配到處理器Pi上的低關鍵級任務與高關鍵級任務的集合，即
由2.3節可知，環境會影響作業的執行時間，從而影響系統的執行關鍵級。而在實際運行過程中，環境始終是變化的，由此也產生了一個問題：環境的變化致使系統執行關鍵級變化，從而使任務所選取的WCET值改變，最終導致在原先低關鍵級狀態下對所有任務的基于利用率的可調度性評估失效。故本節基于離線分析思想，針對雙關鍵級任務，通過對所有可能發生的利用率情況進行全局考慮與區間劃分來對該問題進行解決，如表2所示。
基于ULOALL≤1且UHIALL≥1的系統資源使用情況，本文提出EDF-SLOT算法進行調度。通過對系統高關鍵級狀態時，低關鍵級任務的執行設定條件，在不影響高關鍵級任務執行的情況下合理地利用系統中的空閑資源執行低關鍵級任務，提升低關鍵級任務的可調度率以此提升系統的整體服務質量。
當ULOALL≥1時，絕大數的混合關鍵級調度算法均認為此種情況是無法調度的。但從系統的角度思考，可以認為：如果在所有任務都選用低關鍵級下的WCET值時，依舊沒有充足的系統資源可供所有任務使用，說明系統資源對當前任務而言已極度緊缺。故為了保證系統執行的正確性，此時將拋棄所有低關鍵級任務來保證高關鍵級任務的執行。同時由于當前的研究均是在滿足SDU算法可調度條件UHIHI≤1下進行的，即滿足高關鍵級任務在高關鍵級狀態下的EDF可調度條件。故在不增加系統算法復雜度的情況下，本文提出EDF-HOL算法，選用高關鍵級任務在高關鍵級下的WCET值進行EDF調度，從而將混合關鍵級任務調度簡化為傳統實時任務調度。
觀察ULOALL≤1且UHIALL≤1時的情況發現：即使所有任務都選用其高關鍵級下的WCET值，根據EDF可調度性原則，該任務集仍可被EDF調度，說明此時系統資源對任務集來說是充分的。故為了保證算法簡潔性，可通過選取所有任務在高關鍵級下的WCET值來將混合關鍵級任務簡化為傳統實時任務進行調度。
3.4 對應區間算法描述
3.4.1 EDF-SLOT算法
在EDF-SLOT算法設計過程中，本文將高關鍵級任務的狀態分為掛起（suspend）、運行（running）、未到達（not arrive）三種。掛起是指高關鍵級任務所釋放作業在運行時，由于更高優先級任務釋放作業的到達，而導致目前正在運行的作業被搶占。運行表示該高關鍵級任務所釋放的作業正在當前處理器核上被執行。未到達表示該高關鍵級任務所釋放的作業還未到達。
設定系統從低關鍵級開始運行并在開始時使用傳統EDF算法進行調度。由于此時系統處于低關鍵級，故所有任務的WCET值都選擇低關鍵級下的WCET值進行調度。在此階段，對任務的關鍵級屬性不進行處理，均按照一般實時任務進行調度。一旦有高關鍵級任務的實際執行時間超過其低關鍵級下的WCET值，則系統發生關鍵級切換，進入高關鍵級狀態。一旦系統進入高關鍵級狀態，所有任務均按照高關鍵級別下的WCET值進行調度，但仍繼續使用最早截止期優先原則從運行隊列中挑選任務進行執行。不同的是，若在此階段選中的任務為低關鍵級任務，則其需滿足如下條件才能執行：
a）低關鍵級任務不能搶占高關鍵級任務。
b）掛起隊列中所有高關鍵級任務的動態需求邊界函數在加上低關鍵級任務的剩余執行時間后依舊滿足需求（關鍵級發生切換后，高關鍵級任務的動態需求邊界函數僅考慮自身剩余執行時間與優先級高于自身的高關鍵級任務的剩余執行時間）。
c）當前系統時間在加上所要執行的低關鍵級任務的剩余執行時間后，仍不超過最近一個即將到達的高關鍵級任務的到達時間。
基于上述論述，在此給出EDF-SLOT算法的偽代碼。
算法1 EDF-SLOT算法
輸入：作業集τ。
輸出：若無高關鍵級作業執行超時，則返回調度信息；否則，返回FAIL。
將所有在0時刻到達的作業按最早截止期優先順序插入針對所有任務的就緒隊列all_queue，同時將所有在0時刻到達的高關鍵級任務所釋放的作業也按最早截止期優先順序插入僅針對高關鍵級任務的就緒隊列high_queue。
計算all_queue和high_queue中所有作業的剩余執行時間，以及high_queue中作業的動態需求邊界
將系統關鍵級初始化為低關鍵級并計算所有任務的超周期
while tlt;=hyperperiod do
curr=peek（all_queue）
if 當前作業curr的實際執行時間超過其低關鍵下WCET then
slot_schedule（）
else
edf_schedule（）
end if
end while
由于在系統未發生關鍵級變遷時，所使用的是較為經典的EDF算法，故在此處不再對其進行贅述，只對在系統關鍵級發生變化后所使用的Slot_Schedule算法進行敘述。
算法2 系統高關鍵級下調度機制Slot_Schedule
輸入：作業集τ。
輸出：若無高關鍵級作業執行失敗，則返回調度信息；否則，返回FAIL。
while tlt;=hyperperiod do
curr=peek（all_queue）
if curr=NULL then
continue；
if peek=low then
if t+RemainingExecTimelt;Deadline then
discard（）；
if t+RemainingExecTimelt;=GetProximalHighArrivalTime（） amp;amp; JudgeLow（RemainingExecTime） then
execute（）；
else
discard（）；
endif
end if
if curr=high then
if tlt;RemainingExecTimelt;Deadline then
break；//存在高關鍵級任務超時，調度失敗
else
execute（）；
end if
end while
在此處，peek函數主要用于在all_queue中，按照最早截止期優先原則選取優先級最高的作業進行執行； RemainingExecTime表示當前作業的剩余最長所需執行時間，若選中作業的剩余執行時間加上當前時間超過該作業的絕對截止期，則對該作業的關鍵級屬性進行判斷，若該作業為低關鍵級任務釋放的作業則將其拋棄，若為高關鍵級任務釋放的作業，則直接返回FAIL，調度失敗；GetProximalHigharrivalTime（）函數主要用于獲取所有還未到達任務中，最近一個高關鍵級任務釋放作業的到達時間； JudgeLow（）函數主要用于判斷當前低關鍵級任務釋放作業的執行是否會使掛起狀態下的高關鍵級任務釋放作業的動態需求邊界失效，其傳入參數為低關鍵級作業的剩余執行時間RemainingExecTime，若失效，則將該低關鍵級作業拋棄，否則執行該低關鍵級作業。
3.4.2 EDF-HOL算法
EDF-HOL算法主要適用于所有任務在低關鍵級狀態下利用率總和大于1的情況，即ULOALLgt;1。由于在3.2節中已明確地提出雙關鍵級系統的可調度性上界為UHIHI≤1。故針對ULOALLgt;1情況，本文認為系統仍可進行調度。
在混合關鍵級系統中，當系統處于低關鍵級狀態時，所有任務的調度都是選用低關鍵級下的WCET值進行參考，較低的WCET值反映出單個任務對系統資源的需求相對較弱。然而在單個任務對資源需求較弱時，仍出現ULOALLgt;1，則可認為是系統資源短缺的一種體現。結合以上理解，本文可以認為：ULOALLgt;1且UHIHIlt;1所反映的是一種“系統資源對所有任務而言短缺，但是對高關鍵任務而言是充足”的狀態。
故針對ULOALLgt;1且UHIHIlt;1情況，采用EDF-HOL算法進行處理：在調度時拋棄所有低關鍵級別任務來為高關鍵級任務預留資源。同時為了避免由于高關鍵級任務執行超時帶來的系統關鍵級變化，在EDF-HOL算法中直接選用高關鍵級任務在高關鍵級下的WCET值進行調度。在系統資源緊缺的情況下保全系統正確性。由于在具體調度過程中，EDF-HOL算法的調度規則與EDF算法完全一致，故在此處不再進行其偽代碼贅述。
3.4.3 EDF-WCR算法
EDF-WCR主要適用于系統資源利用率為UHIALL≤1的情況。其主要思想為：當UHIALL≤1時，即認為系統資源對所有任務而言是充分的，所以為了減小由于混合關鍵級任務參數變化帶來的算法復雜性，在此算法中選用所有任務在高關鍵級下的WCET值進行EDF調度，簡化算法流程，提升算法執行速度。由于該算法思想較為簡單，且可直接基于EDF算法進行實現，故不在此進行贅述。
4 實驗與分析
本文將通過仿真的形式對所提算法的性能進行評估。考慮到實際生產中任務所具有的隨機性以及任務模型參數間的相互制約性，本文將基于傳統實時任務調度分析中用于生成隨機任務的uunifast程序，結合文獻［13］中對混合關鍵級任務模型參數制約關系的抽象，使用C語言作為基本編程語言完成對隨機生成混合關鍵級任務程序task launch的設計，以此在保證task launch生成任務數據隨機性的同時，也保證了其生成數據的合理性。在task launch任務生成程序的基礎上，同樣使用C語言實現在調度算法設計過程中必要的數據結構，例如任務棧、等待隊列等，以此完成本文算法和對比算法的具體實現。
在隨機任務生成程序和調度算法實現的基礎上，從算法的對任務集的可調度率與對低關鍵級任務的調度率這兩個維度出發，通過與混合關鍵級任務調度中經典算法的比較，對本文算法進行性能評估。同時為了避免數據的偶然性，在實驗過程中將采用多次實驗減小誤差的方法，具體為：每次實驗前使用task launch程序生成1 000個具有10～20個任務的任務集進行調度，操作重復多次，記錄調度的結果，取多次調度的平均值作為最終結果并使用Excel完成數據的處理與結果的可視化［14］。
下文將對隨機任務生成程序task launch和相關實驗的具體設計實現展開敘述，同時由于在第3章中已對相關調度算法進行過詳細說明并給出偽代碼，故在本章將不再贅述對相關調度算法的設計實現。
4.1 task launch的設計
task launch的主要設計思想如下：在程序運行前，由用戶手動輸入需要task launch生成的任務集數量以及每個任務集中所包含的任務數。在確定任務集數量與每個任務集包含的參數后，程序首先從一個空的任務集開始執行，并依次向此空集中加入隨機生成的混合關鍵級任務。在生成任務過程中，任務的參數主要受到五個條件的限制：隨機出現高關鍵級任務的最大概率PHI，高關鍵級任務中高關鍵級下WCET值與低關鍵級下WCET值的最大比值RHI、任務低關鍵級下WCET值的最大值CmaxLO、期望任務集利用率Uexpection以及生成任務的最大周期Tmax［15］。同時，本文對雙關鍵級系統中任務集ψ的平均利用率作出如下定義：
由于任務集在生成過程中，生成與本文期望利用率Uexpection完全相符的隨機任務集比較困難，故本文允許生成的任務集與Uexpection之間存在一個可接受的誤差范圍：
若生成任務集的平均利用率屬于［Umin，Umax］，即可認為本文生成的任務集是有效的。同時需注意：由于本文中所有的任務均采用隱式截止期模型，故Di=Ti。
隨機任務生成函數task launch代碼描述如下。
算法3 隨機任務生成算法task launch
輸入：生成任務集數n；每個任務集中包含的任務數目m。
輸出：n個具有m任務數目的任務集。
for i=n to 0 do
for j=m to 0 do
根據PHI所設置的概率，隨機生成高/低關鍵級任務
if 生成高關鍵級任務then
根據設置的CmaxLO隨機生成其低關鍵級下的WCET值
根據設置的RHI隨機生成高關鍵級任務中兩個WCET值的比值Rate
高關鍵任務的高關鍵WCET值=高關鍵任務的低關鍵下WCET值*Rate
根據設置的Tmax隨機生成其任務周期Ti
while（Ti≥高關鍵級任務高關鍵級WCET值）do
根據設置的Tmax隨機生成其任務周期Ti
end while
end if
if 生成低關鍵級任務 then
根據設置的CmaxLO隨機生成其低關鍵級下的WCET值
低關鍵級任務高關鍵級WCET值=低關鍵級任務的低關鍵級下WCET值
根據設置的Tmax隨機生成其任務周期Ti
while（Ti≥低關鍵級任務高關鍵級WCET值） do
根據設置的Tmax隨機生成其任務周期Ti
end while
end if
根據Uavg（τ）=ULO（τ）+UHI（τ）2，計算該任務平均利用率
if （sum+Uavg（τ））∈期望任務集利用率區間 then
sum=sum+Uavg（τ）
continue；
else
重新生成該任務
end if
end for
end for
在本文中，將上述限制條件定值如下： PHI=0.6、RHI=3、CmaxLO=10、Tmax=100。
4.2 可調度性的實驗設計與分析
基于上述task launch生成的合法任務集，本文開始對不同算法在不同任務集利用率下的可調度性進行研究。研究的算法對象為混合關鍵級任務調度中經典的EDF-VD算法、本文SDU算法以及SDU算法涉及的WCR算法。在進行算法可調度性研究前，先對這三種算法的可調度性原則進行總結，如表3所示。
在實驗過程中采用多次實驗法來避免可調度性實驗過程中由于任務集偶然性導致的實驗誤差，同時為了解決人工計算產生的誤差與耗時量過大的問題，在此將編寫judge程序以使其可以進行自動化處理。
算法4 任務集可調度性判斷程序judge
輸入：由task launch生成的n個m個任務數量的任務集。
輸出：總任務集合個數與各個算法調度失敗的任務集個數。
for i=n to 0 do
讀取單個任務集合
計算任務各個利用率
if UHIHIgt;1 then
SDU++
end if
if xULOLO（ψ）+UHIHI（ψ）gt;1 then
EDF_VD++
end if
if UHIALLgt;1 then
WCR++
end if
end for
打印總任務集個數與各個算法調度失敗的任務集個數
基于隨機任務生成程序task launch與可調度性判斷程序judge，本文開始進行可調度性分析實驗。基于事先設定的任務集利用率，利用task launch程序隨機生成1 000個符合要求的任務集，使用judge程序對生成的1 000個任務集進行判斷，并依次進行數據記錄。為了避免任務生成過程中的偶然性，在每個任務集利用率下重復三次實驗，記錄其實驗數據并進行成功調度個數的平均值計算，最終求得每個算法的任務調度成功率。同時在實驗過程中發現，當任務集利用率小于等于0.5時，所有算法對生成的任務集都是可以調度的。故在此選取任務集利用率在0.5以后的數據進行展示。處理后的實驗數據如圖1所示。
圖1表示在單核處理器上，任務集利用率發生變化時，各個算法的可調度情況。從圖1觀察到，當任務集的利用率小于0.55時，三種算法的可調度性均接近1。而隨著任務集利用率的增大，三種算法的可調度性開始遞減并出現差距。很顯然SDU相較于EDF-VD在任務集利用率較大的情況下（任務集利用率大于0.55時）具有明顯的優勢；在任務集利用率為1時，SDU的可調度率幾乎是EDF-VD的兩倍。同時由于WCR的設計思想是為所有任務保留其最大執行時間，而在混合關鍵級系統中，高關鍵級任務在高關鍵級下的最壞執行時間較長，故相比于EDF-VD與SDU，WCR可調度率相對較低。結合實驗數據可以得出，在任務集利用率較高時，SDU相較于EDF-VD，對隨機任務集的調度率平均可提升30%，當任務集利用率為1時，SDU相較于EDF-VD，對隨機任務集的調度率可提升100%，在任務集可調度率上提升明顯。
4.3 低關鍵級任務可執行率的實驗設計與分析
基于上述實驗，考慮到WCR的可調度率與另外兩個算法相差較大，故在此僅對SDU與EDF-VD進行低關鍵級任務的可調度率分析。具體流程如下：使用task launch進行隨機任務的生成，三種算法根據其自身調度性原則從隨機生成的任務集集合中選取符合自身調度性原則的任務集進行調度，同時進行低關鍵級任務所釋放作業完成個數與總個數的記錄。需要特別說明的是，由于SDU中的EDF-HOL適用情況為
本文所定義的任務集平均利用率為
若在實驗過程中，將任務集的平均利用率限制為1，則將無法滿足EDF-HOL的運行條件。故在此將任務集平均利用率擴展到1.25進行數據記錄，以全面觀察SDU的運行情況，比較結果如圖2所示。
由于本文提出的SDU本質上可以認為是三種算法的集合。故為了有效說明在任務集利用率變化時，低關鍵級任務執行率變化的原因，在此對不同任務集利用率下，SDU算法的內部使用情況進行統計分析。其結果如圖3所示。
觀察圖3中SDU子算法的執行可以發現：當任務集利用率小于0.75時，SDU認為系統資源是較為充足的，故在此階段利用EDF-WCR進行任務調度；當任務集利用率超過0.75時，此時SDU認為系統資源較為緊缺，故開始使用EDF-SLOT以保全高關鍵級任務執行為目的進行調度，并在保證高關鍵級任務執行的同時，適當地執行不影響高關鍵級任務的低關鍵級任務；當任務集利用率超過1.05后，SDU則認為系統資源極度緊缺，此時執行EDF-HOL，放棄所有低關鍵級任務的執行，以保證高關鍵級任務的完成。結合上述分析，可以很好地解釋圖2中SDU與EDF-VD在不同任務集利用率下低關鍵級任務執行率的變化情況：當任務集利用率小于0.7時，由于SDU在該情況下使用EDF-WCR，故相較于EDF-VD，SDU可以保證所有任務的成功執行。隨著任務集利用率的增大，導致任務集對系統資源的需求增大，故SDU中使用EDF-SLOT的頻率逐漸增高，使用EDF-WCR的頻率逐漸降低，導致SDU對低關鍵級任務的執行整體處于一個下降的趨勢，但相較于同時期的EDF-VD，仍維持在一個較高的水平。當任務集利用率超過1后，在SDU中，不對低關鍵級任務進行調度的EDF-HOL的使用頻率呈上升趨勢，同時EDF-SLOT的使用頻率逐步下降，故SDU對低關鍵級任務的調度率下降加速，但仍存在使用EDF-SLOT的可能性，故SDU對低關鍵級任務的可調度率雖低，但仍未等于0，依然優于同等條件下EDF-VD的低關鍵級任務可調度率。
結合上述實驗數據與分析，本文可以得出以下結論：SDU相較于EDF-VD，在對低關鍵級任務調度的優化上進步明顯；相較于EDF-VD，SDU對低關鍵級任務的執行率可提升165%，且從圖2可以看出，SDU在EDF-VD無法進行調度的情況下仍能保持一定量的低關鍵級任務執行。
5 結束語
在針對雙關鍵級系統的任務調度研究中，EDF-VD憑借其明確的可調度性條件以及被證明為最優的加速因子，被認為是最經典的算法之一。但在實際應用中，由于EDF-VD的可調度性條件較為嚴格，常常導致在調度過程中處理器資源被不可避免地浪費，但低關鍵級任務又無法得到充分計算資源的情況發生。基于EDF-VD存在的問題，本文提出了基于利用率劃分范圍進行調度的SDU，在利用率劃分區間的基礎上，對SDU中各個子算法的設計邏輯與使用情況進行了詳細的說明與分析。通過將任務集平均利用率作為因變量，從可調度率與低關鍵級任務執行率這兩個維度出發，將SDU與EDF-VD進行比較。經實驗證明，SDU相較于EDF-VD，不論在任務集可調度率上還是低關鍵級任務執行率上都提升明顯，在任務集可調度率上的提升為30%，在低關鍵級任務執行率上的提升率為165%。
從實際應用角度對SDU的優化效果進行分析：在汽車等基于集成化系統進行設計的設備中，SDU對任務集可調度率與對低關鍵級任務調度率的優化，可以在保證轉向、剎車等與使用者生命安全相關功能完成的基礎上，通過對導航、影音等任務的執行，優化乘客的體驗，保證設備整體服務的完整性。同時在當今主流的消費電子系統中，若將音樂、視頻等流媒體任務設置為高關鍵級任務，根據混合關鍵級調度算法的正確性判據，在截止期前該高關鍵級任務一定可以完成，從而可以保證使用者在聽歌或看視頻過程中的流暢性，而SDU對低關鍵級任務調度率的優化可以保證在觀看視頻時，內存回寫、網絡連接等相對不重要的后臺服務也可以被盡可能地完成，并通過這些服務的執行來優化前臺任務的運行，最終實現對消費者使用體驗的優化。
綜上可得，本文SDU以及其所具有的優化效果，不論從理論還是實際角度考慮，都具有一定的意義。
參考文獻：
［1］張鳳登.分布式實時系統［M］.北京：科學出版社，2014.（Zhang Fengdeng.Distributed real-time systems［M］.Beijing：China Science Publishing amp; Media Ltd.，2014.）
［2］何浚萍.基于虛擬計算機的混合關鍵性系統調度算法研究［D］.成都：電子科技大學，2020.（He Junping.Research on scheduling algorithm of mixed critical system based on virtual computer［D］.Chengdu：University of Electronic Science and Technology of China，2020.）
［3］Simó J，Balbastre P，Blanes J F，et al.The role of mixed criticality technology in industry 4.0［J］.Electronics，2021，10（3）：226.
［4］Behera L，Bhaduri P.An energy-efficient time-triggered scheduling algorithm for mixed-criticality systems［J］.Design Automation for Embedded Systems，2020，24（2）：79-109.
［5］Chen Gang，Nan Guan，Hu Biao，et al.EDF-VD scheduling of flexible mixed-criticality system with multiple-shot transitions［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2018，37（11）：2393-2403.
［6］Gao Nan，Shi Weiqi，Peng Xin，et al.Effective real-time scheduling optimization for multi-functional mixed-criticality systems［J］.Journal of Circuits，Systems and Computers，2020，29（14）：2050226.
［7］Varghese N V，Azim A，Mahmoud Q H.A feature-based machine learning approach for mixed-criticality systems［C］//Proc of the 22nd IEEE International Conference on Industrial Technology.Piscataway，NJ：IEEE Press，2021：699-704.
［8］Mahdiani M，Masrur A.A novel view on bounding execution demand under mixed-criticality EDF［J］.Real-Time Systems，2021，57（1）：55-94.
［9］Dong Xinyang，Chen Gang，Lyu Mingsong，et al.Flexible mixed-criticality scheduling with dynamic slack management［J］.Journal of Circuits，Systems and Computers，2021，30（10）：2150306.
［10］陳剛，徐廣益，楊俊杰，等.混合關鍵級系統中的一種空閑資源調度方法：中國，CN112799808A［P］.2021-05-14.（Chen Gang，Xu Guangyi，Yang Junjie，et al.An idle resource scheduling method in hybrid critical-level system：China，CN112799808A［P］.2021-05-14.）
［11］曾理寧.嵌入式系統混合關鍵級調度優化算法研究［D］.長沙：湖南大學，2019.（Zeng Lining.Research on optimized algorithm of mixed-criticality scheduling in embedded system［D］.Changsha：Hunan University，2019.）
［12］Jiang Zhe，Dai Xiaotian，Dong Pan，et al.Towards an analysable，scalable，energy-efficient I/O virtualization for mixed-criticality systems［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2022，41（2）：320-333.
［13］谷傳才，關楠，于金銘，等.多處理器混合關鍵性系統中的劃分調度策略［J］.軟件學報，2014，25（2）：284-297.（Gu Chuancai，Guan Nan，Yu Jinming，et al.Partition scheduling strategy in multiprocessor mixed-criticality systems［J］.Journal of Software，2014，25（2）：284-297.）
［14］Zhang Yiwen，Cai Ning.Energy efficient EDF-VD-based mixed-criticality scheduling with shared resources［J］.Journal of Systems Architecture，2021，119（C）：11.
［15］Bhuiyan A A，Yang Kecheng，Arefin S，et al.Mixed-criticality multicore scheduling of real-time gang task systems［C］//Proc of IEEE Real-Time Systems Symposium.Piscataway，NJ：IEEE Press，2019：469-480.
