Exploiting harmonic periods to improve linearly approximated response-time upper bounds

Hard real-time embedded systems need to guarantee that tasks always meet their deadlines. Exact schedulability tests can guarantee this for fixed-priority, preemptively scheduled systems even under the tightest resource constraints. However, these tests are pseudo-polynomial in complexity. This can become a limiting factor in open systems where it might be necessary to have run-time admission tests. A linear-time sufficient test [1] has therefore been developed to estimate response-time upper bounds. In line with utilization-based sufficient tests, we propose to improve this test for task sets with harmonically related task periods. Moreover, we make it possible to reuse this test in the context of hierarchically scheduled (partitioned) resources. In such systems several applications are given a virtual share (budget) of the processor. By modeling the unavailability of processor resources to an application as two fictive tasks, we can also use a budget's period to improve response-time bounds1.