Fixed-Priority Schedulability of Arbitrary-Deadline Sporadic Tasks upon Periodic Resources

Schedulability for compositional real-time systems has been the focus of a great deal of recent research. In this problem domain, we consider the fixed-priority (FP) scheduling of arbitrary-deadline sporadic task systems upon periodic resources. Existing exact or approximate schedulability tests for dedicated uniprocessor scheduling can be used in this setting by modeling the “no-supply period ” of the periodic resource model as a special highest priority task. However, the exact schedulability test is highly inefficient from computational perspective, and the straightforward approximate test is pessimistic due to the approximation on the resource unavailability along with the resource demand. In this paper, along with obtaining an exact characterization of schedulability for this setting, we address the need for efficient and effective schedulability results for the large and important class of arbitrary-deadline task systems by deriving a polynomial-time sufficient schedulability algorithm. By simulations, we show that this algorithm performs very well compared with the exact test, and even better than the approximate test. I