Flexible Fair Scheduling on Multiprocessors

University Of North Carolina At Chapel Hill, Chapel Hill NC

Investigators

Abstract

There has been much recent work on scheduling techniques that ensure fairness, temporal isolation, and timeliness among applications multiplexed on the same resource. Many systems that could benefit from the use of fair scheduling principles have workloads that necessitate the use of multiple processors; consider, for example, the proliferation of Internet service providers that host third-party websites on multiprocessor servers. Unfortunately, most prior work on multiprocessor fair scheduling has been rooted in task models that are too rigid to apply in many settings. The little research on more flexible models that has been done has been almost entirely experimental in nature, with little or no formal analysis of the scheduling algorithms being tested. In this project, fair scheduling algorithms based on rate-based scheduling principles will be developed and analyzed, both formally and experimentally. Specific project objectives include the development of (i) fair scheduling algorithms that minimize task migrations; (ii) extensions to these algorithms that allow tasks to synchronize and share resources; (iii) extensions that allow real-time and non-real-time applications to execute under a common framework; and (iv) techniques for managing dynamically-changing workloads in which tasks may join and leave the system.