王華忠,　聶永高

(華東理工大學(xué)化工過程先進(jìn)控制與優(yōu)化教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

?

多處理器系統(tǒng)實(shí)時(shí)任務(wù)限制搶占調(diào)度算法

王華忠,聶永高

(華東理工大學(xué)化工過程先進(jìn)控制與優(yōu)化教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

針對多處理器平臺(tái)完全可搶占調(diào)度(Fully Preemptive Scheduling,F-PS)可能造成低優(yōu)先級任務(wù)的響應(yīng)時(shí)間超出截止期限的問題,提出了兩種基于固定搶占點(diǎn)模型的限制搶占調(diào)度算法:一種是常規(guī)延遲(Regular Deferrable Scheduling,RDS),即高優(yōu)先級任務(wù)搶占正在運(yùn)行的執(zhí)行到最近搶占點(diǎn)的低優(yōu)先級任務(wù),被搶占的任務(wù)可能不具有最低優(yōu)先級;另一種是自適應(yīng)延遲(Adaptive Deferrable Scheduling,ADS),即高優(yōu)先級任務(wù)等待正在運(yùn)行的最低優(yōu)先級任務(wù)執(zhí)行到最近的可搶占點(diǎn)位置,并搶占。搭建了一個(gè)仿真實(shí)驗(yàn)平臺(tái),并在該平臺(tái)上進(jìn)行一系列的仿真實(shí)驗(yàn)來探究兩種算法的性能表現(xiàn)。實(shí)驗(yàn)結(jié)果表明:在動(dòng)態(tài)和靜態(tài)優(yōu)先級調(diào)度下,任務(wù)搶占次數(shù)大小順序?yàn)镕-PS > RDS > ADS;當(dāng)搶占時(shí)間消耗大于臨界值時(shí),RDS和ADS的任務(wù)可調(diào)度率與F-PS接近。

多核處理器系統(tǒng)調(diào)度; 限制搶占調(diào)度; 常規(guī)延遲調(diào)度; 自適應(yīng)延遲調(diào)度

實(shí)時(shí)系統(tǒng)已經(jīng)廣泛應(yīng)用于航空航天、軍事電子、進(jìn)程控制、網(wǎng)絡(luò)通信以及多媒體系統(tǒng)等領(lǐng)域[1-3]。在這些系統(tǒng)中,任務(wù)越來越復(fù)雜,對處理器的性能要求越來越高。長久以來,半導(dǎo)體廠商將研究重點(diǎn)放在提高時(shí)鐘頻率上,然而,時(shí)鐘頻率的提高會(huì)導(dǎo)致處理器能耗的急劇提升[4],限制了單核處理器性能的持續(xù)提升。為了研制高性能處理器,硬件廠商將研究重點(diǎn)轉(zhuǎn)到在一個(gè)芯片上集成更多的處理器上,即多處理器系統(tǒng)。與單處理器系統(tǒng)相比,同等性能的情況下,多處理器系統(tǒng)的功耗更低。多處理器系統(tǒng)的發(fā)展使多處理器平臺(tái)的任務(wù)調(diào)度算法的研究越來越迫切。

單處理器平臺(tái)上任務(wù)調(diào)度算法的分類有很多種[5]。根據(jù)任務(wù)的優(yōu)先級在執(zhí)行過程中是否改變,任務(wù)調(diào)度算法可以分為靜態(tài)優(yōu)先級和動(dòng)態(tài)優(yōu)先級調(diào)度算法,例如單調(diào)期限調(diào)度算法(Deadline Monotonic,DM)[6]和最早期限優(yōu)先算法(Early Deadline First,EDF)[7];根據(jù)任務(wù)是否允許延時(shí),任務(wù)調(diào)度算法可以分為強(qiáng)實(shí)時(shí)調(diào)度算法(Hard real-time scheduling)和弱實(shí)時(shí)任務(wù)調(diào)度算法(Weak real-time scheduling);根據(jù)任務(wù)在執(zhí)行過程中是否允許被搶占,任務(wù)調(diào)度算法可以分為可搶占調(diào)度算法(Preemptive Scheduling,PS)以及不可搶占算法(Non-Preemptive Scheduling,NPS)。

為了保證實(shí)時(shí)性,多處理器系統(tǒng)任務(wù)調(diào)度算法都有搶占調(diào)度機(jī)制,即高優(yōu)先級任務(wù)可以搶占CPU上正在運(yùn)行的低優(yōu)先級任務(wù)。然而,由搶占造成的操作系統(tǒng)額外時(shí)間消耗增加了任務(wù)的最壞情況響應(yīng)時(shí)間(Worst Case Response Time,WCRT),可能造成低優(yōu)先級任務(wù)不可調(diào)度。限制搶占調(diào)度(Limited Preemptive Scheduling,LPS)是介于完全可搶占(Fully PS,F-PS)與不可搶占調(diào)度(Fully NPS,F-NPS)之間的一種調(diào)度,兼有兩者的優(yōu)缺點(diǎn)。

本文涉及的多核處理器系統(tǒng)限制搶占調(diào)度算法包括兩種:一種是高優(yōu)先級任務(wù)只搶占所有正在運(yùn)行任務(wù)中最低優(yōu)先級的任務(wù);另一種是高優(yōu)先級任務(wù)搶占最早可被搶占的低優(yōu)先級任務(wù),該任務(wù)優(yōu)先級可能不是最低的。

與單處理器系統(tǒng)實(shí)時(shí)調(diào)度算法相比,多處理器系統(tǒng)實(shí)時(shí)調(diào)度算法不僅要考慮任務(wù)的執(zhí)行策略,還要考慮任務(wù)的CPU分配問題。很多優(yōu)良的單處理器實(shí)時(shí)調(diào)度算法在多處理器系統(tǒng)上的表現(xiàn)并不突出,例如“Dhall 效應(yīng)”[8]。文獻(xiàn)[9]已經(jīng)證明,在單核處理器上,LPS的性能比F-PS與F-NPS優(yōu)良。在多核處理器系統(tǒng),文獻(xiàn)[10]和文獻(xiàn)[11]分別對基于固定優(yōu)先級和動(dòng)態(tài)優(yōu)先級的LPS的性能作了仿真研究,但兩者都沒有考慮任務(wù)搶占的操作系統(tǒng)時(shí)間消耗。而本文考慮了任務(wù)搶占過程的操作系統(tǒng)時(shí)間消耗;對基于固定優(yōu)先級的LPS和基于動(dòng)態(tài)優(yōu)先級的LPS的性能作了橫向?qū)Ρ?對設(shè)計(jì)者在不同應(yīng)用場景之下選擇不同的多核處理器系統(tǒng)LPS有一定的指導(dǎo)作用。

1　基于固定搶占點(diǎn)的限制搶占調(diào)度算法

1.1概述

綜合可預(yù)知性和效率考慮,F-PS與F-NPS算法各有優(yōu)缺點(diǎn)[12]。F-PS算法在保證高優(yōu)先級任務(wù)得到及時(shí)響應(yīng)的同時(shí)增加了低優(yōu)先級任務(wù)的WCRT。而在一些特殊場合,例如I/O讀寫等,由于造價(jià)問題,F-NPS占主導(dǎo)地位。限制搶占調(diào)度算法是一種介于F-PS與F-NPS的一種算法,同時(shí)兼顧兩種算法的優(yōu)缺點(diǎn)。

1.2固定搶占點(diǎn)模型

固定搶占點(diǎn) (Fixed Preemptive Points,FPP)模型是文獻(xiàn)[13]中提到的一種限制搶占模型。在FPP模型中,任務(wù)被若干FPP分為不同的不可搶占區(qū)域(Non-Preemptive Region,NPR),搶占只允許發(fā)生在FPP位置。圖1為FPP模型示意圖,其中任務(wù)τ被FPP分為兩個(gè)不可搶占的部分τ1和τ2,即τ在執(zhí)行τ1和τ2期間不允許被高優(yōu)先級任務(wù)搶占。

圖1　固定搶占點(diǎn) (FPP)模型Fig.1　Model of fixed preemptionpoint(FPP)

與F-PS相比,固定搶占點(diǎn)模型使高優(yōu)先級任務(wù)執(zhí)行延遲一段時(shí)間,延遲時(shí)間與NPR的長度有關(guān)。該延遲可能造成高優(yōu)先級任務(wù)錯(cuò)過截止日期,從而造成任務(wù)集不可調(diào)度。同時(shí),NPR的設(shè)置使任務(wù)集在執(zhí)行過程的搶占次數(shù)減少,任務(wù)搶占過程的操作系統(tǒng)總時(shí)間消耗減少。當(dāng)搶占過程的操作系統(tǒng)總時(shí)間消耗較大時(shí),固定搶占點(diǎn)模型的性能將會(huì)明顯提升。

不難發(fā)現(xiàn),F-PS是固定搶占點(diǎn)模型的特殊情況,即NPR = 1。當(dāng)NPR長度大于任務(wù)的可執(zhí)行時(shí)間時(shí),固定搶占點(diǎn)模型退化為F-NPS。

1.3兩種基于固定搶占點(diǎn)模型的LPS

本文提出了兩種基于固定搶占點(diǎn)模型的多處理器平臺(tái)的限制搶占調(diào)度算法即常規(guī)延遲限制搶占調(diào)度(Regular Deferred Limited Preemptive Scheduling,RD-LPS)和自適應(yīng)延遲限制搶調(diào)度(Adaptive Deferred Limited Preemptive Scheduling,AD-LPS)。在RD-LPS中,高優(yōu)先級任務(wù)搶占最先執(zhí)行到固定搶占點(diǎn)的任務(wù),該任務(wù)可能不是所有正在執(zhí)行中最低優(yōu)先級的任務(wù)。在AD-LPS中,當(dāng)高優(yōu)先級任務(wù)被釋放時(shí),搶占只發(fā)生在所有正在執(zhí)行任務(wù)中最低優(yōu)先級任務(wù)的最近固定搶占點(diǎn)位置。圖2和圖3分別展示了RD-LPS和AD-LPS兩種調(diào)度策略。任務(wù)τ1的優(yōu)先級最低,τ3的優(yōu)先級最高。當(dāng)τ3被釋放時(shí),τ1和τ2正在執(zhí)行。在RD-LPS中,τ3搶占τ2,而在ADS-LPS中,τ3搶占τ1。

圖2　一般延遲限制搶占調(diào)度(RD-LPS)Fig.2　Regular deferred limited preemptive scheduling

圖3　自適應(yīng)延遲限制搶占調(diào)度(AD-LPS)Fig.3　Adaptive deferred limited preemptive scheduling

1.4算法適應(yīng)硬件平臺(tái)

按照計(jì)算內(nèi)核是否對等,多核處理器可以分為同構(gòu)多核和異構(gòu)多核。前者所有的計(jì)算內(nèi)核地位對等,后者采用“主處理核+協(xié)處理核”的設(shè)計(jì)。目前比較主流的多核處理器各CPU核心之間的通信機(jī)制主要是基于總線共享的Cache結(jié)構(gòu)和基于片上的互聯(lián)結(jié)構(gòu)。前者結(jié)構(gòu)簡單,通信速度高,但是可擴(kuò)展性差；后者可擴(kuò)展性好,結(jié)構(gòu)復(fù)雜,軟件改動(dòng)較大。

本文的仿真實(shí)驗(yàn)中,各個(gè)處理器內(nèi)核對等,采用基于總線共享的Cache結(jié)構(gòu),處理器內(nèi)核共享一個(gè)任務(wù)隊(duì)列。

2　實(shí)時(shí)任務(wù)模型

2.1任務(wù)模型

設(shè)有一個(gè)任務(wù)集

(1)

其中τi(1?i?n)為周期任務(wù)。每個(gè)周期任務(wù)τi可以用以下四元表示:

(2)

其中:Ci為任務(wù)執(zhí)行所需要的時(shí)間;Ti為周期任務(wù)周期;Bm為不能被搶占區(qū)域的長度;R(i,j) 為第i個(gè)任務(wù)的第j個(gè)實(shí)例的釋放時(shí)間；Di為周期任務(wù)的相對截止期限。本文假設(shè)任務(wù)集所有任務(wù)的第1個(gè)實(shí)例在t= 0 釋放,R(i,j) 的計(jì)算公式如下:

(3)

2.2操作系統(tǒng)時(shí)間消耗

任務(wù)搶占保證了系統(tǒng)的實(shí)時(shí)性,但是操作系統(tǒng)在任務(wù)搶占過程中有一些額外消耗。文獻(xiàn)[13]提出在每次搶占過程中,操作系統(tǒng)的額外時(shí)間消耗包括上下文切換、總線時(shí)間消耗等。當(dāng)搶占次數(shù)過于頻繁時(shí),操作系統(tǒng)的額外時(shí)間消耗可能導(dǎo)致任務(wù)超出截止期限,即不可調(diào)度。圖4中,操作系統(tǒng)額外時(shí)間消耗導(dǎo)致任務(wù)τ1的執(zhí)行完成時(shí)間超出了截止期限,即該任務(wù)不可調(diào)度。

圖4　搶占導(dǎo)致任務(wù)不可調(diào)度Fig.4　Deadline miss due to the overheads caused by preemption

3　實(shí)驗(yàn)設(shè)計(jì)

3.1任務(wù)生成器

任務(wù)生成器對整個(gè)仿真結(jié)果有著至關(guān)重要的作用。任務(wù)生成算法必須滿足兩點(diǎn)要求:(1)算法隨機(jī)生成任務(wù)的過程是無偏(Unbiased)和理想的(Ideally);(2)可以根據(jù)特定設(shè)定值生成任務(wù)。本文采用Unifast-Discard[14]算法來生成任務(wù)。該算法可以根據(jù)預(yù)先設(shè)定的任務(wù)數(shù)量和任務(wù)總可調(diào)度利用率(Utilization)生成分布均勻的任務(wù),滿足任務(wù)生成算法的要求。

在多處理器系統(tǒng)中,任務(wù)可調(diào)度的必要條件是任務(wù)的總可調(diào)度利用率小于處理器的數(shù)量。

3.2仿真工具

按照任務(wù)分配不同CPU的機(jī)制,多處理器系統(tǒng)任務(wù)調(diào)度可分為劃分調(diào)度(Partitioned Scheduling)和全局調(diào)度(Global Scheduling)[15]。本文采用全局調(diào)度機(jī)制,即所有處理器共享一個(gè)任務(wù)隊(duì)列。

按照任務(wù)優(yōu)先級分配機(jī)制的不同,多處理器系統(tǒng)任務(wù)調(diào)度可分為固定優(yōu)先級調(diào)度(FPS)和動(dòng)態(tài)優(yōu)先級調(diào)度(DPS)。在仿真過程中,本文采用了兩種經(jīng)典的調(diào)度策略,即DM和EDF調(diào)度,分別代表兩種調(diào)度機(jī)制。

為了評估不同調(diào)度算法之間的性能差異,搭建了一個(gè)仿真平臺(tái),包括:

(1) 任務(wù)生成器。該生成器能根據(jù)設(shè)定的任務(wù)數(shù)量和任務(wù)總可調(diào)度利用率生成任務(wù)集;

(2) 搶占調(diào)度算法,即G-P-FPS 和 G-P-DPS;

(3) 不可搶占調(diào)度算法,即G-NP-FPS;

(4)一般延遲限制搶占調(diào)度算法,即G-RD-FPS 和 G-RD-DPS;

(5) 自適應(yīng)限制搶占調(diào)度算法,即G-AD-FPS 和 G-AD-DPS。

3.3實(shí)驗(yàn)內(nèi)容

仿真工具搭建完成后,設(shè)計(jì)一些實(shí)驗(yàn)來評估調(diào)度算法性能的差異。通過控制變量法來驗(yàn)證某一因素對實(shí)驗(yàn)結(jié)果的影響,實(shí)驗(yàn)包括:

(1) 改變總可調(diào)度利用率;

(2) 改變每個(gè)任務(wù)集的任務(wù)數(shù)量;

(3) 改變系統(tǒng)中處理器的數(shù)目;

(4) 改變不可搶占區(qū)域的長度;

(5) 改變搶占過程中操作系統(tǒng)額外消耗的時(shí)間。

4　仿真實(shí)驗(yàn)結(jié)果

4.1實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)參數(shù)的選擇對實(shí)驗(yàn)結(jié)果有很大影響,本文的實(shí)驗(yàn)參數(shù)如下:處理器數(shù)目為16;任務(wù)集數(shù)目為30;每個(gè)任務(wù)集任務(wù)數(shù)目為30;每個(gè)任務(wù)的任務(wù)實(shí)例數(shù)目為2 000;任務(wù)總可調(diào)度利用率為0.6×處理器數(shù)目;任務(wù)最小周期為[1,500];NPR長度為3;搶占過程操作系統(tǒng)額外時(shí)間消耗為1。

4.2任務(wù)總可調(diào)度利用率的影響

任務(wù)的總可調(diào)度利用率對任務(wù)執(zhí)行過程中的搶占次數(shù)有一定的影響。實(shí)驗(yàn)中,將任務(wù)總可調(diào)度利用率從2增加到12,其他條件不變。圖5展示了不同任務(wù)總可調(diào)度利用率下的搶占次數(shù)?？芍?

(1) 搶占次數(shù)隨總可調(diào)度利用率的增大而增大。因?yàn)殡S著任務(wù)總可調(diào)度利用率的增大,任務(wù)的執(zhí)行時(shí)間變長,搶占次數(shù)變多;

(2) 動(dòng)態(tài)優(yōu)先級調(diào)度下的搶占次數(shù)遠(yuǎn)大于固定優(yōu)先級下的調(diào)度次數(shù)。因?yàn)槊總€(gè)時(shí)間單元,任務(wù)的優(yōu)先級發(fā)生改變,搶占次數(shù)增多;

(3) 在兩種優(yōu)先級調(diào)度機(jī)制下,搶占次數(shù)的大小順序是一致的。搶占次數(shù)的大小順序是:完全搶占調(diào)度(G-P-S)> 一般延遲限制搶占調(diào)度(G-RD-S)> 自適應(yīng)延遲限制搶占調(diào)度(G-AD-S)。

圖5　不同任務(wù)總可調(diào)度利用率下的搶占次數(shù)Fig.5　Numbers of preemption different task utilizations

4.3每個(gè)任務(wù)集任務(wù)數(shù)量的影響

將單個(gè)任務(wù)集的任務(wù)數(shù)量從20增加到40,圖6展示了不同任務(wù)數(shù)量下的搶占次數(shù)。由圖6可知:

(1) 搶占次數(shù)隨單個(gè)任務(wù)集任務(wù)數(shù)量的增加而增加。因?yàn)槿蝿?wù)數(shù)量變大,任務(wù)搶占的概率增大。

(2) 動(dòng)態(tài)優(yōu)先級調(diào)度下的搶占次數(shù)遠(yuǎn)大于固定優(yōu)先級下的調(diào)度次數(shù)。

(3) 在兩種優(yōu)先級調(diào)度機(jī)制下,搶占次數(shù)的大小順序與4.2節(jié)實(shí)驗(yàn)結(jié)果相同。

(4) G-P-FPS與G-RD-FPS的搶占次數(shù)比較接近。

4.4處理器數(shù)量的影響

將處理器數(shù)量從2增加到28,仿真結(jié)果如圖7所示。由圖7可知:

(1) 動(dòng)態(tài)優(yōu)先級調(diào)度下,搶占次數(shù)隨處理器數(shù)目的增加而增加。靜態(tài)優(yōu)先調(diào)度下,隨著處理器數(shù)量的增加,搶占次數(shù)先減小后增大。

(2) 動(dòng)態(tài)優(yōu)先級調(diào)度下的搶占次數(shù)遠(yuǎn)大于固定優(yōu)先級調(diào)度下的搶占次數(shù)。

(3) 在兩種優(yōu)先級調(diào)度機(jī)制下,搶占次數(shù)的大小順序與4.2節(jié)、4.3節(jié)的實(shí)驗(yàn)結(jié)果相同。

圖6　單個(gè)任務(wù)集任務(wù)數(shù)量不同時(shí)的搶占次數(shù)Fig.6　Numbers of preemption varying the number of tasks per taskset

圖7　處理器數(shù)目不同時(shí)的任務(wù)搶占次數(shù)Fig.7　Numbers of preemption varying the number of processors

4.5NPR長度的影響

不可搶占區(qū)域(NPR)的長度對LPS的表現(xiàn)有很大的影響,對F-P-S 和F-NP-S沒有影響,仿真結(jié)果如圖8所示。由圖8可知:

(1) 隨著NPR長度的增加,搶占次數(shù)減少。當(dāng)NPR長度增加時(shí),任務(wù)的可搶占點(diǎn)變少,發(fā)生搶占的概率變低,次數(shù)變少。

(2) 當(dāng)NPR長度比較小時(shí),動(dòng)態(tài)優(yōu)先級調(diào)度下的搶占次數(shù)遠(yuǎn)大于固定優(yōu)先級調(diào)度。隨著NPR長度的增加,差距減小。當(dāng)NPR長度較大時(shí),任務(wù)的執(zhí)行時(shí)間與NPR長度相近,動(dòng)態(tài)優(yōu)先級調(diào)度退化為靜態(tài)優(yōu)先級調(diào)度,兩者的搶占次數(shù)接近。

(3) 兩種優(yōu)先級調(diào)度機(jī)制的搶占次數(shù)大小順序一致。

圖8　NPR長度不同時(shí)的任務(wù)搶占次數(shù)Fig.8　Numbers of preemption varing the length of NPR

4.6搶占過程操作系統(tǒng)額外時(shí)間消耗的影響

在每次搶占過程中,操作系統(tǒng)會(huì)有一些額外的時(shí)間消耗,影響調(diào)度算法的表現(xiàn)。圖9和圖10分別示出了隨著操作系統(tǒng)額外時(shí)間消耗的增大,任務(wù)在動(dòng)態(tài)優(yōu)先級和靜態(tài)優(yōu)先級調(diào)度的可調(diào)度率。由圖9和圖10知:

(1) 隨著搶占消耗時(shí)間的增加,可搶占的調(diào)度算法的任務(wù)可調(diào)度率快速降低,當(dāng)時(shí)間消耗數(shù)值大于6時(shí),搶占調(diào)度的任務(wù)可調(diào)度率低于不可搶占調(diào)度；當(dāng)數(shù)值大于19時(shí),搶占調(diào)度的可調(diào)度率接近0。

(2) 額外時(shí)間消耗的增加對G-P-DPS的影響程度最大,因?yàn)樵谠撜{(diào)度中,搶占次數(shù)最多。當(dāng)時(shí)間消耗大于某個(gè)值時(shí),可搶占調(diào)度與限制搶占調(diào)度的可調(diào)度率接近。

圖9　動(dòng)態(tài)優(yōu)先級調(diào)度下?lián)屨紩r(shí)間不同時(shí)的可調(diào)度率Fig.9　Schedulable ration of tasksets varying the overheads under dynamic priority scheduling

圖10　靜態(tài)優(yōu)先級調(diào)度下?lián)屨紩r(shí)間不同時(shí)的可調(diào)度率Fig.10　Schedulable ration of tasksets varying the overheads under static priority scheduling

5　結(jié)論和展望

綜合在仿真平臺(tái)上實(shí)施一系列的仿真實(shí)驗(yàn)結(jié)果,不難發(fā)現(xiàn),在多處理器平臺(tái)上:

(1) 動(dòng)態(tài)優(yōu)先級調(diào)度的搶占次數(shù)遠(yuǎn)大于靜態(tài)優(yōu)先級調(diào)度的搶占次數(shù);在每次搶占過程中,操作系統(tǒng)都有一定的時(shí)間消耗。操作系統(tǒng)的時(shí)間消耗增大時(shí),動(dòng)態(tài)優(yōu)先級調(diào)度的性能明顯下降。當(dāng)時(shí)間消耗達(dá)到一定程度時(shí),動(dòng)態(tài)優(yōu)先級調(diào)度的性能比靜態(tài)優(yōu)先級調(diào)度差。

(2) 搶占次數(shù)的大小順序?yàn)镚-P-DPS > G-RD-DPS > G-AD-DPS > G-P-FPS > G-RD-FPS > G-AD-FPS。

(3) 搶占調(diào)度的任務(wù)可調(diào)度率隨搶占時(shí)間消耗的增大而降低。當(dāng)時(shí)間消耗大于某個(gè)值時(shí),搶占調(diào)度的任務(wù)可調(diào)度率低于不可搶占調(diào)度。

本文仍有一些局限之處:首先,由于實(shí)驗(yàn)條件的限制,本文的限制搶占調(diào)度算法的性能未能在實(shí)際多核處理器平臺(tái)上驗(yàn)證;其次,本文仿真產(chǎn)生的任務(wù)為周期性任務(wù),多核平臺(tái)的限制搶占調(diào)度算法對非周期性任務(wù)的性能表現(xiàn)是否與周期性任務(wù)相似尚未得到驗(yàn)證。

[1]王濤.實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度若干關(guān)鍵技術(shù)的研究[D].哈爾濱:哈爾濱工程大學(xué),2006.

[2]賓雪蓮.實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2004.

[3]彭浩,韓江洪,陸陽,等.多處理器硬實(shí)時(shí)系統(tǒng)的搶占閾值調(diào)度研究[J].計(jì)算機(jī)研究與發(fā)展,2015,52(5):1177-1186.

[4]ANSARI K H,CHITRA P.Power-aware scheduling of fixed priority tasks in soft real-time multicore systems[C]//2013 IEEE International Conference on Emerging Trends in Computing,Communication and Nano Technology.USA：IEEE，2013：496-502.

[5]LI Jie.The research of scheduling algorithms in real-time system[C]//2010 International Conference on Computer and Communication Technologies in Agriculture Engineering.USA：IEEE，2010:333-336.

[6]LEUNG J,WHITEHEAD J.On the complexity of fixed priority scheduling of periodic real-time tasks[J].Performance Evaluation,1982:2(4):237 -250.

[7]LIU C L,LAYLAND J.Scheduling algorithms for multiprogramming in a hard real-time systems[J].Journal of the ACM,1973,20(1):46-61.

[8]DHALL S K,LIU C L.On a real-time scheduling problem[J].Operations Research,1978,26:127-140.

[9]MARINHO J,NELIS V.Limited preemptive global fixed task priority[C]//2013 IEEE 34th Real-Time Systems Symposium.Canada:IEEE,2013:182-191.

[10]NIE YONGGAO,THEKKILAKATTIL A.Limited preemptive fixed priority scheduling of real-time tasks on multi-processors[D].Sweden:Malardalen University,2015.

[11]ZHU Kaiqian,THEKKILAKATTIL A.Limited preemptive early deadline first scheduling of real-time tasks on multi-processors[D].Sweden:Malardalen University,2015.

[12]GRENIER M,NAVET N.Fine-tuning MAC-level protocols for optimized real-time QoS[J].IEEE Transactions on Industrial Informatics,2008,4(1):6-15.

[13]BUTTAZZ G C,BERTOGNA M,YAO Gang.Limited preemptive scheduling for real-time systems[J].IEEE Transactions on Industrial Informatics,2013,9(1):3-15.

[14]DAVIS R,BURNS A.Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[C]//30th IEEE Real-Time Systems Symposium.Washington,DC:IEEE,2010:398-409.

[15]LAUZAC S,MELHEM R,MOSS′E D.Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor[C]//10th Euromicro Workshop on Real-Time Systems.Berlin:IEEE,1998:188-195.

Real-Time Task Limited Preemptive Scheduling on Multi-processors

WANG Hua-zhong,NIE Yong-gao

(Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

In multi-processors scheduling,fully preemptive scheduling (F-PS) may result in the tasks with lower priority beyond the deadline.In this work,two limited preemptive scheduling (LPS) algorithms are proposed to solve the above problem.The first one is regular deferrable scheduling (RDS),in which the tasks with higher priority preempt the first among the lower priority tasks that finish executing a non-preemptive region.The other is adaptive deferrable scheduling (ADS),where the scheduler waits to preempt the lowest priority running task.A series of experiments are carried out via the built simulator to investigate the performance of the two LPS,which show:(1) the number of preemptions in dynamic and static scheduling is F-PS > RDS >ADS;(2) the schedulable ratios of RDS and ADS are almost equal to the one of F-PS when the time consuming in preemptions is bigger that the threshold.

multi-processors scheduling; limited preemptive scheduling; regular deferrable scheduling; adaptive deferrable scheduling

A

1006-3080(2016)03-0393-06

10.14135/j.cnki.1006-3080.2016.03.016

2015-09-25

王華忠(1969-),男，江蘇南京人，副教授，博士，從事工業(yè)過程模型化與控制的研究。

TP316