Skip to contentSkip to conversation

PlugSched-6.3.1 for 2.6.16-rc5

RFC Al Boldi 4 participants 24 messages Apr 3, 2006 – Apr 11, 2006

lore
Share & tools
lore

Al Boldi

author
#0 lore raw
Quoted 4 lines · Peter Williams
Quoted 1 line · Peter Williams

Peter Williams wrote:

Now available for 2.6.16 at:

Thanks a lot!

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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>

Can this be made runtime selectable/loadable, akin to iosched?

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system. Is there a module to autotune these values according to cpu/mem/ctxt performance?

Also, different schedulers per cpu could be rather useful.

Thanks!

--
Al

#1 lore raw
Quoted 7 lines · On Mon, 3 Apr 2006 14:59:51 +0300 Al Boldi <[email protected]> wrote:
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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>

Can this be made runtime selectable/loadable, akin to iosched?

There is a project to do so:

http://groups.google.com/group/fa.linux.kernel/msg/d555ecee596690d1

Signature · 2 lines
	Paolo Ornati
	Linux 2.6.16-mm2 on x86_64
#2 lore raw
In reply to Al Boldi
Quoted 7 lines · Al Boldi
Quoted 3 lines · Peter Williams
Quoted 1 line · Peter Williams

Peter Williams wrote:

Now available for 2.6.16 at:

Thanks a lot!

Quoted 7 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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>

Can this be made runtime selectable/loadable, akin to iosched?

See <https://sourceforge.net/projects/dynsched>. It's an extension to PlugSched that allows schedulers to be changed at run time.

Quoted 6 lines
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

Quoted 3 lines

Is there a module to autotune these values according to cpu/mem/ctxt performance?

Also, different schedulers per cpu could be rather useful.

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#3 lore raw
Quoted 4 lines · Peter Williams
Quoted 2 lines · Al Boldi

Is there a module to autotune these values according to cpu/mem/ctxt performance?

I think you're thinking of Jake's genetic algorithms (separate patch). They tune the zaphod scheduler but bear in mind the limitation of such an algorithm is they can only tune for one workload which means that if you have two workloads running concurrently with different requirements, the other will suffer.

Quoted 4 lines
Quoted 2 lines

Also, different schedulers per cpu could be rather useful. Peter Williams wrote:

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

I'm curious. How do you think different schedulers per cpu would be useful?

Cheers,
Con

#4 lore raw
Quoted 6 lines · Con Kolivas
Quoted 4 lines · Peter Williams
Quoted 2 lines · Al Boldi

Is there a module to autotune these values according to cpu/mem/ctxt performance?

Quoted 8 lines

I think you're thinking of Jake's genetic algorithms (separate patch). They tune the zaphod scheduler but bear in mind the limitation of such an algorithm is they can only tune for one workload which means that if you have two workloads running concurrently with different requirements, the other will suffer.

Quoted 4 lines
Quoted 2 lines

Also, different schedulers per cpu could be rather useful. Peter Williams wrote:

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

I'm curious. How do you think different schedulers per cpu would be useful?

I don't but I think they MIGHT make sense for cpusets e.g. one set with a scheduler targeted at interactive tasks and another targeted at server tasks. NB the emphasis on might.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#5 lore raw
Quoted 9 lines · Peter Williams
Quoted 8 lines · Con Kolivas
Quoted 6 lines · Peter Williams
Quoted 2 lines · Al Boldi

Also, different schedulers per cpu could be rather useful. Peter Williams wrote:

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

Quoted 6 lines
Quoted 2 lines

I'm curious. How do you think different schedulers per cpu would be useful?

I don't but I think they MIGHT make sense for cpusets e.g. one set with a scheduler targeted at interactive tasks and another targeted at server tasks. NB the emphasis on might.

I am curious as to Al's answer since he asked for the feature. It would be easy for me to modify the staircase cpu scheduler to allow the interactive and compute modes be set on a per-cpu basis if that was desired. For that to be helpful of course you'd have to manually set affinity for the tasks or logins you wanted to run on each cpu(s).

Cheers,
Con

#6 lore raw
Quoted 8 lines · Con Kolivas
Quoted 7 lines · Peter Williams
Quoted 6 lines · Con Kolivas
Quoted 5 lines · Peter Williams
Quoted 2 lines · Al Boldi

Also, different schedulers per cpu could be rather useful. Peter Williams wrote:

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

I'm curious. How do you think different schedulers per cpu would be useful?

I don't but I think they MIGHT make sense for cpusets e.g. one set with a scheduler targeted at interactive tasks and another targeted at server tasks. NB the emphasis on might.

I am curious as to Al's answer since he asked for the feature.

OK.

Quoted 2 lines

It would be easy for me to modify the staircase cpu scheduler to allow the interactive and compute modes be set on a per-cpu basis if that was desired. For that to be helpful of course you'd have to manually set affinity for the tasks or logins you wanted to run on each cpu(s).

Yes, I agree that it would not be a good idea for CPUs that are sharing (via load balancing) the same set of tasks to have different schedulers or policy which is why I suggested only doing it at the cpuset level.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#7 lore raw
Quoted 7 lines · Peter Williams
Quoted 6 lines · Con Kolivas
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 1 line · Al Boldi

Also, different schedulers per cpu could be rather useful.

I think that would be dangerous. However, different schedulers per cpuset might make sense but it involve a fair bit of work.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines

I'm curious. How do you think different schedulers per cpu would be useful?

I don't but I think they MIGHT make sense for cpusets e.g. one set with a scheduler targeted at interactive tasks and another targeted at server tasks. NB the emphasis on might.

Exactly.

Quoted 1 line
Quoted 1 line

I am curious as to Al's answer since he asked for the feature.

Can you imagine how neat it would be to set timeslice per cpuset/workload?

Quoted 5 lines
Quoted 5 lines

It would be
easy for me to modify the staircase cpu scheduler to allow the interactive and compute modes be set on a per-cpu basis if that was desired. For that to be helpful of course you'd have to manually set affinity for the tasks or logins you wanted to run on each cpu(s).

Your staircase scheduler is great, and adding this feature would make it unique.

Thanks!

--
Al

author
#8 lore raw
In reply to Peter Williams
Quoted 10 lines · Peter Williams
Quoted 5 lines · Al Boldi
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

Thanks!

--
Al

#9 lore raw
Quoted 11 lines · Al Boldi
Quoted 8 lines · Peter Williams
Quoted 4 lines · Al Boldi
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

OK, you could also try increasing the promotion interval.

It should be noted that spa_no_frills isn't really expected to behave very well as it's a pure round robin scheduler. It's intended purpose is as a basis for more sophisticated schedulers. I've been thinking about removing it as a bootable scheduler and only making its children available but I find it useful to compare benchmark and other test results from it with that from the other schedulers to get an idea of the extra costs involved.

Similarly, zaphod is really just a vehicle for trying different ideas and the spa_ws, spa_svr and spa_ebs are the ones intended for use on real systems. Of these, spa_svr isn't very good for interactive systems as it is designed to maximize throughput on a server (it actually beats spa_no_frills by about 1% on kernbench) which isn't always compatible with good interactive response.

Thanks,
Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#10 lore raw
Quoted 9 lines · Peter Williams
Quoted 8 lines · Al Boldi
Quoted 7 lines · Peter Williams
Quoted 5 lines · Al Boldi
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

OK, you could also try increasing the promotion interval.

Seems that this will only delay the lock in spa_svr but not inhibit it.

Quoted 2 lines

It should be noted that spa_no_frills isn't really expected to behave very well as it's a pure round robin scheduler.

It's a bare bone scheduler that allows to prioritize procs to the admins desire, instead of leaving the priority management to the scheduler, which may be undesirable for some but not all.

Quoted 1 line

It's intended purpose is as a basis for more sophisticated schedulers.

And that's why the same problem exists in the child scheds, i.e. spa_ws, spa_svr, zaphod, but not spa_ebs.

Quoted 5 lines

I've been thinking
about removing it as a bootable scheduler and only making its children available but I find it useful to compare benchmark and other test results from it with that from the other schedulers to get an idea of the extra costs involved.

Thanks!

--
Al

#11 lore raw
Quoted 8 lines · Al Boldi
Quoted 7 lines · Peter Williams
Quoted 6 lines · Al Boldi
Quoted 5 lines · Peter Williams
Quoted 4 lines · Al Boldi
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Quoted 8 lines
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

OK, you could also try increasing the promotion interval.

Seems that this will only delay the lock in spa_svr but not inhibit it.

OK. But turning the promotion mechanism off completely (which is what setting the floor to the maximum) runs the risk of a runaway high priority task locking the whole system up. IMHO the only SPA scheduler where it's safe for the promotion floor to be greater than MAX_RT_PRIO is spa_ebs. So a better solution is highly desirable.

I'd like to fix this problem but don't fully understand what it is. What do you mean by a malloc-hog? Would it possible for you to give me an example of how to reproduce the problem?

Quoted 5 lines
Quoted 3 lines

It should be noted that spa_no_frills isn't really expected to behave very well as it's a pure round robin scheduler.

It's a bare bone scheduler that allows to prioritize procs to the admins desire, instead of leaving the priority management to the scheduler, which may be undesirable for some but not all.

OK. But it's important to realize that "nice" does not (in general) control the "amount of CPU" that tasks get with this scheduler. It merely controls the order in which runnable tasks run i.e. it's a "priority based" interpretation of "nice" not an "entitlement based" interpretation. The difference is important.

If you want a "bare bones" scheduler with an "entitlement based" interpretation of "nice" use spa_ebs with the maximum bonuses set to zero. In that state spa_ebs is safe for promotion to be completely disabled unless you also want to use cpu caps (in which case you'd need to set the floor to about 137 to make sure that capped tasks don't get completely starved).

Quoted 4 lines
Quoted 2 lines

It's intended purpose is as a basis for more sophisticated schedulers.

And that's why the same problem exists in the child scheds, i.e. spa_ws, spa_svr, zaphod, but not spa_ebs.

OK.

Quoted 6 lines
Quoted 6 lines

I've been thinking
about removing it as a bootable scheduler and only making its children available but I find it useful to compare benchmark and other test results from it with that from the other schedulers to get an idea of the extra costs involved.

Thanks,
Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#12 lore raw
Quoted 22 lines · Peter Williams
Quoted 21 lines · Al Boldi
Quoted 19 lines · Peter Williams
Quoted 10 lines · Al Boldi
Quoted 9 lines · Peter Williams
Quoted 7 lines · Al Boldi
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Quoted 6 lines
Quoted 3 lines

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

OK, you could also try increasing the promotion interval.

Quoted 7 lines
Quoted 1 line

Seems that this will only delay the lock in spa_svr but not inhibit it.

OK. But turning the promotion mechanism off completely (which is what setting the floor to the maximum) runs the risk of a runaway high priority task locking the whole system up. IMHO the only SPA scheduler where it's safe for the promotion floor to be greater than MAX_RT_PRIO is spa_ebs. So a better solution is highly desirable.

Yes.

Quoted 3 lines

I'd like to fix this problem but don't fully understand what it is. What do you mean by a malloc-hog? Would it possible for you to give me an example of how to reproduce the problem?

Can you try the attached mem-eater passing it the number of kb to be eaten.

	i.e. '# while :; do ./eatm 9999 ; done' 

This will print the number of bytes eaten and the timing in ms.

Adjust the number of kb to be eaten such that the timing will be less than timeslice (120ms by default for spa). Switch to another vt and start pressing enter. A console lockup should follow within seconds for all spas except ebs.

Thanks!

--
Al

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

unsigned long elapsed(int start) {

	static struct timeval s,e;

	if (start) return gettimeofday(&s, NULL);

	gettimeofday(&e, NULL);

	return ((e.tv_sec - s.tv_sec) * 1000 + (e.tv_usec - s.tv_usec) / 1000);

}

int main(int argc, char **argv) {

    unsigned long int i,j,max;
    unsigned char *p;

    if (argc>1)
	max=atol(argv[1]);
    else
	max=0x60000;


    elapsed(1); 

    for (i=0;((i<max/1024) && (p = (char *)malloc(1024*1024)));i++) {
        for (j=0;j<1024;p[1024*j++]=0);
	fprintf(stderr,"\r%d MB ",i+1);
    }

    for (j=max-(i*=1024);((i<max) && (p = (char *)malloc(1024)));i++) {
	*p = 0;
    }
    fprintf(stderr,"%d KB ",j-(max-i));

    fprintf(stderr,"eaten in %lu msec (%lu MB/s)\n",elapsed(0),i/(elapsed(0)?:1)*1000/1024);

    return 0;
}
#13 lore raw
Quoted 31 lines · Al Boldi
Quoted 16 lines · Peter Williams
Quoted 15 lines · Al Boldi
Quoted 14 lines · Peter Williams
Quoted 13 lines · Al Boldi
Quoted 10 lines · Peter Williams
Quoted 6 lines · Al Boldi
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

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

/sys/cpusched/<scheduler>/

The default values for spa make it really easy to lock up the system.

Which one of the SPA schedulers and under what conditions? I've been mucking around with these and may have broken something. If so I'd like to fix it.

spa_no_frills, with a malloc-hog less than timeslice. Setting promotion_floor to max unlocks the console.

Quoted 7 lines
Quoted 2 lines
Quoted 1 line

OK, you could also try increasing the promotion interval.

Seems that this will only delay the lock in spa_svr but not inhibit it.

OK. But turning the promotion mechanism off completely (which is what setting the floor to the maximum) runs the risk of a runaway high priority task locking the whole system up. IMHO the only SPA scheduler where it's safe for the promotion floor to be greater than MAX_RT_PRIO is spa_ebs. So a better solution is highly desirable.

Yes.

Quoted 3 lines

I'd like to fix this problem but don't fully understand what it is. What do you mean by a malloc-hog? Would it possible for you to give me an example of how to reproduce the problem?

Quoted 7 lines

Can you try the attached mem-eater passing it the number of kb to be eaten.

	i.e. '# while :; do ./eatm 9999 ; done' 

This will print the number of bytes eaten and the timing in ms.

Adjust the number of kb to be eaten such that the timing will be less than timeslice (120ms by default for spa). Switch to another vt and start pressing enter. A console lockup should follow within seconds for all spas except ebs.

This doesn't seem to present a problem (other than the eatme loop being hard to kill with control-C) on my system using spa_ws with standard settings. I tried both UP and SMP. I may be doing something wrong or perhaps don't understand what you mean by a console lock up. When you say "less than the timeslice" how much smaller do you mean?

Peter
PS I even managed to do a kernel build with the eatme loop running on a single processor system.

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#14 lore raw
Quoted 13 lines · Peter Williams
Quoted 11 lines · Al Boldi

Can you try the attached mem-eater passing it the number of kb to be eaten.

	i.e. '# while :; do ./eatm 9999 ; done'

This will print the number of bytes eaten and the timing in ms.

Adjust the number of kb to be eaten such that the timing will be less than timeslice (120ms by default for spa). Switch to another vt and start pressing enter. A console lockup should follow within seconds for all spas except ebs.

Quoted 4 lines

This doesn't seem to present a problem (other than the eatme loop being hard to kill with control-C) on my system using spa_ws with standard settings. I tried both UP and SMP. I may be doing something wrong or perhaps don't understand what you mean by a console lock up.

Switching from one vt to another receives hardly any response.

This is especially visible in spa_no_frills, and spa_ws recovers from this lockup somewhat and starts exhibiting this problem as a choking behavior.

Running '# top d.1 (then shift T)' on another vt shows this choking behavior as the proc gets boosted.

Quoted 1 line

When you say "less than the timeslice" how much smaller do you mean?

This depends on your machine's performance. On my 400MhzP2 UP 128MB, w/ spa_no_frills default settings, looping eatm 9999 takes 63ms per eat and causes the rest of the system to be starved. Raising kb to 19999 takes 126ms which is greater than the default 120ms timeslice and causes no system starvation.

What numbers do you get?

Thanks!

--
Al

#15 lore raw
Quoted 13 lines · Al Boldi
Quoted 12 lines · Peter Williams
Quoted 11 lines · Al Boldi

Can you try the attached mem-eater passing it the number of kb to be eaten.

	i.e. '# while :; do ./eatm 9999 ; done'

This will print the number of bytes eaten and the timing in ms.

Adjust the number of kb to be eaten such that the timing will be less than timeslice (120ms by default for spa). Switch to another vt and start pressing enter. A console lockup should follow within seconds for all spas except ebs.

Quoted 6 lines
Quoted 4 lines

This doesn't seem to present a problem (other than the eatme loop being hard to kill with control-C) on my system using spa_ws with standard settings. I tried both UP and SMP. I may be doing something wrong or perhaps don't understand what you mean by a console lock up.

Switching from one vt to another receives hardly any response.

Aah. Virtual terminals. I was using Gnome terminals under X.

Quoted 10 lines

This is especially visible in spa_no_frills, and spa_ws recovers from this lockup somewhat and starts exhibiting this problem as a choking behavior.

Running '# top d.1 (then shift T)' on another vt shows this choking behavior as the proc gets boosted.

Quoted 1 line

When you say "less than the timeslice" how much smaller do you mean?

This depends on your machine's performance. On my 400MhzP2 UP 128MB, w/ spa_no_frills default settings, looping eatm 9999 takes 63ms per eat and causes the rest of the system to be starved. Raising kb to 19999 takes 126ms which is greater than the default 120ms timeslice and causes no system starvation.

What numbers do you get?

For 9999 I get 20ms. I have 1GB of memory and no swapping is taking place but with only 128MB it's possible that your system is swapping and that could make the effect more pronounced.

But anyway, based on the evidence, I think the problem is caused by the fact that the eatm tasks are running to completion in less than one time slice without sleeping and this means that they never have their priorities reassessed. The reason that spa_ebs doesn't demonstrate the problem is that it uses a smaller time slice for the first time slice that a task gets. The reason that it does this is that it gives newly forked processes a fairly high priority and if they're left to run for a full 120 msecs at that high priority they can hose the system. Having a shorter first time slice gives the scheduler a chance to reassess the task's priority before it does much damage.

The reason that the other schedulers don't have this strategy is that I didn't think that it was necessary. Obviously I was wrong and should extend it to the other schedulers. It's doubtful whether this will help a great deal with spa_no_frills as it is pure round robin and doesn't reassess priorities except when nice changes of the task changes policies. This is one good reason not to use spa_no_frills on production systems. Perhaps you should consider creating a child scheduler on top of it that meets your needs?

Anyway, an alternative (and safer) way to reduce the effects of this problem (while your waiting for me to do the above change) is to reduce the size of the time slice. The only bad effects of doing this is that you'll do slightly worse (less than 1%) on kernbench.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#16 lore raw
Quoted 5 lines · Peter Williams
Quoted 4 lines · Al Boldi

This is especially visible in spa_no_frills, and spa_ws recovers from this lockup somewhat and starts exhibiting this problem as a choking behavior.

Quoted 7 lines
Quoted 2 lines

Running '# top d.1 (then shift T)' on another vt shows this choking behavior as the proc gets boosted.

But anyway, based on the evidence, I think the problem is caused by the fact that the eatm tasks are running to completion in less than one time slice without sleeping and this means that they never have their priorities reassessed.

Yes.

Quoted 7 lines

The reason that spa_ebs doesn't demonstrate the
problem is that it uses a smaller time slice for the first time slice that a task gets. The reason that it does this is that it gives newly forked processes a fairly high priority and if they're left to run for a full 120 msecs at that high priority they can hose the system. Having a shorter first time slice gives the scheduler a chance to reassess the task's priority before it does much damage.

But how does this explain spa_no_frills setting promotion to max not having this problem?

Quoted 6 lines

The reason that the other schedulers don't have this strategy is that I didn't think that it was necessary. Obviously I was wrong and should extend it to the other schedulers. It's doubtful whether this will help a great deal with spa_no_frills as it is pure round robin and doesn't reassess priorities except when nice changes of the task changes policies.

Would it hurt to add it to spa_no_frills and let the children inherit it?

Quoted 2 lines

This is one good reason not to use spa_no_frills on production systems.

spa_ebs is great, but rather bursty. Even setting max_ia_bonus=0 doesn't fix that. Is there a way to smooth it like spa_no_frills?

Quoted 2 lines

Perhaps you should consider creating a child
scheduler on top of it that meets your needs?

Perhaps.

Quoted 4 lines

Anyway, an alternative (and safer) way to reduce the effects of this problem (while your waiting for me to do the above change) is to reduce the size of the time slice. The only bad effects of doing this is that you'll do slightly worse (less than 1%) on kernbench.

Actually, setting timeslice to 5,50,100 gives me better performance on kernbench. After closer inspection, I found 120ms a rather awkward timeslice whereas 5,50, and 100 exhibited a smoother and faster response, which may be machine dependent, thus the need for an autotuner.

Thanks!

--
Al

#17 lore raw
Quoted 23 lines · Al Boldi
Quoted 11 lines · Peter Williams
Quoted 6 lines · Al Boldi

This is especially visible in spa_no_frills, and spa_ws recovers from this lockup somewhat and starts exhibiting this problem as a choking behavior.

Running '# top d.1 (then shift T)' on another vt shows this choking behavior as the proc gets boosted.

But anyway, based on the evidence, I think the problem is caused by the fact that the eatm tasks are running to completion in less than one time slice without sleeping and this means that they never have their priorities reassessed.

Yes.

Quoted 7 lines

The reason that spa_ebs doesn't demonstrate the
problem is that it uses a smaller time slice for the first time slice that a task gets. The reason that it does this is that it gives newly forked processes a fairly high priority and if they're left to run for a full 120 msecs at that high priority they can hose the system. Having a shorter first time slice gives the scheduler a chance to reassess the task's priority before it does much damage.

Quoted 1 line

But how does this explain spa_no_frills setting promotion to max not having this problem?

I'm still puzzled by this. The only thing I can think of is that the promotion mechanism is to simple in that it just moves all promotable tasks up one slot without regard for how long they've been on the queue.
Doing this was a deliberate decision based on the desire to minimize
overhead and the belief that it wouldn't matter in the grand scheme of things. I may do some experimenting with slightly more sophisticated version.

Properly done, promotion should hardly ever occur but the cost would be slightly more complex enqueue/dequeue operations. The current version will do unnecessary promotions but it was felt this was more than compensated for by the lower enqueue/dequeue costs. We'll see how a more sophisticated version goes in terms of trade offs.

Quoted 9 lines
Quoted 7 lines

The reason that the other schedulers don't have this strategy is that I didn't think that it was necessary. Obviously I was wrong and should extend it to the other schedulers. It's doubtful whether this will help a great deal with spa_no_frills as it is pure round robin and doesn't reassess priorities except when nice changes of the task changes policies.

Would it hurt to add it to spa_no_frills and let the children inherit it?

That would be the plan :-)

Quoted 5 lines
Quoted 3 lines

This is one good reason not to use spa_no_frills on production systems.

spa_ebs is great, but rather bursty. Even setting max_ia_bonus=0 doesn't fix that. Is there a way to smooth it like spa_no_frills?

The principal determinant would be the smoothness of the yardstick. This is supposed to represent the task with the highest (recent) CPU usage rate per share and is used to determine how fairly CPU is being distributed among the currently active tasks. Tasks are given a priority based on how their CPU usage rate per share compares to this yardstick. This means that as the system load and/or type of task running changes the priorities of the tasks can change dramatically.

Is the burstiness that you're seeing just in the observed priorities or is it associated with behavioural burstiness as well?

Quoted 5 lines
Quoted 3 lines

Perhaps you should consider creating a child
scheduler on top of it that meets your needs?

Perhaps.

Good. I've been hoping that other interested parties might be encouraged by the small interface to SPA children to try different ideas for scheduling.

Quoted 7 lines
Quoted 5 lines

Anyway, an alternative (and safer) way to reduce the effects of this problem (while your waiting for me to do the above change) is to reduce the size of the time slice. The only bad effects of doing this is that you'll do slightly worse (less than 1%) on kernbench.

Actually, setting timeslice to 5,50,100 gives me better performance on kernbench. After closer inspection, I found 120ms a rather awkward timeslice whereas 5,50, and 100 exhibited a smoother and faster response, which may be machine dependent, thus the need for an autotuner.

When I had the SPA schedulers fully instrumented I did some long term measurements of my work station and found that the average CPU burst for all tasks was only a few msecs. The exceptions were some of the tasks involved in building kernels. So the only bad effects of reducing the time slice will be causing those tasks to have more context switches than otherwise and this will slightly reduce their throughput.

One thing that could be played with here is to vary the time slice based on the priority. This would be in the opposite direction to the normal scheduler with higher priority tasks (i.e. those with lower prio values) getting smaller time slices. The rationale being:

1. stop tasks that have been given large bonuses from shutting out other tasks for too long, and
2. reduce the context switch rate for tasks that haven't received bonuses.

Because tasks that get large bonuses will have short CPU bursts they should not be adversely effected (if this is done properly) as they will (except in exceptional circumstances such as a change in behaviour) surrender the CPU voluntarily before their reduced time slice has expired. Imaginative use of the available statistics could make this largely automatic but there would be a need to be aware that the statistics can be distorted by the shorter time slices.

On the other hand, giving tasks without bonuses longer time slices shouldn't adversely effect interactive performance as the interactive tasks will (courtesy of their bonuses) preempt them.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#18 lore raw
Quoted 12 lines · Peter Williams
Quoted 2 lines · Al Boldi

But how does this explain spa_no_frills setting promotion to max not having this problem?

I'm still puzzled by this. The only thing I can think of is that the promotion mechanism is to simple in that it just moves all promotable tasks up one slot without regard for how long they've been on the queue.
Doing this was a deliberate decision based on the desire to minimize
overhead and the belief that it wouldn't matter in the grand scheme of things. I may do some experimenting with slightly more sophisticated version.

Quoted 5 lines

Properly done, promotion should hardly ever occur but the cost would be slightly more complex enqueue/dequeue operations. The current version will do unnecessary promotions but it was felt this was more than compensated for by the lower enqueue/dequeue costs. We'll see how a more sophisticated version goes in terms of trade offs.

Would this affect the current, nearly perfect, spa_no_frills rr-behaviour w/ its ability to circumvent the timeslice problem when setting promo to max?

Quoted 14 lines
Quoted 5 lines
Quoted 2 lines

This is one good reason not to use spa_no_frills on production systems.

spa_ebs is great, but rather bursty. Even setting max_ia_bonus=0
doesn't fix that. Is there a way to smooth it like spa_no_frills?

The principal determinant would be the smoothness of the yardstick. This is supposed to represent the task with the highest (recent) CPU usage rate per share and is used to determine how fairly CPU is being distributed among the currently active tasks. Tasks are given a priority based on how their CPU usage rate per share compares to this yardstick. This means that as the system load and/or type of task running changes the priorities of the tasks can change dramatically.

Quoted 2 lines

Is the burstiness that you're seeing just in the observed priorities or is it associated with behavioural burstiness as well?

It's behavioural, exhibited in a choking style, like a jumpy mouse move during ia boosts.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

Perhaps you should consider creating a child
scheduler on top of it that meets your needs?

Perhaps.

Good. I've been hoping that other interested parties might be encouraged by the small interface to SPA children to try different ideas for scheduling.

Is there a no-op child skeleton available?

Quoted 17 lines

One thing that could be played with here is to vary the time slice based on the priority. This would be in the opposite direction to the normal scheduler with higher priority tasks (i.e. those with lower prio values) getting smaller time slices. The rationale being:

1. stop tasks that have been given large bonuses from shutting out other tasks for too long, and
2. reduce the context switch rate for tasks that haven't received bonuses.

Because tasks that get large bonuses will have short CPU bursts they should not be adversely effected (if this is done properly) as they will (except in exceptional circumstances such as a change in behaviour) surrender the CPU voluntarily before their reduced time slice has expired. Imaginative use of the available statistics could make this largely automatic but there would be a need to be aware that the statistics can be distorted by the shorter time slices.

Quoted 3 lines

On the other hand, giving tasks without bonuses longer time slices shouldn't adversely effect interactive performance as the interactive tasks will (courtesy of their bonuses) preempt them.

I couldn't agree more. Tackling the problem on both fronts (prio/tslice) may give us more control, which could result in a more appropriate / fairer / smoother scheduler.

Thanks!

--
Al

#19 lore raw
Quoted 12 lines · Al Boldi
Quoted 11 lines · Peter Williams
Quoted 2 lines · Al Boldi

But how does this explain spa_no_frills setting promotion to max not having this problem?

I'm still puzzled by this. The only thing I can think of is that the promotion mechanism is to simple in that it just moves all promotable tasks up one slot without regard for how long they've been on the queue.
Doing this was a deliberate decision based on the desire to minimize
overhead and the belief that it wouldn't matter in the grand scheme of things. I may do some experimenting with slightly more sophisticated version.

Quoted 7 lines
Quoted 5 lines

Properly done, promotion should hardly ever occur but the cost would be slightly more complex enqueue/dequeue operations. The current version will do unnecessary promotions but it was felt this was more than compensated for by the lower enqueue/dequeue costs. We'll see how a more sophisticated version goes in terms of trade offs.

Would this affect the current, nearly perfect, spa_no_frills rr-behaviour w/ its ability to circumvent the timeslice problem when setting promo to max?

No, I'd leave those controls in there.

Quoted 13 lines
Quoted 13 lines
Quoted 5 lines
Quoted 3 lines

This is one good reason not to use spa_no_frills on production systems.

spa_ebs is great, but rather bursty. Even setting max_ia_bonus=0
doesn't fix that. Is there a way to smooth it like spa_no_frills?

The principal determinant would be the smoothness of the yardstick. This is supposed to represent the task with the highest (recent) CPU usage rate per share and is used to determine how fairly CPU is being distributed among the currently active tasks. Tasks are given a priority based on how their CPU usage rate per share compares to this yardstick. This means that as the system load and/or type of task running changes the priorities of the tasks can change dramatically.

Quoted 4 lines
Quoted 2 lines

Is the burstiness that you're seeing just in the observed priorities or is it associated with behavioural burstiness as well?

It's behavioural, exhibited in a choking style, like a jumpy mouse move during ia boosts.

Yeah, I just tried it on my machine with the same results. It used to behave quite well so I must have broken something recently. I've been trying different things for IA bonus calculations.

BTW I've increased the smoothing of my rate statistics and that should help smooth scheduling as a whole. It used to average a tasks behaviour over its last 10 cycles but now it does it over 44. Plus I've moved initial_time_slice as discussed. I'll post patches for 2.6.17-rc1-mm2 shortly.

Quoted 9 lines
Quoted 7 lines
Quoted 4 lines
Quoted 3 lines

Perhaps you should consider creating a child
scheduler on top of it that meets your needs?

Perhaps.

Good. I've been hoping that other interested parties might be encouraged by the small interface to SPA children to try different ideas for scheduling.

Is there a no-op child skeleton available?

No. But I could create one.

Quoted 18 lines
Quoted 18 lines

One thing that could be played with here is to vary the time slice based on the priority. This would be in the opposite direction to the normal scheduler with higher priority tasks (i.e. those with lower prio values) getting smaller time slices. The rationale being:

1. stop tasks that have been given large bonuses from shutting out other tasks for too long, and
2. reduce the context switch rate for tasks that haven't received bonuses.

Because tasks that get large bonuses will have short CPU bursts they should not be adversely effected (if this is done properly) as they will (except in exceptional circumstances such as a change in behaviour) surrender the CPU voluntarily before their reduced time slice has expired. Imaginative use of the available statistics could make this largely automatic but there would be a need to be aware that the statistics can be distorted by the shorter time slices.

Quoted 5 lines
Quoted 3 lines

On the other hand, giving tasks without bonuses longer time slices shouldn't adversely effect interactive performance as the interactive tasks will (courtesy of their bonuses) preempt them.

I couldn't agree more. Tackling the problem on both fronts (prio/tslice) may give us more control, which could result in a more appropriate / fairer / smoother scheduler.

"Hedging one's bets" as punters would say.

Quoted 2 lines

Thanks!

My pleasure.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#20 lore raw
In reply to Al Boldi
Quoted 3 lines · Al Boldi

The default values for spa make it really easy to lock up the system. Is there a module to autotune these values according to cpu/mem/ctxt performance?

Jake Moilanen had a genetic algorithm autotuner for Zaphod at one time which I believe he ported over to PlugSched (as he said he was going to). However, I remove the per run queue statistics that he used to use some time ago and he hasn't complained so I've assumed that he's given up on it. I've CC'd him on this mail so he may tell you what's happening.

I could generate a patch to gather the statistic again and make them available via /proc if you would like to try a user space version of Jake's work (his was in kernel).

Peter
PS The reason that I removed the stats gathering is that they add overhead which is undesirable if they're not being used so if I put them back it would probably be as a build configurable option.

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#21 lore raw
Quoted 7 lines · Peter Williams
Quoted 3 lines · Al Boldi

The default values for spa make it really easy to lock up the system. Is there a module to autotune these values according to cpu/mem/ctxt performance?

Jake Moilanen had a genetic algorithm autotuner for Zaphod at one time which I believe he ported over to PlugSched

Would this be a load-adaptive dynamic tuner?

What I meant was a lock-preventive static tuner. Something that would take hw-latencies into account at boot and set values for non-locking console operation.

Quoted 3 lines

I could generate a patch to gather the statistic again and make them available via /proc if you would like to try a user space version of Jake's work (his was in kernel).

That would be great!

Thanks!

--
Al

#22 lore raw
Quoted 9 lines · Al Boldi
Quoted 6 lines · Peter Williams
Quoted 3 lines · Al Boldi

The default values for spa make it really easy to lock up the system. Is there a module to autotune these values according to cpu/mem/ctxt performance?

Jake Moilanen had a genetic algorithm autotuner for Zaphod at one time which I believe he ported over to PlugSched

Would this be a load-adaptive dynamic tuner?

Yes.

Quoted 2 lines

What I meant was a lock-preventive static tuner. Something that would take hw-latencies into account at boot and set values for non-locking console operation.

I'm not sure what you mean here. Can you elaborate?

Quoted 6 lines
Quoted 4 lines

I could generate a patch to gather the statistic again and make them available via /proc if you would like to try a user space version of Jake's work (his was in kernel).

That would be great!

OK, I'll put it on my "to do" list.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
author
#23 lore raw
Quoted 7 lines · Peter Williams
Quoted 6 lines · Al Boldi
Quoted 5 lines · Peter Williams
Quoted 3 lines · Al Boldi

The default values for spa make it really easy to lock up the system. Is there a module to autotune these values according to cpu/mem/ctxt performance?

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Jake Moilanen had a genetic algorithm autotuner for Zaphod at one time which I believe he ported over to PlugSched

Would this be a load-adaptive dynamic tuner?

Yes.

Wow!

Quoted 5 lines
Quoted 3 lines

What I meant was a lock-preventive static tuner. Something that would take hw-latencies into account at boot and set values for non-locking console operation.

I'm not sure what you mean here. Can you elaborate?

Quoted 13 lines · In another thread Al Boldi

After playing w/ these tunables it occurred to me that they are really only deadline limits, w/ a direct relation to cpu/mem/ctxt perf.

i.e timeslice=1 on i386sx means something other than timeslice=1 on amd64

It follows that w/o autotuning, the static default values have to be selected to allow for a large underlying perf range w/ a preference for the high range. This is also the reason why 2.6 feels really crummy on low perf ranges.

Autotuning the default values would allow to tighten this range specific to the hw used, thus allowing for a smoother desktop experience.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

I could generate a patch to gather the statistic again and make them available via /proc if you would like to try a user space version of Jake's work (his was in kernel).

That would be great!

OK, I'll put it on my "to do" list.

Thanks!

--
Al