Real-time performance guarantees in manufacturing systems.

Most research in real-time scheduling theory assumes idealized system conditions. The issues that can arise in applying the theory to real-world applications remain largely unaddressed, which are the focus of this thesis. In particular, we develop practical approaches for hard and probabilistic deadline guarantees in the presence of real-time operating system (RTOS) unpredictability, such as timer interval and task execution time variations. Our target application domain is open-architecture machine tool controllers. Rate-monotonic (RM) has been proven to be an optimal fixed-priority scheduling algorithm for periodic hard real-time tasks. However, given RTOS unpredictability, the periodicity model of the original RM scheduling theory is no longer true. In order to provide hard deadline guarantees, we introduce an empirical task schedulability model, called Rate-Monotonic in the presence of Timing Unpredictability (RMTU) to augment the RM theory to handle RTOS unpredictability. The model parameters can be determined systematically and empirically. Our experimental measurements confirm the validity of RMTU. While hard real-time tasks require absolute deadline guarantees, others may be able to tolerate some deadline misses. For non-hard real-time tasks that still require a certain level of performance, we develop a practical framework for probabilistic deadline guarantees. The first component of this framework is the Probabilistic Real-Time Constraint Model (PRTCM), with which the tolerance of application task deadline misses can be specified in terms of completion probability. The second component consists of two classes of new scheduling algorithms: completion-probability-cognizant and CPU-utilization-cognizant heuristics. Our comparative study of these heuristics and scheduling algorithms RM, earliest-deadline-first, and first-in-first-out demonstrates the superior performance of some new heuristics under certain load conditions. The last component of the framework is the Measurement-Based Simulation Technique (MBST). It uses individual application task execution times (measured in isolation) as inputs, models task interaction and system overhead, and generates task completion time distributions to determine whether probabilistic deadline guarantees can be made. Applying MBST to our prototype open-architecture milling machine controllers, MBST is shown to produce simulation results that match very well the actual measurements. It can also be used to predict the performance of tasks that have not yet been fully implemented. Finally, we evaluate real-time application development strategies to minimize the impact of RTOS unpredictability. We build a prototype modular controller for a milling machine in the University of Michigan Open-Architecture Controller (UMOAC) testbed. To improve its performance, we experiment with the strategy that tunes the computer system environment for the given application, as well as the strategy that attempts to optimize the structure of the application software itself. Our measurement data show that, while both strategies are effective, the latter produces better results.PhDApplied SciencesComputer scienceIndustrial engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/131828/2/9929989.pd