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

有效

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

技術領域

本發明涉及領域，具體涉及一種多核實時容錯系統中獲取準確的最晚截止時間的方法。

背景技術

多核實時系統的實時應用通常由很多任務組成，并且要求這些任務需要在截止時間前完成。例如在一個多核實時系統中，任務之間具有依賴關系，一般用有向無環圖來表示這些任務。

圖1（a）是一個任務調度圖，表示出了圖中任務的調度執行順序，即任務被分配到哪一個核上執行，以及開始執行時間。任務在某一個核上執行過程中有可能發生軟錯誤，為了保證得到正確的結果，必須提供容錯。一種簡單并且常見的方法是讓該任務在同一核上立即重新執行，如圖1（b）所示，圖中陰影是發生錯誤的任務。

現有方法中，多核實時容錯系統中實時應用截止時間的計算方法是讓每個核上具有最長執行時間的任務發生所有錯誤以獲得每個核上任務的最晚截止時間，如果任務之間沒有依賴關系，這種計算方法是準確的。例如圖1(b)中，分別每個核上具有最長執行時間的任務發生兩個錯誤，任務T4發生兩次錯誤的截止時間是19個時間單位，任務T2發生兩次錯誤的截止時間是15個時間單位，任務T3發生兩次錯誤的截止時間是14個時間單位，因此該多核實時系統應用運行的最優截止時間是19個時間單位。但是，如果任務之間有依賴關系，這種方法就不準確。例如，圖1（a）中6個任務分配在三個核上。圖中的箭頭表示任務之間的數據依賴關系，在同一核上和不同核上的任務之間的通信延遲分別被假定為0和1。圖1（c）顯示的情況下，T4發生兩次故障，截止時間是19個時間單位。而圖1（d）中，處理器P0執行的任務T2發生兩次故障，截止時間是20個時間單位。很明顯，圖1（d）中所示情況更糟糕。因此，現有截止時間的計算方法可能低估了真實情況。

另外，由于每個任務發生錯誤的個數不確定，現有方法是窮舉所有可能的情況，進行比較，然后選擇截止時間。這種方法的缺點是：當確定每個任務發生多少個錯誤之后，獲得任務集合的最晚截止時間的時間復雜度為O(N²)，但是由于需要考慮所有情況：N個任務發生X個錯誤共有種情況，因此總的時間復雜度為非常浪費時間。

發明內容

為了克服上述現有技術中存在的缺陷，本發明的目的是提供一種多核實時容錯系統中獲取準確的最晚截止時間的方法，本發明能夠高效快速地獲得任務集合的最晚截止時間。

為了實現本發明的上述目的，本發明提供了一種多核實時容錯系統中獲取準確的最晚截止時間的方法，其包括如下步驟：

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

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

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

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

在本發明的一種優選實施方式中，所述步驟S1具體包括如下步驟：

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

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

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

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

在本發明的另一種優選實施方式中，所述步驟S2具體步驟為：

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

在本發明的一種優選實施方式中，所述步驟S3具體包括如下步驟：

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