Feasibility Analysis of Real-Time Periodic Tasks with Offsets

The problem of feasibility analysis of asynchronous periodic task sets, where tasks can have an initial offset, is known to be co-NP-complete in the strong sense. A sufficient pseudo-polynomial test has been proposed by Baruah, Howell and Rosier, which consists in analyzing the feasibility of the corresponding synchronous task set (i.e. all offsets are set equal to 0). If the test gives a positive result, then the original asynchronous task set is feasible; else, no definitive answer can be given. In many cases, this sufficient test is too pessimistic, i.e. it gives no response for many feasible task sets.In this paper, we present a new sufficient pseudo-polynomial test for asynchronous periodic task sets. Our test reduces the pessimism by explicitely considering the offsets in deriving a small set of critical arrival patterns. We show, trough a set of extensive simulations, that our test outperforms the previous sufficient test.