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

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

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

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