喬 付

(海南熱帶海洋學(xué)院 海洋信息工程學(xué)院,海南 三亞 572022)

預(yù)測(cè)模型下模糊控制實(shí)時(shí)任務(wù)調(diào)度算法

喬 付

(海南熱帶海洋學(xué)院 海洋信息工程學(xué)院,海南 三亞 572022)

現(xiàn)有實(shí)時(shí)任務(wù)調(diào)度算法的性能指標(biāo)相對(duì)比較單一,如只考慮利用率問題,忽略了任務(wù)丟失率這項(xiàng)關(guān)鍵性能指標(biāo).因此,本文提出同時(shí)考慮到節(jié)點(diǎn)的利用率和任務(wù)丟失率,使用預(yù)測(cè)信息來進(jìn)一步提高系統(tǒng)的實(shí)時(shí)性能,在反饋控制實(shí)時(shí)系統(tǒng)模型中增加一個(gè)預(yù)測(cè)模型,并使用模糊控制策略實(shí)現(xiàn)實(shí)時(shí)任務(wù)調(diào)度.最后,通過實(shí)驗(yàn)驗(yàn)證所提模糊控制實(shí)時(shí)任務(wù)調(diào)度算法性能.

實(shí)時(shí)任務(wù)調(diào)度;模糊控制;預(yù)測(cè)模型

0 引 言

一個(gè)大型的應(yīng)用程序通常要被劃分成多個(gè)任務(wù)并被分配到不同的計(jì)算節(jié)點(diǎn)上進(jìn)行計(jì)算,在沒有實(shí)時(shí)任務(wù)調(diào)度算法的配合下,計(jì)算節(jié)點(diǎn)就會(huì)把這些任務(wù)按照到達(dá)的順序進(jìn)行排隊(duì),不會(huì)考慮有時(shí)間要求任務(wù)的計(jì)算問題.

實(shí)時(shí)任務(wù)調(diào)度算法分為靜態(tài)和動(dòng)態(tài)實(shí)時(shí)任務(wù)調(diào)度算法兩種[1-5].靜態(tài)實(shí)時(shí)任務(wù)調(diào)度算實(shí)現(xiàn)已知任務(wù)集和它的約束,如截止期限[6]等.RM(Rate Monotonic)算法是靜態(tài)實(shí)時(shí)任務(wù)調(diào)度的代表算法;而動(dòng)態(tài)實(shí)時(shí)任務(wù)調(diào)度算法不知道具體的任務(wù)集和相關(guān)的約束,例如,有新的任務(wù)加入時(shí),動(dòng)態(tài)實(shí)時(shí)任務(wù)調(diào)度算法不知道當(dāng)前正在調(diào)度的具體任務(wù),也不知道任務(wù)的具體完成時(shí)間.

多數(shù)調(diào)度理論和算法都是基于周期任務(wù)模型或隨機(jī)任務(wù)模型[7-8],且都是從任務(wù)級(jí)角度研究其調(diào)度問題,也有從功能級(jí)模型研究任務(wù)間的調(diào)度問題,但僅限于簡(jiǎn)單的分布式功能[9-12].文獻(xiàn)[2]提出一種類似RM算法的靜態(tài)實(shí)時(shí)任務(wù)調(diào)度算法,該算法對(duì)現(xiàn)有已知任務(wù)的約束要求嚴(yán)格.文獻(xiàn)[3]所述動(dòng)態(tài)實(shí)時(shí)任務(wù)調(diào)度算法的典型代表算法是EDF算法,但是該算法在資源不足時(shí)表現(xiàn)出來的性能欠佳.上述算法均屬于開環(huán)調(diào)度算法,不適合在反饋控制調(diào)節(jié)系統(tǒng)中應(yīng)用.傳統(tǒng)的控制系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的方法是把控制和調(diào)度分開的,不能確保提供控制質(zhì)量,從資源調(diào)度的角度看,應(yīng)用到實(shí)時(shí)調(diào)度的開環(huán)實(shí)時(shí)調(diào)度算法缺乏靈活性,如文獻(xiàn)[13]提出的開環(huán)控制調(diào)度算法;文獻(xiàn)[14]提出按照最大偏差的任務(wù)優(yōu)先策略對(duì)任務(wù)進(jìn)行調(diào)度,其需要不斷地執(zhí)行排序算法,使系統(tǒng)算法的復(fù)雜度增加;文獻(xiàn)[15]提出了適合小規(guī)模的實(shí)時(shí)任務(wù)調(diào)度算法;文獻(xiàn)[16]提出一種反饋實(shí)時(shí)控制任務(wù)的調(diào)度架構(gòu),使用反饋信息調(diào)節(jié)負(fù)載,優(yōu)化整體性能,其缺點(diǎn)是采樣時(shí)間間隔過于精確,使得系統(tǒng)不好控制;文獻(xiàn)[17]側(cè)重按照控制應(yīng)用程序的動(dòng)態(tài)性,使用新的調(diào)度策略來控制系統(tǒng)性能;文獻(xiàn)[18]的預(yù)測(cè)模型不是在時(shí)間約束下考慮的模型;文獻(xiàn)[19]提出一種模糊實(shí)時(shí)任務(wù)調(diào)度算法,該算法適合在不可預(yù)測(cè)情況下的實(shí)時(shí)任務(wù)調(diào)度,也就不能使用預(yù)測(cè)信息來調(diào)節(jié)反饋控制器;文獻(xiàn)[5]提出的模糊反饋控制調(diào)度算法同樣也忽略了使用預(yù)測(cè)信息,并且該算法只側(cè)重于利用率,沒有關(guān)注任務(wù)丟失率問題;文獻(xiàn)[20]雖然考慮了任務(wù)丟失率問題,但其也是沒有使用預(yù)測(cè)信息.

因此,為提高實(shí)時(shí)性能在反饋控制模型中引入預(yù)測(cè)模型,給出預(yù)測(cè)模型算法,設(shè)計(jì)了PID控制器,分析了其穩(wěn)定性,基于該控制器提出一種模糊控制實(shí)時(shí)任務(wù)調(diào)度算法.

1 模糊控制實(shí)時(shí)任務(wù)調(diào)度算法

1.1 預(yù)測(cè)的模糊控制實(shí)時(shí)系統(tǒng)模型

圖1 預(yù)測(cè)模糊控制模型

(1+a1x-1+a2x-2+…+anx-n)y(nT)=(b1+b2x-1+…+bmx-m+1u(nT)+(c0)+c1x-1+…+cpx-p)ξ(nT)+d,

(1)

其中：n(nT)是控制器的輸出;y(nT)是處理后輸出;d是偏移量,ξ(nT)是噪聲.

不失一般性,令d=0,ξ(nT)=0.為方便,把式(1)寫成如下形式：

Ap×(m+n)X(n+m)×1=Yp×1，

(2)

其中：y,bi,ai的個(gè)數(shù)分別是p,m,n.

根據(jù)式(2),X(n+m)×1有如下三種表示方法：

(3)

不妨定義J為下面的形式：

(4)

其中:e(nT-iT)=r(nT-iT)-y(nT-iT)表示r(nT-iT)與y(nT-iT)之間的誤差;Δu(nT-jT)表示輸出增量;h1,h2表示預(yù)測(cè)界限和控制界限.

1.2 模糊PID控制器設(shè)計(jì)

圖1虛線框內(nèi)的PD+I控制器的轉(zhuǎn)移函數(shù)為：

UPID(S)=UPD(s)+U1(S),

(5)

從圖1設(shè)計(jì)的PD+I控制器,可知：

還可以推出：

ΔUPD(nT)=Kp*d(nT)+KD*r(nT),ΔUI(nT)=K1*r(nT)+K1*e(nT-T),

UPD(nT)=-UPD(nT-T)+KUPD*ΔUPD(nT),U1(nT)=U1(nT-T)+KU1*ΔU1(nT),

圖1中的PD+I控制器的轉(zhuǎn)移函數(shù)表示為：

UPID(nT)=UPD(nT)+UI(nT).

(6)

對(duì)于模糊化PD控制器過程,圖2和圖3分別為輸入和輸出的隸屬函數(shù),可以把輸入空間分成如圖4的20個(gè)組合區(qū)域,PD控制器使用下面的四個(gè)模糊控制規(guī)則：

圖2 模糊PD控制器的輸入隸屬函數(shù)

圖3 模糊PD控制器的輸出隸屬函數(shù)

圖4 模糊PD控制器的輸入組合區(qū)域

規(guī)則1：IFd=d.nANDr=r.nThenPD-output=o.p,

規(guī)則2：IFd=d.nANDr=r.nThenPD-output=o.n,

規(guī)則3：IFd=d.pANDr=r.nThenPD-output=o.p,

規(guī)則4：IFd=d.pANDr=r.pThenPD-output=o.z,

其中:d.p表示正誤差,d.n表示負(fù)誤差,r.p表示正誤差率,r.n表示負(fù)誤差率,o.p和o.n分別表示正負(fù)輸出,o.z表示零輸出,AND是扎德模糊算子.

模糊化質(zhì)心表示成如下形式：

(7)

應(yīng)用輸出隸屬度值o.p=L,o.n=-L,o.z=0和圖4中的直線方程可以得到：

因此,圖4的IC1～I(xiàn)C20范圍的有關(guān)模糊PD控制器的ΔuPD(nT)值可求：

同理,對(duì)于模糊I控制器,也有類似如圖2和圖3的輸入和輸出隸屬函數(shù),可以把輸入空間分成類似如圖4 的20個(gè)組合區(qū)域,并有如下的模糊規(guī)則：

規(guī)則5：IFe(nT-T)=e.nANDr=r.nThenI-output=o.n,

規(guī)則6：IFe(nT-T)=e.nANDr=r.pThenI-output=o.z,

規(guī)則7：IFe(nT-T)=e.pANDr=r.nThenI-output=o.z,

規(guī)則8：IFe(nT-T)=e.pANDr=r.pThenI-output=o.p.

1.3 模糊PID控制器穩(wěn)定性分析

分析控制器的穩(wěn)定性方法很多,這里采用Lyapunov’s第二方法[13]來分析所設(shè)計(jì)的PD+I控制器.按照Lyapunov’s第二方法,該控制器可以表示為：

(8)

其中：x是狀態(tài)向量,θ是干擾,u是控制器,y系統(tǒng)輸入,f(x),F(x),g(x),h(x)是非線性函數(shù).

式(8)要保持如下的參考系統(tǒng)：

(9)

所設(shè)計(jì)的可預(yù)測(cè)模糊PD+I控制器的輸入J的兩個(gè)目標(biāo)為

J(nT)的誤差：eJ(nT)=J(nT)-Jr(nT);

當(dāng)y=h(x)=x,h(xr)=xr時(shí),式(8)減去式(9)可得：

e=y-yr=x-xr,

(10)

可令ef=f(x)-fr(xr),eF=F(x)-Fr(xr),則有：

(11)

?α1,α2,α4,α5,α6,α7,β1,β2,β3,β4,β5<0的常量,且滿足如下條件：

按照上面的條件所設(shè)計(jì)的預(yù)測(cè)控制系統(tǒng)是穩(wěn)定的.

該預(yù)測(cè)模型的建模架構(gòu)如圖5所示,選擇控制參數(shù)U={u1,u2,…，uN}用來定義每一個(gè)解決器,對(duì)應(yīng)的參考輸入R=(r1,r2,…，rM),即為給定的問題事例,f1,f2,…，fN為可供選擇的N個(gè)不同配置的模型.模型fi使用動(dòng)態(tài)的信息y(k)預(yù)測(cè)R={r1,r2,…，rM}的最好參數(shù).例如,在第一個(gè)采樣間隔里選擇了u1∈U,如果預(yù)測(cè)可以得到較好的參數(shù)性能,則可繼續(xù)切換到u2,u3,…，uN∈U.從一個(gè)參數(shù)的配置模型切換到另一個(gè)參數(shù)的配置模型,當(dāng)從u1到u2切換時(shí),u1的處理暫停并保留現(xiàn)場(chǎng),恢復(fù)u2的處理現(xiàn)場(chǎng).該預(yù)測(cè)模型還要滿足兩個(gè)條件,第一,可以使用建模后事例的解決器性能參數(shù)預(yù)測(cè)新的事例性能參數(shù);第二,如果在兩個(gè)事例所使用的解決器相同,那么該解決器可以用來繼續(xù)執(zhí)行這兩個(gè)事例的其它處理操作.

基于這兩個(gè)條件,可以按如下步驟描述出該預(yù)測(cè)模型算法PMA(PredictionModelAlgorithm)：

1) 初始化時(shí)為每一個(gè)由參數(shù)配置μ1∈U的解決器給定時(shí)間上限T.

2) 由每一個(gè)解決器記錄每一個(gè)采樣間隔的優(yōu)化參數(shù)配置情況,yij(k)表示第j個(gè)事例rj的第k個(gè)采樣間隔的第i個(gè)解決器所得到的優(yōu)化參數(shù)方案,此過程沒有發(fā)生切換.

4) 計(jì)算Dj(r,k)的最小距離min{Dj(r,k)},求得min{Dj(r,k)}所對(duì)應(yīng)的事例IOPT的參數(shù)配置模型,使用該參數(shù)配置模型預(yù)測(cè)執(zhí)行事例ri的參數(shù)配置情況.

5) 在下一個(gè)采樣時(shí)間間隔,使用解決器參數(shù)配置u(k+1)來預(yù)測(cè)在給定時(shí)間上限T內(nèi)的最終結(jié)果.

6) 在每個(gè)采樣時(shí)間間隔重復(fù)上述過程.

1.4 模糊控制任務(wù)調(diào)度算法描述

不妨取誤差E、誤差變化率ECR和控制輸入U(xiǎn)的模糊集合分別為

E={NB,NM,NS,NZ,PZ,PS,PM,PB},

U={NB，NM，NS，ZE，PS，PM，PB},

其中：NB=負(fù)大,NM=負(fù)中,NS=負(fù)小,NZ=負(fù)零,PZ=正零,ZE=零,PS=正小,PM=正中,PB=正大.

e={-6,-5,-4,-3,-2,-1,-0,+0,+1,+2,+3,+4,+5,+6},

u={-7,-6,-5,-4,-3,-2,-1,0,+1,+2,+3,+4,+5,+6,+7}.

使用表1的控制規(guī)則,采用Min-Max模型使用最大隸屬度方法求出控制決策表,將該控制決策表存儲(chǔ)起來,供運(yùn)行時(shí)查找使用.

表1 模糊控制規(guī)則表

模糊控制實(shí)時(shí)任務(wù)調(diào)度算法(FUCRTSA：FuzzyControlReal-timeTasksSchedulingAlgorithm)步驟如下：

1)當(dāng)有新的任務(wù)進(jìn)入,計(jì)算當(dāng)前節(jié)點(diǎn)的利用率和任務(wù)丟失率,并執(zhí)行這個(gè)新任務(wù).

2)當(dāng)有任務(wù)退出,釋放任務(wù)所占用資源,同時(shí)計(jì)算當(dāng)前節(jié)點(diǎn)利用率和任務(wù)丟失率.

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

模擬實(shí)驗(yàn)平臺(tái)為一臺(tái)PC機(jī),基本參數(shù)：處理器是AMD X2 240、內(nèi)存是4GB, Windows 10操作系統(tǒng).比較本文所提出的FUCRTSA算法與文獻(xiàn)[5,20]算法的性能,文獻(xiàn)[5]提出的模糊反饋控制調(diào)度算法沒有使用預(yù)測(cè)信息,并且該算法只側(cè)重于利用率,沒有關(guān)注任務(wù)丟失率問題.

實(shí)驗(yàn)中選擇了計(jì)算節(jié)點(diǎn)利用率和任務(wù)丟失率作為衡量指標(biāo),圖6為運(yùn)行三個(gè)算法的計(jì)算節(jié)點(diǎn)利用率比較,圖7為運(yùn)行三個(gè)算法的任務(wù)丟失率比較.在實(shí)驗(yàn)中,有足夠多的任務(wù)供系統(tǒng)去執(zhí)行,預(yù)測(cè)利用率為80%,任務(wù)丟失率為2%.從圖6中可以看出,三個(gè)算法在取得計(jì)算節(jié)點(diǎn)利用率達(dá)到穩(wěn)定的時(shí)間有很大區(qū)別,使用FUCRTSA算法在19秒時(shí)開始使得利用率達(dá)到了90%,使用文獻(xiàn)[20]算法在24秒時(shí)開始使得利用率達(dá)到了90%,使用文獻(xiàn)[5]算法在28秒時(shí)開始使得利用率達(dá)到了90%.另外,在0-5秒時(shí),文獻(xiàn)[5]算法所取得的利用率變化不大,而其它兩個(gè)算法取得的利用變化較大.

圖6 使用三個(gè)算法的計(jì)算節(jié)點(diǎn)利用率比較

從圖7中可以看出,三個(gè)算法幾乎在同一時(shí)間得到穩(wěn)定的任務(wù)丟失率狀態(tài),但使用FUCRTSA算法所取得的任務(wù)丟失率維持在1%左右,使用文獻(xiàn)[20]算法所取得的任務(wù)丟失率維持在1.8%左右,使用文獻(xiàn)[5]算法所取得的任務(wù)丟失率維持在2%左右.

綜合上述實(shí)驗(yàn)結(jié)果,在計(jì)算節(jié)點(diǎn)利用率和任務(wù)丟失率上FUCRTSA算法要好于文獻(xiàn)[20]算法和文獻(xiàn)[5]算法.這是由于文獻(xiàn)[20]算法和FUCRTSA算法都是用了閉環(huán)控制,而文獻(xiàn)[5]算法使用的是開環(huán)控制的結(jié)果,而且FUCRTSA算法中使用了預(yù)測(cè)信息來處理反饋信息,使得FUCRTSA算法性能要好于文獻(xiàn)[20]算法.

圖7 使用三個(gè)算法的任務(wù)丟失率比較

3 結(jié)論

解決了網(wǎng)格計(jì)算中實(shí)時(shí)任務(wù)調(diào)度問題,考慮到預(yù)測(cè)信息可以提高實(shí)時(shí)性,在反饋控制模型中引入了預(yù)測(cè)模型,設(shè)計(jì)了模糊PID控制器,并分析其穩(wěn)定性,提出了模糊控制實(shí)時(shí)任務(wù)調(diào)度FUCRTSA算法.實(shí)驗(yàn)表明：在利用率和任務(wù)丟失率兩個(gè)性能指標(biāo)上FUCRTSA算法優(yōu)于文獻(xiàn)[20]和文獻(xiàn)[5]中算法,而文獻(xiàn)[20]中算法又優(yōu)于文獻(xiàn)[5]中算法.

[1]Park SM, Humphrey M.Feedback-controlled resource sharing for predictable eScience[C]//Proc of the 2008 ACM/IEEE conference on supercomputing.New York:IEEE press, 2008:15-21.

[2]Ayav T, Sorel Y.Feedback control static scheduling for real-time distributed embedded systems[C]//Proc of the 11th IEEE IntConf on Embedded and Real-Time Computing Systems and Applications.New York:IEEE press, 2005:173-176.

[3]Baker T P.An analysis of EDF schedulability on a multiprocessor[J].IEEE transactions on parallel and distributed systems, 2005, 16(8):760-768.

[4]殷月竹,殷志祥,許鋒,等.單輸入時(shí)滯離散系統(tǒng)的LQR問題[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2008, 31(12):2072-2076.

[5]Xia F.Feedback scheduling of real-time control systems with resource constraints [J].JCS&T,2007, 7(3):263-267.

[6]黃麗達(dá),李仁發(fā).截止時(shí)限為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)實(shí)時(shí)任務(wù)調(diào)度研究[J].計(jì)算機(jī)研究與發(fā)展, 2016, 53(7): 1641-1647.

[7]Lakshmanan K,De Niz D, Rajkumar R.Mixed-criticality task synchronization in zero-slack scheduling[C]//Proc of IEEE Real-Time and Embedded Technology and Applications Symp.New York:IEEE press, 2011:47-56.

[8]Dorin F, Richard P, Richard M, et al.Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities[J].Real-Time Systems, 2010, 6(3):305-331.

[9]Zeller M, Prehofer C, Weiss G, et al.Towards self-adaptation in real-time, networked systems:Efficient solving of system constraints for automotive embedded systems[C]//Proc of IntConf Self-Adaptive and Self-Organizing Systems.New York:IEEE press, 2010:79-88.

[10]Katoen J P, Noll T, Wu H, et al.Model-based energy optimization of automotive control systems[C]//Proc of the Conf on Design, Automation and Test in Europe.New York:IEEE press, 2013:761-766.

[11]Hernrich P, Prehofer C.Network-wide energy optimization for adaptive embedded systems[J].ACM SIGBED Review, 2013,10(1):33-36.

[12]Xie G, Li R, Xiao X, et al.A high-performance dag task scheduling algorithm for heterogeneous networked embedded systems[C]//Proc of IEEE IntConf on Advanced Information Networking and Applications.New York:IEEE press,2014:1011-1016.

[13]Sahoo D R,Swaminathan S, et al.Feedback control for real-time scheduling[C]// Proceedings of the 2002 American Control Conference.New York:IEEE press, 2002: 1254-1259.

[14]Yepez J, Josep M.Fuertes, Pau Marti.The large error first (LEF) scheduling policy for real-time control systems[EB/OL].(2009-11-9)[2016-11-5].http://dcs.upc.edu/uploads/publications/f1fd9a72bb792dcd7a23b159c4dca8bb.pdf.

[15]Ying L, Crawford S L, Wheeler Ruml, et al.Feedback control for real-time solving[C]//Proceedings of CP2004 workshop.NewYork:IEEE press,2004, 9:1-15.

[16]CervinA,Eker J, Bernhardsson B, et al.Feedback-Feedforward Scheduling of Control Tasks[J].Real-Time Systems, 2002, 23(1):1-15.

[17]Marti P, Fohler G, Ramamritham K, et al.Improving quality-of-control usingflexible timing constraints: metric and scheduling[C]//Proceedings of Real-Time Systems Symposium.New York:IEEE press, 2002: 91-100.

[18]Nudelman E, Devkar A, Shoham Y, et al.Understanding random SAT: beyond the clauses-to-variables ratio[C]// Proceedings of constraint programming.New York:IEEE press2004:438-452.

[19]金宏,王宏安,傅勇,等.模糊反饋控制實(shí)時(shí)調(diào)度算法[J].軟件學(xué)報(bào),2004,15(6):791-798.

[20]喬付.具有模糊多目標(biāo)網(wǎng)格任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與科學(xué),2013,36(9):1644-1649.

(編校：曾福庚)

Fuzzy Control Real-Time TasksScheduling Algorithm Based on Prediction Model

QIAO Fu

(School of Ocean Information Engineering, Hainan Tropical Ocean University, Sanya Hainan 572022,China)

The performance indices are relatively single in existing real-time tasks scheduling algorithms.For instance, if only the utilization rate is considered, the tasks loss rate that is a key performance index is ignored.Therefore in this paper the utilization rate and loss rate were considered simultaneously, and the real-time performance of the system was improved by the use of the prediction information.Moreover, a prediction model was added to the feedback control real time system model, and fuzzy control strategy was used for real-time tasks scheduling.Finally, the performance of the proposed fuzzy control real-time tasks scheduling algorithm was verified by the experiments.

real-time scheduling; fuzzy control; prediction model

格式：?jiǎn)谈?預(yù)測(cè)模型下模糊控制實(shí)時(shí)任務(wù)調(diào)度算法[J].海南熱帶海洋學(xué)院學(xué)報(bào),2017，24(2)：47-54.

2016-10-07

喬付(1975-)，男，黑龍江依安人，海南熱帶海洋學(xué)院海洋信息工程學(xué)院副教授，博士，主要研究方向計(jì)算機(jī)視覺和并行計(jì)算.

TP393.028

A

2096-3122(2017) 02-0047-08

10.13307/j.issn.2096-3122.2017.02.10