對(duì)具有共享資源競(jìng)爭(zhēng)的任務(wù)調(diào)度算法的研究.pdf

1、近年來(lái),計(jì)算機(jī)在交通控制、通訊網(wǎng)絡(luò)等各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。支持上述應(yīng)用的基礎(chǔ)理論問(wèn)題為求解該領(lǐng)域內(nèi)的NP完全問(wèn)題的實(shí)用與快速算法,對(duì)上述領(lǐng)域內(nèi)NP完全問(wèn)題的快速算法的研究已經(jīng)成為近年來(lái)計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)的一個(gè)熱點(diǎn)。本論文主要研究具有共享資源競(jìng)爭(zhēng)的任務(wù)調(diào)度問(wèn)題的快速算法。 在很多系統(tǒng)中,系統(tǒng)中的任務(wù)需要一定的資源完成,在任務(wù)執(zhí)行完畢后就釋放所占用的資源,任何兩個(gè)需要相同資源而又互相沖突的任務(wù)不能同時(shí)進(jìn)行。這屬于具有共享資源競(jìng)爭(zhēng)的任務(wù)調(diào)度

2、問(wèn)題的研究范疇,該類調(diào)度問(wèn)題在現(xiàn)實(shí)世界具有廣泛的應(yīng)用,如計(jì)算機(jī)的實(shí)時(shí)控制、并行與分布式計(jì)算中的多處理機(jī)對(duì)共享資源的競(jìng)爭(zhēng)解決問(wèn)題、通訊過(guò)程中多個(gè)信源對(duì)線路的競(jìng)爭(zhēng)求解、通信控制軟件設(shè)計(jì)、移動(dòng)通信控制等。采用何種調(diào)度方式和調(diào)度算法,將直接影響到系統(tǒng)的運(yùn)行性能,因此對(duì)該類調(diào)度問(wèn)題的研究具有廣泛的意義。 本文首先以十字路口交通調(diào)度問(wèn)題和哲學(xué)家就餐問(wèn)題提出短時(shí)資源混雜占用型任務(wù)調(diào)度問(wèn)題(簡(jiǎn)稱DHDD),該問(wèn)題一般可描述為：在一定的時(shí)間區(qū)間內(nèi),讓盡可

3、能多的任務(wù)使用資源,并能避免死鎖、餓死等現(xiàn)象的發(fā)生。在DHDD問(wèn)題中,一個(gè)任務(wù)允許與任務(wù)集中若干任務(wù)共享資源,而同時(shí)又不允許與任務(wù)集中的某些任務(wù)共享資源。通常一個(gè)任務(wù)本身是由若干子任務(wù)組成,即表示一個(gè)任務(wù)類。以十字路口交通調(diào)度為例,一個(gè)方向的車輛集合為一個(gè)待調(diào)度的任務(wù),而其中每輛汽車為子任務(wù)。為不產(chǎn)生混亂,我們稱任務(wù)類中的任務(wù)為子任務(wù),并稱任務(wù)類中的子任務(wù)數(shù)為該任務(wù)的權(quán)。每一個(gè)任務(wù)內(nèi)的子任務(wù)個(gè)數(shù)是隨時(shí)間變化的,所以整個(gè)調(diào)度過(guò)程是一個(gè)聯(lián)機(jī)