【摘要】：隨著多核/眾核處理器系統(tǒng)以及嵌入式實時應(yīng)用的發(fā)展,多核實時系統(tǒng)的關(guān)鍵技術(shù)研究已成為熱點,實時任務(wù)調(diào)度算法是其核心研究內(nèi)容。在多核計算環(huán)境下,共享資源訪問競爭所導(dǎo)致的任務(wù)同步問題將會延長任務(wù)的執(zhí)行時間,并可能嚴重影響任務(wù)的實時可調(diào)度,從而對實時調(diào)度算法的設(shè)計提出了新的挑戰(zhàn)。因無需任務(wù)的動態(tài)遷移,劃分調(diào)度算法與全局調(diào)度算法相比,可產(chǎn)生較小的運行時開銷,從而具有較好的運行時性能并具備更好的實用性。另一方面,基于鎖機制的資源訪問協(xié)議,例如MSRP(Multiprocessor Stack Resource Policy)等,與懸掛機制相比具有避免死鎖、實現(xiàn)簡單、性能良好等優(yōu)勢,已被廣泛應(yīng)用于實時系統(tǒng)中。面向嵌入式異構(gòu)多核系統(tǒng)的發(fā)展趨勢以及實時應(yīng)用對可靠性日益增長的需求,采用劃分EDF(Earliest Deadline First)算法以及MSRP協(xié)議,研究面向任務(wù)同步的同構(gòu)多核系統(tǒng)容錯劃分調(diào)度以及異構(gòu)多核系統(tǒng)劃分調(diào)度中的實時調(diào)度理論、任務(wù)映射算法以及操作系統(tǒng)內(nèi)核實現(xiàn),旨在解決任務(wù)同步限制下的多核實時調(diào)度中的關(guān)鍵問題。面向資源共享和可靠性需求的同構(gòu)多核實時系統(tǒng),理論探討系統(tǒng)利用率的上界,發(fā)現(xiàn)并從原理上驗證了系統(tǒng)利用率的非單調(diào)性,即更多的處理器核有可能導(dǎo)致系統(tǒng)利用率的下降。以系統(tǒng)利用率上界的理論分析為基礎(chǔ),基于PB(Primary/Backup)容錯機制,提出了一種系統(tǒng)可靠性和任務(wù)同步感知的劃分算法RSA-TPA(Reliability and Synchronization Aware Task Partitioning Algorithm)。首先,對任務(wù)同步干擾的本質(zhì)特征進行分析,提出處理器核數(shù)下降的策略以及一種以資源為導(dǎo)向的新的計算方法,以降低任務(wù)同步開銷上界;估算未劃分任務(wù)的利用率,并據(jù)此進行未劃分任務(wù)(包括主任務(wù)和備份任務(wù))優(yōu)先級的動態(tài)排序;設(shè)計高效的任務(wù)映射策略,使得系統(tǒng)利用率的增長最小化,從而提高任務(wù)集的可調(diào)度比例以及系統(tǒng)的負載均衡能力。另外,為降低算法的時間復(fù)雜度,提出了一種簡化的任務(wù)劃分算法RSA-TPA-efficient。模擬實驗結(jié)果表明,與現(xiàn)有的僅考慮系統(tǒng)可靠性或者任務(wù)同步的劃分算法相比,RSA-TPA具有更高的可調(diào)度比例(可提升60%以上)以及更均衡的系統(tǒng)負載。面向共享資源的異構(gòu)多核實時系統(tǒng),首先給出最壞情況下的任務(wù)同步開銷并推導(dǎo)可調(diào)度充分條件,據(jù)此求解近似的系統(tǒng)利用率上界,從中同樣發(fā)現(xiàn)系統(tǒng)利用率非單調(diào)性的規(guī)律。以系統(tǒng)利用率的悲觀性分析為啟發(fā),提出一種同步感知的異構(gòu)多核實時系統(tǒng)任務(wù)劃分算法SA-TPA-HM(Synchronization Aware Task Partitioning Algorithm for Heterogeneous Mmulticores)。首先,提出異構(gòu)計算平臺上降低任務(wù)同步開銷上界的新的計算方法,以提高任務(wù)的調(diào)度比例;動態(tài)計算未劃分任務(wù)的優(yōu)先權(quán),確定任務(wù)劃分順序以提高任務(wù)集合調(diào)度的可行性;基于此,多次試探并計算系統(tǒng)利用率,確保每次任務(wù)劃分可最小化系統(tǒng)利用率的增長以均衡系統(tǒng)負載。模擬實驗結(jié)果表明,與傳統(tǒng)的同構(gòu)多核系統(tǒng)中任務(wù)劃分算法相比,SA-TPA-HM能明顯提高任務(wù)集合的可調(diào)度比例(可提升60%以上)。為進一步驗證提出的劃分算法的實用性,在Linux操作系統(tǒng)內(nèi)核中實現(xiàn)了提出的算法以及其它測試算法。實測結(jié)果表明,與現(xiàn)有算法相比,RSA-TPA和SA-TPAHM劃分算法可生成系統(tǒng)負載更為均衡的劃分,減少處理器核上在EDF調(diào)度下的上下文切換次數(shù),從而產(chǎn)生較少的在線開銷(可減少15%以上),因此具備更好的應(yīng)用價值。
【圖文】：

同的臨界區(qū)多次訪問同一種資源。假設(shè)任務(wù)i 有in 個臨界區(qū)，第 x 個臨界區(qū)（ 1,...,ix n ）記為i ,xz ，該臨界區(qū)訪問的資源記為 ( )i ,xr R 且基于最低處理核速率1f的臨界區(qū)執(zhí)行時間記為i ,xc 。具體的任務(wù)參數(shù)如圖 2-1 所示。在多核實時系統(tǒng)中，訪問共享資源的任務(wù)劃分至處理器核的基本流程如圖 2-2 所示。整個過程包含兩個步驟：首先確定任務(wù)集合Ψ中所有未劃分任務(wù)的劃分優(yōu)先權(quán)，然后選擇具有最高劃分優(yōu)先權(quán)的任務(wù)，挑選合適的處理器核并將該任務(wù)映射至該處理器核。任務(wù)劃分完畢后，每個處理器核上的所有任務(wù)遵循 EDF 算法以及 MSRP 資源訪問協(xié)議執(zhí)行。圖 2-1 單個任務(wù)的參數(shù)說明

華 中 科 技 大 學(xué) 博 士 學(xué) 位 論 文界區(qū)多次訪問同一種資源。假設(shè)任務(wù)i 有in 個臨界區(qū)，，第 x 個臨,...,in ）記為i ,xz ，該臨界區(qū)訪問的資源記為 ( )i ,xr R 且基于最低處理核區(qū)執(zhí)行時間記為i ,xc 。具體的任務(wù)參數(shù)如圖 2-1 所示。在多核實時系統(tǒng)資源的任務(wù)劃分至處理器核的基本流程如圖 2-2 所示。整個過程包含先確定任務(wù)集合Ψ中所有未劃分任務(wù)的劃分優(yōu)先權(quán)，然后選擇具有最的任務(wù)，挑選合適的處理器核并將該任務(wù)映射至該處理器核。任務(wù)劃個處理器核上的所有任務(wù)遵循 EDF 算法以及 MSRP 資源訪問協(xié)議執(zhí)行
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2019
【分類號】：TP332;TP301.6

【參考文獻】

相關(guān)期刊論文 前5條

1 劉加海;楊茂林;雷航;廖勇;;共享資源約束下多核實時任務(wù)分配算法[J];浙江大學(xué)學(xué)報(工學(xué)版);2014年01期

2 丁萬夫;郭銳鋒;彭健鈞;秦承剛;邵志香;;面向硬實時系統(tǒng)的容錯調(diào)度算法研究[J];小型微型計算機系統(tǒng);2010年09期

3 李仁發(fā);劉彥;徐成;;多處理器片上系統(tǒng)任務(wù)調(diào)度研究進展評述[J];計算機研究與發(fā)展;2008年09期

4 毛南;黃嵐;王忠義;劉志存;;實時嵌入式容錯系統(tǒng)的關(guān)鍵技術(shù)研究[J];計算機工程與設(shè)計;2007年14期

5 陳宇,熊光澤;容錯最早時限優(yōu)先調(diào)度[J];計算機工程與科學(xué);2001年05期

相關(guān)博士學(xué)位論文 前7條

1 黃樂天;片上多核系統(tǒng)能效及可靠性優(yōu)化方法研究[D];電子科技大學(xué);2016年

2 周正勇;實時系統(tǒng)的容錯調(diào)度技術(shù)研究[D];華中科技大學(xué);2014年

3 朱萍;硬實時容錯調(diào)度算法研究[D];華中科技大學(xué);2011年

4 江維;任務(wù)關(guān)鍵實時系統(tǒng)的可信感知調(diào)度研究[D];電子科技大學(xué);2009年

5 王健;容錯系統(tǒng)中實時任務(wù)調(diào)度和負載均衡算法研究[D];浙江大學(xué);2009年

6 李俊;容錯硬實時系統(tǒng)的可調(diào)度性分析[D];華中科技大學(xué);2007年

7 周雙娥;實時分布容錯系統(tǒng)的任務(wù)調(diào)度技術(shù)研究[D];哈爾濱工程大學(xué);2003年

本文編號：2599653