基于滑動(dòng)窗口的低能耗高可靠調(diào)度算法

鄧昌義,郭銳鋒,吳昊天,彭阿珍,杜少華,蓋榮麗

(1.國(guó)家工業(yè)信息安全發(fā)展研究中心 系統(tǒng)所， 北京 100040；2.中國(guó)科學(xué)院大學(xué)， 北京 100049;3.中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所， 遼寧 沈陽(yáng) 110168;4.沈陽(yáng)高精數(shù)控智能技術(shù)股份有限公司，遼寧 沈陽(yáng) 110168;5.大連大學(xué) 信息工程學(xué)院，遼寧 大連 116021)

0 引言

隨著計(jì)算機(jī)系統(tǒng)，特別是網(wǎng)絡(luò)技術(shù)的發(fā)展，計(jì)算機(jī)集成制造系統(tǒng)的實(shí)現(xiàn)形式從集中型向以系統(tǒng)應(yīng)用平臺(tái)化、系統(tǒng)結(jié)構(gòu)開(kāi)放化、制造資源服務(wù)化、管理決策智能化和綠色化制造方向發(fā)展[1]，其變化不僅是技術(shù)上的升級(jí)，更符合實(shí)際生產(chǎn)的需要。在實(shí)際工業(yè)生產(chǎn)中，數(shù)控機(jī)床的種類很多，許多機(jī)床是面向特定用戶的需要開(kāi)發(fā)的。控制器廠家提供的數(shù)控系統(tǒng)大多是全功能的數(shù)控系統(tǒng)，但實(shí)際使用中許多參數(shù)需要根據(jù)機(jī)床的實(shí)際情況進(jìn)行配置和二次開(kāi)發(fā)，廠家提供的數(shù)控系統(tǒng)功能不一定能夠滿足機(jī)床制造企業(yè)的需要。在這種情況下，具有“開(kāi)放性”的數(shù)控系統(tǒng)成為企業(yè)需求，即不僅有高度模塊化的結(jié)構(gòu)，還可以重新配置、修改、擴(kuò)充和改裝的開(kāi)放式數(shù)控系統(tǒng)。

作為一種典型的實(shí)時(shí)系統(tǒng)，開(kāi)放式數(shù)控系統(tǒng)是數(shù)控機(jī)床的核心部件。數(shù)控機(jī)床在數(shù)控系統(tǒng)的控制下，根據(jù)編程指令設(shè)定的速度運(yùn)動(dòng)實(shí)現(xiàn)高速高精加工[2]。數(shù)控系統(tǒng)不但要求在截止期限內(nèi)完成任務(wù)，而且要保證任務(wù)的正確執(zhí)行。當(dāng)前，快速發(fā)展的技術(shù)和復(fù)雜制造工藝已經(jīng)對(duì)處理器可靠性產(chǎn)生潛在影響[2-3],宇宙射線也增加了處理器出錯(cuò)的可能性[4]，同時(shí)高能耗導(dǎo)致系統(tǒng)運(yùn)行在較高的溫度環(huán)境中,進(jìn)一步降低了系統(tǒng)的可靠性。因此，設(shè)計(jì)滿足高可靠低能耗的開(kāi)放式數(shù)控系統(tǒng)成為一個(gè)非常重要的問(wèn)題。為方便快捷地開(kāi)發(fā)出專用控制器，允許系統(tǒng)進(jìn)行二次開(kāi)發(fā)，文獻(xiàn)[3]提出開(kāi)放式專用數(shù)控系統(tǒng)的核心模型，包括功能模型、數(shù)據(jù)模型、結(jié)構(gòu)模型和行為模型，該模型采用嵌入式多CPU架構(gòu)實(shí)現(xiàn)了專用數(shù)控系統(tǒng)的分布型操作;文獻(xiàn)[4]提出一種面向開(kāi)放式數(shù)控系統(tǒng)、基于預(yù)分配的空閑挪用算法。算法開(kāi)始前，采用預(yù)分配算法為實(shí)時(shí)周期任務(wù)預(yù)留處理器時(shí)間，使得在調(diào)度周期任務(wù)時(shí)空閑時(shí)間盡可能提前。在調(diào)度非周期任務(wù)上，采用預(yù)留處理器最大可用空閑時(shí)間機(jī)制實(shí)現(xiàn)以較小的計(jì)算和較低存儲(chǔ)開(kāi)銷獲得最短非周期任務(wù)響應(yīng)時(shí)間。

動(dòng)態(tài)電壓調(diào)整(Dynamic Voltage Scaling, DVS)是嵌入式實(shí)時(shí)系統(tǒng)中普遍采用的一種節(jié)能技術(shù)[5]，它通過(guò)降低電路的供電電壓和運(yùn)行頻率來(lái)降低動(dòng)態(tài)能耗，許多主流的商業(yè)處理器，如Intel XScale[6]、AMD G-series[7]及龍芯[8]系列的多核處理器均支持DVS。通過(guò)DVS改變電壓和頻率會(huì)帶來(lái)時(shí)間、能耗的開(kāi)銷，但這些開(kāi)銷非常小。動(dòng)態(tài)功耗管理(Dynamic Power Management, DPM)主要用于降低處理器之外，如內(nèi)存、I/O等模塊的能耗[9]，當(dāng)這些設(shè)備模塊響應(yīng)處理請(qǐng)求時(shí)，為正常工作和耗電狀態(tài)；當(dāng)設(shè)備空閑時(shí)，進(jìn)入低能耗的睡眠狀態(tài)。但采用DPM，處理器狀態(tài)切換造成的時(shí)間和能消耗不可忽視。因此，采用DVS或DPM降低能耗時(shí)，必須同時(shí)考慮實(shí)時(shí)性和可靠性限制。為了保證實(shí)時(shí)任務(wù)在出現(xiàn)系統(tǒng)軟/硬件故障后仍能在截止期限前完成，需要為實(shí)時(shí)嵌入式系統(tǒng)提供具有實(shí)時(shí)性的容錯(cuò)保障，從而確保系統(tǒng)的可靠性不受影響。主/副版本備份技術(shù)(Primary/Backup copy, P/B)的每個(gè)運(yùn)行任務(wù)包含主、副2個(gè)相互獨(dú)立的任務(wù)[10]，當(dāng)主版本任務(wù)執(zhí)行發(fā)生錯(cuò)誤時(shí)可以啟動(dòng)執(zhí)行副版本任務(wù)，從而保證系統(tǒng)的可靠性不受影響。

文獻(xiàn)[4]提出一種基于預(yù)分配的空閑挪用算法，用于調(diào)度開(kāi)放式數(shù)控系統(tǒng)的混合任務(wù)。算法首先采用預(yù)分配算法為實(shí)時(shí)周期任務(wù)預(yù)留處理器時(shí)間，將調(diào)度周期任務(wù)的空閑時(shí)間盡可能提前。在調(diào)度非周期任務(wù)上，采用最大的可用空閑時(shí)間機(jī)制，實(shí)現(xiàn)以較小的計(jì)算和較低存儲(chǔ)開(kāi)銷下獲得最短的非周期任務(wù)響應(yīng)時(shí)間。文獻(xiàn)[8,11]提出一種基于能耗的調(diào)度算法，該算法以最小化能耗為目標(biāo)同時(shí)滿足處理器吞吐量和響應(yīng)時(shí)間的要求。文獻(xiàn)[9,12]提出一種能耗管理算法，使用流水線和并行處理技術(shù)調(diào)度單處理器上的任務(wù)。在容錯(cuò)方面，要實(shí)現(xiàn)對(duì)瞬態(tài)故障的容錯(cuò)，需要故障檢測(cè)機(jī)制[13-14]。故障檢測(cè)機(jī)制需要滿足數(shù)控系統(tǒng)高可靠性需要，文獻(xiàn)[10,13]提出基于N模塊冗余技術(shù)，該技術(shù)不需要額外硬件檢測(cè)故障，而是使用多數(shù)投票的方法進(jìn)行故障檢測(cè)和容錯(cuò)。因?yàn)樗心K不可能同時(shí)出現(xiàn)相同的錯(cuò)誤，所以多數(shù)投票可以實(shí)現(xiàn)對(duì)系統(tǒng)故障的檢測(cè)和容錯(cuò)[13]，但N模塊冗余需要消耗更多的能耗開(kāi)銷來(lái)實(shí)現(xiàn)容錯(cuò)[14]。Melhem等[15]利用系統(tǒng)的空閑時(shí)間，在DVS降低能耗的同時(shí)基于檢查點(diǎn)技術(shù)實(shí)現(xiàn)容錯(cuò);Zhu等[16]提出可靠性感知能耗管理(Reliability-Aware Power Management, RAPM)，系統(tǒng)的可靠性定義為每個(gè)任務(wù)可靠性的乘積，RAPM的目標(biāo)就是在保證系統(tǒng)原有可靠性的同時(shí)利用DVS節(jié)能。RAPM的基本思路是，對(duì)于每一個(gè)電壓調(diào)整的任務(wù)，在滿足實(shí)時(shí)性約束下另外調(diào)度一個(gè)以最高電壓及CPU速率的恢復(fù)任務(wù)，從而保證該任務(wù)的原有可靠性。Zhao等[17]提出利用預(yù)留部分全局空閑時(shí)間代替給每一個(gè)任務(wù)備份空閑時(shí)間的節(jié)能機(jī)制，通過(guò)減少任務(wù)備份數(shù)量實(shí)現(xiàn)低能耗和可靠性的平衡，但是所提的GSHR(generalized shared recovery)算法只能在一個(gè)范圍內(nèi)保證系統(tǒng)的可靠性，不具有一般性。

基于以上研究，本文首先提出通用任務(wù)模型的可靠性調(diào)度算法，該模型充分考慮系統(tǒng)可靠性，同時(shí)考慮降低系統(tǒng)功耗和保證系統(tǒng)可靠性協(xié)同調(diào)度，實(shí)現(xiàn)系統(tǒng)低能耗和高可靠的目的。在此基礎(chǔ)上，提出基于滑動(dòng)窗口的低能耗調(diào)度算法(Low Power Scheduling Algorithm Based On Sliding Window, LPRSW)，并根據(jù)任務(wù)出錯(cuò)場(chǎng)景將算法分為L(zhǎng)PRSW-A和LPRSW-H算法。其次，依據(jù)出錯(cuò)任務(wù)的特點(diǎn)，優(yōu)化備份任務(wù)數(shù)量，提出基于滑動(dòng)窗口的低能耗與可靠性協(xié)同優(yōu)化調(diào)度算法(Cooperative Optimal Scheduling Algorithm for Low Power and Reliability Based on Sliding Window, COSALPRSW)。該算法以提高系統(tǒng)的可調(diào)度性為目標(biāo)進(jìn)行任務(wù)的分配，通過(guò)備份任務(wù)共享空閑時(shí)間和優(yōu)化后續(xù)任務(wù)的執(zhí)行速度，在不增加硬件代價(jià)的前提下實(shí)現(xiàn)系統(tǒng)低能耗高可靠的目標(biāo)。最后，通過(guò)實(shí)驗(yàn)結(jié)果表明，所提出的算法都能滿足系統(tǒng)可靠性的要求。

1 系統(tǒng)模型與功耗模型

1.1 實(shí)時(shí)任務(wù)模型

數(shù)控系統(tǒng)的加工任務(wù)包括處理軌跡插補(bǔ)、位置控制、運(yùn)動(dòng)控制等周期性任務(wù)?？紤]有n個(gè)實(shí)時(shí)任務(wù)組成的任務(wù)調(diào)度模型J=(J1,J2,…,Jn)，Ji表示在一個(gè)任務(wù)集合的第i次調(diào)用。任務(wù)的參數(shù)用一個(gè)三元數(shù)組表示為J=(ai,ci,di)，各參數(shù)定義如下：

ai表示任務(wù)Ji將要執(zhí)行的時(shí)間;

ci表示Ji在最大速度smax下的最壞執(zhí)行時(shí)間，smax表示處理器能夠提供的最大速度;

di表示任務(wù)Ji的絕對(duì)截止期限。

該任務(wù)模型具有通用性，可以很好地拓展到其他實(shí)時(shí)任務(wù)模型，例如周期任務(wù)模型和非周期任務(wù)模型。所有的任務(wù)相互獨(dú)立，采用EDF(earliest deadline first)調(diào)用策略。

1.2 功耗模型

假設(shè)處理器速度頻率或速度可以連續(xù)調(diào)節(jié);拓展算法支持處理器在離散速度中調(diào)節(jié);當(dāng)任務(wù)Ji在速度Si下執(zhí)行時(shí)，需要的執(zhí)行時(shí)間為ci/si;整個(gè)任務(wù)集合對(duì)應(yīng)的速度可以表示為S={s1,s2,s3,…,sn}，這里Si是任務(wù)Ji運(yùn)行時(shí)對(duì)應(yīng)的速度。本文采用文獻(xiàn)[17]的功耗模型，系統(tǒng)的功耗為

P=Ps+h(Pind+Pdep)

=Ps+h(Pind+Cefsm)。

(1)

(2)

1.3 可靠性模型

研究表明，發(fā)生瞬時(shí)錯(cuò)誤的概率比永久錯(cuò)誤的概率大，瞬時(shí)任務(wù)出錯(cuò)概率符合泊松分布[17]。對(duì)于支持動(dòng)態(tài)電壓調(diào)節(jié)的實(shí)時(shí)系統(tǒng)，考慮到調(diào)節(jié)電壓對(duì)瞬時(shí)錯(cuò)誤產(chǎn)生的不利影響，由瞬時(shí)錯(cuò)誤引起的任務(wù)平均出錯(cuò)率和處理器調(diào)整頻率f(對(duì)應(yīng)電壓V)之間的關(guān)系可以表示為[17]

λ(f)=λ0·g(f)。

(3)

式中：λ0為在頻率fmax最大情況下任務(wù)平均出錯(cuò)率。這里g(fmax)=1。低頻率或低電壓將導(dǎo)致由瞬時(shí)錯(cuò)誤引起的任務(wù)錯(cuò)誤率增加。因?yàn)閒1。

本文考慮由瞬時(shí)錯(cuò)誤引起的任務(wù)錯(cuò)誤指數(shù)評(píng)價(jià)模型，根據(jù)文獻(xiàn)[17]有

(4)

式中d(>0)是一個(gè)常量，表示任務(wù)對(duì)處理器速度調(diào)節(jié)出錯(cuò)的敏感度，即當(dāng)處理器處于最低的頻率工作時(shí)，具有最高的失效率λmax=λ0·10d。瞬時(shí)錯(cuò)誤引起的任務(wù)出錯(cuò)可以使用接受測(cè)試(Acceptance Test，AT)的方法[19]進(jìn)行故障檢測(cè)。每一個(gè)任務(wù)執(zhí)行完畢時(shí)向?qū)?yīng)的備份任務(wù)發(fā)送消息，通知主版本執(zhí)行完畢，如果備份任務(wù)在指定的時(shí)間內(nèi)仍未收到任務(wù)發(fā)來(lái)的消息，則認(rèn)為任務(wù)所在的處理器出現(xiàn)故障。一旦發(fā)現(xiàn)故障，則將執(zhí)行備份任務(wù)。

系統(tǒng)的可靠性為所有任務(wù)成功正確執(zhí)行的概率。一個(gè)任務(wù)按最壞時(shí)間ci執(zhí)行，在處理器頻率f下的可靠性為

(5)

規(guī)定Rj(T1,…,Tn)表示系統(tǒng)的可靠性，即每一個(gè)任務(wù)成功執(zhí)行的可能性。如果任務(wù)出錯(cuò)，則使用空閑時(shí)間恢復(fù)第j個(gè)出錯(cuò)的任務(wù)。規(guī)定Rg表示系統(tǒng)要保證的穩(wěn)定性。

R1(J1,…,Jn)=R1(f1)R1(J2,…,Jn)+

(1-R1(f1))R1(fmax)R0(J2,…,Jn)。

(6)

推廣到一般模型，當(dāng)有j個(gè)任務(wù)需要容錯(cuò)時(shí)，系統(tǒng)的可靠性為

Rj(J1,…,Jn)=R1(f1)Rj(J2,…,Jn)+

(1-R1(f1))R1(fmax)Rj-1(J2,…,Jn)。

(7)

式中:加號(hào)前半部分表示任務(wù)J1成功執(zhí)行，余下的J個(gè)備份任務(wù)可以給后續(xù)任務(wù)使用；加號(hào)的后半部分表示J1執(zhí)行失敗，后續(xù)任務(wù)需要一個(gè)備份任務(wù)容錯(cuò)。系統(tǒng)的可靠性Rj(J1,…,Jn)可以使用動(dòng)態(tài)規(guī)劃快速計(jì)算出，線性漸進(jìn)復(fù)雜度為O(J·n)。

1.4 問(wèn)題定義

低能耗和可靠性協(xié)同系統(tǒng)優(yōu)化算法的問(wèn)題可以表示為：在保證系統(tǒng)可靠性前提下找到最優(yōu)的任務(wù)備份數(shù)，同時(shí)分配調(diào)整后的處理器頻率使得總能耗E最小。

Rj(J1,…,Jn)≥Rg;

(8)

(9)

式中D*為執(zhí)行任務(wù)集合J所需的總時(shí)間。顯然，用于容錯(cuò)的空閑時(shí)間越多，系統(tǒng)的可靠性Rg越容易保證。當(dāng)考慮實(shí)時(shí)任務(wù)的截止期限時(shí)，系統(tǒng)的可靠性和低功耗在空閑時(shí)間上存在競(jìng)爭(zhēng)關(guān)系，因?yàn)槊恳粋€(gè)備份任務(wù)需要占用空閑時(shí)間，處理器通過(guò)調(diào)節(jié)頻率獲得低能耗同樣有賴于空閑時(shí)間的分配。

2 低能耗與可靠性優(yōu)化調(diào)度算法

2.1 動(dòng)態(tài)滑動(dòng)窗口調(diào)度任務(wù)機(jī)制

根據(jù)文獻(xiàn)[20]，在LPEDF算法基礎(chǔ)上進(jìn)行拓展，使其成為一個(gè)能夠容錯(cuò)的低能耗調(diào)度LPRSW算法。

基于以上定義，給出一個(gè)實(shí)時(shí)任務(wù)集合J，LPRSW算法能夠在保證系統(tǒng)可靠性的前提下降低系統(tǒng)能耗，算法步驟如下：

(1)根據(jù)定義1確定滑動(dòng)窗口。

(2)調(diào)整窗口大小，將所有的任務(wù)納入窗口中，設(shè)置所有任務(wù)的速度為S(I)，調(diào)整釋放時(shí)間和截止期限。特別地，調(diào)整滑動(dòng)窗口任務(wù)集合J-J(I)→J按照下面規(guī)則進(jìn)行：如果di∈[ts,tf]，則滑動(dòng)窗口更新di→ts；如果ai≥tf，則ai-(tf-ts)；如果ai∈[ts,tf]，則ai→ts；如果di≥tf，則di-(tf-ts)。

(3)當(dāng)任務(wù)執(zhí)行出現(xiàn)錯(cuò)誤時(shí)，啟動(dòng)容錯(cuò)機(jī)制同時(shí)增加滑動(dòng)窗口負(fù)載。重新計(jì)算出錯(cuò)任務(wù)的強(qiáng)度，用Sm(I)代替s(I)，

(10)

(4)重復(fù)以上步驟直到集合J為空。

根據(jù)公式(10), 在任務(wù)集合中有K個(gè)錯(cuò)誤需要容錯(cuò)的條件限制下，任意一個(gè)采用最早截止期限優(yōu)先(Earliest Deadline First，EDF)調(diào)度策略的實(shí)時(shí)任務(wù)集合可調(diào)度的條件為

定理1文獻(xiàn)[21]給出一個(gè)實(shí)時(shí)任務(wù)集合J，在Smax=1下實(shí)現(xiàn)K個(gè)容錯(cuò)。如果對(duì)于每一個(gè)滑動(dòng)窗口I,

(11)

則任務(wù)集合是可調(diào)度的。注意到，當(dāng)一個(gè)任務(wù)出錯(cuò)后，LPRSW執(zhí)行一個(gè)備份任務(wù)可以有兩種選擇，第一種是使用調(diào)節(jié)后的處理器速度策略LPRSW-A,第二種是使用處理器最高速度策略LPRSW-H。下面通過(guò)實(shí)例說(shuō)明兩種算法在不同任務(wù)下的節(jié)能效果。使用算法LPRSW-H時(shí)，滑動(dòng)窗口的強(qiáng)度表示為

(12)

可以明顯看出在滑動(dòng)窗口I中，如果W(I)+Wft(I)≤L(I)，則Se≤Sm。該方法的優(yōu)勢(shì)在于它需要很少的備份資源去保證任務(wù)容錯(cuò)，因此可以在出錯(cuò)率較低情況下使用該策略。為了進(jìn)一步說(shuō)明，考慮任務(wù)集合調(diào)度實(shí)例(如表1),令m=3，Pind=0.02，Cef=1，簡(jiǎn)單起見(jiàn)，時(shí)間和能耗轉(zhuǎn)換開(kāi)銷忽略不計(jì)。LPRSW-A算法(如圖1a)調(diào)度任務(wù)集合的能耗為11.06，LPRSW-H算法(如圖1b)能耗消耗為11.5，LPRSW-A消耗相對(duì)較少的能耗。然而，當(dāng)系統(tǒng)不存在出錯(cuò)任務(wù)時(shí)(如圖1c)，LPRSW-A算法消耗的能耗為5.53，LPRSW-H(圖1d)消耗的能耗為4.36，反而LPRSW-A消耗更多的能耗。由于出錯(cuò)率在實(shí)際系統(tǒng)中通常較低，LPRSW-H采用處理器最大速度執(zhí)行出錯(cuò)任務(wù)，相對(duì)占用的空閑時(shí)間較少。因此，在降低能耗消耗上，LPRSW-H相比LPRSW-A更有優(yōu)勢(shì)。

表1 任務(wù)集合調(diào)度實(shí)例

為了滿足實(shí)時(shí)任務(wù)的截止期限，上述方法每次迭代調(diào)整滑動(dòng)窗口大小時(shí)，假設(shè)在滑動(dòng)窗口中按最壞執(zhí)行時(shí)間，所有k個(gè)出錯(cuò)任務(wù)將影響執(zhí)行時(shí)間最長(zhǎng)的任務(wù)。這個(gè)假設(shè)相對(duì)比較悲觀，因?yàn)槊恳粋€(gè)滑動(dòng)窗口需要計(jì)算滿足k個(gè)容錯(cuò)所需的預(yù)留資源，有可能導(dǎo)致一個(gè)可調(diào)度任務(wù)集合不可調(diào)度。使用下面的例子進(jìn)行說(shuō)明。

根據(jù)表2,考慮一個(gè)系統(tǒng)中有兩個(gè)確定的任務(wù)需要調(diào)度(如圖2)，最多有一個(gè)任務(wù)需要容錯(cuò)。為了簡(jiǎn)單闡述，假定發(fā)現(xiàn)任務(wù)出錯(cuò)的開(kāi)銷為0。根據(jù)LPRSW算法，第一個(gè)滑動(dòng)窗口為[3，7]，根據(jù)式(12)其強(qiáng)度為1。使用任務(wù)J2調(diào)整窗口[2，6]后，d1調(diào)整為3，則第二個(gè)滑動(dòng)窗口為[0，2]，其強(qiáng)度為2。調(diào)度過(guò)程如圖2所示，這里I1和I2表示第一個(gè)和第二個(gè)滑動(dòng)窗口?？梢?jiàn)Se(I2)比Se(I1)大，這種情形為單調(diào)性優(yōu)先級(jí)翻轉(zhuǎn)，更重要的是，Se(I2)超過(guò)了系統(tǒng)中的最高速度(Smax=1)，因此所需要的速度是不可能獲得的。事實(shí)上，任務(wù)集合在速度低于1下是可以調(diào)度的。從以上討論可以看到，需要考慮容錯(cuò)的能耗最小化問(wèn)題不能簡(jiǎn)單地修改LPEDF(low power earliest deadline first)算法來(lái)實(shí)現(xiàn)，需要在調(diào)度過(guò)程中保證調(diào)度結(jié)果是有效的。

表2 任務(wù)集合調(diào)度實(shí)例

為解決單調(diào)優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題，觀察發(fā)現(xiàn)反轉(zhuǎn)的滑動(dòng)窗口一定和之前迭代的窗口相鄰。具體而言，有以下引理：

引理1LPRSW算法從ith～(i-1)th迭代，相應(yīng)的兩個(gè)窗口為Ii和Ii-1。如果Se(Ii)>Se(Ii-1)，則Ii和Ii-1是相鄰的窗口。

證明當(dāng)調(diào)整窗口Ii-1時(shí)，在沒(méi)有重疊的窗口中工作負(fù)載將不發(fā)生變化，僅當(dāng)Ii-1中重疊部分將發(fā)生小部分改變，改變量為Δ，0<Δ≤L(Ii-1)；因此，在下一次迭代中窗口強(qiáng)度將增加。

正如引理1的證明，當(dāng)調(diào)整滑動(dòng)窗口重疊部分中的空閑時(shí)間，并用于備份任務(wù)時(shí)，滑動(dòng)窗口將發(fā)生反轉(zhuǎn)，因此窗口調(diào)整將減少這些任務(wù)的執(zhí)行時(shí)間。為了消除這種反轉(zhuǎn)，將這些任務(wù)融合到之前的窗口中，方法如下：

引理2LPRSW算法從ith～(i-1)th迭代，相應(yīng)的兩個(gè)窗口為Ii和Ii-1。如果Se(Ii)>Se(Ii-1)，則在Ii和Ii-1之間維持任務(wù)集合可調(diào)度的最低恒速是Se(Ii-1)。

證明在調(diào)整滑動(dòng)窗口Ii-1前，所有在任務(wù)集合J剩下的任務(wù)在恒速Se(Ii-1)將是可調(diào)度的。因此，融合的兩個(gè)窗口Ii和Ii-1后任務(wù)集合將是可調(diào)度的。

定理2LPRSW算法滑動(dòng)窗口第1,2,3,…迭代的強(qiáng)度表示為Se1,Se2,Se3，…。Se1是整個(gè)任務(wù)集合在錯(cuò)誤不超過(guò)K個(gè)情況下，保證任務(wù)不發(fā)生錯(cuò)過(guò)截止期限最低恒定速度。

定理3考慮Se1,Se2,Se3,…作為L(zhǎng)PRSW算法滑動(dòng)窗口第1,2,3,…迭代的速度，有Se1≥Se2…≥Sem。

證明因?yàn)閮?yōu)先級(jí)反轉(zhuǎn)在算法LPRSW中被消除，后續(xù)滑動(dòng)窗口的關(guān)系可以很容易地確定。

如果LPRSW算法能夠滿足以下兩個(gè)條件,則可以保證任務(wù)的最后截止期限:

(1)不超過(guò)K個(gè)任務(wù)出錯(cuò)。

(2)?i∈[1,m]，m表示總的迭代次數(shù)，有Sei≤1。

在LPRSW算法中，一個(gè)滑動(dòng)窗口Ii有專屬的預(yù)留空間給任務(wù)執(zhí)行和任務(wù)備份。高優(yōu)先級(jí)任務(wù)Jh有可能和Ii發(fā)生重疊，并將強(qiáng)制在Ii之前完成。類似地，低優(yōu)先級(jí)任務(wù)Jl可能和Ii發(fā)生重疊執(zhí)行，窗口Ii通過(guò)調(diào)整任務(wù)的到達(dá)時(shí)間和截止時(shí)間消除低優(yōu)先級(jí)任務(wù)的執(zhí)行。因此，為了證明定理3，僅需證明如果設(shè)置處理器速度為Sei，即整個(gè)窗口Ii的速度，在最壞情況下(發(fā)生K個(gè)任務(wù)出錯(cuò))所有任務(wù)是可調(diào)度的條件為Sei≤1。

通過(guò)反證法證明:

算法1LPRSW。

1. 任務(wù)集合初始化輸入:

2. 任務(wù)集合:J={J1，J2，…Jn};

3. 處理器支持的最小運(yùn)行速度:Smin

4. 輸出：{S1，S2，…}

5. Si=Smax，for i=1，2，…，n;

6. p=1;{初始化滑動(dòng)窗口下標(biāo)}

7. While J≠Φ do

8. 遍歷任務(wù)集合J，確定下一個(gè)滑動(dòng)窗口I和對(duì)應(yīng)的處理器速度S，p++;

9. If S

10. Si=Smin，?Ji∈J;

11. break;

12. End if

13. If S>Sp-1AND p>1 then

14. Ip&Ip→1Ip//從上次迭代中恢復(fù)任務(wù)的信息，將滑動(dòng)窗口Ip和Ip-1融合成一個(gè)滑動(dòng)窗口;消除優(yōu)先級(jí)反轉(zhuǎn)。

15. p--;

16. End if

17. End While

18. If 任務(wù)出錯(cuò)

19. 根據(jù)LPRSW算法第4步啟動(dòng)容錯(cuò)機(jī)制，更新備份任務(wù)的新速度

20. End if

21. Return{S1，S2，…}

其中：第8行表示當(dāng)前初始滑動(dòng)窗口和它的速度;第9～12行檢查是否當(dāng)前速度小于最小速度，如果小于則終止迭代;第13～16行表示當(dāng)出現(xiàn)反轉(zhuǎn)窗口時(shí)即消除它;第18～20行表示當(dāng)任務(wù)出錯(cuò)時(shí)，重新計(jì)算備份任務(wù)的速度。LPRSW算法的復(fù)雜性主要來(lái)自第8行滑動(dòng)窗口的計(jì)算，因此算法時(shí)間復(fù)雜度為O(n2)。

2.2 多任務(wù)下的共享空閑時(shí)間分配

由于所有任務(wù)在LPRSW算法中都和一個(gè)滑動(dòng)窗口相關(guān)，當(dāng)相應(yīng)的速度被選定時(shí)，所有任務(wù)在滑動(dòng)窗口內(nèi)均可調(diào)度。雖然LPRSW算法在最大出錯(cuò)任務(wù)數(shù)K個(gè)下能夠保證實(shí)時(shí)任務(wù)集合的可調(diào)度性，但是每一個(gè)窗口內(nèi)需要預(yù)留計(jì)算資源給每一個(gè)備份任務(wù)，而實(shí)際系統(tǒng)中，任務(wù)全部出錯(cuò)的概率較少，造成空閑時(shí)間的浪費(fèi)。例如兩個(gè)滑動(dòng)窗口I1和I2，如果出錯(cuò)任務(wù)為一個(gè)且發(fā)生在I1時(shí)，I2將不會(huì)出錯(cuò)，則I2可以將預(yù)留的備份任務(wù)資源全部分給主任務(wù);如果出錯(cuò)任務(wù)發(fā)生在I2，則I1中全部正確執(zhí)行，留下的資源可以供I2提前執(zhí)行任務(wù)。更復(fù)雜的情況，如圖3a～圖3b所示，揭示了多任務(wù)共享空閑時(shí)間情況下的任務(wù)可靠性保證。

重新調(diào)度表1的任務(wù)，所有任務(wù)都在一個(gè)滑動(dòng)窗口內(nèi)。3個(gè)任務(wù)對(duì)應(yīng)需要的容錯(cuò)空閑時(shí)間為R1,R2,R3，其中R3任務(wù)恢復(fù)需要的時(shí)間最多。如圖3c所示，當(dāng)以最高速度執(zhí)行任務(wù)時(shí)，不會(huì)留下多余的空閑時(shí)間，能耗為10。如果系統(tǒng)中有一個(gè)任務(wù)出錯(cuò)，例如最長(zhǎng)任務(wù)J2出錯(cuò)(如圖3a)，則可以將任務(wù)J1和J3的備份資源用于其他任務(wù)調(diào)節(jié)速度，當(dāng)所有空閑時(shí)間都調(diào)節(jié)J1任務(wù)時(shí)，能耗為8.22，相比3c的調(diào)度策略節(jié)約17.8%。另一種情況，如圖3c所示，如果將空閑時(shí)間用于J1和J3，則能耗為6，相比3c的調(diào)度策略節(jié)約40%的能耗。此外，假設(shè)最長(zhǎng)任務(wù)出現(xiàn)錯(cuò)誤進(jìn)行全局預(yù)留資源SR，則實(shí)際中空閑時(shí)間可以進(jìn)一步回收?；厥盏目臻e時(shí)間可以分給不同的任務(wù)共享，從而進(jìn)一步優(yōu)化能耗。因此，新算法在保證可靠性前提下還可以進(jìn)一步降低能耗。

因此，除了共享預(yù)留空閑時(shí)間可以在保證系統(tǒng)可靠性前提下降低能耗外，合理分配空閑時(shí)間也可以降低能耗。新的算法需要解決以下問(wèn)題：

(1)如何將回收的空閑時(shí)間分配給其他任務(wù)，在保證截止期限內(nèi)實(shí)現(xiàn)更低的能耗。

(2)如何在降低能耗和保證系統(tǒng)可靠性之間找到平衡點(diǎn)。

新算法COSALPRSW從功耗模型出發(fā)，代替之前每個(gè)任務(wù)分配一個(gè)備份任務(wù)，其滑動(dòng)窗口的變化和備份任務(wù)個(gè)數(shù)通過(guò)動(dòng)態(tài)共享空閑時(shí)間確定，從而減少任務(wù)備份占用的資源，在保證系統(tǒng)可靠性前提下使能耗更低。

為了評(píng)估每個(gè)任務(wù)的能耗和空閑時(shí)間的使用效率，定義了以速度f(wàn)運(yùn)行的任務(wù)Jk的空閑時(shí)間能耗，空閑時(shí)間—能耗因子：

(13)

在最大頻率fmax處沒(méi)有空閑時(shí)間和能耗節(jié)約，并且任務(wù)的Slack_Energy(fmax)被定義為0。隨著f的減小，節(jié)省能量更多，Slack_Energy增加。由于預(yù)留用于恢復(fù)的空閑時(shí)間的影響，預(yù)期在某一閾值之后，Slack_Energy(f)將增加然后減小。因此，對(duì)于每個(gè)任務(wù)Jk，應(yīng)該存在最佳速度f(wàn)o=(>fk)，使得Slack_Energy(f)最大。

Sk(f)=Ck/f;

(14)

Ek=Ps,k·Sk(f)+h·Pind·Sk(f)+

h·Cef·ck·fm-1。

(15)

由式(13)～式(15)和關(guān)于f的微分Slack_Energy(f)，當(dāng)f滿足時(shí)，可以得到

Slack_Energy(f)′=Ps+h·Pind+

h·Cef-m·h·Cef·fm-1。

(16)

當(dāng)m=2或m=3時(shí)，分別產(chǎn)生立方或四次方程，得到最大化Slack_Energy(f)下的最佳速度

(17)

算法2COSALPRSW。

1. 按照任務(wù)的執(zhí)行時(shí)間降序排列任務(wù)集合，J1，…，Jn;

2. 計(jì)算可以利用的空閑時(shí)間SL=D-W(I);

4. Set fi=fe(i=1，…，n);

5. Set E=Ei(fi);

6. For n=0 to k do

7. If n>0 then

8. SL=SL-Jn

9. end If

10. End for

11. Assign-frequencies({f}，SL);

12. 根據(jù)公式(2)和(7)重新計(jì)算新速度下的系統(tǒng)可靠性Rf和總能耗Etotal;

13. If E>Etotaland Rf

14. Set E=Etotal;

15. Set k=n;//確定全局最優(yōu)備份任務(wù)數(shù)量

16. Set f=fo(i=1，…，n);

17. Else

18. Set f=fmax

19. End if

20. Return k and f1,…,fn

算法3Assign-frequencies。

1. 計(jì)算每個(gè)滑動(dòng)窗口的Slack_Energy(f)，fo和SLk(fo);

2. SLremain=SL;

3. 隊(duì)列中任務(wù)按照Slack_Energy(f)的值降序排列

4. While(Queue=!Φand SLremain> min{Ji|(J1，J2…，Jn)} do

5. If(SLk(fo)<=Sremain)then

6. 分配SLk(fo)給任務(wù)Jk;

7. SLremain-=SLk(fo);

8. Else

9. 將任務(wù)Jk加入到?jīng)]有被選擇的隊(duì)列，等待下一輪調(diào)度

10. End If

11. End While

12. Return fo

對(duì)于給定的任務(wù)集，Slack_Energy值越高，任務(wù)將越節(jié)能。基于這一觀察，提出COSALPRSW算法，該算法根據(jù)空閑時(shí)間—能耗因子決定選擇任務(wù)的順序和速度。首先優(yōu)化備份任務(wù)數(shù)量，共享空閑時(shí)間。其次，根據(jù)剩余的空閑時(shí)間分配給將要調(diào)度的任務(wù)，找到在系統(tǒng)可靠性前提下能耗最小的速度分配策略。任務(wù)集合需要的時(shí)間資源總量為D，可用空閑時(shí)間量為SL=D-W(I)，則可以安排備份的數(shù)量為Ji≤SL。在保留SL個(gè)空閑時(shí)間量用于恢復(fù)出錯(cuò)任務(wù)(以重新執(zhí)行的形式)后，剩余空閑時(shí)間(SL-Ji)可用于縮小所選擇任務(wù)的處理頻率。在算法Assign-frequencies中，SLremain表示剩余空閑時(shí)間量。隊(duì)列用于按照其最大空閑時(shí)間使用效率因子Slack_Energy(f)(行3)的遞減順序?qū)θ蝿?wù)進(jìn)行排序，空閑時(shí)間以該順序分配給任務(wù)，使其能夠以最佳速度(行5～7)運(yùn)行。算法的復(fù)雜度只有O(nlogn)，主要是對(duì)任務(wù)的Slack_Energy(f)值進(jìn)行排序。

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

實(shí)驗(yàn)采用沈陽(yáng)藍(lán)天數(shù)控GJ400，采用支持動(dòng)態(tài)電壓調(diào)節(jié)的64位龍芯3B-1500處理器，該處理器允許調(diào)整的電壓范圍為1.0 V～1.3 V，對(duì)應(yīng)可變的處理器頻率為1.0 GHz～1.5 GHz[20]?；诘湍芎凝埿咎幚砥鞯拈_(kāi)放式數(shù)控系統(tǒng)GJ400如圖4所示，系統(tǒng)分為二次開(kāi)發(fā)層、CNC數(shù)控系統(tǒng)層和運(yùn)動(dòng)控制層。其中低功耗嵌入式平臺(tái)的運(yùn)動(dòng)控制器負(fù)責(zé)進(jìn)給驅(qū)動(dòng)控制、主軸驅(qū)動(dòng)控制和開(kāi)關(guān)量控制，實(shí)現(xiàn)任務(wù)嚴(yán)格的實(shí)時(shí)性要求。低能耗可靠調(diào)度算法部署在CNC數(shù)控系統(tǒng)層。在實(shí)驗(yàn)中，修改操作系統(tǒng)內(nèi)核，以便在創(chuàng)建線程之前，使用系統(tǒng)調(diào)用將獲得的任務(wù)相關(guān)信息發(fā)送到內(nèi)核和調(diào)度程序。當(dāng)任務(wù)調(diào)用Pthread_create()創(chuàng)建線程時(shí)，它會(huì)依次調(diào)用一系列系統(tǒng)調(diào)用函數(shù)，包括Sys_clone()，Do_fork()和Copy_process()函數(shù)。修改后，Copy_process()和Sched_fork()函數(shù)將收集到的任務(wù)執(zhí)行信息反饋到本文的能耗模型和可靠性模型，用于分析所提算法的能耗和可靠性。

本章實(shí)驗(yàn)比較所提出的4個(gè)算法——NODVS，LPRSW-A，LPRSW-H和COSALPRSW算法。其中NODVS算法沒(méi)有采用能耗管理，執(zhí)行任務(wù)按照最高速度執(zhí)行，當(dāng)系統(tǒng)空閑時(shí)將系統(tǒng)置于省電的睡眠狀態(tài)，NODVS算法為其他算法能耗歸一化的對(duì)比算法。數(shù)控系統(tǒng)中執(zhí)行一次插補(bǔ)任務(wù)的周期為6 ms，每次插補(bǔ)計(jì)算的結(jié)果通過(guò)命令寄存器分若干次傳送到伺服控制單元，以控制機(jī)床各個(gè)坐標(biāo)軸的位移，位置控制任務(wù)的周期為3 ms;執(zhí)行一次運(yùn)動(dòng)控制處理任務(wù)為15 ms[5]。系統(tǒng)任務(wù)出錯(cuò)數(shù)K根據(jù)任務(wù)集合和任務(wù)到達(dá)錯(cuò)誤率確定。根據(jù)文獻(xiàn)[17]確定關(guān)鍵實(shí)時(shí)系統(tǒng)中的任務(wù)達(dá)到錯(cuò)誤率在10-10/h～10-5/h之間。如果實(shí)時(shí)系統(tǒng)在復(fù)雜的環(huán)境中，任務(wù)到達(dá)出錯(cuò)率則更高，在10-2/h～102/h之間。NODVS算法的原始故障概率(即1-R0=1-∏Ri(fmax))由PoF(possibility of fault)表示。用能耗和可靠性指標(biāo)來(lái)測(cè)試所提其他算法的性能，分別為在線性速度和離散速度集合測(cè)試算法。每次實(shí)驗(yàn)時(shí)間為10 000個(gè)時(shí)間片，每個(gè)任務(wù)集運(yùn)行10次，將這10次運(yùn)行結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。

3.1 空閑時(shí)間對(duì)系統(tǒng)可靠性的影響

系統(tǒng)可靠性定義為1-PoF，通過(guò)使用故障率模型和執(zhí)行時(shí)間信息計(jì)算系統(tǒng)的可靠性。圖5所示為故障率模型中的指數(shù)d=2時(shí)對(duì)系統(tǒng)可靠性的影響，結(jié)果和NODVS的結(jié)果進(jìn)行歸一，觀察到即使故障率只有適度增加，NODVS仍導(dǎo)致系統(tǒng)可靠性大幅度下降。此結(jié)果符合預(yù)期，因?yàn)镹ODVS使用最高速度執(zhí)行任務(wù)，而不考慮對(duì)可靠性的影響。然而，LPRSW-A，LPRSW-H和COSALPRSW均為可靠性感知方案，是通過(guò)在減少頻率之前保留空閑時(shí)間來(lái)恢復(fù)出錯(cuò)任務(wù)，從而確保系統(tǒng)在故障率急劇增加時(shí)，也能保證系統(tǒng)的可靠性。這與理論結(jié)果一致。隨著空閑時(shí)間的增加，用于容錯(cuò)的時(shí)間增加，可以使系統(tǒng)管理更多的任務(wù)并獲得更低的故障概率。隨著空閑時(shí)間的增加，LPRSW-A的出錯(cuò)率高于LPRSW-H，這是因?yàn)長(zhǎng)PRSW-A算法采用調(diào)整后的速度執(zhí)行出錯(cuò)任務(wù)，執(zhí)行時(shí)間相對(duì)LPRSW-H算法采用最大速度恢復(fù)出錯(cuò)任務(wù)要長(zhǎng)，從而增加了出錯(cuò)機(jī)率。在系統(tǒng)空閑時(shí)間0.6 ms以后，隨著空閑時(shí)間的增加，LPRSW-A和LPRSW-H的出錯(cuò)率表現(xiàn)更明顯，而COSALPRSW算法出錯(cuò)率更低，這是因?yàn)镃OSALPRSW采用全局共享空閑時(shí)間。

3.2 空閑時(shí)間對(duì)能耗的影響

可用空閑時(shí)間對(duì)能量消耗的影響，如圖6所示頻率無(wú)關(guān)功率設(shè)置為Pind=0.05，可用空閑時(shí)間由SL=D-W(I)表示。在圖6中，目標(biāo)可靠性被設(shè)置為原始系統(tǒng)可靠性Rg=1-PoF。開(kāi)始LPRSW-A和LPRSW-H的能耗非常接近，高于COSALPRSW算法。在空閑時(shí)間大于0.7以后，LPRSW-A算法相比LPRSW-H算法節(jié)約的能耗更多，這是因?yàn)榭臻e時(shí)間增多，當(dāng)任務(wù)出現(xiàn)錯(cuò)誤時(shí)，LPRSW-A算法使用DVS調(diào)節(jié)后的速度執(zhí)行。COSALPRSW算法的能耗更低，是因?yàn)镃OSALPRSW算法進(jìn)行恢復(fù)出錯(cuò)任務(wù)分配時(shí)優(yōu)于LPRSW-A和LPRSW-H?？臻e時(shí)間越多，任務(wù)進(jìn)行動(dòng)態(tài)電壓調(diào)節(jié)DVFS和恢復(fù)出錯(cuò)任務(wù)的機(jī)會(huì)越多;并且COSALPRSW算法通過(guò)全局回收空閑時(shí)間再分配能夠?qū)崿F(xiàn)降低能耗。然而，LPRSW-A和LPRSW-H需要為不同的任務(wù)分配單獨(dú)的空閑時(shí)間，因而算法節(jié)能效果低于COSALPRSW算法。平均COSALPRSW算法比LPRSW-A和LPRSW-H算法節(jié)約31.62%和44.4%的能耗。

3.3 系統(tǒng)可靠性對(duì)能耗的影響

圖7所示為可靠性目標(biāo)Rg對(duì)系統(tǒng)能量消耗的影響，空閑時(shí)間SL=1.1·C，Pind=0.05。通過(guò)調(diào)節(jié)任務(wù)的出錯(cuò)率，測(cè)試算法能耗。隨著出錯(cuò)率PoF從10-4改變?yōu)?0-10，所有算法的能耗隨著可靠性目標(biāo)的增加(即降低PoF)變得更高。這是由于需要預(yù)留更多資源來(lái)恢復(fù)出錯(cuò)任務(wù)，以滿足系統(tǒng)的可靠性，從而減少了用于動(dòng)態(tài)調(diào)節(jié)的可用空閑時(shí)間。隨著可靠性的增加，需要更多的資源用于恢復(fù)任務(wù)，并且保證不超過(guò)截止期限，因此能耗急劇上升，當(dāng)PoF=10-11時(shí)，系統(tǒng)可靠性最大，所有算法都以最大頻率fmax運(yùn)行。

4 結(jié)束語(yǔ)

本文研究開(kāi)放式數(shù)控系統(tǒng)的低能耗高可靠性調(diào)度算法。對(duì)LPEDF算法進(jìn)行拓展，使其成為能夠容錯(cuò)的低能耗調(diào)度算法，考慮可能出現(xiàn)的任務(wù)優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題，通過(guò)融合相鄰滑動(dòng)窗口消除優(yōu)先級(jí)反轉(zhuǎn)。提出LPRSW算法，能夠在保證系統(tǒng)可靠性前提下降低系統(tǒng)功耗，同時(shí)將LPRSW算法拓展為以處理器最高速度執(zhí)行出錯(cuò)任務(wù)的LPRSW-H算法和采用DVS技術(shù)調(diào)節(jié)后的執(zhí)行出錯(cuò)任務(wù)的LPRSW-A算法，并分析二者在不同情況下的優(yōu)勢(shì)和不足。在此基礎(chǔ)上，提出一種性能更好的低能耗和可靠性優(yōu)化調(diào)度算法COSALPRSW，該算法對(duì)任務(wù)容錯(cuò)采用共享全局空閑時(shí)間代替預(yù)先給每任務(wù)都分配一個(gè)備份任務(wù)的方法，因此可以回收更多的空閑時(shí)間，大幅度降低系統(tǒng)能耗，同時(shí)提出空閑時(shí)間—能耗因子用于決定任務(wù)動(dòng)態(tài)調(diào)整后的最優(yōu)速度，實(shí)現(xiàn)在保證系統(tǒng)可靠性前提下進(jìn)一步降低系統(tǒng)能耗。通過(guò)實(shí)驗(yàn)對(duì)比，COSALPRSW算法比LPRSW-A和LPRSW-H的效果更好，能平均節(jié)約31.62%和44.4%的能耗。下一步將基于開(kāi)放式數(shù)控系統(tǒng)對(duì)能耗和可靠性的需求，從實(shí)時(shí)任務(wù)模型構(gòu)建、多核處理器能耗分析、實(shí)時(shí)系統(tǒng)穩(wěn)定性以及基于機(jī)器學(xué)習(xí)的調(diào)度算法等方面研究開(kāi)放式數(shù)控系統(tǒng)，并將所提算法進(jìn)行實(shí)際系統(tǒng)驗(yàn)證，從而實(shí)現(xiàn)開(kāi)放式數(shù)控系統(tǒng)高可靠低能耗的目的。