Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Al Boldi]

Peter Williams wrote:
>
> Probably the last one now that CFS is in the main line :-(.

What do you mean?  A pluggable scheduler framework is indispensible even in 
the presence of CFS or SD.

> A patch for 2.6.22 is available at:
>
> <http://downloads.sourceforge.net/cpuse/plugsched-6.5.1-for-2.6.22.patch>
>
> Very Brief Documentation:
>
> You can select a default scheduler at kernel build time.  If you wish to
> boot with a scheduler other than the default it can be selected at boot
> time by adding:
>
> cpusched=<scheduler>
>
> to the boot command line where <scheduler> is one of: ingosched,
> ingo_ll, nicksched, staircase, spa_no_frills, spa_ws, spa_svr, spa_ebs
> or zaphod.  If you don't change the default when you build the kernel
> the default scheduler will be ingosched (which is the normal scheduler).

Can't PlugSched include CFS and SD?


Thanks!

--
Al

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Giuseppe Bilotta]

On Thursday 12 July 2007 00:17, Al Boldi wrote:

> Peter Williams wrote:
>>
>> Probably the last one now that CFS is in the main line :-(.
> 
> What do you mean?  A pluggable scheduler framework is indispensible even in 
> the presence of CFS or SD.

Indeed, and I hope it gets merged, giving people the chance to test out
different schedulers easily, without having to do patching, de-patching,
re-patching and blah blah blah.

But somehow I doubt it'll get merged now. My bet is that it won't even be
taken into consideration, for the same reasons that ultimately drove Con
Kolivas to giving up on development of SD. And if it's so, chances are
people will get tired of trying to get it merged. :/

>> A patch for 2.6.22 is available at:
>>
>> <http://downloads.sourceforge.net/cpuse/plugsched-6.5.1-for-2.6.22.patch>
>>
>> Very Brief Documentation:
>>
>> You can select a default scheduler at kernel build time.  If you wish to
>> boot with a scheduler other than the default it can be selected at boot
>> time by adding:
>>
>> cpusched=<scheduler>
>>
>> to the boot command line where <scheduler> is one of: ingosched,
>> ingo_ll, nicksched, staircase, spa_no_frills, spa_ws, spa_svr, spa_ebs
>> or zaphod.  If you don't change the default when you build the kernel
>> the default scheduler will be ingosched (which is the normal scheduler).
> 
> Can't PlugSched include CFS and SD?

If I read the announcement correctly, those are the ones referred to as
'ingosched' and 'staircase' :)

-- 
Giuseppe "Oblomov" Bilotta

RE: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Li, Tong N]

> On Thursday 12 July 2007 00:17, Al Boldi wrote:
> 
> > Peter Williams wrote:
> >>
> >> Probably the last one now that CFS is in the main line :-(.
> >
> > What do you mean?  A pluggable scheduler framework is indispensible
even
> in
> > the presence of CFS or SD.
> 
> Indeed, and I hope it gets merged, giving people the chance to test
out
> different schedulers easily, without having to do patching,
de-patching,
> re-patching and blah blah blah.
> 

Yes, such a framework would be invaluable, especially given that
scheduling often has conflicting goals and different workloads have
different requirements. No single solution fits all.

> But somehow I doubt it'll get merged now. My bet is that it won't even
be
> taken into consideration, for the same reasons that ultimately drove
Con
> Kolivas to giving up on development of SD. And if it's so, chances are
> people will get tired of trying to get it merged. :/
> 
> >> A patch for 2.6.22 is available at:
> >>
> >> <http://downloads.sourceforge.net/cpuse/plugsched-6.5.1-for-
> 2.6.22.patch>
> >>
> >> Very Brief Documentation:
> >>
> >> You can select a default scheduler at kernel build time.  If you
wish
> to
> >> boot with a scheduler other than the default it can be selected at
boot
> >> time by adding:
> >>
> >> cpusched=<scheduler>
> >>
> >> to the boot command line where <scheduler> is one of: ingosched,
> >> ingo_ll, nicksched, staircase, spa_no_frills, spa_ws, spa_svr,
spa_ebs
> >> or zaphod.  If you don't change the default when you build the
kernel
> >> the default scheduler will be ingosched (which is the normal
scheduler).
> >
> > Can't PlugSched include CFS and SD?
> 
> If I read the announcement correctly, those are the ones referred to
as
> 'ingosched' and 'staircase' :)
> 
> --
> Giuseppe "Oblomov" Bilotta
> 
> -
> 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: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Adrian Bunk]

On Sun, Jul 15, 2007 at 10:47:51AM -0700, Li, Tong N wrote:
> > On Thursday 12 July 2007 00:17, Al Boldi wrote:
> > 
> > > Peter Williams wrote:
> > >>
> > >> Probably the last one now that CFS is in the main line :-(.
> > >
> > > What do you mean?  A pluggable scheduler framework is indispensible
> even
> > in
> > > the presence of CFS or SD.
> > 
> > Indeed, and I hope it gets merged, giving people the chance to test
> out
> > different schedulers easily, without having to do patching,
> de-patching,
> > re-patching and blah blah blah.
> > 
> 
> Yes, such a framework would be invaluable, especially given that
> scheduling often has conflicting goals and different workloads have
> different requirements. No single solution fits all.
>...

Having a framework for giving people the choice between different 
solutions usually sounds good in theory, but in practice there's the 
often underestimated high price of people using a different solution 
instead of reporting a problem with one solution or people adding 
features to only one of the solutions resulting in different solutions 
having different features and bugs instead of one solution with all 
features and bug fixes.

So you should give a good technical explanation why it's not technically 
possible or not desirable for one solution to work well for everyone.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

RE: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Li, Tong N]

> -----Original Message-----
> From: Adrian Bunk [mailto:bunk@stusta.de]
> Sent: Sunday, July 15, 2007 4:46 PM
> To: Li, Tong N
> Cc: Giuseppe Bilotta; linux-kernel@vger.kernel.org
> Subject: Re: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22
> 
> On Sun, Jul 15, 2007 at 10:47:51AM -0700, Li, Tong N wrote:
> > > On Thursday 12 July 2007 00:17, Al Boldi wrote:
> > >
> > > > Peter Williams wrote:
> > > >>
> > > >> Probably the last one now that CFS is in the main line :-(.
> > > >
> > > > What do you mean?  A pluggable scheduler framework is
indispensible
> > even
> > > in
> > > > the presence of CFS or SD.
> > >
> > > Indeed, and I hope it gets merged, giving people the chance to
test
> > out
> > > different schedulers easily, without having to do patching,
> > de-patching,
> > > re-patching and blah blah blah.
> > >
> >
> > Yes, such a framework would be invaluable, especially given that
> > scheduling often has conflicting goals and different workloads have
> > different requirements. No single solution fits all.
> >...
> 
> Having a framework for giving people the choice between different
> solutions usually sounds good in theory, but in practice there's the
> often underestimated high price of people using a different solution
> instead of reporting a problem with one solution or people adding
> features to only one of the solutions resulting in different solutions
> having different features and bugs instead of one solution with all
> features and bug fixes.
> 
> So you should give a good technical explanation why it's not
technically
> possible or not desirable for one solution to work well for everyone.

There are various metrics a scheduler may want to optimize for, such as
throughput, response time, power consumption, fairness, and so on. Each
of these may also be defined differently in different environments. Take
fairness as an example. People have traditionally talked about it in
terms of CPU time. Now it'd also make sense to talk about scheduling
that enables fair usage of other types of resources, such as shared
caches. Different metrics may require different scheduling policies.
Plus, many metrics may in fact conflict, e.g., a scheduling policy
optimized for throughput may not be power efficient. As a result, Linux,
and all general-purpose OSes, strive to achieve a balance, but it's
conceivable that different hardware platforms and different application
workloads may want to have different scheduling policies to meet their
own needs.

Given that the scheduling policies can be diverse, the mechanisms to
enforce them can also be different. The per-cpu runqueue model may be
best for many scenarios, some scheduling policies (like many real-time
ones) might want global knowledge about all tasks in the system and thus
prefer a global task queue at the cost of being less scalable and
cache-efficient. HPC systems may also want to gang-schedule. And, in
terms of implementation, O(1) might be desirable for large-scale MP
systems while O(log N) might be good enough for small systems. These are
just examples that indicate the scheduler data structures, algorithms,
and implementation can have a variety of possibilities in different
usage models. A single scheduler that is easily extensible for
incorporating different policies would be ideal, but IMO this is not yet
the case and may not even be possible. Therefore, I think having a
framework that enables multiple schedulers to co-exist would be
invaluable and PlugSched seems to be one good step towards this.

  tong

Re: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Adrian Bunk]

On Sun, Jul 15, 2007 at 10:03:02PM -0700, Li, Tong N wrote:
> 
> There are various metrics a scheduler may want to optimize for, such as
> throughput, response time, power consumption, fairness, and so on. Each
> of these may also be defined differently in different environments. Take
> fairness as an example. People have traditionally talked about it in
> terms of CPU time. Now it'd also make sense to talk about scheduling
> that enables fair usage of other types of resources, such as shared
> caches. Different metrics may require different scheduling policies.

Are these real-life problems people need solutions for today or just 
thoughts someone might want to try and write a paper about?

> Plus, many metrics may in fact conflict, e.g., a scheduling policy
> optimized for throughput may not be power efficient. As a result, Linux,
> and all general-purpose OSes, strive to achieve a balance, but it's
> conceivable that different hardware platforms and different application
> workloads may want to have different scheduling policies to meet their
> own needs.

The Linux scheduler already gives you some knobs allowing you to adjust 
the scheduling to your needs.

What is missing, and why wasn't it included in the current scheduler?

> Given that the scheduling policies can be diverse, the mechanisms to
> enforce them can also be different. The per-cpu runqueue model may be
> best for many scenarios, some scheduling policies (like many real-time
> ones) might want global knowledge about all tasks in the system and thus
> prefer a global task queue at the cost of being less scalable and
> cache-efficient. HPC systems may also want to gang-schedule. And, in
> terms of implementation, O(1) might be desirable for large-scale MP
> systems while O(log N) might be good enough for small systems. These are
> just examples that indicate the scheduler data structures, algorithms,
> and implementation can have a variety of possibilities in different
> usage models. A single scheduler that is easily extensible for
> incorporating different policies would be ideal, but IMO this is not yet
> the case and may not even be possible. Therefore, I think having a
> framework that enables multiple schedulers to co-exist would be
> invaluable and PlugSched seems to be one good step towards this.

Much is already possible, and e.g. when you talk about HPC you are in an 
area where the scope of the kernel is anyway often too small and the 
actual scheduling is done with a userspace batch scheduling program.

What are the real-life problems the current scheduler has, and why 
weren't they solved when it was designed and implemented?

People implementing a special purpose scheduler to fit their needs would
really not be an ideal solution - ideally, there should be one scheduler 
that handles all real-life problems.

And therefore the first step for people should be to try to get their 
problems solved with the one scheduler, and if required enhance it, 
instead of saying NIH and implement their own special purpose scheduler.

>   tong

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Siddha, Suresh B]

On Mon, Jul 16, 2007 at 08:56:10AM +0200, Adrian Bunk wrote:
> On Sun, Jul 15, 2007 at 10:03:02PM -0700, Li, Tong N wrote:
> > 
> > There are various metrics a scheduler may want to optimize for, such as
> > throughput, response time, power consumption, fairness, and so on. Each
> > of these may also be defined differently in different environments. Take
> > fairness as an example. People have traditionally talked about it in
> > terms of CPU time. Now it'd also make sense to talk about scheduling
> > that enables fair usage of other types of resources, such as shared
> > caches. Different metrics may require different scheduling policies.
> 
> Are these real-life problems people need solutions for today or just 
> thoughts someone might want to try and write a paper about?

We are at the door step of multi core evolution. So its a bit of both.

thanks,
suresh

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 791 bytes --]

On Thu, 16 Aug 2007 22:42:42 +0200, devzero@web.de said:

> i trust you kernel developers know what you are doing, but if scares me
> a little bit, that some integral and living part like O(1) being ripped off 
> and being replaced by something new. 

There's something even scarier - O(1) being taken out and replaced by multiple
new things, none of which ever gets fully tested because if one misbehaves,
the user says "so what" and tries another one without bothering to file a bug
report...

Been there, done that - I found a timing hole in the pluggable I/O schedulers
that probably nobody had managed to hit because there were 3 or 4 choices
available, and they just set a default they liked.  Turned out there was a
race condition if I/O happened while schedulers were being swapped.

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Ingo Molnar]

* Peter Williams <pwil3058@bigpond.net.au> wrote:

> Ingo Molnar wrote:
> > * Peter Williams <pwil3058@bigpond.net.au> wrote:
> > 
> >> Probably the last one now that CFS is in the main line :-(.
> > 
> > hm, why is CFS in mainline a problem?
> 
> It means a major rewrite of the plugsched interface and I'm not sure 
> that it's worth it (if CFS works well).  However, note that I did say 
> probably not definitely :-).  I'll play with it and see what happens.

i think it's very useful as a constant reality check. Yes, i did 
periodically boot your Zaphod scheduler too on a testbox ;-)
"CFS works well" cannot be determined reliably if there's nothing to
compare it against. One goal behind the CFS changes was to remove the
need for massive scheduler rewrites and to ease prototyping. Somehow
there are lots of people who really love to hack the scheduler,
those weirdos ;-)

> > The CFS merge should make the life of development/test patches like 
> > plugsched conceptually easier. (it will certainly cause a lot of 
> > churn, but that's for the better i think.)
> 
> I don't think that is necessarily the case.

well, kernel/sched_rt.c and kernel/sched_fair.c are already more 
different on a conceptual angle than any of the two schedulers in 
PlugSched i think. But ... i dont expect the initial port of PlugSched 
to be easy at all.

> > Most of the schedulers in plugsched should be readily adaptable to 
> > the modular scheduling-policy scheme of the upstream scheduler.
> 
> I don't think that this necessarily true.  Ingosched and ingo_ll are 
> definitely out and I don't feel like converting staircase and 
> nicksched as I have no real interest in them.  Perhaps I'll just 
> create the interface and some schedulers based on my own ideas and let 
> others such as Con and Nick add schedulers if they're still that way 
> inclined.

Yeah, i think starting with a smaller subset is the right approach - i 
think people _will_ fill the gaps ;-) I agree that preserving 
"Ingosched" would not make much sense. (Although it could still be 
useful to someone who finds some regression and suspects CFS, and wants 
to try with the old scheduler. Or just to test/prove that the 
modularization is strong enough to even include those scheduler 
heuristics the old scheduler did. Or out of historic interest.)

> > I'm sure there will be some minor issues as isolation of the modules 
> > is not enforced right now - and i'd be happy to review (and 
> > potentially apply) common-sense patches that improve the framework.
> 
> Thanks for the offer of support (it may sway my decision),

you are welcome :) Dmitry Adamushko and Srivatsa Vaddagiri already did 
lots of nice "policy module isolation" work in CFS (since the first 
crude cut i did in CFS v1), both for the cleanup factor and to enable 
features like group-scheduling.

	Ingo

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Peter Williams]

Ingo Molnar wrote:
> * Peter Williams <pwil3058@bigpond.net.au> wrote:
> 
>> Probably the last one now that CFS is in the main line :-(.
> 
> hm, why is CFS in mainline a problem?

It means a major rewrite of the plugsched interface and I'm not sure
that it's worth it (if CFS works well).  However, note that I did say
probably not definitely :-).  I'll play with it and see what happens.

> The CFS merge should make the life 
> of development/test patches like plugsched conceptually easier. (it will 
> certainly cause a lot of churn, but that's for the better i think.)

I don't think that is necessarily the case.

> 
> Most of the schedulers in plugsched should be readily adaptable to the 
> modular scheduling-policy scheme of the upstream scheduler.

I don't think that this necessarily true.  Ingosched and ingo_ll are
definitely out and I don't feel like converting staircase and nicksched
as I have no real interest in them.  Perhaps I'll just create the
interface and some schedulers based on my own ideas and let others such
as Con and Nick add schedulers if they're still that way inclined.

> I'm sure 
> there will be some minor issues as isolation of the modules is not 
> enforced right now - and i'd be happy to review (and potentially apply) 
> common-sense patches that improve the framework.

Thanks for the offer of support (it may sway my decision),
Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce

Re: [ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Ingo Molnar]

* Peter Williams <pwil3058@bigpond.net.au> wrote:

> Probably the last one now that CFS is in the main line :-(.

hm, why is CFS in mainline a problem? The CFS merge should make the life 
of development/test patches like plugsched conceptually easier. (it will 
certainly cause a lot of churn, but that's for the better i think.)

Most of the schedulers in plugsched should be readily adaptable to the 
modular scheduling-policy scheme of the upstream scheduler. I'm sure 
there will be some minor issues as isolation of the modules is not 
enforced right now - and i'd be happy to review (and potentially apply) 
common-sense patches that improve the framework.

	Ingo

[ANNOUNCE][RFC] PlugSched-6.5.1 for 2.6.22

[Peter Williams]

Probably the last one now that CFS is in the main line :-(.

A patch for 2.6.22 is available at:

<http://downloads.sourceforge.net/cpuse/plugsched-6.5.1-for-2.6.22.patch>

Very Brief Documentation:

You can select a default scheduler at kernel build time.  If you wish to
boot with a scheduler other than the default it can be selected at boot
time by adding:

cpusched=<scheduler>

to the boot command line where <scheduler> is one of: ingosched,
ingo_ll, nicksched, staircase, spa_no_frills, spa_ws, spa_svr, spa_ebs
or zaphod.  If you don't change the default when you build the kernel
the default scheduler will be ingosched (which is the normal scheduler).

The scheduler in force on a running system can be determined by the
contents of:

/proc/scheduler

Control parameters for the scheduler can be read/set via files in:

/sys/cpusched/<scheduler>/

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce