From 6bfd6d72f51c51177676f2b1ba113fe0a85fdae4 Mon Sep 17 00:00:00 2001 From: Juri Lelli Date: Thu, 7 Nov 2013 14:43:47 +0100 Subject: sched/deadline: speed up SCHED_DEADLINE pushes with a push-heap Data from tests confirmed that the original active load balancing logic didn't scale neither in the number of CPU nor in the number of tasks (as sched_rt does). Here we provide a global data structure to keep track of deadlines of the running tasks in the system. The structure is composed by a bitmask showing the free CPUs and a max-heap, needed when the system is heavily loaded. The implementation and concurrent access scheme are kept simple by design. However, our measurements show that we can compete with sched_rt on large multi-CPUs machines [1]. Only the push path is addressed, the extension to use this structure also for pull decisions is straightforward. However, we are currently evaluating different (in order to decrease/avoid contention) data structures to solve possibly both problems. We are also going to re-run tests considering recent changes inside cpupri [2]. [1] http://retis.sssup.it/~jlelli/papers/Ospert11Lelli.pdf [2] http://www.spinics.net/lists/linux-rt-users/msg06778.html Signed-off-by: Juri Lelli Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1383831828-15501-14-git-send-email-juri.lelli@gmail.com Signed-off-by: Ingo Molnar --- kernel/sched/sched.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'kernel/sched/sched.h') diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index ad4f4fbd002e..2b7421db6c41 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -10,6 +10,7 @@ #include #include "cpupri.h" +#include "cpudeadline.h" #include "cpuacct.h" struct rq; @@ -503,6 +504,7 @@ struct root_domain { cpumask_var_t dlo_mask; atomic_t dlo_count; struct dl_bw dl_bw; + struct cpudl cpudl; /* * The "RT overload" flag: it gets set if a CPU has more than -- cgit v1.2.3