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

作者：Chen, Jinchao^*; Du, Chenglie; Xie, Fei; Yang, Zhenkun

来源：Real-Time Systems, 2016, 52(3): 239-271.

DOI：10.1007/s11241-015-9226-z

• Schedulability analysis
• Non-preemptive scheduling
• Strictly periodic task
• Multi-core system
• Multi-task scheduling

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.

• 出版日期2016-5
• 单位西北工业大学