Priority Assignment Algorithms for Real-Time Systems

Abstract

Priority Assignment is one of the crucial problems in the scheduling of fixed-priority real-time systems, which requires both timely response and correctness of output under specified timing constraints. As the models and hardware platforms of real-time systems become increasingly more complex, it is necessary to consider various design metrics in addition to the system schedulability when we assign priorities to tasks. There has been a rich set of research studies on the priority assignment algorithms. However, there exist several limitations in the state-of-the-art: 1) the current research focuses on improving existing schedulability analyses but fails to integrate them with priority assignment algorithms which has better solution quality than heuristics; 2) the stochastic nature of task execution time in real operation and the properties of heterogeneous hardware platforms are not fully studied in the priority assignment process; and 3) design metrics other than response time are omitted in the priority assignment. In this dissertation, we seek to address the issues in the following aspects. First, instead of using existing schedulability analysis directly, we leverage the proposed concept of response time estimation range to build a novel priority assignment framework. It can quickly rule out infeasible priority assignments that share common attributes and be coupled with a more accurate schedulability analysis than Audsley's Optimal Priority Assignment (OPA) with much weaker compatibility conditions. The framework judiciously takes advantage of optimization techniques and heuristics under different task utilization to achieve better overall acceptance ratio of task system. Second, we consider the attributes of tasks, hardware platform (e.g., heterogeneous platform) and design metrics (e.g., reaction time and data age) of real applications in the process of priority assignment. Current studies assume worst case or certain distribution of tasks' execution times in their response time analysis. However, analysis based on these assumptions are pessimistic and overestimate the response times in some cases. We propose a more general model which does not assume any specific distribution of task execution time and analyze the response time by the convolution method. In addition, we propose stochastic heterogeneous Direct Acyclic Graph (DAG) model to take into account the randomness of execution and heterogeneous hardware platform in real operation. Third, we establish an optimization framework which takes other design metrics (e.g., reaction time, data age), in addition to response time in most studies, as objective and constraints in the optimization process. These design metrics can be important in real applications to guarantee satisfying performance of task system. We demonstrate the effectiveness of our proposed frameworks with several case studies, which have shown that our methods can achieve better system schedulability and/or better run-time.