王得利

（唐山市人才交流中心，河北 唐山 063000）

1 引言

實(shí)時(shí)控制系統(tǒng)是運(yùn)行于計(jì)算機(jī)系統(tǒng)上，主要完成數(shù)據(jù)采集、控制計(jì)算、控制輸出及報(bào)警等功能實(shí)時(shí)系統(tǒng)。為了充分利用處理器資源，減少系統(tǒng)的軟硬件投資，往往在一個(gè)處理器上處理多個(gè)回路。而系統(tǒng)中的任務(wù)必須在一定的時(shí)間內(nèi)完成，否則會(huì)出現(xiàn)災(zāi)難性后果[1]，這就涉及了實(shí)時(shí)多任務(wù)的調(diào)度問(wèn)題。

針對(duì)實(shí)時(shí)任務(wù)的調(diào)度算法，Liu和 Layland[2]給出了著名的RMS算法和EDF算法，這兩種算法都是針對(duì)周期性任務(wù)的調(diào)度算法。然而控制系統(tǒng)的性能與控制系統(tǒng)的采樣周期有關(guān)[3－4]，因此出現(xiàn)了結(jié)合對(duì)系統(tǒng)性能進(jìn)行優(yōu)化的調(diào)度算法。文獻(xiàn)[4]給出了計(jì)算優(yōu)化采樣頻率的方法；文獻(xiàn)[5]給出了使系統(tǒng)性能優(yōu)化的動(dòng)態(tài)調(diào)度算法。但是這些優(yōu)化調(diào)度算法過(guò)于復(fù)雜。因此本文基于PSO算法設(shè)計(jì)控制系統(tǒng)的優(yōu)化調(diào)度算法。

2 任務(wù)模型

典型的數(shù)字控制系統(tǒng)如圖1所示。實(shí)際上這只是一個(gè)控制回路，根據(jù)系統(tǒng)的需要它將完成多種功能，各功能之間既相互聯(lián)系、相互影響又相互獨(dú)立，因此可以看作一個(gè)任務(wù)，這是一個(gè)周期性任務(wù)。另外系統(tǒng)的采樣周期并非固定不變的，在保證控制回路穩(wěn)定的前提下，根據(jù)系統(tǒng)的動(dòng)態(tài)、靜態(tài)性能指標(biāo)要求以及對(duì)象的數(shù)學(xué)模型可以確定回路的采樣周期[6]，這是采樣周期最大值，記為，而為了保證系統(tǒng)的正常運(yùn)行，系統(tǒng)的采樣周期存在最小值（如必須大于該控制回路的采樣、控制計(jì)算和控制輸出的執(zhí)行時(shí)間），記為。

在控制系統(tǒng)中，一般來(lái)說(shuō)當(dāng)控制算法、數(shù)據(jù)采集和控制輸出的方法確定后各任務(wù)的執(zhí)行時(shí)間是確定的。

圖1 實(shí)時(shí)控制系統(tǒng)的結(jié)構(gòu)

基于以上分析，我們給出控制系統(tǒng)的周期性任務(wù)模型如下：

定義1一個(gè)控制系統(tǒng)中的任務(wù)集可表示為

其中n≥1，iτ為一個(gè)回路任務(wù)，可表示為如下的形式

控制系統(tǒng)中除了回路任務(wù)外，還存在諸如報(bào)警等非周期任務(wù)。這類任務(wù)只要在一定的時(shí)間內(nèi)調(diào)度完成即可，故可通過(guò)給非周期任務(wù)預(yù)留一定的處理器資源來(lái)實(shí)現(xiàn)對(duì)其調(diào)度，如采用帶非周期服務(wù)器的調(diào)度算法[1]，因此本文主要研究回路任務(wù)的優(yōu)化調(diào)度算法。

定義2若所有回路任務(wù)的所有實(shí)例都能在其時(shí)限之前完成，則稱任務(wù)集S是可調(diào)度的。

為了分析合設(shè)計(jì)調(diào)度算法的方便，本文做如下假設(shè)：

（1）回路任務(wù)之間相互獨(dú)立，回路任務(wù)時(shí)限等于周期；

（2）所有的任務(wù)在同一處理器上完成。

3 調(diào)度算法及優(yōu)化

由任務(wù)模型可知，控制系統(tǒng)中的任務(wù)均為周期性任務(wù)，故可采用 Liu和 Layland[2]給出了著名速率單調(diào)調(diào)度算法（RMS）和最早截止期優(yōu)先調(diào)度算法（EDF），考慮到EDF可以獲得更高的處理器利用率，本文采用搶占式 EDF調(diào)度算法。由文獻(xiàn)[2]可知，EDF調(diào)度算法的可調(diào)度條件如下：

引理1對(duì)于周期性任務(wù)集，采用搶占式EDF算法，當(dāng)且僅當(dāng)

時(shí)，任務(wù)集是可調(diào)度的。

根據(jù)Seto[4]的研究，控制系統(tǒng)的性能與采樣周期和控制延遲有關(guān)，它們與控制系統(tǒng)的二次性能指標(biāo)存在如下關(guān)系：

式中 ci, ai常數(shù)，可通過(guò)控制算法曲線獲得。由文獻(xiàn)[4]可知，Ji越小系統(tǒng)性能越好。由于各控制回路重要性不盡相同，結(jié)合前面任務(wù)的可調(diào)度性和采樣周期的取值范圍，則優(yōu)化問(wèn)題為：

約束條件：

當(dāng)前的優(yōu)化調(diào)度算法[3-5]過(guò)于復(fù)雜，本文基于優(yōu)化搜索算法尋求最佳的采樣周期。搜索算法中 PSO是一種源于對(duì)鳥群捕食行為的優(yōu)化迭代算法，該算沒(méi)有遺傳算法中的采用交叉和變異操作，沒(méi)有許多參數(shù)需要調(diào)整，因而實(shí)現(xiàn)簡(jiǎn)單。為去掉(5)式中的第一個(gè)不等式約束條件，采用懲罰函數(shù)法[7]，并通過(guò)準(zhǔn)精確懲罰函數(shù)，使得優(yōu)化問(wèn)題變?yōu)椋?/p>

式中M為正常數(shù)，用于調(diào)整對(duì)不合法個(gè)體的懲罰程度，則約束條件化為

粒子群算法將每個(gè)個(gè)體視為在n維搜索空間中，以一定速度飛行的沒(méi)有質(zhì)量和體積的粒子。每個(gè)粒子的飛行速度據(jù)其本身的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行調(diào)整。假設(shè)在n維目標(biāo)搜索空間中，有m個(gè)粒子組成一個(gè)群落，其中第i個(gè)粒子表示為。在n維搜索空間中的位置為Ti，每個(gè)粒子的位置代表一個(gè)潛在的解。第i個(gè)粒子的飛行速度為n維向量，記為。記第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為，對(duì)應(yīng)的適應(yīng)值為pBest，整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為，對(duì)應(yīng)的適應(yīng)值為gBest。每個(gè)粒子的速度和位置按方程(8)和(9)進(jìn)行迭代

式中 j,t均為1,...,n，t為迭代次數(shù)；ω為慣性權(quán)重，ω≥0；c1,c2為學(xué)習(xí)因子，也稱加速因子。這兩個(gè)參數(shù)對(duì)粒子群算法的收斂起的作用不是很大，但如果適當(dāng)調(diào)整這兩個(gè)參數(shù)，可以減少局部最小值的困擾，當(dāng)然也會(huì)使收斂速度變快。為粒子i目前位置到粒子i迄今為止搜索到的最優(yōu)位置在第j維上的距離；為粒子i目前位置到整個(gè)粒子群迄今為止搜索到的最優(yōu)位置在第j維上的距離。

4 調(diào)度算法的仿真

為了驗(yàn)證前述方法的有效性，我們進(jìn)行如下仿真，來(lái)考察對(duì)回路任務(wù)采樣周期的優(yōu)化情況。每個(gè)任務(wù)的最大采樣周期在800到1000之間隨機(jī)生成；每個(gè)任務(wù)的最小采樣周期取為該任務(wù)最大采樣周期的0.6倍；每個(gè)任務(wù)的權(quán)重是在0到1之間歸一化生成的隨機(jī)數(shù)；每個(gè)任務(wù)的執(zhí)行時(shí)間在0到0.1倍的最大采樣周期之間隨機(jī)生成。按照上述任務(wù)參數(shù)生成方式，隨機(jī)生成10個(gè)回路任務(wù)，任務(wù)參數(shù)如表1所示。

表1 控制系統(tǒng)回路任務(wù)參數(shù)

利用粒子群優(yōu)化算法，采用前述算法流程，對(duì)上述 10個(gè)周期性任務(wù)的采樣周期進(jìn)行優(yōu)化。設(shè)該粒子群中有粒子80個(gè)，共進(jìn)行250次迭代。仿真后所得結(jié)果如表2和圖2所示。利用 PSO算法，優(yōu)化搜索了各個(gè)回路任務(wù)的最優(yōu)采樣周期。

表2 單處理器控制系統(tǒng)仿真結(jié)果

圖2 控制系統(tǒng)平均目標(biāo)函數(shù)和迭代次數(shù)之間的關(guān)系

利用表2的數(shù)據(jù)，根據(jù)處理器利用率計(jì)算公式

對(duì)單處理器的利用率進(jìn)行計(jì)算，處理器的利用率為 0.999 991。該處理器的利用率非常接近于 1，表明采用本文所提出的單處理器控制系統(tǒng)的任務(wù)調(diào)度策略和回路任務(wù)采樣周期優(yōu)化方法，在滿足所有回路任務(wù)均可調(diào)度這一前提下，系統(tǒng)計(jì)算資源的利用率很高。

同時(shí)，由圖2可見，盡管最終進(jìn)行了250次迭代，在第50次迭代時(shí)，平均目標(biāo)函數(shù)值就已從約120收斂至約20左右，可見收斂速度快，運(yùn)算效率之高。采用粒子群優(yōu)化搜索算法，平均目標(biāo)函數(shù)值從第0次迭代的120.9945被優(yōu)化至第250次迭代的20.74327，優(yōu)化幅度約為82.856%，優(yōu)化效果顯著。

5 結(jié)論

研究了控制系統(tǒng)中周期性任務(wù)，分析任務(wù)特性，給出了任務(wù)模型。為了提高處理器資源利用率，采用了 EDF調(diào)度算法?；诖?，采用 PSO算法給出了控制任務(wù)采樣周期的優(yōu)化求取算法。仿真實(shí)驗(yàn)表明，本文給出的基于PSO的控制任務(wù)優(yōu)化調(diào)度算法是有效的。