From: "Martin J. Bligh" <mbligh@aracnet.com>
To: Erich Focht <efocht@ess.nec.de>,
Michael Hohnbaum <hohnbaum@us.ibm.com>,
Christoph Hellwig <hch@infradead.org>
Cc: Andrew Theurer <habanero@us.ibm.com>, Robert Love <rml@tech9.net>,
Ingo Molnar <mingo@elte.hu>,
linux-kernel <linux-kernel@vger.kernel.org>,
lse-tech <lse-tech@lists.sourceforge.net>
Subject: Re: [PATCH 2.5.58] new NUMA scheduler: fix
Date: Wed, 15 Jan 2003 22:05:31 -0800 [thread overview]
Message-ID: <23340000.1042697129@titus> (raw)
In-Reply-To: <200301151610.43204.efocht@ess.nec.de>
[-- Attachment #1: Type: text/plain, Size: 579 bytes --]
I'm not keen on the way the minisched patch got reformatted. I changed
it into a seperate function, which I think is much cleaner by the time
you've added the third patch - no #ifdef CONFIG_NUMA in load_balance.
Rejigged patches attatched, no functional changes.
Anyway, I perf tested this, and it comes out more or less the same as
the tuned version I was poking at last night (ie best of the bunch).
Looks pretty good to me.
M.
PS. The fourth patch was so small, and touching the same stuff as 3
that I rolled it into the third one here. Seems like a universal
benefit ;-)
[-- Attachment #2: numasched1 --]
[-- Type: application/octet-stream, Size: 1653 bytes --]
diff -urpN -X /home/fletch/.diff.exclude virgin/kernel/sched.c numasched1/kernel/sched.c
--- virgin/kernel/sched.c Mon Jan 13 21:09:28 2003
+++ numasched1/kernel/sched.c Wed Jan 15 19:52:07 2003
@@ -624,6 +624,22 @@ static inline void double_rq_unlock(runq
spin_unlock(&rq2->lock);
}
+#ifdef CONFIG_NUMA
+
+static inline unsigned long cpus_to_balance(int this_cpu)
+{
+ return __node_to_cpu_mask(__cpu_to_node(this_cpu));
+}
+
+#else /* !CONFIG_NUMA */
+
+static inline unsigned long cpus_to_balance(int this_cpu)
+{
+ return cpu_online_map;
+}
+
+#endif /* CONFIG_NUMA */
+
#if CONFIG_SMP
/*
@@ -652,9 +668,9 @@ static inline unsigned int double_lock_b
}
/*
- * find_busiest_queue - find the busiest runqueue.
+ * find_busiest_queue - find the busiest runqueue among the cpus in cpumask.
*/
-static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance)
+static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance, unsigned long cpumask)
{
int nr_running, load, max_load, i;
runqueue_t *busiest, *rq_src;
@@ -689,7 +705,7 @@ static inline runqueue_t *find_busiest_q
busiest = NULL;
max_load = 1;
for (i = 0; i < NR_CPUS; i++) {
- if (!cpu_online(i))
+ if (!((1UL << i) & cpumask))
continue;
rq_src = cpu_rq(i);
@@ -764,7 +780,8 @@ static void load_balance(runqueue_t *thi
struct list_head *head, *curr;
task_t *tmp;
- busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance);
+ busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance,
+ cpus_to_balance(this_cpu));
if (!busiest)
goto out;
[-- Attachment #3: numasched2 --]
[-- Type: application/octet-stream, Size: 5907 bytes --]
diff -urpN -X /home/fletch/.diff.exclude numasched1/fs/exec.c numasched2/fs/exec.c
--- numasched1/fs/exec.c Mon Jan 13 21:09:13 2003
+++ numasched2/fs/exec.c Wed Jan 15 19:10:04 2003
@@ -1031,6 +1031,8 @@ int do_execve(char * filename, char ** a
int retval;
int i;
+ sched_balance_exec();
+
file = open_exec(filename);
retval = PTR_ERR(file);
diff -urpN -X /home/fletch/.diff.exclude numasched1/include/linux/sched.h numasched2/include/linux/sched.h
--- numasched1/include/linux/sched.h Mon Jan 13 21:09:28 2003
+++ numasched2/include/linux/sched.h Wed Jan 15 19:10:04 2003
@@ -444,6 +444,14 @@ extern void set_cpus_allowed(task_t *p,
# define set_cpus_allowed(p, new_mask) do { } while (0)
#endif
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+#define sched_balance_exec() {}
+#define node_nr_running_init() {}
+#endif
+
extern void set_user_nice(task_t *p, long nice);
extern int task_prio(task_t *p);
extern int task_nice(task_t *p);
diff -urpN -X /home/fletch/.diff.exclude numasched1/init/main.c numasched2/init/main.c
--- numasched1/init/main.c Thu Jan 9 19:16:15 2003
+++ numasched2/init/main.c Wed Jan 15 19:10:04 2003
@@ -495,6 +495,7 @@ static void do_pre_smp_initcalls(void)
migration_init();
#endif
+ node_nr_running_init();
spawn_ksoftirqd();
}
diff -urpN -X /home/fletch/.diff.exclude numasched1/kernel/sched.c numasched2/kernel/sched.c
--- numasched1/kernel/sched.c Wed Jan 15 19:52:07 2003
+++ numasched2/kernel/sched.c Wed Jan 15 19:56:42 2003
@@ -153,7 +153,9 @@ struct runqueue {
task_t *curr, *idle;
prio_array_t *active, *expired, arrays[2];
int prev_nr_running[NR_CPUS];
-
+#ifdef CONFIG_NUMA
+ atomic_t *node_nr_running;
+#endif
task_t *migration_thread;
struct list_head migration_queue;
@@ -177,6 +179,48 @@ static struct runqueue runqueues[NR_CPUS
# define task_running(rq, p) ((rq)->curr == (p))
#endif
+#ifdef CONFIG_NUMA
+
+/*
+ * Keep track of running tasks.
+ */
+
+static atomic_t node_nr_running[MAX_NUMNODES] ____cacheline_maxaligned_in_smp =
+ {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};
+
+static inline void nr_running_init(struct runqueue *rq)
+{
+ rq->node_nr_running = &node_nr_running[0];
+}
+
+static inline void nr_running_inc(runqueue_t *rq)
+{
+ atomic_inc(rq->node_nr_running);
+ rq->nr_running++;
+}
+
+static inline void nr_running_dec(runqueue_t *rq)
+{
+ atomic_dec(rq->node_nr_running);
+ rq->nr_running--;
+}
+
+__init void node_nr_running_init(void)
+{
+ int i;
+
+ for (i = 0; i < NR_CPUS; i++)
+ cpu_rq(i)->node_nr_running = &node_nr_running[__cpu_to_node(i)];
+}
+
+#else /* !CONFIG_NUMA */
+
+# define nr_running_init(rq) do { } while (0)
+# define nr_running_inc(rq) do { (rq)->nr_running++; } while (0)
+# define nr_running_dec(rq) do { (rq)->nr_running--; } while (0)
+
+#endif /* CONFIG_NUMA */
+
/*
* task_rq_lock - lock the runqueue a given task resides on and disable
* interrupts. Note the ordering: we can safely lookup the task_rq without
@@ -294,7 +338,7 @@ static inline void activate_task(task_t
p->prio = effective_prio(p);
}
enqueue_task(p, array);
- rq->nr_running++;
+ nr_running_inc(rq);
}
/*
@@ -302,7 +346,7 @@ static inline void activate_task(task_t
*/
static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
{
- rq->nr_running--;
+ nr_running_dec(rq);
if (p->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
dequeue_task(p, p->array);
@@ -624,7 +668,72 @@ static inline void double_rq_unlock(runq
spin_unlock(&rq2->lock);
}
-#ifdef CONFIG_NUMA
+#if CONFIG_NUMA
+/*
+ * If dest_cpu is allowed for this process, migrate the task to it.
+ * This is accomplished by forcing the cpu_allowed mask to only
+ * allow dest_cpu, which will force the cpu onto dest_cpu. Then
+ * the cpu_allowed mask is restored.
+ */
+static void sched_migrate_task(task_t *p, int dest_cpu)
+{
+ unsigned long old_mask;
+
+ old_mask = p->cpus_allowed;
+ if (!(old_mask & (1UL << dest_cpu)))
+ return;
+ /* force the process onto the specified CPU */
+ set_cpus_allowed(p, 1UL << dest_cpu);
+
+ /* restore the cpus allowed mask */
+ set_cpus_allowed(p, old_mask);
+}
+
+/*
+ * Find the least loaded CPU. Slightly favor the current CPU by
+ * setting its runqueue length as the minimum to start.
+ */
+static int sched_best_cpu(struct task_struct *p)
+{
+ int i, minload, load, best_cpu, node = 0;
+ unsigned long cpumask;
+
+ best_cpu = task_cpu(p);
+ if (cpu_rq(best_cpu)->nr_running <= 2)
+ return best_cpu;
+
+ minload = 10000000;
+ for (i = 0; i < numnodes; i++) {
+ load = atomic_read(&node_nr_running[i]);
+ if (load < minload) {
+ minload = load;
+ node = i;
+ }
+ }
+
+ minload = 10000000;
+ cpumask = __node_to_cpu_mask(node);
+ for (i = 0; i < NR_CPUS; ++i) {
+ if (!(cpumask & (1UL << i)))
+ continue;
+ if (cpu_rq(i)->nr_running < minload) {
+ best_cpu = i;
+ minload = cpu_rq(i)->nr_running;
+ }
+ }
+ return best_cpu;
+}
+
+void sched_balance_exec(void)
+{
+ int new_cpu;
+
+ if (numnodes > 1) {
+ new_cpu = sched_best_cpu(current);
+ if (new_cpu != smp_processor_id())
+ sched_migrate_task(current, new_cpu);
+ }
+}
static inline unsigned long cpus_to_balance(int this_cpu)
{
@@ -752,9 +861,9 @@ out:
static inline void pull_task(runqueue_t *src_rq, prio_array_t *src_array, task_t *p, runqueue_t *this_rq, int this_cpu)
{
dequeue_task(p, src_array);
- src_rq->nr_running--;
+ nr_running_dec(src_rq);
set_task_cpu(p, this_cpu);
- this_rq->nr_running++;
+ nr_running_inc(this_rq);
enqueue_task(p, this_rq->active);
/*
* Note that idle threads have a prio of MAX_PRIO, for this test
@@ -2248,6 +2357,7 @@ void __init sched_init(void)
spin_lock_init(&rq->lock);
INIT_LIST_HEAD(&rq->migration_queue);
atomic_set(&rq->nr_iowait, 0);
+ nr_running_init(rq);
for (j = 0; j < 2; j++) {
array = rq->arrays + j;
[-- Attachment #4: numasched3 --]
[-- Type: application/octet-stream, Size: 4620 bytes --]
diff -urpN -X /home/fletch/.diff.exclude numasched2/include/asm-generic/topology.h numasched3/include/asm-generic/topology.h
--- numasched2/include/asm-generic/topology.h Sun Nov 17 20:29:22 2002
+++ numasched3/include/asm-generic/topology.h Wed Jan 15 19:26:01 2003
@@ -48,4 +48,9 @@
#define __node_to_memblk(node) (0)
#endif
+/* Cross-node load balancing interval. */
+#ifndef NODE_BALANCE_RATE
+#define NODE_BALANCE_RATE 10
+#endif
+
#endif /* _ASM_GENERIC_TOPOLOGY_H */
diff -urpN -X /home/fletch/.diff.exclude numasched2/include/asm-i386/topology.h numasched3/include/asm-i386/topology.h
--- numasched2/include/asm-i386/topology.h Thu Jan 9 19:16:11 2003
+++ numasched3/include/asm-i386/topology.h Wed Jan 15 19:26:01 2003
@@ -61,6 +61,9 @@ static inline int __node_to_first_cpu(in
/* Returns the number of the first MemBlk on Node 'node' */
#define __node_to_memblk(node) (node)
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 100
+
#else /* !CONFIG_NUMA */
/*
* Other i386 platforms should define their own version of the
diff -urpN -X /home/fletch/.diff.exclude numasched2/include/asm-ia64/topology.h numasched3/include/asm-ia64/topology.h
--- numasched2/include/asm-ia64/topology.h Sun Nov 17 20:29:20 2002
+++ numasched3/include/asm-ia64/topology.h Wed Jan 15 19:26:01 2003
@@ -60,4 +60,7 @@
*/
#define __node_to_memblk(node) (node)
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 10
+
#endif /* _ASM_IA64_TOPOLOGY_H */
diff -urpN -X /home/fletch/.diff.exclude numasched2/include/asm-ppc64/topology.h numasched3/include/asm-ppc64/topology.h
--- numasched2/include/asm-ppc64/topology.h Thu Jan 9 19:16:12 2003
+++ numasched3/include/asm-ppc64/topology.h Wed Jan 15 19:26:01 2003
@@ -46,6 +46,9 @@ static inline unsigned long __node_to_cp
return mask;
}
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 10
+
#else /* !CONFIG_NUMA */
#define __cpu_to_node(cpu) (0)
diff -urpN -X /home/fletch/.diff.exclude numasched2/kernel/sched.c numasched3/kernel/sched.c
--- numasched2/kernel/sched.c Wed Jan 15 19:56:42 2003
+++ numasched3/kernel/sched.c Wed Jan 15 20:01:12 2003
@@ -67,6 +67,7 @@
#define INTERACTIVE_DELTA 2
#define MAX_SLEEP_AVG (2*HZ)
#define STARVATION_LIMIT (2*HZ)
+#define NODE_THRESHOLD 125
/*
* If a task is 'interactive' then we reinsert it in the active
@@ -155,6 +156,8 @@ struct runqueue {
int prev_nr_running[NR_CPUS];
#ifdef CONFIG_NUMA
atomic_t *node_nr_running;
+ unsigned int nr_balanced;
+ int prev_node_load[MAX_NUMNODES];
#endif
task_t *migration_thread;
struct list_head migration_queue;
@@ -735,14 +738,52 @@ void sched_balance_exec(void)
}
}
-static inline unsigned long cpus_to_balance(int this_cpu)
+/*
+ * Find the busiest node. All previous node loads contribute with a
+ * geometrically deccaying weight to the load measure:
+ * load_{t} = load_{t-1}/2 + nr_node_running_{t}
+ * This way sudden load peaks are flattened out a bit.
+ */
+static int find_busiest_node(int this_node)
+{
+ int i, node = -1, load, this_load, maxload;
+
+ this_load = maxload = (this_rq()->prev_node_load[this_node] >> 1)
+ + atomic_read(&node_nr_running[this_node]);
+ this_rq()->prev_node_load[this_node] = this_load;
+ for (i = 0; i < numnodes; i++) {
+ if (i == this_node)
+ continue;
+ load = (this_rq()->prev_node_load[i] >> 1)
+ + atomic_read(&node_nr_running[i]);
+ this_rq()->prev_node_load[i] = load;
+ if (load > maxload && (100*load > NODE_THRESHOLD*this_load)) {
+ maxload = load;
+ node = i;
+ }
+ }
+ return node;
+}
+
+static inline unsigned long cpus_to_balance(int this_cpu, runqueue_t *this_rq)
{
- return __node_to_cpu_mask(__cpu_to_node(this_cpu));
+ int this_node = __cpu_to_node(this_cpu);
+ /*
+ * Avoid rebalancing between nodes too often.
+ * We rebalance globally once every NODE_BALANCE_RATE load balances.
+ */
+ if (++(this_rq->nr_balanced) == NODE_BALANCE_RATE) {
+ int node = find_busiest_node(this_node);
+ this_rq->nr_balanced = 0;
+ if (node >= 0)
+ return (__node_to_cpu_mask(node) | (1UL << this_cpu));
+ }
+ return __node_to_cpu_mask(this_node);
}
#else /* !CONFIG_NUMA */
-static inline unsigned long cpus_to_balance(int this_cpu)
+static inline unsigned long cpus_to_balance(int this_cpu, runqueue_t *this_rq)
{
return cpu_online_map;
}
@@ -890,7 +931,7 @@ static void load_balance(runqueue_t *thi
task_t *tmp;
busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance,
- cpus_to_balance(this_cpu));
+ cpus_to_balance(this_cpu, this_rq));
if (!busiest)
goto out;
next prev parent reply other threads:[~2003-01-16 5:57 UTC|newest]
Thread overview: 96+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-01-09 23:54 Minature NUMA scheduler Martin J. Bligh
2003-01-10 5:36 ` [Lse-tech] " Michael Hohnbaum
2003-01-10 16:34 ` Erich Focht
2003-01-10 16:57 ` Martin J. Bligh
2003-01-12 23:35 ` Erich Focht
2003-01-12 23:55 ` NUMA scheduler 2nd approach Erich Focht
2003-01-13 8:02 ` Christoph Hellwig
2003-01-13 11:32 ` Erich Focht
2003-01-13 15:26 ` [Lse-tech] " Christoph Hellwig
2003-01-13 15:46 ` Erich Focht
2003-01-13 19:03 ` Michael Hohnbaum
2003-01-14 1:23 ` Michael Hohnbaum
2003-01-14 4:45 ` [Lse-tech] " Andrew Theurer
2003-01-14 4:56 ` Martin J. Bligh
2003-01-14 11:14 ` Erich Focht
2003-01-14 15:55 ` [PATCH 2.5.58] new NUMA scheduler Erich Focht
2003-01-14 16:07 ` [Lse-tech] " Christoph Hellwig
2003-01-14 16:23 ` [PATCH 2.5.58] new NUMA scheduler: fix Erich Focht
2003-01-14 16:43 ` Erich Focht
2003-01-14 19:02 ` Michael Hohnbaum
2003-01-14 21:56 ` [Lse-tech] " Michael Hohnbaum
2003-01-15 15:10 ` Erich Focht
2003-01-16 0:14 ` Michael Hohnbaum
2003-01-16 6:05 ` Martin J. Bligh [this message]
2003-01-16 16:47 ` Erich Focht
2003-01-16 18:07 ` Robert Love
2003-01-16 18:48 ` Martin J. Bligh
2003-01-16 19:07 ` Ingo Molnar
2003-01-16 18:59 ` Martin J. Bligh
2003-01-16 19:10 ` Christoph Hellwig
2003-01-16 19:44 ` Ingo Molnar
2003-01-16 19:43 ` Martin J. Bligh
2003-01-16 20:19 ` Ingo Molnar
2003-01-16 20:29 ` [Lse-tech] " Rick Lindsley
2003-01-16 23:31 ` Martin J. Bligh
2003-01-17 7:23 ` Ingo Molnar
2003-01-17 8:47 ` [patch] sched-2.5.59-A2 Ingo Molnar
2003-01-17 14:35 ` Erich Focht
2003-01-17 15:11 ` Ingo Molnar
2003-01-17 15:30 ` Erich Focht
2003-01-17 16:58 ` Martin J. Bligh
2003-01-18 20:54 ` NUMA sched -> pooling scheduler (inc HT) Martin J. Bligh
2003-01-18 21:34 ` [Lse-tech] " Martin J. Bligh
2003-01-19 0:13 ` Andrew Theurer
2003-01-17 18:19 ` [patch] sched-2.5.59-A2 Michael Hohnbaum
2003-01-18 7:08 ` William Lee Irwin III
2003-01-18 8:12 ` Martin J. Bligh
2003-01-18 8:16 ` William Lee Irwin III
2003-01-19 4:22 ` William Lee Irwin III
2003-01-17 17:21 ` Martin J. Bligh
2003-01-17 17:23 ` Martin J. Bligh
2003-01-17 18:11 ` Erich Focht
2003-01-17 19:04 ` Martin J. Bligh
2003-01-17 19:26 ` [Lse-tech] " Martin J. Bligh
2003-01-18 0:13 ` Michael Hohnbaum
2003-01-18 13:31 ` [patch] tunable rebalance rates for sched-2.5.59-B0 Erich Focht
2003-01-18 23:09 ` [patch] sched-2.5.59-A2 Erich Focht
2003-01-20 9:28 ` Ingo Molnar
2003-01-20 12:07 ` Erich Focht
2003-01-20 16:56 ` Ingo Molnar
2003-01-20 17:04 ` Ingo Molnar
2003-01-20 17:10 ` Martin J. Bligh
2003-01-20 17:24 ` Ingo Molnar
2003-01-20 19:13 ` Andrew Theurer
2003-01-20 19:33 ` Martin J. Bligh
2003-01-20 19:52 ` Andrew Theurer
2003-01-20 19:52 ` Martin J. Bligh
2003-01-20 21:18 ` [patch] HT scheduler, sched-2.5.59-D7 Ingo Molnar
2003-01-20 22:28 ` Andrew Morton
2003-01-21 1:11 ` Michael Hohnbaum
2003-01-22 3:15 ` Michael Hohnbaum
2003-01-22 16:41 ` Andrew Theurer
2003-01-22 16:17 ` Martin J. Bligh
2003-01-22 16:20 ` Andrew Theurer
2003-01-22 16:35 ` Michael Hohnbaum
2003-02-03 18:23 ` [patch] HT scheduler, sched-2.5.59-E2 Ingo Molnar
2003-02-03 20:47 ` Robert Love
2003-02-04 9:31 ` Erich Focht
2003-01-20 17:04 ` [patch] sched-2.5.59-A2 Martin J. Bligh
2003-01-21 17:44 ` Erich Focht
2003-01-20 16:23 ` Martin J. Bligh
2003-01-20 16:59 ` Ingo Molnar
2003-01-17 23:09 ` Matthew Dobson
2003-01-16 23:45 ` [PATCH 2.5.58] new NUMA scheduler: fix Michael Hohnbaum
2003-01-17 11:10 ` Erich Focht
2003-01-17 14:07 ` Ingo Molnar
2003-01-16 19:44 ` John Bradford
2003-01-14 16:51 ` Christoph Hellwig
2003-01-15 0:05 ` Michael Hohnbaum
2003-01-15 7:47 ` Martin J. Bligh
2003-01-14 5:50 ` [Lse-tech] Re: NUMA scheduler 2nd approach Michael Hohnbaum
2003-01-14 16:52 ` Andrew Theurer
2003-01-14 15:13 ` Erich Focht
2003-01-14 10:56 ` Erich Focht
2003-01-11 14:43 ` [Lse-tech] Minature NUMA scheduler Bill Davidsen
2003-01-12 23:24 ` Erich Focht
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=23340000.1042697129@titus \
--to=mbligh@aracnet.com \
--cc=efocht@ess.nec.de \
--cc=habanero@us.ibm.com \
--cc=hch@infradead.org \
--cc=hohnbaum@us.ibm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=lse-tech@lists.sourceforge.net \
--cc=mingo@elte.hu \
--cc=rml@tech9.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).