Function-driven Scheduling: a General Framework for Expression and Analysis of Scheduling

Scheduling theory maintains that there are fundamental similarities in problems of sequence that transcend the characteristics of the particular tasks to be ordered or the resources to be used. Traditionally, scheduling policies are implemented using algorithms; we study scheduling algorithms to discover the various properties of the schedules they produce. To facilitate analysis the policies are typically limited to homogeneous task sets (e.g., all periodic tasks) and consider only one or very few task attributes. In some cases the results are so attractive that the task sets of systems are made to fit the algorithm rather than using a policy more appropriate to the system. We therefore make the following observation: if scheduling policies are driven by how well they can be expressed and analyzed, then we need a more general framework for expressing scheduling policies.
We introduce the Importance Abstraction as a general scheduling framework. The scheduling algorithm is invariant: choose the most important task at every point in time. Each task is described by a function, called an importance function, that profiles the task’s importance to the system over time. The importance abstraction can express not only the traditional scheduling policies but a wide range of new policies based on how important individual tasks are to the system. Since the scheduling policy is described using functions rather than a single algorithm we can exploit the maturity of mathematical proof techniques when analyzing the schedule produced by the policy. Since this abstraction is applicable to any system of tasks and processors, we examine the communication subsystem as an example, and find that importance functions facilitate the expression of message discrimination policies as well as help unify scheduling across the operating system/communication subsystem domain boundary.