多核處理器數控系統的全局調度算法

彭　浩　張建軍　韓江洪　楊　帆

合肥工業大學安全關鍵工業測控技術教育部工程研究中心,合肥,230009

多核處理器數控系統的全局調度算法

彭浩張建軍韓江洪楊帆

合肥工業大學安全關鍵工業測控技術教育部工程研究中心,合肥,230009

提出了面向多核處理器系統的限制搶占調度算法，通過在任務的末尾設置高優先級(搶占閾值)的限制搶占區，減少任務運行過程中被搶占的次數，提高調度效率。建立了限制搶占調度的可調度性判定條件和限制搶占區設計方法。仿真結果表明，限制搶占調度的調度性能較搶占調度和延遲搶占調度的調度性能有明顯提高。

多核處理器;數控系統;全局調度;限制搶占

0　引言

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

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

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

1　系統的形式化描述

復雜數控系統由硬件平臺和運行在其上的實時控制任務集組成,硬件平臺包含一個m核處理器,實時控制任務集包含n個實時控制任務。

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

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

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

定義1運行優先級表示作業在某個時刻或者時間區間內的優先級,作業Jk運行在普通區時,運行優先級為Pk;運行在限制搶占區時,運行優先級為TPk。

定義2A對B產生干擾是指，當A占用一個處理器運行時,B就不能夠在該處理器上運行,即B不能搶占A。A和B可以分別是一個任務或一個作業。

定義3作業Jk的運行窗口是指從Jk進入就緒狀態到截止期的時間區間。

定義4任務τi在某個時間區間內的負載是指在該時間區間內τi所有作業的累積運行時間長度。

定義5任務τi對作業Jk產生的干擾負載是指在Jk的運行窗口內,τi釋放的作業處于運行狀態而Jk處于就緒狀態但不能運行的累積時間長度。

定義6作業Jk受到的累積干擾負載是指在Jk的運行窗口內所有任務產生的干擾負載的總和。

定義7作業Jk受到的干擾是指在Jk的運行窗口內,Jk處于就緒狀態但得不到運行的累積時間長度。

定義8帶入作業(carry-in job)是指相對于某個時間區間，釋放時間在時間區間前，絕對截止期在時間區間內的作業[11]。

2　GLPS算法描述

GLPS包括在線調度器和離線的可調度性測試兩個部分。在線調度器控制系統運行中實時控制任務的運行秩序和任務運行優先級的變化。可調度性測試用于在系統運行之前確定系統的可行性，即是否所有控制任務都能夠在截止期內正確響應。

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

3　可調度性測試

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

3.1可調度性分析

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

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

(1)

則該作業是可調度的。作業Jk受到的最大干擾Ik([rk,dk])和在Jk的運行窗口[rk,dk]中其他任務產生的最大累積干擾負載ISk([rk,dk])的關系如下：

(2)

在多核系統中,只有所有的核都被高優先級負載占用,作業Jk才無法運行,如圖1所示。式(2)等號右邊表示的是最大累積干擾負載ISk([rk,dk])同時占用m個核的最大可能時間,即作業Jk受到的最大干擾Ik([rk,dk])。

圖1　高優先級負載產生干擾的示意圖

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

(3)

3.2計算最大累計干擾負載

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

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

圖2　其他任務產生干擾的負載

(4)

(5)

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

(6)

(7)

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

(8)

(9)

(10)

其中,當τi∈Ω1∨τi∈Ω2時,L=Dk;當τi∈Ω3∨τi∈Ω4時,L=Sk。

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

在作業Jk的運行窗口[rk,dk]內,除被測試任務τk外的所有任務產生的最大累計干擾負載為

(11)

3.3限制搶占區的最遲開始運行時間

(12)

(13)

4　限制搶占區設計

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

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

圖3　LPRAA的算法流程圖

5　仿真實驗

本節通過生成大量隨機實時控制任務集,以能夠調度的任務集比例為評價指標,比較本文提出的GLPS算法、搶占調度算法FPS[14](fully preemptive scheduling)以及延遲搶占調度算法DPS[10](deferred preemption scheduling)的調度能力。這種對比評價方法在多核實時系統調度研究領域被廣泛采用[10,12,14-15]。

(1)仿真實驗的實驗環境。硬件平臺：Intel Core i7 2.7G處理器,4G RAM;軟件平臺:操作系統為Ubuntu14.04.1,內核為Linux 3.13.0-44。

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

(a)使用DM算法分配優先級

(b)使用DkC算法分配優先級圖4　4核20任務(m=4,n=20)時不同算法可調度隨機控制任務集的比例

(a)使用DM算法分配優先級

(b)使用DkC算法分配優先級圖5　8核40任務(m=8,n=40)時不同算法可調度隨機控制任務集的比例

6　結語

本文針對復雜數控系統中多核處理器上的任務調度問題,以限制搶占行為的方式提高實時控制任務集的可調度性。分析了優先級提高對任務運行過程的影響，在此基礎上建立了實時控制系統的可調度性測試條件，并且提出了限制搶占區的設計方法。仿真實驗結果表明，設置限制搶占區可以有效提高多核實時控制系統的可調度性。

[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消息時隙分配方法研究[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]李迪,萬家富,葉峰,等.軟數控系統混合任務兩級調度策略[J].機械工程學報, 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]姚鑫驊, 傅建中, 陳子辰, 等. 面向數控系統的優化調度算法及容錯策略研究[J].計算機集成制造系統, 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]丁萬夫,郭銳鋒,秦承剛.面向數控系統的容錯實時調度算法研究[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]陸小虎,于東,胡毅,等.基于異構多核處理器的嵌入式數控系統研究[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]谷傳才, 關楠, 于金銘, 等. 多處理器混合關鍵性系統中的劃分調度策略[J].軟件學報, 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

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

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

彭浩,男,1984年生。合肥工業大學計算機與信息學院博士研究生。主要研究方向為實時控制系統、分布式控制系統等。張建軍(通信作者),男,1963年生。合肥工業大學計算機與信息學院教授。韓江洪,男,1954年生。合肥工業大學計算機與信息學院教授、博士研究生導師。楊帆,女,1987年生。合肥工業大學計算機與信息學院博士研究生。