應(yīng)用混合粒子群優(yōu)化的檢查點(diǎn)全局優(yōu)化算法

門朝光，何忠政，陳擁軍，李 香，蔣慶豐

（1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱；2.中國新興建設(shè)開發(fā)總公司，100143北京）

應(yīng)用混合粒子群優(yōu)化的檢查點(diǎn)全局優(yōu)化算法

門朝光1，何忠政1，陳擁軍2，李 香1，蔣慶豐1

（1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱；2.中國新興建設(shè)開發(fā)總公司，100143北京）

針對容錯(cuò)實(shí)時(shí)系統(tǒng)存在的局部最優(yōu)檢查點(diǎn)間隔為單次故障情況下的最優(yōu)檢查點(diǎn)間隔及局部最優(yōu)檢查點(diǎn)間隔并不是任務(wù)集全局最優(yōu)檢查點(diǎn)間隔的缺陷，首先給出檢查點(diǎn)間隔全局優(yōu)化問題的多目標(biāo)優(yōu)化模型，然后基于混合粒子群優(yōu)化算法，提出檢查點(diǎn)間隔全局優(yōu)化算法.該算法通過混合粒子群優(yōu)化算法的交叉和變異操作，避免算法陷入局部極值的困境，且增強(qiáng)了算法搜索全局近優(yōu)檢查點(diǎn)間隔的能力.實(shí)驗(yàn)表明，與其他檢查點(diǎn)間隔優(yōu)化算法相比，本算法可進(jìn)一步提升系統(tǒng)容錯(cuò)能力.檢查點(diǎn)間隔全局優(yōu)化能在故障多次發(fā)生情況下，對任務(wù)集的檢查點(diǎn)間隔進(jìn)行全局搜索，以減小檢查點(diǎn)設(shè)置次數(shù)和故障檢測次數(shù)、高優(yōu)先級(jí)任務(wù)搶占時(shí)間及故障恢復(fù)時(shí)間，提高系統(tǒng)可調(diào)度性.

實(shí)時(shí)系統(tǒng)；檢查點(diǎn)間隔；容錯(cuò)調(diào)度；粒子群優(yōu)化

在航空航天、軍事等多個(gè)關(guān)鍵領(lǐng)域已經(jīng)或正發(fā)揮著極其重要作用的實(shí)時(shí)系統(tǒng)需具備嚴(yán)格的實(shí)時(shí)性以及高度的可靠性［1］.在實(shí)時(shí)系統(tǒng)性能提升過程中，電路中晶體管尺寸及工作電壓的減小降低了集成電路噪聲容限，集成度進(jìn)一步提高使芯片更易受瞬時(shí)故障影響.由瞬時(shí)故障所導(dǎo)致的計(jì)算機(jī)可靠性已成為一個(gè)嚴(yán)峻的課題［2-3］.瞬時(shí)故障影響設(shè)備的性能及其中任務(wù)的可靠、有效及正確執(zhí)行，因此瞬時(shí)故障容錯(cuò)技術(shù)對系統(tǒng)的實(shí)時(shí)性及可靠性保證至關(guān)重要.

可調(diào)度性分析能夠確保系統(tǒng)實(shí)時(shí)性及可靠性［4］.若任務(wù)集所有任務(wù)的最壞響應(yīng)時(shí)間都不超過各自的截止時(shí)間，則該任務(wù)集是可調(diào)度的.基于檢查點(diǎn)設(shè)置和卷回恢復(fù)技術(shù)進(jìn)行任務(wù)的容錯(cuò)調(diào)度，能在瞬時(shí)故障多次發(fā)生情況下，將任務(wù)恢復(fù)至過去某一正確狀態(tài)，把計(jì)算損失減小為檢查點(diǎn)建立時(shí)刻至故障發(fā)生時(shí)刻所做的計(jì)算.局部最優(yōu)檢查點(diǎn)間隔能在提供容錯(cuò)能力的同時(shí)，最小化任務(wù)額外執(zhí)行時(shí)間.檢查點(diǎn)間隔全局優(yōu)化通過增加或減小任務(wù)的檢查點(diǎn)數(shù)量，使不能滿足截止時(shí)間要求的任務(wù)可以搶占其他任務(wù)的空閑時(shí)間.

實(shí)時(shí)系統(tǒng)容錯(cuò)調(diào)度算法已經(jīng)進(jìn)行了大量的研究.文獻(xiàn)［5］提出卷回恢復(fù)模型下實(shí)時(shí)系統(tǒng)任務(wù)最壞響應(yīng)時(shí)間計(jì)算公式，但該文的檢查點(diǎn)間隔是單次故障情況下的局部最優(yōu)檢查點(diǎn)間隔.文獻(xiàn)［6］分析實(shí)時(shí)系統(tǒng)中多次故障發(fā)生時(shí)進(jìn)程的可調(diào)度性.該文中模型的故障發(fā)生次數(shù)是確定的，而故障次數(shù)是由任務(wù)響應(yīng)時(shí)間和故障發(fā)生間隔決定的.文獻(xiàn)［7］提出擁有不同截止時(shí)間的多任務(wù)最優(yōu)檢查點(diǎn)間隔算法，但該算法僅適用于擁有諧波周期的多個(gè)任務(wù).

粒子群優(yōu)化（PSO）算法是一種源于對鳥群捕食行為的研究而發(fā)明的進(jìn)化計(jì)算技術(shù)［8］.該算法具有較強(qiáng)的局部搜索能力和很好的全局尋優(yōu)能力.PSO算法等一些進(jìn)化優(yōu)化算法已被用于求解多目標(biāo)優(yōu)化問題［9］.

1 任務(wù)容錯(cuò)調(diào)度模型

實(shí)時(shí)系統(tǒng)調(diào)度的任務(wù)集合為Γ=｛τ1，τ2，…，τn｝，其中:τi為實(shí)時(shí)周期性任務(wù).在卷回恢復(fù)容錯(cuò)模型下，任務(wù)τi可表示為七元組＜Ti，Di，Ci，ni，Oi，αi，μi＞，其中Ti、Di、Ci分別為τi的周期、截止時(shí)間、執(zhí)行時(shí)間，且三者滿足Ci＜Di≤Ti；ni為τi的檢查點(diǎn)數(shù)量，任務(wù)開始執(zhí)行時(shí)設(shè)置第1個(gè)檢查點(diǎn)，任務(wù)結(jié)束時(shí)不設(shè)置檢查點(diǎn)；Oi為τi設(shè)置一個(gè)檢查點(diǎn)的開銷；αi為故障檢測開銷；μi為卷回恢復(fù)開銷.

系統(tǒng)對任務(wù)集Γ進(jìn)行實(shí)時(shí)調(diào)度時(shí)，首先需采用優(yōu)先級(jí)調(diào)度算法（如速率單調(diào)算法（RM）［10］或時(shí)限單調(diào)算法（DM）［11］）為任務(wù)集Γ中的每個(gè)任務(wù)τi分配固定且唯一的優(yōu)先級(jí)pi（pi∈｛1，2，…，n｝）.τi的優(yōu)先級(jí)越高，其對應(yīng)的pi越大.根據(jù)任務(wù)τi的優(yōu)先級(jí)pi可定義任務(wù)集Γ的兩個(gè)任務(wù)子集.

1）優(yōu)先級(jí)高于pi的任務(wù)所組成的集合hp（i）為

2）優(yōu)先級(jí)不低于 pi的任務(wù)所組成的集合hpe（i）為

本文基于的條件為:僅考慮瞬時(shí)故障的容錯(cuò)處理，且瞬時(shí)故障能在故障檢測階段被成功檢測，沒有錯(cuò)誤傳遞；所有任務(wù)之間均相互獨(dú)立，沒有資源共享引起的任務(wù)阻塞；采用等間隔檢查點(diǎn)設(shè)置.兩個(gè)連續(xù)發(fā)生的故障之間存在最小時(shí)間間隔TE，TE越小，表明系統(tǒng)容錯(cuò)能力越強(qiáng)，因此可用TE來衡量系統(tǒng)容錯(cuò)能力［12］.

文獻(xiàn)［5］中的任務(wù)最壞響應(yīng)時(shí)間忽略故障恢復(fù)開銷；而檢查點(diǎn)設(shè)置及故障的檢測、恢復(fù)是實(shí)現(xiàn)容錯(cuò)必需的過程，且對于不同的任務(wù)三者的時(shí)間開銷各不相同，即使相同任務(wù)在不同的時(shí)間和負(fù)載時(shí)，三者的時(shí)間開銷也不同.檢查點(diǎn)卷回恢復(fù)的開銷由檢查點(diǎn)間隔決定，檢查點(diǎn)設(shè)置和故障檢測的次數(shù)也由檢查點(diǎn)間隔決定，因此檢查點(diǎn)間隔對容錯(cuò)實(shí)時(shí)系統(tǒng)任務(wù)的可調(diào)度性有重要影響.不同配置的任務(wù)在相同的TE下，其故障發(fā)生次數(shù)不同，任務(wù)的局部最優(yōu)檢查點(diǎn)間隔不同.相同的任務(wù)在不同的TE下，故障發(fā)生次數(shù)也不同，因此局部最優(yōu)檢查點(diǎn)間隔也不同.且對于擁有多個(gè)任務(wù)的任務(wù)集而言，任務(wù)的全局最優(yōu)檢查點(diǎn)間隔與局部最優(yōu)檢查點(diǎn)間隔也不一定相同.在特定TE下，最壞響應(yīng)時(shí)間Ri（ni）可表示為檢查點(diǎn)數(shù)量ni的函數(shù).

圖1是文獻(xiàn)［6］提出的基于檢查點(diǎn)設(shè)置和卷回恢復(fù)技術(shù)的容錯(cuò)模型，該模型中任務(wù)τ1的檢查點(diǎn)數(shù)量為6且故障發(fā)生次數(shù)為2次.故障發(fā)生在τ1的第3個(gè)和第6個(gè)檢查點(diǎn)間隔.基于該模型，在任務(wù)可能發(fā)生多次故障的情況下，同時(shí)考慮檢查點(diǎn)設(shè)置開銷、故障檢測開銷、故障恢復(fù)開銷，得任務(wù)最壞響應(yīng)時(shí)間計(jì)算公式Ri（ni）為

式中Ri（ni）為τi的執(zhí)行時(shí)間、檢查點(diǎn)設(shè)置時(shí)間和故障檢測時(shí)間、高優(yōu)先級(jí)任務(wù)的搶占時(shí)間及故障恢復(fù)時(shí)間之和.故障恢復(fù)時(shí)間是在任務(wù)的最壞響應(yīng)時(shí)間內(nèi)任務(wù)故障發(fā)生次數(shù)和最大故障恢復(fù)開銷的乘積.故障恢復(fù)時(shí)間包含相應(yīng)的檢查點(diǎn)間隔執(zhí)行時(shí)間（Ck/nk）、卷回恢復(fù)開銷和故障檢測開銷.

圖1 基于檢查點(diǎn)設(shè)置和卷回恢復(fù)技術(shù)的容錯(cuò)模型

2 檢查點(diǎn)間隔全局優(yōu)化問題

局部最優(yōu)檢查點(diǎn)間隔是任務(wù)單獨(dú)執(zhí)行時(shí)的最優(yōu)檢查點(diǎn)間隔.具有優(yōu)先級(jí)關(guān)系的多個(gè)任務(wù)并發(fā)執(zhí)行時(shí)，高優(yōu)先級(jí)的任務(wù)會(huì)搶占低優(yōu)先級(jí)任務(wù)的執(zhí)行，因此每個(gè)任務(wù)發(fā)生故障的次數(shù)較單獨(dú)執(zhí)行時(shí)有所變化.如圖2所示，在τi執(zhí)行過程中，由于高優(yōu)先級(jí)任務(wù)τj的周期性搶占，使τi的響應(yīng)時(shí)間由73變?yōu)?0，其故障發(fā)生次數(shù)較τi單獨(dú)執(zhí)行時(shí)的次數(shù)（「73/15?=5）增加.如圖3所示，在τi執(zhí)行過程中，由于高優(yōu)先級(jí)任務(wù)τj的搶占，使τi的響應(yīng)時(shí)間由18變?yōu)?5，其故障發(fā)生次數(shù)較τi單獨(dú)執(zhí)行時(shí)的次數(shù)（「18/15?=2）減少.因此單任務(wù)局部最優(yōu)檢查點(diǎn)間隔并不是任務(wù)集全局最優(yōu)檢查點(diǎn)間隔.

圖2 故障次數(shù)增加的情況

圖3 故障次數(shù)減少的情況

在檢查點(diǎn)間隔全局優(yōu)化時(shí)，如果為了減小不可調(diào)度任務(wù)的最壞響應(yīng)時(shí)間中的故障恢復(fù)時(shí)間，而增加引起最大故障恢復(fù)時(shí)間任務(wù)τi的檢查點(diǎn)數(shù)量，那么τi的檢查點(diǎn)設(shè)置和故障檢測次數(shù)將會(huì)增加，由這兩部分所引起的時(shí)間開銷也會(huì)增加.而且對于其他的低優(yōu)先級(jí)任務(wù)τj（τi∈hp（τj）），其高優(yōu)先級(jí)任務(wù)的搶占執(zhí)行時(shí)間將會(huì)增加，這可能導(dǎo)致τj不能滿足其截止時(shí)間要求.如果為了減小不可調(diào)度任務(wù)的最壞響應(yīng)時(shí)間中的高優(yōu)先級(jí)任務(wù)搶占執(zhí)行時(shí)間，而減小非最大故障恢復(fù)時(shí)間開銷任務(wù)τi的檢查點(diǎn)數(shù)量，那么τi的檢查點(diǎn)設(shè)置和故障檢測次數(shù)將會(huì)減小，由這兩部分所引起的時(shí)間開銷也會(huì)減小.對于τi自身及其他低優(yōu)先級(jí)任務(wù)τj（τi∈hp（τj）），其故障恢復(fù)時(shí)間可能會(huì)增加，這可能導(dǎo)致τi和τj不能滿足其截止時(shí)間要求.每個(gè)任務(wù)在優(yōu)化其自身的檢查點(diǎn)間隔時(shí)，有可能導(dǎo)致其他任務(wù)的最壞響應(yīng)時(shí)間增加.因此通過檢查點(diǎn)間隔優(yōu)化來最小化各個(gè)任務(wù)的Ri（ni）是相互沖突的.檢查點(diǎn)間隔全局優(yōu)化問題的數(shù)學(xué)形式可描述為如下的多目標(biāo)優(yōu)化問題:

式中N為由元素n1，n2，…，nn構(gòu)成的向量.任務(wù)τi檢查點(diǎn)數(shù)量ni的取值范圍首先要確保檢查點(diǎn)技術(shù)能夠有效的執(zhí)行，即在檢查點(diǎn)間隔執(zhí)行時(shí)間、檢查點(diǎn)設(shè)置開銷和故障檢測開銷之和與檢查點(diǎn)間隔執(zhí)行時(shí)間、故障檢測開銷和卷回恢復(fù)開銷之和兩者的最大值內(nèi)只能發(fā)生一次故障；而且檢查點(diǎn)數(shù)量取值范圍還要確保檢查點(diǎn)間隔執(zhí)行時(shí)間大于檢查點(diǎn)設(shè)置開銷、故障檢測開銷與卷回恢復(fù)開銷三者的最大值.

3 檢查點(diǎn)間隔全局優(yōu)化算法

PSO算法中每個(gè)粒子i包含兩個(gè)D維的向量:位置向量xi=（xi1，xi2，…，xiD）和速度向量vi=（vi1，vi2，…，viD）.在PSO算法搜索解空間時(shí)，粒子i需要保存其搜索到的自身最優(yōu)位置pbi=（pbi1，pbi2，…，pbiD），種群需要保存當(dāng)前群體全局最優(yōu)位置gbg= （gbg1，gbg2，…，gbgD）.在PSO算法迭代計(jì)算時(shí)，粒子速度向量中的每維元素根據(jù)自身慣性大小（即當(dāng)前速度大小）和粒子自身最優(yōu)位置中該元素對應(yīng)的最優(yōu)位置及群體全局最優(yōu)位置中該元素對應(yīng)的最優(yōu)位置來動(dòng)態(tài)調(diào)整自身的速度，以改善該元素的位置.粒子i第d維元素的第t+1次迭代進(jìn)化的速度計(jì)算公式和位置計(jì)算公式分別為

式中:ω為慣性權(quán)重因子；c1、c2分別為加速因子，其取值為正常數(shù)；r1、r2分別為區(qū)間［0，1］中均勻分布的隨機(jī)數(shù)；d為D維粒子中的維數(shù)，d∈｛1，2，…，D｝；pb為第t次迭代進(jìn)化時(shí)粒子xi中第d維元素的自身最優(yōu)位置；為第t次迭代進(jìn)化時(shí)第d維元素的群體最優(yōu)位置.

3.1 編碼

本算法中離散編碼方式的編碼長度等于任務(wù)個(gè)數(shù)，粒子中每個(gè)元素的位置表示對應(yīng)任務(wù)的檢查點(diǎn)數(shù)量.粒子xi的編碼方案為xi=（xi1，xi2，…，xiD）.其中，xij為任務(wù)集Γ中任務(wù) τj的檢查點(diǎn)數(shù)量，粒子的維數(shù)D為任務(wù)集中任務(wù)的數(shù)量n.

種群初始化時(shí)根據(jù)ChekptLN算法［13］求解每個(gè)任務(wù)的局部最優(yōu)檢查點(diǎn)間隔，然后在每個(gè)任務(wù)的局部最優(yōu)檢查點(diǎn)間隔附近隨機(jī)生成初始解，隨機(jī)生成滿足約束條件的初始速度向量vi=（vi1，vi2，…，viD）.

3.2 適應(yīng)度函數(shù)

本算法的目的是使所有任務(wù)在滿足截止時(shí)間要求的前提下最小化最壞響應(yīng)時(shí)間.因此粒子xi的適應(yīng)度函數(shù)Fit（xi）可定義為

可以看出，適應(yīng)度函數(shù)為粒子所代表的所有任務(wù)的截止時(shí)間與最壞響應(yīng)時(shí)間差值中的最小值.如果粒子xi的最小差值越大，那么Fit（xi）的函數(shù)值越大，該粒子的位置就越有可能成為種群全局最優(yōu)位置.

3.3 交叉

PSO算法的粒子速度和位置更新方法使得粒子可能會(huì)受某個(gè)局部最優(yōu)值影響而陷入局部極小點(diǎn).遺傳算法能夠使得粒子擺脫這種困境的干擾.因此能夠借鑒遺傳算法的交叉和變異進(jìn)化機(jī)制對PSO算法進(jìn)行改進(jìn)的混合PSO算法［14］被提出.

混合PSO算法按照交叉概率μc對選取的粒子進(jìn)行交叉操作.交叉運(yùn)算將粒子中的所有元素進(jìn)行交叉操作，對于粒子xi和xj中的元素xid和xjd及其對應(yīng)的速度vid和vjd交叉操作方式為

3.4 變異

混合PSO算法按照變異概率μm，對粒子中隨機(jī)選取的第d維元素進(jìn)行變異.變異可增大或減小檢查點(diǎn)數(shù)量.位置和速度的變異方式分別為

3.5 基于混合PSO的檢查點(diǎn)間隔全局優(yōu)化算法

基于混合PSO算法的檢查點(diǎn)間隔全局優(yōu)化算法具體步驟如圖4所示.

圖4 混合PSO的檢查點(diǎn)間隔全局優(yōu)化算法具體步驟

如果忽略算法的任務(wù)最壞響應(yīng)時(shí)間計(jì)算開銷，在交叉操作和變異操作同時(shí)進(jìn)行的情況下，算法在某一特定的故障發(fā)生間隔求解全局優(yōu)化檢查點(diǎn)間隔時(shí)的復(fù)雜度為O（I×n×（cm2+M）），即算法的內(nèi)層while循環(huán)的復(fù)雜度.其中:I為群體進(jìn)化次數(shù)；n為任務(wù)集中任務(wù)數(shù)量；cm為交叉操作粒子數(shù)目；M為群體規(guī)模.

4 性能評估

為驗(yàn)證檢查點(diǎn)間隔全局優(yōu)化算法的高效性，本文用仿真試驗(yàn)?zāi)M810個(gè)任務(wù)集，每個(gè)任務(wù)集包含6個(gè)實(shí)時(shí)周期性任務(wù)（可擴(kuò)展至包含任意數(shù)量任務(wù)的任務(wù)集）.試驗(yàn)計(jì)算機(jī)配置為:Intel（R）E4500 CPU，2 G內(nèi)存，500 G硬盤.參照文獻(xiàn)［13］中方法，隨機(jī)產(chǎn)生Γ中各任務(wù)的配置屬性，但任務(wù)τi的配置須滿足以下條件:

1）τi的周期 Ti和截止時(shí)間 Di均為區(qū)間［100，4 000］上的均勻分布，而且Di≤Ti；

4）混合PSO算法配置為:M為區(qū)間［20，100］上的隨機(jī)數(shù)，I為區(qū)間［20，60］上的隨機(jī)數(shù)，cm為區(qū)間［10，40］上的隨機(jī)數(shù)且小于M，c1和c2都為2，r1和r2為區(qū)間［0，1］上的隨機(jī)數(shù)，μc和μm分別為0.8和0.4.ω采用線性遞減權(quán)值策略求解，如

式中:ωmax、ωmin分別為慣性權(quán)重的最大值和最小值，典型取值為ωmax=0.9，ωmin=0.4；ωt為當(dāng)前慣性權(quán)重值；t為種群當(dāng)前進(jìn)化次數(shù).

采用優(yōu)先級(jí)調(diào)度算法RM對任務(wù)集Γ進(jìn)行容錯(cuò)實(shí)時(shí)調(diào)度.在同時(shí)考慮故障檢測、故障恢復(fù)和檢查點(diǎn)設(shè)置開銷情況下，計(jì)算Γ分別在文獻(xiàn)［5］中基于單次故障優(yōu)化檢查點(diǎn)間隔算法、ChekptLN算法［13］、CIGO算法［13］和本文算法下所能達(dá)到的最小故障發(fā)生間隔STE、LTE、GTGE和GTE.與文獻(xiàn)［5］算法相比，本文算法的系統(tǒng)容錯(cuò)能力提升程度通過式（7）來衡量.

與ChekptLN算法相比，本文算法的系統(tǒng)容錯(cuò)能力提升程度通過式（8）來衡量.

與CIGO算法相比，本文算法的系統(tǒng)容錯(cuò)能力提升程度通過式（9）來衡量.

本文算法相對于文獻(xiàn)［5］算法、ChekptLN算法、CIGO算法系統(tǒng)容錯(cuò)能力提升情況分別如圖5～圖7所示.圖5～圖7中縱坐標(biāo)分別表示系統(tǒng)容錯(cuò)能力的提升程度SGTE、GLTE和GLTGE，橫坐標(biāo)都表示處理器利用率U，黑點(diǎn)分別表示一個(gè)任務(wù)集對應(yīng)的SGTE、GLTE和GLTGE.

圖5 本文算法相對于文獻(xiàn)［5］中算法容錯(cuò)能力提升情況

圖6 本文算法相對于ChekptLN算法容錯(cuò)能力提升情況

圖7 本文算法相對于CIGO算法容錯(cuò)能力提升情況

由圖5可知，與文獻(xiàn)［5］中算法的容錯(cuò)能力相比，本文算法能夠大幅提升系統(tǒng)容錯(cuò)能力.當(dāng)0.1≤U＜0.5時(shí)，SGTE較小，但容錯(cuò)能力提升幅度也較明顯.當(dāng)0.5≤U≤0.9時(shí)，SGTE變化區(qū)域范圍較大.因?yàn)榇藭r(shí)任務(wù)檢查點(diǎn)間隔為發(fā)生一次故障時(shí)的優(yōu)化檢查點(diǎn)間隔，此時(shí)任務(wù)的最壞響應(yīng)時(shí)間較大.任務(wù)在實(shí)際執(zhí)行時(shí)發(fā)生多次故障是極有可能的；在不同的TE時(shí)，故障發(fā)生次數(shù)不同，任務(wù)的最優(yōu)檢查點(diǎn)間隔也不同.對于擁有多個(gè)任務(wù)的任務(wù)集而言，全局最優(yōu)檢查點(diǎn)間隔為當(dāng)前TE時(shí)任務(wù)集中所有任務(wù)的最優(yōu)檢查點(diǎn)間隔.本文算法中的檢查點(diǎn)間隔全局優(yōu)化能減少任務(wù)的檢查點(diǎn)設(shè)置和故障檢測次數(shù)、減小故障恢復(fù)時(shí)間、減小搶占任務(wù)的執(zhí)行時(shí)間來減小任務(wù)最壞響應(yīng)時(shí)間，使任務(wù)滿足其截止時(shí)間要求，從而大幅降低TE.由實(shí)驗(yàn)結(jié)果知SGTE為零的情況極少，說明基于單次故障優(yōu)化檢查點(diǎn)間隔算法的容錯(cuò)能力存在較大提升空間.

由圖6可知，當(dāng)0.1≤U＜0.6時(shí)，GLTE較小且基本不超過25%；當(dāng)0.6≤U≤0.9時(shí)，GLTE在較大區(qū)域內(nèi)變化.容錯(cuò)能力提升程度呈現(xiàn)該分布規(guī)律的原因在于:當(dāng)U較低時(shí)，任務(wù)可以利用自身的空閑時(shí)間來進(jìn)行卷回恢復(fù)以實(shí)現(xiàn)瞬時(shí)故障容錯(cuò)，此時(shí)TE可能已接近其下限，檢查點(diǎn)間隔全局優(yōu)化對TE的提升空間較小.當(dāng)U較高時(shí)，在局部最優(yōu)檢查點(diǎn)間隔時(shí)任務(wù)自身空閑時(shí)間不足以完成瞬時(shí)故障容錯(cuò)，所以此時(shí)TE較大.本文算法能夠?qū)θ蝿?wù)集中所有任務(wù)的檢查點(diǎn)間隔進(jìn)行全局優(yōu)化，以減少任務(wù)的檢查點(diǎn)設(shè)置和故障檢測次數(shù)或者減小搶占任務(wù)執(zhí)行時(shí)間、故障恢復(fù)時(shí)間來滿足任務(wù)的截止時(shí)間要求，從而大幅降低TE.GLTE有時(shí)可能為零，此時(shí)檢查點(diǎn)間隔全局優(yōu)化不能提升系統(tǒng)的容錯(cuò)能力.這主要是由于檢查點(diǎn)數(shù)量的改變已經(jīng)不能改善任務(wù)的最壞響應(yīng)時(shí)間或者不存在滿足優(yōu)化約束條件的任務(wù).

由圖7可知，本文算法的系統(tǒng)容錯(cuò)能力優(yōu)于CIGO算法.這得益于混合PSO算法的全局優(yōu)化能力.由于CIGO算法在檢查點(diǎn)間隔全局優(yōu)化時(shí)，并沒有全局考慮，僅僅是首先增加最大故障恢復(fù)開銷任務(wù)的檢查點(diǎn)數(shù)量，這樣最大故障恢復(fù)開銷任務(wù)集合和非最大故障恢復(fù)開銷任務(wù)集合已經(jīng)改變，在后續(xù)優(yōu)化中檢查點(diǎn)數(shù)量減小任務(wù)集合的定義已經(jīng)并不準(zhǔn)確，所以影響其全局優(yōu)化能力.在U較小時(shí)，本文算法系統(tǒng)容錯(cuò)能力的優(yōu)勢與CIGO算法相比并不是太大，多數(shù)情況下不能進(jìn)一步提高系統(tǒng)的容錯(cuò)能力；但是在U較大時(shí)，本文算法系統(tǒng)容錯(cuò)能力較CIGO算法的優(yōu)勢比較明顯，但是由于此時(shí)兩種算法所能達(dá)到的最小故障發(fā)生間隔較大，所以由式（9）計(jì)算的值較小.

5 結(jié) 語

針對實(shí)時(shí)系統(tǒng)卷回恢復(fù)容錯(cuò)模型局部最優(yōu)檢查點(diǎn)間隔并不是任務(wù)多次故障下的最優(yōu)檢查點(diǎn)間隔及局部最優(yōu)檢查點(diǎn)間隔并不是任務(wù)集全局最優(yōu)檢查點(diǎn)間隔的缺陷，本文對實(shí)時(shí)系統(tǒng)的容錯(cuò)調(diào)度進(jìn)行研究，基于混合PSO算法所具有的遺傳算法和PSO算法的優(yōu)點(diǎn)，提出任務(wù)檢查點(diǎn)間隔全局優(yōu)化算法.該算法通過遺傳算法的交叉和變異操作來增強(qiáng)PSO算法的全局尋優(yōu)能力，對任務(wù)集檢查點(diǎn)間隔進(jìn)行全局優(yōu)化.由仿真實(shí)驗(yàn)可知，檢查點(diǎn)間隔全局優(yōu)化算法能夠在基于單次故障優(yōu)化檢查點(diǎn)間隔的算法和局部最優(yōu)檢查點(diǎn)間隔算法的基礎(chǔ)上進(jìn)一步提升系統(tǒng)的容錯(cuò)能力，且該算法的系統(tǒng)容錯(cuò)能力優(yōu)于CIGO算法.

［1］SHA L，ABDELZAHER T F，ARAEN K E，et al.Real time scheduling theory:a historical perspective［J］.Real-Time Systems，2004，28（2/3）:101-155.

［2］傅忠傳，陳紅松，崔剛，等.處理器容錯(cuò)技術(shù)研究與展望［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（1）:154-160.

［3］CLARK J A，PRADHAN D K.Fault injection:a method for validating computer system dependability［J］.IEEE Computer，1995，28（6）:47-56.

［4］ZHANG F，BURNS A.Schedulability analysis for realtime systems with EDF scheduling［J］.IEEE Transactions on Computers，2009，58（9）:1250-1258.

［5］PUNNEKKAT S，BURNS A，DAVIS R.Analysis of checkpointing forreal-timesystems［J］.Real-Time Systems，2001，20（1）:83-102.

［6］POP P，IZOSIMOV V， ELES P， etal.Design optimization of time and cost-constrained fault-tolerant embedded systems with checkpointing and replication［J］.IEEE Transactions on VeryLargeScaleIntegration Systems，2009，17（3）:389-402

［7］KWAK S W，YANG J M.Optimal checkpoint placement on real-time tasks with harmonic periods［J］.Journal of Computer Science and Technology，2012，27（1）:105-112.

［8］KENNEDY J， EBERHART R.Particle swarm optimization［C］//Proceedings of IEEE International Conference on Neural Networks.Perth:IEEE，1995: 1942-1948.

［9］公茂果，焦李成，楊咚咚，等.進(jìn)化多目標(biāo)優(yōu)化算法研究［J］.軟件學(xué)報(bào)，2009，20（2）:271-289.

［10］LIU L C，LAYLAND J W.Scheduling algorithms for multi-programming in a hard real-time environment［J］.Journal of the ACM，1973，20（1）:46-61.

［11］AUDSLEY N C，BURNS A，WELLINGS A J.Deadline monotonic scheduling theory and application［J］.Control Engineering Practice，1993，1（1）:71-78.

［12］BURNS A，PUNNEKKAT S，STRINGINI L，et al.Probabilistic scheduling guarantees for fault-tolerant realtime systems［C］ //ProceedingsofInternational WorkingConference on Dependable Computing for Critical Applications.San Jose:IEEE，1999:361-378.

［13］何忠政，門朝光，李香.基于檢查點(diǎn)間隔優(yōu)化的容錯(cuò)實(shí)時(shí)系統(tǒng)可調(diào)度性［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2014，44（2）:433-439.

［14］時(shí)小虎，韓世遷，閔克學(xué)，等.基于遺傳算法和粒子群優(yōu)化的混合算法［EB/OL］.北京:中國科技論文在線，［2006-10-27］.http://www.paper.edu.cn/ releasepaper/content/200610-461.

（編輯 張 紅）

The checkpoint global optimization algorithm based on the mixed particle swarm optimization

MEN Chaoguang1，HE Zhongzheng1，CHEN Yongjun2，LI Xiang1，JIANG Qingfeng1
（1.College of Computer Science and Technology，Harbin Engineering University，150001 Harbin，China；2.China Xinxing Construction&Development General Company，100143 Beijing，China）

For the task sets in the fault tolerant real time systems，the disadvantages of the local optimal checkpoint interval are under a single fault assumption and also not the global optimal checkpoint interval.To solve these，the multi-objective optimization model for the checkpoint interval global optimization was given first，and then the checkpoint interval global optimization algorithm based on the mixed particle swarm optimization algorithm was proposed.This algorithm avoids the shortcoming of falling into local optimum and enhances the ability of searching the global approximate optimal checkpoint interval by the crossover and mutation operations of the mixed particle swarm optimization algorithm，and further reduces the task worst case response time.The simulation results show that the algorithm can further improve the system fault resilience over the other checkpoint interval optimization algorithms.At the same time，the checkpoint interval global optimization can search the checkpoint intervals of the task set globally when the faults occur many times，by which the number of checkpoint and the number of fault detection can be reduced and the preemption time by the high priority tasks and the fault recovery time can also be decreased，and also the system schedulability can be improved.

real-time systems；checkpoint interval；fault tolerant scheduling；particle swarm optimization

TP316

A

0367-6234（2015）05-0091-06

10.11918/j.issn.0367-6234.2015.05.016

2014-04-20.

國家自然科學(xué)基金（60873138，61100004）.

門朝光（1963—），男，教授，博士生導(dǎo)師.

門朝光，menchaoguang@hrbeu.edu.cn.