本文關(guān)鍵詞：多核系統(tǒng)中實(shí)時(shí)任務(wù)調(diào)度算法的研究　出處：《南京郵電大學(xué)》2012年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 多核系統(tǒng) 異構(gòu) 實(shí)時(shí) 任務(wù)調(diào)度 混合算法

【摘要】：隨著實(shí)時(shí)系統(tǒng)應(yīng)用的日趨廣泛,保證系統(tǒng)的實(shí)時(shí)性變得尤為重要。與此同時(shí),多核系統(tǒng)的飛速發(fā)展讓多核系統(tǒng)中的實(shí)時(shí)任務(wù)調(diào)度問題成為當(dāng)今IT技術(shù)領(lǐng)域的熱點(diǎn)問題。新時(shí)代的研究焦點(diǎn)是,在任務(wù)并行運(yùn)行的同時(shí),如何保證多核系統(tǒng)的實(shí)時(shí)性、提高系統(tǒng)的運(yùn)行效率、縮短任務(wù)調(diào)度長(zhǎng)度以及保持系統(tǒng)的負(fù)載平衡。因此,提高多核系統(tǒng)性能最直接的手段是設(shè)計(jì)出一個(gè)好的實(shí)時(shí)任務(wù)調(diào)度算法,這也是本課題研究的意義所在。 針對(duì)多核系統(tǒng)的實(shí)時(shí)性,本文算法考慮了任務(wù)的到達(dá)時(shí)間、就緒時(shí)間和截止期。再結(jié)合多核系統(tǒng)的復(fù)雜環(huán)境,本文研究的是異構(gòu)多核系統(tǒng),算法考慮了各內(nèi)核不同的運(yùn)行速率和內(nèi)核間不同的通信帶寬。根據(jù)目前這個(gè)領(lǐng)域的研究成果得知,本文的課題是一個(gè)NP完全問題,而智能算法能獲取此類型問題的近似最優(yōu)解決方案。于是本文結(jié)合蟻群算法和遺傳算法提出了一種新型混合算法用于解決異構(gòu)多核系統(tǒng)的實(shí)時(shí)任務(wù)調(diào)度問題。本文首先建立了異構(gòu)多核系統(tǒng)的系統(tǒng)模型,包括任務(wù)模型、處理器模型、調(diào)度模型、約束條件模型,為算法的實(shí)現(xiàn)提供了目標(biāo)環(huán)境。其次,詳細(xì)描述了混合算法的操作步驟,包括任務(wù)到任務(wù)選擇操作、任務(wù)選擇處理核操作、交叉操作、變異操作、信息量更新操作,同時(shí)又涉及若干公式的設(shè)計(jì)。最后,考慮到交叉和變異操作對(duì)原可行解的影響,還提出了一定的篩選機(jī)制,從而保證了最終解的質(zhì)量。 為了驗(yàn)證混合算法的性能,本文用C++語言在集成開發(fā)環(huán)境Microsoft Visual C++ 6.0中實(shí)現(xiàn)了該算法,驗(yàn)證了算法的可行性、參數(shù)取值分析結(jié)果的正確性以及與同類型算法相比的優(yōu)越性。最終證實(shí),本文的混合算法能夠有效解決異構(gòu)多核系統(tǒng)中的實(shí)時(shí)任務(wù)調(diào)度問題。
[Abstract]:Along with the extensive application of real-time system, real-time system has become particularly important. At the same time, the rapid development of multi-core systems for real-time task scheduling problem in multi-core system has become a hot issue in the field of IT technology. The research focus of the new era, while the tasks run in parallel at the same time, how to ensure real-time multi-core system, improve the efficiency of the system, shorten the length of the task scheduling and load balancing system to maintain. Therefore, to improve the most direct means of multi-core system performance is to design a good real-time scheduling algorithm, this is where the significance of the research.
According to the characteristics of real-time multi-core system, this algorithm considers the task arrival time, the ready time and deadline. Combined with the complex environment of multi-core systems, this paper studies the heterogeneous multi-core systems, the algorithm considers the different run rate of every core and the different communication bandwidth between the kernel. According to the current research achievements in this field that this issue is a NP complete problem, while the intelligent algorithm can obtain the approximate optimal solution of this type of problems. So this paper combines ant colony algorithm and genetic algorithm a new hybrid algorithm for real-time task scheduling problems of heterogeneous multi-core system is presented. This paper established a model for heterogeneous multi-core system, including task model, processor model, scheduling model and constraint model, provides the target environment for algorithm implementation. Secondly, a detailed description of the operation steps of the hybrid algorithm At first, including the task to task selection, task to core selection operation, crossover operation, mutation operation, information update operation, involved the design of several formulas. Finally, considering the effect of crossover and mutation operation on the original feasible solutions, also proposed the mechanism of the screen, so as to ensure the quality of the final solution.
In order to verify the performance of the hybrid algorithm, using C++ language in the integrated development environment Microsoft Visual C++ 6 in the implementation of the algorithm in this paper, the feasibility of the algorithm is verified, the superiority of the correctness of the parameters analysis results and compared with the same type of algorithm. The result confirms that this hybrid algorithm can effectively solve the problem of heterogeneous real-time task scheduling nuclear system.

【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP316.2;TP332

【參考文獻(xiàn)】

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

1 徐成;王立東;劉彥;;基于遺傳算法的異構(gòu)多核多幀任務(wù)分配[J];計(jì)算機(jī)應(yīng)用研究;2009年11期

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

1 王旭濤;基于異構(gòu)多核處理器系統(tǒng)的任務(wù)調(diào)度算法研究[D];南京郵電大學(xué);2011年

2 張冬松;實(shí)時(shí)系統(tǒng)的節(jié)能調(diào)度技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2007年

，

本文編號(hào)：1422654