Optimal Order Assignment Algorithms for Single-Rate Time-Driven AFAP Cyclic Executives

In a recent survey, it was observed that the majority of the respondents to the question which task scheduling policy/policies are used in considered systems answered 'static cycle/table driven/time-Triggered'. Cyclic executives, though hardly addressed in contemporary text books, if at all, are therefore still in use in practice. Hence, there is a need for analysis techniques for these executives.In earlier work, exact analysis for single-rate AFAP (as fast as possible) and single-rate time-driven AFAP cyclic executives, scheduling a given sequence of independent hard real-Time polling tasks in single-processor systems, have been presented. Unlike the analysis for single-rate AFAP cyclic executives, the analysis for single-rate time-driven AFAP cyclic executives depends on the order of the tasks in the cycle. In this paper, we present two optimal order assignment (OOA) algorithms for single-rate time-driven AFAP cyclic executives. The first algorithm yields a schedulable order of tasks if and only if such an order exists. The second algorithm enhances the first by yielding an order that maximizes the cycle time of the executive, effectively maximizing energy efficiency or improving the average response times of background tasks.