Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems

• DOI: 10.1007/s11241-015-9226-z
• Publication Date: 2015-04-30T02:40:56Z
• Authors: Jinchao Chen; Chenglie Du; Fei Xie; Zhenkun Yang
• Keywords: Preemption; Worst-case execution time; Processor scheduling; Multi-core processor

Non-preemptive tasks with strict periods are usually adopted in practical real-time systems where missing deadlines may lead to catastrophic situations. Their schedulability analysis plays a crucial role in guiding the design and development of such real-time systems. In this paper, we study the schedulability analysis problem of partitioned non-preemptive scheduling for strictly periodic tasks on multiprocessors. We propose a set of schedulability conditions, which determines whether a new task can be scheduled on a processor without changing the offsets of the existing tasks and identifies all valid start time offsets for the new task if it is schedulable. Based on these conditions, we present a task assignment algorithm, which is not optimal, but provides an upper bound on the number of cores required by a periodic task set. We illustrate this algorithm with a practical example and conduct stimulation experiments with randomly generated task sets to evaluate the performance of our approach from several aspects.