k2Q: A Quadratic-Form Response Time and Schedulability Analysis Framework for Utilization-Based Analysis

In this paper, we present a general response-time analysis and schedulability-test framework, called k2Q. 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 higher-priority tasks. We show the generality of k2Q by applying it to several different task models. Specifically, we achieve many new results in uniprocessor and multiprocessor scheduling for not only traditional sporadic task models, but also some more advanced and expressive task models. In the past, exponential-time schedulability tests were typically not recommended and most of time ignored, as this requires very high complexity. We have successfully shown in this paper that exponential-time schedulability tests may lead to good polynomial-time tests (almost automatically) by using the k2Q framework. Analogously, a similar concept by testing only k points with a different formulation has been studied by us in another framework, called k2U, which provides hyperbolic bounds or utilization bounds based on a different formulation of schedulability test. With the quadratic and hyperbolic forms, k2Q and k2U frameworks can be used to provide many quantitive features to be measured, like the total utilization bounds, speed-up factors, etc., not only for uniprocessor scheduling but also for multiprocessor scheduling. These frameworks can be viewed as a "blackbox" interface for schedulability tests and response-time analysis.