Worst-case analysis of feasibility tests for self-suspending tasks

In most real-time systems, tasks invoke external opera-tions processed upon dedicated processors. External opera-tions introduce self-suspension delays in the task behaviors. In such task systems, checking that deadlines will be meet at run-time is NP-Hard in the strong sense. For that rea-son, known response time analysis (RTA) only compute up-per bounds of worst-case response times. These pessimistic estimations lead in practice the designers of a real-time sys-tem to oversize the computer features. The aim of this paper is to quantify the pessimism used in known RTA methods. We propose an exact exponential time feasibility test and de-fine upper bounds of competitive ratio of three known RTA techniques