Messages in this thread | | | Subject | [RFC] Extend Linux to support proportional-share scheduling | Date | Tue, 5 Jun 2007 18:56:17 -0700 | From | "Li, Tong N" <> |
| |
Hi all,
I've ported my code to mainline 2.6.21.3. You can get it at http://www.cs.duke.edu/~tongli/linux/. As I said before, the intent of the patch is not to compete with CFS and SD because the design relies on the underlying scheduler for interactive performance. The goal here is to present a complementary design that can ensure stronger MP fairness, which I think is lacking in the existing proposals. Here's a brief overview of the design (I call it Trio for the lack of a better name). Any comments or suggestions will be highly appreciated.
Trio extends the existing Linux scheduler with support for proportional-share scheduling. It uses a scheduling algorithm, called Distributed Weighted Round-Robin (DWRR), which retains the existing scheduler design as much as possible, and extends it to achieve proportional fairness with O(1) time complexity and a constant error bound, compared to the ideal fair scheduling algorithm. The goal of Trio is not to improve interactive performance; rather, it relies on the existing scheduler for interactivity and extends it to support MP proportional fairness.
Trio has two unique features: (1) it enables users to control shares of CPU time for any thread or group of threads (e.g., a process, an application, etc.), and (2) it enables fair sharing of CPU time across multiple CPUs. For example, with ten tasks running on eight CPUs, Trio allows each task to take an equal fraction of the total CPU time, whereas no existing scheduler achieves such fairness. These features enable Trio to complement the mainline scheduler and other proposals such as CFS and SD to enable greater user flexibility and stronger fairness.
tong - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |