基于級聯調度的相關性任務集共享資源沖突消解算法

沈陽

（廣州工程技術職業學院 信息工程學院，廣東 廣州 510075）

0 引 言

分布式多處理器系統的處理器之間的結構可以是多種的，如SMP、NoC-MP、Mesh-MP。不同的來源導致它們之間的關系不同，如共享主存與總線的結構、基于片上網絡交換的結構。另外，一個或多個相關性任務集執行過程中，某些子任務之間不存在直接相關性，它們可以被分配在不同的處理器上并發執行。它們可能會在某個時間段產生對存儲器、網絡及外設之類的共享資源的共用、競爭和協同，從而在這些任務間產生間接相關性。

文獻[2]面向時間約束網絡STN，提出的基于度的自動沖突消解方法，任務在執行過程中若無法在執行時間窗口執行，則動態找出沖突源及其數量，并由系統及時調整約束以達到消解潛在的資源沖突。文獻[3，4]使用Petri網模型提出基于優先級的資源沖突檢測和消解算法。文獻[5]從資源總量角度，整體對任務的需求進行規劃，在任務優先級約束條件下對資源進行匹配，從而提高資源共享和使用效率，降低資源的沖突。李津等人在移動邊緣計算網絡中任務調度與資源配置方面展開的研究，將邊緣計算卸載的時延，通過排隊論的方式進行建模，求解該模型需要進行混合整數非線性規劃。通過拆分子問題分別求解的方式，提出了聯合資源分配和任務調度算法。

文獻[7]對相關性任務之間的競爭問題展開研究，評估了在不同控制要求下的一致性問題。文獻[8]從概念層面分析了沖突產生的原因，并對資源組織和資源利用進行了規范化描述。在此基礎上，提出了時間、資源和任務約束下的任務分解、調度和沖突解決模型。文獻[9，10]提出兩階段優化算法，第1階段是項目時序約束優化階段，采用蟻群算法（ACO）進行任務列表的優化求解，通過對信息素增量規則的改進、串聯進度生成機制（SSGS）及資源沖突消解策略的使用，使蟻群算法的求解效率和質量得以提高；第2階段是資源約束優化階段，以第1階段求得的優化任務列表為輸入，逐項對人力資源約束進行核查與調整，最終生成項目調度的優化方案。文獻[11]采用了多個調度代理通過共享的集群資源使用狀態信息并發地進行調度決策工作，然后通過沖突檢測算法解決這些并發生成的調度決策之間沖突問題。

上述文獻研究從各個角度對共享資源沖突消解展開研究，但沒有深入考慮并發任務對多種共享資源的使用情況，以及由時間特性而導致的資源沖突問題，這里的共享資源指在某一時刻只能被一個任務所占用，具有排他性。由于子任務的并發性，在某一時刻可能會出現多個子任務競爭某類共享資源的情況，當子任務對該類共享資源的需求總量超出該資源的總量時就會引發沖突甚至死鎖。為此需要提前檢查調度方案中可能出現的資源沖突狀況，并通過調整相關任務的時間關系，從而實現資源沖突的消解，使并發任務可以順利且盡快執行完成。

1 相關計算模型的定義

設在某段時刻[t-,t+]存在并發任務序列：T={t |=1,2,…,，系統中的共享資源集用R={R|=1,2,…,表示，其中R表示一種共享資源類型，共享資源R的資源總數記為||。用 表示任務t所需資源R的數量，任務t在其整個執行時間x內對資源R的占用量記為j，即 ，整體表示為t(x)|R(j),…,R（k)，例如(40)|(20),(10)表示任務的執行時間為40，該任務在執行時對資源的占用量為20，對資源的占用量為10。

圖1給出一個具有共享資源競爭關系的相關性任務集示例圖，其中直接相關性指任務間具有緊前約束關系，在圖中用實線箭頭表示，間接相關性指任務間存在資源競爭關系，在圖中用虛線和雙虛線表示。表1是該相關性任務集中各任務的執行時間和所需共享資源類型及數量。

圖1 具有共享資源競爭關系的相關性任務集示例圖

表1 任務執行時間和所需資源情況

假設系統中存在的資源數量為：||=40，||=20，||=20。由表1中執行時間以及共享資源使用狀況可知，任務、和對資源的使用上存在沖突，任務、和對和資源的使用上存在沖突。那么{,,}和{,,}這兩個任務集合內部存在間接相關性，這兩個間接相關性表示為：TR={,,}和TR={,,}。為表示任務間的直接相關性和間接相關性，本文引入2種連接邊，即FS和SS，FS表示“完成－開始”的關系，即原有的直接依賴關系（一般來說FS= =0）；SS表示“開始－開始”的關系，是資源沖突引起并發任務間的滯后關系。例如SS=10表示并發任務和存在資源沖突，使開始執行后10個單位時間才能執行。

相關性任務集中由關鍵任務組成的最長路徑為關鍵路徑。而本文的相關性任務集中存在兩種關鍵任務形式：（1）直接前驅任務約束條件下，自由時差為0的后繼任務，若任務自由時差不為0，則該任務不是關鍵任務。（2）共享資源約束條件下，資源自由時差為0的任務，資源自由時差（Resource Free Float, RFF）是指任意任務t在使用某種共享資源時，由于其他任務也在等待該資源，因為任務t沒有彈性使用該資源的自由時間，例如RFF=0，則說明任務t是資源約束下的關鍵任務，若RFF=10說明任務t可以延遲10個時間單位執行，即任務t不是關鍵任務。

2 資源沖突消解算法

本文的資源沖突消解算法MRMTCD（Multi-resource multi-task conflict digestionalgorithm, MRMTCD）首先按相應規則（2.1節）確定并發任務優先級和共享資源優先級，并給出單資源沖突消解算法（2.2節），然后在單資源沖突消解算法的基礎上，通過級聯調度的方式實現多資源多任務沖突消解算法（2.3節），最終實現整個相關性任務集的資源沖突消解過程。

2.1 優先級獲取原則

2.1.1 任務優先級

本文資源沖突消解算法中任務選擇順序取決于任務優先級的高低。若產生資源沖突的并發任務中存在關鍵任務，則關鍵任務優先進行資源分配。若并發任務中存在多個關鍵任務或全部為非關鍵任務，采用先來先服務原則，先處理關鍵任務的資源請求，再處理非關鍵任務的資源請求。若兩個任務的最早開始時間相同，則按最小自由時差優先的原則確定調度順序。

2.1.2 資源優先級

如果出現同一任務請求多種資源或者多個并發任務競爭多種資源的情況，就必須考慮這些資源的優先級問題，由于不同類型的資源（如通信線路、訪存等）很難用同一種單位的數據直接量化，因此本文采用計算資源的負載率來表示資源的優先級，資源負載率是指在同一時間段存在多種資源沖突時，各資源的最大使用率，是在這個時間段中該資源最大使用量與資源容量之比。

例如共享資源R的負載率的計算為：首先在找出TR并發任務集中的最早開始時間（如式（1））和最晚結束時間（如式（2）），然后找出該時間段中R的最大占用量maxR（如式（3）（4）），最后用maxR與|R|之比求出R的負載率maxRLoadR（如式（5））。

2.2 單資源沖突消解算法

單資源沖突消解算法按任務優先級依次進行任務和共享資源的分配，用當前任務所需資源量與剩余資源量進行比較，如果剩余資源量滿足該任務的資源需求，則進行資源分配，該任務沒有SS緊前約束，不受資源約束限制，如果剩余資源量不能滿足該任務的資源需求，則該任務的執行開始時間逐步后移，直到某一時刻該資源的剩余資源量滿足該任務的資源需求。

下面給出單資源沖突消解算法的流程描述：

輸入：相關性任務集TR，需要使用資源R的并發任務集TR，資源R的剩余資源數RR

輸出：沖突消解后的并發任務集TR

步驟1：當并發任務集TR為空時結束本算法，否則按公式6從TR中取出優先集最高的任務t（優先集獲取原則見上一節），并跳轉到步驟2。

步驟2：計算任務t的最早開始時間ES，并跳轉到步驟3。

步驟4：重新計算TR的關鍵路徑，并跳轉到步驟1。

2.3 多資源沖突消解算法

多資源沖突消解算法按資源優先級對沖突資源進行排序，先處理負載率高的沖突資源。多資源沖突消解過程其實是單資源沖突消解的級聯調度過程。該算法分時間段進行資源沖突消解，可以減少任務間耦合的產生，并使相關性任務集的整體完成時間延遲最小化。

下面給出多資源沖突消解算法的流程描述：

步驟1：以式（9）計算T中所有任務的最早開始時間ES，并跳轉到步驟2。

步驟2：遍歷T，依次獲取任務，該任務尚未進行資源沖突消解，否則，結束該算法。

步驟3：遍歷R，獲取任務所使用的所有資源類型，計算這些資源的負載率，并按負載率非遞增排序，放入隊列QueueR中。

步驟4：當QueueR為空時跳轉到步驟5，否則依次取出隊首資源R，并按以下步驟進行處理。

（1）使用2.2節的單資源沖突消解算法計算TR中所有任務的最早開始時間ES，同時更新連接邊（FS）的集合。

（2）添加延遲關系邊(SS)，即優先獲取資源的任務與延遲獲取該資源的任務之間建立“開始—開始”的延遲關系。

（3）計算TR中任務的所有后續任務的最早開始時間，并更新連接邊。

步驟5：計算各個任務的資源自由時差：

（1）首先計算直接依賴關系FS中，以任務為直接前驅時，即任務的最晚開始時間LS。

（2）各個任務的資源自由時差RFF。

步驟6：重新計算關鍵路徑，RFF=0的任務為關鍵任務，并跳轉到步驟2。

3 實例分析

以圖1和表1給出的相關性任務集為例，根據多資源沖突消解算法自左向右解決資源沖突，依次找出資源沖突任務集TR={,,}和TR={,,}。按照任務優先級獲取原則進行依次調度，若存在多任務多資源沖突情況，則按照資源優先級（資源負載率）進行調度。表2給出了資源沖突消解完成后的任務調度情況，表3給出了在資源沖突消解完成的基礎上進行和資源沖突消解完成后的任務調度情況。圖2給出了在資源沖突消解完成時相關性任務集共享資源沖突消解調度結果圖。

表2 R1資源沖突消解完成后數據

表3 R2和R3資源沖突消解完成后數據

圖2 相關性任務集共享資源沖突消解結果

圖3示出的相關性任務集，在圖1的基礎上添加了基于資源沖突消解的SS連接邊，使在該相關性任務集在資源約束條件下建立了關鍵路徑的連通性，圖中灰色底紋的任務是資源自由時差RFF=0的關鍵任務。關鍵路徑為→→→→→，說明在資源沖突消解完成后，整個相關性任務集的完成時間為120個單位時間，比原先任務集延遲了20個單位時間。

圖3 添加了基于資源沖突消解的SS連接邊的相關性任務集

4 結 論

本文基于關鍵路徑和資源使用率優先調度而提出了一種共享資源沖突消解算法，屬于啟發式算法，它能夠實現多資源多任務并發情況下的有效調度。與目前領域中共享資源約束下任務調度的研究成果相比，本算法有如下創新點：（1）給出了基于共享資源競爭關系的相關性任務集的表示方式。（2）提出了基于級聯調度的資源沖突消解的算法，通過分時間段利用任務優先級和資源優先級進行沖突消解。因此本算法對于深入研究分布式多處理器環境下任務并發調度優化具有相應意義，同時對實際情況上相關性任務受多資源約束這一現實問題的研究取得一定的進展。