【摘要】：隨著多核處理器的飛速發(fā)展,越來越多的嵌入式實(shí)時系統(tǒng)設(shè)計(jì)者選擇多核處理器作為硬件平臺,以滿足各類應(yīng)用不斷增長的高性能與低功耗的需求。更高精確度和更高效率的多核處理器實(shí)時調(diào)度技術(shù)已成為這一發(fā)展趨勢的迫切需要。在過去的四十年中,面向單核處理器的實(shí)時調(diào)度技術(shù)已經(jīng)發(fā)展得比較成熟。相比之下,面向多核并行體系結(jié)構(gòu)的實(shí)時調(diào)度,無論從理論方面還是系統(tǒng)實(shí)現(xiàn)方面依然面臨著巨大挑戰(zhàn)。 基于這一背景,本文研究面向多核體系結(jié)構(gòu)的實(shí)時調(diào)度技術(shù),旨在突破多處理機(jī)模型調(diào)度中的重要基本理論難題,并解決在多核平臺上構(gòu)建實(shí)時系統(tǒng)的實(shí)際挑戰(zhàn)。多處理機(jī)調(diào)度主要分為全局調(diào)度和劃分(及半劃分)調(diào)度。本文分別針對這兩類調(diào)度算法中的關(guān)鍵理論問題給出了新的理論結(jié)果(包括全局調(diào)度的關(guān)鍵時刻、全局調(diào)度的有限響應(yīng)時間條件、半劃分調(diào)度中的資源利用率界限),并提出了一系列調(diào)度技術(shù)來提高多處理機(jī)系統(tǒng)的平均實(shí)時性能(包括不可搶占全局調(diào)度技術(shù)、任務(wù)實(shí)例級別優(yōu)先級分配技術(shù)、半劃分調(diào)度中基于響應(yīng)時間的劃分技術(shù)、半劃分調(diào)度中參數(shù)化的資源利用率界限)。主要貢獻(xiàn)點(diǎn)概括如下： (1)建立了多處理機(jī)全局調(diào)度近似關(guān)鍵時刻的概念,在此基礎(chǔ)上提出了一種針對可搶占全局固定優(yōu)先級調(diào)度的響應(yīng)時間分析新技術(shù),在不犧牲分析效率的前提下大幅度提高了分析的精確度。在這一理論基礎(chǔ)之上,建立了可搶占全局固定優(yōu)先級調(diào)度下任務(wù)具有有限響應(yīng)時間的一般性條件。 (2)提出了一種新的針對不可搶占全局固定優(yōu)先級調(diào)度的可調(diào)度性分析技術(shù),并結(jié)合大量的模擬實(shí)驗(yàn),推翻了從單處理機(jī)實(shí)時調(diào)度中衍生出來并被普遍接受的關(guān)于“可搶占調(diào)度的實(shí)時性能總是好于不可搶占調(diào)度”的錯誤觀念,并對這種現(xiàn)象進(jìn)行了深入分析,系統(tǒng)分析了如何利用不可搶占調(diào)度來提高系統(tǒng)的實(shí)時性能。 (3)提出了一種固定實(shí)例優(yōu)先級的全局調(diào)度算法及相應(yīng)的分析技術(shù)。該算法結(jié)合了固定任務(wù)優(yōu)先級分配與最早截止期優(yōu)先(EDF)兩類算法的優(yōu)點(diǎn),通過發(fā)掘任務(wù)實(shí)例之間的優(yōu)先級順序來大幅度提高系統(tǒng)的可調(diào)度性。該算法在設(shè)計(jì)階段僅對有限個具體的任務(wù)實(shí)例進(jìn)行優(yōu)先級分配,以構(gòu)建運(yùn)行時系統(tǒng)的負(fù)載抽象表達(dá)；在運(yùn)行時,通過復(fù)用上述優(yōu)先級分配方案實(shí)現(xiàn)高效的在線調(diào)度。 (4)將單處理機(jī)調(diào)度中著名的LiuLayland資源利用率界限推廣到多處理機(jī)調(diào)度模型,解決了實(shí)時調(diào)度領(lǐng)域一個近四十年懸而未決的重要理論問題。提出一種具有LiuLayland資源利用率界限的半劃分調(diào)度算法,使用與裝箱問題中的“最壞適用遞減”啟發(fā)式算法類似的任務(wù)劃分順序,來使任務(wù)切割只發(fā)生在高優(yōu)先級任務(wù)中,并利用高優(yōu)先級任務(wù)具有較大松弛時間的特性,來抵消任務(wù)切割所帶來的負(fù)載增長效應(yīng)。 (5)將單處理調(diào)度中大部分的參數(shù)化資源利用率界限擴(kuò)展到了多處理機(jī)調(diào)度。提出一種具有參數(shù)化資源利用率的半劃分調(diào)度算法,該算法在大部分情況下滿足單處理機(jī)RMS調(diào)度中任意已知的參數(shù)化資源利用率界限。此外,該算法由于使用響應(yīng)時間分析來決定一個處理器上可以接納的最大負(fù)載,因此獲得了比現(xiàn)有算法更好的平均實(shí)時性能。 此外,本文還研究了面向共享緩存的多核實(shí)時調(diào)度技術(shù)。多核處理器的一個全新特性是存在大量的片上共享硬件資源(如共享緩存等),對共享資源的并行訪問使得一個任務(wù)的執(zhí)行時間依賴于其它同時執(zhí)行的任務(wù),因此動搖了傳統(tǒng)實(shí)時調(diào)度中“已知任務(wù)的最壞情況執(zhí)行時間”這一基本假設(shè),為多核實(shí)時調(diào)度及可調(diào)度性分析帶來了前所未有的挑戰(zhàn)。本文提出了一種全新的共享緩存敏感的多核實(shí)時調(diào)度及可調(diào)度性分析技術(shù)。該方法首先通過劃分共享緩存來減少任務(wù)間干涉從而提高了系統(tǒng)的時間可預(yù)測性,在此基礎(chǔ)上,從“處理機(jī)”和“緩存”兩個維度上解決資源分配與調(diào)度的問題,并相應(yīng)的給出了兩種可調(diào)度性判定的方法。 綜上,本文研究了面向多核處理器的實(shí)時調(diào)度問題,內(nèi)容涵蓋了多個調(diào)度算法種類(全局與劃分,可搶占與不可搶占,固定任務(wù)優(yōu)先級與固定實(shí)例優(yōu)先級)。本文的研究成果為面向多核處理器的實(shí)時系統(tǒng)的設(shè)計(jì)與分析提供了重要的理論依據(jù),并對解決在多核系統(tǒng)上部署實(shí)時系統(tǒng)的實(shí)際問題具有很好的參考價值。
[Abstract]:......
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2012
【分類號】：TP332

【共引文獻(xiàn)】

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

1 夏繼強(qiáng);薛利強(qiáng);滿慶豐;;時間觸發(fā)CAN總線實(shí)時性分析及評估方法[J];北京航空航天大學(xué)學(xué)報(bào);2012年02期

2 趙海;周峰;羅玎玎;;WebitOS中動態(tài)優(yōu)先級調(diào)度機(jī)制及EDF算法的實(shí)現(xiàn)[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年11期

3 周本海;喬建忠;林樹寬;;多核平臺的并行實(shí)時調(diào)度與內(nèi)存分配算法[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

4 廖勇;熊光澤;陳旭東;桑楠;朱清新;;分布式實(shí)時嵌入式系統(tǒng)端到端性能確保[J];電子科技大學(xué)學(xué)報(bào);2007年03期

5 陳旭東;朱清新;廖勇;匡平;熊光澤;;一種非周期軟實(shí)時系統(tǒng)的緩沖設(shè)計(jì)方法[J];電子科技大學(xué)學(xué)報(bào);2007年03期

6 廖勇;陳旭東;桑楠;胡林輝;熊光澤;朱清新;;分布式實(shí)時系統(tǒng)的自適應(yīng)資源管理中間件[J];電子科技大學(xué)學(xué)報(bào);2008年01期

7 宋振超;;基于多處理器嵌入式系統(tǒng)調(diào)度算法的研究[J];電腦知識與技術(shù)(學(xué)術(shù)交流);2007年21期

8 余科軍;盧建斌;;基于平均分配原則的任務(wù)調(diào)度算法[J];電腦知識與技術(shù);2008年01期

9 陶軍;吳清亮;吳強(qiáng);;基于非合作競價博弈的網(wǎng)絡(luò)資源分配算法的應(yīng)用研究[J];電子學(xué)報(bào);2006年02期

10 郭銳鋒;劉嫻;丁萬夫;;基于優(yōu)先級降低策略的回卷恢復(fù)容錯實(shí)時調(diào)度算法研究[J];電子與信息學(xué)報(bào);2012年02期

相關(guān)會議論文 前4條

1 王文偉;魯植雄;袁越陽;;基于CAN總線的拖拉機(jī)虛擬儀表系統(tǒng)設(shè)計(jì)[A];紀(jì)念中國農(nóng)業(yè)工程學(xué)會成立30周年暨中國農(nóng)業(yè)工程學(xué)會2009年學(xué)術(shù)年會（CSAE 2009）論文集[C];2009年

2 淡圖南;朱立平;顏紀(jì)迅;;一種基于時間觸發(fā)的安全關(guān)鍵操作系統(tǒng)混合調(diào)度策略[A];全面建成小康社會與中國航空發(fā)展——2013首屆中國航空科學(xué)技術(shù)大會論文集[C];2013年

3 時小虎;;實(shí)時并行處理技術(shù)在指控系統(tǒng)中的應(yīng)用[A];2014第二屆中國指揮控制大會論文集（上）[C];2014年

4 梁心雄;吳兆雄;羅勝平;;實(shí)現(xiàn)資源信息自助服務(wù)的智慧氣象共享數(shù)據(jù)中心研究論述[A];第31屆中國氣象學(xué)會年會S13 氣象通信與信息技術(shù)應(yīng)用實(shí)踐與新技術(shù)探索[C];2014年

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

1 殷進(jìn)勇;可重構(gòu)系統(tǒng)中實(shí)時任務(wù)調(diào)度算法研究[D];哈爾濱工程大學(xué);2010年

2 郭秀巖;面向多核的多層次實(shí)時網(wǎng)絡(luò)數(shù)據(jù)流調(diào)度技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

3 陳曦;CAN總線實(shí)時性和可靠性若干問題的研究[D];天津大學(xué);2010年

4 盛偉;考慮緩存預(yù)熱時間的多核實(shí)時調(diào)度算法和分析[D];中國科學(xué)技術(shù)大學(xué);2011年

5 李嬋娟;安全關(guān)鍵實(shí)時通信協(xié)議研究[D];蘭州大學(xué);2011年

6 桂盛霖;安全關(guān)鍵嵌入式實(shí)時軟件的關(guān)鍵非功能屬性分析研究[D];電子科技大學(xué);2011年

7 呂鳴松;實(shí)時系統(tǒng)最壞情況執(zhí)行時間分析技術(shù)的研究[D];東北大學(xué);2010年

8 喬穎;實(shí)時異構(gòu)系統(tǒng)的集成動態(tài)調(diào)度算法研究[D];中國科學(xué)院軟件研究所;2001年

9 王X;基于異構(gòu)系統(tǒng)的實(shí)時數(shù)據(jù)處理[D];中國科學(xué)院研究生院（軟件研究所）;2002年

10 陽春華;工業(yè)實(shí)時系統(tǒng)多任務(wù)容錯調(diào)度技術(shù)及應(yīng)用研究[D];中南大學(xué);2002年

，

本文編號：2443142