An integrated approach to dynamic task and resource management in multiprocessor real-time systems

In a dynamic real-time environment, predictability needs to be provided in the face of unpredictable dynamic task arrivals and asynchronous concurrent sharing of system resources. Consequently, the underlying computer system for dynamic real-time systems needs to manage time explicitly as a resource in order to support applications\u27 timing constraints. Such time management requires that the system be time conscious, time conscientious, and time conserving. These three properties encompass the complexity, correctness and performance issues of algorithms designed for a dynamic real-time system. In this dissertation, we take an integrated approach to attack the problems of algorithm design for dynamic multiprocessor real-time systems that require these three properties in the context of on-line scheduling, dispatching, and resource reclaiming. Real-time scheduling algorithms require the use of worst case execution times of tasks. However, the worst case execution time is an upper bound, and the actual execution time of a task at run time varies between some minimum value and this upper bound due to the variabilities inherent in both the computer architecture and the software. The problem of on-line resource reclaiming in a multiprocessor real-time system has not been addressed previously. The research presented in this dissertation represents an initiative effort in characterizing and solving this dynamic resource reclaiming problem. We analyze the worst case run time anomalies that can occur in a multiprocessor schedule where real-time tasks have both resource and processor constraints. We have developed to resource reclaiming algorithms that are correct--guaranteed not to cause run time anomalies, and have bounded complexity. The effectiveness of the algorithms has been demonstrated via simulation and implementation on a multiprocessor kernel. Predictable integration of multiple functional components is a challenge unique to real-time systems. This challenge is exacerbated by the difficulties brought about by the concurrent and asynchronous nature of multiprocessor systems. We demonstrate that, for a dynamic real-time system, it is not sufficient to simply analyze and prove the static properties of an on-line algorithm in isolation of the rest of the system components. The sharing and contention of resources, such as memory, shared system buses, and more importantly time, require the algorithm designer to take an integrated view of the system as a whole, considering the interrelationships of all the system components (be it software, or hardware) that have an effect on the dynamic timing properties of the algorithm at hand. We discuss a predictable integration of scheduling, dispatching, and resource reclamation for a distributed memory real-time multiprocessor system