ENGINEERING AND ANALYSIS OF FIXED PRIORITY SCHEDULERS

Scheduling theory holds great promise as a means to a priori validate timing correctness of real-time applications. However, there currently exists a wide gap between scheduling theory and its implementation in operating system kernels running on specific hardware platforms. The implementation of any particular scheduling algorithm introduces overh ead and blocking components which must be accounted for in the timing correctness validation process. This paper presents a methodology for incorporating the costs of scheduler implementation within the context of fixed priority scheduling algorithms. Both event-driven and timer- driven scheduling implementations are analyzed. We show that for the t imer-driven scheduling implementations the selection of the timer inte rrupt rate can dramatically affect the schedulability of a task set, a nd we present a method for determining the optimal timer rate. We anal yzed both randomly generated and two well-defined task sets and found that their schedulability can be significantly degraded by the impleme ntation costs. Task sets that have ideal breakdown utilization over 90 % may not even be schedulable when the implementation costs are consid ered. This work provides a first step toward bridging the gap between real-time scheduling theory and implementation realities. This gap mus t be bridged for any meaningful validation of timing correctness prope rties of real-time applications.