劉浩波,李軍義,李仁發(fā)

(湖南大學信息科學與工程學院,長沙410082)

一種改進的實時嵌入式系統(tǒng)容錯優(yōu)化方法

劉浩波,李軍義,李仁發(fā)

(湖南大學信息科學與工程學院,長沙410082)

容錯技術(shù)中硬件冗余會產(chǎn)生較高的設(shè)計和生產(chǎn)成本。針對該問題,提出一種改進的實時嵌入式系統(tǒng)容錯優(yōu)化方法,基于檢查點容錯技術(shù)綜合分析系統(tǒng)故障性能、硬實時任務(wù)時間約束和軟實時任務(wù)的效用函數(shù)值。以設(shè)計的容錯模型為基礎(chǔ),計算系統(tǒng)故障概率保證其在故障最大概率值內(nèi),給出硬任務(wù)截止時間確定可調(diào)度性,并應(yīng)用改進的禁忌搜索算法獲得軟任務(wù)效用函數(shù)最佳值,算法有2種簡單的鄰節(jié)點結(jié)構(gòu),其禁忌準則遵循鄰節(jié)點方法禁忌,優(yōu)化效率明顯改善。實驗結(jié)果表明,該方法可進行故障分析等綜合分析,并能迅速獲得最大效用函數(shù)值。

容錯優(yōu)化方法;實時嵌入式;檢查點技術(shù);系統(tǒng)故障分析;實時調(diào)度算法

1 概述

目前,實時嵌入式系統(tǒng)在經(jīng)濟、科學等多個領(lǐng)域起著重要作用,對及時性及可靠性的要求不同,實時嵌入式系統(tǒng)分為硬實時系統(tǒng)和軟實時系統(tǒng)[1]。軟實時系統(tǒng)常應(yīng)用于手機、PDA等方面,在某些情況下能容忍一定量延時,出現(xiàn)故障雖不會導(dǎo)致災(zāi)難性后果,但也會明顯降低系統(tǒng)服務(wù)質(zhì)量。硬實時系統(tǒng)常應(yīng)用于航空航天、核工業(yè)控制、電力監(jiān)控及醫(yī)學應(yīng)用等要求實現(xiàn)全部功能而且有嚴格時間約束的領(lǐng)域,若系統(tǒng)出現(xiàn)故障或者不能滿足時間約束,后果將不堪設(shè)想[2]。因此,提高實時嵌入式系統(tǒng)的容錯能力是一項重要的研究工作。容錯技術(shù)最早由文獻[3]提出,是最重要的系統(tǒng)可靠性保障手段[4]。實時嵌入式系統(tǒng)主要通過基于軟件冗余的復(fù)制、基于時間冗余的重新執(zhí)行、基于錯誤回卷恢復(fù)的檢查點技術(shù)以及硬件冗余等技術(shù)實現(xiàn)容錯。而單獨針對硬實時任務(wù)或軟實時任務(wù)的容錯研究較為常見,將硬實時和軟實時任務(wù)整合到相同的平臺上進行容錯優(yōu)化一直是近年來研究的熱點。

迄今為止,關(guān)于這方面的容錯優(yōu)化已有不少文獻,V.Izosimov等人提出系統(tǒng)故障概率(SFP)分析方法,結(jié)合硬化級別的提高和重新執(zhí)行技術(shù)確保系統(tǒng)架構(gòu)滿足可靠性要求[5-6]。該方法只適應(yīng)于考慮硬化處理器和重新執(zhí)行實現(xiàn)容錯的情況。之后,文獻[7]提出可靠性優(yōu)化系統(tǒng)故障樹(SFT)分析方法,基于組件故障概率結(jié)合硬件復(fù)制和軟件重新執(zhí)行技術(shù)計算系統(tǒng)級概率。該方法適用于硬軟冗余實現(xiàn)容錯的情況?？紤]硬件硬化級別或者硬件復(fù)制往往會產(chǎn)生高設(shè)計和高生產(chǎn)成本,適用性相對減弱,依靠軟件容錯技術(shù)進行可靠性優(yōu)化的分析成為一個非常重要的課題。已有不少文獻應(yīng)用軟件容錯技術(shù)綜合分析時間和開銷約束進行優(yōu)化設(shè)計,實現(xiàn)在限定資源或最大化利用率的情況下滿足時間約束的容錯方案[8-10]。然而,這類型的容錯方案并未結(jié)合容錯技術(shù)進行系統(tǒng)故障優(yōu)化的分析。故障分析具體指以容錯映射方案為基礎(chǔ),分析系統(tǒng)故障概率與系統(tǒng)故障最大概率值的關(guān)系。

所謂優(yōu)化分析,即最優(yōu)執(zhí)行方案,具體是指任務(wù)映射處理器問題。任務(wù)映射處理器問題可描述為,已知m個任務(wù)和n個處理器,各任務(wù)均需要映射到處理器上,滿足各任務(wù)符合要求的調(diào)度即可終止。它是許多實際調(diào)度問題的簡化模型,是典型的NP-hard問題。因此,對其進行研究具有重要的理論意義和工程價值。近年來使用優(yōu)化算法解決這類復(fù)雜問題變得越來越流行,在優(yōu)化算法中,禁忌搜索[11-12]、遺傳算法和模擬退火算法[13]等尋優(yōu)技術(shù)是求解非線性優(yōu)化問題的新方法。其中遺傳算法有很高的并行性,但存在早熟和局部收斂等問題;模擬退火算法搜索時間相對較長;禁忌搜索起源于組合優(yōu)化在非線性覆蓋問題中的應(yīng)用,它能有效利用全局信息和搜索中獲得的信息,可克服遺傳算法的局部性,又比模擬退火算法的搜索速度更快[14]。文獻[15]提出應(yīng)用禁忌搜索算法啟發(fā)式解決任務(wù)映射處理機問題獲得滿足優(yōu)化條件的最佳方案。然而,其禁忌列表限于禁忌當前解決方案,禁忌空間較小,使得優(yōu)化算法在避免局部優(yōu)解時性能存在一定局限性。

文獻[16]研究了如何在實時嵌入式系統(tǒng)中處理永久性故障問題。系統(tǒng)故障可分為瞬時性故障、周期性故障及永久性故障。由于更大復(fù)雜性和更高頻率等原因,瞬時故障數(shù)量越來越大且更常見,研究如何處理瞬時故障問題成為工作重點。

本文在優(yōu)化設(shè)計方面除了考慮時間和效用約束外,還要考慮系統(tǒng)故障分析研究,提出一種改進的優(yōu)化分析方法。該分析方法的容錯策略設(shè)計如下:硬實時任務(wù)使用最早截止時間先執(zhí)行,由于檢查點技術(shù)比復(fù)制方法資源利用率更高,比重新執(zhí)行更能節(jié)省容錯所需的重執(zhí)行時間,可相應(yīng)提高效率,因而采用檢查點回卷恢復(fù)技術(shù)實現(xiàn)容錯。軟實時任務(wù)使用最短執(zhí)行時間后執(zhí)行,不建立檢查點,遇故障直接丟棄?？紤]軟實時任務(wù)高度可變的執(zhí)行時間,提出了自定義效用函數(shù)表示軟任務(wù)執(zhí)行利用率,利用率與軟任務(wù)是否在截止時間內(nèi)完成無關(guān)。在任務(wù)映射處理器問題上,提出一種改進的禁忌搜索算法,設(shè)計了2種簡單的鄰節(jié)點結(jié)構(gòu),在判斷禁忌時,將交換方法獲得的候選方案禁忌,致使禁忌列表內(nèi)包含多種解決方案,可獲得最佳解決方案。

2 問題公式化

2.1 容錯模型

本文以處理瞬時故障和硬軟混合實時任務(wù)為重點,以容錯方案滿足可靠、可調(diào)度和效用函數(shù)最佳為目標,考慮一個典型的由多處理器和混合硬軟實時容錯任務(wù)集構(gòu)成的分布式系統(tǒng),由以下定義進行形式化描述:

定義1分布式架構(gòu)由內(nèi)存子系統(tǒng)、通信控制器和中央處理單元組成,可描述為一組處理器集合。

定義2針對混合硬軟實時容錯應(yīng)用映射到分布式系統(tǒng)架構(gòu)中,將一組實時任務(wù)集A分為硬實時任務(wù)和軟實時任務(wù)。A→{Hard,Soft}分別確定任務(wù)是硬實時或者軟實時。

為方便進行形式化描述,硬實時任務(wù)標記如下:

軟實時任務(wù)標記如下:

軟實時任務(wù)的效用函數(shù)是軟任務(wù)完成時間的非遞增單調(diào)函數(shù),3個效用函數(shù)定義如下:

2.2 系統(tǒng)容錯分析

系統(tǒng)容錯分析包括3個階段:故障分析,可調(diào)度性分析和軟任務(wù)效用函數(shù)值最佳分析。在故障分析階段,以容錯模型為基礎(chǔ),分析系統(tǒng)故障概率與故障最大概率的關(guān)系。計算系統(tǒng)故障概率的過程中,只需要求出在相應(yīng)處理器上的任務(wù)當時遇故障概率。

輸入條件中已知各任務(wù)在各處理器上的執(zhí)行遇故障概率,i和j分別表示任務(wù)號和處理器號,N表示處理器,硬實時用h表示,插入f個檢查點;軟實時用s表示,不需插入檢查點,遇故障丟棄。在運行過程中,可分4種情況:軟實時不遇故障、硬實時不遇故障;軟實時不遇故障、硬實時遇故障;軟實時遇故障、硬實時不遇故障;軟實時遇故障、硬實時遇故障。

(1)處理器j相應(yīng)概率pr(0,h,f;0,s;Nj)和處理器相應(yīng)概率pr(0,h,f;0,s;N):

在此種情況下,每個任務(wù)成功執(zhí)行。g表示硬實時任務(wù)被插入檢查點的第g節(jié)。即使被插入檢查點,任務(wù)還是執(zhí)行在同一處理器上。M(P)=N函數(shù)表示任務(wù)P映射在處理器N上。

(2)處理器j相應(yīng)概率pr(kb,h,f;0,s;Nj)和處理器相應(yīng)概率pr(kB,h,f;0,s;N)。

基于f次插入檢查點、kb次遇故障分析處理器上任務(wù)的故障概率。假設(shè)每任務(wù)插入檢查點個數(shù)相同。

m大于等于0,如果m＞0,表示遇故障重新執(zhí)行。G表示所有插入檢查點組合集,gx∈G表示遇故障段集,g表示檢查段,所有硬任務(wù)執(zhí)行段遇故障總數(shù)不得超過kB。舉例說明如圖1所示。

圖1 軟實時不遇故障、硬實時遇故障實例圖

假設(shè)任務(wù)集A由硬實時任務(wù)τ1和軟實時任務(wù)τ2組成,k=2個瞬時錯誤可能發(fā)生,f=3次插入檢查點。硬實時任務(wù)各任務(wù)段執(zhí)行后進行錯誤檢測,發(fā)現(xiàn)成功執(zhí)行,可建立檢查點;遇故障兩次,產(chǎn)生恢復(fù)開銷,后成功執(zhí)行方建立檢查點;成功運行緊接著,執(zhí)行τ2,無故障,且不建立任何檢查點。

(3)處理器j相應(yīng)概率pr(0,h,f;kc,s;Nj)和處理器相應(yīng)概率pr(0,h,f;kC,s;N):

s∈S表示軟任務(wù)無遇故障,s?S表示軟任務(wù)遇故障。各軟任務(wù)遇故障數(shù)目控制在kc,總數(shù)控制在kC。

(4)處理器j相應(yīng)概率pr(kd1,h,f;kd2,s;Nj)和處理器相應(yīng)概率pr(kD1,h,f;kD2,s;N):

所有硬任務(wù)執(zhí)行段遇故障總數(shù)不得超過kD1。s∈S表示軟任務(wù)無遇故障,s?S表示軟任務(wù)遇故障,且遇故障總數(shù)控制在kD2。gx∈G表示遇故障段集,g表示檢查段。

系統(tǒng)保證故障分析要求應(yīng)滿足pr≤γ,γ為系統(tǒng)故障的最大概率。

在可調(diào)度性分析階段,確保硬實時任務(wù)完成時間hct滿足,hct＜截止時間D,則可調(diào)度。并在這基礎(chǔ)上,計算軟任務(wù)的效用函數(shù)值。軟任務(wù)效用函數(shù)值最佳分析使用2.3節(jié)的禁忌搜索算法啟發(fā)式優(yōu)化實現(xiàn)。

2.3 改進的禁忌搜索算法

禁忌搜索算法是在鄰域搜索候選方案的基礎(chǔ)上,通過引入一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準則來避免迂回搜索,同時通過特赦準則赦免一些優(yōu)良的解決方案,進而保證多樣化的有效搜索以最終實現(xiàn)全局的優(yōu)化。引言中已提到任務(wù)映射處理器問題是許多實際調(diào)度問題的簡化模型,是典型的NP-hard問題,并且使用優(yōu)化算法解決這類復(fù)雜問題變得越來越流行,而優(yōu)化算法中,禁忌搜索可克服遺傳算法的局部性,又比模擬退火算法的搜索速度更快。已有文獻提出應(yīng)用禁忌搜索算法解決任務(wù)映射處理器問題,基于此,提出一種改進的禁忌搜索算法,設(shè)計了2種簡單的鄰節(jié)點結(jié)構(gòu),在判斷禁忌時,將交換方法獲得的候選方案禁忌,通過此算法確定任務(wù)映射方案,以期獲得容錯可調(diào)度方案中軟任務(wù)效用函數(shù)值最佳的優(yōu)化方案。禁忌搜索算法中輸入值為應(yīng)用集A和處理器集N,映射M解決方案作為輸出。

禁忌搜索算法的關(guān)鍵參數(shù)和操作設(shè)計如下:

(1)初始方案產(chǎn)生

禁忌搜索方法對初始方案的依賴性較強,好的初始方案能使禁忌搜索盡快收斂到更好的解決方案,而較差的初始方案則會降低禁忌搜索的收斂速度,很難或不能獲到最優(yōu)解決方案。有些算法選擇初始解決方案的時候并不考慮是否可行,本文采用貪心算法以獲得滿足可靠性和可調(diào)度要求的初始方案,以此緩解對初始方案的依賴。

(2)鄰域產(chǎn)生函數(shù)

鄰域產(chǎn)生函數(shù)主要使用移動來實現(xiàn)。

1)交換

如圖2所示,在此初始方案中,圓形表示為軟實時任務(wù),正方形表示硬實時任務(wù),隨機從一個處理器中隨機選擇一個任務(wù),隨機與另一個處理器中一個任務(wù)作交換。如圖3所示,選擇任務(wù)1與任務(wù)2作交換。

圖2 初始方案實例

圖3 交換方案實例

2)重新映射

隨機從一個處理器中隨機選擇一個任務(wù),作重新映射。如圖4所示,選擇任務(wù)1重新映射,映射到另一個處理器中。

圖4 重新映射方案實例

出于改善算法的優(yōu)化時間性能的考慮,通過鄰域結(jié)構(gòu)可以產(chǎn)生大量的鄰域方案,而候選方案僅取其中的少量最佳狀態(tài)。

(3)禁忌準則

該禁忌列表存儲著通過交換方法獲得的候選解決方案。之所以選擇禁忌交換這一鄰域產(chǎn)生函數(shù),是考慮到交換方法需要牽涉到2個不同處理器,而重新映射首次實現(xiàn)的概率明顯優(yōu)于交換實現(xiàn)。以任務(wù)映射處理器問題為例,某候選方案是通過交換產(chǎn)生的鄰節(jié)點,如圖3實際是由處理器1的任務(wù)1和處理器2的任務(wù)2作交換獲得,但交換可獲得更多候選方案,通過交換獲得的鄰節(jié)點均被禁忌。相比單一的禁忌某解決方案,該禁忌準則的設(shè)計可有助于快速逃離局部最優(yōu)解決方案。

(4)特赦準則

禁忌準則可能限制了某些更優(yōu)解決方案,所以需用特赦準則,以釋放雖被禁忌卻很優(yōu)的解決方案。本文設(shè)計的特赦準則是,若一定數(shù)量的解決方案均被禁忌,則設(shè)置這些方案中目標值最大的為當前最好的解決方案。

(5)終止準則

為了使算法具有優(yōu)良的優(yōu)化性能或時間性能,必須設(shè)置一個合理的終止準則來結(jié)束整個搜索過程。經(jīng)過實驗,算法運行可以采用是否找到最佳解和總的循環(huán)次數(shù)兩種終止原則,從效果上看都還不錯。由于VC++循環(huán)的效率較高,運行的時間相對不是很長,所以采用總的循環(huán)次數(shù)限制作為終止原則,如若在循環(huán)次數(shù)前可獲得最佳方案則也終止。

3 容錯優(yōu)化設(shè)計

硬實時任務(wù)應(yīng)用檢查點技術(shù)實現(xiàn)瞬時故障容錯,軟實時任務(wù)遇故障直接丟棄?；诖?對系統(tǒng)實現(xiàn)故障分析、對硬實時任務(wù)實現(xiàn)可調(diào)度性分析和對軟實時任務(wù)實現(xiàn)效用函數(shù)值最大化分析。一般來說,實現(xiàn)設(shè)計時必須著重兩個部分,即映射和調(diào)度。映射時使用改進的禁忌搜索算法優(yōu)化處理器上應(yīng)用,調(diào)度混合硬軟任務(wù)時,分別用最早截止時間和最短執(zhí)行時間調(diào)度硬實時和軟實時任務(wù)。

實現(xiàn)過程選出滿足故障分析要求和可調(diào)度性要求的映射方案,否則及早擴展分析,即優(yōu)化迭代映射和策略分配,以獲得最優(yōu)組合。

4 算法實現(xiàn)

算法實現(xiàn)過程如下:

(1)算法設(shè)計思路

根據(jù)數(shù)據(jù)項建立2個類,先使用一種貪心算法獲得一個初始可行的解決方案,再應(yīng)用改進的禁忌搜索算法反復(fù)迭代尋優(yōu),獲得通過容錯優(yōu)化分析要求的目標函數(shù)值最優(yōu)的解決方案。算法流程如圖5所示。

圖5 本文算法流程

(2)貪心算法設(shè)計思路

獲得初始方案后,判斷方案是否滿足故障分析要求和可調(diào)度性,如若兩者存一不能通過,則返回改變方案,重新調(diào)度判斷,直到初始方案滿足故障分析要求和可調(diào)度性。

(3)禁忌搜索算法設(shè)計思路

步驟1獲得初始化方案后,設(shè)置當前初始方案為目前最佳方案。

步驟2在當前方案的n1個鄰節(jié)點中選擇滿足故障分析和可調(diào)度性要求的n2個方案,在n2個方案中選擇n3個最好的候選方案,對n3個候選方案進行檢測,如若屬于通過交換方法獲得的方案,則將其禁忌。再在這n3個候選方案中選擇最好的未禁忌解決方案,指定為當前方案。如果所有n3方案都被禁忌了,那么選擇最佳禁忌方案為當前方案,注意更新禁忌表。

步驟3如果當前方案比目前最好的方案要好,則目前最好的方案設(shè)置為當前方案。判斷是否更新了M次迭代,如若是,則終止。并判斷是否獲得了最佳方案,如若是,則終止。否則,跳回步驟2。

5 實驗結(jié)果與分析

該分析和優(yōu)化算法用 VC++實現(xiàn),運行在4 GHz CPU和4 GB內(nèi)存的Windows系統(tǒng)中,每個任務(wù)遇故障概率在1·10-6和1·10-5之間隨機產(chǎn)生,設(shè)置每個硬實時任務(wù)遇故障數(shù)在0～2之間隨機產(chǎn)生,每個軟實時任務(wù)遇故障數(shù)在0～1之間隨機產(chǎn)生,每個硬實時任務(wù)被插入3個檢查點。

第1部分實驗是關(guān)于系統(tǒng)故障分析的實驗,對于故障分析的度量,可達到的系統(tǒng)故障最大概率越小,故障分析性能越好。因已有文獻中針對重新執(zhí)行進行系統(tǒng)故障分析,本文采用檢查點回卷恢復(fù)的系統(tǒng)故障分析分別與無容錯分析、重新執(zhí)行的系統(tǒng)故障分析作比。本文用到的檢查點回卷分析法其故障最大概率可達到1·10-16。在嵌入式系統(tǒng)設(shè)計中,一個重要的步驟就是確定滿足故障分析要求的任務(wù)分配情況。處理器數(shù)量滿足2～5的任意平臺下,設(shè)計硬實時任務(wù)數(shù)量分別為2～6,每次運行方案里都保證軟實時任務(wù)數(shù)量為3。

關(guān)于運行次數(shù)的分析如表1所示。以硬實時任務(wù)數(shù)為2、軟實時任務(wù)數(shù)為3、處理器數(shù)為2的情況為例。

表1 運行次數(shù)分析

從表1可看出,對比實驗取運行次數(shù)100 000次,可達高度穩(wěn)健。如表2所示,運行次數(shù)100 000次時檢查點回卷恢復(fù)的故障分析統(tǒng)計情況。

表2 檢查點技術(shù)的故障分析統(tǒng)計

表2是處理器數(shù)為3時的遇故障通過次數(shù)及概率統(tǒng)計表。從表中可以看出,任務(wù)分配如硬實時任務(wù)為4,軟實時任務(wù)為3時,已經(jīng)可以達到很高的可靠性值。即能保證90%滿足故障分析目標,并因此確定任務(wù)分配情況。

如上所述,分別對其余2種情況進行分析,得出檢查點回卷恢復(fù)的故障分析與無容錯故障分析、重新執(zhí)行的故障分析對比如圖6所示。

圖6 故障分析對比

重新執(zhí)行故障分析和無容錯故障分析可達到的故障最大概率分別為1·10-15和0.999 99,均比檢查點回卷故障分析達到的故障最大概率要大。承上所述,度量故障性能的標準是,可達到的故障最大概率值越小,故障性能越顯著。由此看來,檢查點回卷故障性能明顯優(yōu)于其余兩者。如圖6所示的對比實驗,其x軸表示任務(wù)分配情況,分別是硬任務(wù)數(shù)為2～6和軟任務(wù)數(shù)為3,y軸表示通過概率,即達到故障最大概率值的概率,可知檢查點回卷故障分析達到故障最大概率值的穩(wěn)定性能亦優(yōu)于其余兩者。

第2部分實驗是關(guān)于可調(diào)度性的實驗,對于可調(diào)度性分析的度量,專門針對硬實時任務(wù)的完成時間和截止時間,完成時間小于截止時間記為可實現(xiàn)調(diào)度。達到的可調(diào)度概率值越大,可調(diào)度性越好。對于嵌入式實時系統(tǒng)中常見的瞬時故障,目前重點研究的容錯處理方法是基于任務(wù)重新執(zhí)行的容錯調(diào)度方法和基于檢查點技術(shù)的卷回恢復(fù)方法,重新執(zhí)行是通過時間冗余實現(xiàn)容錯,而檢查點技術(shù)是通過錯誤回卷恢復(fù)實現(xiàn)容錯,本文采用后者,現(xiàn)對這2種方法作對比實驗,各運行100 000次,任務(wù)執(zhí)行時間在100～1 000之間隨機產(chǎn)生,硬實時任務(wù)截止時間在1 000～1 800之間隨機產(chǎn)生,建立檢查點開銷、檢測開銷和恢復(fù)開銷均設(shè)計為2,以上參數(shù)經(jīng)過多次試驗驗證?；诘?部分實驗,設(shè)計硬實時任務(wù)數(shù)為4,軟實時任務(wù)數(shù)為3,本文采用檢查點技術(shù)的可調(diào)度性統(tǒng)計情況見表3。

如表3所示,隨著處理器規(guī)模的擴大,處理器上任務(wù)調(diào)度負載相應(yīng)減少,可調(diào)度性越高。考慮到處理器數(shù)目的增多,系統(tǒng)開銷相應(yīng)增加,所以,處理器數(shù)目也會有一定限制。承上所述,分別對上述兩種情況進行可調(diào)度性分析,得出檢查點技術(shù)可調(diào)度性與重新執(zhí)行可調(diào)度性的對比如圖7所示。

表3 檢查點技術(shù)的可調(diào)度性統(tǒng)計

圖7 可調(diào)度性分析對比

從圖7中可以看出,檢查點技術(shù)明顯優(yōu)于重新執(zhí)行的可調(diào)度性能。相比重新執(zhí)行,檢查點技術(shù)能夠緩解時間冗余的部分壓力。

第3部分實驗是關(guān)于禁忌優(yōu)化的實驗,對于禁忌優(yōu)化的度量,主要考慮參數(shù)為軟實時任務(wù)取得的效用函數(shù)值、計算時間和迭代次數(shù),效用函數(shù)值越大,計算時間越短,迭代次數(shù)越少,表明優(yōu)化效果越明顯。已有文獻中設(shè)計禁忌當前解決方案,本文采用改進的禁忌搜索算法與已有文獻中的算法做優(yōu)化對比?；诘?和第2部分實驗,設(shè)計硬實時任務(wù)數(shù)為4,軟實時任務(wù)數(shù)為3,處理器數(shù)為5。由上述實驗可知,選擇這些參數(shù)是最有效的值。用改進的禁忌搜索算法對其求解時還采用了以下參數(shù),分別運行100次,各求平均值,每次運行迭代300次。若提前達到效用函數(shù)最佳值,則終止迭代。數(shù)值比較結(jié)果如表4所示。

表4 函數(shù)值比較結(jié)果

通過以上實驗計算,可以總結(jié)改進的禁忌搜索算法的以下特點:

(1)算法求得的最終解其質(zhì)量較高;

(2)算法的收斂速度較快,計算效率較高;

(3)算法的穩(wěn)健性較強。

curSolution-tabu方案中禁忌列表只禁忌某個解決方案,不如設(shè)計禁忌交換這一鄰域產(chǎn)生函數(shù)更客觀,禁忌列表內(nèi)包括搜索鄰節(jié)點方法而獲得的所有解決方案,擴大了禁忌范圍。相比已有文獻中單一的禁忌某解決方案,該禁忌準則的設(shè)計可有助于快速逃離局部最優(yōu)解決方案,從而可更快速有效地獲得最佳解決方案。

6 結(jié)束語

本文提出一種改進的實時嵌入式系統(tǒng)的容錯優(yōu)化方法,該優(yōu)化方法基于檢查點容錯技術(shù)綜合分析系統(tǒng)故障性能、硬實時任務(wù)時間約束和軟實時任務(wù)的效用函數(shù)值。以設(shè)計的容錯模型為基礎(chǔ),改進的優(yōu)化方法計算了系統(tǒng)故障概率,保證其在故障最大概率值內(nèi),給出硬任務(wù)截止時間確定可調(diào)度性。此外,改進了禁忌搜索算法,提高了收斂和計算速度,反復(fù)迭代尋優(yōu)以獲得滿足容錯優(yōu)化的最佳方案。

根據(jù)上述總結(jié),本文下一步工作主要包括以下3個方面:(1)任務(wù)遇故障后重新調(diào)度,可提高或降低其優(yōu)先級,而不是繼承其正常運行時優(yōu)先級; (2)關(guān)于檢查點的研究,可以考慮不同等間隔插入檢查點;(3)禁忌搜索算法改進問題。首先可以考慮獲得鄰節(jié)點的方法,可以取交叉。交叉操作是基于任務(wù)集交叉,即先把任務(wù)分成2個非空集合,集合A或者集合B,把處理器分成2個非空集合,集合C或者集合D,從A集合中分別隨機選擇屬于集合A的任務(wù)隨機映射到處理器集C中的處理器,從集合B中分別隨機選擇屬于集合B的任務(wù)隨機映射到處理器集D中的處理器。其次可以考慮禁忌列表的改善,設(shè)計禁忌區(qū)間,若候選方案的適配值在禁忌區(qū)間內(nèi),則將其方案禁忌。

[1] Kopetz H.Real-time Systems-design Principles for Distributed Embedded Applications[M].[S.1.]: Kluwer Academic Publishers,1997.

[2] Li Qing.Real-time Concept for Embedded Systems[M].[S.1.]:CMP Books Inc.,2003.

[3] 袁由光,陳以農(nóng).容錯與避錯技術(shù)及其應(yīng)用[M].北京:科學出版社,1992.

[4] 陳 宇,熊光澤,楊 春.支持自適應(yīng)容錯的多處理器實時操作系統(tǒng)[J].計算機科學,2002,29(3):125-128.

[5] Izosimov V,Polian I,Pop P,et al.An aLysis and Optimization of Fault-tolerant Embedded Systems with Hardened Processors[C]//Proceedings of Conference on Design,Automation&Test in Europe.Nice,England: [s.n.],2009:682-687

[6] Izosimov V.Scheduling and Optimization ofFaulttolerant Distributed Embedded Systems[D].Sweden, Linkoping:Linkoping University,2009.

[7] Huang Jia,Blech J O,Raabe A,et al.Reliability-aware Design Optimization forMulti-processorEmbedded Systems[C]//Proceedings of Conference on Digital System Design in Europe.Oulu,Finland:[s.n.],2011: 239-246.

[8] Izosimov V,Pop P,Eles P,et al.Design Optimization of Time-and Cost-constrained Fault-tolerantDistributed Embedded Systems[C]//Proceedings of Conference on Design,Automation and Testin Europe.Munich, Germany:[s.n.],2005:864-869.

[9] Pop P,Izosimov V,Eles P,et al.Design Optimization of Timeand Cost-constrained Fault-tolerantEmbedded systems with checkpointing and Replication[J].IEEE Transactions on Very Large Scale Integration Systems, 2009,17(3):389-402.

[10] Izosimov V,Eles P,Peng Z.Value-based Scheduling of Distributed Fault-tolerant Real-time Systems with Soft and Hard Timing Constraints[C]//Proceedings of IEEE Workshop on Embedded Systems for Real-time Multimedia.Scottsdale,America:[s.n.],2010:31-40.

[11] Glover F.Tabu Search-part I[J].ORSA Journal on Computing,1989,1(3):190-206.

[12] Glover F,Tabu Search-part II[J].ORSA Journal on Computing,1990,2(1):4-32.

[13] Davis L.Genetic Algorithmsand Simulated Annealing[M].London,England:Pitman Publishing,1987.

[14] 張文化,劉素華,候惠芳.一種用于特征選擇的禁忌搜索算法[J].計算機應(yīng)用與軟件,2010,27(5):125-128.

[15] Saraswat P K,PopP,MadsenJ.TaskMappingand Bandwidth Reservation for Mixed Hard/soft Fault-tolerant Embedded Systems[C]//Proceedings of the 16th IEEE Symposium on Real-time and Embedded Technology and Applications.Stockholm,Sweden:[s.n.],2010:89-98.

[16] Saraswat P K,Pop P,Madsen J.Task Migration for Faulttolerance in Mixed-criticality Embedded Systems[C]// Proceedings of the 2nd Workshop on Adaptive and Reconfig-urable Embedded Systems.Grenoble,France: [s.n.],2009:125-131.

編輯 索書志

An Improved Fault Tolerance Optimization Method of Real-time Embedded System

LIU Haobo,LI Junyi,LI Renfa
(College of Information Science and Engineering,Hunan University,Changsha 410082,China)

For the hardware redundancy fault tolerance technology tends to produce the defect of high design and high production costs,this paper puts forward an improved fault tolerance optimization method of real-time embedded system. The optimization method is based on checkpoint fault tolerance technology,and it comprehensively analyzes system failure performance,hard real-time task time constraints,and the utility function value of the soft real-time tasks.It is based on the design of fault tolerance model,the improved optimization method calculates the system failure probability, determines the schedulability of hard tasks,and uses an improved tabu search heuristic optimization to obtain utility function best value of soft tasks.The tabu search algorithm has two neighboring nodes of simple structure,it is tabu guidelines follow the tabu of adjacent node method and optimization efficiency is improved significantly.Experimental results show that the fault tolerance optimization method can carry on fault analysis and so on,and can quickly obtain maximum utility function.

fault tolerance optimization method;real-time embedded;checkpoint technology;system fault analysis; real-time scheduling algorithm

1000-3428(2015)01-0012-07

A

TP302

10.3969/j.issn.1000-3428.2015.01.003

國家“863”計劃基金資助項目(2012AA01A301-01);廣東省產(chǎn)學研基金資助重大項目(2011A091000027);廣東省產(chǎn)學研基金資助重大項目“基于北斗/GPS的智能車載信息終端關(guān)鍵技術(shù)研究與產(chǎn)業(yè)化”([2012]391)。

劉浩波(1989-),女,碩士研究生,主研方向:嵌入式容錯,軟件測試;李軍義,副教授、博士;李仁發(fā),教授、博士。

2014-02-12

2014-04-05 E-mail:15974144754@163.com

中文引用格式:劉浩波,李軍義,李仁發(fā).一種改進的實時嵌入式系統(tǒng)容錯優(yōu)化方法[J].計算機工程,2015,41(1): 12-18.

英文引用格式:Liu Haobo,Li Junyi,Li Renfa.An Improved Fault Tolerance Optimization Method of Real-time Embedded System[J].Computer Engineering,2015,41(1):12-18.