From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756971AbcAOJJF (ORCPT ); Fri, 15 Jan 2016 04:09:05 -0500 Received: from mail-wm0-f43.google.com ([74.125.82.43]:35566 "EHLO mail-wm0-f43.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756860AbcAOJIU (ORCPT ); Fri, 15 Jan 2016 04:08:20 -0500 Date: Fri, 15 Jan 2016 10:08:00 +0100 From: Luca Abeni To: Peter Zijlstra Cc: linux-kernel@vger.kernel.org, Ingo Molnar , Juri Lelli Subject: Re: [RFC 7/8] Make GRUB a task's flag Message-ID: <20160115100800.5abb36cb@luca-1225C> In-Reply-To: <20160115084150.GD3421@worktop> References: <1452785094-3086-1-git-send-email-luca.abeni@unitn.it> <1452785094-3086-8-git-send-email-luca.abeni@unitn.it> <20160114195651.GG6357@twins.programming.kicks-ass.net> <5698AAAB.9040606@unitn.it> <20160115084150.GD3421@worktop> X-Mailer: Claws Mail 3.8.0 (GTK+ 2.24.10; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, 15 Jan 2016 09:41:50 +0100 Peter Zijlstra wrote: > On Fri, Jan 15, 2016 at 09:15:39AM +0100, Luca Abeni wrote: > > On 01/14/2016 08:56 PM, Peter Zijlstra wrote: > > > >Something with an average runtime/budget that also puts limits on > > >the max (say 2*avg) would be far more amenable to be exposed to > > >unpriv tasks, except since that would directly result in an > > >average tardiness bound this might be non-trivial to combine with > > >tasks not opting for this. > > > I'll try to think about this... The advantage of GRUB is that a > > theoretically sound algorithm already existed; here, we would need > > to design the algorithm so that it does not break the > > SCHED_DEADLINE guarantees. Anyway, this is an interesting > > challenge, I'll work on it :) > > Didn't Baruah and Jim do the whole theory on statistical EDF? Which > shows that if you use a statistical budget the combined distribution > transfers to the tardiness. With stdev=0 for the budgets this > trivially collapses to the regular EDF, since then the combined > distribution is also stdev=0 and you get 0 tardiness (on UP). I remember a paper by Anderson, but it was slightly different from this... Maybe I am remembering the wrong paper... I'll check it again. > But yes, combining the two into one scheduler is 'interesting'. I was > thinking it would be possible with least-laxity-first, since you can > assign the hard (stdev=0) tasks a tighter laxity bound. > > But LLF is horrendously painful to implement IIRC. LLF would be interesting (even because if would help in implementing an optimal SMP scheduler), but yes, it is not simple to implement (at least, as far as I remember). I had a student working on it, who implemented some kind of LLF approximation, but I still have to cleanup the code and see how much useful it can be). Thanks, Luca