預測模型下模糊控制實時任務調度算法

喬 付

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

預測模型下模糊控制實時任務調度算法

喬 付

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

現有實時任務調度算法的性能指標相對比較單一,如只考慮利用率問題,忽略了任務丟失率這項關鍵性能指標.因此,本文提出同時考慮到節點的利用率和任務丟失率,使用預測信息來進一步提高系統的實時性能,在反饋控制實時系統模型中增加一個預測模型,并使用模糊控制策略實現實時任務調度.最后,通過實驗驗證所提模糊控制實時任務調度算法性能.

實時任務調度;模糊控制;預測模型

0 引 言

一個大型的應用程序通常要被劃分成多個任務并被分配到不同的計算節點上進行計算,在沒有實時任務調度算法的配合下,計算節點就會把這些任務按照到達的順序進行排隊,不會考慮有時間要求任務的計算問題.

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

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

因此,為提高實時性能在反饋控制模型中引入預測模型,給出預測模型算法,設計了PID控制器,分析了其穩定性,基于該控制器提出一種模糊控制實時任務調度算法.

1 模糊控制實時任務調度算法

1.1 預測的模糊控制實時系統模型

圖1 預測模糊控制模型

(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的個數分別是p,m,n.

根據式(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表示預測界限和控制界限.

1.2 模糊PID控制器設計

圖1虛線框內的PD+I控制器的轉移函數為：

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

(5)

從圖1設計的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控制器的轉移函數表示為：

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

(6)

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

圖2 模糊PD控制器的輸入隸屬函數

圖3 模糊PD控制器的輸出隸屬函數

圖4 模糊PD控制器的輸入組合區域

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

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

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

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

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

模糊化質心表示成如下形式：

(7)

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

因此,圖4的IC1～IC20范圍的有關模糊PD控制器的ΔuPD(nT)值可求：

同理,對于模糊I控制器,也有類似如圖2和圖3的輸入和輸出隸屬函數,可以把輸入空間分成類似如圖4 的20個組合區域,并有如下的模糊規則：

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

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

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

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

1.3 模糊PID控制器穩定性分析

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

(8)

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

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

(9)

所設計的可預測模糊PD+I控制器的輸入J的兩個目標為

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

當y=h(x)=x,h(xr)=xr時,式(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的常量,且滿足如下條件：

按照上面的條件所設計的預測控制系統是穩定的.

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

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

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

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

4) 計算Dj(r,k)的最小距離min{Dj(r,k)},求得min{Dj(r,k)}所對應的事例IOPT的參數配置模型,使用該參數配置模型預測執行事例ri的參數配置情況.

5) 在下一個采樣時間間隔,使用解決器參數配置u(k+1)來預測在給定時間上限T內的最終結果.

6) 在每個采樣時間間隔重復上述過程.

1.4 模糊控制任務調度算法描述

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

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

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

其中：NB=負大,NM=負中,NS=負小,NZ=負零,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的控制規則,采用Min-Max模型使用最大隸屬度方法求出控制決策表,將該控制決策表存儲起來,供運行時查找使用.

表1 模糊控制規則表

模糊控制實時任務調度算法(FUCRTSA：FuzzyControlReal-timeTasksSchedulingAlgorithm)步驟如下：

1)當有新的任務進入,計算當前節點的利用率和任務丟失率,并執行這個新任務.

2)當有任務退出,釋放任務所占用資源,同時計算當前節點利用率和任務丟失率.

2 實驗結果與分析

模擬實驗平臺為一臺PC機,基本參數：處理器是AMD X2 240、內存是4GB, Windows 10操作系統.比較本文所提出的FUCRTSA算法與文獻[5,20]算法的性能,文獻[5]提出的模糊反饋控制調度算法沒有使用預測信息,并且該算法只側重于利用率,沒有關注任務丟失率問題.

實驗中選擇了計算節點利用率和任務丟失率作為衡量指標,圖6為運行三個算法的計算節點利用率比較,圖7為運行三個算法的任務丟失率比較.在實驗中,有足夠多的任務供系統去執行,預測利用率為80%,任務丟失率為2%.從圖6中可以看出,三個算法在取得計算節點利用率達到穩定的時間有很大區別,使用FUCRTSA算法在19秒時開始使得利用率達到了90%,使用文獻[20]算法在24秒時開始使得利用率達到了90%,使用文獻[5]算法在28秒時開始使得利用率達到了90%.另外,在0-5秒時,文獻[5]算法所取得的利用率變化不大,而其它兩個算法取得的利用變化較大.

圖6 使用三個算法的計算節點利用率比較

從圖7中可以看出,三個算法幾乎在同一時間得到穩定的任務丟失率狀態,但使用FUCRTSA算法所取得的任務丟失率維持在1%左右,使用文獻[20]算法所取得的任務丟失率維持在1.8%左右,使用文獻[5]算法所取得的任務丟失率維持在2%左右.

綜合上述實驗結果,在計算節點利用率和任務丟失率上FUCRTSA算法要好于文獻[20]算法和文獻[5]算法.這是由于文獻[20]算法和FUCRTSA算法都是用了閉環控制,而文獻[5]算法使用的是開環控制的結果,而且FUCRTSA算法中使用了預測信息來處理反饋信息,使得FUCRTSA算法性能要好于文獻[20]算法.

圖7 使用三個算法的任務丟失率比較

3 結論

解決了網格計算中實時任務調度問題,考慮到預測信息可以提高實時性,在反饋控制模型中引入了預測模型,設計了模糊PID控制器,并分析其穩定性,提出了模糊控制實時任務調度FUCRTSA算法.實驗表明：在利用率和任務丟失率兩個性能指標上FUCRTSA算法優于文獻[20]和文獻[5]中算法,而文獻[20]中算法又優于文獻[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]殷月竹,殷志祥,許鋒,等.單輸入時滯離散系統的LQR問題[J].合肥工業大學學報(自然科學版),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]黃麗達,李仁發.截止時限為關鍵參數的混合關鍵級實時任務調度研究[J].計算機研究與發展, 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]金宏,王宏安,傅勇,等.模糊反饋控制實時調度算法[J].軟件學報,2004,15(6):791-798.

[20]喬付.具有模糊多目標網格任務調度算法[J].計算機工程與科學,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

格式：喬付.預測模型下模糊控制實時任務調度算法[J].海南熱帶海洋學院學報,2017，24(2)：47-54.

2016-10-07

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

TP393.028

A

2096-3122(2017) 02-0047-08

10.13307/j.issn.2096-3122.2017.02.10