Scheduling problem in distributed hard real-time computer systems :|a simulation approach to dynamic task scheduling using focused addressing and bidding

Abstract

The unique feature, the time constraint, of hard real-time systems makes them different from the traditional computer systems because in such systems the required tasks must be executed not only functionally correctly but in a timely manner. In this thesis, the scheduling problem of hard real-time tasks in distributed systems is examined in detail. Previous work on the algorithms proposed for scheduling in hard real-time systems is reviewed. A heuristic algorithm which considers not only CPU scheduling but also general resource requirements of tasks is chosen to be evaluated. A set of heuristics that can be used by this algorithm is studied through a sequence of simulations. The heuristic function which is observed to perform the best is incorporated in the distributed scheduling algorithm. In this algorithm the determination of a good destination node for a locally nonguaranteed task, is based on a technique that combines bidding and focused addressing algorithms. Simulation studies are conducted in order to evaluate the performance of the algorithm in a wide range of application enviroil.ments. The performance of the algorithm' is also compared to that of three other distributed scheduling algorithms. It is observed that though this algorithm is sensitive to the characteristics of the environments, it performs well in a wide range of environments, compared with the other algorithms.