The application of static optimization techniques to real-time task scheduling has been investigated. Few pieces of work, however, have been reported which propose and investigate on-line optimization techniques for dynamic scheduling of real-time tasks. In such task domains, the difficulty of scheduling is exacerbated by the fact that the cost of scheduling itself contributes directly to the performance of the algorithms and that it cannot be ignored. In this thesis, we propose algorithms that address a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The algorithms control the time allocated to scheduling explicitly, in order to obtain good-quality schedules in reasonable times. We show that taking into account the...[ Read more ]

The application of static optimization techniques to real-time task scheduling has been investigated. Few pieces of work, however, have been reported which propose and investigate on-line optimization techniques for dynamic scheduling of real-time tasks. In such task domains, the difficulty of scheduling is exacerbated by the fact that the cost of scheduling itself contributes directly to the performance of the algorithms and that it cannot be ignored. In this thesis, we propose algorithms that address a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The algorithms control the time allocated to scheduling explicitly, in order to obtain good-quality schedules in reasonable times. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled real-time tasks. Beside the scheduling time, the available processing units provide another resource to manage optimization. Scheduling algorithms are expected to scale-up to the high-end in terms of deadline compliance as more time and/or processors are added. When multiple processing units are provided, real-time system researchers emphasize a search for an appropriate ordering of tasks to satisfy problem constraints more than they emphasize the choice of processors to which tasks are assigned. Another alternative would be to emphasize more the search for an appropriate assignment of tasks to processors to satisfy problem constraints. We present and study the performance implications of these representations in the context of dynamic scheduling for a multiprocessor architecture. We also introduce a new technique that uses an assignment-oriented representation to dynamically schedule tasks on the processing nodes of a non-uniform memory access multiprocessor architecture. We provide an experimental evaluation of our algorithms via performance comparisons with existing landmark algorithms that were originally designed to address some similar issues. The results of our experiments show that our algorithms outperform the existing techniques in several parameter configurations.