實(shí)時(shí)多處理器系統(tǒng)作為一個(gè)數(shù)學(xué)模型,它刻畫表達(dá)和反映自然界、人類社會(huì)中大量、廣泛的實(shí)際問題,在現(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í)際問題中,空間都是一個(gè)不可回避的因素。文獻(xiàn)[6-8]將空間因素引入到實(shí)時(shí)多處理系統(tǒng)中,首次提出了帶空間限制的實(shí)時(shí)多處理器系統(tǒng)調(diào)度模型。論文則是在這個(gè)模型框架下針對(duì)任務(wù)占用空間情況重點(diǎn)研究了實(shí)時(shí)并行模型、線性并發(fā)模型,非線性并發(fā)模型的調(diào)度算法性能,時(shí)空利用率等性質(zhì)。 論文研究工作主要集中在以下方面： 針對(duì)已有文獻(xiàn)提出的實(shí)時(shí)并行模型中主調(diào)度算法與全局調(diào)度算法存在的不足：(1)在劃分極大相容組時(shí),忽略了問題的實(shí)時(shí)性,沒有保證重要任務(wù)的優(yōu)先調(diào)度,任務(wù)的時(shí)間限有可能得不到滿足；(2)在同一極大相容組中,有可能因各個(gè)任務(wù)的Ci／Ti值相差較大,從而導(dǎo)致調(diào)度時(shí)系統(tǒng)的利用率較低,論文提出了一種與文獻(xiàn)[7]思路不同的調(diào)度算法,即基于EDF的優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度算法,該算法很好的解決了文獻(xiàn)[7]的調(diào)度算法的不足。從算法調(diào)度成功率以及時(shí)空利用率等方面考慮并經(jīng)過實(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)。 該定理在理論研究上有一定價(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,當(dāng)經(jīng)過一定的時(shí)間時(shí),系統(tǒng)趨于穩(wěn)定,即每隔一個(gè)固定的時(shí)間,系統(tǒng)切入一個(gè)任務(wù),記住個(gè)時(shí)間間隔為t0,則有： 定理5.3.1 (2k-1)/(2k)是所有PCM模型中有效調(diào)度的時(shí)空利用率的上界。
【學(xué)位單位】：廣西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2010
【中圖分類】：TP332

【參考文獻(xiàn)】

相關(guān)期刊論文 前9條

1 張惠娟,周利華;一種基于EDF算法的多處理器實(shí)時(shí)調(diào)度算法[J];計(jì)算機(jī)工程與應(yīng)用;2003年30期

2 高立娥;同愛麗;康鳳舉;劉衛(wèi)東;趙寧寧;;實(shí)時(shí)多處理器動(dòng)態(tài)調(diào)度算法的研究與應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2005年34期

3 喬穎,王宏安,戴國(guó)忠;一種新的實(shí)時(shí)多處理器系統(tǒng)的動(dòng)態(tài)調(diào)度算法[J];軟件學(xué)報(bào);2002年01期

4 王永吉,陳秋萍;單調(diào)速率及其擴(kuò)展算法的可調(diào)度性判定[J];軟件學(xué)報(bào);2004年06期

5 劉真環(huán);韋立;陳艷;趙榮盛;王駒;;DDS并行模型及其形式化[J];軟件學(xué)報(bào);2009年06期

6 張惠娟,翟鴻鳴,周利華;多處理器系統(tǒng)的實(shí)時(shí)調(diào)度算法研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2004年08期

7 邢群科;郝紅衛(wèi);溫天江;;兩種經(jīng)典實(shí)時(shí)調(diào)度算法的研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與設(shè)計(jì);2006年01期

8 馮艷紅,張玉明,徐美華;實(shí)時(shí)調(diào)度算法分類研究[J];微型電腦應(yīng)用;2005年07期

9 涂碧波,李勝利;視頻服務(wù)器存儲(chǔ)子系統(tǒng)的I/O優(yōu)化[J];小型微型計(jì)算機(jī)系統(tǒng);2003年03期

相關(guān)博士學(xué)位論文 前2條

1 賓雪蓮;實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2004年

2 王濤;實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度若干關(guān)鍵技術(shù)的研究[D];哈爾濱工程大學(xué);2006年

相關(guān)碩士學(xué)位論文 前4條

1 謝建平;單處理器環(huán)境下實(shí)時(shí)混合任務(wù)的調(diào)度算法研究[D];武漢理工大學(xué);2008年

2 陳艷;并發(fā)實(shí)時(shí)系統(tǒng)的模型及其形式化[D];廣西師范大學(xué);2008年

3 韋立;SLDDS問題的離散化與形式化[D];廣西師范大學(xué);2008年

4 劉真環(huán);DDS并行模型及其形式化[D];廣西師范大學(xué);2008年

本文編號(hào)：2822279