Scheduling of non-preemptive strictly periodic tasks in multi-core systems

摘要

The problem of scheduling and allocation of non-preemptive strictly periodic tasks in multi-core systems mainly appears in large-scale real-time multi-core systems with strict constraints on time. Although the use of multi-core platform makes greatly improvement on computing power and reliability of electronic systems, it also enhances the complexity of the task scheduling and allocation issues. In the non-preemptive strictly periodic task scheduling research of multi-core system, how to use a minimized number of processors to meet the task execution conditions is an important issue. Based on existing schedulability analysis and related algorithms, we propose the Sequential Task Assignment Algorithm (STAA) to solve the problem of how to minimize the number of processors for non-preemptive strictly periodic real-time tasks in the multi-core system under non-overlapping constraints. We also give formulas based on Mixed Integer Linear Programming (MILP) to calculate the minimum number of processors and the proposed MILP algorithm can get the optimal solution to the problem. Simulation results show that for randomly generated task sets, the STAA is superior to the existing algorithm in efficiency and results and is more efficient than the MILP algorithm and have a small difference in results.