Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Al Boldi]

William Lee Irwin III wrote:
> On Thu, Mar 08, 2007 at 10:31:48PM -0800, Linus Torvalds wrote:
> > No. Really.
> > I absolutely *detest* pluggable schedulers. They have a huge downside:
> > they allow people to think that it's ok to make special-case schedulers.
> > And I simply very fundamentally disagree.
> > If you want to play with a scheduler of your own, go wild. It's easy
> > (well, you'll find out that getting good results isn't, but that's a
> > different thing). But actual pluggable schedulers just cause people to
> > think that "oh, the scheduler performs badly under circumstance X, so
> > let's tell people to use special scheduler Y for that case".
> > And CPU scheduling really isn't that complicated. It's *way* simpler
> > than IO scheduling. There simply is *no*excuse* for not trying to do it
> > well enough for all cases, or for having special-case stuff.
> > But even IO scheduling actually ends up being largely the same. Yes, we
> > have pluggable schedulers, and we even allow switching them, but in the
> > end, we don't want people to actually do it. It's much better to have a
> > scheduler that is "good enough" than it is to have five that are
> > "perfect" for five particular cases.
>
> For the most part I was trying to assist development, but ran out of
> patience and interest before getting much of anywhere. The basic idea
> was to be able to fork over a kernel to a benchmark team and have them
> run head-to-head comparisons, switching schedulers on the fly,
> particularly on machines that took a very long time to boot. The
> concept ideally involved making observations and loading fresh
> schedulers based on them as kernel modules on the fly. I was more
> interested in rapid incremental changes than total rewrites, though I
> considered total rewrites to be tests of adequacy, since somewhere in
> the back of my mind I had thoughts about experimenting with gang
> scheduling policies on those machines taking very long times to boot.
>
> What actually got written, the result of it being picked up by others,
> and how it's getting used are all rather far from what I had in mind,
> not that I'm offended in the least by any of it. I also had little or
> no interest in mainline for it. The intention was more on the order of
> an elaborate instrumentation patch for systems where the time required
> to reboot is prohibitive and the duration of access strictly limited.
> (In fact, downward-revised estimates of the likelihood of such access
> also factored into the abandonment of the codebase.)
>
> I consider policy issues to be hopeless political quagmires and
> therefore stick to mechanism. So even though I may have started the
> code in question, I have little or nothing to say about that sort of
> use for it.
>
> There's my longwinded excuse for having originated that tidbit of code.

I've no idea what both of you are talking about.

How can giving people the freedom of choice be in any way counter-productive?


Thanks!

--
Al

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[William Lee Irwin III]

William Lee Irwin III wrote:
>> I consider policy issues to be hopeless political quagmires and
>> therefore stick to mechanism. So even though I may have started the
>> code in question, I have little or nothing to say about that sort of
>> use for it.
>> There's my longwinded excuse for having originated that tidbit of code.

On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> I've no idea what both of you are talking about.

The short translation of my message for you is "Linus, please don't
LART me too hard."


On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> How can giving people the freedom of choice be in any way counter-productive?

This sort of concern is too subjective for me to have an opinion on it.
My preferred sphere of operation is the Manichean domain of faster vs.
slower, functionality vs. non-functionality, and the like. For me, such
design concerns are like the need for a kernel to format pagetables so
the x86 MMU decodes what was intended, or for a compiler to emit valid
assembly instructions, or for a programmer to write C the compiler
won't reject with parse errors. If Linus, akpm, et al object to the
design, then invalid output was produced. Please refer to Linus, akpm,
et al for these sorts of design concerns.


-- wli

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Al Boldi]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
> >> I consider policy issues to be hopeless political quagmires and
> >> therefore stick to mechanism. So even though I may have started the
> >> code in question, I have little or nothing to say about that sort of
> >> use for it.
> >> There's my longwinded excuse for having originated that tidbit of code.
>
> On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> > I've no idea what both of you are talking about.
>
> The short translation of my message for you is "Linus, please don't
> LART me too hard."

Right.

> On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> > How can giving people the freedom of choice be in any way
> > counter-productive?
>
> This sort of concern is too subjective for me to have an opinion on it.

How diplomatic.

> My preferred sphere of operation is the Manichean domain of faster vs.
> slower, functionality vs. non-functionality, and the like. For me, such
> design concerns are like the need for a kernel to format pagetables so
> the x86 MMU decodes what was intended, or for a compiler to emit valid
> assembly instructions, or for a programmer to write C the compiler
> won't reject with parse errors.

Sure, but I think, even from a technical point of view, competition is a good 
thing to have.  Pluggable schedulers give us this kind of competition, that 
forces each scheduler to refine or become obsolete.  Think evolution.

> If Linus, akpm, et al object to the
> design, then invalid output was produced. Please refer to Linus, akpm,
> et al for these sorts of design concerns.

Point taken.

Linus Torvalds wrote:
> And hey, you can try to prove me wrong. Code talks. So far, nobody has
> really ever come close.
>
> So go and code it up, and show the end result. So far, nobody who actually
> *does* CPU schedulers have really wanted to do it, because they all want
> to muck around with their own private versions of the data structures.

What about PlugSched?


Thanks!

--
Al

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Ryan Hope]

from what I understood, there is a performance loss in plugsched
schedulers because they have to share code....

even if pluggable schedulers is not a viable option, being able to
choose which one was built into the kernel would be easy (only takes a
few ifdefs), i too think competition would be good

On 3/9/07, Al Boldi <a1426z@gawab.com> wrote:
> William Lee Irwin III wrote:
> > William Lee Irwin III wrote:
> > >> I consider policy issues to be hopeless political quagmires and
> > >> therefore stick to mechanism. So even though I may have started the
> > >> code in question, I have little or nothing to say about that sort of
> > >> use for it.
> > >> There's my longwinded excuse for having originated that tidbit of code.
> >
> > On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> > > I've no idea what both of you are talking about.
> >
> > The short translation of my message for you is "Linus, please don't
> > LART me too hard."
>
> Right.
>
> > On Fri, Mar 09, 2007 at 04:25:55PM +0300, Al Boldi wrote:
> > > How can giving people the freedom of choice be in any way
> > > counter-productive?
> >
> > This sort of concern is too subjective for me to have an opinion on it.
>
> How diplomatic.
>
> > My preferred sphere of operation is the Manichean domain of faster vs.
> > slower, functionality vs. non-functionality, and the like. For me, such
> > design concerns are like the need for a kernel to format pagetables so
> > the x86 MMU decodes what was intended, or for a compiler to emit valid
> > assembly instructions, or for a programmer to write C the compiler
> > won't reject with parse errors.
>
> Sure, but I think, even from a technical point of view, competition is a good
> thing to have.  Pluggable schedulers give us this kind of competition, that
> forces each scheduler to refine or become obsolete.  Think evolution.
>
> > If Linus, akpm, et al object to the
> > design, then invalid output was produced. Please refer to Linus, akpm,
> > et al for these sorts of design concerns.
>
> Point taken.
>
> Linus Torvalds wrote:
> > And hey, you can try to prove me wrong. Code talks. So far, nobody has
> > really ever come close.
> >
> > So go and code it up, and show the end result. So far, nobody who actually
> > *does* CPU schedulers have really wanted to do it, because they all want
> > to muck around with their own private versions of the data structures.
>
> What about PlugSched?
>
>
> Thanks!
>
> --
> Al
>
> -
> 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/
>

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[David Lang]

On Fri, 9 Mar 2007, Al Boldi wrote:

>
>> My preferred sphere of operation is the Manichean domain of faster vs.
>> slower, functionality vs. non-functionality, and the like. For me, such
>> design concerns are like the need for a kernel to format pagetables so
>> the x86 MMU decodes what was intended, or for a compiler to emit valid
>> assembly instructions, or for a programmer to write C the compiler
>> won't reject with parse errors.
>
> Sure, but I think, even from a technical point of view, competition is a good
> thing to have.  Pluggable schedulers give us this kind of competition, that
> forces each scheduler to refine or become obsolete.  Think evolution.

The point Linus is makeing is that with pluggable schedulers there isn't 
competition between them, the various developer teams would go off in their own 
direction and any drawbacks to their scheduler could be answered with "that's 
not what we are good at, use a different scheduler", with the very real 
possibility that a person could get this answer from ALL schedulers, leaving 
them with nothing good to use.

David Lang

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[William Lee Irwin III]

William Lee Irwin III wrote:
>> The short translation of my message for you is "Linus, please don't
>> LART me too hard."

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> Right.

Given where the code originally came from, I've got bullets to dodge.


William Lee Irwin III wrote:
>> This sort of concern is too subjective for me to have an opinion on it.

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> How diplomatic.

Impoliteness doesn't accomplish anything I want to do.


William Lee Irwin III wrote:
>> My preferred sphere of operation is the Manichean domain of faster vs.
>> slower, functionality vs. non-functionality, and the like. For me, such
>> design concerns are like the need for a kernel to format pagetables so
>> the x86 MMU decodes what was intended, or for a compiler to emit valid
>> assembly instructions, or for a programmer to write C the compiler
>> won't reject with parse errors.

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> Sure, but I think, even from a technical point of view, competition is a good 
> thing to have.  Pluggable schedulers give us this kind of competition, that 
> forces each scheduler to refine or become obsolete.  Think evolution.

I'm more of a cooperative than competitive person, not to say that
flies well in Linux. There are more productive uses of time than having
everyone NIH'ing everyone else's code. If the result isn't so great,
I'd rather send them code or talk them about what needs to be done.


William Lee Irwin III wrote:
>> If Linus, akpm, et al object to the
>> design, then invalid output was produced. Please refer to Linus, akpm,
>> et al for these sorts of design concerns.

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> Point taken.

Decisions with respect to overall kernel design are made from well
above my level. Similarly with coding style, release management, code
directory hierarchy, nomenclature, and more. These things are Linus'
and devolved to those who go along with him on those fronts. If I
made those decisions, you might as well call it "wlix" not "Linux."


Linus Torvalds wrote:
>> And hey, you can try to prove me wrong. Code talks. So far, nobody has
>> really ever come close.
>> So go and code it up, and show the end result. So far, nobody who actually
>> *does* CPU schedulers have really wanted to do it, because they all want
>> to muck around with their own private versions of the data structures.

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> What about PlugSched?

The extant versions of it fall well short of Linus' challenge as well
as my original goals for it. A useful exercise may also be enumerating
your expectations and having those who actually work with the code
describe how well those are actually met.


-- wli

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[William Lee Irwin III]

On Fri, Mar 09, 2007 at 05:18:31PM -0500, Ryan Hope wrote:
> from what I understood, there is a performance loss in plugsched
> schedulers because they have to share code....
> even if pluggable schedulers is not a viable option, being able to
> choose which one was built into the kernel would be easy (only takes a
> few ifdefs), i too think competition would be good

Neither sharing code nor data structures is strictly necessary for a
pluggable scheduler. For instance, backing out per-cpu runqueues in
favor of a single locklessly-accessed queue or similar per-leaf-domain
queues is one potential design alternative (never mind difficulties
with ->cpus_allowed) explicitly considered for the sake of sched_yield()
semantics on SMP, among other concerns. What plugsched originally did
was to provide a set of driver functions and allow each scheduler to
play with its private data declared static in separate C files in what
were later intended to become kernel modules. As far as I know, runtime
switchover code to complement all that has never been written in such a
form. One possibility abandoned early-on was to have multiple schedulers
simultaneously active to manage different portions of the system with
different policies, in no small part due to the difficulty of load
balancing between the partitions associated with the different schedulers.
Some misguided attempts were made to export the lowest-level API possible,
which I rather quickly deemed a mistake, but they still held to such
largely design considerations as I described above.


-- wli

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Al Boldi]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
> >> This sort of concern is too subjective for me to have an opinion on it.
>
> On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> > How diplomatic.
>
> Impoliteness doesn't accomplish anything I want to do.

Fair enough.  But being honest about it, without flaming, may be more 
constructive.

> William Lee Irwin III wrote:
> >> My preferred sphere of operation is the Manichean domain of faster vs.
> >> slower, functionality vs. non-functionality, and the like. For me, such
> >> design concerns are like the need for a kernel to format pagetables so
> >> the x86 MMU decodes what was intended, or for a compiler to emit valid
> >> assembly instructions, or for a programmer to write C the compiler
> >> won't reject with parse errors.
>
> On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> > Sure, but I think, even from a technical point of view, competition is a
> > good thing to have.  Pluggable schedulers give us this kind of
> > competition, that forces each scheduler to refine or become obsolete. 
> > Think evolution.
>
> I'm more of a cooperative than competitive person, not to say that
> flies well in Linux. There are more productive uses of time than having
> everyone NIH'ing everyone else's code. If the result isn't so great,
> I'd rather send them code or talk them about what needs to be done.

Ok, let's call it cooperative competitiveness.  You know, the kind of 
competitiveness that drives improvements that helps everybody

> Linus Torvalds wrote:
> >> And hey, you can try to prove me wrong. Code talks. So far, nobody has
> >> really ever come close.
> >> So go and code it up, and show the end result. So far, nobody who
> >> actually *does* CPU schedulers have really wanted to do it, because
> >> they all want to muck around with their own private versions of the
> >> data structures.
>
> On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
> > What about PlugSched?
>
> The extant versions of it fall well short of Linus' challenge as well
> as my original goals for it.

Do you mean Peter Williams' PlugSched-6.5-for-2.6.20?

> A useful exercise may also be enumerating
> your expectations and having those who actually work with the code
> describe how well those are actually met.

A runtime configurable framework that allows for dynamically extensible 
schedulers.  PlugSched seems to be a good start.


Thanks!

--
Al

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[William Lee Irwin III]

William Lee Irwin III wrote:
>>>> This sort of concern is too subjective for me to have an opinion on it.

On Fri, Mar 09, 2007 at 11:43:46PM +0300, Al Boldi wrote:
>>> How diplomatic.

William Lee Irwin III wrote:
>> Impoliteness doesn't accomplish anything I want to do.

On Sat, Mar 10, 2007 at 08:34:25AM +0300, Al Boldi wrote:
> Fair enough.  But being honest about it, without flaming, may be more 
> constructive.

There was no flamage. It is literally true.


William Lee Irwin III wrote:
>> I'm more of a cooperative than competitive person, not to say that
>> flies well in Linux. There are more productive uses of time than having
>> everyone NIH'ing everyone else's code. If the result isn't so great,
>> I'd rather send them code or talk them about what needs to be done.

On Sat, Mar 10, 2007 at 08:34:25AM +0300, Al Boldi wrote:
> Ok, let's call it cooperative competitiveness.  You know, the kind of 
> competitiveness that drives improvements that helps everybody

This trips over ideological issues best not discussed on lkml.


William Lee Irwin III wrote:
>> The extant versions of it fall well short of Linus' challenge as well
>> as my original goals for it.

On Sat, Mar 10, 2007 at 08:34:25AM +0300, Al Boldi wrote:
> Do you mean Peter Williams' PlugSched-6.5-for-2.6.20?

You'd be well-served by talking to Peter Williams sometime. He's a
knowledgable individual. I should also mention that Con Kolivas did
significant amounts of work to get the early codebase he inherited
from me working before things were handed off to Peter Williams.


William Lee Irwin III wrote:
>> A useful exercise may also be enumerating
>> your expectations and having those who actually work with the code
>> describe how well those are actually met.

On Sat, Mar 10, 2007 at 08:34:25AM +0300, Al Boldi wrote:
> A runtime configurable framework that allows for dynamically extensible 
> schedulers.  PlugSched seems to be a good start.

Last I checked there were limits to runtime configurability centering
around only supporting a compiled-in set of scheduling drivers, unless
Peter's taken it the rest of the way without my noticing. It's unclear
what you have in mind in terms of dynamic extensibility. My only guess
would be pluggable scheduling policy/class support for individual
schedulers in addition to plugging the individual schedulers, except
I'm rather certain that Williams' code doesn't do anything with modules.


-- wli

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Al Boldi]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
> >> A useful exercise may also be enumerating
> >> your expectations and having those who actually work with the code
> >> describe how well those are actually met.
>
> On Sat, Mar 10, 2007 at 08:34:25AM +0300, Al Boldi wrote:
> > A runtime configurable framework that allows for dynamically extensible
> > schedulers.  PlugSched seems to be a good start.
>
> Last I checked there were limits to runtime configurability centering
> around only supporting a compiled-in set of scheduling drivers, unless
> Peter's taken it the rest of the way without my noticing. It's unclear
> what you have in mind in terms of dynamic extensibility. My only guess
> would be pluggable scheduling policy/class support for individual
> schedulers in addition to plugging the individual schedulers, except
> I'm rather certain that Williams' code doesn't do anything with modules.

Correct, it doesn't, yet.  But do you think that PlugSched has the basic 
infrastructure in place to support this, or would it require a complete 
redesign/rewrite.


Thanks!

--
Al

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[William Lee Irwin III]

William Lee Irwin III wrote:
>> Last I checked there were limits to runtime configurability centering
>> around only supporting a compiled-in set of scheduling drivers, unless
>> Peter's taken it the rest of the way without my noticing. It's unclear
>> what you have in mind in terms of dynamic extensibility. My only guess
>> would be pluggable scheduling policy/class support for individual
>> schedulers in addition to plugging the individual schedulers, except
>> I'm rather certain that Williams' code doesn't do anything with modules.

On Sat, Mar 10, 2007 at 07:47:11PM +0300, Al Boldi wrote:
> Correct, it doesn't, yet.  But do you think that PlugSched has the basic 
> infrastructure in place to support this, or would it require a complete 
> redesign/rewrite.

The piece I got done was just representing schedulers as driver-like
affairs (which, embarrassingly enough, needed lots of bugfixing), and
everyone's just been running with that and boot-time switching ever
since. Runtime switching (to module-loaded schedulers or otherwise)
needs a lot of hotplug-esque work. Scheduler class support, pluggable
or otherwise, needs per-scheduler abstracting things out along the same
lines as what was originally done for the overall schedulers
surrounding enqueueing and dequeueing so the scheduler itself only
plucks tasks out of and stuffs tasks into some sort of abstracted-out
queue or set of queues, though I did try to break things down at a low
enough level where they'd be plausible for more than just the one
driver (never distributed) I used to test the design. I dumped the
entire project long before ever getting to where modules entered the
picture, and have never touched modules otherwise, so I'm not entirely
sure what other issues would come up with those after the smoke clears
from runtime switching.

I don't plan on doing anything here myself, since the boot-time
switching etc. is likely already considered offensive enough.

The next time something comes up that bears a risk of positioning me
against the kernel's political winds, I'll just rm it or not write it
at all instead of leaving code around (or worse yet, passing it around)
to be taken up by others. It just leaves a lot of embarrassed explaining
to do when it resurfaces years later, or otherwise leaves a rather bad
taste in my mouth when NIH'd years later like other things not mentioned
here (VM code kept quiet similarly to plugsched) and everyone approves
so long as it didn't come from me.


-- wli

Re: Pluggable Schedulers (was: [ANNOUNCE] RSDL completely fair starvation free interactive cpu scheduler)

[Bill Davidsen]

David Lang wrote:
> On Fri, 9 Mar 2007, Al Boldi wrote:
> 
>>
>>> My preferred sphere of operation is the Manichean domain of faster vs.
>>> slower, functionality vs. non-functionality, and the like. For me, such
>>> design concerns are like the need for a kernel to format pagetables so
>>> the x86 MMU decodes what was intended, or for a compiler to emit valid
>>> assembly instructions, or for a programmer to write C the compiler
>>> won't reject with parse errors.
>>
>> Sure, but I think, even from a technical point of view, competition is 
>> a good
>> thing to have.  Pluggable schedulers give us this kind of competition, 
>> that
>> forces each scheduler to refine or become obsolete.  Think evolution.
> 
> The point Linus is makeing is that with pluggable schedulers there isn't 
> competition between them, the various developer teams would go off in 
> their own direction and any drawbacks to their scheduler could be 
> answered with "that's not what we are good at, use a different 
> scheduler", with the very real possibility that a person could get this 
> answer from ALL schedulers, leaving them with nothing good to use.
> 
Have you noticed that currently that is exactly what happens? If the 
default scheduler doesn't handle your load well you have the option of 
rewriting it and maintaining it, or doing without, or tying to fix your 
case without breaking others, or patching in some other, non-mainline, 
scheduler.

The default scheduler has been around long enough that I don't see it 
being tuned for any A without making some B perform worse. Thus multiple 
schedulers are a possible solution.

They don't need to be available as runtime choices, boot time selection 
would still allow reasonable testing. I can see myself using a compile 
time option and building multiple kernels, but not the average user.

-- 
Bill Davidsen <davidsen@tmr.com>
   "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot