  Competitive analysis of online algorithms has commonly been applied to
understand the behaviour of real-time systems during overload conditions. While
competitive analysis provides insight into the behaviour of certain algorithms,
it is hard to make inferences about the performance of those algorithms in
practice. Other approaches to dealing with overload resort to heuristics that
seem to perform well but are hard to prove as being good. Further, most work on
handling overload in real-time systems does not consider using information
regarding the distribution of arrival rates of jobs and execution times to make
scheduling decisions. We present an scheduling policy (obtained through
stochastic approximation, and using information about the workload) to handle
overload in real-time systems and improve the revenue earned when each
successful job completion results in revenue accrual. We prove that the policy
we outline does lead to increased revenue when compared to a class of
scheduling policies that make static resource allocations to different service
classes. We also use empirical evidence to underscore the fact that this policy
performs better than a variety of other scheduling policies. The ideas
presented can be applied to several soft real-time systems, specifically
systems with multiple service classes.
