多核系统中实时任务调度算法的研究

发布时间：2018-01-14 07:39

本文关键词：多核系统中实时任务调度算法的研究　出处：《南京邮电大学》2012年硕士论文　论文类型：学位论文

【摘要】：随着实时系统应用的日趋广泛,保证系统的实时性变得尤为重要。与此同时,多核系统的飞速发展让多核系统中的实时任务调度问题成为当今IT技术领域的热点问题。新时代的研究焦点是,在任务并行运行的同时,如何保证多核系统的实时性、提高系统的运行效率、缩短任务调度长度以及保持系统的负载平衡。因此,提高多核系统性能最直接的手段是设计出一个好的实时任务调度算法,这也是本课题研究的意义所在。针对多核系统的实时性,本文算法考虑了任务的到达时间、就绪时间和截止期。再结合多核系统的复杂环境,本文研究的是异构多核系统,算法考虑了各内核不同的运行速率和内核间不同的通信带宽。根据目前这个领域的研究成果得知,本文的课题是一个NP完全问题,而智能算法能获取此类型问题的近似最优解决方案。于是本文结合蚁群算法和遗传算法提出了一种新型混合算法用于解决异构多核系统的实时任务调度问题。本文首先建立了异构多核系统的系统模型,包括任务模型、处理器模型、调度模型、约束条件模型,为算法的实现提供了目标环境。其次,详细描述了混合算法的操作步骤,包括任务到任务选择操作、任务选择处理核操作、交叉操作、变异操作、信息量更新操作,同时又涉及若干公式的设计。最后,考虑到交叉和变异操作对原可行解的影响,还提出了一定的筛选机制,从而保证了最终解的质量。为了验证混合算法的性能,本文用C++语言在集成开发环境Microsoft Visual C++ 6.0中实现了该算法,验证了算法的可行性、参数取值分析结果的正确性以及与同类型算法相比的优越性。最终证实,本文的混合算法能够有效解决异构多核系统中的实时任务调度问题。
[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.

【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP316.2;TP332

【参考文献】