多核處理器數(shù)控系統(tǒng)的全局調(diào)度算法

彭　浩　張建軍　韓江洪　楊　帆

合肥工業(yè)大學(xué)安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,合肥,230009

多核處理器數(shù)控系統(tǒng)的全局調(diào)度算法

彭浩張建軍韓江洪楊帆

合肥工業(yè)大學(xué)安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,合肥,230009

提出了面向多核處理器系統(tǒng)的限制搶占調(diào)度算法，通過在任務(wù)的末尾設(shè)置高優(yōu)先級(jí)(搶占閾值)的限制搶占區(qū)，減少任務(wù)運(yùn)行過程中被搶占的次數(shù)，提高調(diào)度效率。建立了限制搶占調(diào)度的可調(diào)度性判定條件和限制搶占區(qū)設(shè)計(jì)方法。仿真結(jié)果表明，限制搶占調(diào)度的調(diào)度性能較搶占調(diào)度和延遲搶占調(diào)度的調(diào)度性能有明顯提高。

多核處理器;數(shù)控系統(tǒng);全局調(diào)度;限制搶占

0　引言

數(shù)控技術(shù)是現(xiàn)代制造業(yè)的核心技術(shù)之一。隨著數(shù)控技術(shù)的飛速發(fā)展,人們對(duì)數(shù)控系統(tǒng)計(jì)算能力的要求越來越高。以文獻(xiàn)[1]中研究的光刻機(jī)為例，系統(tǒng)中同時(shí)運(yùn)行上千個(gè)實(shí)時(shí)控制任務(wù)，每個(gè)任務(wù)都有嚴(yán)格的運(yùn)行時(shí)限約束，系統(tǒng)所需的計(jì)算能力由多個(gè)同構(gòu)多核處理器硬件模塊提供，模塊間使用實(shí)時(shí)通信網(wǎng)絡(luò)傳輸數(shù)據(jù)。在這樣一個(gè)分布式實(shí)時(shí)控制系統(tǒng)中，模塊間傳輸?shù)臄?shù)據(jù)需要共享通信網(wǎng)絡(luò)資源，一個(gè)模塊上運(yùn)行的實(shí)時(shí)控制任務(wù)集需要共享處理器資源。許多學(xué)者針對(duì)不同實(shí)時(shí)通信網(wǎng)絡(luò)的調(diào)度問題進(jìn)行了深入研究[2-3]。文獻(xiàn)[4]針對(duì)軟數(shù)控系統(tǒng)中的混合任務(wù)集,提出了兩級(jí)結(jié)構(gòu)的調(diào)度策略。文獻(xiàn)[5]利用人工智能領(lǐng)域的啟發(fā)式搜索算法，提出了最佳優(yōu)先調(diào)度BF(best first)算法，并結(jié)合回卷容錯(cuò)機(jī)制，用以提高數(shù)控系統(tǒng)運(yùn)行的可靠性。文獻(xiàn)[6]研究了數(shù)控系統(tǒng)的容錯(cuò)調(diào)度問題，通過盡量推遲替代版本的運(yùn)行，提高了主版本成功率。上述研究針對(duì)的都是單核處理器數(shù)控系統(tǒng)的調(diào)度問題，本文的研究對(duì)象是多核處理器數(shù)控系統(tǒng)。文獻(xiàn)[7]研究了異構(gòu)多核處理器數(shù)控系統(tǒng)中的劃分調(diào)度問題，而本文研究同構(gòu)多核處理器數(shù)控系統(tǒng)中的全局調(diào)度問題。

在多核實(shí)時(shí)調(diào)度問題中，一個(gè)核心內(nèi)容是提高多核實(shí)時(shí)調(diào)度算法的調(diào)度能力。調(diào)度能力強(qiáng)的多核實(shí)時(shí)調(diào)度算法能夠在有限的資源約束(核的數(shù)量)下滿足更多復(fù)雜實(shí)時(shí)控制任務(wù)集的時(shí)間約束要求。多核實(shí)時(shí)控制系統(tǒng)調(diào)度主要分為劃分調(diào)度(partitioned scheduling)和全局調(diào)度(global scheduling)兩類。劃分調(diào)度將實(shí)時(shí)控制任務(wù)集分成若干個(gè)組,每組任務(wù)占用1個(gè)獨(dú)立的核運(yùn)行[7-8],這樣就把1個(gè)多核調(diào)度問題轉(zhuǎn)化成了多個(gè)單核調(diào)度問題,可以直接使用已經(jīng)成熟的單核實(shí)時(shí)調(diào)度理論。劃分調(diào)度的弱點(diǎn)在于，當(dāng)有任務(wù)就緒但是所屬的核被高優(yōu)先級(jí)任務(wù)占用時(shí)，即使有空閑的核也不能被調(diào)度運(yùn)行，并且劃分調(diào)度會(huì)帶來更多的搶占數(shù)量，導(dǎo)致不必要的資源開銷[9]。全局調(diào)度允許任務(wù)在任意1個(gè)核上運(yùn)行,并且被搶占之后可以在別的核上恢復(fù)，這樣就不會(huì)出現(xiàn)有空閑的核而任務(wù)不能運(yùn)行的問題。

為了提高多核全局實(shí)時(shí)調(diào)度算法的調(diào)度性能,文獻(xiàn)[10]將單核實(shí)時(shí)調(diào)度中的延遲搶占調(diào)度算法(deferred preemption scheduling)擴(kuò)展到多核領(lǐng)域。延遲搶占通過在任務(wù)中劃分不可搶占區(qū)來減少不必要搶占的數(shù)量,以提高系統(tǒng)的可調(diào)度性。但是延遲搶占只考慮了利用最高優(yōu)先級(jí)實(shí)時(shí)控制任務(wù)的剩余資源，而該任務(wù)通常又是剩余資源最少的任務(wù)，這限制了調(diào)度性能的提升。在實(shí)時(shí)控制任務(wù)集中,中優(yōu)先級(jí)實(shí)時(shí)控制任務(wù)一般有剩余資源較多的情況,因此,本文提出多核實(shí)時(shí)控制系統(tǒng)的全局限制搶占調(diào)度(global limited preemption scheduling,GLPS)算法,在任務(wù)末段設(shè)置一段高優(yōu)先級(jí)區(qū)域(相對(duì)前面的部分更高，不一定是最高優(yōu)先級(jí)),以免實(shí)時(shí)控制任務(wù)在運(yùn)行過程中受到不必要搶占,并且避免給高優(yōu)先級(jí)任務(wù)帶來過大的額外資源需求壓力，從而提高實(shí)時(shí)控制任務(wù)集的可調(diào)度性。

1　系統(tǒng)的形式化描述

復(fù)雜數(shù)控系統(tǒng)由硬件平臺(tái)和運(yùn)行在其上的實(shí)時(shí)控制任務(wù)集組成,硬件平臺(tái)包含一個(gè)m核處理器,實(shí)時(shí)控制任務(wù)集包含n個(gè)實(shí)時(shí)控制任務(wù)。

任務(wù)集中的單個(gè)任務(wù)分為普通區(qū)和限制搶占區(qū)兩個(gè)部分,普通區(qū)在前,用六元組τi(Ti,Ci,Di,Pi,TPi,Fi)表示序號(hào)為i的任務(wù)，其中,Ti表示任務(wù)的最小釋放間隔，即相鄰兩次運(yùn)行開始時(shí)刻的最小時(shí)間間隔，對(duì)于周期任務(wù)來說即其周期;Ci表示任務(wù)的最壞情況運(yùn)行時(shí)間，包含普通區(qū)和限制搶占區(qū);Di表示任務(wù)的相對(duì)截止期，即運(yùn)行時(shí)限，Di≤Ti;Pi表示任務(wù)的優(yōu)先級(jí),數(shù)值越小代表優(yōu)先級(jí)越高，每個(gè)任務(wù)有全局唯一的優(yōu)先級(jí)；TPi表示限制搶占區(qū)的搶占閾值,即限制搶占區(qū)的優(yōu)先級(jí)，TPi≤Pi,搶占閾值不具有唯一性;Fi表示限制搶占區(qū)的長度。

任務(wù)在每個(gè)周期開始時(shí)釋放一次作業(yè),在不需要特別指明作業(yè)的序數(shù)時(shí),用Ji表示任務(wù)τi的一次作業(yè);ri表示作業(yè)Ji的釋放時(shí)間；di表示作業(yè)Ji絕對(duì)截止期，di=ri+Di;sk表示作業(yè)Jk的限制搶占區(qū)開始運(yùn)行的時(shí)間。

為了便于理解下文的分析過程,給出下列定義:

定義1運(yùn)行優(yōu)先級(jí)表示作業(yè)在某個(gè)時(shí)刻或者時(shí)間區(qū)間內(nèi)的優(yōu)先級(jí),作業(yè)Jk運(yùn)行在普通區(qū)時(shí),運(yùn)行優(yōu)先級(jí)為Pk;運(yùn)行在限制搶占區(qū)時(shí),運(yùn)行優(yōu)先級(jí)為TPk。

定義2A對(duì)B產(chǎn)生干擾是指，當(dāng)A占用一個(gè)處理器運(yùn)行時(shí),B就不能夠在該處理器上運(yùn)行,即B不能搶占A。A和B可以分別是一個(gè)任務(wù)或一個(gè)作業(yè)。

定義3作業(yè)Jk的運(yùn)行窗口是指從Jk進(jìn)入就緒狀態(tài)到截止期的時(shí)間區(qū)間。

定義4任務(wù)τi在某個(gè)時(shí)間區(qū)間內(nèi)的負(fù)載是指在該時(shí)間區(qū)間內(nèi)τi所有作業(yè)的累積運(yùn)行時(shí)間長度。

定義5任務(wù)τi對(duì)作業(yè)Jk產(chǎn)生的干擾負(fù)載是指在Jk的運(yùn)行窗口內(nèi),τi釋放的作業(yè)處于運(yùn)行狀態(tài)而Jk處于就緒狀態(tài)但不能運(yùn)行的累積時(shí)間長度。

定義6作業(yè)Jk受到的累積干擾負(fù)載是指在Jk的運(yùn)行窗口內(nèi)所有任務(wù)產(chǎn)生的干擾負(fù)載的總和。

定義7作業(yè)Jk受到的干擾是指在Jk的運(yùn)行窗口內(nèi),Jk處于就緒狀態(tài)但得不到運(yùn)行的累積時(shí)間長度。

定義8帶入作業(yè)(carry-in job)是指相對(duì)于某個(gè)時(shí)間區(qū)間，釋放時(shí)間在時(shí)間區(qū)間前，絕對(duì)截止期在時(shí)間區(qū)間內(nèi)的作業(yè)[11]。

2　GLPS算法描述

GLPS包括在線調(diào)度器和離線的可調(diào)度性測試兩個(gè)部分。在線調(diào)度器控制系統(tǒng)運(yùn)行中實(shí)時(shí)控制任務(wù)的運(yùn)行秩序和任務(wù)運(yùn)行優(yōu)先級(jí)的變化。可調(diào)度性測試用于在系統(tǒng)運(yùn)行之前確定系統(tǒng)的可行性，即是否所有控制任務(wù)都能夠在截止期內(nèi)正確響應(yīng)。

實(shí)時(shí)控制任務(wù)在每個(gè)周期開始時(shí)釋放1次作業(yè),此時(shí)作業(yè)的運(yùn)行優(yōu)先級(jí)等于任務(wù)的優(yōu)先級(jí)P,在運(yùn)行C-F個(gè)時(shí)間單位(普通區(qū)的長度)后,調(diào)度器將該作業(yè)的運(yùn)行優(yōu)先級(jí)提升至搶占閾值TP,直到該作業(yè)完成工作運(yùn)行優(yōu)先級(jí)都不會(huì)再發(fā)生變化。在任意時(shí)刻調(diào)度器調(diào)度優(yōu)先級(jí)最高的m(核的數(shù)量)個(gè)作業(yè)在多核處理器上運(yùn)行。在運(yùn)行過程中搶占是始終被允許的,即任意時(shí)刻釋放的作業(yè)在沒有空閑的核可以運(yùn)行的情況下,會(huì)搶占運(yùn)行優(yōu)先級(jí)低于該作業(yè)的正在運(yùn)行的作業(yè)，如果有多個(gè)運(yùn)行優(yōu)先級(jí)低的作業(yè)，則搶占運(yùn)行優(yōu)先級(jí)最低的作業(yè);如果沒有運(yùn)行優(yōu)先級(jí)更低的作業(yè)，則等待直到有空閑的核可以使用。

3　可調(diào)度性測試

可調(diào)度性測試是實(shí)時(shí)調(diào)度算法的重要組成部分,是確定實(shí)時(shí)控制系統(tǒng)可行性的重要技術(shù)。實(shí)時(shí)控制任務(wù)可調(diào)度是指該任務(wù)釋放的每一次作業(yè)都能在時(shí)限內(nèi),即截止期內(nèi)完成工作。實(shí)時(shí)控制任務(wù)集可調(diào)度是指該任務(wù)集內(nèi)所有的任務(wù)都是可調(diào)度的。本文基于截止期分析法(deadline analysis,DA)[12]建立GLPS的可調(diào)度性測試,該測試每次判定一個(gè)實(shí)時(shí)控制任務(wù)的可調(diào)度性,判定硬件平臺(tái)上的整個(gè)實(shí)時(shí)控制任務(wù)集的可調(diào)度性時(shí)，需要對(duì)每個(gè)實(shí)時(shí)控制任務(wù)運(yùn)行一次測試過程。

3.1可調(diào)度性分析

假設(shè)被測試的實(shí)時(shí)控制任務(wù)為τk,τk釋放的一次作業(yè)Jk受到最大干擾而最遲響應(yīng),那么如果作業(yè)Jk可以在截止期dk前正確響應(yīng),則τk釋放的所有作業(yè)都能在規(guī)定時(shí)限內(nèi)完成工作,所以被測試控制任務(wù)τk是可調(diào)度的。作業(yè)Jk在時(shí)刻rk釋放,絕對(duì)截止期是dk,那么在其運(yùn)行窗口[rk,dk]中,如果作業(yè)Jk受到的最大干擾為Ik([rk,dk]),即所有核都被更高優(yōu)先級(jí)負(fù)載占用的最大時(shí)間長度,和作業(yè)Jk的最長運(yùn)行時(shí)間Ck、相對(duì)截止期Dk的關(guān)系滿足下式：

Ik([rk,dk])+Ck≤Dk

(1)

則該作業(yè)是可調(diào)度的。作業(yè)Jk受到的最大干擾Ik([rk,dk])和在Jk的運(yùn)行窗口[rk,dk]中其他任務(wù)產(chǎn)生的最大累積干擾負(fù)載ISk([rk,dk])的關(guān)系如下：

(2)

在多核系統(tǒng)中,只有所有的核都被高優(yōu)先級(jí)負(fù)載占用,作業(yè)Jk才無法運(yùn)行,如圖1所示。式(2)等號(hào)右邊表示的是最大累積干擾負(fù)載ISk([rk,dk])同時(shí)占用m個(gè)核的最大可能時(shí)間,即作業(yè)Jk受到的最大干擾Ik([rk,dk])。

圖1　高優(yōu)先級(jí)負(fù)載產(chǎn)生干擾的示意圖

根據(jù)式(1)和式(2),可以推導(dǎo)出作業(yè)Jk的可調(diào)度條件,即被測試實(shí)時(shí)控制任務(wù)τk的可調(diào)度條件是在Jk的運(yùn)行窗口[rk,dk]中其他任務(wù)產(chǎn)生的最大累積干擾負(fù)載ISk([rk,dk])滿足下式:

(3)

3.2計(jì)算最大累計(jì)干擾負(fù)載

在Jk的運(yùn)行窗口[rk,dk]中,其他控制任務(wù)產(chǎn)生的最大累積干擾負(fù)載ISk([rk,dk])是實(shí)時(shí)控制任務(wù)集中除被測試控制任務(wù)τk之外的其他所有任務(wù)產(chǎn)生的最大干擾負(fù)載之和,因此,需要分別計(jì)算每個(gè)控制任務(wù)產(chǎn)生的最大干擾負(fù)載。而求最大干擾負(fù)載，需要先計(jì)算該任務(wù)在Jk的運(yùn)行窗口[rk,dk]中產(chǎn)生干擾的最大負(fù)載。

作業(yè)Jk在運(yùn)行窗口[rk,dk]內(nèi)的sk時(shí)刻運(yùn)行優(yōu)先級(jí)由Pk提升到TPk,實(shí)時(shí)控制任務(wù)集中的另一個(gè)任務(wù)τi在運(yùn)行過程中也會(huì)發(fā)生一次優(yōu)先級(jí)提升，因此,根據(jù)Jk的優(yōu)先級(jí)Pk和搶占閾值TPk以及τi的優(yōu)先級(jí)Pi和搶占閾值TPi的高低關(guān)系,可以把控制任務(wù)集中的其他任務(wù)分別劃分到集合Ω1～Ω5中(Ω5是不產(chǎn)生干擾的任務(wù)集合)。每個(gè)集合中的任務(wù)在不同的時(shí)間區(qū)間([rk,sk]或[rk,dk])干擾作業(yè)Jk的運(yùn)行,并且產(chǎn)生干擾的部分也不相同(全部或只有限制搶占區(qū))。圖2是集合Ω1～Ω4中的任務(wù)產(chǎn)生干擾的示意圖,圖中T僅為示意作用,并不表示具體某個(gè)任務(wù)的最小釋放間隔。由圖2可以看出,sk的位置對(duì)Ω1和Ω2中的任務(wù)產(chǎn)生干擾的負(fù)載并無影響,而sk時(shí)刻越遲,Ω3和Ω4中的任務(wù)產(chǎn)生干擾的負(fù)載越大,因此,假設(shè)sk出現(xiàn)在其最遲可能時(shí)刻,即任務(wù)的限制搶占區(qū)開始運(yùn)行時(shí)間最晚,同時(shí)假設(shè)的[rk,sk]長度為Sk。本節(jié)假設(shè)限制搶占區(qū)的最遲開始運(yùn)行時(shí)間是已知參數(shù)。

圖2　其他任務(wù)產(chǎn)生干擾的負(fù)載

(4)

(5)

(2)Ω2={τi|TPi≤TPk≤Pk

(6)

(7)

(5)Ω5={τi|τi?Ω1-4}。Ω5中的任務(wù)不產(chǎn)生干擾。

(8)

(9)

(10)

其中,當(dāng)τi∈Ω1∨τi∈Ω2時(shí),L=Dk;當(dāng)τi∈Ω3∨τi∈Ω4時(shí),L=Sk。

限制控制任務(wù)τi最大干擾負(fù)載不超過Dk-Ck+1的原因是,τi釋放的作業(yè)同一時(shí)刻只能在一個(gè)核上運(yùn)行,如果其最大干擾負(fù)載達(dá)到Dk-Ck+1,就相當(dāng)于占用了一個(gè)核而使作業(yè)Jk不能在這個(gè)核上被調(diào)度,但如果繼續(xù)增加τi干擾負(fù)載,在計(jì)算最大干擾時(shí)(式(2))，超過Dk-Ck+1的干擾負(fù)載會(huì)被平均到m個(gè)核上,錯(cuò)誤地增加所有核都被占用的時(shí)間長度，造成判定結(jié)果偏離實(shí)際情況。

在作業(yè)Jk的運(yùn)行窗口[rk,dk]內(nèi),除被測試任務(wù)τk外的所有任務(wù)產(chǎn)生的最大累計(jì)干擾負(fù)載為

(11)

3.3限制搶占區(qū)的最遲開始運(yùn)行時(shí)間

(12)

(13)

4　限制搶占區(qū)設(shè)計(jì)

在GLPS中,限制搶占區(qū)的設(shè)置是影響實(shí)時(shí)控制任務(wù)集是否可調(diào)度的關(guān)鍵因素。假設(shè)一個(gè)已分配優(yōu)先級(jí)的任務(wù)集被判定為不可調(diào)度，如果在不可調(diào)度的任務(wù)τi的末尾設(shè)置一段限制搶占區(qū)，減少該任務(wù)每次運(yùn)行時(shí)受到的干擾，可能使該任務(wù)為可調(diào)度的。但同時(shí)，限制搶占區(qū)會(huì)給高優(yōu)先級(jí)任務(wù)帶來額外的干擾負(fù)載，可能使得原先可調(diào)度的高優(yōu)先級(jí)任務(wù)變成不可調(diào)度。設(shè)計(jì)限制搶占區(qū)涉及如何選取限制搶占區(qū)的兩個(gè)參數(shù)：搶占閾值TPi和限制搶占區(qū)的長度Fi。這兩個(gè)參數(shù)相互影響，通常提高搶占閾值意味著可以縮短限制搶占區(qū)的長度，對(duì)高優(yōu)先級(jí)任務(wù)的額外干擾相對(duì)較少，但不論采用哪種優(yōu)先級(jí)分配算法(如DM、DkC、OPA)，一般優(yōu)先級(jí)越高的任務(wù)能夠承受的額外干擾越小,簡單地分配有高搶占閾值的限制搶占區(qū)可能造成原先可調(diào)度的高優(yōu)先級(jí)任務(wù)變?yōu)椴豢烧{(diào)度，更嚴(yán)重的是通過設(shè)置限制搶占區(qū)使高優(yōu)先級(jí)任務(wù)可調(diào)度的困難非常大，特別是對(duì)最高優(yōu)先級(jí)任務(wù)該方法不可行。事實(shí)上，一個(gè)低優(yōu)先級(jí)的不可調(diào)度任務(wù)可能只需要設(shè)置一個(gè)搶占閾值比自身優(yōu)先級(jí)(普通區(qū)優(yōu)先級(jí))略高的限制搶占區(qū)就可調(diào)度，而且這樣做不會(huì)給資源需求壓力已經(jīng)很大的高優(yōu)先級(jí)任務(wù)帶來額外干擾。盡量減少高優(yōu)先級(jí)任務(wù)的額外干擾，充分利用中優(yōu)先級(jí)任務(wù)的剩余資源是設(shè)計(jì)限制搶占區(qū)的主導(dǎo)思想。

本節(jié)綜合考慮限制搶占區(qū)的搶占閾值和長度，提出一種限制搶占區(qū)分配算法(limited preemption region assignment algorithm,LPRAA)。LPRAA假設(shè)待處理的任務(wù)集已經(jīng)分配了優(yōu)先級(jí),但被判定為不可調(diào)度。LPRAA從最低優(yōu)先級(jí)任務(wù)開始遍歷控制任務(wù)集中的所有控制任務(wù),每當(dāng)遇到不可調(diào)度的控制任務(wù),則計(jì)算所有搶占閾值小于該任務(wù)當(dāng)前搶占閾值(數(shù)值小則優(yōu)先級(jí)高)的可以令該任務(wù)可調(diào)度的最小(長度最短)限制搶占區(qū)作為候選,再從中選擇使控制任務(wù)集中不可調(diào)度任務(wù)數(shù)量最少的限制搶占區(qū)配置，并更新控制任務(wù)集中所有任務(wù)的可調(diào)度性狀態(tài)。如果有多個(gè)限制搶占區(qū)配置符合條件,則取其中搶占閾值最小的。如果在遍歷結(jié)束后控制任務(wù)集仍不可調(diào)度(存在不可調(diào)度的任務(wù))，則再次執(zhí)行上述遍歷過程，直至控制任務(wù)集可調(diào)度，或是有某個(gè)控制任務(wù)無法找到使其可調(diào)度的限制搶占區(qū)，則該控制任務(wù)集不可調(diào)度。圖3是LPRAA的算法流程圖。

圖3　LPRAA的算法流程圖

5　仿真實(shí)驗(yàn)

本節(jié)通過生成大量隨機(jī)實(shí)時(shí)控制任務(wù)集,以能夠調(diào)度的任務(wù)集比例為評(píng)價(jià)指標(biāo),比較本文提出的GLPS算法、搶占調(diào)度算法FPS[14](fully preemptive scheduling)以及延遲搶占調(diào)度算法DPS[10](deferred preemption scheduling)的調(diào)度能力。這種對(duì)比評(píng)價(jià)方法在多核實(shí)時(shí)系統(tǒng)調(diào)度研究領(lǐng)域被廣泛采用[10,12,14-15]。

(1)仿真實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境。硬件平臺(tái)：Intel Core i7 2.7G處理器,4G RAM;軟件平臺(tái):操作系統(tǒng)為Ubuntu14.04.1,內(nèi)核為Linux 3.13.0-44。

在圖4和圖5中,橫軸為隨機(jī)生成的實(shí)時(shí)控制任務(wù)集的總使用率,縱軸為可調(diào)度任務(wù)集的比例?？梢钥闯?在使用相同的優(yōu)先級(jí)分配算法(DM或DkC)時(shí),GLPS和DPS可調(diào)度任務(wù)集比例明顯高于FPS,說明不必要的搶占會(huì)減弱實(shí)時(shí)控制系統(tǒng)的可調(diào)度性，而GLPS可調(diào)度任務(wù)集比例又高于DPS的可調(diào)度任務(wù)集比例，這個(gè)結(jié)果證明本文提出的利用中優(yōu)先級(jí)任務(wù)的剩余資源的策略比僅利用最高優(yōu)先級(jí)任務(wù)的剩余資源更有效。DPS將任務(wù)末段直接賦予最高優(yōu)先級(jí)，干擾了最高優(yōu)先級(jí)任務(wù)運(yùn)行，而最高優(yōu)先級(jí)任務(wù)通常承受干擾的能力很差，這是DPS調(diào)度性能弱于GLPS調(diào)度性能的最大原因。

(a)使用DM算法分配優(yōu)先級(jí)

(b)使用DkC算法分配優(yōu)先級(jí)圖4　4核20任務(wù)(m=4,n=20)時(shí)不同算法可調(diào)度隨機(jī)控制任務(wù)集的比例

(a)使用DM算法分配優(yōu)先級(jí)

(b)使用DkC算法分配優(yōu)先級(jí)圖5　8核40任務(wù)(m=8,n=40)時(shí)不同算法可調(diào)度隨機(jī)控制任務(wù)集的比例

6　結(jié)語

本文針對(duì)復(fù)雜數(shù)控系統(tǒng)中多核處理器上的任務(wù)調(diào)度問題,以限制搶占行為的方式提高實(shí)時(shí)控制任務(wù)集的可調(diào)度性。分析了優(yōu)先級(jí)提高對(duì)任務(wù)運(yùn)行過程的影響，在此基礎(chǔ)上建立了實(shí)時(shí)控制系統(tǒng)的可調(diào)度性測試條件，并且提出了限制搶占區(qū)的設(shè)計(jì)方法。仿真實(shí)驗(yàn)結(jié)果表明，設(shè)置限制搶占區(qū)可以有效提高多核實(shí)時(shí)控制系統(tǒng)的可調(diào)度性。

[1]Adyanthaya S,Geilen M,Basten T,et al.Fast Multiprocessor Scheduling with Fixed Task Binding of Large Scale Industrial Cyber Physical Systems[C]//Proceedings of Euromicro Conference on Digital System Design.Los Alamitos,2013:979-988.

[2]張利,張本宏,王躍飛,等.基于總線占用率的FlexRay消息時(shí)隙分配方法研究[J].中國機(jī)械工程, 2012, 23(6): 699-702.

Zhang Li,Zhang Benhong, Wang Yuefei, et al. Research on FlexRay Message Slot Distribution Methods Based on Bus Occupancy Rate [J]. China Mechanical Engineering, 2012, 23(6): 699-702.

[3]Selicean D T,Pop P,Steiner W.Design Optimization of TTEthernet-based Distributed Real-time Systems[J].Real-Time Systems,2014,51(1):1-35.

[4]李迪,萬家富,葉峰,等.軟數(shù)控系統(tǒng)混合任務(wù)兩級(jí)調(diào)度策略[J].機(jī)械工程學(xué)報(bào), 2008, 44(12): 157-162.

Li Di,Wan Jiafu,Ye Feng,et al.Two-level Hierarchical Scheduling Scheme of Hybrid Tasks for Software CNC System[J].Chinese Journal of Mechanical Engineering,2008,44(12):157-162.

[5]姚鑫驊, 傅建中, 陳子辰, 等. 面向數(shù)控系統(tǒng)的優(yōu)化調(diào)度算法及容錯(cuò)策略研究[J].計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(4): 768-776.

Yao Xinhua, Fu Jianzhong, Chen Zichen, et al. Optimazed Scheduling Algorithm Oriented to Numerical Control System [J]. Computer Integrated Manufacturing Systems, 2007, 13(4): 768-776.

[6]丁萬夫,郭銳鋒,秦承剛.面向數(shù)控系統(tǒng)的容錯(cuò)實(shí)時(shí)調(diào)度算法研究[J].中國機(jī)械工程,2010,21(15):1809-1815.

Ding Wanfu,Guo Ruifeng,Qin Chenggang.Real-time Scheduling Algorithm with Fault-tolerance in Numerical Control Systems[J].China Mechanical Engineering,2010,21(15):1809-1815.

[7]陸小虎,于東,胡毅,等.基于異構(gòu)多核處理器的嵌入式數(shù)控系統(tǒng)研究[J].中國機(jī)械工程,2013,24(19):2623-2628.

Lu Xiaohu,Yu Dong,Hu Yi,et al.Study on Embedded NC System Based on Heterogeneous Multi-core Processors[J].China Mechanical Engineering,2013,24(19):2623-2628.

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

Gu Chuancai, Guan Nan, Yu Jinming, et al. Partitioned Scheduling Polocies on Multi-processor Mixed-criticality Systems [J]. Journal of Software, 2014, 25(2): 284-297.

[9]Andersson B,Jonsson J.Fixed-priority Preemptive Multiprocessor Scheduling:to Partition or not to Partition[C]//Proceedings of 7th International Conference on Real-time Computing Systems and Applications.Cheju Island:IEEE,2000:337-346.

[10]Davis R I,Burns A,Marinho J,et al.Global Fixed Priority Scheduling with Deferred Pre-emption[C]//Proceedings of IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications.Taipei:IEEE,2013:1-11.

[11]Lee J,Shin I.Limited Carry-in Technique for Real-time Multi-core Scheduling[J].Journal of Systems Architecture,2013,59(7):372-375.

[12]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.

[13]Guan N,Wang Y.Fixed-priority Multiprocessor Scheduling:Critical Instant,Response Time and Utilization Bound [C]//Proceedings of Parallel and Distributed Processing Symposium Workshops & PhD Forum.Shanghai,2012:2470-2473.

[14]Guan N, Stigge M, Yi W, et al. New Response Time Bounds for Fixed Priority Multiprocessor Scheduling[C]//Proceedings of 30th IEEE Real-Time Systems Symposium.Washington,D C,2009:387-397.

[15]Chen H M,Luo W,Wang W,et al.A Novel Real-Time Fault-Tolerant Scheduling Algorithm Based on Distributed Control Systems[C]//Proceedings of 2011 International Conference on Computer Science and Service System.Nanjing,2011:80-83.

(編輯陳勇)

Global Scheduling for Multicore Processor-Based Numerical Control Systems Peng HaoZhang JianjunHan JianghongYang Fan

Engineering Research Center of Safety Critical Industry Measure and Control Technology,

Ministry of Education,Hefei University of Technology,Hefei,230009

A multicore global limited preemption scheduling algorithm was proposed to take advantages of preemption while reducing the unnecessary preemptions herein.A limited preemption region was set up at the end of each task which had higher priority,i.e. preemption threshold.By decreasing unnecessary preemptions,the schedulability of the whole system increased.The schedulability test was established as well as a heuristic limited preemption region assignment algorithm.It is shown by simulation that limited preemption scheduling has better performance than that of preemptive global scheduling and deferred preemption global scheduling.

multicore processor;numerical control system;global scheduling;limited preemption

2015-01-28

國家自然科學(xué)基金資助項(xiàng)目(61370088);國家國際科技合作專項(xiàng)(2014DFB10060)

TP316DOI：10.3969/j.issn.1004-132X.2015.20.013

彭浩,男,1984年生。合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院博士研究生。主要研究方向?yàn)閷?shí)時(shí)控制系統(tǒng)、分布式控制系統(tǒng)等。張建軍(通信作者),男,1963年生。合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院教授。韓江洪,男,1954年生。合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院教授、博士研究生導(dǎo)師。楊帆,女,1987年生。合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院博士研究生。