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.

I. Introduction

With the rapid development of the computer and electronics industry, large-scale multi-core computing platform is widely adopted in many areas. For example, in the aviation field, the Integrated Modular Avionics (IMA) which uses multi-core computing platform has been widely used. The avionic industry is transitioning from federated avionics architectures to IMA-based architectures to meet the increasing system requirements [1], [2]. Although the adoption of the IMA system can reduce the design cost of the aeronautical system [3], the task scheduling and allocation problem in IMA system has become an increasingly complex problem with the increase in the amount of task computation. In the field of communication, cloud computing and etc., the problem of non-preemptive strictly periodic task scheduling on large-scale multi-core computing platform is also worthy of further study.