• Uladzislau Rezki's avatar
    sched/fair: Search a task from the tail of the queue · 93824900
    Uladzislau Rezki authored
    As a first step this patch makes cfs_tasks list as MRU one.
    It means, that when a next task is picked to run on physical
    CPU it is moved to the front of the list.
    
    Therefore, 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, i.e. MRU list.
    
    Second, as part of the load balance operation, this approach
    starts detach_tasks()/detach_one_task() from the tail of the
    queue instead of the head, giving some advantages:
    
     - tends to pick a task with highest wait time;
    
     - tasks located in the tail are less likely cache-hot,
       therefore the can_migrate_task() decision is higher.
    
    hackbench illustrates slightly better performance. For example
    doing 1000 samples and 40 groups on i5-3320M CPU, it shows below
    figures:
    
     default: 0.657 avg
     patched: 0.646 avg
    Signed-off-by: default avatarUladzislau Rezki (Sony) <urezki@gmail.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Cc: Kirill Tkhai <tkhai@yandex.ru>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Mike Galbraith <efault@gmx.de>
    Cc: Mike Galbraith <umgwanakikbuti@gmail.com>
    Cc: Nicolas Pitre <nicolas.pitre@linaro.org>
    Cc: Oleg Nesterov <oleg@redhat.com>
    Cc: Oleksiy Avramchenko <oleksiy.avramchenko@sonymobile.com>
    Cc: Paul Turner <pjt@google.com>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Steven Rostedt <rostedt@goodmis.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: Tim Chen <tim.c.chen@linux.intel.com>
    Link: http://lkml.kernel.org/r/20170913102430.8985-2-urezki@gmail.comSigned-off-by: default avatarIngo Molnar <mingo@kernel.org>
    93824900
fair.c 258 KB