CFS scheduler, -v8
in [Kernel]
|
Prev: Bug in current -git tree causing dbus and gnome to chew up cpu time
Next: Introduce O_CLOEXEC (take >2)
From: Li, Tong N on 2 May 2007 14:50 > Based on my understanding, adopting something like EEVDF in CFS should > not be very difficult given their similarities, although I do not have > any idea on how this impacts the load balancing for SMP. Does this worth > a try? > > Sorry for such a long email :-) Thanks for the excellent explanation. I think EEVDF and many algs alike assume global ordering of all tasks in the system (based on virtual time), whereas CFS does so locally on each processor and relies on load balancing to achieve fairness across processors. It'd achieve strong fairness locally, but I'm not sure about its global fairness properties in an MP environment. If ideally the total load weight on each processor is always the same, then local fairness would imply global fairness, but this is a bin packing problem and is intractable ... tong - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: William Lee Irwin III on 2 May 2007 15:00 * William Lee Irwin III <wli(a)holomorphy.com> wrote: >> Virtual time is time from the task's point of view, which it has spent >> executing. ->wait_runtime is a device to subtract out time spent on >> the runqueue but not running from what would otherwise be virtual time >> to express lag, whether deliberately or coincidentally. [...] On Wed, May 02, 2007 at 08:15:33PM +0200, Ingo Molnar wrote: > CFS is in fact _built around_ the ->wait_runtime metric (which, as its > name suggests already, expresses the precise lag a task observes > relative to 'ideal' fair execution), so what exactly makes you suspect > that this property of the ->wait_runtime metric might be 'coincidental'? > ;-) The coincidental aspect would be that at the time it was written, the formal notion of lag was not being used particularly with respect to priorities and load weights. The documentation doesn't describe it in those terms, and I can't read minds, so I refrained from guessing. Things are moving in good directions on all this as far as I'm concerned. Moving according to Ting Yang's analysis should wrap up the soundness concerns about intra-queue policy I've had. OTOH load balancing I know much less about (not that I was ever any sort of an expert on single queue affairs). That remains a very deep concern, as load balancing is where most of the enterprise performance improvements and degradations occur. -- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Ingo Molnar on 2 May 2007 15:20 * William Lee Irwin III <wli(a)holomorphy.com> wrote: > The coincidental aspect would be that at the time it was written, the > formal notion of lag was not being used particularly with respect to > priorities and load weights. [...] (nice levels for SCHED_OTHER are 'just' an add-on concept to the core of CFS, in fact i had two wildly different approaches that both did the trick for users, so i fail to see the relevance of priorities to the core concept of measuring how much a task is waiting to get on the runqueue via the 'fair clock' ... but lets move on.) > Things are moving in good directions on all this as far as I'm > concerned. Moving according to Ting Yang's analysis should wrap up the > soundness concerns about intra-queue policy I've had. OTOH load > balancing I know much less about (not that I was ever any sort of an > expert on single queue affairs). [...] the whole move to ->load_weight based calculations was to make CFS integrate better with load-balancing and to bring the smpnice infrastructure even more into the scheduler mainstream. [ There's a small smpnice related buglet i fixed in -v9-to-be (based on Balbir Singh's feedback), but otherwise it behaves quite well on SMP and that's not a big surprise: i left the load-balancer largely intact. ] Ingo - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: William Lee Irwin III on 2 May 2007 15:20 At some point in the past, Ting Yang wrote: >> Based on my understanding, adopting something like EEVDF in CFS should >> not be very difficult given their similarities, although I do not have >> any idea on how this impacts the load balancing for SMP. Does this worth >> a try? >> Sorry for such a long email :-) On Wed, May 02, 2007 at 11:42:20AM -0700, Li, Tong N wrote: > Thanks for the excellent explanation. I think EEVDF and many algs alike > assume global ordering of all tasks in the system (based on virtual > time), whereas CFS does so locally on each processor and relies on load > balancing to achieve fairness across processors. It'd achieve strong > fairness locally, but I'm not sure about its global fairness properties > in an MP environment. If ideally the total load weight on each processor > is always the same, then local fairness would imply global fairness, but > this is a bin packing problem and is intractable ... It's sort of obvious how to approximate it, but not entirely obvious whether a given approximation actually suffices. More help with the theoretical aspects is needed. - wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: William Lee Irwin III on 2 May 2007 15:50
* William Lee Irwin III <wli(a)holomorphy.com> wrote: >> Things are moving in good directions on all this as far as I'm >> concerned. Moving according to Ting Yang's analysis should wrap up the >> soundness concerns about intra-queue policy I've had. OTOH load >> balancing I know much less about (not that I was ever any sort of an >> expert on single queue affairs). [...] On Wed, May 02, 2007 at 09:12:35PM +0200, Ingo Molnar wrote: > the whole move to ->load_weight based calculations was to make CFS > integrate better with load-balancing and to bring the smpnice > infrastructure even more into the scheduler mainstream. [ There's a > small smpnice related buglet i fixed in -v9-to-be (based on Balbir > Singh's feedback), but otherwise it behaves quite well on SMP and that's > not a big surprise: i left the load-balancer largely intact. ] Despite the original motive, the ->load_weight -based calculations largely resolved my concerns about intra-queue prioritization. They were the change to the ->fair_key computation I wanted to see, which were still not enough because of the O(rq->nr_running) lag issue due to the differences from EEVDF, but I wasn't entirely aware of that, only suspicious that some issue remained. Load balancing has non-negligible impacts on fairness but I'm almost entirely ignorant of the aspects of the theory relating to it. More knowledgeable people, e.g. Tong Li and Ting Yang, need to take over reviewing here much as they did on the intra-queue front, where I only knew enough to drop hints and not to make more useful suggestions. O(1) vs. O(lg(n)) priority queues are not what matter here (well, obviously O(n) priority queues would break), but rather O(1) vs. O(n) lag. -- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |