并行軟實(shí)時(shí)系統(tǒng)中GEDF調(diào)度器的性能仿真與分析
發(fā)布時(shí)間：2021-07-27 04:52
隨著時(shí)代的發(fā)展,實(shí)時(shí)系統(tǒng)越來(lái)越多地應(yīng)用于各種新興領(lǐng)域和應(yīng)用當(dāng)中,例如一些軌跡跟蹤系統(tǒng)和虛擬現(xiàn)實(shí)系統(tǒng)等。同時(shí)這些新應(yīng)用場(chǎng)景也對(duì)實(shí)時(shí)系統(tǒng)提出了一些新的指標(biāo)和要求,例如某些應(yīng)用場(chǎng)景允許在一定程度上錯(cuò)過(guò)系統(tǒng)的時(shí)限要求。而隨著多核系統(tǒng)的逐漸流行,并行任務(wù)實(shí)時(shí)調(diào)度就顯得愈發(fā)重要。但是由于以前的研究主要關(guān)注的是非并行任務(wù)的相關(guān)理論,因此這是一個(gè)全新的挑戰(zhàn)。由于實(shí)時(shí)系統(tǒng)并行任務(wù)所展現(xiàn)出來(lái)的重要作用,學(xué)術(shù)界對(duì)其研究愈發(fā)重視起來(lái)。其中,實(shí)時(shí)系統(tǒng)調(diào)度算法就是一個(gè)研究熱點(diǎn),而本文正是針對(duì)并行軟實(shí)時(shí)系統(tǒng)中全局最早截止時(shí)間優(yōu)先（GEDF）調(diào)度算法的仿真和性能分析。以前有關(guān)GEDF算法的研究工作主要聚焦于硬實(shí)時(shí)和非并行任務(wù)系統(tǒng),這種硬實(shí)時(shí)系統(tǒng)為了確保滿(mǎn)足所有的時(shí)限要求,在最壞的情況下,必須犧牲大約50%的處理能力,而這對(duì)于允許有限延遲度的軟實(shí)時(shí)系統(tǒng)而言是過(guò)度要求的。在本文中,當(dāng)并行任務(wù)系統(tǒng)中任務(wù)利用率滿(mǎn)足ui≤m/2且任務(wù)的關(guān)鍵路徑長(zhǎng)度滿(mǎn)足Li<d1/2時(shí),在多處理器上的搶占式GEDF下獲得了有限的延遲度上界。證明出的延遲度上界取決于每個(gè)任務(wù)的...
【文章來(lái)源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校
【文章頁(yè)數(shù)】：93 頁(yè)
【學(xué)位級(jí)別】：碩士
【部分圖文】：
基于劃分的多核調(diào)度但是需要注意的是，選擇的算法需要保證在各自的核心下，分配的任務(wù)總利用
哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文算法進(jìn)行分區(qū)，并且在核心上使用 TFP 調(diào)度的情況下，如果滿(mǎn)足 ≤ ，那該任務(wù)集同樣是硬實(shí)時(shí)可調(diào)度的�；谌值亩嗪苏{(diào)度算法 該類(lèi)算法下，若系統(tǒng)有 m 個(gè)核心，則維護(hù)一個(gè)局預(yù)備隊(duì)列，作業(yè)允許在核心間遷移執(zhí)行，每次取出最多 m 個(gè)待執(zhí)行作業(yè)分配 m 個(gè)核心上執(zhí)行，具體過(guò)程如下圖所示。在 GTFP 調(diào)度下，任務(wù)被分配固定的先級(jí)，各個(gè)作業(yè)則從所屬的任務(wù)中繼承這個(gè)優(yōu)先級(jí)。
圖 1-3 基于簇的多核調(diào)度1.2.3 實(shí)時(shí)系統(tǒng)并行任務(wù)調(diào)度研究現(xiàn)狀并行任務(wù)研究對(duì)于實(shí)時(shí)應(yīng)用程序的重要性日益增加，而這對(duì)主要關(guān)注非并行任務(wù)模型的實(shí)時(shí)調(diào)度理論提出了新的挑戰(zhàn)。在文獻(xiàn)[38]中已經(jīng)提出了許多關(guān)于同構(gòu)多處理器系統(tǒng)的硬實(shí)時(shí)調(diào)度算法及其可調(diào)度性分析。他們研究的也是傳統(tǒng)的非并行獨(dú)立實(shí)時(shí)任務(wù)模型。另外，在多處理器系統(tǒng)上調(diào)度偶發(fā)任務(wù)集的問(wèn)題更加復(fù)雜，在論文[39]中被證明是 NP 難問(wèn)題，他的這項(xiàng)工作側(cè)重于 GEDF 調(diào)度算法，并在多項(xiàng)式時(shí)間內(nèi)提供了充分的可調(diào)度性測(cè)試條件，還提出了在偽多項(xiàng)式時(shí)間內(nèi)計(jì)算的更有效但更復(fù)雜的充分可調(diào)度性測(cè)試。關(guān)于具有任務(wù)內(nèi)并行性的實(shí)時(shí)任務(wù)的并行調(diào)度，針對(duì)不同的模型，每個(gè)模型都有自己的優(yōu)點(diǎn)和缺點(diǎn)。首先是 Fork-join 模型，在該模型中并行任務(wù)是并行和非并行段的交替序列。Lakshmanan 等人提出了一種盡可能順序執(zhí)行并行段的拉伸算法并分析了使用分區(qū)截止單調(diào)（DM）調(diào)度算法的資源增加界限（resourceaugmentationbound）。資源增
本文編號(hào)：3305119
【文章來(lái)源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校
【文章頁(yè)數(shù)】：93 頁(yè)
【學(xué)位級(jí)別】：碩士
【部分圖文】：
基于劃分的多核調(diào)度但是需要注意的是，選擇的算法需要保證在各自的核心下，分配的任務(wù)總利用
哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文算法進(jìn)行分區(qū)，并且在核心上使用 TFP 調(diào)度的情況下，如果滿(mǎn)足 ≤ ，那該任務(wù)集同樣是硬實(shí)時(shí)可調(diào)度的�；谌值亩嗪苏{(diào)度算法 該類(lèi)算法下，若系統(tǒng)有 m 個(gè)核心，則維護(hù)一個(gè)局預(yù)備隊(duì)列，作業(yè)允許在核心間遷移執(zhí)行，每次取出最多 m 個(gè)待執(zhí)行作業(yè)分配 m 個(gè)核心上執(zhí)行，具體過(guò)程如下圖所示。在 GTFP 調(diào)度下，任務(wù)被分配固定的先級(jí)，各個(gè)作業(yè)則從所屬的任務(wù)中繼承這個(gè)優(yōu)先級(jí)。
圖 1-3 基于簇的多核調(diào)度1.2.3 實(shí)時(shí)系統(tǒng)并行任務(wù)調(diào)度研究現(xiàn)狀并行任務(wù)研究對(duì)于實(shí)時(shí)應(yīng)用程序的重要性日益增加，而這對(duì)主要關(guān)注非并行任務(wù)模型的實(shí)時(shí)調(diào)度理論提出了新的挑戰(zhàn)。在文獻(xiàn)[38]中已經(jīng)提出了許多關(guān)于同構(gòu)多處理器系統(tǒng)的硬實(shí)時(shí)調(diào)度算法及其可調(diào)度性分析。他們研究的也是傳統(tǒng)的非并行獨(dú)立實(shí)時(shí)任務(wù)模型。另外，在多處理器系統(tǒng)上調(diào)度偶發(fā)任務(wù)集的問(wèn)題更加復(fù)雜，在論文[39]中被證明是 NP 難問(wèn)題，他的這項(xiàng)工作側(cè)重于 GEDF 調(diào)度算法，并在多項(xiàng)式時(shí)間內(nèi)提供了充分的可調(diào)度性測(cè)試條件，還提出了在偽多項(xiàng)式時(shí)間內(nèi)計(jì)算的更有效但更復(fù)雜的充分可調(diào)度性測(cè)試。關(guān)于具有任務(wù)內(nèi)并行性的實(shí)時(shí)任務(wù)的并行調(diào)度，針對(duì)不同的模型，每個(gè)模型都有自己的優(yōu)點(diǎn)和缺點(diǎn)。首先是 Fork-join 模型，在該模型中并行任務(wù)是并行和非并行段的交替序列。Lakshmanan 等人提出了一種盡可能順序執(zhí)行并行段的拉伸算法并分析了使用分區(qū)截止單調(diào)（DM）調(diào)度算法的資源增加界限（resourceaugmentationbound）。資源增
本文編號(hào)：3305119
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/3305119.html
最近更新
教材專(zhuān)著
