Skip to contentSkip to conversation

[2.6.6] Replacing CPU scheduler active and expired with a single array

RFC PATCH Peter Williams 2 participants 6 messages May 29, 2004 – May 31, 2004

lore
Share & tools
lore
#0 lore raw
Quoted 9 lines · Con Kolivas
Quoted 7 lines · Peter Williams
Quoted 6 lines · Ingo Molnar

just try it - run a task that runs 95% of the time and sleeps 5% of the time, and run a (same prio) task that runs 100% of the time. With the current scheduler the slightly-sleeping task gets 45% of the CPU, the looping one gets 55% of the CPU. With your patch the slightly-sleeping process can easily monopolize 90% of the CPU!

Quoted 8 lines
Quoted 4 lines

This does, of course, not take into account the interactive bonus. If the task doing the shorter CPU bursts manages to earn a larger interactivity bonus than the other then it will get more CPU but isn't that the intention of the interactivity bonus?

No. Ideally the interactivity bonus should decide what goes first every time to decrease the latency of interactive tasks, but the cpu percentage should remain close to the same for equal "nice" tasks.

There are at least two possible ways of viewing "nice": one of these is that it is an indicator of the tasks entitlement to CPU resource (which is more or less the view you describe) and another that it is an indicator of the task's priority with respect to access to CPU resources.

If you wish the system to take the first of these views then the appropriate solution to the scheduling problem is to use an entitlement based scheduler such as EBS (see <http://sourceforge.net/projects/ebs-linux/>) which is also much simpler than the current O(1) scheduler and has the advantage that it gives pretty good interactive responsiveness without treating interactive tasks specially (although some modification in this regard may be desirable if very high loads are going to be encountered).

If you want the second of these then this proposed modification is a simple way of getting it (with the added proviso that starvation be avoided).

Of course, there can be other scheduling aims such as maximising throughput where different scheduler paradigms need to be used. As a matter of interest these tend to have not very good interactive response.

If the system is an interactive system then all of these models (or at least two of them) need to be modified to "break the rules" as far as interactive tasks are concerned and give them higher priority in order not to try human patience.

Quoted 2 lines

Interactive tasks need low scheduling latency and short bursts of high
cpu usage; not more cpu usage overall. When the cpu percentage differs > significantly from this the logic has failed.

The only way this will happen is if the interactive bonus mechanism misidentifies a CPU bound task as an interactive task and gives it a large bonus. This seems to be the case as tasks with a 95% CPU demand rate are being given a bonus of 9 (out of 10 possible) points.

Peter

Signature · 4 lines
Dr Peter Williams                                [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#1 lore raw
Quoted 49 lines · Peter Williams
Quoted 9 lines · Con Kolivas
Quoted 8 lines · Peter Williams
Quoted 6 lines · Ingo Molnar

just try it - run a task that runs 95% of the time and sleeps 5% of the time, and run a (same prio) task that runs 100% of the time. With the current scheduler the slightly-sleeping task gets 45% of the CPU, the looping one gets 55% of the CPU. With your patch the slightly-sleeping process can easily monopolize 90% of the CPU!

Quoted 8 lines
Quoted 4 lines

This does, of course, not take into account the interactive bonus. If the task doing the shorter CPU bursts manages to earn a larger interactivity bonus than the other then it will get more CPU but isn't that the intention of the interactivity bonus?

No. Ideally the interactivity bonus should decide what goes first every time to decrease the latency of interactive tasks, but the cpu percentage should remain close to the same for equal "nice" tasks.

There are at least two possible ways of viewing "nice": one of these is that it is an indicator of the tasks entitlement to CPU resource (which is more or less the view you describe) and another that it is an indicator of the task's priority with respect to access to CPU resources.

If you wish the system to take the first of these views then the appropriate solution to the scheduling problem is to use an entitlement based scheduler such as EBS (see
<http://sourceforge.net/projects/ebs-linux/>) which is also much simpler than the current O(1) scheduler and has the advantage that it gives pretty good interactive responsiveness without treating interactive tasks specially (although some modification in this regard may be desirable if very high loads are going to be encountered).

If you want the second of these then this proposed modification is a simple way of getting it (with the added proviso that starvation be avoided).

Of course, there can be other scheduling aims such as maximising throughput where different scheduler paradigms need to be used. As a matter of interest these tend to have not very good interactive response.

If the system is an interactive system then all of these models (or at least two of them) need to be modified to "break the rules" as far as interactive tasks are concerned and give them higher priority in order not to try human patience.

Quoted 2 lines

Interactive tasks need low scheduling latency and short bursts of high cpu usage; not more cpu usage overall. When the cpu percentage

Quoted 6 lines

differs > significantly from this the logic has failed.

The only way this will happen is if the interactive bonus mechanism misidentifies a CPU bound task as an interactive task and gives it a large bonus. This seems to be the case as tasks with a 95% CPU demand rate are being given a bonus of 9 (out of 10 possible) points.

This is all a matter of semantics and I have no argument with it.

I think your aims of simplifying the scheduler are admirable but I hope you don't suffer the quagmire that is manipulating the interactivity stuff. Changing one value and saying it has no apparent effect is almost certainly wrong; surely it was put there for a reason - or rather I put it there for a reason.

Con

#2 lore raw
Quoted 59 lines · Con Kolivas
Quoted 49 lines · Peter Williams
Quoted 9 lines · Con Kolivas
Quoted 8 lines · Peter Williams
Quoted 6 lines · Ingo Molnar

just try it - run a task that runs 95% of the time and sleeps 5% of the time, and run a (same prio) task that runs 100% of the time. With the current scheduler the slightly-sleeping task gets 45% of the CPU, the looping one gets 55% of the CPU. With your patch the slightly-sleeping process can easily monopolize 90% of the CPU!

Quoted 8 lines
Quoted 4 lines

This does, of course, not take into account the interactive bonus. If the task doing the shorter CPU bursts manages to earn a larger interactivity bonus than the other then it will get more CPU but isn't that the intention of the interactivity bonus?

No. Ideally the interactivity bonus should decide what goes first every time to decrease the latency of interactive tasks, but the cpu percentage should remain close to the same for equal "nice" tasks.

There are at least two possible ways of viewing "nice": one of these is that it is an indicator of the tasks entitlement to CPU resource (which is more or less the view you describe) and another that it is an indicator of the task's priority with respect to access to CPU resources.

If you wish the system to take the first of these views then the appropriate solution to the scheduling problem is to use an entitlement based scheduler such as EBS (see
<http://sourceforge.net/projects/ebs-linux/>) which is also much simpler than the current O(1) scheduler and has the advantage that it gives pretty good interactive responsiveness without treating interactive tasks specially (although some modification in this regard may be desirable if very high loads are going to be encountered).

If you want the second of these then this proposed modification is a simple way of getting it (with the added proviso that starvation be avoided).

Of course, there can be other scheduling aims such as maximising throughput where different scheduler paradigms need to be used. As a matter of interest these tend to have not very good interactive response.

If the system is an interactive system then all of these models (or at least two of them) need to be modified to "break the rules" as far as interactive tasks are concerned and give them higher priority in order not to try human patience.

Quoted 2 lines

Interactive tasks need low scheduling latency and short bursts of high cpu usage; not more cpu usage overall. When the cpu percentage

Quoted 6 lines

differs > significantly from this the logic has failed.

The only way this will happen is if the interactive bonus mechanism misidentifies a CPU bound task as an interactive task and gives it a large bonus. This seems to be the case as tasks with a 95% CPU demand rate are being given a bonus of 9 (out of 10 possible) points.

Quoted 3 lines

This is all a matter of semantics and I have no argument with it.

I think your aims of simplifying the scheduler are admirable but I hope you don't suffer the quagmire that is manipulating the interactivity stuff.

As you surmise, this patch is just a starting point and there are some parts of it the may need to be fine tuned.

For instance, the current time slice used is set at the average that the current mechanism would have dispensed. Making this smaller would lessen the severity of the anomaly under discussion but making it too small would increase the context switch rate. There is evidence from our kernbench results that we have room to decrease this value and still keep the context switch rate below that of the current scheduler (at least, for normal to moderately heavy loads). If possible I'd like to get some statistics on the sleep/wake cycles of tasks on a typical system to help make a judgment about what is the best value here.

Another area that needs more consideration is the determination of the promotion interval. At the moment, there's no promotion if there's less than 2 runnable tasks on a CPU and the interval is a constant multiplied by the number of runnable tasks otherwise.

Another area of investigation is (yet another) bonus intended to increase system throughput by minimizing (or at least attempting to) the time tasks spend on the run queues. The principal difficulty here is making sure that this doesn't adversely effect interactive responsiveness as it's an unfortunate fact of life that what's good for interactive response isn't necessarily (and usually isn't) good for maximizing throughput and vice versa.

Then, the interactive bonus mechanism might be examined but this is of low priority as the current one seems to do a reasonable job.

Lastly, with the simplification of the scheduler I believe that it would be possible to make both the interactive response and throughput bonuses optional. An example of why this MIGHT BE desirable is that the interactive response bonus adversely effects throughput and turning it off on servers where there are no interactive users may be worthwhile.

Quoted 1 line

Changing one value and saying it has no apparent effect is almost certainly wrong; surely it was put there for a reason - or rather I put it there for a reason.

Out of interest, what was the reason? What problem were you addressing?

Peter

Signature · 4 lines
Dr Peter Williams                                [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#3 lore raw
Quoted 1 line · Peter Williams

Out of interest, what was the reason? What problem were you addressing?

The interactive credit?

There was a problem with difficulty elevating back to interactive state if an interactive task had used too long a burst of cpu (ie Xfree) which was addressed by making the bonus pseudo-exponentially curved for rapid recovery and slow decay - in fact this is probably the most important part of addressing the interactive tasks and had the best effect. The problem was that giving this to all tasks meant that cpu bound tasks that had, as a property of their behaviour, long waits on say pipes or i/o would also get this rapid recovery to interactive state and as soon as they became fully bound to cpu again they would cause noticable stalls. The standard example is the increasing number of jobs in a make, where each job waits longer for i/o as the job numbers increase. However there were much worse examples at even normal - low loads, such as mpeg or divx encoding where the encoder would buffer say 250 frames sleeping and then do them in a burst. (this is the maximum space between key [I] frame or intervals). The interactive credit prevented those tasks that would have long but only infrequent sleeps from getting the curved bonus/penalty.

Hmm... if this is black magic I guess I'm breaking the magician's cardinal rules and revealing my tricks ;-)

Con

#4 lore raw
Quoted 6 lines · Con Kolivas
Quoted 1 line · Peter Williams

Out of interest, what was the reason? What problem were you addressing?

The interactive credit?

No. I was asking about the mechanism in schedule() that, based on the value of "activated", allows some tasks to count their time on the run queue as sleep time.

Quoted 2 lines

There was a problem with difficulty elevating back to interactive state if an interactive task had used too long a burst of cpu (ie Xfree) which was addressed by making the bonus pseudo-exponentially curved for rapid recovery and slow decay - in fact this is probably the most important part of addressing the interactive tasks and had the best effect.

But this probably answers my question anyway.

Quoted 1 line

The problem was that giving this to all tasks meant that cpu bound tasks that had, as a property of their behaviour, long waits on say pipes or i/o would also get this rapid recovery to interactive state and as soon as they became fully bound to cpu again they would cause noticable stalls. The standard example is the increasing number of jobs in a make, where each job waits longer for i/o as the job numbers increase. However there were much worse examples at even normal - low loads, such as mpeg or divx encoding where the encoder would buffer say 250 frames sleeping and then do them in a burst. (this is the maximum space between key [I] frame or intervals). The interactive credit prevented those tasks that would have long but only infrequent sleeps from getting the curved bonus/penalty.

In the near future, I'll be proposing another patch that goes on top of the single priority array (SPA) patch that has the express purpose of reducing the time that all tasks spend on run queues. I think that one of the side effects of this mechanism is that it will alleviate the problem you've described above.

I also think that their is a category of task that may be automatically detected and that needs special attention and that is tasks that need very regular access to small bursts of CPU. I suspect that the tasks doing the mpeg and divx encoding/decoding that you refer to above fall into this category. The key to identifying these tasks would be that the variance (or standard deviation) of their sleeps would be close to zero and as they probably do much the same amount of work each CPU burst the same would be true of the variance of the length of the CPU bursts.
Currently, the scheduler relies on the interactive bonus to make sure
that these tasks get CPU when they need it but I suspect that to make this happen the interactive bonus has to be larger than it might otherwise need to be. So if these tasks can be identified and treated specially (e.g. reserve the MAX_RT_PRIO slot for them) the interactive bonus could be reduced and this would improve overall system throughput.

Quoted 3 lines

Hmm... if this is black magic I guess I'm breaking the magician's cardinal rules and revealing my tricks ;-)

Peter

Signature · 4 lines
Dr Peter Williams                                [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#5 lore raw

Quoting Peter Williams <[email protected]>:

Quoted 6 lines
Quoted 1 line · Con Kolivas

The interactive credit?

No. I was asking about the mechanism in schedule() that, based on the value of "activated", allows some tasks to count their time on the run queue as sleep time.

No this is different again. When there is significant load and an interactive task (like X) is using bursts of cpu it will not get a chance to sleep. It will either run out of timeslice or be preempted and thus will be constantly on the runqueue. In that time if only sleep time is counted it is progressively seen as a cpu bound task - in fact this was a major problem before where X would basically die under load because you'd move a window and it would be constantly waiting for more cpu time rather than ever sleeping.

Quoted 8 lines

I also think that their is a category of task that may be automatically detected and that needs special attention and that is tasks that need very regular access to small bursts of CPU. I suspect that the tasks doing the mpeg and divx encoding/decoding that you refer to above fall into this category. The key to identifying these tasks would be that the variance (or standard deviation) of their sleeps would be close to zero and as they probably do much the same amount of work each CPU burst the same would be true of the variance of the length of the CPU bursts.

I've already tried that experiment and I personally failed to make the pattern of sleep/burst correspond with interactivity. There is a huge variation in the duration of sleep/run for all different things, and it changes with load. Of course your modelling may be better than mine.

Quoted 1 line

Dr Peter Williams [email protected]

Oooh I've got one of those too but I normally dont use it on lkml. So just for this once...

Dr Con Kolivas