隨著時代的發(fā)展,實時系統(tǒng)越來越多地應(yīng)用于各種新興領(lǐng)域和應(yīng)用當(dāng)中,例如一些軌跡跟蹤系統(tǒng)和虛擬現(xiàn)實系統(tǒng)等。同時這些新應(yīng)用場景也對實時系統(tǒng)提出了一些新的指標(biāo)和要求,例如某些應(yīng)用場景允許在一定程度上錯過系統(tǒng)的時限要求。而隨著多核系統(tǒng)的逐漸流行,并行任務(wù)實時調(diào)度就顯得愈發(fā)重要。但是由于以前的研究主要關(guān)注的是非并行任務(wù)的相關(guān)理論,因此這是一個全新的挑戰(zhàn)。由于實時系統(tǒng)并行任務(wù)所展現(xiàn)出來的重要作用,學(xué)術(shù)界對其研究愈發(fā)重視起來。其中,實時系統(tǒng)調(diào)度算法就是一個研究熱點,而本文正是針對并行軟實時系統(tǒng)中全局最早截止時間優(yōu)先（GEDF）調(diào)度算法的仿真和性能分析。以前有關(guān)GEDF算法的研究工作主要聚焦于硬實時和非并行任務(wù)系統(tǒng),這種硬實時系統(tǒng)為了確保滿足所有的時限要求,在最壞的情況下,必須犧牲大約50%的處理能力,而這對于允許有限延遲度的軟實時系統(tǒng)而言是過度要求的。在本文中,當(dāng)并行任務(wù)系統(tǒng)中任務(wù)利用率滿足u_i≤m/2且任務(wù)的關(guān)鍵路徑長度滿足L_i<d₁/2時,在多處理器上的搶占式GEDF下獲得了有限的延遲度上界。證明出的延遲度上界取決于每個任務(wù)的... 

【文章來源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校

【文章頁數(shù)】：93 頁

【學(xué)位級別】：碩士

【部分圖文】：

基于劃分的多核調(diào)度但是需要注意的是，選擇的算法需要保證在各自的核心下，分配的任務(wù)總利用

哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文算法進(jìn)行分區(qū)，并且在核心上使用 TFP 調(diào)度的情況下，如果滿足 ≤ ，那該任務(wù)集同樣是硬實時可調(diào)度的�；谌值亩嗪苏{(diào)度算法 該類算法下，若系統(tǒng)有 m 個核心，則維護(hù)一個局預(yù)備隊列，作業(yè)允許在核心間遷移執(zhí)行，每次取出最多 m 個待執(zhí)行作業(yè)分配 m 個核心上執(zhí)行，具體過程如下圖所示。在 GTFP 調(diào)度下，任務(wù)被分配固定的先級，各個作業(yè)則從所屬的任務(wù)中繼承這個優(yōu)先級。

圖 1-3 基于簇的多核調(diào)度1.2.3 實時系統(tǒng)并行任務(wù)調(diào)度研究現(xiàn)狀并行任務(wù)研究對于實時應(yīng)用程序的重要性日益增加，而這對主要關(guān)注非并行任務(wù)模型的實時調(diào)度理論提出了新的挑戰(zhàn)。在文獻(xiàn)[38]中已經(jīng)提出了許多關(guān)于同構(gòu)多處理器系統(tǒng)的硬實時調(diào)度算法及其可調(diào)度性分析。他們研究的也是傳統(tǒng)的非并行獨立實時任務(wù)模型。另外，在多處理器系統(tǒng)上調(diào)度偶發(fā)任務(wù)集的問題更加復(fù)雜，在論文[39]中被證明是 NP 難問題，他的這項工作側(cè)重于 GEDF 調(diào)度算法，并在多項式時間內(nèi)提供了充分的可調(diào)度性測試條件，還提出了在偽多項式時間內(nèi)計算的更有效但更復(fù)雜的充分可調(diào)度性測試。關(guān)于具有任務(wù)內(nèi)并行性的實時任務(wù)的并行調(diào)度，針對不同的模型，每個模型都有自己的優(yōu)點和缺點。首先是 Fork-join 模型，在該模型中并行任務(wù)是并行和非并行段的交替序列。Lakshmanan 等人提出了一種盡可能順序執(zhí)行并行段的拉伸算法并分析了使用分區(qū)截止單調(diào)（DM）調(diào)度算法的資源增加界限（resourceaugmentationbound）。資源增


本文編號：3305119