Online Feasibility Analysis with Composite-Deadline

Scheduling analysis of fixed priority systems can generally be divided into two categories: (1) utilization based approaches and (2) response time analysis. The farmer class is more efficient but propose a bound on system utilization, while the later posses pseudo-polynomial time complexity and considered to be slow, although its importance has been recognized. For periodic tasks with larger deadlines, we introduce the concept of composite deadline; a deadline which is shared by all jobs released in a given interval. Integrating this concept with response time analysis, we propose a novel solution which is both necessary and sufficient condition, and prove that it is suffix to analyze task feasibility at only one point.