淺析周期性任務系統(tǒng)調(diào)度的MCS任務模型

陳洪琪 涂珍 王志軍

摘要：隨著技術的發(fā)展，嵌入式實時系統(tǒng)處理能力飛速提升，如汽車和飛機的電子系統(tǒng)集合了數(shù)百個處理器。受嵌入式系統(tǒng)體積和能耗等方面制約，許多原來不同子系統(tǒng)（組件）中的關鍵性應用被共享到單個處理器（硬件）平臺中，這就導致混合關鍵系統(tǒng)（簡稱MCS）的出現(xiàn)。

關鍵字：MCS；系統(tǒng)模型

一、MCS現(xiàn)狀分析

如今，已有的調(diào)度策略能一定程度上提升系統(tǒng)的可調(diào)度性，但依然存在許多問題：其一，很多策略是基于單核平臺，不能直接應用于多處理器之間的任務處理；其二，任務模型大多基于周期性任務或偶發(fā)性任務，忽略了兼容周期性與偶發(fā)性兩種形態(tài)的存在；其三，主要目標為關鍵性任務的成功率，忽略了其他系統(tǒng)指標和有效利用率。

周期性任務系統(tǒng)調(diào)度方法研究的MCS系統(tǒng)模型提出了基于多核平臺的任務調(diào)度策略，使系統(tǒng)不僅獲得較高的成功率，還具備較強的綜合性能，能有效利用已有的硬件環(huán)境。

二、MCS趨勢分析

MCS具有不同關鍵性等級的任務，下面對其系統(tǒng)模型和代表性調(diào)度策略進行分析。

Vestal等首先利用形式化提出了MCS系統(tǒng)任務模型，系統(tǒng)由k個組件的有限集合來表示，每個組件擁有一個關鍵性級別記為L。任務τi是一個四元組組成：τi=（Ti，Di，Ci，Li），其中：Ti、Di、Ci和Li分別為任務τi的周期、截止期、估算執(zhí)行時間和關鍵性級別。

由于許多任務參數(shù)與關鍵性級別沒有太多聯(lián)系，如最壞估算執(zhí)行時間（WCET，Ci）。隨著關鍵性級別越高，Ci的數(shù)值越大，但其準確數(shù)值難以估算，估算WCET需要花費大量的系統(tǒng)資源，會導致MCS系統(tǒng)中的資源浪費。

Baruah等從任務執(zhí)行時間和周期與關鍵性級別關系的角度改進了MCS任務模型，任務τi是一個四元組組成：τi=（Di，Li），其中分別為表示執(zhí)行時間和周期的向量，對于任意兩個關鍵性級別L1、L2，關鍵性級別高的任務，具有更高的估算執(zhí)行時間、周期以及更大數(shù)值的截止期。

三、MCS研究意義及目標

由于多核平臺的普及，原有的基于單核環(huán)境的MCS系統(tǒng)資源共享策略不再適用。為此，需要研究適用于多核環(huán)境以及兼容周期性任務和偶發(fā)性任務的資源共享策略，在保證高關鍵性和高優(yōu)先級任務獲得資源的前提下，提高系統(tǒng)資源利用率。具體如下：

首先，防止出現(xiàn)高關鍵性倒置問題。MCS系統(tǒng)與一般實時應用環(huán)境的區(qū)別在于：系統(tǒng)中混合著不同關鍵性級別的任務，如果低關鍵性任務阻塞了高關鍵性任務的資源請求，那么可能會影響整個系統(tǒng)的安全性。

其次，防止出現(xiàn)優(yōu)先級倒置問題。傳統(tǒng)實時環(huán)境下防止出現(xiàn)優(yōu)先級倒置可采用優(yōu)先級繼承、優(yōu)先級思想等方法。同時，為了執(zhí)行的邏輯正確性及數(shù)據(jù)的一致性，可引入基于封鎖的思想。

最后，注意多核平臺下的資源利用和負載均衡。單核實時系統(tǒng)下的資源共享策略的高利用率一般是以保證高優(yōu)先級（及高關鍵性）任務執(zhí)行為前提，如果出現(xiàn)更緊急的任務則在前者的空閑時間內(nèi)執(zhí)行，MCS系統(tǒng)也是此思想。另外，多核平臺下系統(tǒng)在資源分配時，必須盡量使各個處理器上執(zhí)行的任務都能獲得資源，利用排隊論M/M/1模型來分配任務集到處理器上，并允許任務能夠在不同處理器上進行遷移，從而充分均衡地利用平臺資源。

多核平臺下MCS系統(tǒng)任務處理機制需解決的關鍵問題包括：一種周期性任務系統(tǒng)調(diào)度多核平臺任務模型、針對周期性任務模型構造任務的優(yōu)先級分配函數(shù)、基于優(yōu)先級繼承的資源共享等。

由于MCS的并發(fā)控制和任務調(diào)度都是基于優(yōu)先級驅動的，因此優(yōu)先級分派極為重要。已有的MCS較少考慮除截止期之外的因素。本項目的優(yōu)先級分配問題具體考慮如下：

首先，任務關鍵性與優(yōu)先級的關系。為了保證高關鍵性任務的優(yōu)先執(zhí)行，在同等時間性特點下，高關鍵性任務應被賦予更高的優(yōu)先級。

其次，任務價值密度。為了量化任務完成給系統(tǒng)帶來的收益，優(yōu)先級分派應考慮任務的價值密度因素（即單位時間所具有的價值）。根據(jù)已有的實時調(diào)度策略，價值密度可根據(jù)數(shù)值特性分為靜態(tài)價值密度和動態(tài)價值密度兩種形式。

最后，綜合構造優(yōu)先級函數(shù)。為了體現(xiàn)系統(tǒng)綜合性能，在優(yōu)先級分派時應結合執(zhí)行時間、空閑時間和關鍵性級別等因素，動態(tài)多維度地構造分派函數(shù)，優(yōu)化函數(shù)模型。

四、MCS研究內(nèi)容

根據(jù)已有的MCS調(diào)度策略研究結果，對多核環(huán)境下的MCS采用劃分調(diào)度思想，對分配到具體處理器上的任務采用基于搶占閾值的調(diào)度方法。主要研究內(nèi)容如下：

第一，實時任務的排序。在將任務分配到具體處理器之前，需要對任務集進行排序，盡量將特征相近的任務分配到同一個處理器上?？紤]關鍵性級別的因素，MCS在任務排序和處理器選擇時可以按關鍵性排序。

第二，處理器的選擇。針對排序之后的任務子集，可以利用啟發(fā)式策略將其分配到處理器，以達到更好的可劃分性能。

第三，單處理機上實時調(diào)度策略。由于任務子集是在單處理器上執(zhí)行的，因此可以采用基于單處理器的調(diào)度策略，即基于優(yōu)先級驅動的策略。

參考文獻

[1]黃經(jīng)州.開放式混合實時系統(tǒng)調(diào)度策略研究[D]. 浙江師范大學，2009.

[2]谷傳才，關楠，于金銘，等.多處理器混合關鍵性系統(tǒng)中的劃分調(diào)度策略[J]. 軟件學報，2014（2）：284-297

[3]佟欣. 嵌入式實時系統(tǒng)的混合調(diào)度算法研究[D]. 沈陽工業(yè)大學，2010.