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 (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.