The Explicit Incorporation of Variance in the Performance Modeling of Scheduling Algorithms in Distributed and Soft Real-Time Systems

Abstract

As distributed and real-time systems become more pervasive, there is growing interest in their performance and reliability. The workloads found in these environments can exhibit variability that results in unpredictable and undesirable system behavior. Therefore, a key requirement in analyzing such systems is developing robust models and tools that accurately replicate the task workload and correctly mimic the variability found in real-world environments.

Based on observations made during a case study of an enterprise grid environment, the method of stages modeling technique is adopted and applied to the performance evaluation of soft real-time systems. This approach achieves a two-moment match of performance parameters and allows the effects of variance to be studied in a uniform and systematic manner. Based on this technique, a new discrete-event simulator, the Method Of Stages Simulator (MOSS), is developed and used to conduct sensitivity analysis experiments on the variance of task parameters such as arrival, service, and deadline rates. The Matlab State-space Analysis Tool (MSAT) is also developed, which constructs and analytically solves state-space models representing small real-time systems.

Traditional real-time scheduling algorithms such as Rate Monotonic (RM), Earliest Deadline First (EDF), and Least Laxity First (LLF) ignore the variance of performance parameters when allocating resources. However, this variance can directly influence the choice of the best scheduling algorithm, particularly under varying system loads. Explicit incorporation of variance in scheduling decisions leads to hybrid scheduling algorithms that are insensitive to, or unaffected by, the workload variability. Results from MOSS sensitivity analysis experiments suggest a promising new scheduling algorithm, TLAX (Threshold LAXity), that outperforms the traditional algorithms by as much as 50% in heavy load conditions. MSAT is used to analytically validate the results obtained from MOSS and to gain further insight into the robust TLAX algorithm. The explicit incorporation of variance in the performance modeling of scheduling algorithms improves the design, efficiency, and performance of distributed and soft real-time systems.