ADAPTING AND EVALUATING ALGORITHMS

FOR

DYNAMIC SCHEDULABILITY TESTING

February 1994

Charlie McElhone
Department of Computer Science
University of York, England.

ABSTRACT

This report describes an investigation into methods of dynamic schedulability testing. A sporadic task which arrives at a processor must be either rejected or guaranteed to be schedulable alongside the set of tasks already executing on the processor. There already exist algorithms for the static schedulability testing of a task set before run-time. This report describes how these may be adapted to make use of dynamic scheduling data and thus provide an optimal schedulability test for incoming sporadic tasks. The adapted algorithms trade off complexity with pessimism. Their performance may be improved by combining them in a hybrid algorithm. Further performance improvements may be made in all of the algorithms by inserting a timeout in order to limit their worst-case execution time. It is found that the hybrid algorithm still consistently outperforms all of the other adapted algorithms. The hybrid algorithm is then chosen for an investigation into the parameters which determine the optimum value of the performance-enhancing timeout. Finally, this optimum value is made use of, in an investigation into the effect on total processor utilisation, of changing the proportions of periodic and sporadic utilisations.