A Schedulability Analysis of Deferrable Scheduling Using Patterns

The schedulability testing for the deferrable scheduling algorithm for fixed priority transactions (DS-FP) [24] remains an open problem since its introduction. In this paper, we take the first step towards investigating necessary and sufficient conditions for the DS-FP schedulability. We propose a necessary and sufficient schedulability condition for the algorithm in discrete time systems, and prove its correctness. Based on this condition, we propose a schedulability test algorithm that is more accurate than the prior test based on the sufficient condition proposed in [25]. Our algorithm exploits the fact that there is always a repeating pattern in a DS-FP schedule in discrete time systems. We demonstrate through examples that our schedulability test algorithm outperforms the existing algorithm in terms of accuracy.