基于動(dòng)態(tài)關(guān)鍵路徑的bnp調(diào)度算法

基于動(dòng)態(tài)關(guān)鍵路徑的bnp調(diào)度算法

1靜態(tài)調(diào)度和bnp調(diào)度獲得并行系統(tǒng)的性能的關(guān)鍵是對(duì)處理機(jī)器的有效規(guī)劃。它將任務(wù)集T分布到處理機(jī)系統(tǒng)P上求解,滿足任務(wù)之間的依賴關(guān)系,且使得調(diào)度長(zhǎng)度最短。若并行任務(wù)的任務(wù)執(zhí)行時(shí)間、任務(wù)依賴關(guān)系、通信時(shí)間和同步時(shí)間是預(yù)先知道的,則調(diào)度可以在編譯時(shí)進(jìn)行,稱為靜態(tài)調(diào)度。若分布式系統(tǒng)中的處理機(jī)數(shù)有限,則稱為BNP調(diào)度問題。由于實(shí)際應(yīng)用中,處理機(jī)數(shù)多是受限的,所以靜態(tài)BNP調(diào)度問題是調(diào)度算法研究中的一個(gè)重要分支。2問題模型和相關(guān)工作首先對(duì)BNP調(diào)度模型及一些相關(guān)概念進(jìn)行描述。2.1bnp調(diào)度算法的研究目標(biāo)一個(gè)并行任務(wù)T由滿足一定前趨約束的子任務(wù)集{T1,T2,Λ,Tν}組成,它可以用一個(gè)有向無環(huán)圖G=(V,E)表示。其中V(|V|=ν)是節(jié)點(diǎn)集,對(duì)應(yīng)著并行任務(wù)中的一個(gè)子任務(wù),節(jié)點(diǎn)權(quán)量wi代表了任務(wù)Ti的運(yùn)行時(shí)間,表示任務(wù)需用的單位執(zhí)行時(shí)間(UnitExecutingTime,UET)數(shù)。E(|E|=e)是有向邊集,表明了任務(wù)之間的偏序?關(guān)?系?和?通?信?時(shí)?間,即Ti→Tj表示只有在任務(wù)Ti完成之后,Tj才能開始,Ti稱為Tj的直接前趨,Tj稱為Ti的直接后繼,或稱Ti為有向邊的尾,Tj為有向邊的頭。有向邊上的權(quán)值ci,j表明了任務(wù)Ti傳遞數(shù)據(jù)給任務(wù)Tj所需的時(shí)間。但當(dāng)Ti,Tj分配到同一個(gè)處理機(jī)上執(zhí)行時(shí),ci,j為0。另外,假設(shè)分布式系統(tǒng)P由n臺(tái)同構(gòu)的處理機(jī)P1,P2,Λ,Pn全互連組成,且網(wǎng)絡(luò)同構(gòu)。BNP調(diào)度算法的研究目標(biāo)是:將并行任務(wù)T分布到P上求解,使得它們滿足任務(wù)間的約束關(guān)系,同時(shí)使任務(wù)T的執(zhí)行時(shí)間最短。定義1若并行任務(wù)T對(duì)應(yīng)的任務(wù)圖G=(V,E)中存在一條從子任務(wù)Ti到子任務(wù)Tj的路徑,則稱Ti為Tj的前趨,Tj為Ti的后繼。定義2稱任務(wù)圖G=(V,E)中沒有前趨的節(jié)點(diǎn)為入節(jié)點(diǎn)或就緒任務(wù),沒有后繼的節(jié)點(diǎn)為出節(jié)點(diǎn)。定義3任務(wù)圖的關(guān)鍵路徑是圖中任務(wù)節(jié)點(diǎn)和有向邊的一個(gè)集合,它是任務(wù)圖中從一個(gè)入節(jié)點(diǎn)到一個(gè)出節(jié)點(diǎn)的所有路徑中節(jié)點(diǎn)計(jì)算量和有向邊的通信開銷之和最大的路徑,簡(jiǎn)記為CP(critialpath),稱關(guān)鍵路徑上的任務(wù)為關(guān)鍵任務(wù)。2.2bnp調(diào)度算法眾所周知,大多數(shù)情況下,有前趨約束的任務(wù)在多處理機(jī)上的調(diào)度是NP-完全問題,大多使用啟發(fā)式算法進(jìn)行求解,包括遺傳調(diào)度、隊(duì)列調(diào)度等。但基于算法復(fù)雜度和對(duì)任務(wù)圖限制的考慮,其中最通用的是隊(duì)列調(diào)度算法,它主要是重復(fù)以下過程直至所有的任務(wù)已被調(diào)度:①根據(jù)所有未調(diào)度節(jié)點(diǎn)的靜態(tài)或動(dòng)態(tài)優(yōu)先級(jí)確定調(diào)度節(jié)點(diǎn);②根據(jù)一定的準(zhǔn)則為該調(diào)度節(jié)點(diǎn)分配處理機(jī)及相應(yīng)的時(shí)間槽?，F(xiàn)有的BNP隊(duì)列調(diào)度算法有HLFET(highestlevelfirstwithestimatedtimes)、MCP(modifiedcriticalpath)、DLS(dynamic-levelscheduling)等調(diào)度算法。其中HLFET和MCP分別以節(jié)點(diǎn)的靜態(tài)b-level值和ALAP(aslateaspossible)值作為節(jié)點(diǎn)的優(yōu)先級(jí),并為調(diào)度節(jié)點(diǎn)分配可最早執(zhí)行它的處理機(jī)。而DLS采用了一種動(dòng)態(tài)優(yōu)先級(jí)的概念,它定義了任務(wù)-處理機(jī)對(duì)的動(dòng)態(tài)層概念,每次調(diào)度時(shí),對(duì)其中動(dòng)態(tài)層值最大者進(jìn)行調(diào)度,并將它分配給對(duì)應(yīng)的處理機(jī)。由于采用了動(dòng)態(tài)優(yōu)先級(jí)的概念,因而它優(yōu)于前兩者,但其時(shí)間復(fù)雜度也因此高于HLFET的O(v2)和MCP的O(v2log2v)的時(shí)間復(fù)雜度,為O(nv3)。對(duì)上述3種算法進(jìn)行分析,發(fā)現(xiàn)它們不能保證對(duì)影響算法性能的動(dòng)態(tài)關(guān)鍵任務(wù)進(jìn)行最早調(diào)度,從而有可能導(dǎo)致整個(gè)任務(wù)系統(tǒng)的完成時(shí)間被拖延(非動(dòng)態(tài)關(guān)鍵任務(wù)已占用了時(shí)間槽,例子見第3節(jié))。為克服上述算法中的缺點(diǎn),進(jìn)一步優(yōu)化任務(wù)的調(diào)度長(zhǎng)度,本文對(duì)BNP調(diào)度問題提出了一種新的啟發(fā)式調(diào)度算法。該算法不同于隊(duì)列調(diào)度算法——不需計(jì)算所有未調(diào)度任務(wù)的優(yōu)先級(jí),它基于任務(wù)圖的動(dòng)態(tài)關(guān)鍵路徑,遞歸地確定調(diào)度任務(wù),是第一個(gè)使用遞歸思想進(jìn)行調(diào)度的算法。同時(shí),它結(jié)合調(diào)度任務(wù)的后繼任務(wù),為其選擇了最佳時(shí)間槽。3任務(wù)圖12關(guān)鍵路徑在調(diào)度算法中起著重要作用,任務(wù)優(yōu)先級(jí)的確定常受限于它(如b-level值)。但由于任務(wù)之間通信開銷的不確定性,故隨著調(diào)度的進(jìn)行,任務(wù)圖的關(guān)鍵路徑也隨之改變。為此,我們提出動(dòng)態(tài)關(guān)鍵路徑的概念,它是針對(duì)調(diào)度過程中的剩余任務(wù)子圖定義的。3.1動(dòng)態(tài)關(guān)鍵路徑的定義首先對(duì)任務(wù)圖的概念進(jìn)行擴(kuò)充,允許它沒有入節(jié)點(diǎn),可以從一條邊進(jìn)入,相應(yīng)地稱這條沒有尾節(jié)點(diǎn)的邊為該任務(wù)圖的入邊,記作?→Tj。其中?是空節(jié)點(diǎn),Tj是它的頭節(jié)點(diǎn)。定義4定義任務(wù)圖G=(V,E)的去掉某個(gè)入節(jié)點(diǎn)Ti或去掉某條入邊的頭節(jié)點(diǎn)Ti及所有以Ti為頭的入邊而剩余的G的子圖為節(jié)點(diǎn)Ti關(guān)于G的剩余任務(wù)子圖,記為GL(Ti,G),即GL(Ti,G)=(VL,EL),其中VL=V-{Ti},EL=E-{?→Ti|?→Ti∈E}。上述剩余任務(wù)子圖的定義是相對(duì)于一個(gè)節(jié)點(diǎn)而言的,但它也同樣適用于對(duì)節(jié)點(diǎn)集S={Ti1,Ti2,Λ,Til}定義剩余任務(wù)子圖,即GL(S,G)=GL(Til,ΛGL(Ti2,GL(Ti1,G)))。顯然,調(diào)度節(jié)點(diǎn)只能是任務(wù)圖的入節(jié)點(diǎn)Ti或入邊的頭節(jié)點(diǎn)Ti(它的前趨已被調(diào)度),當(dāng)節(jié)點(diǎn)Ti被調(diào)度后,我們稱它對(duì)應(yīng)的剩余任務(wù)子圖中的關(guān)鍵路徑為當(dāng)前的關(guān)鍵路徑(按定義3計(jì)算,但路徑可以從一條入邊起始,終止于一個(gè)出節(jié)點(diǎn)),此即提出的動(dòng)態(tài)關(guān)鍵路徑的概念。由于任務(wù)之間的通信開銷也影響著任務(wù)的調(diào)度長(zhǎng)度,因而我們?cè)谏鲜鰟?dòng)態(tài)關(guān)鍵路徑的定義中允許入邊的存在。這也是本文的動(dòng)態(tài)關(guān)鍵路徑概念與一般定義的關(guān)鍵路徑(按定義3計(jì)算)的不同之處。定義5對(duì)于任務(wù)圖G=(V,E)來講,定義其子任務(wù)Ti(∈V)的前趨任務(wù)子圖是由G中Ti的所有前趨及它們之間的有向邊組成的一個(gè)有向無環(huán)圖,它是G的一個(gè)子圖,且其節(jié)點(diǎn)權(quán)重和邊權(quán)重與G中的對(duì)應(yīng)節(jié)點(diǎn)和邊保持一致。若將該前趨任務(wù)子圖記為GP(Ti,G),則有GP(Ti,G)=(VP,EP),其中VP={Tj|Tj∈V且在G中Tj為Ti的前趨},EP={Tk→Tl|Tk→Tl∈E,Tk,Tl∈VP或Tk=?,Tl∈VP或Tk∈VP,Tl=Ti}。對(duì)上述定義,為直觀化,下面舉一個(gè)簡(jiǎn)單的例子,如圖1所示。3.2基于主要?jiǎng)討B(tài)路徑的序列并行規(guī)劃算法調(diào)度算法的研究通常是確定兩個(gè)準(zhǔn)則,即選擇調(diào)度節(jié)點(diǎn)的準(zhǔn)則R1和為調(diào)度節(jié)點(diǎn)確定處理機(jī)的準(zhǔn)則R2。下面分別對(duì)它們進(jìn)行研究。3.2.1遞歸調(diào)度的思想由于關(guān)鍵路徑在調(diào)度算法中的重要作用,因而,我們希望對(duì)當(dāng)前動(dòng)態(tài)關(guān)鍵路徑上的第一個(gè)關(guān)鍵節(jié)點(diǎn)(稱為動(dòng)態(tài)關(guān)鍵任務(wù))進(jìn)行調(diào)度,但此時(shí)存在一個(gè)問題:該節(jié)點(diǎn)的前趨節(jié)點(diǎn)可能未被調(diào)度。如圖1(b)所示,按關(guān)鍵節(jié)點(diǎn)調(diào)度的思想,當(dāng)T1、T3被調(diào)度后,剩余任務(wù)子圖中的第一個(gè)關(guān)鍵節(jié)點(diǎn)是T5,但此時(shí)它的前趨節(jié)點(diǎn)T2、T4未被調(diào)度。為此,我們提出遞歸調(diào)度的思想,即對(duì)該節(jié)點(diǎn)的前趨任務(wù)子圖進(jìn)行調(diào)度,遞歸地確定調(diào)度節(jié)點(diǎn)。具體算法描述如下。其中函數(shù)調(diào)用select-processor(Ti)實(shí)現(xiàn)為調(diào)度節(jié)點(diǎn)Ti選擇處理機(jī)的功能。對(duì)它的算法實(shí)現(xiàn),我們有如下考慮。3.2.2任務(wù)ts的最早調(diào)度和終止時(shí)間常用的處理機(jī)選擇算法是為調(diào)度任務(wù)Ti選擇可最早執(zhí)行它的處理機(jī)。但對(duì)有通信開銷的任務(wù)系統(tǒng)來講,它不能有效地減少調(diào)度長(zhǎng)度。如圖2所示。從圖2中可以看出,由于在對(duì)調(diào)度任務(wù)進(jìn)行處理機(jī)分配時(shí)只考慮了它自身,沒有考慮它的通信開銷對(duì)后繼任務(wù)的影響,因而有可能拖延整個(gè)任務(wù)系統(tǒng)。為此我們按如下方法對(duì)任務(wù)Ti進(jìn)行調(diào)度。假設(shè)Tj為當(dāng)前關(guān)鍵路徑中Ti的直接后繼節(jié)點(diǎn)。(1)若Tj=?,則將Ti調(diào)度到可最早執(zhí)行它的處理機(jī)上;(2)若Tj≠?,則從各處理機(jī)上可最早開始Ti的n個(gè)時(shí)間槽內(nèi)選擇一個(gè),使Tj具有最早開始時(shí)間(根據(jù)已調(diào)度直接前趨節(jié)點(diǎn)計(jì)算得到的開始時(shí)間)。顯然,這種處理機(jī)選擇算法避免了通信開銷過大,有可能拖延任務(wù)完成時(shí)間這種情況的發(fā)生。對(duì)上述第(2)種情況,若逐個(gè)進(jìn)行比較,則它的時(shí)間復(fù)雜度較高,為O(nv)。為此,本文提出了時(shí)間復(fù)雜度為O(v)的一個(gè)快速算法。為便于算法描述,首先定義如下參數(shù)(其中后4個(gè)參數(shù)是相對(duì)于某個(gè)任務(wù)TS定義的):task-proc[q]——任務(wù)Tq分配的處理機(jī)(q=1,2,Λ,ν);st-task[q]——任務(wù)Tq的開始執(zhí)行時(shí)間(q=1,2,Λ,ν);st-proc[i]——處理機(jī)Pi的空閑起始時(shí)間(i=1,2,Λ,n);SPT[s]——任務(wù)TS的已調(diào)度直接前驅(qū)任務(wù)集,假設(shè)SPT[s]={Tm1,Tm2,Λ,Tml};SPP[s]——SPT[s]分配的處理機(jī)集,假設(shè)SPP[s]={Ps1,Ps2,Λ,Psb}(b≤l);et-task[q]——SPT[s]中任務(wù)Tq的包含通信開銷cq,s的結(jié)束時(shí)間,即et-task[q]=st-task[q]+wq+cq,s,q=m1,m2,Λ,ml;et[q]——SPT[s]中分配到處理機(jī)Pq上的任務(wù)的et-task的最大值,即et[q]=max{et-task[m]|Tm∈SPT[i],且task-proc[m]=Pq}(q=s1,s2,Λ,sb)。實(shí)際上,et[q](q=s1,s2,Λ,sb)直接影響著任務(wù)TS的開始時(shí)間。當(dāng)TS不被調(diào)度到處理機(jī)Pq上時(shí),它的開始時(shí)間只能是等于或大于et[q]+1,這即是提出的快速算法的依據(jù)。首先,假設(shè)對(duì)調(diào)度任務(wù)Ti進(jìn)行最早調(diào)度。假設(shè)它被調(diào)度在處理機(jī)Pk上,開始執(zhí)行時(shí)間為st-task[i]。在對(duì)Ti進(jìn)行最早調(diào)度后,我們假設(shè)對(duì)Tj也進(jìn)行最早調(diào)度(由于通信開銷的存在,只考慮將Tj調(diào)度在SPP[j]中(如式(1)所示)。且若有多個(gè)處理機(jī)同時(shí)取st-task[j],則選擇處理機(jī)的st-proc最小者)。假設(shè)它被調(diào)度在處理機(jī)PS上,開始執(zhí)行時(shí)間為st-task[j],它對(duì)應(yīng)的et[q](q=j1,j2,Λ,jb)分別為et1[q],其中的第1、2、3個(gè)最大值分別為et1[j1],et1[j2],et1[j3],它的前驅(qū)任務(wù)Ti的包括通信開銷ci,j的結(jié)束時(shí)間為et-task。提出的算法的實(shí)質(zhì)即是在對(duì)Ti,Tj進(jìn)行最早調(diào)度后,進(jìn)一步根據(jù)et-task和st-task[j]的取值情況對(duì)任務(wù)Ti有可能使st-task[j]最小的調(diào)度位置進(jìn)行比較,從中選取最佳者。①Pk≠Ps且et-task+1<st-task[j]這種情況下,對(duì)任務(wù)Ti的調(diào)度保持不變,st-task[j]已達(dá)到最小。②Pk≠Ps且et-task+1=st-task[j]此時(shí),若k=j1,則令x=j2;若k=j2,則令x=j1;然后分別將Ti調(diào)度到處理機(jī)Ps,Px上可最早開始它的時(shí)間槽內(nèi),計(jì)算對(duì)應(yīng)的st-task[j],取3種調(diào)度情況對(duì)應(yīng)的st-task[j]最小者作為Ti的調(diào)度結(jié)果(相同值時(shí),順序?yàn)镻k,Ps,Px,即仍保證最早調(diào)度)。③Pk=Ps此種情況下,若k=j1,則令x=j2;若k≠j1,則令x=j1;然后將Ti調(diào)度到處理機(jī)Px上可最早開始它的時(shí)間槽內(nèi),計(jì)算對(duì)應(yīng)的st-task[j],與已有的st-task[j]比較,取最小者。若值相同,則保持Ti的最早調(diào)度。對(duì)上述的調(diào)度調(diào)整過程,可證明如下定理。定理1在對(duì)任務(wù)Ti,Tj進(jìn)行最早調(diào)度后,若進(jìn)一步按上述①～③對(duì)Ti的調(diào)度進(jìn)行選擇,則Tj具有最早的開始時(shí)間。定理1的證明如下:證明假設(shè)對(duì)任務(wù)Tj,Tj進(jìn)行最早調(diào)度后,某些參數(shù)定義如2.2.2節(jié)所述。實(shí)際上,st-task[j]可根據(jù)(1)式計(jì)算。st-task[j]=min{max{st-proc[j1],et[j2]+1},max{st-proc[q],et[j1]+1},q=j2,Λ,jb}(1)st?task[j]=min{max{st?proc[j1],et[j2]+1},max{st?proc[q],et[j1]+1},q=j2,Λ,jb}(1)假設(shè)在Ti被調(diào)度到處理機(jī)Pl(Pl∈SPP[j],Pl≠Pk)上后,對(duì)Tj進(jìn)行最早調(diào)度。假設(shè)它對(duì)應(yīng)的開始執(zhí)行時(shí)間為st-task′[j],對(duì)應(yīng)的et[q](q=j1,j2,Λ,jb)分別為et2[q],其中的第1、2個(gè)最大值分別為et2[j1′],et2[j2′]。同(1)式有st-task′[j]=min{max{st-proc[j1′],et[j2′]+1},max{st-proc[q],et2[j1′]+1},q=j1,j2,Λ,jb?≠j1′}(2)st?task′[j]=min{max{st?proc[j1′],et[j2′]+1},max{st?proc[q],et2[j1′]+1},q=j1,j2,Λ,jb?≠j1′}(2)(注:(1)和(2)式中的st-proc的某些值是不同的,即在Tj被調(diào)度的處理機(jī)Pk,Pl上是不同的,其它情況取值一樣。)證明的思路即是比較(1)式和(2)式,證明它們?cè)诒徽{(diào)度到3.2.2節(jié)①～③中要求的處理機(jī)上時(shí),有可能使得st-task′[j]<st-task[j],而在Ti被調(diào)度在其它處理機(jī)上時(shí),Tj的最早調(diào)度的開始時(shí)間將大于、等于st-task′[j](或st-task[j])。仍按①～③分情況證明。這里,只以第②種情況為例,其它情況可同理證明。Ps≠Pk且et-task+1=st-task[j]結(jié)合(1)式可知有3種情況存在:①st-task[j]=et1[j2]+1=et-task+1(≠et1[j1]+1此時(shí),進(jìn)一步由(1)式可推得et1[s]=et1[j1],即處理機(jī)Ps,Pk上的et值分別等于前兩個(gè)最大值,且Ps=Pj1。由于Pk是可最早開始任務(wù)Ti的處理機(jī),所以當(dāng)Ti被調(diào)度在處理機(jī)Pl(Pl∈SPP[j],≠Ps,Pk)時(shí),有et2[j1′]≥et[j1],et2[j2′]≥et[j2](3)且若j1≠j1′,則有et2[j1′]≥et2[j2′]≥et1[j1]≥et1[j2];若j1=j1′,則有et1[j1]=et2[j1′],et2[j2′]≥et1[j2],將其代入(1)式和(2)式可得st-task′[j]≥st-task[j1]。同理分析,當(dāng)Ti被調(diào)度在處理機(jī)Ps上時(shí),有et2[j1′]=et2[s]≥et1[j1],et2[j2′]≤et1[j2](4)因此,當(dāng)et2[j2′]<et1[j2],且此時(shí)的st-proc[j1′]=st-proc[s]≤et2[j2′]+1時(shí),有st-task′[j]=et2[j2′]+1<st-proc[j]即當(dāng)Ti被調(diào)度在處理機(jī)Ps上時(shí),有可能使得st-task[j]更小。②st-task[j]=et1[j1]+1=et-task+1(≠et1[j2]+1)同①的分析,當(dāng)Ti被調(diào)度在處理機(jī)Ps上時(shí),有et2[j1′]=et2[s]≥et1[j1],et2[j2′]≤et1[j1](5)故根據(jù)(2)式可知,若此時(shí)的st-proc[s](假設(shè)為st-proc)≤et1[j1]+1,則有st-task[j′]≤st-task[j]。假設(shè)在Ti被調(diào)度到處理機(jī)Pl(Pl∈SPP[j],Pl≠Pk,Ps)上后,類似地定義st-task″[j],et3[j1″],et3[j2″]。顯?然?,當(dāng)Pl≠Px時(shí),由于Ps是滿足(1)式的st-proc最小者,所以有et3[j1″]=et3[l]≥et2[j1′],et3[j2″]≤et2[j2′](6)由于此時(shí)的st-proc[l]≥st-proc,故可推得st-task″[j]≥st-proc′[j]。同理,當(dāng)Pl=Px時(shí),有et3[j1″]=et3[x]≥et2[j1′],et3[j2″]≤et2[j2′],故可推得st-task″[j]有可能小于st-task′[j]。所以,這種情況下,Ti只有被調(diào)度在處理機(jī)Ps,Pk,Px上,st-task[j]才具有最小值。③st-task[j]=et1[j]+1=et1[j2]+1=et-task+1同理可證,若et1[j3]=et1[j1],則當(dāng)Ti被調(diào)度在處理機(jī)Pl(Pl∈SPP[j],Pl≠Pk)上時(shí),st-task′[j]≥st-task[j];若et1[j3]≠et1[j1],則當(dāng)Ti只有被調(diào)度在處理機(jī)Pl(Pk=Pj1,則為Pj2;否則,為Pj1)上時(shí),st-task′[j]才有可能小于st-task[j]上述即為提出的處理機(jī)選擇算法,它的具體算法描述見第3.2.3節(jié)。3.2.3鍵路徑的遞歸并行調(diào)度算法對(duì)上述調(diào)度節(jié)點(diǎn)選擇和處理機(jī)選擇算法進(jìn)行綜合,我們得到如下并行調(diào)度算法。算法1基于動(dòng)態(tài)關(guān)鍵路徑的遞歸并行調(diào)度算法定義G,st-task,st-proc,task-proc,q為全局變量;初始化:st-task[i]=-1(i=1,2,Λ,ν);st-proc[i]=0(i=1,2,Λ,n);task-proc[i]=-1(i=1,2,Λ,v);3.3最早調(diào)度的時(shí)間復(fù)雜度下面分析提出的算法在最壞情況下的時(shí)間復(fù)雜度。算法的復(fù)雜度依賴于使用的數(shù)據(jù)結(jié)構(gòu),由于算法中需計(jì)算前驅(qū)任務(wù)子圖,所以我們用包含兩個(gè)指針的鏈表表示任務(wù)圖(一個(gè)指向它的直接前驅(qū)節(jié)點(diǎn),一個(gè)指向它的直接后繼節(jié)點(diǎn))。首先對(duì)select-processor()進(jìn)行復(fù)雜度分析。顯然,若對(duì)Ti(Tj)進(jìn)行最早調(diào)度,則需計(jì)算SPT,SPP,et-task和et,然后類似于式(1)計(jì)算,其中前4個(gè)可