CFS scheduler, v3

this is the third release of the CFS patchset (against v2.6.21-rc7), and can be downloaded from:
http://redhat.com/~mingo/cfs-scheduler/
this is a pure "fix reported regressions" release so there's much less churn:

   5 files changed, 71 insertions(+), 29 deletions(-)

(the added lines are mostly debug related, not genuine increase in the scheduler's size)

It appears to me that the following can be taken in for mainline (or rejected for mainline) independently of the rest of the cfs patch.

Mark the runqueues ____cacheline_aligned_in_smp to avoid false sharing.

Quoted 2 lines

Mark the runqueues ____cacheline_aligned_in_smp to avoid false sharing.

False sharing for a per cpu data structure? Are we updating that structure from other processors?

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

Mark the runqueues ____cacheline_aligned_in_smp to avoid false sharing.

Quoted 2 lines · Christoph Lameter

False sharing for a per cpu data structure? Are we updating that structure from other processors?

Primarily in the load balancer, but also in wakeups.

Quoted 2 lines

Quoted 2 lines

False sharing for a per cpu data structure? Are we updating that structure from other processors?

Quoted 1 line

Primarily in the load balancer, but also in wakeups.

That is fairly rare I think. What other variables that are also writtten frequently would cause false sharing?

I'm not really convinced it's all that worthwhile of an optimization, essentially for the same reasons as you, but presumably there's a benchmark result somewhere that says it matters. I've just not seen it.

Quoted 3 lines

I'm not really convinced it's all that worthwhile of an optimization, essentially for the same reasons as you, but presumably there's a benchmark result somewhere that says it matters. I've just not seen it.

If it is true that we frequently remotely write the per cpu runqueue data then we may have a NUMA scalability issue.

From the discussion on Suresh's thread, it appears to have sped up a

Quoted 3 lines · William Lee Irwin III

Quoted 3 lines

I'm not really convinced it's all that worthwhile of an optimization, essentially for the same reasons as you, but presumably there's a benchmark result somewhere that says it matters. I've just not seen it.

Quoted 2 lines · Christoph Lameter

If it is true that we frequently remotely write the per cpu runqueue data then we may have a NUMA scalability issue.

From the discussion on Suresh's thread, it appears to have sped up a database benchmark 0.5%.

Last I checked it was workload-dependent, but there were things that hammer it. I mostly know of the remote wakeup issue, but there could be other things besides wakeups that do it, too.

Quoted 3 lines

Last I checked it was workload-dependent, but there were things that hammer it. I mostly know of the remote wakeup issue, but there could be other things besides wakeups that do it, too.

remote wakeup was the main issue and the 0.5% improvement was seen on a two node platform. Aligning it reduces the number of remote cachelines that needs to be touched as part of this wakeup.

Quoted 4 lines · Suresh B

Quoted 3 lines

Last I checked it was workload-dependent, but there were things that hammer it. I mostly know of the remote wakeup issue, but there could be other things besides wakeups that do it, too.

Quoted 3 lines

remote wakeup was the main issue and the 0.5% improvement was seen on a two node platform. Aligning it reduces the number of remote cachelines that needs to be touched as part of this wakeup.

.5% is usually in the noise ratio. Are you consistently seeing an improvement or is that sporadic?

Quoted 2 lines

.5% is usually in the noise ratio. Are you consistently seeing an improvement or is that sporadic?

No. This is consistent. I am waiting for the perf data on a much much bigger NUMA box.

Anyhow, this is a straight forward optimization and needs to be done. Do you have any specific concerns?

Quoted 2 lines · Suresh B

Anyhow, this is a straight forward optimization and needs to be done. Do you have any specific concerns?

Yes there should not be contention on per cpu data in principle. The point of per cpu data is for the cpu to have access to contention free cachelines.

If the data is contented then it should be moved out of per cpu data and properly placed to minimize contention. Otherwise we will get into cacheline aliases (__read_mostly in per cpu??) etc etc in the per cpu areas.

Quoted 8 lines · Christoph Lameter

Quoted 2 lines · Suresh B

Anyhow, this is a straight forward optimization and needs to be done. Do you have any specific concerns?

Yes there should not be contention on per cpu data in principle. The point of per cpu data is for the cpu to have access to contention free cachelines.

Quoted 3 lines

If the data is contented then it should be moved out of per cpu data and properly placed to minimize contention. Otherwise we will get into cacheline aliases (__read_mostly in per cpu??) etc etc in the per cpu areas.

yes, we were planning to move this to a different percpu section, where all the elements in this new section will be cacheline aligned(both at the start, aswell as end)

Quoted 3 lines · Suresh B

yes, we were planning to move this to a different percpu section, where all the elements in this new section will be cacheline aligned(both at the start, aswell as end)

I would not call this a per cpu area. It is used by multiple cpus it seems.

But for 0.5%? on what benchmark? Is is really worth it?

Quoted 2 lines · William Lee Irwin III

Mark the runqueues ____cacheline_aligned_in_smp to avoid false sharing.

False sharing for a per cpu data structure? Are we updating that structure from other processors?

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

Quoted 5 lines · Ingo Molnar

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:

effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)

If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:

expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

Calculating p->avg_cpu_per_cycle costs one add, one multiply and one shift right per scheduling cycle of the task. An additional cost is that you need a shift right to get the nanosecond value from value stored in the task struct. (i.e. the above code is simplified to give the general idea). The average would be number of cycles based rather than time based and (happily) this simplifies the calculations.

If the expected time to get onto the CPU (i.e. expected_wait plus the current time) for p is earlier than the equivalent time for the currently running task then preemption of that task would be justified.

Quoted 22 lines · Peter Williams

Quoted 4 lines · Ingo Molnar

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:

effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)

If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:

expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

Quoted 3 lines

Calculating p->avg_cpu_per_cycle costs one add, one multiply and one shift right per scheduling cycle of the task. An additional cost is that you need a shift right to get the nanosecond value from value stored in the task struct. (i.e. the above code is simplified to give the general idea). The average would be number of cycles based rather than time based and (happily) this simplifies the calculations.

If the expected time to get onto the CPU (i.e. expected_wait plus the current time) for p is earlier than the equivalent time for the currently running task then preemption of that task would be justified.

I 100% agree on this method because I came to nearly the same conclusion on paper about 1 year ago. What I'd like to add is that the expected wake up time is not the most precise criterion for fairness.

The expected completion
time is better. When you have one task t1 which is expected to run for T1 nanosecs and another task t2 which is expected to run for T2, what is important for the user for fairness is when the task completes its work. If t1 should wake up at time W1 and t2 at W2, then the list should be ordered by comparing W1+T1 and W2+T2.

What I like with this method is that it remains fair with nice tasks because because in order to renice a task tN, you just have to change TN, and if it has to run shorter, it can be executed before CPU hogs and stay there for a very short time.

Also, I found that if we want to respect interactivity, we must conserve a credit for each task.

It is a bounded amount of CPU time left to be used. When
the task t3 has the right to use T3 nsecs, and wakes up at W3, if it does not spend T3 nsec on the CPU, but only N3<T3, then we have a credit C3 computed like this :

C3 = MAX(MAX_CREDIT, C3 + T3 - N3)

And if a CPU hog uses more than its assigned time slice due to scheduler resolution, then C3 can become negative (and bounded too) :

C3 = MAX(MIN_CREDIT, C3 + T3 - N3)

Now how is the credit used ? Simple: the credit is a part of a timeslice, so it's systematically added to the computed timeslice when ordering the tasks. So we indeed order tasks t1 and t2 by W1+T1+C1 and W2+T2+C2.

It means that an interactive task which has not eaten all of timeslice will accumulate time credit have great chances of being able to run before others if it wakes up again, and even use slightly more CPU time than others if it has not used it before. Conversely, if a task eats too much CPU time, it will be punished and wait longer than others, and run less, to compensate for the advance it has taken.

Also, what I like with this method is that it can correctly handle the fork/exit storms which quickly change the per-task allocated CPU time. Upon fork() or exit(), it should not be too hard to readjust Tx and Cx for each task and reorder them according to their new completion time.

I've not found a way to include a variable nr_running in the tree and order the tasks according to an external variable, hence the need to rescan the tree upon fork/exit for maximum precision. That's where I stopped working on those ideas. If someone knows how to order the tree by (Wx+(Tx+Cx)/nr_running) with nr_running which can change at any time but which is common for everyone in the tree, that would be great.

Quoted 21 lines · Willy Tarreau

Quoted 20 lines · Peter Williams

Quoted 2 lines · Ingo Molnar

- bugfix: use constant offset factor for nice levels instead of
sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:

effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)

If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:

expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

Quoted 7 lines

Quoted 3 lines

Calculating p->avg_cpu_per_cycle costs one add, one multiply and one shift right per scheduling cycle of the task. An additional cost is that you need a shift right to get the nanosecond value from value stored in the task struct. (i.e. the above code is simplified to give the general idea). The average would be number of cycles based rather than time based and (happily) this simplifies the calculations.

If the expected time to get onto the CPU (i.e. expected_wait plus the current time) for p is earlier than the equivalent time for the currently running task then preemption of that task would be justified.

I 100% agree on this method because I came to nearly the same conclusion on paper about 1 year ago. What I'd like to add is that the expected wake up time is not the most precise criterion for fairness.

It's not the expected wake up time being computed. It's the expected time that the task is selected to run after being put on the queue (either as a result of waking or being pre-empted).

I think that your comments below are mainly invalid because of this understanding.

Quoted 6 lines

The expected completion
time is better. When you have one task t1 which is expected to run for T1 nanosecs and another task t2 which is expected to run for T2, what is important for the user for fairness is when the task completes its work. If t1 should wake up at time W1 and t2 at W2, then the list should be ordered by comparing W1+T1 and W2+T2.

This is a point where misunderstanding results in a wrong conclusion. However, the notion of expected completion time is useful. I'd calculate the expected completion time for the task as it goes on to the CPU and if while it is running a new task is queued whose expected "on CPU" time is before the current task's expected end time you can think about preempting when the new tasks "on CPU" task arrives -- how hard/easy this would be to implement is moot.

Quoted 8 lines

What I like with this method is that it remains fair with nice tasks because because in order to renice a task tN, you just have to change TN, and if it has to run shorter, it can be executed before CPU hogs and stay there for a very short time.

Also, I found that if we want to respect interactivity, we must conserve a credit for each task.

This is one point where the misunderstanding results in an invalid conclusion. There is no need for credits as the use of the average time on CPU each cycle makes the necessary corrections that credits would be used to address.

Quoted 12 lines

It is a bounded amount of CPU time left to be used. When
the task t3 has the right to use T3 nsecs, and wakes up at W3, if it does not spend T3 nsec on the CPU, but only N3<T3, then we have a credit C3 computed like this :

C3 = MAX(MAX_CREDIT, C3 + T3 - N3)

And if a CPU hog uses more than its assigned time slice due to scheduler resolution, then C3 can become negative (and bounded too) :

C3 = MAX(MIN_CREDIT, C3 + T3 - N3)

Quoted 3 lines

Now how is the credit used ? Simple: the credit is a part of a timeslice, so it's systematically added to the computed timeslice when ordering the tasks. So we indeed order tasks t1 and t2 by W1+T1+C1 and W2+T2+C2.

I think this is overcomplicating matters.

However, some compensating credit might be in order for tasks that get pre-empted e.g. base their next expected "on CPU" time on the difference between their average on CPU time and they amount they got to use before they were pre-empted.

Quoted 55 lines · Willy Tarreau

Quoted 53 lines · Peter Williams

Quoted 4 lines · Ingo Molnar

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */
p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:

effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)

If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:

expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

Calculating p->avg_cpu_per_cycle costs one add, one multiply and one shift right per scheduling cycle of the task. An additional cost is that you need a shift right to get the nanosecond value from value stored in the task struct. (i.e. the above code is simplified to give the general idea). The average would be number of cycles based rather than time based and (happily) this simplifies the calculations.

If the expected time to get onto the CPU (i.e. expected_wait plus the current time) for p is earlier than the equivalent time for the currently running task then preemption of that task would be justified.

Quoted 4 lines

I 100% agree on this method because I came to nearly the same conclusion on paper about 1 year ago. What I'd like to add is that the expected wake up time
is not the most precise criterion for fairness.

It's not the expected wake up time being computed. It's the expected time that the task is selected to run after being put on the queue (either as a result of waking or being pre-empted).

In practice, it might be prudent to use the idea of maximum expected "on CPU" time instead of the average (especially if you're going to use this for triggering pre-emption).

This would be the average plus two or
three time the standard deviation and has the down side that you have to calculate the standard deviation and that means a square root (of course we could use some less mathematically rigorous metric to approximate the standard deviation).

The advantage would be that streamer type programs
such as audio/video applications would have very small standard deviations and would hence get earlier expected "on CPU" times than other tasks with similar averages but more random distribution.

Quoted 4 lines

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea [...]

[...] and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

I appreciate that the notion of basing the expected wait on the task's average cpu use per scheduling cycle is counter intuitive but I believe that (if you think about it) you'll see that it actually makes sense.

Quoted 5 lines · Peter Williams

Quoted 4 lines

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea [...]

yes, that's exactly the main idea behind CFS, and thanks for the compliment :)

Under this concept the scheduler never really has to guess: every scheduler decision derives straight from the relatively simple one-sentence (!) scheduling concept outlined above. Everything that tasks 'get' is something they 'earned' before and all the scheduler does are micro-decisions based on math with the nanosec-granularity values. Both the rbtree and nanosec accounting are a straight consequence of this too: they are the tools that allow the implementation of this concept in the highest-quality way. It's certainly a very exciting experiment to me and the feedback 'from the field' is very promising so far.

Quoted 4 lines

[...] and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

Quoted 1 line

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

yes. rq->nr_running is really just a first-level approximation of rq->raw_weighted_load. I concentrated on the 'nice 0' case initially.

Quoted 1 line

I appreciate that the notion of basing the expected wait on the task's average cpu use per scheduling cycle is counter intuitive but I believe that (if you think about it) you'll see that it actually makes sense.

hm. So far i tried to not do any statistical approach anywhere: the p->wait_runtime metric (which drives the task ordering) is in essence an absolutely precise 'integral' of the 'expected runtimes' that the task observes and hence is a precise "load-average as observed by the task"

in itself. Every time we base some metric on an average value we introduce noise into the system.

i definitely agree with your suggestion that CFS should use a nice-scaled metric for 'load' instead of the current rq->nr_running, but regarding the basic calculations i'd rather lean towards using rq->raw_weighted_load. Hm?

your suggestion concentrates on the following scenario: if a task happens to schedule in an 'unlucky' way and happens to hit a busy period while there are many idle periods. Unless i misunderstood your suggestion, that is the main intention behind it, correct?

Quoted 15 lines · Ingo Molnar

Quoted 4 lines · Peter Williams

Quoted 3 lines

- bugfix: use constant offset factor for nice levels instead of sched_granularity_ns. Thus nice levels work even if someone sets
sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea [...]

yes, that's exactly the main idea behind CFS, and thanks for the compliment :)

Under this concept the scheduler never really has to guess: every scheduler decision derives straight from the relatively simple one-sentence (!) scheduling concept outlined above. Everything that tasks 'get' is something they 'earned' before and all the scheduler does are micro-decisions based on math with the nanosec-granularity values. Both the rbtree and nanosec accounting are a straight consequence of this too: they are the tools that allow the implementation of this concept in the highest-quality way. It's certainly a very exciting experiment to me and the feedback 'from the field' is very promising so far.

Quoted 4 lines

[...] and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

Quoted 7 lines

Quoted 1 line

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

yes. rq->nr_running is really just a first-level approximation of rq->raw_weighted_load. I concentrated on the 'nice 0' case initially.

Quoted 1 line

I appreciate that the notion of basing the expected wait on the task's average cpu use per scheduling cycle is counter intuitive but I believe that (if you think about it) you'll see that it actually makes sense.

hm. So far i tried to not do any statistical approach anywhere: the p->wait_runtime metric (which drives the task ordering) is in essence an absolutely precise 'integral' of the 'expected runtimes' that the task observes and hence is a precise "load-average as observed by the task"

To me this is statistics :-)

Quoted 3 lines

in itself. Every time we base some metric on an average value we introduce noise into the system.

i definitely agree with your suggestion that CFS should use a nice-scaled metric for 'load' instead of the current rq->nr_running, but regarding the basic calculations i'd rather lean towards using rq->raw_weighted_load. Hm?

This can result in jerkiness (in my experience) but using the smoothed version is certainly something that can be tried later rather than sooner. Perhaps just something to bear in mind as a solution to "jerkiness" if it manifests.

Quoted 2 lines

your suggestion concentrates on the following scenario: if a task happens to schedule in an 'unlucky' way and happens to hit a busy period while there are many idle periods. Unless i misunderstood your suggestion, that is the main intention behind it, correct?

You misunderstand (that's one of my other schedulers :-)). This one's based on the premise that if everything happens as the task expects it will get the amount of CPU bandwidth (over this short period) that it's entitled to. In reality, sometimes it will get more and sometimes less but on average it should get what it deserves. E.g. If you had two tasks with equal nice and both had demands of 90% of a CPU you'd expect them each to get about half of the CPU bandwidth. Now suppose that one of them uses 5ms of CPU each time it got onto the CPU and the other uses 10ms. If these two tasks just round robin with each other the likely outcome is that the one with the 10ms bursts will get twice as much CPU as the other but my proposed method should prevent and cause them to get roughly the same amount of CPU. (I believe this was a scenario that caused problems with O(1) and required a fix at some stage?)

BTW this has the advantage that the decay rate used in calculating the task's statistics can be used to control how quickly the scheduler reacts to changes in the task's behaviour.

Quoted 4 lines · Peter Williams

Quoted 1 line · Ingo Molnar

your suggestion concentrates on the following scenario: if a task happens to schedule in an 'unlucky' way and happens to hit a busy period while there are many idle periods. Unless i misunderstood your suggestion, that is the main intention behind it, correct?

You misunderstand (that's one of my other schedulers :-)). This one's based on the premise that if everything happens as the task expects it will get the amount of CPU bandwidth (over this short period) that it's entitled to. In reality, sometimes it will get more and sometimes less but on average it should get what it deserves. E.g. If you had two tasks with equal nice and both had demands of 90% of a CPU you'd expect them each to get about half of the CPU bandwidth. Now suppose that one of them uses 5ms of CPU each time it got onto the CPU and the other uses 10ms. If these two tasks just round robin with each other the likely outcome is that the one with the 10ms bursts will get twice as much CPU as the other but my proposed method should prevent and cause them to get roughly the same amount of CPU. (I believe this was a scenario that caused problems with O(1) and required a fix at some stage?)

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.
rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:
effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load) If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:
expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

I appreciate that the notion of basing the expected wait on the task's average cpu use per scheduling cycle is counter intuitive but I believe that (if you think about it) you'll see that it actually makes sense.

Quoted 1 line · Peter Williams

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

Hmm. Let me take a look...

Quoted 3 lines · Peter Williams

First suppose we have the following metrics available in addition to what's already provided. rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

I'm suspicious of mean service times not paired with mean inter-arrival times.

On Fri, Apr 20, 2007 at 10:10:45AM +1000, Peter Williams wrote:

Quoted 1 line

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

I went and looked up priority queueing queueing theory garbage and re-derived various things I needed. The basics check out. Probably no one cares that I checked.

Quoted 4 lines · Peter Williams

We can then define:
effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)
If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:
expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

This doesn't look right, probably because the scaling factor of p->avg_cpu_per_cycle is the reciprocal of its additive contribution to the ->avg_weight_load as opposed to a direct estimate of its initial delay or waiting time before completing its current requested service.

p->load_weight/effective_weighted_load more properly represents an entitlement to CPU bandwidth.

	p->avg_cpu_per_cycle/(p->load_weight/effective_weighted_load)

would be more like the expected time spent on the runqueue

(whether
waiting to run or actually running) for a time interval spent in a runnable state and the expected time runnable and waiting to run in such an interval would be

	p->avg_cpu_per_cycle*(1-effective_weighted_load/p->load_weight),

Neither represents the initial delay between entering the runqeueue and first acquiring the CPU, but that's a bit hard to figure out without deciding the scheduling policy up-front anyway.

This essentially doesn't look correct because while you want to enforce the CPU bandwidth allocation, this doesn't have much to do with that apart from the CPU bandwidth appearing as a term. It's more properly a rate of service as opposed to a time at which anything should happen or a number useful for predicting such. When service should begin more properly depends on the other tasks in the system and a number of other decisions that are part of the scheduling policy.

If you want to choose a "quasi-inter-arrival time" to achieve the specified CPU bandwidth allocation, this would be it, but to use that to actually enforce the CPU bandwidth allocation, you would need to take into account the genuine inter-arrival time to choose an actual time for service to begin. In other words, this should be a quota for the task to have waited. If it's not waited long enough, then it should be delayed by the difference to achieve the inter-arrival time you're trying to enforce. If it's waited longer, it should be executed sooner modulo other constraints, and perhaps even credited for future scheduling cycles.

In order to partially avoid underallocating CPU bandwidth to p, one should track the time last spent sleeping and do the following:

	last_sleep = now - p->last_went_to_sleep;
	wait = p->avg_cpu_per_cycle*effective_weighted_load/p->load_weight;
	wait = wait > last_sleep ? wait - last_sleep : 0;

By and large the scheduler can deterministically choose waits on the runqueue but it doesn't actually do that. Some additional corrections for delays beyond those decided up-front while on the runqueue or getting scheduled early on the runqueue may also help, though I'm not as interested in them as I am the one for sleep:

	last_wait = now - p->last_taken_off_the_cpu;
	wait = p->avg_cpu_per_cycle*effective_weighted_load/p->load_weight;
	if (wait > last_wait) /* didn't wait long enough? */
		wait += wait - last_wait; /* wait the difference longer */
	else if (wait < last_wait) /* waited too long? */
		/* wait less to make up the difference */
		wait -= wait > last_wait - wait ? last_wait - wait : wait;

Where ->last_taken_off_the_cpu represents the time the task was last taken off the CPU for whatever reason (this may need to be done differently to handle time variables).

In order to do better, longer-term history is required,

but it can't be
a truly infinite history.

To attempt to maintain an infinite history of
bandwidth underutilization to be credited too far in the future would enable potentially long-term overutilization when such credits are cashed en masse for a sustained period of time. At some point you have to say "use it or lose it;" over a shorter period of time some smoothing is still admissible and even desirable.

One might also consider debits owing to non-preemptibility or other sorts of cpu bandwidth overutilization with similar caveats. A half- life to an otherwise infinite history of credits and/or debits specified in absolute time may be appropriate, though it's not quite as computationally cheap as the above. The accounting for these credits and debits would take the place of ->last_taken_off_the_cpu above.

Another attack on the problem of CPU bandwidth misallocation would be to further credit or debit the task according to the ratio of actual CPU bandwidth to allocated CPU bandwidth in order to compensate for prior failures to enforce the allocation.

Unfortunately, the result
of scaling the artificial inter-arrival time in the obvious way is degenerate (independent of priority) so it can't be done that simply. Perhaps it could be used solely to adjust the credit and debit history contribution to the quasi-inter-arrival time or the difference used somehow, but I don't care to make more complex proposals than the first-order correction above (if it's even worthy of being called a proposal or a correction) for either this or a time-decaying credit and debit history or even debit accounting at all.

I'd be happy enough to see the correction term to subtract out sleeping time (i.e. the code snippet with last_sleep).

The rest and/or stronger
attempts to factor in sleeping time or bandwidth misallocation I don't consider so significant, at least not without some demonstration there is CPU bandwidth misallocation happening.

Quoted 1 line · Peter Williams

I appreciate that the notion of basing the expected wait on the task's average cpu use per scheduling cycle is counter intuitive but I believe that (if you think about it) you'll see that it actually makes sense.

I don't know. It sounds rather standard to me.

Quoted 7 lines

This essentially doesn't look correct because while you want to enforce the CPU bandwidth allocation, this doesn't have much to do with that apart from the CPU bandwidth appearing as a term. It's more properly a rate of service as opposed to a time at which anything should happen or a number useful for predicting such. When service should begin more properly depends on the other tasks in the system and a number of other decisions that are part of the scheduling policy.

This model takes all of those into consideration. The idea is not just to predict but to use the calculated time to decide when to boot the current process of the CPU (if it doesn't leave voluntarily) and put this one on. This more or less removes the need to give each task a predetermined chunk of CPU when they go on to the CPU. This should, in

general, reduce the number context switches as tasks get to run until they've finished what they're doing or another task becomes higher priority rather than being booted off after an arbitrary time interval.
(If this ever gets tried it will be interesting to see if this
prediction comes true.)
BTW Even if Ingo doesn't choose to try this model, I'll probably make a patch (way in the future after Ingo's changes are settled) to try it out myself.

Quoted 10 lines

If you want to choose a "quasi-inter-arrival time" to achieve the specified CPU bandwidth allocation, this would be it, but to use that to actually enforce the CPU bandwidth allocation, you would need to take into account the genuine inter-arrival time to choose an actual time for service to begin. In other words, this should be a quota for the task to have waited. If it's not waited long enough, then it should be delayed by the difference to achieve the inter-arrival time you're trying to enforce. If it's waited longer, it should be executed sooner modulo other constraints, and perhaps even credited for future scheduling cycles.

The idea isn't to enforce the bandwidth entitlement to the extent of throttling tasks if they exceed their entitlement and there's no other tasks ready to use the CPU. This is mainly because the bandwidth entitlement isn't fixed -- it's changing constantly as the number and type of runnable tasks changes.

Quoted 2 lines

In order to partially avoid underallocating CPU bandwidth to p, one should track the time last spent sleeping and do the following:

Yes I made a mistake in omitting to take into account sleep interval. See another e-mail to Ingo correcting this problem.

Quoted 1 line

In order to do better, longer-term history is required,

The half life of the Kalman filter (roughly equivalent to a running average) used to calculate the averages determines how much history is taken into account. It could be made configurable (at least, until enough real life experience was available to decide on the best value to use).

Quoted 6 lines

To attempt to maintain an infinite history of
bandwidth underutilization to be credited too far in the future would enable potentially long-term overutilization when such credits are cashed en masse for a sustained period of time. At some point you have to say "use it or lose it;" over a shorter period of time some smoothing is still admissible and even desirable.

Yes, that's why I suggest a running average over the last few scheduling cycles for the task. But thinking about it some more I'm now not so sure. The lack of apparent "smoothness" when I've done this sort of thing with raw rather than smooth data (in modifications to the current dynamic priority based scheduler model) is usually noticed by running top and seeing wildly fluctuating dynamic priorities. I'm not sure that the actual responsiveness of the system reflects this. So I'm now willing to reserve my judgement on this issue.

Quoted 6 lines

One might also consider debits owing to non-preemptibility or other sorts of cpu bandwidth overutilization with similar caveats. A half- life to an otherwise infinite history of credits and/or debits specified in absolute time may be appropriate, though it's not quite as computationally cheap as the above. The accounting for these credits and debits would take the place of ->last_taken_off_the_cpu above.

Credits shouldn't be necessary with this model if, instead of using the average "on CPU" time per cycle for a pre-empted task when requeuing it, you use the time period that it was "an CPU" before it was booted off as this should compensate it correctly.

Quoted 4 lines

Another attack on the problem of CPU bandwidth misallocation would be to further credit or debit the task according to the ratio of actual CPU bandwidth to allocated CPU bandwidth in order to compensate for prior failures to enforce the allocation.

The fact that the allocated CPU bandwidth is changing continuously makes this not a good idea. On a system where allocations were made directly rather being a side effect of "nice" and the number of runnable processes it might be the way to go.

Quoted 4 lines

The rest and/or stronger
attempts to factor in sleeping time or bandwidth misallocation I don't consider so significant, at least not without some demonstration there is CPU bandwidth misallocation happening.

Quoted 1 line

I don't know. It sounds rather standard to me.

That's good to hear.
I also think that (as Ingo would probably prefer) that this mechanism might work without using averages i.e. just use the last "on CPU" time.
If it does work it would have the advantage of being impervious to the
possible bad effects of CPU speed changes on those systems where this is a feature. When using averages, I think that special consideration would need to be made for variable cpu speeds -- probably not that difficult but additional overhead anyway.

I've been giving some thought into a mechanism for pre-empting the current task when another task's expected "on CPU" time arrives. I think that it would be sufficient for scheduler_tick() to compare the current time (via sched_clock() or whatever) with the "on CPU" for the next task on the queue and initiation pre-emption if it's later than that time. This increases the granularity a little but is compensated for by the fact it will help with the situation where more than one task on the queue has the same expected "on CPU" time in that each of them would get at least a tick (if they needed it).

If some form of precise timer was used (instead) to trigger pre-emption then, where there is more than one task with the same expected "on CPU" time, only the last would get any CPU (and that's only the case if some infinite loop doesn't get created).

Quoted 7 lines · William Lee Irwin III

Quoted 7 lines

This essentially doesn't look correct because while you want to enforce the CPU bandwidth allocation, this doesn't have much to do with that apart from the CPU bandwidth appearing as a term. It's more properly a rate of service as opposed to a time at which anything should happen or a number useful for predicting such. When service should begin more properly depends on the other tasks in the system and a number of other decisions that are part of the scheduling policy.

Quoted 4 lines · Peter Williams

This model takes all of those into consideration. The idea is not just to predict but to use the calculated time to decide when to boot the current process of the CPU (if it doesn't leave voluntarily) and put this one on. This more or less removes the need to give each task a predetermined chunk of CPU when they go on to the CPU. This should, in general, reduce the number context switches as tasks get to run until they've finished what they're doing or another task becomes higher priority rather than being booted off after an arbitrary time interval.
(If this ever gets tried it will be interesting to see if this
prediction comes true.)
BTW Even if Ingo doesn't choose to try this model, I'll probably make a patch (way in the future after Ingo's changes are settled) to try it out myself.

I think I smoked out what you were doing.

Quoted 10 lines · William Lee Irwin III

Quoted 10 lines

If you want to choose a "quasi-inter-arrival time" to achieve the specified CPU bandwidth allocation, this would be it, but to use that to actually enforce the CPU bandwidth allocation, you would need to take into account the genuine inter-arrival time to choose an actual time for service to begin. In other words, this should be a quota for the task to have waited. If it's not waited long enough, then it should be delayed by the difference to achieve the inter-arrival time you're trying to enforce. If it's waited longer, it should be executed sooner modulo other constraints, and perhaps even credited for future scheduling cycles.

Quoted 1 line · Peter Williams

The idea isn't to enforce the bandwidth entitlement to the extent of throttling tasks if they exceed their entitlement and there's no other tasks ready to use the CPU. This is mainly because the bandwidth entitlement isn't fixed -- it's changing constantly as the number and type of runnable tasks changes.

Well, a little hysteresis will end up throttling in such a manner anyway as a side-effect,

or you'll get anomalies. Say two tasks with
equal entitlements compete, where one sleeps for 1/3 of the time and the other is fully CPU-bound. If only the times when they're in direct competition are split 50/50, then the CPU-bound task gets 2/3 and the sleeper 1/3, which is not the intended effect. I don't believe this model will be very vulnerable to it, though.

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

In order to partially avoid underallocating CPU bandwidth to p, one should track the time last spent sleeping and do the following:

Quoted 1 line · Peter Williams

Yes I made a mistake in omitting to take into account sleep interval. See another e-mail to Ingo correcting this problem.

I took it to be less trivial of an error than it was. No big deal.

Quoted 1 line · William Lee Irwin III

Quoted 1 line

In order to do better, longer-term history is required,

Quoted 1 line · Peter Williams

The half life of the Kalman filter (roughly equivalent to a running average) used to calculate the averages determines how much history is taken into account. It could be made configurable (at least, until enough real life experience was available to decide on the best value to use).

A Kalman filter would do better than a running average. I'm all for it.

Quoted 6 lines · William Lee Irwin III

Quoted 6 lines

To attempt to maintain an infinite history of
bandwidth underutilization to be credited too far in the future would enable potentially long-term overutilization when such credits are cashed en masse for a sustained period of time. At some point you have to say "use it or lose it;" over a shorter period of time some smoothing is still admissible and even desirable.

Quoted 1 line · Peter Williams

Yes, that's why I suggest a running average over the last few scheduling cycles for the task. But thinking about it some more I'm now not so sure. The lack of apparent "smoothness" when I've done this sort of thing with raw rather than smooth data (in modifications to the current dynamic priority based scheduler model) is usually noticed by running top and seeing wildly fluctuating dynamic priorities. I'm not sure that the actual responsiveness of the system reflects this. So I'm now willing to reserve my judgement on this issue.

I'm thinking smoothing should be over a relatively short period of time, probably shorter than human reflexes can discern.

Quoted 6 lines · William Lee Irwin III

Quoted 6 lines

One might also consider debits owing to non-preemptibility or other sorts of cpu bandwidth overutilization with similar caveats. A half- life to an otherwise infinite history of credits and/or debits specified in absolute time may be appropriate, though it's not quite as computationally cheap as the above. The accounting for these credits and debits would take the place of ->last_taken_off_the_cpu above.

Quoted 1 line · Peter Williams

Credits shouldn't be necessary with this model if, instead of using the average "on CPU" time per cycle for a pre-empted task when requeuing it, you use the time period that it was "an CPU" before it was booted off as this should compensate it correctly.

That was all about trying to do more in the vein of CPU bandwidth allocation enforcement. It's not the only attack on the problem, and may not even be a desirable one.

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

Another attack on the problem of CPU bandwidth misallocation would be to further credit or debit the task according to the ratio of actual CPU bandwidth to allocated CPU bandwidth in order to compensate for prior failures to enforce the allocation.

Quoted 1 line · Peter Williams

The fact that the allocated CPU bandwidth is changing continuously makes this not a good idea. On a system where allocations were made directly rather being a side effect of "nice" and the number of runnable processes it might be the way to go.

Where it changes continuously the intended effect is some hysteresis. I'm thinking of the CPU-bound task vs. the task that sleeps 1/3 of the time and similar such cases. Interestingly, cfs seems to get the intended allocation by maintaining an effectively infinite history. This is another reason I think it's important to strive for the CPU bandwidth allocation "correctness;" it's already been accomplished in some respects, albeit without relative prioritization.

Maybe a good test for whether an extension for relative prioritization works would be to make the load weights for each nice level configurable via /proc/ and then see if the algorithm successfully allocates shares of CPU bandwidth in various cases accordingly.

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

The rest and/or stronger
attempts to factor in sleeping time or bandwidth misallocation I don't consider so significant, at least not without some demonstration there is CPU bandwidth misallocation happening.

Right here I sort of downplayed trying too hard to enforce things, at least computationally.

Quoted 1 line · William Lee Irwin III

Quoted 1 line

I don't know. It sounds rather standard to me.

On Sat, Apr 21, 2007 at 10:23:07AM +1000, Peter Williams wrote:

Quoted 4 lines

That's good to hear.
I also think that (as Ingo would probably prefer) that this mechanism might work without using averages i.e. just use the last "on CPU" time.
If it does work it would have the advantage of being impervious to the
possible bad effects of CPU speed changes on those systems where this is a feature. When using averages, I think that special consideration would need to be made for variable cpu speeds -- probably not that difficult but additional overhead anyway.

Timekeeping needs adjustments for all that, so the scheduler should just be able to call the timekeeping functions that need to be written for it anyway.

Quoted 1 line

I've been giving some thought into a mechanism for pre-empting the current task when another task's expected "on CPU" time arrives. I think that it would be sufficient for scheduler_tick() to compare the current time (via sched_clock() or whatever) with the "on CPU" for the next task on the queue and initiation pre-emption if it's later than that time. This increases the granularity a little but is compensated for by the fact it will help with the situation where more than one task on the queue has the same expected "on CPU" time in that each of them would get at least a tick (if they needed it).

Another nicety is that you can pretty much predict when you're going to need to preempt, so you can nuke the periodic scheduling interrupt and use a one-shot timer for whenever the next preemption is meant to occur. This nets power savings and less interrupt overhead for userspace.

Quoted 1 line

If some form of precise timer was used (instead) to trigger pre-emption then, where there is more than one task with the same expected "on CPU" time, only the last would get any CPU (and that's only the case if some infinite loop doesn't get created).

I think you can check for this and adjust their on-cpu times in various ways and choose what order to run them in. I think it'd end up something of a missed deadline policy.

Quoted 4 lines · William Lee Irwin III

William Lee Irwin III wrote:

Quoted 1 line · Peter Williams

If some form of precise timer was used (instead) to trigger pre-emption then, where there is more than one task with the same expected "on CPU" time, only the last would get any CPU (and that's only the case if some infinite loop doesn't get created).

Quoted 3 lines

I think you can check for this and adjust their on-cpu times in various ways and choose what order to run them in. I think it'd end up something of a missed deadline policy.

Arguably the latest one should go first as its estimate is more likely to be correct being based on more recent info i.e. the other's estimates would be based on less runnable tasks and be optimistic. This would involve pushing them down the queue and pushing items already on the queue downwards is likely to be expensive. Which is why I prefer the less elegant solution of the periodical interrupt.

Of course, one solution might be to just add the adjustment to the key time on all tasks on the queue?

I retract this suggestion as it's a very bad idea. It introduces the possibility of starvation via the poor sods at the bottom of the queue having their "on CPU" forever postponed and we all know that even the smallest possibility of starvation will eventually cause problems.

I think there should be a rule: Once a task is on the queue its "on CPU" time is immutable.

In practice they can starve a bit when one renices thousands of tasks, so i was thinking about the following special-case: to at least make them easily killable: if a nice 0 task sends a SIGKILL to a nice 19 task then we could 'share' its p->wait_runtime with that nice 19 task and copy the signal sender's nice_offset. This would in essence pass the right to execute over to the killed task, so that it can tear itself down.
This cannot be used to gain an 'unfair advantage' because the signal sender spends its own 'right to execute on the CPU', and because the target task cannot execute any user code anymore when it gets a SIGKILL.

In any case, it is clear that rq->raw_cpu_load should be used instead of rq->nr_running, when calculating the fair clock, but i begin to like the nice_offset solution too in addition of this: it's effective in practice and starvation-free in theory, and most importantly, it's very simple. We could even make the nice offset granularity tunable, just in case anyone wants to weaken (or strengthen) the effectivity of nice levels. What do you think, can you see any obvious (or less obvious) showstoppers with this approach?

I suppose this is a special case of the dreaded priority inversion. What of, say, nice 19 tasks holding fs semaphores and/or mutexes that nice -19 tasks are waiting to acquire? Perhaps rt_mutex should be the default mutex implementation.

Quoted 8 lines

In any case, it is clear that rq->raw_cpu_load should be used instead of rq->nr_running, when calculating the fair clock, but i begin to like the nice_offset solution too in addition of this: it's effective in practice and starvation-free in theory, and most importantly, it's very simple. We could even make the nice offset granularity tunable, just in case anyone wants to weaken (or strengthen) the effectivity of nice levels. What do you think, can you see any obvious (or less obvious) showstoppers with this approach?

->nice_offset's semantics are not meaningful to the end user, regardless of whether it's effective. [...]

[...] If there is something to be tuned, it should be relative shares of CPU bandwidth (load_weight) corresponding to each nice level or something else directly observable. The implementation could be ->nice_offset, if it suffices.

Suppose a table of nice weights like the following is tuned via /proc/:

-20 21 0 1
-1 2 19 0.0476

Essentially 1/(n+1) when n >= 0 and 1-n when n < 0.

Quoted 5 lines

Suppose a table of nice weights like the following is tuned via /proc/:
-20 21 0 1
-1 2 19 0.0476
Essentially 1/(n+1) when n >= 0 and 1-n when n < 0.

ok, thanks for thinking about it. I have changed the nice weight in CVSv5-to-be so that it defaults to something pretty close to your
suggestion: the ratio between a nice 0 loop and a nice 19 loop is now set to about 2%. (This something that users requested for some time, the default ~5% is a tad high when running reniced SETI jobs, etc.)

the actual percentage scales almost directly with the nice offset granularity value, but if this should be exposed to users at all, i agree that it would be better to directly expose this as some sort of 'ratio between nice 0 and nice 19 tasks', right? Or some other, more finegrained metric. Percentile is too coarse i think, and using 0.1% units isnt intuitive enough i think. The sysctl handler would then transform that 'human readable' sysctl value into the appropriate internal nice-offset-granularity value (or whatever mechanism the implementation ends up using).

I'd not do this as a per-nice-level thing but as a single value that rescales the whole nice level range at once. That's alot less easy to misconfigure and we've got enough nice levels for users to pick from almost arbitrarily, as long as they have the ability to influence the max.
does this sound mostly OK to you?

Quoted 3 lines · Peter Williams

I retract this suggestion as it's a very bad idea. It introduces the possibility of starvation via the poor sods at the bottom of the queue having their "on CPU" forever postponed and we all know that even the smallest possibility of starvation will eventually cause problems.

I think there should be a rule: Once a task is on the queue its "on CPU" time is immutable.

Yeah, fully agreed. Currently i'm using the simple method of p->nice_offset, which plainly just moves the per nice level areas of the tree far enough apart (by a constant offset) so that lower nice levels rarely interact with higher nice levels. Lower nice levels never truly starve because rq->fair_clock increases deterministically and currently the fair_key values are indeed 'immutable' as you suggest.

In practice they can starve a bit when one renices thousands of tasks, so i was thinking about the following special-case: to at least make them easily killable: if a nice 0 task sends a SIGKILL to a nice 19 task then we could 'share' its p->wait_runtime with that nice 19 task and copy the signal sender's nice_offset. This would in essence pass the right to execute over to the killed task, so that it can tear itself down.

This cannot be used to gain an 'unfair advantage' because the signal sender spends its own 'right to execute on the CPU', and because the target task cannot execute any user code anymore when it gets a SIGKILL.

In any case, it is clear that rq->raw_cpu_load should be used instead of rq->nr_running, when calculating the fair clock, but i begin to like the nice_offset solution too in addition of this: it's effective in practice and starvation-free in theory, and most importantly, it's very simple. We could even make the nice offset granularity tunable, just in case anyone wants to weaken (or strengthen) the effectivity of nice levels. What do you think, can you see any obvious (or less obvious) showstoppers with this approach?

Quoted 10 lines · Ingo Molnar

Quoted 3 lines · Peter Williams

I retract this suggestion as it's a very bad idea. It introduces the possibility of starvation via the poor sods at the bottom of the queue having their "on CPU" forever postponed and we all know that even the smallest possibility of starvation will eventually cause problems.

I think there should be a rule: Once a task is on the queue its "on CPU" time is immutable.

Yeah, fully agreed. Currently i'm using the simple method of p->nice_offset, which plainly just moves the per nice level areas of the tree far enough apart (by a constant offset) so that lower nice levels rarely interact with higher nice levels. Lower nice levels never truly starve because rq->fair_clock increases deterministically and currently the fair_key values are indeed 'immutable' as you suggest.

In practice they can starve a bit when one renices thousands of tasks, so i was thinking about the following special-case: to at least make them easily killable: if a nice 0 task sends a SIGKILL to a nice 19 task then we could 'share' its p->wait_runtime with that nice 19 task and copy the signal sender's nice_offset. This would in essence pass the right to execute over to the killed task, so that it can tear itself down.

Quoted 3 lines

This cannot be used to gain an 'unfair advantage' because the signal sender spends its own 'right to execute on the CPU', and because the target task cannot execute any user code anymore when it gets a SIGKILL.

In any case, it is clear that rq->raw_cpu_load should be used instead of rq->nr_running, when calculating the fair clock, but i begin to like the nice_offset solution too in addition of this: it's effective in practice and starvation-free in theory, and most importantly, it's very simple. We could even make the nice offset granularity tunable, just in case anyone wants to weaken (or strengthen) the effectivity of nice levels. What do you think, can you see any obvious (or less obvious) showstoppers with this approach?

I haven't had a close look at it but from the above description it sounds an order of magnitude more complex than I thought it would be. The idea of different nice levels sounds like a recipe for starvation to me (if it works the way it sounds like it works).

I guess I'll have to spend more time reading the code because I don't seem to be able to make sense of the above description in any way that doesn't say "starvation here we come".

Quoted 3 lines · Ingo Molnar

- bugfix: use constant offset factor for nice levels instead of
sched_granularity_ns. Thus nice levels work even if someone sets sched_granularity_ns to 0. NOTE: nice support is still naive, i'll address the many nice level related suggestions in -v4.

I have a suggestion I'd like to make that addresses both nice and fairness at the same time. As I understand the basic principle behind this scheduler it to work out a time by which a task should make it onto the CPU and then place it into an ordered list (based on this value) of tasks waiting for the CPU. I think that this is a great idea and my suggestion is with regard to a method for working out this time that takes into account both fairness and nice.

First suppose we have the following metrics available in addition to what's already provided.

rq->avg_weight_load /* a running average of the weighted load on the CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p spends on the CPU each scheduling cycle */

where a scheduling cycle for a task starts when it is placed on the queue after waking or being preempted and ends when it is taken off the CPU either voluntarily or after being preempted. So p->avg_cpu_per_cycle is just the average amount of time p spends on the CPU each time it gets on to the CPU. Sorry for the long explanation here but I just wanted to make sure there was no chance that "scheduling cycle" would be construed as some mechanism being imposed on the scheduler.)

We can then define:

effective_weighted_load = max(rq->raw_weighted_load, rq->avg_weighted_load)

If p is just waking (i.e. it's not on the queue and its load_weight is not included in rq->raw_weighted_load) and we need to queue it, we say that the maximum time (in all fairness) that p should have to wait to get onto the CPU is:

expected_wait = p->avg_cpu_per_cycle * effective_weighted_load / p->load_weight

Calculating p->avg_cpu_per_cycle costs one add, one multiply and one shift right per scheduling cycle of the task. An additional cost is that you need a shift right to get the nanosecond value from value stored in the task struct. (i.e. the above code is simplified to give the general idea). The average would be number of cycles based rather than time based and (happily) this simplifies the calculations.

BTW Given that I'm right and dynamic priorities have been dispensed with what do you intend exporting (in their place) to user space for display by top and similar?