Re: [RFC][PATCH]: sched/fair: search a task from the tail of the queue

[Peter Zijlstra]

On Thu, Aug 24, 2017 at 12:44:45PM +0200, Uladzislau Rezki (Sony) wrote:
> From: Uladzislau Rezki <urezki@xxxxxxxxx>
> 
> When a task is enqueued back from a physical CPU to the running
> list it is placed in the beginning of the queue. Thus, the cfs_tasks
> list is more or less sorted (except woken tasks) starting from recently
> given CPU time tasks toward tasks with max wait time in a run-queue.

Hurm... that is only true for short running tasks, the moment you get
things like involuntary preemption that's completely off.

Imagine starting 3 busy-spinning tasks, lets call then A, B and C.

So our cfs_tasks list is ordered: C B A, since C is the last task we
started.

At this point, C might also be the leftmost task, since it has ran
least. But the moment we let A run its full quantum it will become the
rightmost and we'll pick C. Let C run its full quantum and that becomes
the rightmost.

So now we have, in our tree: B A C, while our list is still C B A. No
relation left what so ever.

How, hackbench will be very short running tasks, so the list tends to be
better ordered vs the tree.

That said, functionally it really doesn't matter what way around the
list we iterate for migration, so if this is a win for some, that's
nice. But it would be nice to get more benchmarks ran to see if there is
cases where it hurts.

Another thing you could play with is making pick_next_task_fair() move
the selected task to the front of the list. That way the list becomes a
MRU and picking from the tail always makes sense.