  In this paper, we present a general response-time analysis and
schedulability-test framework, called k2Q (k to Q). It provides automatic
constructions of closed-form quadratic bounds or utilization bounds for a wide
range of applications in real-time systems under fixed-priority scheduling. The
key of the framework is a $k$-point schedulability test or a $k$-point response
time analysis that is based on the utilizations and the execution times of
$k-1$ higher-priority tasks. The natural condition of k2Q is a quadratic form
for testing the schedulability or analyzing the response time. The response
time analysis and the schedulability analysis provided by the framework can be
viewed as a "blackbox" interface that can result in sufficient
utilization-based analysis. Since the framework is independent from the task
and platform models, it can be applied to a wide range of applications.
  We show the generality of k2Q by applying it to several different task
models. k2Q produces better uniprocessor and/or multiprocessor schedulability
tests not only for the traditional sporadic task model, but also more
expressive task models such as the generalized multi-frame task model and the
acyclic task model. Another interesting contribution is that in the past,
exponential-time schedulability tests were typically not recommended and most
of time ignored due to high complexity. We have successfully shown that
exponential-time schedulability tests may lead to good polynomial-time tests
(almost automatically) by using the k2Q framework.
