linux-kernel - Re: RFC for a new Scheduling policy/class in the Linux-kernel

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <200907142128.48558.henrik@austad.us>
Date:	Tue, 14 Jul 2009 21:28:47 +0200
From:	Henrik Austad <henrik@...tad.us>
To:	"James H. Anderson" <anderson@...unc.edu>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Chris Friesen <cfriesen@...tel.com>,
	Raistlin <raistlin@...ux.it>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ted Baker <baker@...fsu.edu>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Noah Watkins <jayhawk@....ucsc.edu>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>,
	Bjoern Brandenburg <bbb@...unc.edu>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

On Tuesday 14 July 2009 18:54:13 James H. Anderson wrote:
> 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.

Using deadlines as the only measure on multi-core will fail as you must 
consider time (of deadline-miss) in a different way.

In UP, this is given implicitly as you only have a single processor. In MC you 
need to do this the hard way, namely compute the point in time not when the 
task misses the deadline, but when it will *eventually* fail a dealine. By 
doing that, you combine deadline, wcet and granted time in one variable, and 
you have a *single* variable to compare.

By doing this in a global sense, you can avoid bin-packing, load-balancing and 
a lot of the issues that seem to be keeping the PI-people busy. But I think 
I'm going to stay away from that topic now (as I haven't had the time to give 
those emails their deserved attention.

I think M^2-LLF would be as good a name as EFF, but I wanted to emphasize the 
usage of the two failure-variables (the static and the dynamic).

> 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).  

the tardiness is either 0 or bounded, depending on what you want (and what you 
will do with tasks that do miss their deadlines when they block on locks).

> 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.

Is this available outside locked portals?

> 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)



-- 
     henrik
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/