多處理器系統(tǒng)實時任務限制搶占調度算法

王華忠,　聶永高

(華東理工大學化工過程先進控制與優(yōu)化教育部重點實驗室,上海 200237)

?

多處理器系統(tǒng)實時任務限制搶占調度算法

王華忠,聶永高

(華東理工大學化工過程先進控制與優(yōu)化教育部重點實驗室,上海 200237)

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

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

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

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

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

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

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

1　基于固定搶占點的限制搶占調度算法

1.1概述

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

1.2固定搶占點模型

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

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

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

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

1.3兩種基于固定搶占點模型的LPS

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

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

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

1.4算法適應硬件平臺

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

本文的仿真實驗中,各個處理器內核對等,采用基于總線共享的Cache結構,處理器內核共享一個任務隊列。

2　實時任務模型

2.1任務模型

設有一個任務集

(1)

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

(2)

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

(3)

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

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

圖4　搶占導致任務不可調度Fig.4　Deadline miss due to the overheads caused by preemption

3　實驗設計

3.1任務生成器

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

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

3.2仿真工具

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

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

為了評估不同調度算法之間的性能差異,搭建了一個仿真平臺,包括:

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

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

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

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

(5) 自適應限制搶占調度算法,即G-AD-FPS 和 G-AD-DPS。

3.3實驗內容

仿真工具搭建完成后,設計一些實驗來評估調度算法性能的差異。通過控制變量法來驗證某一因素對實驗結果的影響,實驗包括:

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

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

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

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

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

4　仿真實驗結果

4.1實驗參數(shù)

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

4.2任務總可調度利用率的影響

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

(1) 搶占次數(shù)隨總可調度利用率的增大而增大。因為隨著任務總可調度利用率的增大,任務的執(zhí)行時間變長,搶占次數(shù)變多;

(2) 動態(tài)優(yōu)先級調度下的搶占次數(shù)遠大于固定優(yōu)先級下的調度次數(shù)。因為每個時間單元,任務的優(yōu)先級發(fā)生改變,搶占次數(shù)增多;

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

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

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

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

(1) 搶占次數(shù)隨單個任務集任務數(shù)量的增加而增加。因為任務數(shù)量變大,任務搶占的概率增大。

(2) 動態(tài)優(yōu)先級調度下的搶占次數(shù)遠大于固定優(yōu)先級下的調度次數(shù)。

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

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

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

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

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

(2) 動態(tài)優(yōu)先級調度下的搶占次數(shù)遠大于固定優(yōu)先級調度下的搶占次數(shù)。

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

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

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

4.5NPR長度的影響

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

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

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

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

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

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

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

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

(2) 額外時間消耗的增加對G-P-DPS的影響程度最大,因為在該調度中,搶占次數(shù)最多。當時間消耗大于某個值時,可搶占調度與限制搶占調度的可調度率接近。

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

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

5　結論和展望

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

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

(2) 搶占次數(shù)的大小順序為G-P-DPS > G-RD-DPS > G-AD-DPS > G-P-FPS > G-RD-FPS > G-AD-FPS。

(3) 搶占調度的任務可調度率隨搶占時間消耗的增大而降低。當時間消耗大于某個值時,搶占調度的任務可調度率低于不可搶占調度。

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

[1]王濤.實時系統(tǒng)任務調度若干關鍵技術的研究[D].哈爾濱:哈爾濱工程大學,2006.

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

[3]彭浩,韓江洪,陸陽,等.多處理器硬實時系統(tǒng)的搶占閾值調度研究[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