王穎慧,郭銳鋒,韓衛(wèi)光,尹震宇,鄧昌義,彭阿珍,吳昊天

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

基于多核ARM的數(shù)控系統(tǒng)實(shí)時性研究①

王穎慧1,2,郭銳鋒2,韓衛(wèi)光2,尹震宇2,鄧昌義1,2,彭阿珍1,2,吳昊天1,2

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

隨著數(shù)控系統(tǒng)的不斷發(fā)展,數(shù)控系統(tǒng)對精度和速度有了更高的要求,這都對當(dāng)前普遍采用的單核處理器平臺提出了嚴(yán)峻的挑戰(zhàn).基于同構(gòu)的四核ARM處理器平臺,在添加了實(shí)時補(bǔ)丁的Linux系統(tǒng)環(huán)境下,根據(jù)數(shù)控系統(tǒng)中硬實(shí)時任務(wù)、軟實(shí)時任務(wù)、非實(shí)時任務(wù)并存的特點(diǎn),把數(shù)控系統(tǒng)任務(wù)合理的分配到多核ARM上運(yùn)行,并采用改進(jìn)的RM算法進(jìn)行調(diào)度,最后對新的任務(wù)調(diào)度算法進(jìn)行實(shí)時性能測試.本調(diào)度模型能夠解決了數(shù)控系統(tǒng)混合任務(wù)調(diào)度的問題,并能滿足數(shù)控系統(tǒng)對實(shí)時性的要求.

多核ARM;實(shí)時調(diào)度;RM算法;IRM算法

1 引言

目前基于嵌入式芯片的數(shù)控系統(tǒng)普遍采用單核處理器平臺,隨著對數(shù)控系統(tǒng)功能和性能要求的不斷提高,對處理器平臺的性能要求也越來越高,在單核平臺上運(yùn)行高檔數(shù)控系統(tǒng)軟件遇到了嚴(yán)峻的挑戰(zhàn).單純通過提高CPU的主頻和指令的執(zhí)行效率來提高性能,不僅會帶來巨大的功耗問題,而且還面臨著技術(shù)和工藝方面的瓶頸.多核處理器的出現(xiàn),大大提高了處理器的性能,滿足了人們對處理器性能提高的要求,成了商業(yè)化處理器的發(fā)展趨勢,但也給體系結(jié)構(gòu)、軟件、功耗和安全性設(shè)計(jì)等方面帶來了巨大挑戰(zhàn),多核系統(tǒng)線程調(diào)度算法就是其中一個重要的研究方向.隨著數(shù)控技術(shù)的發(fā)展,加工對象的復(fù)雜度增加,處理器處理運(yùn)動控制插補(bǔ)運(yùn)算的高速度高精度要求更高,要解決這一問題,除了更換更好性能的ARM芯片,多核ARM是其另一個重要的發(fā)展方向.

數(shù)控系統(tǒng)具有實(shí)時性和多任務(wù)的特點(diǎn)[1],如當(dāng)數(shù)控系統(tǒng)正處于加工控制狀態(tài)時,各數(shù)控加工程序段的預(yù)處理、插補(bǔ)計(jì)算、位置控制和各種輔助控制任務(wù)都要及時進(jìn)行.且數(shù)控系統(tǒng)是一個實(shí)時任務(wù)系統(tǒng),其任務(wù)按是否具有實(shí)時性要求和周期性要求可分為:實(shí)時周期性任務(wù)、實(shí)時突發(fā)性任務(wù)和非實(shí)時任務(wù).數(shù)控系統(tǒng)任務(wù)的復(fù)雜性,使得單核處理器不再適應(yīng)數(shù)控系統(tǒng)對速度和精度的要求,而將多核ARM應(yīng)用于數(shù)控系統(tǒng)可以根據(jù)任務(wù)的不同性質(zhì)將任務(wù)合理的分配到不同的核,減少所有任務(wù)都等待同一個處理器而增加的延時,從而更好的適應(yīng)數(shù)控系統(tǒng)的要求.目前,對多核處理器實(shí)時調(diào)度算法的研究主要為了提高多核處理器系統(tǒng)的負(fù)載平衡,本文采用改進(jìn)的RM調(diào)度算法,主要針對數(shù)控系統(tǒng)混合任務(wù)的特點(diǎn),可減小插補(bǔ)周期的延遲,提高數(shù)控系統(tǒng)加工工件的精度和速度.

2 基于數(shù)控系統(tǒng)的RM調(diào)度算法及其改進(jìn)算法

2.1 RM調(diào)度算法的概述

1973年Liu和Layland提出的單調(diào)速率調(diào)度算法(RM)[5]是一種靜態(tài)優(yōu)先級調(diào)度算法,已被證明是可搶占的硬實(shí)時周期性任務(wù)調(diào)度的最優(yōu)算法.RM算法應(yīng)用于周期任務(wù),根據(jù)任務(wù)的周期來分配優(yōu)先級,周期越短,優(yōu)先級越高.理想的RM調(diào)度模型是基于一系列假設(shè)的基礎(chǔ)上的,這些假設(shè)是RM調(diào)度算法可執(zhí)行的必要條件,RM調(diào)度模型的基本假設(shè)如下:

(A1) 所有的任務(wù)請求都是相隔固定時間觸發(fā)的即任務(wù)具有周期性,且為硬實(shí)時任務(wù),任務(wù)必須在規(guī)定的時限內(nèi)完成;

(A2)任務(wù)的周期即為任務(wù)的截止期,即任務(wù)必須在下一次任務(wù)到來之前完成;

(A3)任務(wù)之間是相互獨(dú)立的,每個任務(wù)的請求和執(zhí)行與其他任務(wù)的請求和執(zhí)行無關(guān);

(A4)每個任務(wù)的運(yùn)行時間是不變的,這里任務(wù)的運(yùn)行時間是指處理器在無中斷情況下用于處理該任務(wù)的時間;

(A5)系統(tǒng)調(diào)度和任務(wù)的上下文切換的時間不計(jì);

(A6)任務(wù)之間是可搶占的,高優(yōu)先級任務(wù)可以搶占低優(yōu)先級任務(wù);

(A7)默認(rèn)CPU是任務(wù)唯一需要爭奪的資源,任務(wù)所需的其他資源都是可滿足的.

給定一個獨(dú)立的任務(wù)集S={t1,t2,…,tn},集合中任務(wù)ti={Ei,Ti,Di}(i=1,…,n),其中,Ei表示任務(wù)ti的執(zhí)行時間,Ti表示任務(wù)ti的周期,Di表示任務(wù)ti的截止期限.如果這n個任務(wù)的CPU利用率滿足下面的條件:

則該任務(wù)集S用RM算法是可調(diào)度的.L(n)表示這n個任務(wù)的CPU利用率的最小上界.當(dāng)任務(wù)的數(shù)量n趨向于無窮大時,L(n)的最大值約為0.69,即系統(tǒng)的CPU利用率最大值為69%.圖1為RM調(diào)度算法的任務(wù)調(diào)度圖.

圖1 RM調(diào)度算法任務(wù)調(diào)度

由于RM調(diào)度算法的可執(zhí)行條件的限制,導(dǎo)致RM調(diào)度算法在面對數(shù)控系統(tǒng)的實(shí)時環(huán)境方面存在一些不足.首先,數(shù)控系統(tǒng)是混合任務(wù)系統(tǒng),不僅有周期任務(wù)還有非周期任務(wù),而RM調(diào)度算法規(guī)定實(shí)時任務(wù)必須為周期任務(wù);其次,RM調(diào)度算法是固定優(yōu)先級調(diào)度算法,它的優(yōu)先級只取決于任務(wù)的周期,任務(wù)周期越短,優(yōu)先級越高,但是數(shù)控系統(tǒng)中的實(shí)時任務(wù)除了實(shí)時周期任務(wù),還有實(shí)時突發(fā)任務(wù),這些任務(wù)周期不固定且具有很高的實(shí)時性,需要系統(tǒng)及時的響應(yīng)和處理.使用RM調(diào)度算法可能會使得一些重要的實(shí)時突發(fā)任務(wù)得不到調(diào)度,從而超過任務(wù)的時限,給系統(tǒng)帶來不可挽回的錯誤.

2.2 基于RM調(diào)度算法的改進(jìn)算法

基于以上提到的RM調(diào)度算法的不足,文獻(xiàn)[3]提出一種基于RM調(diào)度算法的單調(diào)速率計(jì)算能力調(diào)度算法[3],該算法是應(yīng)用于云環(huán)境任務(wù)調(diào)度.因數(shù)控系統(tǒng)有其自身的特點(diǎn),例如:混合多任務(wù)、高要求的實(shí)時性等.本文在該算法的基礎(chǔ)上進(jìn)行改進(jìn),提出一種能更好的適用于數(shù)控系統(tǒng)任務(wù)環(huán)境的調(diào)度算法IRM算法,使其更好的滿足數(shù)控系統(tǒng)對實(shí)時性的要求.

文獻(xiàn)[3]在RM調(diào)度算法的基礎(chǔ)上引進(jìn)參數(shù)I,I表示一個任務(wù)的重要程度,數(shù)控系統(tǒng)操作者根據(jù)經(jīng)驗(yàn)靜態(tài)的給不同的實(shí)時任務(wù)賦一個I值,則數(shù)控系統(tǒng)任務(wù)的優(yōu)先級為:其中,Di為任務(wù)的截止時間,周期任務(wù)的Ti=Di,ξ根據(jù)任務(wù)的性質(zhì)設(shè)定,P值越大表示任務(wù)的優(yōu)先級越高.本文在該算法的基礎(chǔ)上引入一個計(jì)數(shù)值N,N的值表示數(shù)控系統(tǒng)實(shí)時任務(wù)還可以等待多長時間,N=D-E-C(C表示任務(wù)已經(jīng)等待的時間),這可以判斷哪些任務(wù)不能在該核上繼續(xù)等待,否則會錯過截止期限,通過對N值的判斷可以將不能繼續(xù)等待的任務(wù)遷移到其他核運(yùn)行,從而避免這些任務(wù)錯過截止期限.設(shè)置兩個隊(duì)列Q、R分別存放數(shù)控系統(tǒng)實(shí)時任務(wù).

IRM調(diào)度算法描述如下:

(1)調(diào)度開始;

(2)通過(3)式計(jì)算各個任務(wù)的優(yōu)先級,按優(yōu)先級從高到低進(jìn)行排列;

(3)設(shè)置兩個隊(duì)列Q和R,且為每一個實(shí)時任務(wù)設(shè)置一個N值,計(jì)算并保存N值;

(4)按優(yōu)先級從高到低選取實(shí)時任務(wù),使用(1)(2)式來計(jì)算實(shí)時任務(wù)集是否可調(diào)度,選取最大可調(diào)度集,將此可調(diào)度集任務(wù)加入隊(duì)列Q中,將剩余任務(wù)加入隊(duì)列R中;

(5)選取隊(duì)列Q中的優(yōu)先級最高的任務(wù)調(diào)度執(zhí)行,同時每個時鐘周期將任務(wù)的N值減一,若某個任務(wù)的N<1,則將此任務(wù)遷移到其他核執(zhí)行;

(6)判斷隊(duì)列R是否為空,如果為空,執(zhí)行第7步,如果不是空隊(duì)列,則執(zhí)行第4步;

(7)判斷隊(duì)列Q是否為空,如果是空執(zhí)行第8步,如果不為空跳回到第5步;

(8)調(diào)度結(jié)束.

由此看出,改進(jìn)的RM調(diào)度算法,任務(wù)的優(yōu)先級不再僅僅取決于任務(wù)的周期,而是任務(wù)的重要度和截止期的二元函數(shù).同時為每一個任務(wù)維持一個表示還能等待多長時間的N值,保證任務(wù)不會由于等待而錯過截止期限.這樣在多任務(wù)混合的數(shù)控系統(tǒng)中,不僅能夠保證周期任務(wù)的正常運(yùn)行,而且能夠使得非周期任務(wù)能及時響應(yīng).由此可以看出,IRM調(diào)度算法比RM調(diào)度算法更加適用于多種實(shí)時任務(wù)并存的數(shù)控系統(tǒng),能更好的滿足數(shù)控系統(tǒng)對實(shí)時性的需求.

3 多核處理器下數(shù)控系統(tǒng)的架構(gòu)及實(shí)驗(yàn)結(jié)果分析

3.1 多核處理器下數(shù)控系統(tǒng)的架構(gòu)

按照對實(shí)時性要求的不同,數(shù)控系統(tǒng)的任務(wù)可分為硬實(shí)時任務(wù)、軟實(shí)時任務(wù)和非實(shí)時任務(wù).在單核處理器時代,其主要解決方法為在保證實(shí)時任務(wù)能夠在周期內(nèi)完成的前提下,在處理器空閑的時間才執(zhí)行非實(shí)時任務(wù).由于處理器的個數(shù)限制,使得非實(shí)時任務(wù)的等待時間大大的增加,甚至導(dǎo)致非實(shí)時任務(wù)得不到運(yùn)行.同時也可能由于多個實(shí)時任務(wù)的周期相近而導(dǎo)致實(shí)時任務(wù)不能在截止期內(nèi)完成.

軌跡插補(bǔ)是數(shù)控系統(tǒng)最重要的計(jì)算任務(wù),軌跡插補(bǔ)具有實(shí)時性和精度的要求,數(shù)控系統(tǒng)如果需要提高加工零件的精度,則需要提高插補(bǔ)的精度,插補(bǔ)精度可以通過減小步長獲得,但減小步長將導(dǎo)致計(jì)算量成倍地增加,極大地限制機(jī)床進(jìn)的進(jìn)給速度的提高,甚至可能造成數(shù)控系統(tǒng)無法進(jìn)行實(shí)時加工.本文基于以上考慮,從任務(wù)分配和任務(wù)調(diào)度兩個方面來縮小插補(bǔ)周期,提高數(shù)控系統(tǒng)的加工精度,同時保證數(shù)控系統(tǒng)的其他任務(wù)能夠更加高效的運(yùn)行.基于數(shù)控系統(tǒng)對實(shí)時性的需求,本文基于四核的ARM硬件結(jié)構(gòu),采用開源的Linux為軟件系統(tǒng)來搭建數(shù)控系統(tǒng).

圖2 數(shù)控系統(tǒng)任務(wù)分配

圖2 中,數(shù)控系統(tǒng)非實(shí)時任務(wù)分配到core0上執(zhí)行,使用Linux的分時調(diào)度器調(diào)度.軟實(shí)時任務(wù)在core1核上調(diào)度,采用Linux的實(shí)時調(diào)度器進(jìn)行調(diào)度.core2核上調(diào)度數(shù)控系統(tǒng)的硬實(shí)時任務(wù),采用IRM調(diào)度算法進(jìn)行調(diào)度,當(dāng)core2核上某個任務(wù)的剩余等待時間N<1時,則將此任務(wù)賦予一個最高優(yōu)先級,遷移到core1核上運(yùn)行.core3核上運(yùn)行數(shù)控系統(tǒng)的插補(bǔ)任務(wù),使用RM調(diào)度算法進(jìn)行調(diào)度,單獨(dú)為插補(bǔ)任務(wù)分配一個內(nèi)核運(yùn)行,有利于插補(bǔ)任務(wù)周期的縮短,能有效提高數(shù)控系統(tǒng)的加工精度.此任務(wù)分配模型既可以保證數(shù)控系統(tǒng)重要的實(shí)時任務(wù)能夠得到更快的執(zhí)行,也可以保證非實(shí)時任務(wù)能夠及時的響應(yīng),有效的解決了數(shù)控系統(tǒng)多任務(wù)混合的調(diào)度問題.

3.2仿真實(shí)驗(yàn)與結(jié)果分析

本文基于四核ARM結(jié)構(gòu),操作系統(tǒng)為添加了實(shí)時內(nèi)核的Linux系統(tǒng),實(shí)時內(nèi)核為Xenomai.

3.2.1 Linux系統(tǒng)實(shí)時性能測試

本文針對數(shù)控系統(tǒng)的延遲時間進(jìn)行了測試,分別就Linux系統(tǒng)和添加了Xenomai實(shí)時內(nèi)核后的系統(tǒng)進(jìn)行了20000次實(shí)驗(yàn),以下是測試結(jié)果.

圖3 未添加實(shí)時補(bǔ)丁的系統(tǒng)延遲

圖4 添加實(shí)時補(bǔ)丁的系統(tǒng)延遲

圖3 為標(biāo)準(zhǔn)Linux內(nèi)核的延遲,延遲的最大值為97us,最小值為15us,平均值為20us,延遲的波動性較大,延遲時間較大,系統(tǒng)的實(shí)時性能不佳.圖4為添加了實(shí)時補(bǔ)丁后的系統(tǒng)延遲,其最大延遲為40us,最小延遲為5us,延遲的時間比較穩(wěn)定,平均延遲為11us.從結(jié)果可以看出,增加了實(shí)時補(bǔ)丁的Linux系統(tǒng)延遲明顯減小,系統(tǒng)延遲更加穩(wěn)定,能更好的提高系統(tǒng)對任務(wù)的響應(yīng)速度,使得增加了實(shí)時補(bǔ)丁的系統(tǒng)比之前的系統(tǒng)在實(shí)時性能方面有很大的提高,能更好的滿足數(shù)控系統(tǒng)對實(shí)時性的要求.

3.2.2 數(shù)控系統(tǒng)實(shí)時任務(wù)調(diào)度測試

本文基于搭建的數(shù)控系統(tǒng)仿真環(huán)境進(jìn)行性能測試,插補(bǔ)算法選用逐點(diǎn)比較法[10],直線插補(bǔ)算法是在本地進(jìn)行模擬測試,設(shè)插補(bǔ)周期為1ms和0.8ms,分別用C語言對直線插補(bǔ)進(jìn)行仿真,把交叉編譯后的程序在目標(biāo)平臺上運(yùn)行,測試結(jié)果表明該插補(bǔ)算法可以在目標(biāo)平臺上運(yùn)行并繪制出一條直線,插補(bǔ)運(yùn)算都能在其周期內(nèi)完成,從而說明數(shù)控系統(tǒng)的實(shí)時性能基本能夠滿足數(shù)控系統(tǒng)插補(bǔ)運(yùn)算的要求,能夠明顯的縮短數(shù)控系統(tǒng)的插補(bǔ)周期.

4 總結(jié)

由于單核處理器在性能上遇到的瓶頸問題,多核處理器的出現(xiàn)有效的提高了系統(tǒng)的性能和效率,將多核處理器應(yīng)用到數(shù)控系統(tǒng)能有效的提高數(shù)控系統(tǒng)的效率,滿足數(shù)控系統(tǒng)對速度和精度的要求.本文基于四核的ARM處理器,搭建添加了實(shí)時補(bǔ)丁的Linux操作系統(tǒng),將數(shù)控系統(tǒng)任務(wù)合理的分配到每個核上運(yùn)行,很好的提高了數(shù)控系統(tǒng)的效率.同時使用改進(jìn)的RM調(diào)度算法來調(diào)度數(shù)控系統(tǒng)的實(shí)時任務(wù),能夠進(jìn)一步提高數(shù)控系統(tǒng)的加工速度和精度.接下來的進(jìn)一步任務(wù)是進(jìn)行大量的實(shí)驗(yàn),根據(jù)這些實(shí)驗(yàn)的經(jīng)驗(yàn)確定合理的插補(bǔ)周期,既能保證數(shù)控任務(wù)精度的要求也能使插補(bǔ)運(yùn)算能夠在周期內(nèi)完成.

1王保勝,馬躍,吳文江,秦承剛.開放式數(shù)控系統(tǒng)任務(wù)調(diào)度模型.控制與檢測,2010,(6):37–39,42.

2丁萬夫,郭銳鋒,高甜容,秦承剛.面向數(shù)控系統(tǒng)的三級調(diào)度模型研究.小型微型計(jì)算機(jī)系統(tǒng),2011,3(3):439–443.

3王琪元,閆宏印.基于改進(jìn)RM算法的云環(huán)境任務(wù)調(diào)度研究.計(jì)算機(jī)測量與控制,2013,21(6):1612–1614.

4鄭玉虎,王品,陸小虎.基于雙核處理器平臺的數(shù)控系統(tǒng)軟件架構(gòu)設(shè)計(jì).組合機(jī)床與自動化加工技術(shù),2013,(8):62–65.

5 Liu CL,Layland J.Scheduling algorithms for multiprogramming in a hard real-time environment.Journal of the ACM,1973,20(1):46–61.

6張修棋.基于Linux多核進(jìn)程調(diào)度的研究[碩士學(xué)位論文].成都:電子科技大學(xué),2012.

7張曉龍.實(shí)時系統(tǒng)性能測試方法的研究及應(yīng)用[碩士學(xué)位論文].北京:中國科學(xué)院大學(xué),2014.

8姚鑫驊,潘雪增,傅建中,陳子辰.數(shù)控系統(tǒng)的混合任務(wù)模型及其最優(yōu)調(diào)度算法研究.浙江大學(xué)學(xué)報(bào),2006,40(8):1315–1319.

9王濤,王太勇,許愛芬,趙麗,楊潔.嵌入式實(shí)時操作系統(tǒng)在數(shù)控系統(tǒng)設(shè)計(jì)中的應(yīng)用.計(jì)算機(jī)工程,2008,34(4):250,251,268.

10金中波,張百臣,韓霞,代洪慶.逐點(diǎn)比較法直線插補(bǔ)原理及其改進(jìn)算法分析.機(jī)械工程師,2009,3:126–128.

11 Laplante PA,Ovaska SJ.Real-Time Systems Design and Analysis.IEEE Press,2012:237–253.

12韓守謙,裴海龍,王清陽.基于Xenomai的實(shí)時嵌入式Linux操作系統(tǒng)的構(gòu)建.計(jì)算機(jī)工程與設(shè)計(jì),2011,32(1):96–98,102.

13 Zheng YH,Wang P,Lu XH.CNC Software architecture design based on dual-core CPU platform.Modular Machine Tool&AutomaticManufacturingTechnique,2013,(8):62–65.

Real-Time Performance of CNC System Based on Multi-CoreARM

WANG Ying-Hui1,2,GUO Rui-Feng2,HAN Wei-Guang2,YIN Zhen-Yu2,DENG Chang-Yi1,2,PENG A-Zhen1,2,WU Hao-Tian1,2

1(University of ChineseAcademy of Sciences,Beijing 100049,China)

2(Shenyang Institute of Computing Technology,ChineseAcademy of Sciences,Shenyang 110168,China)

With the continuous development of computer numerical control(CNC)system,there are higher requirements of accuracy and speed for CNC system,which brings grave challenge for the current most widely used single-core processor platform.In this paper,based on isomorphic quad core ARM processor platform which is under the Linux system environment with the real-time patch,according to the characteristic of hard real-time tasks,soft real-time tasks and non real-time tasks running parallel in the CNC system,the CNC system tasks are distributed to multi-core ARM reasonably.The improved RM algorithm is used to schedule.Finally execute the real-time performance test for the new scheduling algorithm.This scheduling model can solve the problems of mixed tasks scheduling of CNC system admirably,can well meet the real-time requirement of real-time control of CNC system.

multi-coreARM;real-time scheduling algorithm;rate-monotonic scheduling algorithm;IRM algorithm

國家科技重大專項(xiàng)(2014ZX04009031)

2016-08-03;收到修改稿時間:2016-09-05

10.15888/j.cnki.csa.005714