Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755716AbZGNQzN (ORCPT ); Tue, 14 Jul 2009 12:55:13 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1755624AbZGNQzM (ORCPT ); Tue, 14 Jul 2009 12:55:12 -0400 Received: from fafnir.cs.unc.edu ([152.2.129.90]:38494 "EHLO fafnir.cs.unc.edu" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755163AbZGNQzL (ORCPT ); Tue, 14 Jul 2009 12:55:11 -0400 Date: Tue, 14 Jul 2009 12:54:13 -0400 (EDT) From: "James H. Anderson" To: Peter Zijlstra cc: Chris Friesen , Raistlin , Douglas Niehaus , Henrik Austad , LKML , Ingo Molnar , Bill Huey , Linux RT , Fabio Checconi , Thomas Gleixner , Ted Baker , Dhaval Giani , Noah Watkins , KUSP Google Group , Tommaso Cucinotta , Giuseppe Lipari , Bjoern Brandenburg , "James H. Anderson" Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel In-Reply-To: <1247589099.7500.191.camel@twins> Message-ID: References: <200907102350.47124.henrik@austad.us> <1247336891.9978.32.camel@laptop> <4A594D2D.3080101@ittc.ku.edu> <1247412708.6704.105.camel@laptop> <1247499843.8107.548.camel@Palantir> <4A5B61DF.8090101@nortel.com> <1247568455.9086.115.camel@Palantir> <4A5C9ABA.9070909@nortel.com> <1247589099.7500.191.camel@twins> User-Agent: Alpine 2.00 (LRH 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2656 Lines: 60 On Tue, 14 Jul 2009, Peter Zijlstra wrote: > > Hi Jim, > > On Tue, 2009-07-14 at 11:19 -0400, James H. Anderson wrote: >> The first email in this thread that I was cc'ed on talked about >> implementing global EDF, > > Hendrik says that its a modified Modified-Least-Laxity-First, so > something like M^2-LLF, and I cc'ed you (and I meant to add Bjorn too, > but now see I failed to actually do so) in the hope that you would have > some thoughts on his scheduling algorithm, since that is what you do a > lot of ;-) > > It could well be he modified M-LLF into G-EDF, but I'm behind in my > reading here, so I'll have to leave that up to others. I meant to say something about this algorithm earlier that may be worthwhile. If I understand Hendrik's algorithm correctly, it falls within a class of global schedulers for which bounded deadline tardiness is guaranteed (as long as total utilization doesn't exceed the system's capacity). This follows from results in: H. Leontyev and J. Anderson, "Generalized Tardiness Bounds for Global Multiprocessor Scheduling", Proceedings of the 28th IEEE Real-Time Systems Symposium, pp. 413-422, December 2007. This is a positive thing w.r.t. wanting to support soft real-time workloads. However, global EDF also has this property and (I would think) is easier to implement (I'm just guessing here -- we haven't actually implemented any algorithm that involves laxities in LITMUS^RT). Ted Baker did some work on an algorithm called EDZL (EDF until zero laxity) that is essentially a hybrid of these two algorithms. In simulations we've done (not based on real implementations), EDZL exhibits really low tardiness (almost non-existent). EDZL may give you the benefits of using laxities where useful and be easier to implement (but that's just my guess) Regarding all these "legacy" issues, I think it would be helpful to write them all down carefully and formally, and then think about what are the *simplest* mechanisms that will do the job in the common case. It is not worthwhile (in my opinion) to introduce tons of complexity to nip at corner cases that aren't that common. Of course, this begs the question of what is "common" and what is not: something that may also be worth trying to find evidence for and writing down. Or better yet, someone needs to define a new standard for multicore... but I'm not sure how that gets done. Gotta go.... -Jim -- 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/