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

【共引文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前4條

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

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

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

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

相關博士學位論文 前10條

1 殷進勇;可重構系統(tǒng)中實時任務調度算法研究[D];哈爾濱工程大學;2010年

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

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

4 盛偉;考慮緩存預熱時間的多核實時調度算法和分析[D];中國科學技術大學;2011年

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

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

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

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

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

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

，

本文編號：2443142