[發明專利]一種多核實時容錯系統中獲取準確的最晚截止時間的方法

有效

• 申請號: 201310739053.0
• 申請日: 2013-12-27
• 公開（公告）號: CN103699455A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 沙行勉;吳剴劼;崔曉通
• 申請（專利權）人: 重慶大學
• 主分類號: G06F11/07
• 分類號: G06F11/07
• 代理公司: 重慶市前沿專利事務所(普通合伙) 50211
• 代理人: 郭云

1.一種多核實時容錯系統中獲取準確的最晚截止時間的方法，其特征在于，包括如下步驟：

S1，根據多核系統的任務調度，在保持原有數據依賴的基礎上，為在同一核上執行的相鄰任務增加調度順序依賴，建立新的有向無環圖；

S2，在新的有向無環圖的基礎上，增加兩個虛擬任務節點，所述虛擬任務的執行時間為0，在以該有向無環圖為模型的任務調度中，其中一個虛擬任務節點最先執行，另外一個虛擬任務節點最后執行；

S3，假設在任務執行過程中最多出現X個軟錯誤，在原有調度的基礎上通過出錯任務在同一核上的立即重新執行來實現容錯，保證任務集合的正確執行，并確定任務集合的關鍵任務，獲取任務集合的準確的最晚截止時間；

S4，衡量任務集合的準確的最晚截止時間是否滿足當前多核實時容錯系統中的工作時限需求，如果滿足，則退出，如果不滿足，則調整調度策略，返回步驟S1。

2.如權利要求1所述的多核實時容錯系統中獲取準確的最晚截止時間的方法，其特征在于，所述步驟S1具體包括如下步驟：

S11，獲取任務集合中任務的個數N，以及任務集合執行過程中可能發生的最大軟錯誤的個數X；

S12，用有向無環圖表示任務間的數據依賴；

S13，根據給定的任務調度，如果兩個任務在同一核上被調度執行并且調度順序相鄰，則增加這兩個任務間的調度順序依賴，并在原來的有向無環圖的基礎上增加表示調度順序依賴的邊，得到新的有向無環圖；

S14，獲取每個任務節點的執行時間存入任務節點的數據結構中，獲取邊的權重存入數組中。

3.如權利要求1所述的多核實時容錯系統中獲取準確的最晚截止時間的方法，其特征在于，所述步驟S2具體步驟為：

在新的有向無環圖基礎上增加兩個節點，源節點和匯聚節點，并設這兩個節點的執行時間為0；對于所有沒有父節點的任務節點，增加一條從源節點到該節點的邊；對于所有沒有子節點的任務節點，增加一條從該節點到匯聚節點的邊，同時將所有與源節點和匯聚節點相連的邊的權重設為0。

4.如權利要求1所述的多核實時容錯系統中獲取準確的最晚截止時間的方法，其特征在于，所述步驟S3具體包括如下步驟：

S31，初始化每個任務的最早截止時間為所有任務都不發生錯誤時該任務的完成時間；初始化每個任務的最晚截止時間為0；

S32，以一個任務節點I作為輸入，該任務可以是任何一個節點；如果該任務節點I的最晚截止時間大于0，說明該任務節點已經被計算過，直接返回其最晚截止時間及其關鍵任務；如果該任務節點的父節點集合包含源節點，則該任務的關鍵任務是它本身，通過讓該任務發生所有錯誤來獲得該任務的最晚截止時間；否則進入下一步驟；

S33、遞歸的遍歷求解該任務節點I的所有父節點的最晚截止時間以及對應的關鍵任務；

S34、假設任務I共有m個父節點，且它們的最晚截止時間分別為F(I)₁,F(I)₂,…,F(I)_m，分別在F(I)₁,F(I)₂,…,F(I)_m的基礎上計算任務I的完成時間，分別為I₁,I₂,…,I_m，同時計算其他任務都不發生錯誤而只有任務I發生所有X個軟錯誤的完成時間I₀，將I₀與I₁,I₂,…,I_m進行比較，選取最大的作為任務I的最晚截止時間，同時確定該任務節點I的關鍵任務是其本身還是S33中所求得的關鍵任務。