Feedback-based scheduling: a toolbox approach

Fine-grain scheduling based on software feedback was introduced in the Synthesis operating system to solve two problems: the dependency between jobs in a pipeline and the low-latency requirements of multimedia type applications. The performance level achieved and the adaptiveness of applications running on Synthesis demonstrated the success of fine-grain scheduling based on software feedback. However, the Synthesis implementation of software feedback is specialized for that particular architecture and a particular application (pipelined process scheduling). Consequently, despite the proven success of fine-grain scheduling, it is not easy to port it to another operating system or to apply its lessons elsewhere, even within Synthesis. To address the problems of portability and extensibility of software feedback scheduling mechanisms, we have taken a toolbox approach in our current research. Instead of creating a specialized solution for each particular scheduling problem, we are developing a toolbox of standard, relatively simple components with well-defined performance and functionality characteristics. The goal is the ability to quickly implement sophisticated software feedback mechanisms by composing these basic toolbox components. The intended applications are primarily in the adaptive scheduling needed in multimedia and real-time domains, especially when input/output operations introduce a large variance in job completion time,