[發明專利]一種用于分布式系統的雙目標快速優化任務調度方法

有效

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

1.一種用于分布式系統的雙目標快速優化任務調度方法，所述方法至少包含以下幾個步驟：

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

步驟二、將每一個任務在其可靠性最大的可用處理器上進行復制，直至每一個任務的實時可靠性滿足可靠性目標；

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

步驟四、根據應用可靠性與可靠性目標的大小關系，將滿足可靠性目標所需要復制的副本數下限|need|個任務分別在其可靠性最大的可用處理器上進行一次復制，至少包括以下幾個步驟：

1)將所有任務按實時可靠性由大到小進行排序，得到R(n_seq(i))：

2)將R(n_seq(i))按由大到小的順序作乘積，直至乘積小于可靠性目標R_req(G)，得到滿足可靠性目標所需要復制的副本數下限：

式中，n表示在不增加冗余的情況下，該應用中最多只有n個任務的可靠性乘積可以滿足可靠性目標R_req(G)，即至少有need＝num_t-n個任務仍需要至少1次復制，num_t表示任務數；

3)若need＝0，則當前的應用可靠性能夠滿足可靠性目標，進行步驟6)，否則進行步驟4)；

4)將need個當前滿足可靠性目標所需要復制的副本數下限的任務分別在其可靠性最大的可用處理器上進行一次復制，得到新的實時可靠性R(n_i)：

5)反復對任務的實時可靠性進行排序、作乘積并對相應任務進行復制，直至need＝0；

6)確定應用的可靠性，計算如下：

式中，N表示滿足可靠性目標所需的副本數下限的任務數；

7)確定應用的冗余數，計算如下：

8)計算應用的運行時間，計算如下：

RT＝FT-ST； (8)

其中，RT表示應用中任務進行調度的運行時間，ST表示調度開始時間，FT表示調度結束時間；

步驟五、重復步驟三和步驟四直至應用可靠性滿足可靠性目標為止；

步驟六、確定應用的可靠性、冗余數、運行時間。

2.根據權利要求1所述的用于分布式系統的雙目標快速優化任務調度方法，其特征在于將每一個任務在其可靠性最大的可用處理器上進行復制，直至每一個任務的實時可靠性滿足可靠性目標的過程，至少還包括以下步驟：

1)計算各任務在各處理器上的可靠性：

式中，n_i表示應用中的第i個任務，u_k表示處理器集中的第k個處理器，w_i,k表示任務n_i在處理器u_k上的執行時間，λ_k表示第k個處理器的故障率，計算每一個任務在不同處理器上的可靠性，并保存在二維數組r[x][y]，其中x表示任務數，y表示處理器數；

2)將每一個任務在不同處理器上的可靠性由大到小進行排序，即對二維數組中的每一行數據由大到小進行排序，排序后二維數組r[x][y]的第i行數據表示任務n_i在各處理器上經由大到小排序后的可靠性值；

3)設置可靠性目標R_req(G)；

4)提升每個任務的實時可靠性R(n_i)，直至其滿足可靠性目標R_req(G)，其計算公式如下：

式中，num_i表示任務n_i的實時副本數。