面向多核系統(tǒng)的實時調(diào)度算法研究.pdf

1、隨著多核處理器的飛速發(fā)展，越來越多的嵌入式實時系統(tǒng)設(shè)計者選擇多核處理器作為硬件平臺，以滿足各類應用不斷增長的高性能與低功耗的需求。更高精確度和更高效率的多核處理器實時調(diào)度技術(shù)已成為這一發(fā)展趨勢的迫切需要。在過去的四十年中，面向單核處理器的實時調(diào)度技術(shù)已經(jīng)發(fā)展得比較成熟。相比之下，面向多核并行體系結(jié)構(gòu)的實時調(diào)度，無論從理論方面還是系統(tǒng)實現(xiàn)方面依然面臨著巨大挑戰(zhàn)。
　　基于這一背景，本文研究面向多核體系結(jié)構(gòu)的實時調(diào)度技術(shù)，旨在突破多處

2、理機模型調(diào)度中的重要基本理論難題，并解決在多核平臺上構(gòu)建實時系統(tǒng)的實際挑戰(zhàn)。多處理機調(diào)度主要分為全局調(diào)度和劃分（及半劃分）調(diào)度。本文分別針對這兩類調(diào)度算法中的關(guān)鍵理論問題給出了新的理論結(jié)果（包括全局調(diào)度的關(guān)鍵時刻、全局調(diào)度的有限響應時間條件、半劃分調(diào)度中的資源利用率界限），并提出了一系列調(diào)度技術(shù)來提高多處理機系統(tǒng)的平均實時性能（包括不可搶占全局調(diào)度技術(shù)、任務實例級別優(yōu)先級分配技術(shù)、半劃分調(diào)度中基于響應時間的劃分技術(shù)、半劃分調(diào)度中參數(shù)化的

3、資源利用率界限）。主要貢獻點概括如下:
　　(1)建立了多處理機全局調(diào)度近似關(guān)鍵時刻的概念，在此基礎(chǔ)上提出了一種針對可搶占全局固定優(yōu)先級調(diào)度的響應時間分析新技術(shù)，在不犧牲分析效率的前提下大幅度提高了分析的精確度。在這一理論基礎(chǔ)之上，建立了可搶占全局固定優(yōu)先級調(diào)度下任務具有有限響應時間的一般性條件。
　　(2)提出了一種新的針對不可搶占全局固定優(yōu)先級調(diào)度的可調(diào)度性分析技術(shù)，并結(jié)合大量的模擬實驗，推翻了從單處理機實時調(diào)度中衍生出

4、來并被普遍接受的關(guān)于“可搶占調(diào)度的實時性能總是好于不可搶占調(diào)度”的錯誤觀念，并對這種現(xiàn)象進行了深入分析，系統(tǒng)分析了如何利用不可搶占調(diào)度來提高系統(tǒng)的實時性能。
　　(3)提出了一種固定實例優(yōu)先級的全局調(diào)度算法及相應的分析技術(shù)。該算法結(jié)合了固定任務優(yōu)先級分配與最早截止期優(yōu)先(EDF)兩類算法的優(yōu)點，通過發(fā)掘任務實例之間的優(yōu)先級順序來大幅度提高系統(tǒng)的可調(diào)度性。該算法在設(shè)計階段僅對有限個具體的任務實例進行優(yōu)先級分配，以構(gòu)建運行時系統(tǒng)的負載

5、抽象表達;在運行時，通過復用上述優(yōu)先級分配方案實現(xiàn)高效的在線調(diào)度。
　　(4)將單處理機調(diào)度中著名的Liu& Layland資源利用率界限推廣到多處理機調(diào)度模型，解決了實時調(diào)度領(lǐng)域一個近四十年懸而未決的重要理論問題。提出一種具有Liu&Layland資源利用率界限的半劃分調(diào)度算法，使用與裝箱問題中的“最壞適用遞減”啟發(fā)式算法類似的任務劃分順序，來使任務切割只發(fā)生在高優(yōu)先級任務中，并利用高優(yōu)先級任務具有較大松弛時間的特性，來抵消任務

6、切割所帶來的負載增長效應。
　　(5)將單處理調(diào)度中大部分的參數(shù)化資源利用率界限擴展到了多處理機調(diào)度。提出一種具有參數(shù)化資源利用率的半劃分調(diào)度算法，該算法在大部分情況下滿足單處理機RMS調(diào)度中任意已知的參數(shù)化資源利用率界限。此外，該算法由于使用響應時間分析來決定一個處理器上可以接納的最大負載，因此獲得了比現(xiàn)有算法更好的平均實時性能。
　　此外，本文還研究了面向共享緩存的多核實時調(diào)度技術(shù)。多核處理器的一個全新特性是存在大量的片

7、上共享硬件資源（如共享緩存等），對共享資源的并行訪問使得一個任務的執(zhí)行時間依賴于其它同時執(zhí)行的任務，因此動搖了傳統(tǒng)實時調(diào)度中“已知任務的最壞情況執(zhí)行時間”這一基本假設(shè)，為多核實時調(diào)度及可調(diào)度性分析帶來了前所未有的挑戰(zhàn)。本文提出了一種全新的共享緩存敏感的多核實時調(diào)度及可調(diào)度性分析技術(shù)。該方法首先通過劃分共享緩存來減少任務間干涉從而提高了系統(tǒng)的時間可預測性，在此基礎(chǔ)上，從“處理機”和“緩存”兩個維度上解決資源分配與調(diào)度的問題，并相應的給出了