A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03282011-020103

Type of Document Dissertation
Author Hamm, Nathan
URN etd-03282011-020103
Title The Explicit Incorporation of Variance in the Performance Modeling of Scheduling Algorithms in Distributed and Soft Real-Time Systems
Degree PhD
Department Computer Science
Advisory Committee
Advisor Name Title
Larry Dowdy Committee Chair
Aniruddha Gokhale Committee Member
J. Michael Fitzpatrick Committee Member
Jeremy Spinrad Committee Member
Mark McDonald Committee Member
  • soft real-time
  • performance analysis
  • evaluation
  • scheduling algorithms
  • simulation
  • variance
Date of Defense 2011-03-15
Availability unrestricted
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.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  01_Hamm_dissertation_complete.pdf 12.96 Mb 01:00:00 00:30:51 00:27:00 00:13:30 00:01:09

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.