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

Citations Over TimeTop 10% of 2013 papers

Abstract

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.

Related Papers

• → Schedulability Analysis for Real-Time Systems with EDF Scheduling(2009)209 cited
• → The limited-preemption uniprocessor scheduling of sporadic task systems(2005)119 cited
• → Combining EDF and LST to enhance the performance of real-time task scheduling(2016)12 cited
• → The research of scheduling algorithms in real-time system(2010)19 cited
• → Schedulability analysis of task scheduling in multiprocessor real-time systems using EDF algorithm(2012)9 cited