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

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

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

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

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