The Research On A Scheduling Algorithm For Real-time Tasks In Multi-core Systems

With the increasingly widespread application of real-time systems, it becomes especially important to ensure the systems'performance of real-time. At the same time, the scheduling problem for real-time tasks in multi-core systems has become a hot issue in the field of IT technology, with the rapid development of multi-core systems. In this new era, the research focus is on how to ensure multi-core systems in real time, how to improve the systems'efficiency, how to shorten the length of the task scheduling and how to keep load balance, while the tasks run in parallel. Therefore, the design of a good scheduling algorithm for real-time tasks is the most direct means to improve the multi-core systems'performance, which is also the significance of studying the scheduling algorithm for real-time tasks.Concerning the systems'performance of real-time, the algorithm in the thesis considered the arrival time, the ready time and the deadline of tasks. Combined with the complex environment of multi-core systems, for instance the heterogeneous multi-core systems as we studied, the algorithm took the different run rate of every core and the different communication bandwidth between any two cores into account. According to the current research achievements in this field, the subject of this thesis is known as an NP-complete problem, while the intelligent algorithm can obtain the approximate optimal solution of this type of problems. Then, the thesis proposed a new hybrid algorithm, on the basis of Ant Colony Optimization and Genetic Algorithm, for solving the scheduling problem of real-time tasks in the heterogeneous multi-core systems. At first, the thesis made a heterogeneous multi-core system modeling, including task model, processor model, scheduling model and constraint model, which provided the target environment for algorithm implementation. Secondly, a detailed description of the operation steps of the hybrid algorithm, including the task-to-task selection, task-to-core selection, crossover, mutation and pheromone updating, involved the design of several formulas. Finally, considering the impact of the crossover and mutation operation on the original feasible solutions, a screening mechanism was proposed to ensure the quality of the final solutions.In order to verify the performance of the hybrid algorithm, the thesis realized this algorithm with C ++ language in the integrated development environment named Microsoft Visual C ++ 6.0. Moreover, the thesis verified the feasibility of the algorithm, the correctness of the analysis results of parameter values and the superiority of this hybrid algorithm compared with the same type of other algorithms. Finally, it was confirmed that the hybrid algorithm proposed in this thesis can effectively solve the scheduling problem for real-time tasks in heterogeneous multi-core systems.