Skip to contentSkip to conversation

Add group fairness to CFS

RFC PATCH In review Srivatsa Vaddagiri 9 participants 45 messages May 23, 2007 – May 31, 2007 4 messages not in the archive

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

cover Add group fairness to CFS

Here's an attempt to extend CFS (v13) to be fair at a group level, rather than just at task level. The patch is in a very premature state (passes simple tests, smp load balance not supported yet) at this point. I am sending it out early to know if this is a good direction to proceed.

Salient points which needs discussion:

1. This patch reuses CFS core to achieve fairness at group level also.

To make this possible, CFS core has been abstracted to deal with generic schedulable "entities" (tasks, users etc).

2. The per-cpu rb-tree has been split to be per-group per-cpu.

schedule() now becomes two step on every cpu : pick a group first (from group rb-tree) and a task within that group next (from that group's task rb-tree)

3. Grouping mechanism - I have used 'uid' as the basis of grouping for timebeing (since that grouping concept is already in mainline today). The patch can be adapted to a more generic process grouping mechanism (like http://lkml.org/lkml/2007/4/27/146) later.

Some results below, obtained on a 4way (with HT) Intel Xeon box. All number are reflective of single CPU performance (tests were forced to run on single cpu since load balance is not yet supported).

uid "vatsa" uid "guest"
(make -s -j4 bzImage) (make -s -j20 bzImage)

2.6.22-rc1 772.02 sec 497.42 sec (real)
2.6.22-rc1+cfs-v13 780.62 sec 478.35 sec (real)
2.6.22-rc1+cfs-v13+this patch 776.36 sec 776.68 sec (real)

[ An exclusive cpuset containing only one CPU was created and the compilation jobs of both users were run simultaneously in this cpuset ]

I also disabled CONFIG_FAIR_USER_SCHED and compared the results with cfs-v13:

uid "vatsa" make -s -j4 bzImage

2.6.22-rc1+cfs-v13 395.57 sec (real)
2.6.22-rc1+cfs-v13+this_patch 388.54 sec (real)

There is no regression I can see (rather some improvement, which I can't understand atm). I will run more tests later to check this regression aspect.

Request your comments on the future direction to proceed!

Signature · 2 lines
Regards,
vatsa
#1 lore raw

RFC PATCH 1/3 task_cpu(p) needs to be correct always

We rely very much on task_cpu(p) to be correct at all times, so that we can correctly find the task_grp_rq from which the task has to be removed or added to.

There is however one place in the scheduler where this assumption of task_cpu(p) being correct is broken. This patch fixes that piece of code.

(Thanks to Balbir Singh for pointing this out to me)

---
 kernel/sched.c |    8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
kernel/sched.c +5 -3
Index: linux-2.6.21-rc7/kernel/sched.c
===================================================================
@@ -4571,7 +4571,7 @@
 static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
 {
 	struct rq *rq_dest, *rq_src;
-	int ret = 0;
+	int ret = 0, on_rq;
 
 	if (unlikely(cpu_is_offline(dest_cpu)))
 		return ret;
@@ -4587,9 +4587,11 @@
 	if (!cpu_isset(dest_cpu, p->cpus_allowed))
 		goto out;
 
-	set_task_cpu(p, dest_cpu);
-	if (p->on_rq) {
+	on_rq = p->on_rq;
+	if (on_rq)
 		deactivate_task(rq_src, p, 0);
+	set_task_cpu(p, dest_cpu);
+	if (on_rq) {
 		activate_task(rq_dest, p, 0);
 		check_preempt_curr(rq_dest, p);
 	}
Signature · 2 lines
Regards,
vatsa
#2 lore raw

RFC PATCH 2/3 Introduce two new structures - struct lrq and sched_entity

In reply to Srivatsa Vaddagiri

This patch groups together fields used by CFS (for SCHED_NORMAL tasks) in task_struct and runqueue into separate structures so that they can be reused in a later patch.

'struct sched_entity' represents the attributes used by CFS for every schedulable entity (task in this case).

'struct lrq' represents the runqueue used to store schedulable entities (tasks in this case) and to maintain various clocks (ex: fair clock for tasks).

This patch also modifies rest of kernel to reflect these new structures.

Intended effect of this patch is zero on overall functionality of scheduler.

---
 fs/proc/array.c           |    2 
 include/linux/sched.h     |   44 ++++----
 kernel/exit.c             |    2 
 kernel/posix-cpu-timers.c |   19 +--
 kernel/sched.c            |  195 +++++++++++++++++++------------------
 kernel/sched_debug.c      |   85 ++++++++--------
 kernel/sched_fair.c       |  238 +++++++++++++++++++++++-----------------------
 7 files changed, 301 insertions(+), 284 deletions(-)
fs/proc/array.c +1 -1
Index: linux-2.6.21-rc7/fs/proc/array.c
===================================================================
@@ -412,7 +412,7 @@
 	 * Use CFS's precise accounting, if available:
 	 */
 	if (!has_rt_policy(task)) {
-		utime = nsec_to_clock_t(task->sum_exec_runtime);
+		utime = nsec_to_clock_t(task->se.sum_exec_runtime);
 		stime = 0;
 	}
 
include/linux/sched.h +24 -20

64 lines not on this page · raw message

kernel/exit.c +1 -1
Index: linux-2.6.21-rc7/kernel/exit.c
===================================================================
@@ -124,7 +124,7 @@
 		sig->nivcsw += tsk->nivcsw;
 		sig->inblock += task_io_get_inblock(tsk);
 		sig->oublock += task_io_get_oublock(tsk);
-		sig->sum_sched_runtime += tsk->sum_exec_runtime;
+		sig->sum_sched_runtime += tsk->se.sum_exec_runtime;
 		sig = NULL; /* Marker for below. */
 	}
 
kernel/posix-cpu-timers.c +10 -9
Index: linux-2.6.21-rc7/kernel/posix-cpu-timers.c
===================================================================
@@ -161,7 +161,8 @@
 }
 static inline unsigned long long sched_ns(struct task_struct *p)
 {
-	return (p == current) ? current_sched_runtime(p) : p->sum_exec_runtime;
+	return (p == current) ? current_sched_runtime(p) :
+				 p->se.sum_exec_runtime;
 }
 
 int posix_cpu_clock_getres(const clockid_t which_clock, struct timespec *tp)
@@ -249,7 +250,7 @@
 		cpu->sched = p->signal->sum_sched_runtime;
 		/* Add in each other live thread.  */
 		while ((t = next_thread(t)) != p) {
-			cpu->sched += t->sum_exec_runtime;
+			cpu->sched += t->se.sum_exec_runtime;
 		}
 		cpu->sched += sched_ns(p);
 		break;
@@ -467,7 +468,7 @@
 void posix_cpu_timers_exit(struct task_struct *tsk)
 {
 	cleanup_timers(tsk->cpu_timers,
-		       tsk->utime, tsk->stime, tsk->sum_exec_runtime);
+		       tsk->utime, tsk->stime, tsk->se.sum_exec_runtime);
 
 }
 void posix_cpu_timers_exit_group(struct task_struct *tsk)
@@ -475,7 +476,7 @@
 	cleanup_timers(tsk->signal->cpu_timers,
 		       cputime_add(tsk->utime, tsk->signal->utime),
 		       cputime_add(tsk->stime, tsk->signal->stime),
-		       tsk->sum_exec_runtime + tsk->signal->sum_sched_runtime);
+		     tsk->se.sum_exec_runtime + tsk->signal->sum_sched_runtime);
 }
 
 
@@ -536,7 +537,7 @@
 		nsleft = max_t(unsigned long long, nsleft, 1);
 		do {
 			if (likely(!(t->flags & PF_EXITING))) {
-				ns = t->sum_exec_runtime + nsleft;
+				ns = t->se.sum_exec_runtime + nsleft;
 				if (t->it_sched_expires == 0 ||
 				    t->it_sched_expires > ns) {
 					t->it_sched_expires = ns;
@@ -1004,7 +1005,7 @@
 		struct cpu_timer_list *t = list_first_entry(timers,
 						      struct cpu_timer_list,
 						      entry);
-		if (!--maxfire || tsk->sum_exec_runtime < t->expires.sched) {
+		if (!--maxfire || tsk->se.sum_exec_runtime < t->expires.sched) {
 			tsk->it_sched_expires = t->expires.sched;
 			break;
 		}
@@ -1049,7 +1050,7 @@
 	do {
 		utime = cputime_add(utime, t->utime);
 		stime = cputime_add(stime, t->stime);
-		sum_sched_runtime += t->sum_exec_runtime;
+		sum_sched_runtime += t->se.sum_exec_runtime;
 		t = next_thread(t);
 	} while (t != tsk);
 	ptime = cputime_add(utime, stime);
@@ -1208,7 +1209,7 @@
 				t->it_virt_expires = ticks;
 			}
 
-			sched = t->sum_exec_runtime + sched_left;
+			sched = t->se.sum_exec_runtime + sched_left;
 			if (sched_expires && (t->it_sched_expires == 0 ||
 					      t->it_sched_expires > sched)) {
 				t->it_sched_expires = sched;
@@ -1300,7 +1301,7 @@
 
 	if (UNEXPIRED(prof) && UNEXPIRED(virt) &&
 	    (tsk->it_sched_expires == 0 ||
-	     tsk->sum_exec_runtime < tsk->it_sched_expires))
+	     tsk->se.sum_exec_runtime < tsk->it_sched_expires))
 		return;
 
 #undef	UNEXPIRED
kernel/sched.c +103 -92

456 lines not on this page · raw message

kernel/sched_debug.c +43 -42

128 lines not on this page · raw message

kernel/sched_fair.c +119 -119

536 lines not on this page · raw message

Signature · 2 lines
Regards,
vatsa
#3 lore raw

RFC PATCH 3/3 Generalize CFS core and provide per-user fairness

In reply to Srivatsa Vaddagiri

This patch reuses CFS core to provide inter task-group fairness. For demonstration purpose, the patch also extends CFS to provide per-user fairness. The patch is very experimental atm and in particular, SMP LOAD BALANCE IS DISABLED to keep the patch simple. I think group-based smp load
balance is more trickier and I intend to look at it next.

Although user id is chosen as the basis of grouping tasks, the patch can be adapted to work with other task grouping mechanisms (like :
http://lkml.org/lkml/2007/4/27/146).

---
 arch/i386/Kconfig     |    6 
 arch/x86_64/Kconfig   |    6 
 include/linux/sched.h |   16 
 kernel/sched.c        |  256 +++++++++++----
 kernel/sched_debug.c  |    4 
 kernel/sched_fair.c   |  820 ++++++++++++++++++++++++++++++++------------------
 kernel/sched_rt.c     |    2 
 kernel/user.c         |    5 
 8 files changed, 753 insertions(+), 362 deletions(-)
arch/i386/Kconfig +6 -0
Index: linux-2.6.21-rc7/arch/i386/Kconfig
===================================================================
@@ -307,6 +307,12 @@
 	  making when dealing with multi-core CPU chips at a cost of slightly
 	  increased overhead in some places. If unsure say N here.
 
+config FAIR_USER_SCHED
+	bool "Fair user scheduler"
+	default n
+	help
+		Fair user scheduler
+
 source "kernel/Kconfig.preempt"
 
 config X86_UP_APIC
arch/x86_64/Kconfig +6 -0
Index: linux-2.6.21-rc7/arch/x86_64/Kconfig
===================================================================
@@ -330,6 +330,12 @@
 	  making when dealing with multi-core CPU chips at a cost of slightly
 	  increased overhead in some places. If unsure say N here.
 
+config FAIR_USER_SCHED
+	bool "Fair user scheduler"
+	default n
+	help
+		Fair user scheduler
+
 source "kernel/Kconfig.preempt"
 
 config NUMA
include/linux/sched.h +16 -0
Index: linux-2.6.21-rc7/include/linux/sched.h
===================================================================
@@ -551,6 +551,16 @@
 #define is_rt_policy(p)		((p) != SCHED_NORMAL && (p) != SCHED_BATCH)
 #define has_rt_policy(p)	unlikely(is_rt_policy((p)->policy))
 
+#ifdef CONFIG_FAIR_USER_SCHED
+int sched_alloc_user(struct user_struct *user);
+void sched_free_user(struct user_struct *user);
+void sched_move_task(struct user_struct *old);
+#else
+static inline int sched_alloc_user(struct user_struct *user) { return 0; }
+static inline void sched_free_user(struct user_struct *user) { }
+static inline void sched_move_task(struct user_struct *user) { }
+#endif
+
 /*
  * Some day this will be a full-fledged user tracking system..
  */
@@ -575,6 +585,10 @@
 	/* Hash table maintenance information */
 	struct list_head uidhash_list;
 	uid_t uid;
+#ifdef CONFIG_FAIR_USER_SCHED
+	struct sched_entity *se;        /* per-cpu sched_entity */
+	struct lrq *lrq;        /* per-cpu runqueue for this user */
+#endif
 };
 
 extern struct user_struct *find_user(uid_t);
@@ -859,6 +873,8 @@
 	s64 fair_key;
 	s64 sum_wait_runtime, sum_sleep_runtime;
 	unsigned long wait_runtime_overruns, wait_runtime_underruns;
+	struct sched_entity *parent;
+	struct lrq *my_q;       /* The queue owned by this entity */
 };
 
 struct task_struct {
kernel/sched.c +185 -71

380 lines not on this page · raw message

kernel/sched_debug.c +2 -2
Index: linux-2.6.21-rc7/kernel/sched_debug.c
===================================================================
@@ -68,7 +68,7 @@
 	"------------------------------------------------"
 	"--------------------------------\n");
 
-	curr = first_fair(rq);
+	curr = first_fair(&rq->lrq);
 	while (curr) {
 		p = rb_entry(curr, struct task_struct, se.run_node);
 		print_task(m, rq, p, now);
@@ -85,7 +85,7 @@
 	unsigned long flags;
 
 	spin_lock_irqsave(&rq->lock, flags);
-	curr = first_fair(rq);
+	curr = first_fair(&rq->lrq);
 	while (curr) {
 		p = rb_entry(curr, struct task_struct, se.run_node);
 		wait_runtime_rq_sum += p->se.wait_runtime;
kernel/sched_fair.c +532 -288

1,145 lines not on this page · raw message

kernel/user.c +5 -0
Index: linux-2.6.21-rc7/kernel/user.c
===================================================================
@@ -112,6 +112,7 @@
 	if (atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
 		spin_unlock_irqrestore(&uidhash_lock, flags);
+		sched_free_user(up);
 		key_put(up->uid_keyring);
 		key_put(up->session_keyring);
 		kmem_cache_free(uid_cachep, up);
@@ -153,6 +154,8 @@
 			return NULL;
 		}
 
+		sched_alloc_user(new);
+
 		/*
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..
@@ -163,6 +166,7 @@
 			key_put(new->uid_keyring);
 			key_put(new->session_keyring);
 			kmem_cache_free(uid_cachep, new);
+			sched_free_user(new);
 		} else {
 			uid_hash_insert(new, hashent);
 			up = new;
@@ -187,6 +191,7 @@
 	atomic_dec(&old_user->processes);
 	switch_uid_keyring(new_user);
 	current->user = new_user;
+	sched_move_task(old_user);
 
 	/*
 	 * We need to synchronize with __sigqueue_alloc()
kernel/sched_rt.c +1 -1
Index: linux-2.6.21-rc7/kernel/sched_rt.c
===================================================================
@@ -166,7 +166,7 @@
 	activate_task(rq, p, 1);
 }
 
-static struct sched_class rt_sched_class __read_mostly = {
+struct sched_class rt_sched_class __read_mostly = {
 	.enqueue_task		= enqueue_task_rt,
 	.dequeue_task		= dequeue_task_rt,
 	.yield_task		= yield_task_rt,
Signature · 2 lines
Regards,
vatsa
#4 lore raw
In reply to Srivatsa Vaddagiri
Quoted 5 lines · Srivatsa Vaddagiri

Here's an attempt to extend CFS (v13) to be fair at a group level, rather than just at task level. The patch is in a very premature state (passes simple tests, smp load balance not supported yet) at this point. I am sending it out early to know if this is a good direction to proceed.

cool patch! :-)

Quoted 6 lines

Salient points which needs discussion:

1. This patch reuses CFS core to achieve fairness at group level also.

To make this possible, CFS core has been abstracted to deal with generic schedulable "entities" (tasks, users etc).

yeah, i like this alot.

The "struct sched_entity" abstraction looks very clean, and that's the main thing that matters: it allows for a design that will only cost us performance if group scheduling is desired.

If you could do a -v14 port and at least add minimal SMP support: i.e. it shouldnt crash on SMP, but otherwise no extra load-balancing logic is needed for the first cut - then i could try to pick all these core changes up for -v15. (I'll let you know about any other thoughts/details when i do the integration.)

Quoted 5 lines

2. The per-cpu rb-tree has been split to be per-group per-cpu.

schedule() now becomes two step on every cpu : pick a group first (from group rb-tree) and a task within that group next (from that group's task rb-tree)

yeah. It might even become more steps if someone wants to have a different, deeper hierarchy (at the price of performance). Containers will for example certainly want to use one more level.

Quoted 4 lines

3. Grouping mechanism - I have used 'uid' as the basis of grouping for timebeing (since that grouping concept is already in mainline today). The patch can be adapted to a more generic process grouping mechanism (like http://lkml.org/lkml/2007/4/27/146) later.

yeah, agreed.

Quoted 8 lines

Some results below, obtained on a 4way (with HT) Intel Xeon box. All number are reflective of single CPU performance (tests were forced to run on single cpu since load balance is not yet supported).

uid "vatsa" uid "guest"
(make -s -j4 bzImage) (make -s -j20 bzImage)

Quoted 7 lines

2.6.22-rc1 772.02 sec 497.42 sec (real)
2.6.22-rc1+cfs-v13 780.62 sec 478.35 sec (real)
2.6.22-rc1+cfs-v13+this patch 776.36 sec 776.68 sec (real)

[ An exclusive cpuset containing only one CPU was created and the compilation jobs of both users were run simultaneously in this cpuset ]

looks really promising!

Quoted 6 lines

I also disabled CONFIG_FAIR_USER_SCHED and compared the results with cfs-v13:

uid "vatsa" make -s -j4 bzImage

Quoted 6 lines

2.6.22-rc1+cfs-v13 395.57 sec (real)
2.6.22-rc1+cfs-v13+this_patch 388.54 sec (real)

There is no regression I can see (rather some improvement, which I can't understand atm). I will run more tests later to check this regression aspect.

kernel builds dont really push scheduling micro-costs, rather try something like 'hackbench.c' to measure that. (kernel builds are of course one of our primary benchmarks.)

Quoted 1 line

Request your comments on the future direction to proceed!

full steam ahead please! =B-)

Ingo

#5 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 5 lines

Here's an attempt to extend CFS (v13) to be fair at a group level, rather than just at task level. The patch is in a very premature state (passes simple tests, smp load balance not supported yet) at this point. I am sending it out early to know if this is a good direction to proceed.

cool patch! :-)

Thanks!

Quoted 11 lines
Quoted 4 lines

1. This patch reuses CFS core to achieve fairness at group level also.

To make this possible, CFS core has been abstracted to deal with generic schedulable "entities" (tasks, users etc).

yeah, i like this alot.

The "struct sched_entity" abstraction looks very clean, and that's the main thing that matters: it allows for a design that will only cost us performance if group scheduling is desired.

Quoted 5 lines

If you could do a -v14 port and at least add minimal SMP support: i.e. it shouldnt crash on SMP, but otherwise no extra load-balancing logic is needed for the first cut - then i could try to pick all these core changes up for -v15. (I'll let you know about any other thoughts/details when i do the integration.)

Sure ..I will work on a -v14 port. I would like to target for something which:

1. doesn't break performance/functionality of existing CFS scheduler -if- CONFIG_FAIR_USER_SCHEDULER is disabled. This also means load balance should work as it works today when the config option is disabled.

Do you recommend a set of tests that I need to run to ensure there is no regression? I know that there is a bunch of scheduler tests floating around on lkml ..Just need to dig to them (or if someone has all these tests handy on a website, I will download from that site!)

2. Provides fairness at group (user) level at the cost of missing load balance functionaility (missing until I get around to work on it that is).

Quoted 3 lines

kernel builds dont really push scheduling micro-costs, rather try something like 'hackbench.c' to measure that. (kernel builds are of course one of our primary benchmarks.)

sure i will try that on my next version.

Signature · 2 lines
Regards,
vatsa

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw
Quoted 3 lines · Guillaume Chazarain

As a sidenote, while in CFS-v13 a nice=0 tasks seems to get 10x more CPU than a nice=10 one, with the group fairness patch, the ratio drops to less than 2x (for tasks with the same UID).

gah ..silly me.

Can you repeat your tests with this patch pls? With the patch applied, I am now getting the same split between nice 0 and nice 10 task as CFS-v13 provides (90:10 as reported by top )

 5418 guest     20   0  2464  304  236 R   90  0.0   5:41.40 3 hog
 5419 guest     30  10  2460  304  236 R   10  0.0   0:43.62 3 nice10hog

Fix a stupid bug, where I was not calling __check_preempt_curr_fair() at task level during task_tick ..

---

kernel/sched_fair.c renamed from kernel/sched_fair.c~fix +5 -4
diff -puN kernel/sched_fair.c~fix kernel/sched_fair.c
@@ -577,11 +577,12 @@ static void entity_tick(struct lrq *lrq,
 				   *n = task_entity(next);
 
 		if ((c == lrq->rq->idle) || (rt_prio(n->prio) &&
-						(n->prio < c->prio)))
+						(n->prio < c->prio))) {
 			resched_task(c);
-	} else
-		__check_preempt_curr_fair(lrq, next, curr,
-					  *(lrq->sched_granularity));
+			return;
+		}
+	}
+	__check_preempt_curr_fair(lrq, next, curr, *(lrq->sched_granularity));
 }
 
 static void _update_load(struct lrq *this_rq)

_

Signature · 2 lines
Regards,
vatsa
#10 lore raw
Quoted 6 lines · Srivatsa Vaddagiri

Can you repeat your tests with this patch pls? With the patch applied, I am now getting the same split between nice 0 and nice 10 task as CFS-v13 provides (90:10 as reported by top )

 5418 guest     20   0  2464  304  236 R   90  0.0   5:41.40 3 hog
 5419 guest     30  10  2460  304  236 R   10  0.0   0:43.62 3 nice10hog

btw., what are you thoughts about SMP?

it's a natural extension of your current code. I think the best approach would be to add a level of 'virtual CPU' objects above struct user. (how to set the attributes of those objects is open - possibly combine it with cpusets?)

That way the scheduler would first pick a "virtual CPU" to schedule, and then pick a user from that virtual CPU, and then a task from the user.

To make group accounting scalable, the accounting object attached to the user struct should/must be per-cpu (per-vcpu) too. That way we'd have a clean hierarchy like:

CPU #0 => VCPU A [ 40% ] + VCPU B [ 60% ]
CPU #1 => VCPU C [ 30% ] + VCPU D [ 70% ]

VCPU A => USER X [ 10% ] + USER Y [ 90% ]
VCPU B => USER X [ 10% ] + USER Y [ 90% ]
VCPU C => USER X [ 10% ] + USER Y [ 90% ]
VCPU D => USER X [ 10% ] + USER Y [ 90% ]

the scheduler first picks a vcpu, then a user from a vcpu. (the actual external structure of the hierarchy should be opaque to the scheduler core, naturally, so that we can use other hierarchies too)

whenever the scheduler does accounting, it knows where in the hierarchy it is and updates all higher level entries too. This means that the accounting object for USER X is replicated for each VCPU it participates in.

SMP balancing is straightforward: it would fundamentally iterate through the same hierarchy and would attempt to keep all levels balanced - i abstracted away its iterators already.

Hm?

Ingo

#11 lore raw
Quoted 1 line · Ingo Molnar

btw., what are you thoughts about SMP?

I was planning on reusing smpnice concepts here, with the difference that we balance group weights across CPU in addition to total weight of CPUs.

For ex, assuming weight of each task is 10

CPU0 => USER X (Wt 100) + USER Y (Wt 200) => total weight 300 CPU1 => USER X (Wt 30) + USER Y (Wt 80) => total weight 110

So first we notice that CPU0 and CPU1 are imbalanced by weight 190 and target at reducing this imbalance by half i.e CPU1 has to pull total weight of 95 (190/2) from CPU0. However while pulling weights, we apply the same imbalance/2 rule at group level also. For ex: we cannot pull more than 70/2 = 35 from USER X on CPU0 or more than 120/2 = 60 from USER Y on CPU0.

Using this rule, after balance, the two CPUs may look like:

CPU0 => USER X (Wt 70) + USER Y (Wt 140) => total weight 210 CPU1 => USER X (Wt 60) + USER Y (Wt 140) => total weight 200

I had tried this approach earlier (in
https://lists.linux-foundation.org/pipermail/containers/2007-April/004580.html)
and had obtained decent results. It also required minimal changes to smpnice.

Compared to this, what better degree of control/flexibilty does virtual cpu approach give?

Quoted 4 lines

it's a natural extension of your current code. I think the best approach would be to add a level of 'virtual CPU' objects above struct user. (how to set the attributes of those objects is open - possibly combine it with cpusets?)

are these virtual CPUs visible to users (ex: does smp_processor_id() return virtual cpu id rather than physical id and does DEFINE_PER_CPU create per-cpu data for virtual CPUs rather than physical cpus)?

Quoted 1 line

That way the scheduler would first pick a "virtual CPU" to schedule,

are virtual cpus pinned to their physical cpu or can they bounce around? i.e can CPU #0 schedule VCPU D (in your example below)? If bouncing is allowed, I am not sure whether that is a good thing for performance. How do we minimize this performance cost?

Quoted 28 lines

and then pick a user from that virtual CPU, and then a task from the user.

To make group accounting scalable, the accounting object attached to the user struct should/must be per-cpu (per-vcpu) too. That way we'd have a clean hierarchy like:

CPU #0 => VCPU A [ 40% ] + VCPU B [ 60% ]
CPU #1 => VCPU C [ 30% ] + VCPU D [ 70% ]

VCPU A => USER X [ 10% ] + USER Y [ 90% ]
VCPU B => USER X [ 10% ] + USER Y [ 90% ]
VCPU C => USER X [ 10% ] + USER Y [ 90% ]
VCPU D => USER X [ 10% ] + USER Y [ 90% ]

the scheduler first picks a vcpu, then a user from a vcpu. (the actual external structure of the hierarchy should be opaque to the scheduler core, naturally, so that we can use other hierarchies too)

whenever the scheduler does accounting, it knows where in the hierarchy it is and updates all higher level entries too. This means that the accounting object for USER X is replicated for each VCPU it participates in.

SMP balancing is straightforward: it would fundamentally iterate through the same hierarchy and would attempt to keep all levels balanced - i abstracted away its iterators already

Hm?

Signature · 2 lines
Regards,
vatsa
#12 lore raw
Quoted 6 lines · Srivatsa Vaddagiri
Quoted 1 line · Ingo Molnar

btw., what are you thoughts about SMP?

I was planning on reusing smpnice concepts here, with the difference that we balance group weights across CPU in addition to total weight of CPUs.

ok, that would be (much) simpler that any explicit vcpu approach. Do you plan to add this next?

Ingo

#13 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 3 lines

I was planning on reusing smpnice concepts here, with the difference that we balance group weights across CPU in addition to total weight of CPUs.

ok, that would be (much) simpler that any explicit vcpu approach. Do you plan to add this next?

sure, after i first cleanup current group changes a bit. Hopefully I can send you first version of smp support by early next week.

Signature · 2 lines
Regards,
vatsa
#14 lore raw
Quoted 10 lines · Srivatsa Vaddagiri
Quoted 6 lines · Ingo Molnar
Quoted 3 lines

I was planning on reusing smpnice concepts here, with the difference that we balance group weights across CPU in addition to total weight of CPUs.

ok, that would be (much) simpler that any explicit vcpu approach. Do you plan to add this next?

sure, after i first cleanup current group changes a bit. Hopefully I can send you first version of smp support by early next week.

great. Btw., could you please keep the "up to this point there should be no behavioral change in CFS" fundamental splitup of your patches - that way i can look at the core changes (and possibly apply them) without having to consider the uid based changes (which do change behavior and which need more upstream buy-in).

Ingo

#15 lore raw
Quoted 2 lines · Ingo Molnar

great. Btw., could you please keep the "up to this point there should be no behavioral change in CFS" fundamental splitup of your patches -

sure ..basically the changes required in CFS core is the introduction of two structures - struct sched_entity and struct lrq and generalization of cfs routines to operate on these structures rather than on task_struct/rq structures directly.

In the first split, I will ensure that this generalization is applied only to tasks (which represents reorganization of core with no behavioral/functional change in scheduler) and in a subsequent split/patch I will apply the generalization to uids also (which will add group fairness aspect to scheduler), as you require.

Thanks for your feedback so far!

Quoted 3 lines

that way i can look at the core changes (and possibly apply them) without having to consider the uid based changes (which do change behavior and which need more upstream buy-in).

Signature · 2 lines
Regards,
vatsa
#16 lore raw
In reply to Ingo Molnar
Quoted 13 lines · Ingo Molnar
Quoted 6 lines · Srivatsa Vaddagiri

Can you repeat your tests with this patch pls? With the patch applied, I am now getting the same split between nice 0 and nice 10 task as CFS-v13 provides (90:10 as reported by top )

5418 guest     20   0  2464  304  236 R   90  0.0   5:41.40 3 hog
5419 guest     30  10  2460  304  236 R   10  0.0   0:43.62 3 nice10hog

btw., what are you thoughts about SMP?

Quoted 7 lines

it's a natural extension of your current code. I think the best approach would be to add a level of 'virtual CPU' objects above struct user. (how to set the attributes of those objects is open - possibly combine it with cpusets?)

That way the scheduler would first pick a "virtual CPU" to schedule, and then pick a user from that virtual CPU, and then a task from the user.

don't you mean the vice versa:
first use to scheduler, then VCPU (which is essentially a runqueue or rbtree), then a task from VCPU?

this is the approach we use in OpenVZ and if you don't mind I would propose to go this way for fair-scheduling in mainstream. It has it's own advantages and disatvantages.

This is not the easy way to go and I can outline the problems/disadvantages which appear on this way:
- tasks which bind to CPU mask will bind to virtual CPUs.
no problem with user tasks, but some kernel threads
use this to do CPU-related management (like cpufreq).
This can be fixed using SMP IPI actually.
- VCPUs should no change PCPUs very frequently,
otherwise there is some overhead. Solvable.

Advantages:
- High precision and fairness.
- Allows to use different group scheduling algorithms on top of VCPU concept.
OpenVZ uses fairscheduler with CPU limiting feature allowing to set maximum CPU time given to a group of tasks.

Quoted 6 lines

To make group accounting scalable, the accounting object attached to the user struct should/must be per-cpu (per-vcpu) too. That way we'd have a clean hierarchy like:

CPU #0 => VCPU A [ 40% ] + VCPU B [ 60% ]
CPU #1 => VCPU C [ 30% ] + VCPU D [ 70% ]

how did you select these 40%:60% and 30%:70% split?

Quoted 5 lines

VCPU A => USER X [ 10% ] + USER Y [ 90% ]
VCPU B => USER X [ 10% ] + USER Y [ 90% ]
VCPU C => USER X [ 10% ] + USER Y [ 90% ]
VCPU D => USER X [ 10% ] + USER Y [ 90% ]

Quoted 8 lines

the scheduler first picks a vcpu, then a user from a vcpu. (the actual external structure of the hierarchy should be opaque to the scheduler core, naturally, so that we can use other hierarchies too)

whenever the scheduler does accounting, it knows where in the hierarchy it is and updates all higher level entries too. This means that the accounting object for USER X is replicated for each VCPU it participates in.

So if 2 VCPUs running on 2 physical CPUs do accounting the have to update the same user X accounting information which is not per-[v]cpu?

Quoted 3 lines

SMP balancing is straightforward: it would fundamentally iterate through the same hierarchy and would attempt to keep all levels balanced - i abstracted away its iterators already.

Thanks,
Kirill

#17 lore raw
Quoted 8 lines · Kirill Korotaev
Quoted 2 lines

That way the scheduler would first pick a "virtual CPU" to schedule, and then pick a user from that virtual CPU, and then a task from the user.

don't you mean the vice versa:
first use to scheduler, then VCPU (which is essentially a runqueue or rbtree), then a task from VCPU?

this is the approach we use in OpenVZ [...]

So is this how it looks in OpenVZ?

CONTAINER1 => VCPU0 + VCPU1
CONTAINER2 => VCPU2 + VCPU3

PCPU0 picks a container first, a vcpu next and then a task in it PCPU1 also picks a container first, a vcpu next and then a task in it.

Few questions:

1. Are VCPU runqueues (on which tasks are present) global queues?

That is, let's say that both PCPU0 and PCPU1 pick CONTAINER1 to schedule (first level) at the same time and next (let's say) they pick same vcpu VCPU0 to schedule (second level). Will the two pcpu's now have to be serialized for scanning task to schedule next (third level) within VCPU0 using a spinlock? Won't that shootup scheduling costs (esp on large systems), compared to (local scheduling + balance across cpus once in a while, the way its done today)?

Or do you required that two pcpus don't schedule the same vcpu at the same time (the way hypervisors normally work)? Even then I would imagine a fair level of contention to be present in second step (pick a virtual cpu from a container's list of vcpus).

2. How would this load balance at virtual cpu level and sched domain based load balancing interact?

The current sched domain based balancing code has many HT/MC/SMT related optimizations, which ensure that tasks are spread across physical threads/cores/packages in a most efficient manner - so as to utilize hardware bandwidth to the maximum. You would now need to introduce those optimizations essentially at schedule() time ..? Don't know if that is a wise thing to do.

3. How do you determine the number of VCPUs per container? Is there any relation for number of virtual cpus exposed per user/container and the number of available cpus? For ex: in case of user-driven scheduling, we would want all users to see the same number of cpus (which is the number available in the system).

4. VCPU ids (namespace) - is it different for different containers?

For ex: can id's of vcpus belonging to different containers (say VCPU0 and VCPU2), as seen by users thr' vgetcpu/smp_processor_id() that is, be same? If so, then potentially two threads belonging to different users may find that they are running -truly simultaneously- on /same/ cpu 0 (one on VCPU0/PCPU0 and another on VCPU2/PCPU1) which normally isn't possible!

This may be ok for containers, with non-overlapping cpu id namespace, but when applied to group scheduling for, say, users, which require a global cpu id namespace, wondering how that would be addressed ..

Quoted 8 lines

and if you don't mind I would propose to go this way for fair-scheduling in mainstream.
It has it's own advantages and disatvantages.

This is not the easy way to go and I can outline the problems/disadvantages which appear on this way:
- tasks which bind to CPU mask will bind to virtual CPUs.
no problem with user tasks, [...]

Why is this not a problem for user tasks? Tasks which bind to different CPUs for performance reason now can find that they are running on same (physical) CPU unknowingly.

Quoted 8 lines

but some kernel threads
use this to do CPU-related management (like cpufreq). This can be fixed using SMP IPI actually.
- VCPUs should no change PCPUs very frequently, otherwise there is some overhead. Solvable.

Advantages:
- High precision and fairness.

I just don't know if this benefit of high degree of fairness is worth the complexity it introduces. Besides having some data which shows how much better is is with respect to fairness/overhead when compared with other approaches (like smpnice) would help I guess. I will however let experts like Ingo make the final call here :)

Signature · 2 lines
Regards,
vatsa
#18 lore raw
Quoted 12 lines · Srivatsa Vaddagiri
Quoted 8 lines · Kirill Korotaev
Quoted 2 lines

That way the scheduler would first pick a "virtual CPU" to schedule, and then pick a user from that virtual CPU, and then a task from the user.

don't you mean the vice versa:
first use to scheduler, then VCPU (which is essentially a runqueue or rbtree), then a task from VCPU?

this is the approach we use in OpenVZ [...]

Quoted 7 lines

So is this how it looks in OpenVZ?

CONTAINER1 => VCPU0 + VCPU1
CONTAINER2 => VCPU2 + VCPU3

PCPU0 picks a container first, a vcpu next and then a task in it PCPU1 also picks a container first, a vcpu next and then a task in it.

correct.

Quoted 4 lines

Few questions:

1. Are VCPU runqueues (on which tasks are present) global queues?

Quoted 11 lines

That is, let's say that both PCPU0 and PCPU1 pick CONTAINER1 to schedule (first level) at the same time and next (let's say) they pick same vcpu VCPU0 to schedule (second level). Will the two pcpu's now have to be serialized for scanning task to schedule next (third level) within VCPU0 using a spinlock? Won't that shootup scheduling costs (esp on large systems), compared to (local scheduling + balance across cpus once in a while, the way its done today)?
Or do you required that two pcpus don't schedule the same vcpu at the same time (the way hypervisors normally work)? Even then I would imagine a fair level of contention to be present in second step (pick a virtual cpu from a container's list of vcpus).

2 physical CPUs can't select the same VCPU at the same time. i.e. VCPU can be running on 1 PCPU only at the moment. and vice versa: PCPU can run only 1 VCPU at the given moment.

So serialization is done when we need to assign VCPU to PCPU moment only, not when we select a particular task from the runqueue.

About the contention: you can control how often VCPUs should be rescheduled, so the contention can be quite small. This contention is unavoidable in any fair scheduler since fairness implies across CPUs accounting and decision making at least with some period of time.

Well it is possible to avoid contention at all - if we do fair scheduling separately on each CPU. But in this case we still do user-based balancing (which requires serialization) and precision can be nasty.

Quoted 9 lines

2. How would this load balance at virtual cpu level and sched domain based load balancing interact?

The current sched domain based balancing code has many HT/MC/SMT related optimizations, which ensure that tasks are spread across physical threads/cores/packages in a most efficient manner - so as to utilize hardware bandwidth to the maximum. You would now need to introduce those optimizations essentially at schedule() time ..? Don't know if that is a wise thing to do.

load balancing is done taking into account *current* VCPUs assignments to PCPUs. i.e. sched domains are taken into account.
nothing is introduces at schedule() time - not sure what you meant actually by this.

Quoted 5 lines

3. How do you determine the number of VCPUs per container? Is there any relation for number of virtual cpus exposed per user/container and the number of available cpus? For ex: in case of user-driven scheduling, we would want all users to see the same number of cpus (which is the number available in the system).

by default every user is given num_online_cpus() VCPUs, i.e. it can run on all physical CPUs at the same time. If needed a user can be limited.

Quoted 1 line

4. VCPU ids (namespace) - is it different for different containers?

yes.

Quoted 2 lines

For ex: can id's of vcpus belonging to different containers (say VCPU0 and VCPU2), as seen by users thr' vgetcpu/smp_processor_id() that is, be same?

yes.

Quoted 3 lines

If so, then potentially two threads belonging to different users may find that they are running -truly simultaneously- on /same/ cpu 0 (one on VCPU0/PCPU0 and another on VCPU2/PCPU1) which normally isn't possible!

yes. but for user space this has no any implications. You see, there is no way for user space to determine whether it is "-truly simultaneously- running on /same/ cpu 0".

Quoted 3 lines

This may be ok for containers, with non-overlapping cpu id namespace, but when applied to group scheduling for, say, users, which require a global cpu id namespace, wondering how that would be addressed ..

very simple imho.
the only way from user space to get some task CPU id is /proc. All you need is to return *some* value there.
For example, one can report PCPU id to which VCPU is assigned.

Quoted 10 lines
Quoted 8 lines

and if you don't mind I would propose to go this way for fair-scheduling in mainstream.
It has it's own advantages and disatvantages.

This is not the easy way to go and I can outline the problems/disadvantages which appear on this way:
- tasks which bind to CPU mask will bind to virtual CPUs.
no problem with user tasks, [...]

Quoted 3 lines

Why is this not a problem for user tasks? Tasks which bind to different CPUs for performance reason now can find that they are running on same (physical) CPU unknowingly.

if there is no high load - tasks will be running on different PCPUs
as the author was planning, since VCPUs will get different PCPUs for sure. Otherwise - it is not performance critical, and moreover *controversial* to *fairness*.

Let me provide an example why binding is controversial to fairness. Imagine that we have 2 USERs - USER1 and USER2 and 2 CPUs in the system. USER1 has 50 tasks binded to CPU0 and 50 tasks binded to CPU1. USER2 has 1 task.

Let USER2 to be as important as USER1 is, so these USERs should share summary CPU time as 1:1.
How will it work with your approach?

Quoted 10 lines
Quoted 8 lines

but some kernel threads
use this to do CPU-related management (like cpufreq). This can be fixed using SMP IPI actually.
- VCPUs should no change PCPUs very frequently, otherwise there is some overhead. Solvable.

Advantages:
- High precision and fairness.

Quoted 5 lines

I just don't know if this benefit of high degree of fairness is worth the complexity it introduces. Besides having some data which shows how much better is is with respect to fairness/overhead when compared with other approaches (like smpnice) would help I guess. I will however let experts like Ingo make the final call here :)

sure. The "perfect" solution doesn't exist :( So I would be happy to know Ingo opinion as well.

Thanks,
Kirill

#19 lore raw
Quoted 7 lines · Kirill Korotaev

2 physical CPUs can't select the same VCPU at the same time. i.e. VCPU can be running on 1 PCPU only at the moment. and vice versa: PCPU can run only 1 VCPU at the given moment.

So serialization is done when we need to assign VCPU to PCPU moment only, not when we select a particular task from the runqueue.

Quoted 8 lines

About the contention: you can control how often VCPUs should be rescheduled, so the contention can be quite small. This contention is unavoidable in any fair scheduler since fairness implies across CPUs accounting and decision making at least with some period of time.

Well it is possible to avoid contention at all - if we do fair scheduling separately on each CPU. But in this case we still do user-based balancing (which requires serialization) and precision can be nasty.

I guess how nasty or not it is depends on interval over which fairness is expected. Longer the interval, better the scope to provide good fairness based on load-balance schemes like sched-domain/smpnice ..

Quoted 2 lines
Quoted 2 lines

2. How would this load balance at virtual cpu level and sched domain based load balancing interact?

[snip]

Quoted 4 lines

load balancing is done taking into account *current* VCPUs assignments to PCPUs. i.e. sched domains are taken into account.
nothing is introduces at schedule() time - not sure what you meant actually by this.

Basically, lets say that there are 2 CPUs, each with two threads

	    --------------------
	   |			|
	------              ---------
       i      i            i         i
     CPU0   CPU1         CPU2      CPU3

CPU0/1 and CPU2/3 are siblings.

Lets say that CPU0 has two or more tasks while CPU[1-3] are idle. Then the HT optimizations in sched domains based load balancer ensures that CPU2 or 3 picks up one (or more) task from CPU0 rather than CPU1 picking it. The same logic works at higher packaging levels (core, package, node? etc).

How would the virtual cpu scheduler achieve such optimizations? My thought was such optimizations (if they have to be retained) has to be introduced at virtual cpu schedule time ..?

Not just this, the sched domain based load balancer has other (nice?) properties that it balances less frequently across nodes than across cpus inside a node. This lets tasks execute longer on same node.

Essentially what I wanted to know was : what will be the role of sched domain based load balancer on top of virtual cpu load balancer? Do you disable sched domain based balancer completely? Or does it balance tasks across virtual cpus? Given that virtual cpus can run anywhere, then it needs to be significantly changed to understand that (for ex: the HT/MC optimizations in sched domain balancer needs to becomes aware of this virtual->physical cpu relationship).

Quoted 3 lines
Quoted 1 line

4. VCPU ids (namespace) - is it different for different containers?

yes.

Is this namespace different inside kernel context too?

To illustrate, consider my previous example:

CONTAINER1 => VCPU0 + VCPU1
CONTAINER2 => VCPU2 + VCPU3

Lets say that T1 in CONTAINER1 is running on VCPU0/PCPU0 at the same time that T2 in CONTAINER2 is running on VCPU2/PCPU1. As we discussed earlier, they both can see themselves running on same (virtual) cpu 0. Lets say they make system calls now and what does the kernel see this cpu id as thr' smp_processor_id()? Hopefully it is different for the two threads when they are inside kernel ..

Quoted 11 lines
Quoted 2 lines

For ex: can id's of vcpus belonging to different containers (say VCPU0 and VCPU2), as seen by users thr' vgetcpu/smp_processor_id() that is, be same?

yes.

Quoted 3 lines

If so, then potentially two threads belonging to different users may find that they are running -truly simultaneously- on /same/ cpu 0 (one on VCPU0/PCPU0 and another on VCPU2/PCPU1) which normally isn't possible!

yes. but for user space this has no any implications. You see, there is no way for user space to determine whether it is "-truly simultaneously- running on /same/ cpu 0".

Hmm ..what if some user space app maintains per-cpu stuff and (now that we return same cpu id to both tasks running simultaneously on two different physical cpus) they collide writing to the the same per-cpu area?

Quoted 6 lines
Quoted 3 lines

This may be ok for containers, with non-overlapping cpu id namespace, but when applied to group scheduling for, say, users, which require a global cpu id namespace, wondering how that would be addressed ..

very simple imho.
the only way from user space to get some task CPU id is /proc.

I believe there is a syscall (vgetcpu?) in works to get a cpu id.

Quoted 2 lines

All you need is to return *some* value there.
For example, one can report PCPU id to which VCPU is assigned.

That may break other things. What if task had bound to (virtual) cpu0 and now its call to vgetcpu returns different values at different times, based on where that virtual cpu0 was running at that moment!

IMHO introduction of virtual cpu for cases which require global cpu id space will be a pretty complex thingy (both for user space and for kernel). Not sure if it is worth the benefits.

Quoted 6 lines
Quoted 3 lines

Why is this not a problem for user tasks? Tasks which bind to different CPUs for performance reason now can find that they are running on same (physical) CPU unknowingly.

if there is no high load - tasks will be running on different PCPUs as the author was planning, since VCPUs will get different PCPUs for sure.

Again it depends on the application I guess. Even under high load, it may be the expectation of the user to run on same cpu for correctness reasons.

Quoted 10 lines

Otherwise - it is not performance critical, and moreover *controversial* to *fairness*.

Let me provide an example why binding is controversial to fairness. Imagine that we have 2 USERs - USER1 and USER2 and 2 CPUs in the system. USER1 has 50 tasks binded to CPU0 and 50 tasks binded to CPU1. USER2 has 1 task.

Let USER2 to be as important as USER1 is, so these USERs should share summary CPU time as 1:1.
How will it work with your approach?

Good example :) USER2's single task will have to share its CPU with USER1's 50 tasks (unless we modify the smpnice load balancer to disregard cpu affinity that is - which I would not prefer to do).

Ingo/Peter, any thoughts here? CFS and smpnice probably is "broken" with respect to such example as above albeit for nice-based tasks.

Signature · 2 lines
Regards,
vatsa
#20 lore raw
Quoted 3 lines · Srivatsa Vaddagiri

Good example :) USER2's single task will have to share its CPU with USER1's 50 tasks (unless we modify the smpnice load balancer to disregard cpu affinity that is - which I would not prefer to do).

I don't think that ignoring cpu affinity is an option. Setting the cpu affinity of tasks is a deliberate policy action on the part of the system administrator and has to be honoured. Load balancing has to do the best it can in these circumstances which may mean sub optimal distribution of the load BUT it is result of a deliberate policy decision by the system administrator.

Quoted 3 lines

Ingo/Peter, any thoughts here? CFS and smpnice probably is "broken" with respect to such example as above albeit for nice-based tasks.

See above. I think that faced with cpu affinity use by the system administrator that smpnice will tend towards a task to cpu allocation that is (close to) the best that can be achieved without violating the cpu affinity assignments. (It may take a little longer than normal but it should get there eventually.)

You have to assume that the system administrator knows what (s)he's doing and is willing to accept the impact of their policy decision on the overall system performance.

Having said that, if it was deemed necessary you could probably increase the speed at which the load balancer converged on a good result in the face of cpu affinity by keeping a "pinned weighted load" value for each run queue and using that to modify find_busiest_group() and find_busiest_queue() to be a bit smarter. But I'm not sure that it would be worth the added complexity.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#21 lore raw
Quoted 2 lines · Srivatsa Vaddagiri
Quoted 2 lines

Ingo/Peter, any thoughts here? CFS and smpnice probably is "broken" with respect to such example as above albeit for nice-based tasks.

Quoted 6 lines · Peter Williams

See above. I think that faced with cpu affinity use by the system administrator that smpnice will tend towards a task to cpu allocation that is (close to) the best that can be achieved without violating the cpu affinity assignments. (It may take a little longer than normal but it should get there eventually.)
You have to assume that the system administrator knows what (s)he's

Quoted 8 lines

doing and is willing to accept the impact of their policy decision on the overall system performance.
Having said that, if it was deemed necessary you could probably increase the speed at which the load balancer converged on a good result in the face of cpu affinity by keeping a "pinned weighted load" value for each run queue and using that to modify find_busiest_group() and
find_busiest_queue() to be a bit smarter. But I'm not sure that it
would be worth the added complexity.

Just in case anyone was looking for algorithms...

Lag should be considered in lieu of load because lag is what the scheduler is trying to minimize; load is not directly relevant, but appears to have some sort of relationship. Also, instead of pinned, unpinned should be considered. It's unpinned that load balancing can actually migrate. Using the signed minimax pseudonorm (i.e. the highest signed lag, where positive is higher than all negative regardless of magnitude) on unpinned lags yields a rather natural load balancing algorithm consisting of migrating from highest to lowest signed lag, with progressively longer periods for periodic balancing across progressively higher levels of hierarchy in sched_domains etc. as usual. Basically skip over pinned tasks as far as lag goes.

The trick with all that comes when tasks are pinned within a set of cpus (especially crossing sched_domains) instead of to a single cpu. There one can just consider a cpu to enter a periodic load balance cycle, and then consider pushing and pulling, perhaps what could be called the "exchange lags" for the pair of cpus. That would be the minimax lag pseudonorms for the tasks migratable to both cpus of the pair. That makes the notion of moving things from highest to lowest lag (where load is now considered) unambiguous apart from whether all this converges, but not when to actually try to load balance vs. when not to, or when it's urgent vs. when it should be done periodically.

To clarify that, an O(cpus**2) notion appears to be necessary, namely the largest exchange lag differential between any pair of cpus. There is also the open question of whether moving tasks between cpus with the highest exchange lag differential will actually reduce it or whether it runs the risk of increasing it by creating a larger exchange lag differential between different pairs of cpus. A similar open question is raised by localizing balancing decisions to sched_domains. What remains clear is that any such movement reduces the worst-case lag in the whole system. Because of that, the worst-case lag in the whole system monotonically decreases as balancing decisions are made, and that much is subject to an infinite descent argument. Unfortunately, determining the largest exchange lag differential appears to be more complex than merely finding the highest and lowest lags. Bipartite forms of the problem also arise from sched_domains.

I doubt anyone's really paying any sort of attention, so I'll not really bother working out much more in the way of details with respect to load balancing. It may be that there are better ways to communicate algorithmic notions than prose descriptions. However, it's doubtful I'll produce anything in a timely enough fashion to attract or hold interest.

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

task    nice    hier1   hier2   ...     hierN
t_1     w_n1    w_h11   w_h21   ...     w_hN1
t_2     w_n2    w_h12   w_h22   ...     w_hN2

...

For the example of nice 0 vs. nice 10 as distinct users with 10% steppings between nice levels, one would have

task    nice   hier1
t_1     1      1
t_2     0.3855 1

w_1, the weight of t_1, would be

        (w_h11*w_n1/(w_h11*w_n1 + w_h12*w_n2))
                = (1*1/(1 + 1*0.3855..))
                = 0.7217..
w_2, the weight of t_2, would be
        (w_h12*w_n2/(w_h11*w_n1 + w_h12*w_n2))
                = (1*0.3855../(1 + 1*0.3855..))
                = 0.27826..

This just so happens to work out to being the same as if t_1 and t_2 had their respective nice numbers without the scheduler grouping, which is basically what everyone wants to happen.

It's more obvious how to extend it to more tasks than levels of hierarchy. An example of that follows:

task    nice    hier1   hier2   ...     hierN
t_1     0.3     0.6     *       ...     *
t_2     0.7     0.4     *       ...     *

hier2 through hierN are ignorable since t_1 and t_2 are both the only members at those levels of hierarchy. We then get something just like the above example, w_1 = 0.3*0.6/(0.3*0.6+0.7*0.4) = 0.3913.. and w2 = 0.7*0.4/(0.3*0.6+0.7*0.4) = 0.6087..

It's more interesting with enough tasks to have more meaningful levels of hierarchy.

task    nice    hier1   hier2
t_1     0.7     0.6     0.6
t_2     0.3     0.6     0.4
t_3     0.7     0.4     0.6
t_4     0.3     0.4     0.4

where t_1 and t_2 share a hier1 grouping and t_3 and t_4 also share a hier1 grouping, but the hier1 grouping for t_1 and t_2 is distinct from the hier1 grouping for t_3 and t_4. All hier2 groupings are distinct. So t_1 would have pre-nice weight 0.6*0.6, t_2 0.6*0.4, t_3 0.6*0.4, and t_4 0.4*0.4 (the numbers were chosen so denominators conveniently collapse to 1). Now that the hierarchy is flattened, nice numbers can be factored in for t_1's final weight being 0.7*0.36/(0.7*0.36+0.3*0.24+0.7*0.24+0.3*0.16) = 0.252/0.54 = 0.467.. and the others being 0.133.. (t_2), 0.311.. (t_3), and 0.0889.. (t_4).

In such a manner nice numbers obey the principle of least surprise.

-- wli

#22 lore raw
Quoted 11 lines · William Lee Irwin III
Quoted 1 line · Srivatsa Vaddagiri
Quoted 1 line

Ingo/Peter, any thoughts here? CFS and smpnice probably is "broken" with respect to such example as above albeit for nice-based tasks.

Quoted 3 lines · Peter Williams

See above. I think that faced with cpu affinity use by the system administrator that smpnice will tend towards a task to cpu allocation that is (close to) the best that can be achieved without violating the cpu affinity assignments. (It may take a little longer than normal but it should get there eventually.) You have to assume that the system administrator knows what (s)he's doing and is willing to accept the impact of their policy decision on the overall system performance.
Having said that, if it was deemed necessary you could probably increase the speed at which the load balancer converged on a good result in the face of cpu affinity by keeping a "pinned weighted load" value for each run queue and using that to modify find_busiest_group() and find_busiest_queue() to be a bit smarter. But I'm not sure that it would be worth the added complexity.

Just in case anyone was looking for algorithms...

Lag should be considered in lieu of load because lag

What's the definition of lag here?

Quoted 2 lines

is what the
scheduler is trying to minimize;

This isn't always the case. Some may prefer fairness to minimal lag. Others may prefer particular tasks to receive preferential treatment.

Quoted 3 lines

load is not directly relevant, but
appears to have some sort of relationship. Also, instead of pinned, unpinned should be considered.

If you have total and pinned you can get unpinned. It's probably cheaper to maintain data for pinned than unpinned as there's less of it on normal systems.

Quoted 2 lines

It's unpinned that load balancing can
actually migrate.

True but see previous comment.

Quoted 10 lines

Using the signed minimax pseudonorm (i.e. the highest
signed lag, where positive is higher than all negative regardless of magnitude) on unpinned lags yields a rather natural load balancing algorithm consisting of migrating from highest to lowest signed lag, with progressively longer periods for periodic balancing across progressively higher levels of hierarchy in sched_domains etc. as usual. Basically skip over pinned tasks as far as lag goes.

The trick with all that comes when tasks are pinned within a set of cpus (especially crossing sched_domains) instead of to a single cpu.

Yes, this makes the cost of maintaining the required data higher which makes keeping pinned data more attractive than unpinned.

BTW keeping data for sets of CPU affinities could cause problems as the number of possible sets is quite large (being 2 to the power of the number of CPUs). So you need an algorithm based on pinned data for single CPUs that knows the pinning isn't necessarily exclusive rather than one based on sets of CPUs. As I understand it (which may be wrong), the mechanism you describe below takes that approach.

Quoted 89 lines

There one can just consider a cpu to enter a periodic load balance cycle, and then consider pushing and pulling, perhaps what could be called the "exchange lags" for the pair of cpus. That would be the minimax lag pseudonorms for the tasks migratable to both cpus of the pair. That makes the notion of moving things from highest to lowest lag (where load is now considered) unambiguous apart from whether all this converges, but not when to actually try to load balance vs. when not to, or when it's urgent vs. when it should be done periodically.

To clarify that, an O(cpus**2) notion appears to be necessary, namely the largest exchange lag differential between any pair of cpus. There is also the open question of whether moving tasks between cpus with the highest exchange lag differential will actually reduce it or whether it runs the risk of increasing it by creating a larger exchange lag differential between different pairs of cpus. A similar open question is raised by localizing balancing decisions to sched_domains. What remains clear is that any such movement reduces the worst-case lag in the whole system. Because of that, the worst-case lag in the whole system monotonically decreases as balancing decisions are made, and that much is subject to an infinite descent argument. Unfortunately, determining the largest exchange lag differential appears to be more complex than merely finding the highest and lowest lags. Bipartite forms of the problem also arise from sched_domains.

I doubt anyone's really paying any sort of attention, so I'll not really bother working out much more in the way of details with respect to load balancing. It may be that there are better ways to communicate algorithmic notions than prose descriptions. However, it's doubtful I'll produce anything in a timely enough fashion to attract or hold interest.

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

task    nice    hier1   hier2   ...     hierN
t_1     w_n1    w_h11   w_h21   ...     w_hN1
t_2     w_n2    w_h12   w_h22   ...     w_hN2

...

For the example of nice 0 vs. nice 10 as distinct users with 10% steppings between nice levels, one would have

task    nice   hier1
t_1     1      1
t_2     0.3855 1

w_1, the weight of t_1, would be

        (w_h11*w_n1/(w_h11*w_n1 + w_h12*w_n2))
                = (1*1/(1 + 1*0.3855..))
                = 0.7217..
w_2, the weight of t_2, would be
        (w_h12*w_n2/(w_h11*w_n1 + w_h12*w_n2))
                = (1*0.3855../(1 + 1*0.3855..))
                = 0.27826..

This just so happens to work out to being the same as if t_1 and t_2 had their respective nice numbers without the scheduler grouping, which is basically what everyone wants to happen.

It's more obvious how to extend it to more tasks than levels of hierarchy. An example of that follows:

task    nice    hier1   hier2   ...     hierN
t_1     0.3     0.6     *       ...     *
t_2     0.7     0.4     *       ...     *

hier2 through hierN are ignorable since t_1 and t_2 are both the only members at those levels of hierarchy. We then get something just like the above example, w_1 = 0.3*0.6/(0.3*0.6+0.7*0.4) = 0.3913.. and w2 = 0.7*0.4/(0.3*0.6+0.7*0.4) = 0.6087..

It's more interesting with enough tasks to have more meaningful levels of hierarchy.

task    nice    hier1   hier2
t_1     0.7     0.6     0.6
t_2     0.3     0.6     0.4
t_3     0.7     0.4     0.6
t_4     0.3     0.4     0.4

where t_1 and t_2 share a hier1 grouping and t_3 and t_4 also share a hier1 grouping, but the hier1 grouping for t_1 and t_2 is distinct from the hier1 grouping for t_3 and t_4. All hier2 groupings are distinct. So t_1 would have pre-nice weight 0.6*0.6, t_2 0.6*0.4, t_3 0.6*0.4, and t_4 0.4*0.4 (the numbers were chosen so denominators conveniently collapse to 1). Now that the hierarchy is flattened, nice numbers can be factored in for t_1's final weight being 0.7*0.36/(0.7*0.36+0.3*0.24+0.7*0.24+0.3*0.16) = 0.252/0.54 = 0.467.. and the others being 0.133.. (t_2), 0.311.. (t_3), and 0.0889.. (t_4).

Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

Is it just me or did you stray from the topic of handling cpu affinity during load balancing to hierarchical load balancing? I couldn't see anything in the above explanation that would improve the handling of cpu affinity.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#23 lore raw
Quoted 1 line · William Lee Irwin III
Quoted 1 line

Lag should be considered in lieu of load because lag

Quoted 1 line · Peter Williams

What's the definition of lag here?

Lag is the deviation of a task's allocated CPU time from the CPU time it would be granted by the ideal fair scheduling algorithm (generalized processor sharing; take the limit of RR with per-task timeslices proportional to load weight as the scale factor approaches zero). Negative lag reflects receipt of excess CPU time. A close-to-canonical "fairness metric" is the maximum of the absolute values of the lags of all the tasks on the system. The "signed minimax pseudonorm" is the largest lag without taking absolute values; it's a term I devised ad hoc to describe the proposed algorithm.

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

is what the
scheduler is trying to minimize;

Quoted 2 lines · Peter Williams

This isn't always the case. Some may prefer fairness to minimal lag. Others may prefer particular tasks to receive preferential treatment.

This comment does not apply. Generalized processor sharing expresses preferential treatment via weighting. Various other forms of preferential treatment require more elaborate idealized models.

Quoted 3 lines
Quoted 3 lines

load is not directly relevant, but
appears to have some sort of relationship. Also, instead of pinned, unpinned should be considered.

Quoted 3 lines · Peter Williams

If you have total and pinned you can get unpinned. It's probably cheaper to maintain data for pinned than unpinned as there's less of it on normal systems.

Regardless of the underlying accounting, I've presented a coherent algorithm. It may be that there's no demonstrable problem to solve. On the other hand, if there really is a question as to how to load balance in the presence of tasks pinned to cpus, I just answered it.

Quoted 9 lines · William Lee Irwin III
Quoted 9 lines

Using the signed minimax pseudonorm (i.e. the highest
signed lag, where positive is higher than all negative regardless of magnitude) on unpinned lags yields a rather natural load balancing algorithm consisting of migrating from highest to lowest signed lag, with progressively longer periods for periodic balancing across progressively higher levels of hierarchy in sched_domains etc. as usual. Basically skip over pinned tasks as far as lag goes.
The trick with all that comes when tasks are pinned within a set of cpus (especially crossing sched_domains) instead of to a single cpu.

Quoted 8 lines · Peter Williams

Yes, this makes the cost of maintaining the required data higher which makes keeping pinned data more attractive than unpinned.
BTW keeping data for sets of CPU affinities could cause problems as the number of possible sets is quite large (being 2 to the power of the number of CPUs). So you need an algorithm based on pinned data for single CPUs that knows the pinning isn't necessarily exclusive rather than one based on sets of CPUs. As I understand it (which may be wrong), the mechanism you describe below takes that approach.

Yes, the mechanism I described takes that approach.

Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

[...]

Quoted 1 line
Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

Quoted 4 lines · Peter Williams

Is it just me or did you stray from the topic of handling cpu affinity during load balancing to hierarchical load balancing? I couldn't see anything in the above explanation that would improve the handling of cpu affinity.

There was a second issue raised to which I responded. I didn't stray per se. I addressed a second topic in the post.

-- wli

#24 lore raw
Quoted 10 lines · William Lee Irwin III
Quoted 1 line · William Lee Irwin III
Quoted 1 line

Lag should be considered in lieu of load because lag

Quoted 1 line · Peter Williams

What's the definition of lag here?

Lag is the deviation of a task's allocated CPU time from the CPU time it would be granted by the ideal fair scheduling algorithm (generalized processor sharing; take the limit of RR with per-task timeslices proportional to load weight as the scale factor approaches zero).

Over what time period does this operate?

Quoted 5 lines

Negative lag reflects receipt of excess CPU time. A close-to-canonical "fairness metric" is the maximum of the absolute values of the lags of all the tasks on the system. The "signed minimax pseudonorm" is the largest lag without taking absolute values; it's a term I devised ad hoc to describe the proposed algorithm.

So what you're saying is that you think dynamic priority (or its equivalent) should be used for load balancing instead of static priority?

Quoted 11 lines
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

is what the
scheduler is trying to minimize;

Quoted 1 line · Peter Williams

This isn't always the case. Some may prefer fairness to minimal lag. Others may prefer particular tasks to receive preferential treatment.

This comment does not apply. Generalized processor sharing expresses preferential treatment via weighting. Various other forms of preferential treatment require more elaborate idealized models.

This was said before I realized that your "lag" is just a measure of fairness.

Quoted 10 lines
Quoted 5 lines
Quoted 5 lines

load is not directly relevant, but
appears to have some sort of relationship. Also, instead of pinned, unpinned should be considered.

Quoted 1 line · Peter Williams

If you have total and pinned you can get unpinned. It's probably cheaper to maintain data for pinned than unpinned as there's less of it on normal systems.

Regardless of the underlying accounting,

I was just replying to your criticism of my suggestion to keep pinned task statistics and use them.

Quoted 4 lines

I've presented a coherent
algorithm. It may be that there's no demonstrable problem to solve. On the other hand, if there really is a question as to how to load balance in the presence of tasks pinned to cpus, I just answered it.

Unless I missed something there's nothing in your suggestion that does anything more about handling pinned tasks than is already done by the load balancer.

Quoted 24 lines
Quoted 9 lines · William Lee Irwin III
Quoted 9 lines

Using the signed minimax pseudonorm (i.e. the highest
signed lag, where positive is higher than all negative regardless of magnitude) on unpinned lags yields a rather natural load balancing algorithm consisting of migrating from highest to lowest signed lag, with progressively longer periods for periodic balancing across progressively higher levels of hierarchy in sched_domains etc. as usual. Basically skip over pinned tasks as far as lag goes.
The trick with all that comes when tasks are pinned within a set of cpus (especially crossing sched_domains) instead of to a single cpu.

Quoted 2 lines · Peter Williams

Yes, this makes the cost of maintaining the required data higher which makes keeping pinned data more attractive than unpinned.
BTW keeping data for sets of CPU affinities could cause problems as the number of possible sets is quite large (being 2 to the power of the number of CPUs). So you need an algorithm based on pinned data for single CPUs that knows the pinning isn't necessarily exclusive rather than one based on sets of CPUs. As I understand it (which may be wrong), the mechanism you describe below takes that approach.

Yes, the mechanism I described takes that approach.

Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

Quoted 8 lines

[...]

Quoted 1 line
Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

Quoted 1 line · Peter Williams

Is it just me or did you stray from the topic of handling cpu affinity during load balancing to hierarchical load balancing? I couldn't see anything in the above explanation that would improve the handling of cpu affinity.

There was a second issue raised to which I responded. I didn't stray per se. I addressed a second topic in the post.

OK.

To reiterate, I don't think that my suggestion is really necessary. I think that the current load balancing (stand fast a small bug that's being investigated) will come up with a good distribution of tasks to CPUs within the constraints imposed by any CPU affinity settings.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#25 lore raw
Quoted 4 lines · William Lee Irwin III
Quoted 4 lines

Lag is the deviation of a task's allocated CPU time from the CPU time it would be granted by the ideal fair scheduling algorithm (generalized processor sharing; take the limit of RR with per-task timeslices proportional to load weight as the scale factor approaches zero).

Quoted 1 line · Peter Williams

Over what time period does this operate?

Over a period of time while the task is runnable.

Quoted 5 lines · William Lee Irwin III
Quoted 5 lines

Negative lag reflects receipt of excess CPU time. A close-to-canonical "fairness metric" is the maximum of the absolute values of the lags of all the tasks on the system. The "signed minimax pseudonorm" is the largest lag without taking absolute values; it's a term I devised ad hoc to describe the proposed algorithm.

Quoted 2 lines · Peter Williams

So what you're saying is that you think dynamic priority (or its equivalent) should be used for load balancing instead of static priority?

It doesn't do much in other schemes, but when fairness is directly measured by the dynamic priority, it is a priori more meaningful. This is not to say the net effect of using it is so different.

Quoted 5 lines · William Lee Irwin III
Quoted 4 lines

I've presented a coherent
algorithm. It may be that there's no demonstrable problem to solve. On the other hand, if there really is a question as to how to load balance in the presence of tasks pinned to cpus, I just answered it.

Quoted 3 lines · Peter Williams

Unless I missed something there's nothing in your suggestion that does anything more about handling pinned tasks than is already done by the load balancer.

There are two things, both of which are relatively subtle and coincidentally happen to some extent. The first is the unpinned lag, which behaves much differently from unpinned load weight even if it's not so different in concept, but apparently achieves a similar result. The second is the relativistic point of view, which happens somewhat by coincidence anyway, but isn't formalized anywhere at all as a basis for handling tasks pinned to cpus. The first difference is minor and the second formalizing something that mostly or completely already happens.

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

There was a second issue raised to which I responded. I didn't stray per se. I addressed a second topic in the post.

Quoted 5 lines · Peter Williams

OK.
To reiterate, I don't think that my suggestion is really necessary. I think that the current load balancing (stand fast a small bug that's being investigated) will come up with a good distribution of tasks to CPUs within the constraints imposed by any CPU affinity settings.

It's sort of like performance. If the numbers are already good enough, my algorithm on that front need not be bothered with either.

-- wli

#26 lore raw
Quoted 6 lines · William Lee Irwin III
Quoted 1 line · Peter Williams

So what you're saying is that you think dynamic priority (or its equivalent) should be used for load balancing instead of static priority?

It doesn't do much in other schemes, but when fairness is directly measured by the dynamic priority, it is a priori more meaningful. This is not to say the net effect of using it is so different.

I suspect that while it's probably theoretically better it wouldn't make much difference on a real system (probably not enough to justify any extra complexity if there were any). The exception might be on systems where there were lots of CPU intensive tasks that used relatively large chunks of CPU each time they were runnable which would give the load balancer a more stable load to try and balance. It might be worth the extra effort to get it exactly right on those systems. On most normal systems this isn't the case and the load balancer is always playing catch up to a constantly changing scenario.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#27 lore raw
In reply to William Lee Irwin III
Quoted 49 lines · William Lee Irwin III

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

task    nice    hier1   hier2   ...     hierN
t_1     w_n1    w_h11   w_h21   ...     w_hN1
t_2     w_n2    w_h12   w_h22   ...     w_hN2

...

For the example of nice 0 vs. nice 10 as distinct users with 10% steppings between nice levels, one would have

task    nice   hier1
t_1     1      1
t_2     0.3855 1

w_1, the weight of t_1, would be

        (w_h11*w_n1/(w_h11*w_n1 + w_h12*w_n2))
                = (1*1/(1 + 1*0.3855..))
                = 0.7217..
w_2, the weight of t_2, would be
        (w_h12*w_n2/(w_h11*w_n1 + w_h12*w_n2))
                = (1*0.3855../(1 + 1*0.3855..))
                = 0.27826..

This just so happens to work out to being the same as if t_1 and t_2 had their respective nice numbers without the scheduler grouping, which is basically what everyone wants to happen.

It's more obvious how to extend it to more tasks than levels of hierarchy. An example of that follows:

task    nice    hier1   hier2   ...     hierN
t_1     0.3     0.6     *       ...     *
t_2     0.7     0.4     *       ...     *

hier2 through hierN are ignorable since t_1 and t_2 are both the only members at those levels of hierarchy. We then get something just like the above example, w_1 = 0.3*0.6/(0.3*0.6+0.7*0.4) = 0.3913.. and w2 = 0.7*0.4/(0.3*0.6+0.7*0.4) = 0.6087..

It's more interesting with enough tasks to have more meaningful levels of hierarchy.

task    nice    hier1   hier2
t_1     0.7     0.6     0.6
t_2     0.3     0.6     0.4
t_3     0.7     0.4     0.6
t_4     0.3     0.4     0.4
Quoted 9 lines

where t_1 and t_2 share a hier1 grouping and t_3 and t_4 also share a hier1 grouping, but the hier1 grouping for t_1 and t_2 is distinct from the hier1 grouping for t_3 and t_4. All hier2 groupings are distinct. So t_1 would have pre-nice weight 0.6*0.6, t_2 0.6*0.4, t_3 0.6*0.4, and t_4 0.4*0.4 (the numbers were chosen so denominators conveniently collapse to 1). Now that the hierarchy is flattened, nice numbers can be factored in for t_1's final weight being 0.7*0.36/(0.7*0.36+0.3*0.24+0.7*0.24+0.3*0.16) = 0.252/0.54 = 0.467.. and the others being 0.133.. (t_2), 0.311.. (t_3), and 0.0889.. (t_4).

Hmm ..so do you think this weight decomposition can be used to flatten the tree all the way to a single level in case of cfs? That would mean we can achieve group fairness with single level scheduling in cfs ..I am somewhat skeptical that we can achieve group fairness with a single level rb-tree (and w/o substantial changes to pick_next_task logic in cfs that is), but if it can be accomplished would definitely be a great win.

Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

Signature · 2 lines
Regards,
vatsa
#28 lore raw
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

The smpnice affair is better phrased in terms of task weighting. It's simple to honor nice in such an arrangement. First unravel the grouping hierarchy, then weight by nice. This looks like

[...]

Quoted 4 lines
Quoted 4 lines

conveniently collapse to 1). Now that the hierarchy is flattened, nice numbers can be factored in for t_1's final weight being 0.7*0.36/(0.7*0.36+0.3*0.24+0.7*0.24+0.3*0.16) = 0.252/0.54 = 0.467.. and the others being 0.133.. (t_2), 0.311.. (t_3), and 0.0889.. (t_4).

Quoted 6 lines · Srivatsa Vaddagiri

Hmm ..so do you think this weight decomposition can be used to flatten the tree all the way to a single level in case of cfs? That would mean we can achieve group fairness with single level scheduling in cfs ..I am somewhat skeptical that we can achieve group fairness with a single level rb-tree (and w/o substantial changes to pick_next_task logic in cfs that is), but if it can be accomplished would definitely be a great win.

Yes, the hierarchy can be flattened completely and global task weights computed and used to achieve group fairness. The changes aren't to pick_next_task() but rather to the ->fair_key computations. In fact, I went a step beyond that.

Quoted 1 line · William Lee Irwin III
Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

The step beyond was to show how nice numbers can be done with all that hierarchical task grouping so they have global effects instead of effects limited to the scope of the narrowest grouping hierarchy containing the task. I had actually assumed the weighting and flattening bits were already in your plans from some other post you made and was building upon that.

-- wli

#29 lore raw
Quoted 10 lines · William Lee Irwin III
Quoted 6 lines · Srivatsa Vaddagiri

Hmm ..so do you think this weight decomposition can be used to flatten the tree all the way to a single level in case of cfs? That would mean we can achieve group fairness with single level scheduling in cfs ..I am somewhat skeptical that we can achieve group fairness with a single level rb-tree (and w/o substantial changes to pick_next_task logic in cfs that is), but if it can be accomplished would definitely be a great win.

Yes, the hierarchy can be flattened completely and global task weights computed and used to achieve group fairness.

ok, lets say we are are considering a hierarchy of user->process->thread as below:

Users = {U1, U2, U3}

where process in a user are:

U1 = {P0, P1, P2, P3, P4}
U2 = {P5, P6}
U3 = {P7}

and where threads/tasks in a process are:

P0 = {T0, T1}
P1 = {T2}
P2 = {T3, T4, T5}
P3 = {T6}
P4 = {T8}
P5 = {T9, T10}
P6 = {T11}
P7 = {T14, T15, T16}

If we need to achieve group fairness given single-level hierarchy, then tasks need to be spread out in rb-tree like something below?

	     U1         U2         U3     U1         U2        U3
	|---------|---------|---------|---------|---------|---------|--- // ---
       t0	 t1	   t2	     t3	       t4	 t5        t6

[ t0, t1 ..tN are equally spaced points in time. t1 = t0 + K, t2 = t1 + K .. ]

Viewed at the top hierarchy level (users) tasks are spread such that each user gets "equal" execution over some interval (lets say b/n t0-t3).

When viewed at the next lower hierarchy level (processes), it should look like:

        |     U1    |    U2    |    U3    |     U1    |    U2    |    U3   |
	|	    |          |          |           |          |         |
	| P0  P1  P2| P5    P6 |    P7    | P3  P4 P0 | P5    P6 |    P7   |
	|---|---|---|----|-----|----------|---|---|---|----|-----|---------|-//-
	t0	   t1	      t2	 t3	t3'  t4	        t5        t6

[contd below ..]

        |     U1    |    U2    |    U3    |     U1    |    U2    |    U3   |
	|	    |          |          |           |          |         |
	| P1  P2  P3| P5    P6 |    P7    | P4  P0  P1| P5    P6 |    P7   |
  --//  |---|---|---|----|-----|----------|---|---|---|----|-----|---------|-//-
       t6	   t7	      t8	 t9	    t10	       t11       t12

The available bandwidth to a user is dividided "equally" between various processes of the user over some time (say between t0 - t3').

When viewed at the next lower hierarchy level (threads), it should look like:

        |     U1    |    U2    |    U3    |     U1    |    U2    |    U3    |
	|	    |          |          |           |          |          |
	| P0| P1| P2| P5 |  P6 |    P7    | P3| P4| P0| P5 |  P6 |    P7    |
        |   |   |   |    |     |    |     |   |   |   |    |     |    |     |  
	| T0| T2| T3| T9 | T11 | T14| T15 | T6| T8| T1| T10| T11 | T16| T14 |
        |---|---|---|----|-----|----|-----|---|---|---|----|-----|----|-----|-//
	t0	   t1	      t2	 t3	     t4	        t5         t6

(continuting below)

        |     U1    |    U2    |    U3    |     U1    |    U2    |    U3    |
	|	    |          |          |           |          |          |
	| P1| P2| P3| P5 |  P6 |    P7    | P4| P0| P1| P5 |  P6 |    P7    |
        |   |   |   |    |     |    |     |   |   |   |    |     |    |     |  
	| T2| T4| T6| T9 | T11 | T15| T16 | T8| T0|T2 | T10| T11 | T14| T14 |
   --// |---|---|---|----|-----|----|-----|---|---|---|----|-----|----|-----|-//
       t6	   t7	      t8	 t9	    t10	       t11        t12

Available bandwidth to a process is divided "equally" between threads of the process.

Although I have been using "equally" everywhere above, it needs to take into account relative importance of tasks/processes/users.

Quoted 2 lines

The changes aren't to pick_next_task() but rather to the ->fair_key computations.

Thats the $$ question I guess :) What computation of ->fair_key can we use such that task execution sequence is (from the above example):

	T0, T2, T3, T9, T11, T14, T15, T6, T8, T1, T10, T11, T16, T14 ...

?

Of course, this ->fair_key computation should default to what it is today when hierarchical res mgmt is disabled?

Quoted 4 lines

In fact, I went a step beyond that.

On Sat, May 26, 2007 at 08:41:12AM -0700, William Lee Irwin III wrote:

Quoted 8 lines
Quoted 1 line
Quoted 1 line

In such a manner nice numbers obey the principle of least surprise.

The step beyond was to show how nice numbers can be done with all that hierarchical task grouping so they have global effects instead of effects limited to the scope of the narrowest grouping hierarchy containing the task. I had actually assumed the weighting and flattening bits were already in your plans from some other post you made and was building upon that.

I would definitely be willing to try out any experiments you think of, esp those that allow the hierarchy to be flattened. atm fair_key calculation (in the context of cfs) seem to be the biggest challenge to surmount for this to work.

Signature · 2 lines
Regards,
vatsa
#30 lore raw
Quoted 6 lines · William Lee Irwin III
Quoted 6 lines

The step beyond was to show how nice numbers can be done with all that hierarchical task grouping so they have global effects instead of effects limited to the scope of the narrowest grouping hierarchy containing the task. I had actually assumed the weighting and flattening bits were already in your plans from some other post you made and was building upon that.

Quoted 4 lines · Srivatsa Vaddagiri

I would definitely be willing to try out any experiments you think of, esp those that allow the hierarchy to be flattened. atm fair_key calculation (in the context of cfs) seem to be the biggest challenge to surmount for this to work.

It's not all that tricky. The ->fair_key computations are already parametrized on load weights. The "task weights" here are just what Linux calls "load weight," so we're largely done once task weights are calculated.

The tricky part (if any) is essentially what you've already got nailed down, that is, creating and manipulating the accounting objects for the task groups or whatever you're calling them.

-- wli

#31 lore raw
Quoted 1 line · William Lee Irwin III

It's not all that tricky.

Hmm ..the fact that each task runs for a minimum of 1 tick seems to complicate the matters to me (when doing group fairness given a single level hierarchy). A user with 1000 (or more) tasks can be unduly advantaged compared to another user with just 1 (or fewer) task because of this?

Quoted 8 lines

The ->fair_key computations are already
parametrized on load weights. The "task weights" here are just what Linux calls "load weight," so we're largely done once task weights are calculated.

The tricky part (if any) is essentially what you've already got nailed down, that is, creating and manipulating the accounting objects for the task groups or whatever you're calling them.

Signature · 2 lines
Regards,
vatsa
#32 lore raw
Quoted 1 line · William Lee Irwin III
Quoted 1 line

It's not all that tricky.

Quoted 5 lines · Srivatsa Vaddagiri

Hmm ..the fact that each task runs for a minimum of 1 tick seems to complicate the matters to me (when doing group fairness given a single level hierarchy). A user with 1000 (or more) tasks can be unduly advantaged compared to another user with just 1 (or fewer) task because of this?

Temporarily, yes. All this only works when averaged out. The basic idea is that you want a constant upper bound on the difference between the CPU time a task receives and the CPU time it was intended to get. This discretization is one of the larger sources of the "error" in the CPU time granted. The constant upper bound usually only applies to the largest difference for any task. When absolute values of differences are summed across tasks the aggregate will be O(tasks) because there's something almost like a constant per-task lower bound a la Heisenberg. It would have to get more exact the more tasks there are on the system for that to work, and something of the opposite actually holds.

It might be appropriate for the scheduler to dynamically adjust a periodic timer's period or to set up one-shot timers at involuntary preemption times in order to achieve more precise fairness in this sort of situation. In the case of few preemption points such one-shot code or low periodicity code would also save on taking interrupts that would otherwise manifest as overhead.

In short, a user with many tasks can reap a temporary advantage relative to users with fewer tasks because of this, but over time, longer-running tasks will receive the CPU time intended to within some constant upper bound, provided other things aren't broken.

-- wli

#33 lore raw
Quoted 8 lines · William Lee Irwin III
Quoted 5 lines · Srivatsa Vaddagiri

Hmm ..the fact that each task runs for a minimum of 1 tick seems to complicate the matters to me (when doing group fairness given a single level hierarchy). A user with 1000 (or more) tasks can be unduly advantaged compared to another user with just 1 (or fewer) task because of this?

Temporarily, yes. All this only works when averaged out.

So essentially when we calculate delta_mine component for each of those 1000 tasks, we will find that it has executed for 1 tick (4 ms say) but its fair share was very very low.

	fair_share = delta_exec * p->load_weight / total_weight

If p->load_weight has been calculated after factoring in hierarchy (as you outlined in a previous mail), then p->load_weight of those 1000 tasks will be far less compared to the p->load_weight of one task belonging to other user, correct? Just to make sure I get all this correct:

User U1 has tasks T0 - T999
User U2 has task T1000

assuming each task's weight is 1 and each user's weight is 1 then:

	WT0 = (WU1 / WU1 + WU2) * (WT0 / WT0 + WT1 + ... + WT999)
	    = (1 / 1 + 1) * (1 / 1000)
	    = 1/2000
	    = 0.0005

	WT1 ..WT999 will be same as WT0

whereas, weight of T1000 will be:

	WT1000 	= (WU1 / WU1 + WU2) * (WT1000 / WT1000)
		= (1 / 1 + 1) * (1/1)
		= 0.5

?

So when T0 (or T1 ..T999) executes for 1 tick (4ms), their fair share would be:

	T0's fair_share (delta_mine)
			= 4 ms * 0.0005 / (0.0005 * 1000 + 0.5)
			= 4 ms * 0.0005 / 1
			= 0.002 ms (2000 ns)

This would cause T0's ->wait_runtime to go negative sharply, causing it to be inserted back in rb-tree well ahead in future. One change I can forsee in CFS is with regard to limit_wait_runtime() ..We will have to change its default limit, atleast when group fairness thingy is enabled.

Compared to this when T1000 executes for 1 tick, its fair share would be calculated as:

	T1000's fair_share (delta_mine)
				= 4 ms * 0.5 / (0.0005 * 1000 + 0.5)
				= 4 ms * 0.5 / 1
				= 2 ms (2000000 ns)

Its ->wait_runtime will drop less significantly, which lets it be inserted in rb-tree much to the left of those 1000 tasks (and which indirectly lets it gain back its fair share during subsequent schedule cycles).

Hmm ..is that the theory?

Ingo, do you have any comments on this approach?

/me is tempted to try this all out.

Quoted 22 lines

The basic
idea is that you want a constant upper bound on the difference between the CPU time a task receives and the CPU time it was intended to get. This discretization is one of the larger sources of the "error" in the CPU time granted. The constant upper bound usually only applies to the largest difference for any task. When absolute values of differences are summed across tasks the aggregate will be O(tasks) because there's something almost like a constant per-task lower bound a la Heisenberg. It would have to get more exact the more tasks there are on the system for that to work, and something of the opposite actually holds.

It might be appropriate for the scheduler to dynamically adjust a periodic timer's period or to set up one-shot timers at involuntary preemption times in order to achieve more precise fairness in this sort of situation. In the case of few preemption points such one-shot code or low periodicity code would also save on taking interrupts that would otherwise manifest as overhead.

In short, a user with many tasks can reap a temporary advantage relative to users with fewer tasks because of this, but over time, longer-running tasks will receive the CPU time intended to within some constant upper bound, provided other things aren't broken.

Signature · 2 lines
Regards,
vatsa
#34 lore raw
Quoted 1 line · William Lee Irwin III
Quoted 1 line

Temporarily, yes. All this only works when averaged out.

Quoted 8 lines · Srivatsa Vaddagiri

So essentially when we calculate delta_mine component for each of those 1000 tasks, we will find that it has executed for 1 tick (4 ms say) but its fair share was very very low.

	fair_share = delta_exec * p->load_weight / total_weight

If p->load_weight has been calculated after factoring in hierarchy (as you outlined in a previous mail), then p->load_weight of those 1000 tasks will be far less compared to the p->load_weight of one task belonging to other user, correct? Just to make sure I get all this correct:

You've got it all correct.

Quoted 12 lines · Srivatsa Vaddagiri

User U1 has tasks T0 - T999
User U2 has task T1000
assuming each task's weight is 1 and each user's weight is 1 then:

	WT0 = (WU1 / WU1 + WU2) * (WT0 / WT0 + WT1 + ... + WT999)
	    = (1 / 1 + 1) * (1 / 1000)
	    = 1/2000
	    = 0.0005
	WT1 ..WT999 will be same as WT0
whereas, weight of T1000 will be:
	WT1000 	= (WU1 / WU1 + WU2) * (WT1000 / WT1000)
		= (1 / 1 + 1) * (1/1)
		= 0.5
Quoted 1 line

?

Yes, these calculations are correct.

Quoted 12 lines · Srivatsa Vaddagiri

So when T0 (or T1 ..T999) executes for 1 tick (4ms), their fair share would be:

	T0's fair_share (delta_mine)
			= 4 ms * 0.0005 / (0.0005 * 1000 + 0.5)
			= 4 ms * 0.0005 / 1
			= 0.002 ms (2000 ns)

This would cause T0's ->wait_runtime to go negative sharply, causing it to be inserted back in rb-tree well ahead in future. One change I can forsee in CFS is with regard to limit_wait_runtime() ..We will have to change its default limit, atleast when group fairness thingy is enabled. Compared to this when T1000 executes for 1 tick, its fair share would be calculated as:

Quoted 7 lines
	T1000's fair_share (delta_mine)
				= 4 ms * 0.5 / (0.0005 * 1000 + 0.5)
				= 4 ms * 0.5 / 1
				= 2 ms (2000000 ns)

Its ->wait_runtime will drop less significantly, which lets it be inserted in rb-tree much to the left of those 1000 tasks (and which indirectly lets it gain back its fair share during subsequent schedule cycles).

This analysis is again entirely correct.

Quoted 3 lines · Srivatsa Vaddagiri

Hmm ..is that the theory?
Ingo, do you have any comments on this approach?
/me is tempted to try this all out.

Yes, this is the theory behind using task weights to flatten the task group hierarchies. My prior post assumed all this and described a method to make nice numbers behave as expected in the global context atop it.

-- wli

#35 lore raw
In reply to Srivatsa Vaddagiri
Quoted 5 lines · Srivatsa Vaddagiri

Its ->wait_runtime will drop less significantly, which lets it be inserted in rb-tree much to the left of those 1000 tasks (and which indirectly lets it gain back its fair share during subsequent schedule cycles).

Hmm ..is that the theory?

My only concern is the time needed to converge to this fair distribution, especially in face of fluctuating workloads. For ex: a container who does a fork bomb can have a very adverse impact on other container's fair share under this scheme compared to other schemes which dedicate separate rb-trees for differnet containers (and which also support two level hierarchical scheduling inside the core scheduler).

I am inclined to have the core scheduler support atleast two levels of hierarchy (to better isolate each container) and resort to the flattening trick for higher levels.

Signature · 2 lines
Regards,
vatsa
#36 lore raw
Quoted 5 lines · Srivatsa Vaddagiri
Quoted 5 lines

Its ->wait_runtime will drop less significantly, which lets it be inserted in rb-tree much to the left of those 1000 tasks (and which indirectly lets it gain back its fair share during subsequent schedule cycles).
Hmm ..is that the theory?

Quoted 10 lines · Srivatsa Vaddagiri

My only concern is the time needed to converge to this fair distribution, especially in face of fluctuating workloads. For ex: a container who does a fork bomb can have a very adverse impact on other container's fair share under this scheme compared to other schemes which dedicate separate rb-trees for differnet containers (and which also support two level hierarchical scheduling inside the core scheduler).
I am inclined to have the core scheduler support atleast two levels of hierarchy (to better isolate each container) and resort to the flattening trick for higher levels.

Yes, the larger number of schedulable entities and hence slower convergence to groupwise weightings is a disadvantage of the flattening. A hybrid scheme seems reasonable enough. Ideally one would chop the hierarchy in pieces so that n levels of hierarchy become k levels of n/k weight-flattened hierarchies for this sort of attack to be most effective (at least assuming similar branching factors at all levels of hierarchy and sufficient depth to the hierarchy to make it meaningful) but this is awkward to do. Peeling off the outermost container or whichever level is deemed most important in terms of accuracy of aggregate enforcement as a hierarchical scheduler is a practical compromise.

Hybrid schemes will still incur the difficulties of hierarchical scheduling, but they're by no means insurmountable. Sadly, only complete flattening yields the simplifications that make task group weighting enforcement orthogonal to load balancing and the like. The scheme I described for global nice number behavior is also not readily adaptable to hybrid schemes.

-- wli

#37 lore raw
Quoted 3 lines · William Lee Irwin III

Yes, the larger number of schedulable entities and hence slower convergence to groupwise weightings is a disadvantage of the flattening. A hybrid scheme seems reasonable enough.

Cool! This puts me back on track to implement hierarchical scheduling in CFS :)

Once this is done and once I can get containers running on a box, I will experiment with the flattening trick for user and process levels inside containers.

Thanks for your feedback so far!

Quoted 15 lines

Ideally one would chop the
hierarchy in pieces so that n levels of hierarchy become k levels of n/k weight-flattened hierarchies for this sort of attack to be most effective (at least assuming similar branching factors at all levels of hierarchy and sufficient depth to the hierarchy to make it meaningful) but this is awkward to do. Peeling off the outermost container or whichever level is deemed most important in terms of accuracy of aggregate enforcement as a hierarchical scheduler is a practical compromise.

Hybrid schemes will still incur the difficulties of hierarchical scheduling, but they're by no means insurmountable. Sadly, only complete flattening yields the simplifications that make task group weighting enforcement orthogonal to load balancing and the like. The scheme I described for global nice number behavior is also not readily adaptable to hybrid schemes.

Signature · 2 lines
Regards,
vatsa
#38 lore raw
In reply to Peter Williams
Quoted 3 lines · Peter Williams

I don't think that ignoring cpu affinity is an option. Setting the cpu affinity of tasks is a deliberate policy action on the part of the system administrator and has to be honoured.

mmm ..but users can set cpu affinity w/o administrator priveleges ..

Signature · 2 lines
Regards,
vatsa
#39 lore raw
Quoted 5 lines · Srivatsa Vaddagiri
Quoted 1 line · Peter Williams

I don't think that ignoring cpu affinity is an option. Setting the cpu affinity of tasks is a deliberate policy action on the part of the system administrator and has to be honoured.

mmm ..but users can set cpu affinity w/o administrator priveleges ..

OK. So you have to assume the users know what they're doing. :-)

In reality though, the policy of allowing ordinary users to set affinity on their tasks should be rethought.

In any case, there's no point having cpu affinity if it's going to be ignored. Maybe you could have two levels of affinity: 1. if set by a root it must be obeyed; and 2. if set by an ordinary user it can be overridden if the best interests of the system dictate. BUT I think that would be a bad idea.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#40 lore raw
Quoted 6 lines · Peter Williams

In any case, there's no point having cpu affinity if it's going to be ignored. Maybe you could have two levels of affinity: 1. if set by a root it must be obeyed; and 2. if set by an ordinary user it can be overridden if the best interests of the system dictate. BUT I think that would be a bad idea.

Something like that already exists (at least for controlling the bounding set of allowed cpus) via cpusets.

Paul

#41 lore raw
In reply to Peter Williams
Quoted 10 lines · Peter Williams
Quoted 5 lines · Srivatsa Vaddagiri
Quoted 1 line · Peter Williams

I don't think that ignoring cpu affinity is an option. Setting the cpu affinity of tasks is a deliberate policy action on the part of the system administrator and has to be honoured.

mmm ..but users can set cpu affinity w/o administrator priveleges ..

OK. So you have to assume the users know what they're doing. :-)

In reality though, the policy of allowing ordinary users to set affinity on their tasks should be rethought.

After more contemplation, I now think I may have gone overboard here. I am now of the opinion that any degradation of overall system performance due to the use of cpu affinity would be confined to the tasks with cpu affinity set. So there's no need to prevent ordinary users from setting cpu affinity on their own processes as any degradation will only affect them.

So it goes back to the situation where you have to assume that they know what they're doing and obey their policy.

Quoted 2 lines

In any case, there's no point having cpu affinity if it's going to be ignored. Maybe you could have two levels of affinity: 1. if set by a root it must be obeyed; and 2. if set by an ordinary user it can be overridden if the best interests of the system dictate. BUT I think that would be a bad idea.

This idea is now not just bad but unnecessary.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#42 lore raw
In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

Can you repeat your tests with this patch pls? With the patch applied, I am now getting the same split between nice 0 and nice 10 task as CFS-v13 provides (90:10 as reported by top )

Yep, this fixes the problem for me too.

Thanks.

Signature · 1 line
Guillaume

A message that is not in the archive (sent off-list or not yet received): [email protected]

#44 lore raw
Quoted 1 line · William Lee Irwin III

Well, SMP load balancing is what makes all this hard.

Agreed. I am optimistic that we can achieve good degree of SMP fairness using similar mechanism as smpnice ..

Quoted 8 lines · Srivatsa Vaddagiri
Quoted 4 lines

Salient points which needs discussion:
1. This patch reuses CFS core to achieve fairness at group level also. To make this possible, CFS core has been abstracted to deal with generic schedulable "entities" (tasks, users etc).

The ability to handle deeper hierarchies would be useful for those who want such semantics.

sure, although the more levels of hierarchy scheduler recoginizes, more the (accounting/scheduling) cost is!

Quoted 6 lines · Srivatsa Vaddagiri
Quoted 4 lines

2. The per-cpu rb-tree has been split to be per-group per-cpu. schedule() now becomes two step on every cpu : pick a group first (from group rb-tree) and a task within that group next (from that group's task rb-tree)

Quoted 7 lines

That assumes per-user scheduling groups; other configurations would make it one step for each level of hierarchy. It may be possible to reduce those steps to only state transitions that change weightings and incremental updates of task weightings. By and large, one needs the groups to determine task weightings as opposed to hierarchically scheduling, so there are alternative ways of going about this, ones that would even make load balancing easier.

Yeah I agree that providing hierarchical group-fairness at the cost of single (or fewer) scheduling levels would be a nice thing to target for, although I don't know of any good way to do it. Do you have any ideas here? Doing group fairness in a single level, using a common rb-tree for tasks from all groups is very difficult IMHO. We need atleast two levels.

One possibility is that we recognize deeper hierarchies only in user-space, but flatten this view from kernel perspective i.e some user space tool will have to distributed the weights accordingly in this flattened view to the kernel.

Quoted 10 lines · Srivatsa Vaddagiri
Quoted 4 lines

3. Grouping mechanism - I have used 'uid' as the basis of grouping for timebeing (since that grouping concept is already in mainline today). The patch can be adapted to a more generic process grouping mechanism (like http://lkml.org/lkml/2007/4/27/146) later.

I'd like to see how desirable the semantics achieved by reflecting more of the process hierarchy structure in the scheduler groupings are. Users, sessions, pgrps, and thread_groups would be the levels of hierarchy there, where some handling of orphan pgrps is needed.

Good point. Essentially all users should get fair cpu first, then all sessions/pgrps under a user should get fair share, followed by process-groups under a session, followed by processes in a process-group, followed by threads in a process (phew) .. ?

The container patches by Paul Menage at http://lkml.org/lkml/2007/4/27/146
provide a generic enough mechanism to group tasks in a hierarchical manner for each resource controller. For ex: for the cpu controller, if the desired fairness is as per the above scheme (user/session/pgrp/threads etc), then it is possible to write a script which creates such a tree under cpu controller filesystem:

	# mkdir /dev/cpuctl
	# mount -t container -o cpuctl none /dev/cpuctl

/dev/cpuctl is the cpu controller filesystem which can look like this:

	/dev/cpuctl
		|----uid root
		|       |-- sid 10
		|	|      |------ pgrp 20
		| 	|      | 	  |-- process 100
		|	|      |          |-- process 101
		|	|      |          |
		|       |
		|	|-- sid 11
		|
		|--- uid guest

(If the cpu controller really supports those many levels that is!)

user scripts can be written to modify this filesystem tree upon every login/session/user creation (if that is possible to trap on). Essentially it lets this semantics (what you ask) be dynamic/tunable by user.

Quoted 2 lines

Kernel compiles are markedly poor benchmarks. Try lat_ctx from lmbench, VolanoMark, AIM7, OAST, SDET, and so on.

Thanks for this list of tests. I intend to run all of them if possible for my next version.

Signature · 2 lines
Regards,
vatsa
#45 lore raw
Quoted 15 lines · Srivatsa Vaddagiri
Quoted 8 lines

That assumes per-user scheduling groups; other configurations would make it one step for each level of hierarchy. It may be possible to reduce those steps to only state transitions that change weightings and incremental updates of task weightings. By and large, one needs the groups to determine task weightings as opposed to hierarchically scheduling, so there are alternative ways of going about this, ones that would even make load balancing easier.

Yeah I agree that providing hierarchical group-fairness at the cost of single (or fewer) scheduling levels would be a nice thing to target for, although I don't know of any good way to do it. Do you have any ideas here? Doing group fairness in a single level, using a common rb-tree for tasks from all groups is very difficult IMHO. We need atleast two levels.

Quoted 4 lines

One possibility is that we recognize deeper hierarchies only in user-space, but flatten this view from kernel perspective i.e some user space tool will have to distributed the weights accordingly in this flattened view to the kernel.

Nice work, Vatsa. When I wrote the DWRR algorithm, I flattened the hierarchies into one level, so maybe that approach can be applied to your code as well. What I did is to maintain task and task group weights and reservations separately from the scheduler, while the scheduler only sees one system-wide weight per task and does not concern about which group a task is in. The key here is the system-wide weight of each task should represent an equivalent share to the share represented by the group hierarchies. To do this, the scheduler looks up the task and group weights/reservations it maintains, and dynamically computes the system-wide weight *only* when it need a weight for a given task while scheduling. The on-demand weight computation makes sure the cost is small (constant time). The computation itself can be seen from an
example: assume we have a group of two tasks and the group's total share is represented by a weight of 10. Inside the group, let's say the two tasks, P1 and P2, have weights 1 and 2. Then the system-wide weight for P1 is 10/3 and the weight for P2 is 20/3. In essence, this flattens weights into one level without changing the shares they represent.

tong

#46 lore raw
Quoted 9 lines · Tong N

Nice work, Vatsa. When I wrote the DWRR algorithm, I flattened the hierarchies into one level, so maybe that approach can be applied to your code as well. What I did is to maintain task and task group weights and reservations separately from the scheduler, while the scheduler only sees one system-wide weight per task and does not concern about which group a task is in. The key here is the system-wide weight of each task should represent an equivalent share to the share represented by the group hierarchies. To do this, the scheduler looks up the task and group weights/reservations it maintains, and dynamically computes the

Quoted 8 lines

system-wide weight *only* when it need a weight for a given task while scheduling. The on-demand weight computation makes sure the cost is small (constant time). The computation itself can be seen from an
example: assume we have a group of two tasks and the group's total share is represented by a weight of 10. Inside the group, let's say the two tasks, P1 and P2, have weights 1 and 2. Then the system-wide weight for P1 is 10/3 and the weight for P2 is 20/3. In essence, this flattens weights into one level without changing the shares they represent.

What do these task weights control? Timeslice primarily? If so, I am not sure how well it can co-exist with cfs then (unless you are planning to replace cfs with a equally good interactive/fair scheduler :)

I would be very interested if this weight calculation can be used for smpnice based load balancing purposes too ..

Signature · 2 lines
Regards,
vatsa
#47 lore raw
Quoted 9 lines · Srivatsa Vaddagiri
Quoted 4 lines · Tong N

is represented by a weight of 10. Inside the group, let's say the two tasks, P1 and P2, have weights 1 and 2. Then the system-wide weight for P1 is 10/3 and the weight for P2 is 20/3. In essence, this flattens weights into one level without changing the shares they represent.

What do these task weights control? Timeslice primarily? If so, I am not sure how well it can co-exist with cfs then (unless you are planning to replace cfs with a equally good interactive/fair scheduler :)

It's called SD. From Con Kolivas that got it right the first time around :)

Quoted 2 lines

I would be very interested if this weight calculation can be used for smpnice based load balancing purposes too ..

bill

#48 lore raw
In reply to Srivatsa Vaddagiri
Quoted 5 lines · Srivatsa Vaddagiri

What do these task weights control? Timeslice primarily? If so, I am not sure how well it can co-exist with cfs then (unless you are planning to replace cfs with a equally good interactive/fair scheduler :) I would be very interested if this weight calculation can be used for smpnice based load balancing purposes too ..

Task weights represent shares of CPU bandwidth. If task i has weight w_i then its share of CPU bandwidth is intended to be w_i/sum_i w_i.

"Load weight" seems to be used more in the scheduler source.

-- wli