[發(fā)明專利]一種用于分布式系統(tǒng)的雙目標(biāo)快速優(yōu)化任務(wù)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201811018403.3
• 申請日: 2018-08-31
• 公開（公告）號: CN109240817B
• 公開（公告）日: 2021-11-02
• 發(fā)明（設(shè)計）人: 朱江;王禮贊;劉昊霖;許海霞;田淑娟;裴廷睿;鄧清勇;李哲濤
• 申請（專利權(quán)）人: 湘潭大學(xué);賽爾網(wǎng)絡(luò)有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 長沙市護(hù)航專利代理事務(wù)所(特殊普通合伙) 43220
• 代理人: 莫曉齊

本發(fā)明提出一種用于分布式系統(tǒng)的雙目標(biāo)快速優(yōu)化任務(wù)調(diào)度方法。本發(fā)明步驟：首先，計算應(yīng)用中各任務(wù)在各處理器上執(zhí)行的可靠性，并對該可靠性按大小排序；然后，將各任務(wù)在其可靠性最大的可用處理器上進(jìn)行復(fù)制，直至各任務(wù)的實時可靠性滿足可靠性目標(biāo)；第三，將各任務(wù)的實時可靠性按大小排序并作乘積，直至乘積小于可靠性目標(biāo)，得到滿足可靠性目標(biāo)所需的副本數(shù)下限(n個)；第四，根據(jù)應(yīng)用的可靠性與可靠性目標(biāo)的大小關(guān)系，將實時可靠性最小的n個任務(wù)分別在其可靠性最大的可用處理器上復(fù)制一次；第五，重復(fù)步驟三和步驟四直至應(yīng)用的可靠性滿足可靠性目標(biāo)為止；最后，確定應(yīng)用的可靠性，冗余數(shù)，運行時間。本發(fā)明具有高效率、低冗余的優(yōu)點。

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

本發(fā)明涉及分布式系統(tǒng)領(lǐng)域，尤其涉及該領(lǐng)域中雙目標(biāo)快速優(yōu)化任務(wù)調(diào)度方法。

背景技術(shù)

分布式系統(tǒng)是一種為了提高并行處理速度而提出的體系架構(gòu)。分布式系統(tǒng)通過通信網(wǎng)絡(luò)將不同地點的，或具有不同功能的，或擁有不同數(shù)據(jù)的多個處理器連接起來，在系統(tǒng)的統(tǒng)一管理控制下，協(xié)調(diào)地完成大規(guī)模信息處理任務(wù)。處理器種類和數(shù)量的不斷增加為分布式系統(tǒng)帶來了更強大的功能和更顯著的性能。正因如此，分布式系統(tǒng)在工業(yè)領(lǐng)域被廣泛應(yīng)用。

可靠性是衡量分布式系統(tǒng)性能的一個重要指標(biāo)，它反映了成功執(zhí)行任務(wù)調(diào)度的概率。受高溫、輻射、電磁干擾、振動及其他因素的影響，隨機硬件故障的發(fā)生往往無法避免。因此，系統(tǒng)中執(zhí)行的任何應(yīng)用都不可能保證100％的可靠。在實際運行中，只要應(yīng)用的實際可靠性能夠滿足既定的可靠性目標(biāo)，就認(rèn)為該應(yīng)用的執(zhí)行是可靠的，否則認(rèn)為該應(yīng)用的執(zhí)行存在風(fēng)險。為了使應(yīng)用的實際可靠性滿足可靠性目標(biāo)，通常采用基于復(fù)制的容錯機制來提升可靠性。盡管通過基于復(fù)制的容錯機制提升應(yīng)用的可靠性行之有效，但分布式系統(tǒng)中的硬件和資源有限，無節(jié)制的復(fù)制會導(dǎo)致硬件和資源的嚴(yán)重浪費和消耗殆盡。以分布式的汽車系統(tǒng)為例，每個電子控制單元的價格為25美元至110美元，如果電子控制單元的數(shù)量不被限制，硬件成本將大幅增長，且不必要的復(fù)制將不可避免地導(dǎo)致更多的信息傳輸，從而造成更大的資源開銷。因此，對于分布式系統(tǒng)而言，找到滿足可靠性目標(biāo)前提下的理想冗余值至關(guān)重要。

目前最新的HRRM方法和ERRM方法能夠在滿足可靠性目標(biāo)的前提下減少冗余。但是，通過HRRM方法進(jìn)行雙目標(biāo)優(yōu)化的冗余值仍然較大，而通過ERRM方法進(jìn)行雙目標(biāo)優(yōu)化的運行時間較長。

本發(fā)明針對它們的不足進(jìn)行改進(jìn)，并提出了一種既能夠滿足可靠性目標(biāo)又能夠最小化冗余值的雙目標(biāo)快速優(yōu)化解決方案，它能夠在滿足可靠性目標(biāo)的前提下獲得理想的冗余值。

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

針對現(xiàn)有技術(shù)的不足，本發(fā)明提出一種用于分布式系統(tǒng)的雙目標(biāo)快速優(yōu)化任務(wù)調(diào)度方法，該方法能在保證可靠性目標(biāo)的前提下以最高效率獲取理想冗余值。

本發(fā)明通過以下方案實現(xiàn)：

步驟一、計算每一個任務(wù)在不同處理器上的可靠性，并按照大小排序，得到每一個任務(wù)復(fù)制時選擇處理器的先后順序；

步驟二、將每一個任務(wù)在其可靠性最大的可用處理器上進(jìn)行復(fù)制，直至每一個任務(wù)的實時可靠性滿足可靠性目標(biāo)；

步驟三、將每一個任務(wù)的實時可靠性按大小排序并作乘積，直至乘積小于可靠性目標(biāo)，得到滿足可靠性目標(biāo)所需要復(fù)制的副本數(shù)下限|need|個任務(wù)；

步驟四、根據(jù)應(yīng)用可靠性與可靠性目標(biāo)的大小關(guān)系，將滿足可靠性目標(biāo)所需要復(fù)制的副本數(shù)下限|need|個任務(wù)分別在其可靠性最大的可用處理器上進(jìn)行一次復(fù)制；

步驟五、重復(fù)以上步驟三和步驟四直至應(yīng)用可靠性滿足可靠性目標(biāo)為止；

步驟六、確定應(yīng)用的可靠性、冗余數(shù)、運行時間。

本發(fā)明具有以下優(yōu)點：

1、本發(fā)明所獲取的應(yīng)用可靠性能夠滿足既定的可靠性目標(biāo)，保證了系統(tǒng)的安全運行；