機(jī)載多分區(qū)系統(tǒng)可調(diào)度性分析算法研究

張旻, 武君勝, 崔西寧, 孫景昌

1.西北工業(yè)大學(xué)軟件學(xué)院， 陜西 西安 710072；2.中國(guó)航空工業(yè)集團(tuán)有限公司西安航空計(jì)算技術(shù)研究所， 陜西 西安 710065

實(shí)時(shí)系統(tǒng)主要分為2類:①軟實(shí)時(shí)系統(tǒng);②硬實(shí)時(shí)系統(tǒng)。軟實(shí)時(shí)系統(tǒng)是指少數(shù)事件/進(jìn)程的截止期允許被違反,尤其是當(dāng)系統(tǒng)負(fù)載較高時(shí),允許發(fā)生少數(shù)事件處理錯(cuò)過(guò)截止期。硬實(shí)時(shí)系統(tǒng)則不允許任何進(jìn)程的周期和截止期被違反,系統(tǒng)必須及時(shí)地對(duì)事件做出響應(yīng),不允許發(fā)生錯(cuò)過(guò)事件處理時(shí)機(jī)或超出截止期的情況。例如,飛機(jī)飛行控制、導(dǎo)彈/火箭發(fā)射、飛船太空飛行等系統(tǒng),如果沒(méi)有對(duì)突發(fā)故障做出及時(shí)處理,將造成巨大的損失或?yàn)?zāi)難。

硬實(shí)時(shí)系統(tǒng)不僅在傳統(tǒng)的航空、航天領(lǐng)域,而且在民用飛機(jī)、智能汽車等領(lǐng)域也逐步得到廣泛應(yīng)用[1]。例如在機(jī)載嵌入式安全關(guān)鍵系統(tǒng)中,其可用性和可靠性不僅僅取決于軟件功能的正確性,在某些應(yīng)用場(chǎng)景(如飛行控制)下更加依賴于軟件運(yùn)行的實(shí)時(shí)性。機(jī)載嵌入式硬實(shí)時(shí)系統(tǒng)一個(gè)重要特征就是必須在給定的時(shí)限和周期內(nèi),對(duì)規(guī)定事件進(jìn)行及時(shí)響應(yīng)和處理。

美國(guó)航空電子工程委員會(huì)制定的航空應(yīng)用軟件接口標(biāo)準(zhǔn)ARINC653(avionics application software standard interface)[2-4],定義了綜合化航空電子系統(tǒng)(IMA)架構(gòu)下分區(qū)實(shí)時(shí)操作系統(tǒng)的行為邏輯、調(diào)度機(jī)制和應(yīng)用軟件接口規(guī)范。分區(qū)是ARINC653規(guī)范的核心概念,它實(shí)現(xiàn)了應(yīng)用程序的時(shí)空隔離。在機(jī)載軟件領(lǐng)域應(yīng)用程序是一組計(jì)算任務(wù)的集合,部署和運(yùn)行在一組資源分區(qū)之上。這些計(jì)算任務(wù)在分區(qū)內(nèi)進(jìn)行本地調(diào)度,與其他分區(qū)內(nèi)的任務(wù)調(diào)度相互獨(dú)立;同時(shí),若干個(gè)分區(qū)之間進(jìn)行分區(qū)間調(diào)度以共享處理器的計(jì)算時(shí)間資源。針對(duì)ARINC653的任務(wù)調(diào)度方法,已有大量深入的研究[5-7]。

分區(qū)操作系統(tǒng)是面向機(jī)載綜合化航空電子系統(tǒng)、滿足ARINC653標(biāo)準(zhǔn),且具備時(shí)空隔離能力的嵌入式實(shí)時(shí)操作系統(tǒng)[8]。為了防止個(gè)別分區(qū)出現(xiàn)故障影響到其他分區(qū)的運(yùn)行,分配給一個(gè)分區(qū)的執(zhí)行時(shí)間不會(huì)由于其他分區(qū)的超時(shí)運(yùn)行而有所改變。另外,分區(qū)實(shí)時(shí)操作系統(tǒng)采用兩級(jí)層次調(diào)度模型[9],分別對(duì)分區(qū)間和分區(qū)內(nèi)進(jìn)程進(jìn)行調(diào)度。第一級(jí)是分區(qū)間調(diào)度,將分區(qū)作為調(diào)度的單位,各個(gè)分區(qū)按照固定的時(shí)間片分配計(jì)算資源;第二級(jí)是分區(qū)內(nèi)進(jìn)程調(diào)度,各個(gè)進(jìn)程按照固定優(yōu)先級(jí)進(jìn)行搶占式調(diào)度。分區(qū)按固定時(shí)間序列,即用戶配置的調(diào)度表進(jìn)行調(diào)度。為避免在試飛階段才發(fā)現(xiàn)分區(qū)或進(jìn)程不可調(diào)度的情況,進(jìn)而造成系統(tǒng)失效、事故以及經(jīng)濟(jì)損失,在系統(tǒng)開(kāi)發(fā)和集成階段事先針對(duì)調(diào)度表進(jìn)行可調(diào)度性分析就顯得至關(guān)重要。

很多學(xué)者針對(duì)可調(diào)度性分析進(jìn)行了研究,采用的方法包括時(shí)間依賴結(jié)構(gòu)模型[10]、時(shí)間約束著色Petri網(wǎng)[11]、多項(xiàng)式時(shí)間線性松弛[12]、基于主副版本混合關(guān)鍵任務(wù)優(yōu)先級(jí)劃分[13]、基于優(yōu)先級(jí)控制的系統(tǒng)分解[14]、函數(shù)圖像分析[15]、DAG(directed acyclic graph)模型[16-17]、PFP(artitioned fifixed-priority)調(diào)度策略[18]、基于掛起的協(xié)議LPP[19]等技術(shù)和方法對(duì)可調(diào)度性分析進(jìn)行了研究和探索。上述研究工作針對(duì)實(shí)時(shí)系統(tǒng)、并發(fā)系統(tǒng)、任務(wù)關(guān)鍵系統(tǒng)、混合關(guān)鍵系統(tǒng)等對(duì)時(shí)間約束具備較高要求的任務(wù)系統(tǒng)從理論角度進(jìn)行了可調(diào)度性分析,相關(guān)研究理論嚴(yán)謹(jǐn),學(xué)術(shù)價(jià)值高。區(qū)別于上述研究,機(jī)載領(lǐng)域應(yīng)用場(chǎng)景不僅具備實(shí)時(shí)特征,同時(shí)具備多分區(qū)時(shí)空隔離特征,并且采用多級(jí)調(diào)度機(jī)制,此類領(lǐng)域特征使得上述研究很難直接應(yīng)用于指導(dǎo)機(jī)載分區(qū)系統(tǒng)在綜合化條件下的可調(diào)度性分析。因此,有必要結(jié)合機(jī)載分區(qū)、實(shí)時(shí)、多級(jí)調(diào)度等特征,研究具備領(lǐng)域特點(diǎn)的可調(diào)度性分析算法。

為解決現(xiàn)有可調(diào)度性分析算法未考慮機(jī)載分區(qū)特征的問(wèn)題,本文針對(duì)機(jī)載分區(qū)系統(tǒng)高安全、強(qiáng)實(shí)時(shí)、高可靠等特點(diǎn),提出一種基于虛擬進(jìn)程的多分區(qū)多進(jìn)程的調(diào)度可行性判定算法。該算法根據(jù)給定調(diào)度表和分區(qū)進(jìn)程時(shí)間約束條件,判定所有進(jìn)程的可調(diào)度性。與現(xiàn)有判別技術(shù)不同,針對(duì)機(jī)載分區(qū)系統(tǒng)多級(jí)調(diào)度分析難的問(wèn)題,本文提出了基于虛擬進(jìn)程的可調(diào)度性方法,該方法在判斷某一分區(qū)中進(jìn)程的截止期是否能被滿足時(shí),將其他分區(qū)對(duì)應(yīng)的時(shí)間窗口作為一個(gè)虛擬進(jìn)程來(lái)看待,將復(fù)雜的多分區(qū)多進(jìn)程的調(diào)度可行性判斷問(wèn)題,轉(zhuǎn)化為一組單分區(qū)多進(jìn)程的調(diào)度可行性判斷問(wèn)題,從而降低了多分區(qū)多進(jìn)程可行性判斷的難度及算法在工程實(shí)踐中應(yīng)用的難度。最后通過(guò)正反例調(diào)度實(shí)例驗(yàn)證了本文提出可調(diào)度性分析算法的正確性。

1 多分區(qū)系統(tǒng)調(diào)度模型

為簡(jiǎn)潔、準(zhǔn)確地表述算法設(shè)計(jì)過(guò)程,本節(jié)針對(duì)問(wèn)題模型進(jìn)行一些參數(shù)符號(hào)的定義,并基于相關(guān)定義描述多分區(qū)系統(tǒng)的調(diào)度規(guī)則。

1.1 分區(qū)調(diào)度參數(shù)

假設(shè)操作系統(tǒng)配置K個(gè)分區(qū),分區(qū)Pk(1≤k≤K)由nk個(gè)進(jìn)程組成,進(jìn)程優(yōu)先級(jí)由高到低排列。

本文所使用的主要符號(hào)見(jiàn)表1。

表1 分區(qū)調(diào)度參數(shù)

周期進(jìn)程必須滿足Ck,i≤Dk,i≤Tk,i;非周期進(jìn)程無(wú)周期參數(shù);對(duì)某些進(jìn)程,不存在截止期限制,此時(shí)截止期值為空。

1.2 分區(qū)調(diào)度規(guī)則

分區(qū)調(diào)度表的核心屬性為時(shí)間窗口,關(guān)鍵參數(shù)包括時(shí)間窗口所對(duì)應(yīng)的分區(qū)和持續(xù)時(shí)間。依據(jù)ARINC653標(biāo)準(zhǔn),分區(qū)調(diào)度表應(yīng)滿足以下約束條件:

1) 調(diào)度表由一組時(shí)間窗口的集合組成,可在一個(gè)調(diào)度表中多次調(diào)用一個(gè)分區(qū),但不必在一個(gè)調(diào)度表中調(diào)度所有分區(qū);

2) 一個(gè)調(diào)度表里可以有多個(gè)時(shí)間窗口,可以有空閑時(shí)間窗口;

3) 同一時(shí)刻處理器僅能運(yùn)行一個(gè)時(shí)間窗口;

4) 每個(gè)分區(qū)內(nèi)的進(jìn)程及進(jìn)程的時(shí)間屬性都是靜態(tài)配置的,一個(gè)進(jìn)程只能屬于一個(gè)分區(qū);

5) 主時(shí)間框架是調(diào)度表的循環(huán)周期;

6) 某一分區(qū)的分區(qū)循環(huán)時(shí)長(zhǎng)等于該分區(qū)內(nèi)所有周期進(jìn)程的周期與主時(shí)間框架的最小公倍數(shù)。

本文以時(shí)間窗口作為主時(shí)間框架內(nèi)調(diào)度主體,一個(gè)調(diào)度表即為一組時(shí)間窗口的排列。假設(shè)主時(shí)間框架內(nèi)有M個(gè)時(shí)間窗口(M≥K),記Ti=(Zi,Si,Yi,Fi),i=1,2,…,M,其中:

1)Zi表示時(shí)間窗口的周期;

2)Si表示時(shí)間窗口的開(kāi)始運(yùn)行時(shí)間;

3)Yi表示時(shí)間窗口的運(yùn)行時(shí)長(zhǎng);

4)Fi表示時(shí)間窗口對(duì)應(yīng)的分區(qū)。

分區(qū)調(diào)度規(guī)則示例如圖1所示。

處理器上運(yùn)行P1,P2,P33個(gè)分區(qū)。主時(shí)間框架包含T1,T2,…,T12共12個(gè)時(shí)間窗口。時(shí)間窗口屬性見(jiàn)表2。

表2 多分區(qū)調(diào)度表時(shí)間窗口屬性

對(duì)于單核處理器,時(shí)間窗口是串行排列的,其中可能包括空閑的時(shí)間窗口。每個(gè)時(shí)間窗口處理且僅處理一個(gè)分區(qū)的調(diào)度。調(diào)度表按照就緒時(shí)間依次運(yùn)行各個(gè)時(shí)間窗口。每個(gè)時(shí)間窗口內(nèi)對(duì)應(yīng)分區(qū)內(nèi)的所有進(jìn)程,按優(yōu)先級(jí)依次串行運(yùn)行。

1.3 進(jìn)程調(diào)度規(guī)則

進(jìn)程具有固定的優(yōu)先級(jí),高優(yōu)先級(jí)的進(jìn)程優(yōu)先獲得處理器資源。機(jī)載分區(qū)操作系統(tǒng)在管理分區(qū)內(nèi)進(jìn)程時(shí),按照優(yōu)先級(jí)維護(hù)一個(gè)就緒隊(duì)列,每次從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)程,將處理器分配給它。

在優(yōu)先級(jí)調(diào)度算法中,進(jìn)程分為可被搶占和不可被搶占2種類型?？蓳屨歼M(jìn)程在運(yùn)行過(guò)程中允許被更高優(yōu)先級(jí)進(jìn)程搶占處理器;不可搶占進(jìn)程則反之,不允許被更高優(yōu)先級(jí)進(jìn)程搶占處理器。

按照ARINC653標(biāo)準(zhǔn)的定義,進(jìn)程的優(yōu)先級(jí)是靜態(tài)配置的,即在創(chuàng)建進(jìn)程前事先確定,在進(jìn)程的整個(gè)運(yùn)行期間優(yōu)先級(jí)保持不變。

2 可調(diào)度性分析算法設(shè)計(jì)

在機(jī)載軟件工程實(shí)踐中,要求調(diào)度表中每個(gè)分區(qū)都必須可調(diào)度,每個(gè)進(jìn)程的時(shí)間約束都必須被滿足。因此,可調(diào)度性分析算法采取的總體策略是:先分別計(jì)算每個(gè)分區(qū)的可調(diào)度性,再得出調(diào)度表的整體可調(diào)度性分析結(jié)論。

首先,給出計(jì)算單個(gè)分區(qū)時(shí)將其他分區(qū)視為虛擬進(jìn)程的算法1,然后再分別針對(duì)非周期進(jìn)程和周期進(jìn)程設(shè)計(jì)可調(diào)度性分析算法2和3,最后,基于算法1～3設(shè)計(jì)總體可調(diào)度性分析算法。

2.1 確定分區(qū)循環(huán)時(shí)長(zhǎng)

調(diào)度表的可行性判定必須涵蓋所有分區(qū),而某一分區(qū)調(diào)度方案的可行性需判斷在分區(qū)循環(huán)時(shí)長(zhǎng)內(nèi),所有進(jìn)程的可調(diào)度性。因此,確定分區(qū)循環(huán)時(shí)長(zhǎng)是進(jìn)行可調(diào)度性分析的前提。由前述1.2節(jié)分區(qū)調(diào)度規(guī)則及圖1多分區(qū)的調(diào)度過(guò)程示意圖可知,為滿足多分區(qū)內(nèi)多進(jìn)程調(diào)度需求,某一分區(qū)的分區(qū)循環(huán)時(shí)長(zhǎng)等于該分區(qū)內(nèi)所有周期進(jìn)程的周期與主時(shí)間框架的最小公倍數(shù)。如果無(wú)法滿足這一要求,該分區(qū)的部分進(jìn)程可能無(wú)法在一個(gè)分區(qū)循環(huán)時(shí)長(zhǎng)內(nèi)執(zhí)行完畢。依據(jù)最小公倍數(shù)的結(jié)合律性質(zhì)[20],記a和b的最小公倍數(shù)為[a,b],則[a,b,c]=[[a,b],c],因此分區(qū)的循環(huán)時(shí)長(zhǎng)等于該分區(qū)內(nèi)所有周期進(jìn)程的周期與主時(shí)間框架的最小公倍數(shù)。

2.2 虛擬進(jìn)程生成算法

對(duì)于分區(qū)操作系統(tǒng),通常采用兩級(jí)層次調(diào)度模型,分別對(duì)分區(qū)和分區(qū)內(nèi)進(jìn)程進(jìn)行調(diào)度。第一級(jí)是對(duì)各個(gè)分區(qū)的調(diào)度,將分區(qū)作為調(diào)度的單位,各個(gè)分區(qū)按照固定的時(shí)間片分配計(jì)算資源;第二級(jí)是對(duì)各個(gè)分區(qū)內(nèi)的進(jìn)程進(jìn)行調(diào)度,各個(gè)進(jìn)程按照固定優(yōu)先級(jí)進(jìn)行搶占計(jì)算資源。多分區(qū)多進(jìn)程調(diào)度可行性分析是一個(gè)NP-Hard問(wèn)題,但從分區(qū)運(yùn)行行為考慮,當(dāng)某一分區(qū)占有處理器時(shí),其余分區(qū)處于停止?fàn)顟B(tài),因此可以從宏觀角度將處于停止?fàn)顟B(tài)的分區(qū)中的多個(gè)進(jìn)程視為一個(gè)虛擬進(jìn)程,反之亦然。因此,本文基于虛擬進(jìn)程,將多分區(qū)多進(jìn)程的調(diào)度可行性分析轉(zhuǎn)換為單分區(qū)多進(jìn)程調(diào)度可行性問(wèn)題。

以圖1為例說(shuō)明虛擬進(jìn)程的生成算法。

基于圖1的調(diào)度表和表2給出的調(diào)度表,將所有時(shí)間窗口視為虛擬進(jìn)程,描述見(jiàn)表3。

表3 時(shí)間窗口對(duì)應(yīng)的虛擬進(jìn)程

判斷各個(gè)分區(qū)內(nèi)所有進(jìn)程的可調(diào)度性。以第一個(gè)分區(qū)為例,假設(shè)分區(qū)P1包含3個(gè)進(jìn)程,見(jiàn)表4。

表4 分區(qū)P1所有進(jìn)程的屬性

為判斷分區(qū)P1所有進(jìn)程的可調(diào)度性,將除P1外其他分區(qū)對(duì)應(yīng)的時(shí)間窗口轉(zhuǎn)化成虛擬進(jìn)程,并為時(shí)間窗口對(duì)應(yīng)的虛擬進(jìn)程分配適當(dāng)?shù)膬?yōu)先級(jí)。由于時(shí)間窗口不可被打斷,同樣也不可被搶占,所以可將這些時(shí)間窗口所對(duì)應(yīng)的虛擬進(jìn)程的優(yōu)先級(jí)設(shè)置成比P1內(nèi)所有進(jìn)程的優(yōu)先級(jí)都要高,以保證虛擬進(jìn)程不會(huì)被真實(shí)進(jìn)程搶占,而虛擬進(jìn)程可以搶占真實(shí)進(jìn)程?？紤]最極端的情況,即虛擬進(jìn)程的WCET和截止期相等,以此保證虛擬進(jìn)程可以在規(guī)定的時(shí)間結(jié)束。另一方面,假設(shè)虛擬進(jìn)程的周期等于主時(shí)間框架的長(zhǎng)度,保證虛擬進(jìn)程在整個(gè)分區(qū)循環(huán)時(shí)長(zhǎng)里可以正常運(yùn)行。判斷分區(qū)P1的可調(diào)度性時(shí),所生成的除分區(qū)P1外所有時(shí)間窗口對(duì)應(yīng)的虛擬進(jìn)程見(jiàn)表5。

表5 除P1外所有時(shí)間窗口對(duì)應(yīng)的虛擬進(jìn)程

虛擬進(jìn)程生成算法構(gòu)建虛擬進(jìn)程并將其加入到當(dāng)前所需檢驗(yàn)分區(qū)Pi的進(jìn)程列表中,輸出需要檢驗(yàn)的分區(qū)Pi的最終進(jìn)程列表。為了防止其他分區(qū)所對(duì)應(yīng)的時(shí)間窗口影響運(yùn)行分區(qū)內(nèi)進(jìn)程,需要將時(shí)間窗口作為進(jìn)程考慮。將時(shí)間窗口Ti虛擬進(jìn)程化,令其屬性為:

1) 最惡劣情況下的執(zhí)行時(shí)間:Ck,i=Yi;

2) 截止期:Dk,i=Yi;

3) 優(yōu)先級(jí):高于運(yùn)行分區(qū)內(nèi)所有進(jìn)程;

4) 就緒時(shí)間:該虛擬進(jìn)程還差多長(zhǎng)時(shí)間可以就緒,在0時(shí)刻等于時(shí)間窗口的開(kāi)始時(shí)間Sk;

5) 周期:等于主時(shí)間框架。

算法1虛擬進(jìn)程生成算法

輸入:調(diào)度表(包括所有時(shí)間窗口的屬性);所有分區(qū)的進(jìn)程列表(包括所有進(jìn)程的屬性)

具體執(zhí)行步驟如下:

step1 初始化:j=1;

step2 對(duì)j=1,…,M,判斷Tj是否對(duì)應(yīng)于Pi

step3 若否,將虛擬進(jìn)程Tj加入Pi的進(jìn)程列表,Ck,i=Yi,Dk,i=Yi,優(yōu)先級(jí)為運(yùn)行的分區(qū)中所有進(jìn)程的最高優(yōu)先級(jí)+j,還差多長(zhǎng)時(shí)間可以就緒為Sj,周期為主時(shí)間框架長(zhǎng)度。若是,則跳過(guò)該時(shí)間窗口。輸出最終需要檢驗(yàn)的進(jìn)程列表。

該算法基本運(yùn)算在于判斷Tj是否對(duì)應(yīng)于Pi并進(jìn)行相應(yīng)賦值操作,因此其時(shí)間復(fù)雜度取決于參數(shù)j的值,為o(n)。

2.3 可調(diào)度性分析算法

對(duì)第k個(gè)分區(qū)進(jìn)行判斷,定義下述4個(gè)列表:

1) 剩余列表Sj:后續(xù)還需運(yùn)行的進(jìn)程列表;

2) 完成列表Wj:已經(jīng)完成至少一次運(yùn)行的進(jìn)程列表;

4) 未就緒列表WJj:還未準(zhǔn)備就緒的進(jìn)程列表(包含未就緒的進(jìn)程i以及進(jìn)程i還差dji可以就緒,進(jìn)程tk,i的優(yōu)先級(jí)Pk,i等信息)。

特別說(shuō)明:由于在后續(xù)的可調(diào)度性分析算法中,上述4個(gè)列表均需要不斷更新,所以上述列表中的所有下角標(biāo)j表示第j次更新。

算法運(yùn)行過(guò)程中所涉及的判據(jù)及更新規(guī)則如下:

進(jìn)程截止期滿足的定義分為2種情況:

在判據(jù)2和判據(jù)3中,進(jìn)程tk,m∈Jj描述了針對(duì)第j次更新的截止期可滿足,列表更新后,進(jìn)程tk,m有可能會(huì)被違反。因此,需要在每次列表更新后進(jìn)行判斷。

針對(duì)進(jìn)程的相關(guān)屬性以及上述相關(guān)列表的更新規(guī)則分3種情況進(jìn)行討論:

1)Jj為非空,Jj中優(yōu)先級(jí)最高的進(jìn)程tk,i能在不被更高優(yōu)先級(jí)進(jìn)程搶占情況下完成運(yùn)行:

2)Jj為非空,Jj中優(yōu)先級(jí)最高的進(jìn)程tk,i不能在不被更高優(yōu)先級(jí)進(jìn)程搶占情況下完成運(yùn)行:

如果某個(gè)分區(qū)內(nèi)的進(jìn)程都是非周期進(jìn)程,所加入的虛擬時(shí)間窗口進(jìn)程都為非周期性,則需運(yùn)行這里的算法2。為此,定義以下3個(gè)列表:

1) 完成列表Wj:已經(jīng)完成運(yùn)行的進(jìn)程列表;

2) 就緒列表Jj:已經(jīng)準(zhǔn)備就緒的進(jìn)程列表(包括已準(zhǔn)備就緒的進(jìn)程tk,i,進(jìn)程的優(yōu)先級(jí)Pk,i進(jìn)程最惡劣情況下執(zhí)行時(shí)間Ck,i,以及進(jìn)程的截止期Dk,i等信息);

3) 未就緒列表WJj:還未準(zhǔn)備就緒的進(jìn)程列表(包含未就緒的進(jìn)程i以及進(jìn)程i還差dji可以就緒,進(jìn)程tk,i優(yōu)先級(jí)Pk,i等信息)。

算法2非周期進(jìn)程的可調(diào)度性分析算法

具體執(zhí)行步驟如下:

step1 第k個(gè)分區(qū)的進(jìn)程運(yùn)行時(shí)間Tk=0,

j=0;

step2 若j≤nk

Pk,i>Pk,m,?tk,m≠tk,i且tk,i,tk,m∈Jj,則令

Tk=Tk+Ck,i;

j=j+1;

step2.1 截止期判斷

若?tk,m∈Jj,Dk,m

輸出由于進(jìn)程tk,m的截止期未被滿足(注:此處截止期未被滿足的進(jìn)程不唯一),該分區(qū)不可行,轉(zhuǎn)step3;

否則:

Wj=完成列表Wj-1中加入進(jìn)程tk,i;

Jj=就緒列表Jj-1中刪除進(jìn)程tk,i;

繼續(xù)執(zhí)行;

否則

輸出:該分區(qū)可調(diào)度,轉(zhuǎn)step3;

step3 終止

該算法基本運(yùn)算在于比較j與nk,并進(jìn)行賦值運(yùn)算,其時(shí)間復(fù)雜度取決于參數(shù)j與參數(shù)k的值,為o(n2)。

對(duì)某個(gè)分區(qū),如果分區(qū)內(nèi)存在一個(gè)周期進(jìn)程,或至少加入了一個(gè)周期的虛擬時(shí)間窗口,則需運(yùn)行算法3。在給定分區(qū)調(diào)度表以及相應(yīng)的分區(qū)循環(huán)時(shí)長(zhǎng)的情況下,判斷進(jìn)程在運(yùn)行的過(guò)程中,進(jìn)程的截止期屬性是否能夠得到滿足。為了方便后續(xù)算法的設(shè)計(jì),首先定義4個(gè)列表:

1) 剩余列表Sj:后續(xù)還需運(yùn)行的進(jìn)程列表;

2) 完成列表Wj:已經(jīng)完成至少一次運(yùn)行的進(jìn)程列表;

4) 未就緒列表WJj:還未準(zhǔn)備就緒的進(jìn)程列表(包含未就緒的進(jìn)程i以及進(jìn)程i還差dji可以就緒,進(jìn)程tk,i優(yōu)先級(jí)Pk,i等信息)。

算法3的循環(huán)次數(shù)應(yīng)為最壞情況下進(jìn)程的切換次數(shù),而分區(qū)循環(huán)時(shí)長(zhǎng)除以sysClkRateHz是其理論上的一個(gè)上界(sysClkRateHz由用戶給出,通常為100或1 000),可使用這個(gè)上界作為算法3中運(yùn)行步驟的上界Nk。

算法3周期進(jìn)程的可調(diào)度性分析算法

具體執(zhí)行步驟如下:

step1 第k個(gè)分區(qū)的進(jìn)程運(yùn)行時(shí)間Tk=0,運(yùn)行步驟的上界Nk,j=1

step2 若j≤Nk

判斷Jj中優(yōu)先級(jí)最高的進(jìn)程tk,i能否在不被更高優(yōu)先級(jí)進(jìn)程搶占情況下完成運(yùn)行;

step2.1 若Jj中優(yōu)先級(jí)最高的進(jìn)程tk,i能在不被更高優(yōu)先級(jí)進(jìn)程搶占情況下完成運(yùn)行:

step2.1.1 判斷進(jìn)程截止期是否滿足

若滿足:

執(zhí)行step2.1.2;

否則

輸出由于進(jìn)程tk,m的截止期未被滿足,分區(qū)不可行。轉(zhuǎn)step3;

step2.1.2 更新進(jìn)程的相關(guān)屬性及列表;

step2.2 若Jj中優(yōu)先級(jí)最高的進(jìn)程tk,i不能在不被更高優(yōu)先級(jí)進(jìn)程搶占情況下完成運(yùn)行:

step2.2.1 進(jìn)程截止期Dk,i等是否滿足:

若滿足:

執(zhí)行step2.2.2;

否則

輸出由于進(jìn)程tk,m的截止期未被滿足,分區(qū)不可行。轉(zhuǎn)step3;

step2.2.2 更新進(jìn)程的相關(guān)屬性以及相關(guān)列表;

step2.3.1 更新進(jìn)程的相關(guān)屬性以及相關(guān)列表;

step 2.4.1j=j+1;

否則

輸出:該分區(qū)可調(diào)度,轉(zhuǎn)step3;

step3 終止

該算法基本運(yùn)算在于比較j與nk,并進(jìn)行賦值運(yùn)算,其時(shí)間復(fù)雜度取決于參數(shù)j與參數(shù)k的值,為o(n2)。

基于算法1～3,給出多分區(qū)調(diào)度表的總體可調(diào)度性分析算法。該算法的關(guān)鍵是對(duì)每個(gè)分區(qū)均進(jìn)行一次進(jìn)程可調(diào)度性分析。具體地,針對(duì)每個(gè)分區(qū)的情況,首先執(zhí)行虛擬進(jìn)程生成算法(算法1)將時(shí)間窗口轉(zhuǎn)化為虛擬進(jìn)程,進(jìn)而分非周期進(jìn)程和周期進(jìn)程2種情況分別調(diào)用相應(yīng)的單個(gè)分區(qū)調(diào)度表可行性檢驗(yàn)算法(算法2或算法3)來(lái)判別這個(gè)分區(qū)內(nèi)進(jìn)程和其他時(shí)間窗口的相容性,也就是這個(gè)分區(qū)的可調(diào)度性。通過(guò)依次對(duì)所有分區(qū)均進(jìn)行一遍檢查,就形成了多分區(qū)調(diào)度表的總體可調(diào)度性檢查算法。

算法4多分區(qū)調(diào)度表的總體可調(diào)度性分析算法

輸入:分區(qū)的調(diào)度表(所有時(shí)間窗口的屬性),所有分區(qū)的進(jìn)程列表,分區(qū)個(gè)數(shù)K

具體執(zhí)行步驟如下:

step1 對(duì)i=1:K

step1.1 調(diào)用算法1,生成虛擬進(jìn)程列表;

step1.2 將虛擬進(jìn)程列表和分區(qū)Pi的所有進(jìn)程組合到一起,形成總進(jìn)程列表;

step1.3 如果總進(jìn)程列表均為非周期進(jìn)程,則調(diào)用算法2判斷分區(qū)Pi是否可調(diào)度。

step1.3.1 判斷某個(gè)進(jìn)程截止期等屬性是否滿足:

若滿足:

若后續(xù)還有進(jìn)程,則判斷下一個(gè)進(jìn)程, 否則轉(zhuǎn)step1.5;

若不滿足:

輸出:不可調(diào)度及截止期不滿足的進(jìn)程,轉(zhuǎn)step3;

step1.4 如果總進(jìn)程列表包括周期進(jìn)程,則調(diào)用算法3判斷各個(gè)分區(qū)Pi是否可調(diào)度。

step 1.4.1 判斷某個(gè)進(jìn)程截止期等屬性是否滿足:

若滿足:

若后續(xù)還有進(jìn)程;則判斷下一個(gè)進(jìn)程, 否則轉(zhuǎn)step1.5;

若不滿足:

輸出:不可調(diào)度及截止期不滿足的進(jìn)程,轉(zhuǎn)step3;

step1.5i=i+1;

step2 若所有分區(qū)均可調(diào)度;

輸出:調(diào)度表可調(diào)度,轉(zhuǎn)step3;

step3 終止

該算法基本運(yùn)算在于對(duì)算法1、算法2、算法3的調(diào)用,其時(shí)間復(fù)雜度取決于3個(gè)算法的時(shí)間復(fù)雜度以及K的值,為o(n3)。

針對(duì)給定調(diào)度表和所有分區(qū)內(nèi)全部進(jìn)程的屬性,算法4需首先從數(shù)據(jù)文件載入全部進(jìn)程的序號(hào)、WCET、截止期、周期、優(yōu)先級(jí),以及載入全部時(shí)間窗口的序號(hào)、對(duì)應(yīng)分區(qū)、周期、開(kāi)始時(shí)間、運(yùn)行時(shí)間;然后調(diào)用算法1,對(duì)每個(gè)分區(qū)生成包括時(shí)間窗口虛擬進(jìn)程在內(nèi)的全部總進(jìn)程列表;如果總進(jìn)程列表內(nèi)全部為非周期進(jìn)程,算法2可判斷這些進(jìn)程是否可調(diào)度,如果算法輸出可調(diào)度,則可保證在實(shí)際運(yùn)行時(shí),主時(shí)間框架內(nèi)該分區(qū)的所有非周期進(jìn)程和該分區(qū)外的所有時(shí)間窗口均可運(yùn)行一次;如果總進(jìn)程列表包括周期進(jìn)程,算法3判斷這些進(jìn)程是否可調(diào)度,如果算法輸出可調(diào)度,則在實(shí)際運(yùn)行時(shí),保證該分區(qū)的所有非周期進(jìn)程和該分區(qū)外的所有時(shí)間窗口均可運(yùn)行一次,且該分區(qū)的所有進(jìn)程和該分區(qū)外的所有時(shí)間窗口的周期性和截止期等要求均可得到滿足。

如算法4輸出不可調(diào)度,則說(shuō)明當(dāng)前調(diào)度表不可調(diào)度。根據(jù)跳出循環(huán)的位置,可以判斷是何原因?qū)е抡{(diào)度不可行,如某個(gè)進(jìn)程的截止期太短,或分區(qū)時(shí)間窗口過(guò)小等。用戶可根據(jù)算法4的輸出,相應(yīng)地調(diào)整進(jìn)程的截止期或分區(qū)的時(shí)間窗口屬性,直至得到可行的調(diào)度表配置。

3 算法驗(yàn)證

本節(jié)通過(guò)2個(gè)具體的調(diào)度表,一個(gè)可行以及一個(gè)不可行的實(shí)例,從正反2個(gè)方面來(lái)檢驗(yàn)所設(shè)計(jì)算法。由于本文中所采用調(diào)度表考慮了機(jī)載應(yīng)用分區(qū)領(lǐng)域特征,無(wú)法與現(xiàn)有針對(duì)實(shí)時(shí)操作系統(tǒng)的調(diào)度算法進(jìn)行直接對(duì)比,因此采用正反例方式對(duì)本文提出算法進(jìn)行驗(yàn)證。

3.1 正例:可行的調(diào)度表分析結(jié)果

考慮表6中所述的進(jìn)程屬性和表7中所給的調(diào)度表屬性,通過(guò)虛擬進(jìn)程生成算法,周期進(jìn)程的可調(diào)度性檢查算法以及多分區(qū)調(diào)度表的總體可調(diào)度性檢查算法進(jìn)行可行性的判斷。

表6 進(jìn)程屬性

表7 調(diào)度表屬性

首先,由2.1節(jié)容易計(jì)算出各分區(qū)的分區(qū)循環(huán)時(shí)長(zhǎng):

1) 分區(qū)P1的分區(qū)循環(huán)時(shí)長(zhǎng):[[10,25],30]=[50,30]=150 ms。

2) 分區(qū)P2的分區(qū)循環(huán)時(shí)長(zhǎng):[[50,120], 30]=[600,30]=600 ms。

3) 分區(qū)P3的分區(qū)循環(huán)時(shí)長(zhǎng):[[30, 60],30]=[60,30]=60 ms。

然后,應(yīng)用第2節(jié)的算法1～4,輸入表6和表7中的信息,可輸出“此調(diào)度表可行”。分區(qū)P1、P2、P3進(jìn)程可調(diào)度判斷如圖2～4所示。為了方便展示,這里只展示了第一個(gè)主時(shí)間框架的示意圖,而不是整個(gè)分區(qū)循環(huán)時(shí)長(zhǎng)。

圖4 分區(qū)P3的可調(diào)度性分析分析結(jié)果

在圖2～4中,淺藍(lán)色的豎線表示進(jìn)程就緒時(shí)間,紅色豎線表示進(jìn)程的截止期時(shí)間。因此,進(jìn)程必須在淺藍(lán)色豎線和紅色豎線所標(biāo)定的時(shí)間區(qū)間內(nèi)完成運(yùn)行才可以滿足截止期的要求。而在根據(jù)生成算法產(chǎn)生虛擬進(jìn)程時(shí),因?yàn)榻o其賦予了較高的優(yōu)先級(jí)和特定的屬性,所以虛擬進(jìn)程在可調(diào)度判別過(guò)程中恒定滿足截止期的要求,在每次可調(diào)度判斷時(shí),可以只關(guān)注相應(yīng)分區(qū)包含的真實(shí)進(jìn)程是否滿足截止期的要求。從上述3張圖形中可以看出:分區(qū)1～3的進(jìn)程均可以在截止期內(nèi)完成運(yùn)行,因此不會(huì)造成截止期不被滿足的情況。

3.2 反例:不可行的調(diào)度表分析結(jié)果

在表6中,將進(jìn)程1的周期屬性10改為9,可輸出“此調(diào)度表不可行”。首先,根據(jù)2.1節(jié)可以計(jì)算出分區(qū)P1新的分區(qū)時(shí)長(zhǎng),其他2個(gè)分區(qū)的分區(qū)循環(huán)時(shí)長(zhǎng)保持不變。分區(qū)P1新的分區(qū)循環(huán)時(shí)長(zhǎng)為:[[9,25],30]=[225,30]=450 ms。

然后,調(diào)用算法4針對(duì)分區(qū)P1進(jìn)行可調(diào)度性判斷,如圖5所示。

圖5 分區(qū)P1的可調(diào)度性分析結(jié)果

從圖5中可以看到:進(jìn)程t1,1(A)的第二次就緒時(shí)間至截止期的時(shí)間區(qū)間剛好包含在虛擬進(jìn)程T4的運(yùn)行區(qū)間內(nèi)。由于虛擬進(jìn)程T4的優(yōu)先級(jí)更高,進(jìn)程t1,1(A)無(wú)法搶占計(jì)算資源進(jìn)行運(yùn)行,而只要等到虛擬進(jìn)程T4完成運(yùn)行之后才可以。但是,此時(shí)進(jìn)程t1,1(A)的截止期將不滿足。因此,分區(qū)P1內(nèi)進(jìn)程不可調(diào)度。

4 結(jié) 論

研究了機(jī)載多分區(qū)系統(tǒng)的調(diào)度規(guī)則,提出了一組調(diào)度分析算法,能夠根據(jù)給定的調(diào)度參數(shù)和分區(qū)內(nèi)進(jìn)程時(shí)間屬性,分析系統(tǒng)調(diào)度表的可調(diào)度性。經(jīng)過(guò)正反2個(gè)方面的驗(yàn)證,該算法能夠準(zhǔn)確給出是否可調(diào)度的定性分析結(jié)論,為可調(diào)度性分析工具的設(shè)計(jì)實(shí)現(xiàn)提供了理論支撐。本文提出的算法適用于符合ARINC653標(biāo)準(zhǔn)的分區(qū)操作系統(tǒng)產(chǎn)品,與機(jī)載領(lǐng)域的工程需求吻合,具備較強(qiáng)的應(yīng)用價(jià)值,已在某操作系統(tǒng)配套開(kāi)發(fā)環(huán)境中得到工程應(yīng)用。

隨著多核處理器的廣泛應(yīng)用,可調(diào)度性分析將不再局限于單核處理器。在多核條件下,可調(diào)度性分析呈現(xiàn)出一些完全不同的特征,國(guó)內(nèi)外已經(jīng)有一些前瞻性的研究[21-25],本文的不足之處在于僅對(duì)單核處理器的場(chǎng)景進(jìn)行了研究,后續(xù)還將繼續(xù)針對(duì)多核處理器場(chǎng)景下的調(diào)度模型和調(diào)度算法開(kāi)展相關(guān)研究。