Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks

We study the preemptive scheduling of real-time sporadic tasks on a uniprocessor. We consider both fixed priority (FP) scheduling as well as dynamic priority scheduling by the Earliest Deadline First (EDF) algorithm. We investigate the problems of testing schedulability and computing the response time of tasks. Generally these problems are known to be computationally intractable for task systems with constrained deadlines. In this paper, we focus on the particular case of task systems with harmonic period lengths, meaning that the periods of the tasks pair wise divide each other. This is a special case of practical relevance. We present provably efficient exact algorithms for constrained-deadline task systems with harmonic periods. In particular, we provide an exact polynomial-time algorithm for computing the response time of a task in a system with an arbitrary fixed priority order. This also implies an exact FP-schedulability test. For dynamic priority scheduling, we show how to test EDF-schedulability in polynomial time. Additionally, we give a very simple EDF-schedulability test for the simpler case where relative deadlines and periods are jointly harmonic.