Scheduling policies for real-time systems exhibit threshold behavior that is related to the utilization of the task set they schedule, and in some cases this threshold is sharp. For the rate monotonic scheduling policy, we show that periodic workload with utilization less than a threshold @math can be scheduled almost surely and that all workload with utilization greater than @math is almost surely not schedulable. We study such sharp threshold behavior in the context of processor scheduling using static task priorities, not only for periodic real-time tasks but for aperiodic real-time tasks as well. The notion of a utilization threshold provides a simple schedulability test for most real-time applications. These results improve our understanding of scheduling policies and provide an interesting characterization of the typical behavior of policies. The threshold is sharp (small deviations around the threshold cause schedulability, as a property, to appear or disappear) for most policies; this is a happy consequence that can be used to address the limitations of existing utilization-based tests for schedulability. We demonstrate the use of such an approach for balancing power consumption with the need to meet deadlines in web servers.
Our work presents a fresh perspective on scheduling for real-time systems. Only Lehoczky, Sha and Ding @cite_1 have attempted to obtain average-case results. For rate monotonic scheduling, they characterized the breakdown utilization of the rate monotonic policy for the Liu and Layland model of real-time tasks as @math . Breakdown utilization, however, is not the same as a utilization threshold, and the connection between the two needs to be examined more closely. The methodology we employ in obtaining our results is new and extremely general. It was not possible to reason in a rather abstract sense about the average-case behavior of scheduling policies with the more traditional analysis techniques of time demand and resource supply. Furthermore, our abstraction allows for reasoning about multi-stage and multiprocessor systems. Dutertre @cite_30 identified phase transitions in a non-preemptive recurring task scheduling problem. While Dutertre's work emphasized the empirical evidence for sharp thresholds, we have provided the mathematical basis for the existence of sharp thresholds.
@cite_30 @cite_1
2112780035 2166440675
We present an approach to computing cyclic schedules online and in real time, while attempting to maximize a quality-of-service metric. The motivation is the detection of RF emitters using a schedule that controls the scanning of disjoint frequency bands. The problem is NP-hard, but it exhibits a so-called phase transition that can be exploited to rapidly find a "good enough" schedule. Our approach relies on a graph-based schedule-construction algorithm. Selecting the input to this algorithm in the phase-transition region ensures, with high probability, that a schedule will be found quickly, and gives a lower bound on the quality of service this schedule will achieve. An exact characterization of the ability of the rate monotonic scheduling algorithm to meet the deadlines of a periodic task set is represented. In addition, a stochastic analysis which gives the probability distribution of the breakdown utilization of randomly generated task sets is presented. It is shown that as the task set size increases, the task computation times become of little importance, and the breakdown utilization converges to a constant determined by the task periods. For uniformly distributed tasks, a breakdown utilization of 88 is a reasonable characterization. A case is shown in which the average-case breakdown utilization reaches the worst-case lower bound of C.L. Liu and J.W. Layland (1973). >