基于級聯(lián)調(diào)度的相關(guān)性任務(wù)集共享資源沖突消解算法

沈陽

（廣州工程技術(shù)職業(yè)學(xué)院 信息工程學(xué)院，廣東 廣州 510075）

0 引 言

分布式多處理器系統(tǒng)的處理器之間的結(jié)構(gòu)可以是多種的，如SMP、NoC-MP、Mesh-MP。不同的來源導(dǎo)致它們之間的關(guān)系不同，如共享主存與總線的結(jié)構(gòu)、基于片上網(wǎng)絡(luò)交換的結(jié)構(gòu)。另外，一個(gè)或多個(gè)相關(guān)性任務(wù)集執(zhí)行過程中，某些子任務(wù)之間不存在直接相關(guān)性，它們可以被分配在不同的處理器上并發(fā)執(zhí)行。它們可能會在某個(gè)時(shí)間段產(chǎn)生對存儲器、網(wǎng)絡(luò)及外設(shè)之類的共享資源的共用、競爭和協(xié)同，從而在這些任務(wù)間產(chǎn)生間接相關(guān)性。

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

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

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

1 相關(guān)計(jì)算模型的定義

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

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

圖1 具有共享資源競爭關(guān)系的相關(guān)性任務(wù)集示例圖

表1 任務(wù)執(zhí)行時(shí)間和所需資源情況

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

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

2 資源沖突消解算法

本文的資源沖突消解算法MRMTCD（Multi-resource multi-task conflict digestionalgorithm, MRMTCD）首先按相應(yīng)規(guī)則（2.1節(jié)）確定并發(fā)任務(wù)優(yōu)先級和共享資源優(yōu)先級，并給出單資源沖突消解算法（2.2節(jié)），然后在單資源沖突消解算法的基礎(chǔ)上，通過級聯(lián)調(diào)度的方式實(shí)現(xiàn)多資源多任務(wù)沖突消解算法（2.3節(jié)），最終實(shí)現(xiàn)整個(gè)相關(guān)性任務(wù)集的資源沖突消解過程。

2.1 優(yōu)先級獲取原則

2.1.1 任務(wù)優(yōu)先級

本文資源沖突消解算法中任務(wù)選擇順序取決于任務(wù)優(yōu)先級的高低。若產(chǎn)生資源沖突的并發(fā)任務(wù)中存在關(guān)鍵任務(wù)，則關(guān)鍵任務(wù)優(yōu)先進(jìn)行資源分配。若并發(fā)任務(wù)中存在多個(gè)關(guān)鍵任務(wù)或全部為非關(guān)鍵任務(wù)，采用先來先服務(wù)原則，先處理關(guān)鍵任務(wù)的資源請求，再處理非關(guān)鍵任務(wù)的資源請求。若兩個(gè)任務(wù)的最早開始時(shí)間相同，則按最小自由時(shí)差優(yōu)先的原則確定調(diào)度順序。

2.1.2 資源優(yōu)先級

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

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

2.2 單資源沖突消解算法

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

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

輸入：相關(guān)性任務(wù)集TR，需要使用資源R的并發(fā)任務(wù)集TR，資源R的剩余資源數(shù)RR

輸出：沖突消解后的并發(fā)任務(wù)集TR

步驟1：當(dāng)并發(fā)任務(wù)集TR為空時(shí)結(jié)束本算法，否則按公式6從TR中取出優(yōu)先集最高的任務(wù)t（優(yōu)先集獲取原則見上一節(jié)），并跳轉(zhuǎn)到步驟2。

步驟2：計(jì)算任務(wù)t的最早開始時(shí)間ES，并跳轉(zhuǎn)到步驟3。

步驟4：重新計(jì)算TR的關(guān)鍵路徑，并跳轉(zhuǎn)到步驟1。

2.3 多資源沖突消解算法

多資源沖突消解算法按資源優(yōu)先級對沖突資源進(jìn)行排序，先處理負(fù)載率高的沖突資源。多資源沖突消解過程其實(shí)是單資源沖突消解的級聯(lián)調(diào)度過程。該算法分時(shí)間段進(jìn)行資源沖突消解，可以減少任務(wù)間耦合的產(chǎn)生，并使相關(guān)性任務(wù)集的整體完成時(shí)間延遲最小化。

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

步驟1：以式（9）計(jì)算T中所有任務(wù)的最早開始時(shí)間ES，并跳轉(zhuǎn)到步驟2。

步驟2：遍歷T，依次獲取任務(wù)，該任務(wù)尚未進(jìn)行資源沖突消解，否則，結(jié)束該算法。

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

步驟4：當(dāng)QueueR為空時(shí)跳轉(zhuǎn)到步驟5，否則依次取出隊(duì)首資源R，并按以下步驟進(jìn)行處理。

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

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

（3）計(jì)算TR中任務(wù)的所有后續(xù)任務(wù)的最早開始時(shí)間，并更新連接邊。

步驟5：計(jì)算各個(gè)任務(wù)的資源自由時(shí)差：

（1）首先計(jì)算直接依賴關(guān)系FS中，以任務(wù)為直接前驅(qū)時(shí)，即任務(wù)的最晚開始時(shí)間LS。

（2）各個(gè)任務(wù)的資源自由時(shí)差RFF。

步驟6：重新計(jì)算關(guān)鍵路徑，RFF=0的任務(wù)為關(guān)鍵任務(wù)，并跳轉(zhuǎn)到步驟2。

3 實(shí)例分析

以圖1和表1給出的相關(guān)性任務(wù)集為例，根據(jù)多資源沖突消解算法自左向右解決資源沖突，依次找出資源沖突任務(wù)集TR={,,}和TR={,,}。按照任務(wù)優(yōu)先級獲取原則進(jìn)行依次調(diào)度，若存在多任務(wù)多資源沖突情況，則按照資源優(yōu)先級（資源負(fù)載率）進(jìn)行調(diào)度。表2給出了資源沖突消解完成后的任務(wù)調(diào)度情況，表3給出了在資源沖突消解完成的基礎(chǔ)上進(jìn)行和資源沖突消解完成后的任務(wù)調(diào)度情況。圖2給出了在資源沖突消解完成時(shí)相關(guān)性任務(wù)集共享資源沖突消解調(diào)度結(jié)果圖。

表2 R1資源沖突消解完成后數(shù)據(jù)

表3 R2和R3資源沖突消解完成后數(shù)據(jù)

圖2 相關(guān)性任務(wù)集共享資源沖突消解結(jié)果

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

圖3 添加了基于資源沖突消解的SS連接邊的相關(guān)性任務(wù)集

4 結(jié) 論

本文基于關(guān)鍵路徑和資源使用率優(yōu)先調(diào)度而提出了一種共享資源沖突消解算法，屬于啟發(fā)式算法，它能夠?qū)崿F(xiàn)多資源多任務(wù)并發(fā)情況下的有效調(diào)度。與目前領(lǐng)域中共享資源約束下任務(wù)調(diào)度的研究成果相比，本算法有如下創(chuàng)新點(diǎn)：（1）給出了基于共享資源競爭關(guān)系的相關(guān)性任務(wù)集的表示方式。（2）提出了基于級聯(lián)調(diào)度的資源沖突消解的算法，通過分時(shí)間段利用任務(wù)優(yōu)先級和資源優(yōu)先級進(jìn)行沖突消解。因此本算法對于深入研究分布式多處理器環(huán)境下任務(wù)并發(fā)調(diào)度優(yōu)化具有相應(yīng)意義，同時(shí)對實(shí)際情況上相關(guān)性任務(wù)受多資源約束這一現(xiàn)實(shí)問題的研究取得一定的進(jìn)展。