帶空間限制的實(shí)時(shí)多處理器系統(tǒng)調(diào)度研究.pdf

1、實(shí)時(shí)多處理器系統(tǒng)作為一個(gè)數(shù)學(xué)模型,它刻畫(huà)表達(dá)和反映自然界、人類(lèi)社會(huì)中大量、廣泛的實(shí)際問(wèn)題,在現(xiàn)實(shí)生活的各個(gè)領(lǐng)域中有廣泛的應(yīng)用,而與其相應(yīng)的任務(wù)調(diào)度理論研究則成為實(shí)時(shí)系統(tǒng)研究的一個(gè)重要課題。當(dāng)前對(duì)實(shí)時(shí)多處理器系統(tǒng)調(diào)度理論的研究很少考慮到空間的約束,但在許多實(shí)際問(wèn)題中,空間都是一個(gè)不可回避的因素。文獻(xiàn)[6-8]將空間因素引入到實(shí)時(shí)多處理系統(tǒng)中,首次提出了帶空間限制的實(shí)時(shí)多處理器系統(tǒng)調(diào)度模型。論文則是在這個(gè)模型框架下針對(duì)任務(wù)占用空間情況重點(diǎn)研

2、究了實(shí)時(shí)并行模型、線性并發(fā)模型,非線性并發(fā)模型的調(diào)度算法性能,時(shí)空利用率等性質(zhì)。論文研究工作主要集中在以下方面:針對(duì)已有文獻(xiàn)提出的實(shí)時(shí)并行模型中主調(diào)度算法與全局調(diào)度算法存在的不足:(1)在劃分極大相容組時(shí),忽略了問(wèn)題的實(shí)時(shí)性,沒(méi)有保證重要任務(wù)的優(yōu)先調(diào)度,任務(wù)的時(shí)間限有可能得不到滿(mǎn)足;(2)在同一極大相容組中,有可能因各個(gè)任務(wù)的Ci/Ti值相差較大,從而導(dǎo)致調(diào)度時(shí)系統(tǒng)的利用率較低,論文提出了一種與文獻(xiàn)[7]思路不同的調(diào)度算法,即基于EDF

3、的優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度算法,該算法很好的解決了文獻(xiàn)[7]的調(diào)度算法的不足。從算法調(diào)度成功率以及時(shí)空利用率等方面考慮并經(jīng)過(guò)實(shí)例分析,得出該算法明顯優(yōu)于文獻(xiàn)[7]的調(diào)度算法,而且得出結(jié)論只要文獻(xiàn)[7]的算法能調(diào)度的任務(wù)集,則論文提出的調(diào)度算法一定能調(diào)度。針對(duì)文獻(xiàn)[6]提出的LCM并發(fā)模型,對(duì)貪心算法與循環(huán)算法的性質(zhì)作進(jìn)一步的研究,得到并證明了定理:基于LCM模型的貪心算法與循環(huán)算法調(diào)度,它們的時(shí)空利用率均可達(dá)到(2k-1)/(2k)。該定理在理論

4、研究上有一定價(jià)值。針對(duì)任務(wù)pi的空間占用函數(shù)di(t)的多樣性以及di(t)為拋物線下降情形的典型性,論文提出了PCM并發(fā)模型并對(duì)該模型的時(shí)空利用率及相應(yīng)的貪心算法性質(zhì)作了初步研究,得到如下結(jié)論:定理5.2.1對(duì)于PCM下GA算法,對(duì)任意k≥2,k∈N,系統(tǒng)的時(shí)空利用率eG=(2k-1)/(2k)定理5.2.2對(duì)于PCM下GA算法,對(duì)任意k≥2,k∈N,系統(tǒng)同時(shí)運(yùn)行任務(wù)個(gè)數(shù)平均為:定理5.2.3對(duì)于PCM下GA算法,對(duì)任意k≥2,k∈N