Optimizing the ready queue structure for dynamic scheduling strategies in real-time operating systems

Dynamic scheduling strategies employed in real-time operating systems dynamically assign priorities to processes based on the time remained to some predefined deadlines, laxities, or other run-time metrics. Although, theoretically, these strategies do not restrict CPU utilization, in reality, they produce some run-time overhead, which is mainly due to the time required to sort processes in the ready queue each time a process is preempted. This paper trios to attack the above shortcoming by proposing and evaluating two alternative approaches to optimizing the structure of the ready queue in order to eliminate the need for a traditional sorting algorithm and consequently minimize the run-time overhead. These approaches are arbitrarily based on the mathematical properties of laxities (although they-can well be based on the mathematical properties of any other dynamic priority variables considered in the system). It is shown that these approaches can reduce the time complexity of the run-time overhead of dynamic scheduling strategies, in terms of the number of active processes in the ready queue (n), from O(nlogn) to O(n). This can considerably improve the performance of real-time operating systems.