Real-time scheduling algorithms
Hossein Moiin · 1992
This thesis presents novel solutions to the problem of scheduling tasks in a real-time system. A real-time system is defined as a system in which the correctness of results depend not only on the logical correctness of the computations, but also on the time at which the results are produced. Real-time systems have a wide range of applications including process control systems, avionics systems, medical systems and safety systems. The actions in all of these systems must be performed in a timely fashion and the failure to do so may result in severe consequences. In this thesis we investigate scheduling algorithms for distributed and single processor real-time systems. Several scheduling algorithms for distributed systems are investigated and their performances are compared via simulations. Simulation results suggest that distributed algorithms in which scheduling decisions are made by individual processors have better performance than centralized algorithms in which one processor of the system acts as the decision maker. Therefore, to improve the performance of a distributed real-time system it is essential that we understand and develop scheduling algorithms for a uniprocessor system. Our uniprocessor scheduling algorithms are based on a novel and general model of real-time tasks. We extend the definition of real-time tasks so that quality of results and deadline overruns can be modeled in our system. This new model of real-time tasks is used in several scheduling algorithms and the algorithms are simulated to measure their performances. These algorithms are suitable for processor scheduling as well as scheduling of messages in computer networks. The simulation results are encouraging as our heuristic solutions closely approximate the expensive optimal solution, suggesting the possibility of extending these algorithms to dynamic real-time systems.