From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756198AbdJJLFP (ORCPT ); Tue, 10 Oct 2017 07:05:15 -0400 Received: from terminus.zytor.com ([65.50.211.136]:34595 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751420AbdJJLFM (ORCPT ); Tue, 10 Oct 2017 07:05:12 -0400 Date: Tue, 10 Oct 2017 03:58:16 -0700 From: tip-bot for Uladzislau Rezki Message-ID: Cc: hpa@zytor.com, peterz@infradead.org, mingo@kernel.org, tkhai@yandex.ru, umgwanakikbuti@gmail.com, nicolas.pitre@linaro.org, oleksiy.avramchenko@sonymobile.com, tim.c.chen@linux.intel.com, tglx@linutronix.de, pjt@google.com, torvalds@linux-foundation.org, efault@gmx.de, linux-kernel@vger.kernel.org, urezki@gmail.com, rostedt@goodmis.org, oleg@redhat.com Reply-To: tkhai@yandex.ru, mingo@kernel.org, nicolas.pitre@linaro.org, umgwanakikbuti@gmail.com, hpa@zytor.com, peterz@infradead.org, efault@gmx.de, linux-kernel@vger.kernel.org, urezki@gmail.com, torvalds@linux-foundation.org, oleg@redhat.com, rostedt@goodmis.org, oleksiy.avramchenko@sonymobile.com, tim.c.chen@linux.intel.com, pjt@google.com, tglx@linutronix.de In-Reply-To: <20170913102430.8985-2-urezki@gmail.com> References: <20170913102430.8985-2-urezki@gmail.com> To: linux-tip-commits@vger.kernel.org Subject: [tip:sched/core] sched/fair: Search a task from the tail of the queue Git-Commit-ID: 93824900a2e242766f5fe6ae7697e3d7171aa234 X-Mailer: tip-git-log-daemon Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Commit-ID: 93824900a2e242766f5fe6ae7697e3d7171aa234 Gitweb: https://git.kernel.org/tip/93824900a2e242766f5fe6ae7697e3d7171aa234 Author: Uladzislau Rezki AuthorDate: Wed, 13 Sep 2017 12:24:30 +0200 Committer: Ingo Molnar CommitDate: Tue, 10 Oct 2017 11:45:30 +0200 sched/fair: Search a task from the tail of the queue 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: Uladzislau Rezki (Sony) Signed-off-by: Peter Zijlstra (Intel) Cc: Kirill Tkhai Cc: Linus Torvalds Cc: Mike Galbraith Cc: Mike Galbraith Cc: Nicolas Pitre Cc: Oleg Nesterov Cc: Oleksiy Avramchenko Cc: Paul Turner Cc: Peter Zijlstra Cc: Steven Rostedt Cc: Thomas Gleixner Cc: Tim Chen Link: http://lkml.kernel.org/r/20170913102430.8985-2-urezki@gmail.com Signed-off-by: Ingo Molnar --- kernel/sched/fair.c | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index ac6602c..cc0bfb0 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6628,10 +6628,7 @@ again: set_next_entity(cfs_rq, se); } - if (hrtick_enabled(rq)) - hrtick_start_fair(rq, p); - - return p; + goto done; simple: #endif @@ -6645,6 +6642,16 @@ simple: p = task_of(se); +done: __maybe_unused +#ifdef CONFIG_SMP + /* + * Move the next running task to the front of + * the list, so our cfs_tasks list becomes MRU + * one. + */ + list_move(&p->se.group_node, &rq->cfs_tasks); +#endif + if (hrtick_enabled(rq)) hrtick_start_fair(rq, p); @@ -7080,11 +7087,12 @@ static void detach_task(struct task_struct *p, struct lb_env *env) */ static struct task_struct *detach_one_task(struct lb_env *env) { - struct task_struct *p, *n; + struct task_struct *p; lockdep_assert_held(&env->src_rq->lock); - list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) { + list_for_each_entry_reverse(p, + &env->src_rq->cfs_tasks, se.group_node) { if (!can_migrate_task(p, env)) continue; @@ -7130,7 +7138,7 @@ static int detach_tasks(struct lb_env *env) if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1) break; - p = list_first_entry(tasks, struct task_struct, se.group_node); + p = list_last_entry(tasks, struct task_struct, se.group_node); env->loop++; /* We've more or less seen every task there is, call it quits */ @@ -7180,7 +7188,7 @@ static int detach_tasks(struct lb_env *env) continue; next: - list_move_tail(&p->se.group_node, tasks); + list_move(&p->se.group_node, tasks); } /*