We propose a design methodology for producing CPU schedulers with provable real-time behaviors. Our approach is grounded in the well-known technique of using virtual time to track a fluid model representation of the system. However, our work aims to go far beyond traditional fair sharing schedulers like Weighted Fair Queueing by laying bare the mathematical foundations of virtual time. We show how arbitrary changes described mathematically to the fair sharing fluid model can be manifested in real time in the running system. The BERT scheduler is presented as an example of how to use our framework. We hope that this work will enable the creation of new and interesting real-time scheduling algorithms.
