Logo image
Back
Optimizing the ready queue structure for dynamic scheduling strategies in real-time operating systems
Journal article

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

M Sharifi and B Zolfaghari
Computer Systems Science and Engineering, Vol.18(6), pp.325-330
11/2003
Web of Science ID: WOS:000188171900002

Metrics

1 Record Views

Abstract

systems software Queuing theory software publishers online data processing Computer Architecture Computer Operating Systems Computer Science
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 tries 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 call considerably improve the performance of real-time operating systems.

Details

Logo image