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

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

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

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

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

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

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