Efficiency and Optimality of Largest Deficit First Prioritization: Dynamic User Prioritization for Soft Real-Time Applications

摘要

An increasing number of real-time applications with compute and/or communication deadlines are being supported on a shared infrastructure. Such applications can often tolerate occasional deadline violations without substantially impacting their Quality of Service (QoS). This article explores the efficient allocation of shared resources to satisfy such QoS requirements. We study a simple framework which decouples this problem into two subproblems: (1) dynamic prioritization of users based on arbitrary functions of their deficits (difference of achieved vs. required QoS), and (2) priority-based resource allocation on the underlying compute fabric. In this article, we shall assume the solution to the latter is fixed, e.g., as realized in the task prioritization capabilities of current hardware/software, and focus on compatible solutions to the former. We first characterize the set of feasible QoS requirements and show the optimality of max weight-like prioritization. We then consider simple weighted Largest Deficit First (w-LDF) prioritization policies, where users with higher weighted QoS deficits are given higher priority. The article gives an inner bound for the feasible set under w-LDF policies, and, under an additional monotonicity assumption, characterizes its geometry leading to a sufficient condition for optimality. Additional insights on the efficiency ratio of w-LDF policies, the optimality of hierarchical-LDF, and characterization of clustering of failures are also discussed.