Scheduling non-preemptive tasks with strict periods in multi-core real-time systems

Non-preemptive tasks with strict periods are usually adopted in practical multi-core real-time systems when continual sampling and processing of data are required. Systems designers need to provide a proper scheduling strategy such that the tasks' deadlines will be met even under the worst-case conditions. In this paper, we study the scheduling problem of non-preemptive tasks with strict periods in multi-core real-time systems. We first derive a necessary and sufficient condition to determine whether a new task is schedulable upon a multi-core platform without changing the allocations of the existing tasks. Then, with a game theory analogy, we design a recursive method to calculate the maximum permissible execution time for a given task, and propose a new schedulability condition used when the start time and processor assignments of the existing tasks can be modified. Finally, based on the conditions derived previously, we present a task assignment algorithm, which not only provides valid allocations for all tasks, but also obtains the minimum number of processors required by the system. Simulation experiments with randomly generated task sets have been conducted to show the high efficiency and reliability of the proposed approach.