CFS: Add hierarchical tree-based penalty.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Hi,
Quoted 1 line · ----- "Peter Zijlstra
It's customary to CC people who work on the code you patch...
Please take a look at the revised patch I just sent to the list.
Quoted 54 lines · William Pitcock
Quoted 1 line
Inspired by the recent change to BFS by Con Kolivas, this patch
causes
Quoted 4 lines
vruntime to be penalized based on parent depth from their root task group.
I have, for the moment, decided to make it a default feature since
the
Quoted 1 line
design of CFS ensures that broken applications depending on task
enqueue
Quoted 3 lines
behaviour behaving traditionally will continue to work.
My method for applying the penalty is different than that of BFS,
it
Quoted 1 line
divides the vruntime by the number of parents the process has.
Aside from the funny semantic error in your sentence there (every process can, by definition, only have one parent), the patch doesn't look quite right either.
Quoted 13 lines
Signed-off-by William Pitcock <[email protected]>--- include/linux/sched.h | 2 ++ kernel/sched.c | 4 ++++ kernel/sched_fair.c | 8 ++++++++ kernel/sched_features.h | 12 ++++++++++++ 4 files changed, 26 insertions(+), 0 deletions(-)include/linux/sched.h +0
-0include/linux/sched.h struct task_struct { · line 1499
Quoted 6 lines
include/linux/sched.h +2
-0@@ -1494,6 +1494,8 @@ struct task_struct { unsigned long memsw_bytes; /* uncharged mem+swap usage */ } memcg_batch;#endif + +int parent_count; };so
copy_process()will make a child inherit theparent_countfrom the parent.kernel/sched.c void wake_up_new_task(struct task_struct *p,
Quoted 6 lines
include/linux/sched.h +0
-0/* Future-safe accessor for struct task_struct's cpus_allowed. */ kernel/sched.c +0
-0@@ -2621,6 +2621,10 @@ void wake_up_new_task(struct task_struct *p,unsigned long
clone_flags)Quoted 2 lines
kernel/sched.c +0
-0#endif
Quoted 9 lines
kernel/sched.c void wake_up_new_task(struct task_struct *p, · line 2627
Quoted 5 lines
kernel/sched.c +4
-0rq =task_rq_lock (p, &flags); + +if (!(clone_flags &CLONE_THREAD )) + p->parent_count++; +And we increment it for every new !THREAD child, so its basically a task
depth counter, except it doesn't take re-parenting into account.
I renamed it to fork_depth, which is what BFS uses to describe this variable. It may be better to put this in sched_entity, however.
Quoted 13 lines
kernel/sched_fair.c place_entity(struct cfs_rq *cfs_rq, struct
Quoted 9 lines
kernel/sched.c +0
-0activate_task (rq, p,0 );trace_sched_wakeup_new (p,1 );check_preempt_curr (rq, p,WF_FORK );kernel/sched_fair.c +0
-0@@ -737,6 +737,14 @@ place_entity(struct cfs_rq *cfs_rq, struct
sched_entity*se, int initial)Quoted 3 lines
kernel/sched_fair.c +0
-0if (initial &&sched_feat (START_DEBIT )) vruntime +=sched_vslice (cfs_rq, se);
Quoted 7 lines
kernel/sched_fair.c place_entity(struct cfs_rq *cfs_rq, struct · line 742
Quoted 3 lines
kernel/sched_fair.c +3
-0+if (sched_feat (HIERARCHICAL_PENALTY )) { +struct task_struct *tsk =task_of (se); +And here you have a bug,.. there is no guarantee se is actually a task.
Which means you're dereferencing random memory here:
I am now checking this with entity_is_task() in the newest version.
Quoted 17 lines
kernel/sched_fair.c place_entity(struct cfs_rq *cfs_rq, struct · line 745
Quoted 4 lines
kernel/sched_fair.c +3
-0+if (tsk->parent_count >1 ) + vruntime =max_vruntime (vruntime, + vruntime / tsk->parent_count);Aside from the wrap issue, that is a NOP statement.
x / y < x : y > 1, therefore,
max(x, x/y)== x and you wrote, x = x;Furthermore, vruntime here is an absolute measure of service, dividing
that by anything reduces the total amount of service the task received
during its history, doing so for y > 1 means at least halving it, which
again means that you basically end up with:
Quoted 8 lines
se->vruntime = se->vruntime;Due to the final few statements in
place_entity():se->vruntime = max_vruntime(se->vruntime, vruntime);What I think you meant to do was proportionally decrease the relative placement of the new task by the task-depth, or something like that.
Yes, this should be a multiplication I believe, not a divide. My original code had this as a multiplication, not a division, as does the new patch.
However, I think:
vruntime >>= tsk->fork_depth;
would do the job just as well and be faster.
I would be glad to know what you think about this.
William
Quoted 8 lines · William Pitcock
Yes, this should be a multiplication I believe, not a divide. My original code had this as a multiplication, not a division, as does the new patch.
However, I think:
vruntime >>= tsk->fork_depth;would do the job just as well and be faster.
That's still somewhat iffy as explained, vruntime is the absolute service level, multiplying that by 2 (or even more) will utterly upset things.
Imagine two runnable tasks of weight 1, say both have a vruntime of 3 million, seconds (there being two, vruntime will advance at 1/2 wall-time).
Now, suppose you wake a third, it too had a vruntime of around 3 million seconds (it only slept for a little while), if you then multiply that with 2 and place it at 6 mil, it will have to wait for 6 mil seconds before it gets serviced (twice the time of the 3 mil difference in service time between this new and the old tasks).
So, theory says the fair thing to do is place new tasks at the weighted average of the existing tasks, but computing that is expensive, so what we do is place it somewhere near the leftmost task in the tree.
Now, you don't want to push it out too far to the right, otherwise we get starvation issues and people get upset.
So you have to somehow determine a window in which you want to place this task and then vary in that depending on your fork_depth.
Simply manipulating the absolute service levels like you propose isn't going to work.