【正文】 資源的時(shí)間分配也應(yīng)不同，這樣才能保證高優(yōu)先級(jí)的任務(wù)優(yōu)先執(zhí)行。對(duì)此方法的改進(jìn)是采用隨機(jī)時(shí)間設(shè)置法，即所有任務(wù)占有自旋鎖的時(shí)間不是固定的，可根據(jù)任務(wù)自身特性以及優(yōu)先級(jí)大小進(jìn)行設(shè)置，這樣既避免了某個(gè)任務(wù)長(zhǎng)時(shí)間占有，其余任務(wù)一直處于饑餓狀態(tài)的想象，又使得高優(yōu)先級(jí)的任務(wù)更易于獲得資源的占有權(quán)。當(dāng)然改進(jìn)后的方法增加了系統(tǒng)開銷，如果使用不當(dāng)反而會(huì)降低系統(tǒng)的效率。選擇何種方法要根據(jù)具體的系統(tǒng)應(yīng)用類型而定，由于本文對(duì)共享內(nèi)存的訪問(wèn)是基于消息包的，通信量小，操作簡(jiǎn)單，因此選用第一種方法即可滿足系統(tǒng)要求。針對(duì)第二個(gè)問(wèn)題，由于自旋鎖未實(shí)現(xiàn)當(dāng)前任務(wù)與本核中斷以及當(dāng)前中斷與本核中斷的互斥，而單核系統(tǒng)提供的關(guān)中斷機(jī)制正是為解決該問(wèn)題而提出的，因此系統(tǒng)可以采用自旋鎖與關(guān)中斷相結(jié)合的策略。這樣系統(tǒng)提供中斷自旋鎖和任務(wù)自旋鎖兩種機(jī)制來(lái)保證多核下任務(wù)對(duì)資源的互斥訪問(wèn)。 RTEMS多核下的同步互斥機(jī)制 信號(hào)量機(jī)制實(shí)現(xiàn)（一） 中斷自旋鎖的實(shí)現(xiàn)（1） 中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)要實(shí)現(xiàn)一個(gè)中斷自旋鎖，需要記錄自旋鎖歸屬字段，表示自旋鎖是否在某個(gè)處理器核上，并且給出是哪一個(gè)處理器核取得了該自旋鎖，以判斷該鎖是否正在被使用。另外處理器核在讀鎖過(guò)程中根據(jù)任務(wù)中斷自旋鎖的狀態(tài)標(biāo)記處理器核對(duì)該鎖的獲取情況。由于在讀鎖初始強(qiáng)制關(guān)閉中斷，因此需要一個(gè)字段記錄中斷級(jí)別，在解鎖或放棄等待時(shí)將中斷打開。根據(jù)以上解析，本文定義的中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)具體代碼實(shí)現(xiàn)如下：structure tSpinLockIsr{int CpuOwner；tCpu cpu[CPU_COUNT]；int key；TCB *pTcb；}structure tCpu{int flag；}包含的字段含義為CpuOwner：自旋鎖歸屬字段；CPU_COUNT：系統(tǒng)中包含的可用處理器核的總數(shù)；cpu[CPU_COUNT]：自旋鎖針對(duì)每一個(gè)處理器核的獨(dú)立字段；：自旋鎖在每個(gè)處理器核下的標(biāo)識(shí)，表示該處理器對(duì)于指定自旋鎖的使用情況。可設(shè)置為SPIN_LOCK_INTERESTED（正在準(zhǔn)備取鎖），SPIN_LOCK_EMPTY（沒有使用任何自旋鎖），SPIN_LOCK_WAIT（等待其它處理器核正在使用的自旋鎖）。key：該自旋鎖被取得后運(yùn)行的中斷級(jí)別。pTcb：獲得該鎖的任務(wù)的任務(wù)控制塊。（2） 中斷自旋鎖的初始化在定義了中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)后，在使用中斷自旋鎖之前要對(duì)其進(jìn)行初始化。在對(duì)中斷自旋鎖初始化時(shí)，先將中斷自旋鎖的歸屬字段設(shè)置為SPIN_LOCK_NOBODY (1),表示該自旋鎖當(dāng)前不被任何處理器核占有。再將屬于每個(gè)處理器核的flag字段設(shè)置為 SPIN_LOCK_EMPTY（0），表示當(dāng)前該處理器核沒有使用任何的自旋鎖。具體代碼實(shí)現(xiàn)如下：void spinLockIsrInit(tSpinLockIsr *pLock){int i；pLockCpuOwner = SPIN_LOCK_NOBODY；for (i = 0。 i CPU_COUNT。 i++){pLock cpu[i].flag = SPIN_LOCK_EMPTY；}}（3） 中斷自旋鎖的加鎖在被初始化以后，中斷自旋鎖就可以被使用了。加鎖過(guò)程要先判斷該鎖是否已經(jīng)被其它的任務(wù)或中斷取得，如果沒有則取鎖，改變鎖當(dāng)前狀態(tài)。若該鎖已被其它任務(wù)或中斷取得，則任務(wù)循環(huán)等待，直到鎖被釋放或到達(dá)一定的循環(huán)次數(shù)。在這個(gè)過(guò)程中必須保證對(duì)鎖中各個(gè)字段的修改操作是原子的。 中斷自旋鎖獲取流程（4） 中斷自旋鎖的解鎖在中斷自旋鎖的解鎖過(guò)程中，應(yīng)該將在獲得該鎖時(shí)關(guān)閉的中斷打開。 中斷自旋鎖釋放流程（二） 任務(wù)自旋鎖的實(shí)現(xiàn)（1） 任務(wù)自旋鎖的數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)一個(gè)任務(wù)自旋鎖，需要定義字段記錄任務(wù)對(duì)鎖的擁有權(quán)的標(biāo)識(shí)、下一個(gè)可獲取自旋鎖的任務(wù)的標(biāo)識(shí)、已獲取到自旋鎖的標(biāo)識(shí)以及相應(yīng)的處理器核，因此任務(wù)自旋鎖的數(shù)據(jù)結(jié)構(gòu)具體代碼實(shí)現(xiàn)如下：structure tSpinLocktask{myTicket；int nextTicket；int ticketInService；int cpuIndex；}包含的字段含義為：myTicket：調(diào)用該函數(shù)的任務(wù)對(duì)鎖的擁有權(quán)的標(biāo)識(shí)。nextTicket：下一個(gè)可獲取自旋鎖的任務(wù)的標(biāo)識(shí)。ticketInService：已獲取到自旋鎖的標(biāo)識(shí)。cpuIndex：相應(yīng)的處理器核。（2） 任務(wù)自旋鎖的初始化對(duì)任務(wù)自旋鎖的初始化，只要設(shè)置自旋鎖中變量值為初始值即可。其中nextTicket 為 0；ticketInService 為 0；cpuIndex 為1。具體代碼實(shí)現(xiàn)如下：void spinLockTaskInit(tSpinlocktask *pLock){pLocknextTicket = 0；pLockticketInService = 0；pLockcpuIndex = 1；}（3） 任務(wù)自旋鎖的加鎖任務(wù)自旋鎖在初始化后就可以被使用了，使用前要先獲取任務(wù)自旋鎖。任務(wù)自旋鎖的加鎖之前要等待該鎖空閑，即使用該鎖的任務(wù)將該鎖解鎖。 任務(wù)自旋鎖加鎖流程（4） 任務(wù)自旋鎖解鎖。 任務(wù)自旋鎖解鎖流程 本章小結(jié)詳細(xì)介紹了并行系統(tǒng)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)模型、通信機(jī)制和MPSL層三個(gè)模塊：MPCI接口層，共享內(nèi)存實(shí)現(xiàn)層，硬件相關(guān)實(shí)現(xiàn)層。探討了RTEMS支持SMP設(shè)計(jì)過(guò)程中采用的節(jié)點(diǎn)間通信機(jī)制。并在原有自旋鎖機(jī)制的基礎(chǔ)上提出了一種任務(wù)自旋鎖與中斷自旋鎖相結(jié)合的機(jī)制，解決了單核情況下的同步互斥機(jī)制在多核系統(tǒng)中不能保持原有的語(yǔ)義的問(wèn)題。第4章 RTEMS多核任務(wù)調(diào)度機(jī)制第4章 RTEMS多核任務(wù)調(diào)度機(jī)制在實(shí)時(shí)系統(tǒng)中任務(wù)分配問(wèn)題起著重要作用，直接決定著系統(tǒng)的實(shí)時(shí)性、高效性[46]。合理的分配任務(wù)將在保證系統(tǒng)實(shí)時(shí)性的前提下最大程度地提升系統(tǒng)的整體性能。RTEMS內(nèi)核對(duì)多核任務(wù)調(diào)度采用平均分配策略。由于任務(wù)具有不確定性，并且系統(tǒng)資源隨著任務(wù)執(zhí)行會(huì)不斷發(fā)生變化，如果簡(jiǎn)單的采用平均策略，系統(tǒng)并行性不能得到很好的利用，嚴(yán)重影響系統(tǒng)整體性能。動(dòng)態(tài)調(diào)度算法能夠根據(jù)系統(tǒng)的狀態(tài)信息動(dòng)態(tài)決定任務(wù)分配，靈活性較高，更好的保證了系統(tǒng)負(fù)載平衡，提高了系統(tǒng)并行性。 任務(wù)分配問(wèn)題任務(wù)分配是指將任務(wù)分配到系統(tǒng)最合適的位置運(yùn)行[47]，任務(wù)分配算法解決任務(wù)分配問(wèn)題，一個(gè)好的任務(wù)分配算法可以縮小并行程序的執(zhí)行時(shí)間。在設(shè)計(jì)任務(wù)分配算法之前需要確定任務(wù)就緒隊(duì)列模型的選擇。在多核系統(tǒng)中，任務(wù)就緒隊(duì)列模型主要分為兩種：全局隊(duì)列模型和局部隊(duì)列模型[48]。全局隊(duì)列模型是指系統(tǒng)中所有節(jié)點(diǎn)共享一個(gè)全局任務(wù)就緒隊(duì)列，全局任務(wù)就緒隊(duì)列中記錄系統(tǒng)中所有處于就緒狀態(tài)的任務(wù)，由主控節(jié)點(diǎn)將就緒隊(duì)列中任務(wù)調(diào)度到系統(tǒng)中可用節(jié)點(diǎn)上執(zhí)行，一個(gè)任務(wù)在其生命周期中并不一定是在同一個(gè)節(jié)點(diǎn)上完成的，可能在不同時(shí)間運(yùn)行在不同的節(jié)點(diǎn)上。相反，局部就緒隊(duì)列模型是指每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)任務(wù)就緒隊(duì)列，每個(gè)任務(wù)自始至終都在同一個(gè)節(jié)點(diǎn)上執(zhí)行，系統(tǒng)中各節(jié)點(diǎn)的任務(wù)調(diào)度互不干擾。全局隊(duì)列模型由于所有節(jié)點(diǎn)共享一個(gè)就緒隊(duì)列，因此實(shí)現(xiàn)了系統(tǒng)的負(fù)載均衡。但是，由于全局就緒隊(duì)列是共享的，因此必須采取同步互斥機(jī)制實(shí)現(xiàn)多核的正確訪問(wèn)，這樣多個(gè)節(jié)點(diǎn)不能同時(shí)進(jìn)行任務(wù)調(diào)度，嚴(yán)重影響了系統(tǒng)的并行性。另外cache命中率也會(huì)受影響，因?yàn)橄到y(tǒng)要實(shí)現(xiàn)負(fù)載均衡，所以會(huì)出現(xiàn)同個(gè)任務(wù)在不同核之間遷移的情況，這樣會(huì)增加cache不命中率，使得系統(tǒng)性能降低。而局部就緒任務(wù)隊(duì)列模型相對(duì)全局隊(duì)列模型來(lái)說(shuō)，更好的利用了系統(tǒng)資源，首先系統(tǒng)中各個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)就緒任務(wù)隊(duì)列，這樣可以同時(shí)進(jìn)行任務(wù)調(diào)度，提高了系統(tǒng)的并行性。其次，任務(wù)在其生命周期中很可能在同一個(gè)節(jié)點(diǎn)上執(zhí)行，因此cache命中率會(huì)有很大增加，提高系統(tǒng)性能?；谝陨蠈?duì)比，選擇將局部就緒任務(wù)隊(duì)列模型作為RTEMS多核化任務(wù)分配模型。如果采用局部就緒任務(wù)隊(duì)列模型，則必須考慮負(fù)載平衡實(shí)現(xiàn)問(wèn)題。與全局隊(duì)列模型不同，局部隊(duì)列模型的負(fù)載平衡實(shí)現(xiàn)需要更多的機(jī)制提供支持。多核處理器的出現(xiàn)很大程度上提升了處理器性能。為了充分發(fā)揮多核處理器高并行性的優(yōu)勢(shì)，面臨的一個(gè)基本問(wèn)題是如何將工作均衡的分配到各個(gè)節(jié)點(diǎn)。對(duì)于多核系統(tǒng)，由于任務(wù)到達(dá)時(shí)間不確定性、任務(wù)在運(yùn)行過(guò)程中產(chǎn)生的不確定變化，使得多核系統(tǒng)中的一些節(jié)點(diǎn)任務(wù)較多，負(fù)載過(guò)重，而另一些節(jié)點(diǎn)卻是空閑的。負(fù)載均衡是把任務(wù)根據(jù)所有節(jié)點(diǎn)的負(fù)載情況按照一定的任務(wù)調(diào)度策略和調(diào)度算法進(jìn)行分配，以實(shí)現(xiàn)各節(jié)點(diǎn)統(tǒng)一開始工作，統(tǒng)一結(jié)束，不會(huì)因?yàn)椴糠止?jié)點(diǎn)任務(wù)輕處于空閑狀態(tài)，而另一部分節(jié)點(diǎn)任務(wù)負(fù)載過(guò)重而一直處于忙碌狀態(tài)[49]。下面部分主要針對(duì)采取局部隊(duì)列模型進(jìn)行任務(wù)分配問(wèn)題的研究，并設(shè)計(jì)一種高效的任務(wù)調(diào)度算法，以滿足系統(tǒng)性能需求。 任務(wù)調(diào)度算法分類任務(wù)調(diào)度算法根據(jù)任務(wù)調(diào)度時(shí)機(jī)可以分為靜態(tài)任務(wù)調(diào)度算法和動(dòng)態(tài)任務(wù)調(diào)度算法兩種[50]。（1）靜態(tài)任務(wù)調(diào)度算法在靜態(tài)任務(wù)調(diào)度中，所有任務(wù)在編譯階段根據(jù)任務(wù)的通信開銷、計(jì)算開銷、任務(wù)之間的依賴關(guān)系等屬性來(lái)確定各個(gè)節(jié)點(diǎn)的運(yùn)行任務(wù)以及各任務(wù)的執(zhí)行順序，一旦任務(wù)確定執(zhí)行處理器后，在運(yùn)行過(guò)程中將不再調(diào)整，一直運(yùn)行在該處理器內(nèi)核上。靜態(tài)任務(wù)調(diào)度相對(duì)簡(jiǎn)單，運(yùn)行時(shí)調(diào)度器開銷較小，系統(tǒng)具有很好的可預(yù)測(cè)性。但是由于靜態(tài)任務(wù)調(diào)度任務(wù)對(duì)應(yīng)的執(zhí)行處理器一經(jīng)確認(rèn)就不予更改，未考慮任務(wù)到達(dá)時(shí)間、任務(wù)在運(yùn)行過(guò)程中產(chǎn)生的不確定以及任務(wù)運(yùn)行過(guò)程中節(jié)點(diǎn)的負(fù)載狀況，因此這種算法缺少靈活性，在某些情況下嚴(yán)重影響系統(tǒng)的整體性能。（2）動(dòng)態(tài)任務(wù)調(diào)度算法動(dòng)態(tài)任務(wù)調(diào)度是指在并行任務(wù)運(yùn)行過(guò)程中，根據(jù)任務(wù)的運(yùn)行情況以及各節(jié)點(diǎn)的負(fù)載狀況決定每個(gè)任務(wù)的執(zhí)行處理器節(jié)點(diǎn)。該算法具有更強(qiáng)的執(zhí)行能力，能夠根據(jù)系統(tǒng)的狀態(tài)信息動(dòng)態(tài)決定任務(wù)分配。動(dòng)態(tài)任務(wù)調(diào)度相對(duì)靜態(tài)任務(wù)調(diào)度靈活性較高，根據(jù)任務(wù)的動(dòng)態(tài)運(yùn)行情況以及各處理器的負(fù)載情況進(jìn)行調(diào)整，更好的保證了系統(tǒng)負(fù)載平衡，提高系統(tǒng)并行性。但是動(dòng)態(tài)調(diào)度算法不可避免的加大了額外開銷，如信息搜集、分析、存儲(chǔ)以及任務(wù)的移動(dòng)，因此動(dòng)態(tài)任務(wù)調(diào)度算法應(yīng)該盡可能的簡(jiǎn)單、高效，這樣才能抵消這些額外開銷，充分發(fā)揮動(dòng)態(tài)任務(wù)調(diào)度算法的優(yōu)勢(shì)。RTEMS對(duì)多核處理器的支持如果采用動(dòng)態(tài)調(diào)度策略，不但可以彌補(bǔ)平均分配策略帶來(lái)的不足，而且可以充分利用共享內(nèi)存獲取各節(jié)點(diǎn)的負(fù)載狀態(tài)，進(jìn)而對(duì)任務(wù)進(jìn)行均衡分配。下面首先對(duì)現(xiàn)有動(dòng)態(tài)任務(wù)調(diào)度策略進(jìn)行分析，在此基礎(chǔ)上提出一種基于系統(tǒng)整體效能和系統(tǒng)整體負(fù)載均衡的動(dòng)態(tài)任務(wù)調(diào)度算法。 現(xiàn)有集中式動(dòng)態(tài)任務(wù)調(diào)度策略RandCentLB調(diào)度策略，是一個(gè)隨機(jī)調(diào)度策略，即當(dāng)多核系統(tǒng)出現(xiàn)負(fù)載不均衡情況時(shí)隨機(jī)選擇一個(gè)處理器，實(shí)現(xiàn)任務(wù)重分配。該策略實(shí)現(xiàn)簡(jiǎn)單，當(dāng)任務(wù)數(shù)量很大，并且任務(wù)之間通信非常小時(shí)，調(diào)度結(jié)果比較滿意。但是該策略有非常大的局限和不確定性。GreedyLB調(diào)度策略，首先找到系統(tǒng)中負(fù)載最小的處理器，然后將當(dāng)前未分配任務(wù)的最大負(fù)載分配給該處理器。該策略未考慮通信開銷，對(duì)于任務(wù)之間通信頻繁、通信代價(jià)大的系統(tǒng)并不一定能提高效率。GreedyComm調(diào)度策略在GreedyLB的基礎(chǔ)上進(jìn)行改進(jìn)，在選擇目標(biāo)機(jī)的時(shí)候不但考慮節(jié)點(diǎn)當(dāng)前負(fù)載情況，而且加進(jìn)通信開銷因素，一定程度上彌補(bǔ)GreedyLB調(diào)度策略的不足。RefineLB調(diào)度策略，是在系統(tǒng)運(yùn)行過(guò)程中不斷調(diào)整系統(tǒng)負(fù)載分布，系統(tǒng)每個(gè)節(jié)點(diǎn)都設(shè)有一個(gè)閾值，當(dāng)存在任務(wù)負(fù)載超過(guò)該閾值的節(jié)點(diǎn)時(shí)，啟動(dòng)系統(tǒng)調(diào)度模塊，進(jìn)行任務(wù)重分配。該策略屬于任務(wù)發(fā)起者調(diào)動(dòng)策略。由于該策略只考慮了系統(tǒng)中重載節(jié)點(diǎn)，算法實(shí)現(xiàn)簡(jiǎn)單，并且通信開銷較少。RefineCommLB調(diào)度策略，類似于RefineLB，但是該策略在選擇任務(wù)接收者時(shí)考慮到了任務(wù)之間的通信開銷，以尋求一種更有益的選擇[51]。為了充分發(fā)揮多核處理器并行性能，必須找到一個(gè)合理的任務(wù)分配策略。任務(wù)策略的選擇首先要考慮具體系統(tǒng)結(jié)構(gòu)和任務(wù)類型，再在此基礎(chǔ)上尋求最優(yōu)任務(wù)調(diào)度策略[39]。任務(wù)調(diào)度問(wèn)題已被證明是NP完全問(wèn)題，所以在大多數(shù)情況下，只能取得問(wèn)題的近似最優(yōu)解。并且一種具體的調(diào)度算法是在很多限制和先設(shè)條件下提出的，只能適應(yīng)某些特定的情況和環(huán)境。系統(tǒng)任務(wù)重新分配會(huì)帶來(lái)兩種開銷[52]：任務(wù)在節(jié)點(diǎn)上的執(zhí)行時(shí)間和節(jié)點(diǎn)之間的通信開銷。為了提高系統(tǒng)性能，一個(gè)優(yōu)秀的任務(wù)調(diào)度策略需要滿足兩個(gè)目標(biāo)：減少節(jié)點(diǎn)的執(zhí)行時(shí)間；減少節(jié)點(diǎn)之間的通信開銷。這是兩個(gè)相互沖突的目標(biāo)，一方面要想減少節(jié)點(diǎn)的執(zhí)行時(shí)間，達(dá)到縮短整個(gè)任務(wù)的執(zhí)行時(shí)間目的，必須將任務(wù)均衡分配到各個(gè)節(jié)點(diǎn)上，但這勢(shì)必會(huì)加大節(jié)點(diǎn)之間的通信開銷。另一方面，如果減少節(jié)點(diǎn)之間的通信開銷，則任務(wù)要盡量分配到一個(gè)節(jié)點(diǎn)中運(yùn)行，這又會(huì)導(dǎo)致系統(tǒng)負(fù)載嚴(yán)重不均衡，影響任務(wù)執(zhí)行結(jié)束時(shí)間。因此任務(wù)調(diào)度策略需要在這兩個(gè)目標(biāo)中達(dá)到一個(gè)平衡?；趯?duì)以上考慮提出一種更加全面調(diào)度策略，該策略不但考慮了系統(tǒng)各節(jié)點(diǎn)的負(fù)載情況和節(jié)點(diǎn)之間的通信開銷，而且考慮了系統(tǒng)中每個(gè)任務(wù)優(yōu)先級(jí)和系統(tǒng)整體負(fù)載狀況，最大限度的利用系統(tǒng)的并行性，提高系統(tǒng)整體性能。 動(dòng)態(tài)任務(wù)調(diào)度模型動(dòng)態(tài)任務(wù)調(diào)度模型可以形象描述多核系統(tǒng)任務(wù)調(diào)度過(guò)程，動(dòng)態(tài)任務(wù)調(diào)度模型包括任務(wù)集、負(fù)載估計(jì)、調(diào)度策略和任務(wù)映射。對(duì)動(dòng)態(tài)任務(wù)調(diào)度模型的求解過(guò)程就是在多核處理器系統(tǒng)環(huán)境下，尋求一個(gè)優(yōu)秀的調(diào)度策略[53]，該策略以任務(wù)集和節(jié)點(diǎn)負(fù)載情況作為輸入，將任務(wù)到節(jié)點(diǎn)的映射作為輸出。 任務(wù)集多核處理器系統(tǒng)中的任務(wù)集可表示為一個(gè)四元組.定義1（任務(wù)集）：，其中：，任務(wù)集合，每個(gè)頂點(diǎn)表示一個(gè)任務(wù)，表示任務(wù)i；，任務(wù)關(guān)系集合，任務(wù)頂點(diǎn)和邊的關(guān)系可表示為，即任務(wù)i是任務(wù)j的前驅(qū)，任務(wù)j是任務(wù)i的后繼，只有任務(wù)i完成之后，任務(wù)j才能開始；，任務(wù)運(yùn)行時(shí)間集合，表示任務(wù)i運(yùn)行時(shí)間；，通信時(shí)間集合，其中，越大表示任務(wù)i與j之間的通信代價(jià)越大。=0表示兩個(gè)任務(wù)之間無(wú)通信。根據(jù)定義1描述，可將系統(tǒng)任務(wù)集表示為一個(gè)加權(quán)的有向無(wú)環(huán)路圖DAG。： DAG圖例該圖中頂點(diǎn)表示系統(tǒng)所有任務(wù)，本例中共包括三個(gè)任務(wù)，其中每個(gè)任務(wù)又可以進(jìn)行分解，T1，T2，T3，T4屬于任務(wù)1，T5，T6，T7，T8屬于任務(wù)2，T9，T10，T11，T12屬于任務(wù)3。圖中有向邊表示任