發(fā)布時間：2020-03-25 08:15

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

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

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

【參考文獻】

相關期刊論文 前5條

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

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

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

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

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

相關博士學位論文 前7條

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

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

3 朱萍;硬實時容錯調度算法研究[D];華中科技大學;2011年

4 江維;任務關鍵實時系統(tǒng)的可信感知調度研究[D];電子科技大學;2009年

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

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

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

本文編號：2599653