The Tyche CPU scheduler

Multimedia PCs run a diverse mix of multimedia, interactive, and batch applications. To better support the variety of real-time requirements generated by this application mix, multimedia PCs are evolving from soft to firm real-time systems. The hallmark of a firm real-time system is its ability to provide predictability to the user and applications. Share-based CPU schedulers provide predictable CPU service to applications by allowing fractions of the CPU to be reserved on their behalf; if the share of an application is k, and the sum of all application shares is n, then the application receives at least k/n of the CPU capacity. Share-based CPU schedulers are frequently proposed for use in multimedia systems.; A challenge facing the user of a multimedia PC with a share-based CPU scheduler is to select a share value for every application so that the application receives sufficient resources to help the user accomplish his goals. Finding the optimal share assignment is NP-hard, implying that many choices of application shares will be less than optimal in practice. This thesis argues that a multimedia CPU scheduler must gracefully handle the situation where the user is dissatisfied with an application's performance because its chosen share is too small. In this situation, the system should help the user prioritize among applications, and the scheduler should shift CPU cycles to the more important applications to help satisfy their real-time requirements.; In this dissertation we present a new CPU scheduler called Tyche. Tyche consists of a share-based scheduler augmented with a novel share shifting mechanism that assists the user in achieving his goals when the share of a multimedia or interactive application is too small. We derive the Tyche algorithm mathematically by extending the theory on which many share-based schedulers are based; analyze its real-time properties; and demonstrate that Tyche adds value for the user across a range of multimedia and interactive workloads.