A preorder relation for exact schedulability test

Authors: Youcheng Sun Giuseppe Lipari

Publish Date: 2015/12/08

Volume: 52, Issue: 3, Pages: 323-355

PDF Link

Abstract

In this paper we present an exact schedulability test for sporadic realtime tasks scheduled by the Global Fixed Priority Fully Preemptive Scheduler on a multiprocessor system The analysis consists in modeling the system as a Linear Hybrid Automaton and in performing a reachability analysis for states representing deadline miss conditions To mitigate the problem of state space explosion we propose a preorder relationship over the symbolic states of the model states that are simulated by others can be safely eliminated from the state space We also formulate the concept of decidability interval with respect to a set of constraineddeadline sporadic tasks on multiprocessor The decidability interval is a bounded time interval such that if a deadline miss occurs in the schedule then it is possible to find a configuration of arrival times for the tasks such that the deadline miss happens within the bounded interval Vice versa if no configuration of arrival times produces a deadline miss in the bounded interval then no deadline miss is ever possible in the schedule Hence we prove that the schedulability analysis problem is decidable and we provide a formula for computing the decidability interval To our knowledge this is the first time such a time interval is proposed for sporadic tasks running on multiprocessor The proposed schedulability analysis has been implemented in a software tool For the first time we assess the pessimism of the stateoftheart approximate schedulability test through experiments Moreover we show that the use of the proposed model permits to analyse tasks with more general parameter values than other exact algorithms in the literature Nevertheless even with our approach the complexity remains too high for analysing practical task sets with more than seven tasks

Keywords: