對具有共享資源競爭的任務調度算法的研究.pdf

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

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

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