Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Ph. Marek]

Pine.LNX.4.64.0704181515290.25880 () alien ! or ! mcafeemobile ! com

Davide Libenzi wrote:
> On Wed, 18 Apr 2007, Ingo Molnar wrote:
> > That's one reason why i dont think it's necessarily a good idea to
> > group-schedule threads, we dont really want to do a per thread group
> > percpu_alloc().
>
> I still do not have clear how much overhead this will bring into the
> table, but I think (like Linus was pointing out) the hierarchy should look
> like:
...
> The "run_queue" concept (and data) that now is bound to a CPU, need to be
> replicated in:
>
> ROOT <- VCPUs add themselves here
>     VCPU <- USERs add themselves here
>         USER <- PROCs add themselves here
>             PROC <- THREADs add themselves here
>                 THREAD (ultimate fine grained scheduling unit)
>
> So ROOT, VCPU, USER and PROC will have their own "run_queue". 
...

I can't comment on the internals about run_queues, overhead and so on, but 
these discussion leads me to the idea about a dynamic *tree* of scheduler 
queues.

With dynamic I mean that they are configured in user-space - be it with 
something like CLONE_NEW_SCHEDULER_CLASS, or possibly better some other 
interface to allow an *arbitrary* tree that is not coupled on the 
user/process/thread borders. New threads and processes are per default 
created in the parents queue, just like now.

So user-space could build an tree like this (eg with a pam module):

 Default queue - init
   +- kernel-thread queue (to avoid having kernel threads being blocked by
   |               user-space)
   +- cron, atd, sshd, .... unless they change their "class"
   +- user1
   |  +- X
   |  +- kde
   |  |  + konsole
   |  |  \ kmail
   |  |    + mail fetch thread
   |  |    + mail filter thread
   |  |    + GUI thread
   |  |  \- mplayer 
   \- user2
      +.....

Whether the queues are handled with some staircase behaviour, or CFS, or just 
get CPU time distributed by nice level, is another question - but they have 
to be "fair" only locally.

Of course, that's simply some sort of moving the problem into user-space - but 
I think (and read that often enough) that the needs vary so much that a 
single, hardcoded system won't suffice. And we can try to get the "right" 
behaviour in each queue, just like now.

Walking the tree might make the scheduler not fully O(1) - but per default 
only one queue is defined (or possibly two queues, one for kernel threads), 
and everything else can be done by user-space.


The mentioned case of a web-server with gzip started would be done with having 
each httpd being in a queue just below init, and having everything else in 
another - or by nicing the webserver, as it's defined as "important".
(I believe that's called "moving policy into userspace" :-)


Regards,

Phil

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

William Lee Irwin III wrote:
> On Fri, Apr 13, 2007 at 10:21:00PM +0200, Ingo Molnar wrote:
> > [announce] [patch] Modular Scheduler Core and Completely Fair Scheduler
> > [CFS] i'm pleased to announce the first release of the "Modular
> > Scheduler Core and Completely Fair Scheduler [CFS]" patchset:
> >    http://redhat.com/~mingo/cfs-scheduler/sched-modular+cfs.patch
> > This project is a complete rewrite of the Linux task scheduler. My goal
> > is to address various feature requests and to fix deficiencies in the
> > vanilla scheduler that were suggested/found in the past few years, both
> > for desktop scheduling and for server scheduling workloads.
> > [ QuickStart: apply the patch to v2.6.21-rc6, recompile, reboot. The
> >   new scheduler will be active by default and all tasks will default
> >   to the new SCHED_FAIR interactive scheduling class. ]
>
> A pleasant surprise, though I did see it coming.

Same here, but I didn't expect it so soon.  Thanks!

> >    The CFS patch uses a completely different approach and implementation
> >    from RSDL/SD. My goal was to make CFS's interactivity quality exceed
> >    that of RSDL/SD, which is a high standard to meet :-) Testing
> >    feedback is welcome to decide this one way or another.

I slammed this patch on 2.6.20.6 with some ugly rejects but it did compile, 
then tested, so my results may be affected by the rejects.

Boot into /bin/sh.
Run chew.c on three different VT's with different nice each.  Observe.

Console 1:
pid 615, prio  19, out for   19 ms, ran for    0 ms, load   4%
pid 615, prio  19, out for   19 ms, ran for    0 ms, load   4%
pid 615, prio  19, out for   19 ms, ran for    0 ms, load   4%
pid 615, prio  19, out for   19 ms, ran for    0 ms, load   4%
pid 615, prio  19, out for   77 ms, ran for    0 ms, load   1%
pid 615, prio  19, out for  125 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for  209 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for  346 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for  552 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for  882 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1231 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1335 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1218 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1254 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1774 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1946 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 1942 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 2749 ms, ran for    0 ms, load   0%
pid 615, prio  19, out for 3217 ms, ran for    0 ms, load   0%

Console 2:
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    9 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    9 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    9 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    7 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    8 ms, ran for    2 ms, load  26%
pid 616, prio   0, out for    9 ms, ran for    2 ms, load  24%
pid 616, prio   0, out for    5 ms, ran for    2 ms, load  26%

Console 3:
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    8 ms, load  74%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%
pid 617, prio -10, out for    3 ms, ran for    7 ms, load  72%

It looks like negative nice affects positive nice adversely.

> >    CFS's design is quite radical: it does not use runqueues, it uses a
> >    time-ordered rbtree to build a 'timeline' of future task execution,
> >    and thus has no 'array switch' artifacts (by which both the vanilla
> >    scheduler and RSDL/SD are affected).

Sounds interresting, but it looks like CPU-bound procs easily steal sleeping 
proc timeslices, thus making it rather unfair, affecting interactivity.

The latencies look great, though.

Also, it may be useful to lower-bound timeslices, as they become ridiculously 
small ( < 1ms ).


Thanks!

--
Al

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

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

Peter Williams wrote:
> William Lee Irwin III wrote:
> > On Mon, Apr 16, 2007 at 11:06:56AM +1000, Peter Williams wrote:
> >> PS I no longer read LKML (due to time constraints) and would appreciate
> >> it if I could be CC'd on any e-mails suggesting scheduler changes.
> >> PPS I'm just happy to see that Ingo has finally accepted that the
> >> vanilla scheduler was badly in need of fixing and don't really care who
> >> fixes it.
> >> PPS Different schedulers for different aims (i.e. server or work
> >> station) do make a difference.  E.g. the spa_svr scheduler in plugsched
> >> does about 1% better on kernbench than the next best scheduler in the
> >> bunch. PPPS Con, fairness isn't always best as humans aren't very
> >> altruistic and we need to give unfair preference to interactive tasks
> >> in order to stop the users flinging their PCs out the window.  But the
> >> current scheduler doesn't do this very well and is also not very good
> >> at fairness so needs to change.  But the changes need to address
> >> interactive response and fairness not just fairness.
> >
> > Kernel compiles not so useful a benchmark. SDET, OAST, AIM7, etc. are
> > better ones. I'd not bother citing kernel compile results.
>
> spa_svr actually does its best work when the system isn't fully loaded
> as the type of improvement it strives to achieve (minimizing on queue
> wait time) hasn't got much room to manoeuvre when the system is fully
> loaded.  Therefore, the fact that it's 1% better even in these
> circumstances is a good result and also indicates that the overhead for
> keeping the scheduling statistics it uses for its decision making is
> well spent.  Especially, when you consider that the total available room
> for improvement on this benchmark is less than 3%.
>
> To elaborate, the motivation for this scheduler was acquired from the
> observation of scheduling statistics (in particular, on queue wait time)
> on systems running at about 30% to 50% load.  Theoretically, at these
> load levels there should be no such waiting but the statistics show that
> there is considerable waiting (sometimes as high as 30% to 50%).  I put
> this down to "lack of serendipity" e.g.  everyone sleeping at the same
> time and then trying to run at the same time would be complete lack of
> serendipity.  On the other hand, if everyone is synced then there would
> be total serendipity.
>
> Obviously, from the POV of a client, time the server task spends waiting
> on the queue adds to the response time for any request that has been
> made so reduction of this time on a server is a good thing(tm).  Equally
> obviously, trying to achieve this synchronization by asking the tasks to
> cooperate with each other is not a feasible solution and some external
> influence needs to be exerted and this is what spa_svr does -- it nudges
> the scheduling order of the tasks in a way that makes them become well
> synced.
>
> Unfortunately, this is not a good scheduler for an interactive system as
> it minimizes the response times for ALL tasks (and the system as a
> whole) and this can result in increased response time for some
> interactive tasks (clunkiness) which annoys interactive users.  When you
> start fiddling with this scheduler to bring back "interactive
> unfairness" you kill a lot of its superior low overall wait time
> performance.

spa_svr is my favorite, but as you mentioned doesn't work well with ia.  So I 
started instrumenting its behaviour with chew.c (attached).  What I found is 
that prio-levels are way to coarse.  Setting max_tpt_bonus = 3 bounds this 
somewhat, but it was still not enough.  Looking at spa_svr_reassess_bonus 
and changing it to simply adjust prio based on avg_sleep did the trick like 
this:

static void spa_svr_reassess_bonus(struct task_struct *p)
{
	if (p->sdu.spa.avg_sleep_per_cycle >> 10) {
		incr_throughput_bonus(p, 1);
	} else
		decr_throughput_bonus(p);
}


Thanks!

--
Al

[-- Attachment #2: chew.c --]
[-- Type: text/x-csrc, Size: 1136 bytes --]

/*
 * original idea by Chris Friesen.  Thanks.
 */

#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

#define THRESHOLD_USEC 2000

unsigned long long stamp()
{
        struct timeval tv;
        gettimeofday(&tv, 0);
        return (unsigned long long) tv.tv_usec + ((unsigned long long) tv.tv_sec)*1000000;
}


int main()
{
        unsigned long long thresh_ticks = THRESHOLD_USEC;
        unsigned long long cur, last, start, act, delta;
        struct timespec ts;

        sched_rr_get_interval(0, &ts);
        printf("pid %d, prio %3d, interval of %d nsec\n", getpid(), getpriority(PRIO_PROCESS, 0), ts.tv_nsec);

        start = last = stamp();
        while(1) {
                cur = stamp();
                delta = cur-last;
                if (delta > thresh_ticks) {
			act = last - start;
                        printf("pid %d, prio %3d, out for %4llu ms, ran for %4llu ms, load %3llu%\n"
			, getpid(), getpriority(PRIO_PROCESS, 0), delta/1000, act/1000,(act*100)/(cur-start));
                        start = cur = stamp();
                }
                last = cur;
        }

        return 0;
}

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Peter Williams]

Al Boldi wrote:
> Peter Williams wrote:
>> William Lee Irwin III wrote:
>>> On Mon, Apr 16, 2007 at 11:06:56AM +1000, Peter Williams wrote:
>>>> PS I no longer read LKML (due to time constraints) and would appreciate
>>>> it if I could be CC'd on any e-mails suggesting scheduler changes.
>>>> PPS I'm just happy to see that Ingo has finally accepted that the
>>>> vanilla scheduler was badly in need of fixing and don't really care who
>>>> fixes it.
>>>> PPS Different schedulers for different aims (i.e. server or work
>>>> station) do make a difference.  E.g. the spa_svr scheduler in plugsched
>>>> does about 1% better on kernbench than the next best scheduler in the
>>>> bunch. PPPS Con, fairness isn't always best as humans aren't very
>>>> altruistic and we need to give unfair preference to interactive tasks
>>>> in order to stop the users flinging their PCs out the window.  But the
>>>> current scheduler doesn't do this very well and is also not very good
>>>> at fairness so needs to change.  But the changes need to address
>>>> interactive response and fairness not just fairness.
>>> Kernel compiles not so useful a benchmark. SDET, OAST, AIM7, etc. are
>>> better ones. I'd not bother citing kernel compile results.
>> spa_svr actually does its best work when the system isn't fully loaded
>> as the type of improvement it strives to achieve (minimizing on queue
>> wait time) hasn't got much room to manoeuvre when the system is fully
>> loaded.  Therefore, the fact that it's 1% better even in these
>> circumstances is a good result and also indicates that the overhead for
>> keeping the scheduling statistics it uses for its decision making is
>> well spent.  Especially, when you consider that the total available room
>> for improvement on this benchmark is less than 3%.
>>
>> To elaborate, the motivation for this scheduler was acquired from the
>> observation of scheduling statistics (in particular, on queue wait time)
>> on systems running at about 30% to 50% load.  Theoretically, at these
>> load levels there should be no such waiting but the statistics show that
>> there is considerable waiting (sometimes as high as 30% to 50%).  I put
>> this down to "lack of serendipity" e.g.  everyone sleeping at the same
>> time and then trying to run at the same time would be complete lack of
>> serendipity.  On the other hand, if everyone is synced then there would
>> be total serendipity.
>>
>> Obviously, from the POV of a client, time the server task spends waiting
>> on the queue adds to the response time for any request that has been
>> made so reduction of this time on a server is a good thing(tm).  Equally
>> obviously, trying to achieve this synchronization by asking the tasks to
>> cooperate with each other is not a feasible solution and some external
>> influence needs to be exerted and this is what spa_svr does -- it nudges
>> the scheduling order of the tasks in a way that makes them become well
>> synced.
>>
>> Unfortunately, this is not a good scheduler for an interactive system as
>> it minimizes the response times for ALL tasks (and the system as a
>> whole) and this can result in increased response time for some
>> interactive tasks (clunkiness) which annoys interactive users.  When you
>> start fiddling with this scheduler to bring back "interactive
>> unfairness" you kill a lot of its superior low overall wait time
>> performance.
> 
> spa_svr is my favorite, but as you mentioned doesn't work well with ia.  So I 
> started instrumenting its behaviour with chew.c (attached).  What I found is 
> that prio-levels are way to coarse.  Setting max_tpt_bonus = 3 bounds this 
> somewhat, but it was still not enough.  Looking at spa_svr_reassess_bonus 
> and changing it to simply adjust prio based on avg_sleep did the trick like 
> this:
> 
> static void spa_svr_reassess_bonus(struct task_struct *p)
> {
> 	if (p->sdu.spa.avg_sleep_per_cycle >> 10) {
> 		incr_throughput_bonus(p, 1);
> 	} else
> 		decr_throughput_bonus(p);
> }
> 

I suspect that this would kill some of the good server performance as it 
removes the mechanism that minimises wait time.  It is effectively just 
a simplification of what the vanilla O(1) scheduler tries to do i.e. 
assume tasks that sleep a lot are interactive and give them a boost.

spa_ws tries to do this as well only in a bit more complicated fashion. 
  So maybe an spa_svr modified in this way and renamed could make a good 
interactive scheduler.

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

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

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

Peter Williams wrote:
> Al Boldi wrote:
> > Peter Williams wrote:
> >> William Lee Irwin III wrote:
> >>> On Mon, Apr 16, 2007 at 11:06:56AM +1000, Peter Williams wrote:
> >>>> PS I no longer read LKML (due to time constraints) and would
> >>>> appreciate it if I could be CC'd on any e-mails suggesting scheduler
> >>>> changes. PPS I'm just happy to see that Ingo has finally accepted
> >>>> that the vanilla scheduler was badly in need of fixing and don't
> >>>> really care who fixes it.
> >>>> PPS Different schedulers for different aims (i.e. server or work
> >>>> station) do make a difference.  E.g. the spa_svr scheduler in
> >>>> plugsched does about 1% better on kernbench than the next best
> >>>> scheduler in the bunch. PPPS Con, fairness isn't always best as
> >>>> humans aren't very altruistic and we need to give unfair preference
> >>>> to interactive tasks in order to stop the users flinging their PCs
> >>>> out the window.  But the current scheduler doesn't do this very well
> >>>> and is also not very good at fairness so needs to change.  But the
> >>>> changes need to address interactive response and fairness not just
> >>>> fairness.
> >>>
> >>> Kernel compiles not so useful a benchmark. SDET, OAST, AIM7, etc. are
> >>> better ones. I'd not bother citing kernel compile results.
> >>
> >> spa_svr actually does its best work when the system isn't fully loaded
> >> as the type of improvement it strives to achieve (minimizing on queue
> >> wait time) hasn't got much room to manoeuvre when the system is fully
> >> loaded.  Therefore, the fact that it's 1% better even in these
> >> circumstances is a good result and also indicates that the overhead for
> >> keeping the scheduling statistics it uses for its decision making is
> >> well spent.  Especially, when you consider that the total available
> >> room for improvement on this benchmark is less than 3%.
> >>
> >> To elaborate, the motivation for this scheduler was acquired from the
> >> observation of scheduling statistics (in particular, on queue wait
> >> time) on systems running at about 30% to 50% load.  Theoretically, at
> >> these load levels there should be no such waiting but the statistics
> >> show that there is considerable waiting (sometimes as high as 30% to
> >> 50%).  I put this down to "lack of serendipity" e.g.  everyone sleeping
> >> at the same time and then trying to run at the same time would be
> >> complete lack of serendipity.  On the other hand, if everyone is synced
> >> then there would be total serendipity.
> >>
> >> Obviously, from the POV of a client, time the server task spends
> >> waiting on the queue adds to the response time for any request that has
> >> been made so reduction of this time on a server is a good thing(tm). 
> >> Equally obviously, trying to achieve this synchronization by asking the
> >> tasks to cooperate with each other is not a feasible solution and some
> >> external influence needs to be exerted and this is what spa_svr does --
> >> it nudges the scheduling order of the tasks in a way that makes them
> >> become well synced.
> >>
> >> Unfortunately, this is not a good scheduler for an interactive system
> >> as it minimizes the response times for ALL tasks (and the system as a
> >> whole) and this can result in increased response time for some
> >> interactive tasks (clunkiness) which annoys interactive users.  When
> >> you start fiddling with this scheduler to bring back "interactive
> >> unfairness" you kill a lot of its superior low overall wait time
> >> performance.
> >
> > spa_svr is my favorite, but as you mentioned doesn't work well with ia. 
> > So I started instrumenting its behaviour with chew.c (attached).  What I
> > found is that prio-levels are way to coarse.  Setting max_tpt_bonus = 3
> > bounds this somewhat, but it was still not enough.  Looking at
> > spa_svr_reassess_bonus and changing it to simply adjust prio based on
> > avg_sleep did the trick like this:
> >
> > static void spa_svr_reassess_bonus(struct task_struct *p)
> > {
> > 	if (p->sdu.spa.avg_sleep_per_cycle >> 10) {
> > 		incr_throughput_bonus(p, 1);
> > 	} else
> > 		decr_throughput_bonus(p);
> > }
>
> I suspect that this would kill some of the good server performance as it
> removes the mechanism that minimises wait time.  It is effectively just
> a simplification of what the vanilla O(1) scheduler tries to do i.e.
> assume tasks that sleep a lot are interactive and give them a boost.
>
> spa_ws tries to do this as well only in a bit more complicated fashion.
>   So maybe an spa_svr modified in this way and renamed could make a good
> interactive scheduler.

Great!

Reducing the prio-level granularity may also be helpful; or maybe even make 
it adjustable?  Any easy way to introduce something like this?


Thanks!

--
Al

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Peter Williams]

Al Boldi wrote:
> Peter Williams wrote:
>> Al Boldi wrote:
>>> Peter Williams wrote:
>>>> William Lee Irwin III wrote:
>>>>> On Mon, Apr 16, 2007 at 11:06:56AM +1000, Peter Williams wrote:
>>>>>> PS I no longer read LKML (due to time constraints) and would
>>>>>> appreciate it if I could be CC'd on any e-mails suggesting scheduler
>>>>>> changes. PPS I'm just happy to see that Ingo has finally accepted
>>>>>> that the vanilla scheduler was badly in need of fixing and don't
>>>>>> really care who fixes it.
>>>>>> PPS Different schedulers for different aims (i.e. server or work
>>>>>> station) do make a difference.  E.g. the spa_svr scheduler in
>>>>>> plugsched does about 1% better on kernbench than the next best
>>>>>> scheduler in the bunch. PPPS Con, fairness isn't always best as
>>>>>> humans aren't very altruistic and we need to give unfair preference
>>>>>> to interactive tasks in order to stop the users flinging their PCs
>>>>>> out the window.  But the current scheduler doesn't do this very well
>>>>>> and is also not very good at fairness so needs to change.  But the
>>>>>> changes need to address interactive response and fairness not just
>>>>>> fairness.
>>>>> Kernel compiles not so useful a benchmark. SDET, OAST, AIM7, etc. are
>>>>> better ones. I'd not bother citing kernel compile results.
>>>> spa_svr actually does its best work when the system isn't fully loaded
>>>> as the type of improvement it strives to achieve (minimizing on queue
>>>> wait time) hasn't got much room to manoeuvre when the system is fully
>>>> loaded.  Therefore, the fact that it's 1% better even in these
>>>> circumstances is a good result and also indicates that the overhead for
>>>> keeping the scheduling statistics it uses for its decision making is
>>>> well spent.  Especially, when you consider that the total available
>>>> room for improvement on this benchmark is less than 3%.
>>>>
>>>> To elaborate, the motivation for this scheduler was acquired from the
>>>> observation of scheduling statistics (in particular, on queue wait
>>>> time) on systems running at about 30% to 50% load.  Theoretically, at
>>>> these load levels there should be no such waiting but the statistics
>>>> show that there is considerable waiting (sometimes as high as 30% to
>>>> 50%).  I put this down to "lack of serendipity" e.g.  everyone sleeping
>>>> at the same time and then trying to run at the same time would be
>>>> complete lack of serendipity.  On the other hand, if everyone is synced
>>>> then there would be total serendipity.
>>>>
>>>> Obviously, from the POV of a client, time the server task spends
>>>> waiting on the queue adds to the response time for any request that has
>>>> been made so reduction of this time on a server is a good thing(tm). 
>>>> Equally obviously, trying to achieve this synchronization by asking the
>>>> tasks to cooperate with each other is not a feasible solution and some
>>>> external influence needs to be exerted and this is what spa_svr does --
>>>> it nudges the scheduling order of the tasks in a way that makes them
>>>> become well synced.
>>>>
>>>> Unfortunately, this is not a good scheduler for an interactive system
>>>> as it minimizes the response times for ALL tasks (and the system as a
>>>> whole) and this can result in increased response time for some
>>>> interactive tasks (clunkiness) which annoys interactive users.  When
>>>> you start fiddling with this scheduler to bring back "interactive
>>>> unfairness" you kill a lot of its superior low overall wait time
>>>> performance.
>>> spa_svr is my favorite, but as you mentioned doesn't work well with ia. 
>>> So I started instrumenting its behaviour with chew.c (attached).  What I
>>> found is that prio-levels are way to coarse.  Setting max_tpt_bonus = 3
>>> bounds this somewhat, but it was still not enough.  Looking at
>>> spa_svr_reassess_bonus and changing it to simply adjust prio based on
>>> avg_sleep did the trick like this:
>>>
>>> static void spa_svr_reassess_bonus(struct task_struct *p)
>>> {
>>> 	if (p->sdu.spa.avg_sleep_per_cycle >> 10) {
>>> 		incr_throughput_bonus(p, 1);
>>> 	} else
>>> 		decr_throughput_bonus(p);
>>> }
>> I suspect that this would kill some of the good server performance as it
>> removes the mechanism that minimises wait time.  It is effectively just
>> a simplification of what the vanilla O(1) scheduler tries to do i.e.
>> assume tasks that sleep a lot are interactive and give them a boost.
>>
>> spa_ws tries to do this as well only in a bit more complicated fashion.
>>   So maybe an spa_svr modified in this way and renamed could make a good
>> interactive scheduler.
> 
> Great!
> 
> Reducing the prio-level granularity may also be helpful;

Because of some of the bit operations code makes it a bad idea to have 
more than 160 priority levels, you're more or less limited to 60 
priority levels for SCHED_OTHER tasks (as 100 are used for real time) 
and you need 40 of these to pay some attention to niceness leaving you 
about 20 priority levels to use for fiddling.  Is that enough?

With spa_ebs (now that CPU rate caps have been removed), you have all 60 
priorities available for fiddling with as niceness is taken care of when 
calculating each task's entitlement.

> or maybe even make 
> it adjustable?  Any easy way to introduce something like this?
> 

As long as sysfs remains available it should be fairly easy.  Although 
replacing constants with variables (which may be necessary) has 
space/time overhead implications but they would probably be insignificant.

Peter
-
Peter Williams                                   pwil3058@bigpond.net.au

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

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

Peter Williams wrote:
> Al Boldi wrote:
> > Reducing the prio-level granularity may also be helpful;
>
> Because of some of the bit operations code makes it a bad idea to have
> more than 160 priority levels, you're more or less limited to 60
> priority levels for SCHED_OTHER tasks (as 100 are used for real time)
> and you need 40 of these to pay some attention to niceness leaving you
> about 20 priority levels to use for fiddling.  Is that enough?
>
> With spa_ebs (now that CPU rate caps have been removed), you have all 60
> priorities available for fiddling with as niceness is taken care of when
> calculating each task's entitlement.

Ok, increasing the number of prio-levels is one thing, but I was more 
thinking of reducing the effective difference between each prio-level. For 
example, this would allow max_tpt_bonus=18, while the effective range would 
be 3, thus reducing granularity.  Would this be easily introduceable?


Thanks!

--
Al

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Peter Williams]

Al Boldi wrote:
> Peter Williams wrote:
>> Al Boldi wrote:
>>> Reducing the prio-level granularity may also be helpful;
>> Because of some of the bit operations code makes it a bad idea to have
>> more than 160 priority levels, you're more or less limited to 60
>> priority levels for SCHED_OTHER tasks (as 100 are used for real time)
>> and you need 40 of these to pay some attention to niceness leaving you
>> about 20 priority levels to use for fiddling.  Is that enough?
>>
>> With spa_ebs (now that CPU rate caps have been removed), you have all 60
>> priorities available for fiddling with as niceness is taken care of when
>> calculating each task's entitlement.
> 
> Ok, increasing the number of prio-levels is one thing, but I was more 
> thinking of reducing the effective difference between each prio-level. For 
> example, this would allow max_tpt_bonus=18, while the effective range would 
> be 3, thus reducing granularity.  Would this be easily introduceable?

OK.  Now (I think) I see what you mean.  I think that you could achieve 
this effect by shortening the promotion interval which I think is still 
one of the tunables.  This effectively controls the strength of priority 
levels -- short promotion intervals weaken and long promotion intervals 
strengthen the effect of different priority levels.

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

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

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

Ingo Molnar wrote:
> * William Lee Irwin III <wli@holomorphy.com> wrote:
> > On Sun, Apr 15, 2007 at 09:57:48PM +0200, Ingo Molnar wrote:
> > > Oh I was very much testing "CPU bandwidth allocation as influenced by
> > > nice numbers" - it's one of the basic things i do when modifying the
> > > scheduler. An automated tool, while nice (all automation is nice)
> > > wouldnt necessarily show such bugs though, because here too it needed
> > > thousands of running tasks to trigger in practice. Any volunteers? ;)
> >
> > Worse comes to worse I might actually get around to doing it myself.
> > Any more detailed descriptions of the test for a rainy day?
>
> the main complication here is that the handling of nice levels is still
> typically a 2nd or 3rd degree design factor when writing schedulers. The
> reason isnt carelessness, the reason is simply that users typically only
> care about a single nice level: the one that all tasks run under by
> default.
>
> Also, often there's just one or two good ways to attack the problem
> within a given scheduler approach and the quality of nice levels often
> suffers under other, more important design factors like performance.
>
> This means that for example for the vanilla scheduler the distribution
> of CPU power depends on HZ, on the number of tasks and on the scheduling
> pattern. The distribution of CPU power amongst nice levels is basically
> a function of _everything_. That makes any automated test pretty
> challenging. Both with SD and with CFS there's a good chance to actually
> formalize the meaning of nice levels, but i'd not go as far as to
> mandate any particular behavior by rigidly saying "pass this automated
> tool, else ...", other than "make nice levels resonable". All the other
> more formal CPU resource limitation techniques are then a matter of
> CKRM-alike patches, which offer much more finegrained mechanisms than
> pure nice levels anyway.
>
> so to answer your question: it's pretty much freely defined. Make up
> your mind about it and figure out the ways how people use nice levels
> and think about which aspects of that experience are worth testing for
> intelligently.

I think this post, http://lkml.org/lkml/2007/4/15/5, shows the problem 
clearly with only 3 tasks running.


Thanks!

--
Al

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

Ingo Molnar wrote:
> Anyone who thinks that there exists only two kinds of code: 100% correct
> and 100% incorrect with no shades of grey inbetween is in reality a sort
> of an extremist: whom, depending on mood and affection, we could call
> either a 'coding purist' or a 'coding taliban' ;-)

I am not sure what you mean by this?!?

It's probably well known that nothing is perfect, even if you tried, but to 
use this to excuse sub-optimal coding sounds rather lame.

Now, admitting that everything may be fixable, would have been a much more 
reasonable response.


Thanks!

--
Al

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[William Lee Irwin III]

Ingo Molnar wrote:
>> Anyone who thinks that there exists only two kinds of code: 100% correct
>> and 100% incorrect with no shades of grey inbetween is in reality a sort
>> of an extremist: whom, depending on mood and affection, we could call
>> either a 'coding purist' or a 'coding taliban' ;-)

On Tue, Apr 17, 2007 at 07:29:00PM +0300, Al Boldi wrote:
> I am not sure what you mean by this?!?
> It's probably well known that nothing is perfect, even if you tried, but to 
> use this to excuse sub-optimal coding sounds rather lame.
> Now, admitting that everything may be fixable, would have been a much more 
> reasonable response.

I don't need this sort of help. I wasn't even all that interested in
having it acknowledged as a cfs lacuna, but rather a common design goal
across all scheduler implementations with a standardized semantics.

Granted, some of my insistence was intended as a hint about what might
not be working very well, but I was rather far from wanting to suggest
such things, hence the initial avoidance of even mentioning whatever
issues cfs' current incarnation in particular might have directly. I
rather wanted some statement of the eventual intention, along with some
consensus as to what scheduler implementations in general should also
use as their objective for nice semantics. With that in hand, it would
be made possible to track the progress of cfs in that particular area,
and also make direct comparisons against other schedulers attempting to
implement the same prioritization semantics.

A less abstract statement about this would be that I wanted to hear
"This is what should be going on in the area of prioritization in terms
of nice levels. We can get yardsticks to measure how schedulers are
doing in this area from this." How cfs' current implementation did was
a secondary concern apart from using the issue as a hint about what
there might be to patch up. The whole reason for resorting to hints
instead of going on about nice level support being weak directly was
precisely to avoid making the kind of statement you're making. I'm
not in the business of shooting down scheduler implementations. I
furthermore expect cfs to be useful to people regardless of whether
it "pans out" in terms of mainline acceptance, just as many of the
other out-of-tree schedulers are; if it should hit mainline, so be it,
as it's a technical improvement over epoch expiry semantics regardless.

Also, AFAICS honoring nice levels isn't a fundamental issue with the
design. Adjusting the sorting key calculation, which doesn't affect the
overall design at all, should suffice IMHO. This is also quite far from
what you suggest in terms of the gravity of the issue. While I have my
own disagreements with the response, it's best to take it at face value
instead of the sort of interpretation you're doing.


-- wli

Re: [Announce] [patch] Modular Scheduler Core and Completely Fair

[Al Boldi]

William Lee Irwin III wrote:
> Ingo Molnar wrote:
> >> Anyone who thinks that there exists only two kinds of code: 100%
> >> correct and 100% incorrect with no shades of grey inbetween is in
> >> reality a sort of an extremist: whom, depending on mood and affection,
> >> we could call either a 'coding purist' or a 'coding taliban' ;-)
>
> On Tue, Apr 17, 2007 at 07:29:00PM +0300, Al Boldi wrote:
> > I am not sure what you mean by this?!?
> > It's probably well known that nothing is perfect, even if you tried, but
> > to use this to excuse sub-optimal coding sounds rather lame.
> > Now, admitting that everything may be fixable, would have been a much
> > more reasonable response.
>
> I don't need this sort of help.

This was more directed at the general notion that constructive criticism is 
somehow perceived as perfectionist, when it should rather be taken at face 
value, as being a helping hand.

> The whole reason for resorting to hints
> instead of going on about nice level support being weak directly was
> precisely to avoid making the kind of statement you're making.

Sometimes hints may mean different things to different people, and as such 
may be misleading.  IMHO, being IMHO without resorting to rudeness is much 
more constructive.


Thanks!

--
Al