  An increasing number of real-time applications with compute and/or
communication deadlines are being supported on shared infrastructure. Such
applications can often tolerate occasional deadline violations without
substantially impacting their Quality of Service (QoS). A fundamental problem
in such systems is deciding how to allocate shared resources so as to meet
applications' QoS requirements. A simple framework to address this problem is
to, (1) dynamically prioritize users as a possibly complex function of their
deficits (difference of achieved vs required QoS), and (2) allocate resources
so to expedite users with higher priority. This paper focuses on a general
class of systems using such priority-based resource allocation. 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 paper 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.
