Really Simple Really Fair Scheduler
Quoted 15 lines · Ingo Molnar
Your math is fairly simple (and that is _good_, just like CFS's existing math is simple), it can be summed up in essence as (without complicating it with nice-level weighting, for easy understandability):
" use the already existing
p->sum_exec_runtime'task runtime' metric
that CFS maintains, and use that as the key into the rb-tree that selects tasks that should be run next. To handle sleeping tasks: keep a per-rq sum of all runnable task's ->sum_exec_runtime values and start newly woken tasks at the average rq->sum/nr_running value. "Now your patch does not actually do it that way in a clearly discernible manner because lots of changes are intermixed into one big patch.
Quoted 5 lines
( please correct me if i got your math wrong. Your patch does not add
any comments at all to the new code and this slowed down my review and analysis of your patch quite considerably. Lack of comments makes it harder to see the purpose and makes it harder to notice the benefits/tradeoffs involved in each change. )
Roman, as an addendum to my review, please find below a prototype patch i've just written that implements RSRFS (Really Simple Really Fair Scheduler) ontop of CFS. It is intended to demonstrate the essence of the math you have presented via your patch. (it has no nice levels support yet, to make the math really apparent to everyone interested)
It's a truly simple patch:
3 files changed, 30 insertions(+), 23 deletions(-)
and gives good fairness:
$ ./massive_intr 10 10 002510 00000114 002515 00000114 002518 00000114 002514 00000114 002513 00000115 002509 00000115 002517 00000115 002511 00000115 002512 00000115 002516 00000115
Could you please confirm whether the math algorithm you are suggesting is implemented by this patch roughly correctly? (ignoring nice levels, i.e. only considering nice-0 tasks, ignoring rounding issues and Bresenham optimizations, CPU time slicing and other changes.)
Thanks,
Ingo
--- include/linux/sched.h | 1 + kernel/sched.c | 2 ++ kernel/sched_fair.c | 50 +++++++++++++++++++++++++++----------------------- 3 files changed, 30 insertions(+), 23 deletions(-)
include/linux/sched.h +1 -0
@@ -904,6 +904,7 @@ struct sched_entity {u64 exec_start;u64 sum_exec_runtime; +u64 exec_runtime;u64 prev_sum_exec_runtime;u64 wait_start_fair;u64 sleep_start_fair;
kernel/sched.c +2 -0
@@ -183,6 +183,7 @@ struct cfs_rq {s64 fair_clock;u64 exec_clock; +u64 exec_runtime;s64 wait_runtime;u64 sleeper_bonus;unsigned long wait_runtime_overruns, wait_runtime_underruns;
@@ -1586,6 +1587,7 @@ static void __sched_fork(struct task_str { p->se.wait_start_fair =0 ; p->se.exec_start =0 ; + p->se.exec_runtime =0 ; p->se.sum_exec_runtime =0 ; p->se.prev_sum_exec_runtime =0 ; p->se.delta_exec =0 ;
kernel/sched_fair.c +27 -23
105 lines not on this page · raw message
I like this patch since it's really simple. CFS does provide a nice infrastructure to enable new algorithmic changes/extensions. My only concern was the O(log N) complexity under heavy load, but I'm willing to agree that it's OK in the common case. Some comments on the code:
Quoted 27 lines · Ingo Molnar
static void
update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se){kernel/sched_fair.c +1
-1-s64 key; +u64 key;/* * Are we enqueueing a waiting task? (for current taskskernel/sched_fair.c +0
-14@@ -442,26 +448,7 @@ static void update_stats_enqueue(struct/* * Update the key: */ - key = cfs_rq->fair_clock; - -/* -* Optimize the common nice 0 case: -*/ -if (likely (se->load.weight ==NICE_0_LOAD )) { - key -= se->wait_runtime; - }else { -u64 tmp; - -if (se->wait_runtime <0 ) { - tmp = -se->wait_runtime; - key += (tmp * se->load.inv_weight) >> - (WMULT_SHIFT -NICE_0_SHIFT );
kernel/sched_fair.c static void update_stats_enqueue(struct · line 454
Quoted 10 lines
kernel/sched_fair.c +1
-6- }else { - tmp = se->wait_runtime; - key -= (tmp * se->load.inv_weight) >> - (WMULT_SHIFT -NICE_0_SHIFT ); - } - } + key = se->exec_runtime; se->fair_key = key; }
Should we use the weighted fair clock exec_runtime as the key? This way tasks with larger weights will have their keys incremented more slowly and thus be given more CPU time. This is what other virtual-clock based fair scheduling algorithms commonly do.
Quoted 34 lines
kernel/sched_fair.c +17
-1@@ -583,6 +570,20 @@ static void __enqueue_sleeper(struct cfs cfs_rq->sleeper_bonus += delta_fair; } +/* +* Newly woken tasks are put into the "middle" of all runnable +* task's current runtime: +*/ +static u64 avg_exec_runtime (struct cfs_rq *cfs_rq) +{ +u64 avg_exec_runtime = cfs_rq->exec_runtime; + +if (cfs_rq->nr_running) +do_div (avg_exec_runtime, cfs_rq->nr_running); + +return avg_exec_runtime; +} +static void enqueue_sleeper (struct cfs_rq *cfs_rq,struct sched_entity *se) {struct task_struct *tsk =task_of (se);@@ -640,8 +641,10 @@ enqueue_entity(struct cfs_rq *cfs_rq, st*/ update_curr (cfs_rq); -if (wakeup) +if (wakeup) { + se->exec_runtime =avg_exec_runtime (cfs_rq);enqueue_sleeper (cfs_rq, se); + }update_stats_enqueue (cfs_rq, se);__enqueue_entity (cfs_rq, se);
kernel/sched_fair.c static void task_new_fair(struct rq *rq, · line 1134
Quoted 6 lines
kernel/sched_fair.c +1
-0@@ -1126,6 +1129,7 @@ static void task_new_fair(struct rq *rq,schedstat_add (cfs_rq, wait_runtime, se->wait_runtime); } + se->exec_runtime =avg_exec_runtime (cfs_rq);__enqueue_entity (cfs_rq, se); }
What's the intuition behind avg_exec_runtime? I thought the original CFS approach, i.e., setting a newly arriving task's key to be the current fair clock, adjusted by wait_runtime, was good. It matches other fair queuing algorithms and thus has provably good properties.
tong
Quoted 4 lines · Tong Li
I like this patch since it's really simple. CFS does provide a nice infrastructure to enable new algorithmic changes/extensions. My only concern was the O(log N) complexity under heavy load, but I'm willing to agree that it's OK in the common case. [...]
yeah. Note that just in case i wasnt clear enough: my patch attempts to be an adoption of the core fairness math algorithm Roman suggested - so it is not my idea and i dont want to take credit for it. (if it were to go upstream it would of course carry a prominent "fairness math rewritten by Roman Zippel" credit.)
about O(log N) complexity: the "timeline" nature of the CFS rbtree (which rbtree Roman's patch preserves) guarantees a certain good level of cache locality. We generally insert tasks at the "right side" of the tree and remove them from the "left side" of the tree. (not always of course, but for most workloads) So in practice, on a reasonable CPU, there's no difference to the cachemiss patterns of pure O(1) algorithms. And in terms of cycle overhead, lets consider something really extreme:_one million runnable tasks on a single CPU_ (which is clearly silly and unrealistic), which has a worst-case rbtree depth of ~31. A modern CPU can walk a 31-deep binary tree in the neighborhood of 100 cycles (cached). That makes it comparable to the O(1) scheduler's reliance on the BSF instruction on x86 (which instruction costs a few dozen cycles last i remember). In practice O(log(N)) algorithms are really equivalent to O(1) algorithms. The big thing about the "O(1) scheduler" was that the scheduler it replaced was O(N). Now an O(N) algorithm _does_ hurt.
No doubt, people _will_ play with CFS and will try to implement its timeline data structure using O(1) algorithms (or improved tree algorithms). It's doable and it will certainly be interesting to see the results of such experiments. The rbtree was simply the most natural choice of an already existing, lightweight in-kernel tree data structure. [ It's also used by the MM so continued sanity and performance of that code is guaranteed by the MM hackers ;-) ]
Quoted 11 lines
[...] Some comments on the code:
Quoted 4 lines
kernel/sched_fair.c +1
-0+ key = se->exec_runtime;se->fair_key = key; }Should we use the weighted fair clock
exec_runtimeas the key? This way tasks with larger weights will have their keys incremented more slowly and thus be given more CPU time. This is what other virtual-clock based fair scheduling algorithms commonly do.
yep. The code i posted treats all tasks as nice-0. I suspect by adding a calc_weighted() transformation to the key calculation above we'd get most of the nice level support. (but i havent tried that yet - i was mainly interested in a simple expression of Roman's ideas)
Quoted 8 lines
Quoted 3 lines
(quoted diff) +1
-0+ se->exec_runtime = avg_exec_runtime(cfs_rq);__enqueue_entity(cfs_rq, se); }What's the intuition behind
avg_exec_runtime? I thought the original CFS approach, i.e., setting a newly arriving task's key to be the current fair clock, adjusted bywait_runtime, was good. It matches other fair queuing algorithms and thus has provably good properties.
it's i think what Roman's algorithm does, and i wanted to implement that and only that, to be able to review the effects of a much simpler, yet behaviorally equivalent patch. Perhaps Roman can shed some light on what the thinking behind that average is.
Ingo
Hi,
Quoted 5 lines · Ingo Molnar
Roman, as an addendum to my review, please find below a prototype patch i've just written that implements RSRFS (Really Simple Really Fair Scheduler) ontop of CFS. It is intended to demonstrate the essence of the math you have presented via your patch. (it has no nice levels support yet, to make the math really apparent to everyone interested)
It simplifies the math too much, the nice level weighting is an essential part of the math and without it one can't really understand the problem I'm trying to solve. At http://lkml.org/lkml/2007/9/3/168 I provide an example of the math, which more acurately demonstrates the essential math.
bye, Roman
Quoted 10 lines · Roman Zippel
Hi,
Quoted 5 lines · Ingo Molnar
Roman, as an addendum to my review, please find below a prototype patch i've just written that implements RSRFS (Really Simple Really Fair Scheduler) ontop of CFS. It is intended to demonstrate the essence of the math you have presented via your patch. (it has no nice levels support yet, to make the math really apparent to everyone interested)
Quoted 5 lines
It simplifies the math too much, the nice level weighting is an essential part of the math and without it one can't really understand the problem I'm trying to solve. At http://lkml.org/lkml/2007/9/3/168
I provide an example of the math, which more acurately demonstrates the essential math.
as i mentioned it above, in the first level review i'm mainly interested in your patch's behavior wrt. simple nice-0 tasks, how they run and how they sleep and wake up. Nothing else. Why? That's what 99% of the Linux tasks do after all. So could you please confirm whether that aspect of what i wrote (both in words and in code) is correct?
If this basic model is correct, we can look further. If this basic model is flawed, no amount of weighting, nice level logic, rounding behavior can fix it. I'm sure you agree with that too.
That's why i wrote this prototype, please confirm or deny whether i correctly understood how you intend to handle nice-0 tasks. (From your mails i read a part-acknowledgement of that but i'd like to see a more clear acknowledgement - or please mention any issues if you know about them.) Thanks!
Ingo
Hi,
Quoted 1 line · Ingo Molnar
If this basic model is correct, we can look further.
The basic model is correct insofar I use an absolute time instead of a relative time, but it's not the essence of my math, so I don't quite understand the point of this exercise.
bye, Roman
Quoted 7 lines · Roman Zippel
Quoted 1 line · Ingo Molnar
If this basic model is correct, we can look further.
The basic model is correct insofar I use an absolute time instead of a relative time, but it's not the essence of my math, so I don't quite understand the point of this exercise.
thanks. (and i did not claim nor do i want to claim this to be the essence of your efforts - it is very clear from your mails where your focus is.)
My next question then is about this code of yours in the wakeup path:
+static void
+enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) +{
+ kclock_t min_time;
+
+ verify_queue(cfs_rq, cfs_rq->curr != se, se); + min_time = get_time_avg(cfs_rq) - se->req_weight_inv; + if ((kclock_t)(se->time_norm - min_time) < 0)
+ se->time_norm = min_time;
why do you only use the "min_time" if the pre-sleep time_norm is smaller than the min_time? Here 'min_time' is close to the current average. Shouldnt here the woken up task be set to the average time, like i did it in the crude prototype:
+ se->exec_runtime = avg_exec_runtime(cfs_rq);
(and lets again only consider the special case of only having nice-0 tasks.)
Or is it set in a similar way as my prototype does, and i missed some detail why that branch is there?
Ingo
Hi,
Quoted 7 lines · Ingo Molnar
My next question then is about this code of yours in the wakeup path:
+static void
+enqueue_entity(structcfs_rq*cfs_rq, structsched_entity*se) +{
+kclock_tmin_time;
+
Quoted 7 lines
+ verify_queue(cfs_rq, cfs_rq->curr != se, se); + min_time = get_time_avg(cfs_rq) - se->req_weight_inv; + if ((kclock_t)(se->time_norm - min_time) < 0)+
se->time_norm=min_time;why do you only use the "
min_time" if the pre-sleeptime_normis smaller than themin_time? Here 'min_time' is close to the current average.
It's a variation of the sleeper bonus. Let's assume two running tasks which have been running for 95ms and 105ms and a time slice of 10ms, the average is thus 100ms. If the new task has been sleeping for a while it starts at 90ms, if the task had been running lately it doesn't get this bonus again.
Quoted 4 lines
Shouldnt here the woken up task be set to the average time, like i did it in the crude prototype:
+
se->exec_runtime=avg_exec_runtime(cfs_rq);
That would be equivalent to simply clearing wait_runtime in CFS.
bye, Roman
Quoted 16 lines · Roman Zippel
Hi,
Quoted 12 lines · Ingo Molnar
My next question then is about this code of yours in the wakeup path:
+static void
+enqueue_entity(structcfs_rq*cfs_rq, structsched_entity*se) +{
+kclock_tmin_time;
++ verify_queue(cfs_rq, cfs_rq->curr != se, se); + min_time = get_time_avg(cfs_rq) - se->req_weight_inv; + if ((kclock_t)(se->time_norm - min_time) < 0)+
se->time_norm=min_time;
Quoted 4 lines
Quoted 2 lines
why do you only use the "
min_time" if the pre-sleeptime_normis smaller than themin_time? Here 'min_time' is close to the current average.It's a variation of the sleeper bonus. [...]
hm, where are its effects described in your explanation? Seems like a key item.
Quoted 4 lines
[...] Let's assume two running tasks which have been running for 95ms and 105ms and a time slice of 10ms, the average is thus 100ms. If the new task has been sleeping for a while it starts at 90ms, if the task had been running lately it doesn't get this bonus again.
what happens if there are lots of such tasks? What limits the total bonus?
Quoted 6 lines
Quoted 4 lines
Shouldnt here the woken up task be set to the average time, like i did it in the crude prototype:
+
se->exec_runtime=avg_exec_runtime(cfs_rq);That would be equivalent to simply clearing
wait_runtimein CFS.
so my prototype patch is not an exact map of the nice-0 special-case of your code? Would this be the correct thing then perhaps:
+ se->exec_runtime =
+ max(avg_exec_runtime(cfs_rq), se->exec_runtime);
Or if not, could you suggest a code-line at that place? Thanks,
Ingo
Hi,
Quoted 4 lines · Ingo Molnar
Quoted 1 line
It's a variation of the sleeper bonus. [...]
hm, where are its effects described in your explanation? Seems like a key item.
It has no direct effect on the correctness of the mathematical model, the time is initialized before the time is added to the model. What you're after is the effect on the behaviour, which wasn't my focus, so sorry, I didn't mention it.
Quoted 7 lines
Quoted 4 lines
[...] Let's assume two running tasks which have been running for 95ms and 105ms and a time slice of 10ms, the average is thus 100ms. If the new task has been sleeping for a while it starts at 90ms, if the task had been running lately it doesn't get this bonus again.
what happens if there are lots of such tasks? What limits the total bonus?
Every task gets a little more bonus, but it grows quite slowly, every task gets time_slice/task_cnt more than the previous one (assuming all tasks are started at the same time), so the 10th gets 2.82*time_slice, the 100th gets 5.18*time_slice, the 1000th gets 7.48*time_slice...
I thought about it already and I didn't consider it a serious problem, however it's solvable if needed by keeping the bonus separate:
avg = avg_exec_runtime(cfs_rq); se->time_norm = kclock_max(avg - time_slice, se->time_norm); se->bonus = avg - se->time_norm; cfs_rq->time_sum += avg;
But the bonus also had to be undone when unqueueing the task:
cfs_rq->time_sum -= se->time_norm + bonus;
Review
Quoted 7 lines
Quoted 1 line
That would be equivalent to simply clearing
wait_runtimein CFS.so my prototype patch is not an exact map of the nice-0 special-case of your code? Would this be the correct thing then perhaps:
(quoted diff) +2
-0+ se->exec_runtime = + max(avg_exec_runtime(cfs_rq), se->exec_runtime);
You should substract the desired bonus here from the average as above and evtl. also store the given bonus separately.
bye, Roman
Quoted 9 lines · Roman Zippel
Quoted 4 lines
Quoted 1 line
It's a variation of the sleeper bonus. [...]
hm, where are its effects described in your explanation? Seems like a key item.
It has no direct effect on the correctness of the mathematical model, the time is initialized before the time is added to the model. What you're after is the effect on the behaviour, which wasn't my focus, so sorry, I didn't mention it.
and what about the mirror image problem? Your math assumes that tasks use up their full timeslices, somewhere starting at (12):
| (12) time_norm_app = sum_{t}^{T}(time_norm_{t} * weight_{t}) /
| sum_{t}^{T}(weight_{t})
|
| This produces only a approximate normalized time, but if all
| time_norm_{t} are equal (i.e. all tasks got their share), the result
| is the same, thus the error is only temporary.Quoted 1 line
From here on the reasoning and the math is flawed i believe: it assumes
that tasks use up their timeslices - which is rarely the case.
In practical terms: your code causes unfairness to tasks that sleep when they have used up only a fraction of their slice, when they are in a fairness-deficit. For example consider a task that just waited alot to get on the CPU, and when it finally got there (gathering a fairness deficit of say 9 milliseconds), a hundred microseconds later it sleeps.
The problem is that when it wakes up and gets back on the runqueue your code "forgets" that the task is in "need of fairness" by 9 milliseconds:
the task continues as if its previous starvation didnt happen at all. This effect can cause _far more noise_ and even systematic starvation than any numeric rounding effects could cause. (This could perhaps explain the unfairness Mike reported, and this could perhaps explain the noisy hackbench results i'm seeing with your patch - although i'm not certain about this, i havent looked into those usecases in detail.)
CFS's current math addresses this problem via the use of the fair-clock metric and via ->wait_runtime: that gives us a good idea what happened to the system while the task slept. With your model, that information is not maintained at all, and is not regainable. At the moment i dont see how we could achieve good sleeper behavior with your model, you've over-simplified the scheduler metrics and we've lost essential information.
That's why i'm concentrating on the basic scheduling properties first, without considering nice levels, rounding or optimizations - if that basic model does not fit then a scheduler cannot work. That's also why i've asked for a split-up patch series - it makes it far easier to review and test the code and it makes it far easier to quickly apply the obviously correct bits.
And i'd like to concur with Tong Li's observation that currently CFS is a very generic fair scheduler upon which a multitude of scheduling variants can be built and prototyped (we use a specific one right now, but it's not cast into stone). The 30-lines-changed patch i sent shows this property of CFS pretty well - and it already demonstrates the issues we are talking about here.
Ingo
Hi,
Quoted 1 line · Ingo Molnar
and what about the mirror image problem?
Sorry, I'm not familiar with that in a scheduler context.
Quoted 10 lines
Your math assumes that tasks
use up their full timeslices, somewhere starting at (12):| (12) time_norm_app = sum_{t}^{T}(time_norm_{t} * weight_{t}) / | sum_{t}^{T}(weight_{t}) | | This produces only a approximate normalized time, but if all | time_norm_{t} are equal (i.e. all tasks got their share), the result | is the same, thus the error is only temporary.
Quoted 2 lines
Quoted 1 line
From here on the reasoning and the math is flawed i believe: it assumes
that tasks use up their timeslices - which is rarely the case.
I'm not sure what you're refering to. The remaining math basically only deals with the average calculation and if we're still at your simplified model, then it's largely irrevelant, because the approximation error only comes into effect with different weights. This means for the common case, you can assume my code produces a perfect average.
Quoted 9 lines
In practical terms: your code causes unfairness to tasks that sleep when they have used up only a fraction of their slice, when they are in a fairness-deficit. For example consider a task that just waited alot to get on the CPU, and when it finally got there (gathering a fairness deficit of say 9 milliseconds), a hundred microseconds later it sleeps.
The problem is that when it wakes up and gets back on the runqueue your code "forgets" that the task is in "need of fairness" by 9 milliseconds:
the task continues as if its previous starvation didnt happen at all.
Please put this into more context, e.g. demonstrate how this problem doesn't exist in CFS. My code should largely mirror CFS behaviour with the exception that the bonus maybe isn't as big and this:
if (sysctl_sched_features & SCHED_FEAT_SLEEPER_AVG)
delta_fair = div64_likely32((u64)delta_fair * load,
load + se->load.weight);Quoted 5 lines
This effect can cause
_farmorenoise_and even systematic starvation than any numeric rounding effects could cause. (This could perhaps explain the unfairness Mike reported, and this could perhaps explain the noisy hackbench results i'm seeing with your patch - although i'm not certain about this, i havent looked into those usecases in detail.)
The problem Mike reported looks more like a bug, I'm puzzled why the verify code didn't trigger as the whole thing was pretty much out of sync, so in the next version I'll add a few more checks, but I'm not finished with the hackbench results yet.
Quoted 7 lines
CFS's current math addresses this problem via the use of the fair-clock metric and via ->wait_runtime: that gives us a good idea what happened to the system while the task slept. With your model, that information is not maintained at all, and is not regainable. At the moment i dont see how we could achieve good sleeper behavior with your model, you've over-simplified the scheduler metrics and we've lost essential information.
Please describe this sleeper behaviour, what kind of sleeper do you have in mind exactly? If we take for example interactive tasks, these should be constantly behind other running tasks and thus have an advantage at getting the cpu, i.e. if a task doesn't use up its time slice its runtime value won't advance as much as of other tasks which do use their slice.
bye, Roman