View article

The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that …