[發(fā)明專利]一種適用于數(shù)控系統(tǒng)容錯(cuò)調(diào)度的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210445612.2
• 申請(qǐng)日: 2012-11-09
• 公開（公告）號(hào): CN103810025A
• 公開（公告）日: 2014-05-21
• 發(fā)明（設(shè)計(jì)）人: 郭銳鋒;劉嫻;王鴻亮;張憶文
• 申請(qǐng)（專利權(quán)）人: 中國科學(xué)院沈陽計(jì)算技術(shù)研究所有限公司
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46;G06F11/07
• 代理公司: 沈陽科苑專利商標(biāo)代理有限公司 21002
• 代理人: 許宗富

技術(shù)領(lǐng)域

本發(fā)明涉及實(shí)時(shí)系統(tǒng)領(lǐng)域的任務(wù)容錯(cuò)調(diào)度技術(shù)，具體是一種適用于數(shù)控系統(tǒng)的容錯(cuò)實(shí)時(shí)調(diào)度算法。?

背景技術(shù)

實(shí)時(shí)系統(tǒng)的正確運(yùn)行不僅要求系統(tǒng)中的實(shí)時(shí)任務(wù)在規(guī)定時(shí)限內(nèi)正確完成，還要求系統(tǒng)在發(fā)生單個(gè)或多個(gè)錯(cuò)誤時(shí)仍然可以保證任務(wù)的正確執(zhí)行。數(shù)控系統(tǒng)作為一種典型的實(shí)時(shí)應(yīng)用系統(tǒng)，控制數(shù)控機(jī)床高精度、高效率地完成各種加工任務(wù)。機(jī)床加工過程中任何不可靠因素導(dǎo)致的實(shí)時(shí)任務(wù)失效，都可能嚴(yán)重影響工件的加工質(zhì)量，甚至造成安全生產(chǎn)隱患。為了提供系統(tǒng)的容錯(cuò)能力，目前已經(jīng)提出了多種容錯(cuò)模型。基于檢查點(diǎn)的回卷回復(fù)容錯(cuò)模型通過在任務(wù)執(zhí)行過程中創(chuàng)建檢查點(diǎn)，并在任務(wù)出錯(cuò)時(shí)回卷恢復(fù)到最近的檢查點(diǎn)狀態(tài)執(zhí)行的機(jī)制提供容錯(cuò)。此模型在系統(tǒng)無故障的情況下加大了系統(tǒng)的執(zhí)行開銷。基于主替代版本的容錯(cuò)模型為每個(gè)實(shí)時(shí)任務(wù)提供主版本和替代版本。主版本實(shí)現(xiàn)較完善的功能，并提供更精確的執(zhí)行結(jié)果，其復(fù)雜度高因而出錯(cuò)概率較大。替代版本僅實(shí)現(xiàn)任務(wù)的基本功能，并提供系統(tǒng)可接受的低精確度結(jié)果，其復(fù)雜度低因而出錯(cuò)概率小。在正常情況下任務(wù)執(zhí)行主版本，并為替代版本預(yù)留足夠的執(zhí)行時(shí)間。當(dāng)主版本成功完成時(shí)，釋放其替代版本的預(yù)留時(shí)間。當(dāng)主版本執(zhí)行出錯(cuò)后，調(diào)度執(zhí)行其替代版本。此模型在系統(tǒng)無故障的情況下不會(huì)增加系統(tǒng)的執(zhí)行開銷，在系統(tǒng)出錯(cuò)時(shí)，替代版本能夠保證任務(wù)的實(shí)時(shí)性與可靠性。?

經(jīng)過對(duì)現(xiàn)有技術(shù)的文獻(xiàn)檢索發(fā)現(xiàn)，Ching-Chih?Han等人發(fā)表的《AFault-Tolerant?Scheduling?Algorithm?for?Real-Time?Periodic?Tasks?with?PossibleSoftware?Faults》（刊物《IEEE?Transactions?on?Computers》2003,52(3):362-372）對(duì)主替代版本模型下的容錯(cuò)實(shí)時(shí)調(diào)度算法進(jìn)行研究，提出了基于截止期限機(jī)制的BCE算法。BCE算法集成了Basic、CAT與EIT三個(gè)子算法。其中Basic算法作為BCE的主體實(shí)現(xiàn)容錯(cuò)實(shí)時(shí)調(diào)度，首先采用實(shí)時(shí)調(diào)度算法從后往前生成任?務(wù)集替代版本的反向調(diào)度序列，以確定需為替代版本預(yù)留的執(zhí)行時(shí)間，任務(wù)集運(yùn)行時(shí)在余下的時(shí)間間隔內(nèi)從前往后正向調(diào)度主版本執(zhí)行。CAT算法通過預(yù)測主版本的可執(zhí)行性，選擇可行的主版本執(zhí)行，EIT算法在系統(tǒng)空閑時(shí)選擇替代版本提前執(zhí)行，二者輔助Basic算法，避免CPU處理時(shí)間的浪費(fèi)，改善BCE算法的調(diào)度性能。韓建軍等人在《基于軟件容錯(cuò)的動(dòng)態(tài)實(shí)時(shí)調(diào)度算法》（期刊《計(jì)算機(jī)研究與發(fā)展》2005,42(2):315-321）中對(duì)CAT算法的預(yù)測性進(jìn)行改進(jìn)，提出了PKSA（EBPA）和CUBA算法，更有效地減少CPU處理時(shí)間的浪費(fèi)。?

在已有研究中，反向調(diào)度過程均采用順序調(diào)度，即任務(wù)集反向調(diào)度時(shí)的優(yōu)先級(jí)次序與其運(yùn)行時(shí)的優(yōu)先級(jí)次序相同。當(dāng)高優(yōu)先級(jí)任務(wù)替代版本的預(yù)留時(shí)間與低優(yōu)先級(jí)任務(wù)替代版本的預(yù)留時(shí)間沖突時(shí)，低優(yōu)先級(jí)任務(wù)的通知時(shí)間提前。由于運(yùn)行時(shí)高優(yōu)先級(jí)任務(wù)先于低優(yōu)先級(jí)任務(wù)執(zhí)行，高優(yōu)先級(jí)主版本正確完成后，除了釋放其替代版本的預(yù)留時(shí)間，還需同步更新余下替代版本的通知時(shí)刻，這將增加容錯(cuò)實(shí)時(shí)調(diào)度算法的在線運(yùn)行開銷。?

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)中反向調(diào)度過程會(huì)大幅增加容錯(cuò)調(diào)度算法的在線運(yùn)行開銷的不足，本發(fā)明要解決的技術(shù)問題是提供一種逆序反向調(diào)度方法。?

本發(fā)明為實(shí)現(xiàn)上述目的所采用的技術(shù)方案是：一種適用于數(shù)控系統(tǒng)容錯(cuò)調(diào)度的方法，包括以下步驟?

步驟1）為數(shù)控系統(tǒng)中每個(gè)實(shí)時(shí)任務(wù)的功能定義兩種實(shí)現(xiàn)：主版本和替代版本；?

步驟2）按照固定優(yōu)先級(jí)調(diào)度算法確定數(shù)控系統(tǒng)的實(shí)時(shí)任務(wù)集的運(yùn)行時(shí)優(yōu)先級(jí)序列；?

步驟3）按照與實(shí)時(shí)任務(wù)集運(yùn)行時(shí)優(yōu)先級(jí)序列相反的次序，離線生成任務(wù)集替代版本的反向調(diào)度序列；?

步驟4）數(shù)控系統(tǒng)運(yùn)行時(shí)，正向調(diào)度任務(wù)集中各實(shí)時(shí)任務(wù)的主版本，當(dāng)主版本在其替代版本的最晚啟動(dòng)時(shí)刻之前正確完成，則釋放期替代版本的預(yù)留執(zhí)行時(shí)間；否則撤銷主版本的執(zhí)行，并在最晚啟動(dòng)時(shí)刻開始執(zhí)行替代版本，替代版本啟動(dòng)?后具有最高執(zhí)行優(yōu)先級(jí)，能夠搶占任意主版本執(zhí)行。?

所述主版本實(shí)現(xiàn)任務(wù)的全部功能。?

所述替代版本為主版本的精簡，只實(shí)現(xiàn)系統(tǒng)可接受的任務(wù)的基本功能。?

所述替代版本在反向調(diào)度過程中，占用的時(shí)間間隔為運(yùn)行時(shí)為其預(yù)留的執(zhí)行時(shí)間，結(jié)束時(shí)刻即為其在運(yùn)行時(shí)的最晚啟動(dòng)時(shí)刻。?

所述所有替代版本之間在一個(gè)T內(nèi)的時(shí)間沖突表示為集合：?