陳洪琪 涂珍 王志軍

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

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

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

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

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

二、MCS趨勢分析

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

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

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

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

三、MCS研究意義及目標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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