Fair-user scheduler

Current Linux CPU scheduler doesnt recognize process aggregates while allocating bandwidth. As a result of this, an user could simply spawn large number of processes and get more bandwidth than others.

Here's a patch that provides fair allocation for all users in a system.

Some benchmark numbers with and without the patch applied follows:

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

2.6.20-rc5 472.07s (real) 257.48s (real)
2.6.20-rc5+fairsched 766.74s (real) 766.73s (real)

(Numbers taken on a 2way Intel x86_64 box)

Eventually something like this can be extended to do weighted fair share scheduling for:

- KVM
- containers
- resource management

Salient features of the patch:

- Based on Ingo's RTLIMIT_RT_CPU patch [1]. Primary difference between RTLIMIT_RT_CPU patch and this one is that this patch handles starvation of lower priority tasks in a group and also accounting is token based (rather than decaying avg).

- Retains existing one-runqueue-per-cpu design

- breaks O(1) (ouch!)
Best way to avoid this is to split runqueue to be per-user and per-cpu, which I have not implemented to keep the patch simple.

- Fairsched aware SMP load balance NOT addressed (yet)

Comments/flames wellcome!

References:

1. http://kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm2/broken-out/rlimit_rt_cpu.patch

Regards,
vatsa

This patch does several things:

- Introduces the notion of control window (current set at 1 sec - ideally the window size should be adjusted based on number of users to avoid rapid context switches). Bandwidth of each user is controlled within this window. rq->last_update tracks where are in the current window.

- Modifies scheduler_tick() to account cpu bandwidth consumption by a task group. Basically bandwidth consumed by a task is charged to itself (p->time_slice) -and- to its group as well.

- A task is forced off the CPU once its group has expired the bandwidth in the current control window. Such a task is also marked as "starving".

- schedule() avoids picking tasks whose group has expired its bandwidth in current control window. Any task (with non-zero p->timeslice) which is not picked to run in schedule() because of this reason is marked "starving".

- If a group has bandwidth left and it has starving tasks, then schedule() prefers picking such tasks over non-starving tasks. This will avoid starvation of lower-priority tasks in a group.

---

diff -puN include/linux/sched.h~cpu-controller-based-on-rtlimit_rt_cpu-patch include/linux/sched.h
@@ -531,6 +531,10 @@ struct signal_struct {
 #define is_rt_policy(p)		((p) != SCHED_NORMAL && (p) != SCHED_BATCH)
 #define has_rt_policy(p)	unlikely(is_rt_policy((p)->policy))
 
+#ifdef CONFIG_FAIRSCHED
+struct cpu_usage;
+#endif
+
 /*
  * Some day this will be a full-fledged user tracking system..
  */

@@ -555,6 +559,10 @@ struct user_struct {
 	/* Hash table maintenance information */
 	struct list_head uidhash_list;
 	uid_t uid;
+#ifdef CONFIG_FAIRSCHED
+	int cpu_limit;
+	struct cpu_usage *cpu_usage;
+#endif
 };
 
 extern struct user_struct *find_user(uid_t);

@@ -1137,6 +1145,9 @@ static inline void put_task_struct(struc
 					/* Not implemented yet, only for 486*/
 #define PF_STARTING	0x00000002	/* being created */
 #define PF_EXITING	0x00000004	/* getting shut down */
+#ifdef CONFIG_FAIRSCHED
+#define PF_STARVING	0x00000010      /* Task starving for CPU */
+#endif
 #define PF_FORKNOEXEC	0x00000040	/* forked but didn't exec */
 #define PF_SUPERPRIV	0x00000100	/* used super-user privileges */
 #define PF_DUMPCORE	0x00000200	/* dumped core */

_

Regards,
vatsa

The patch below makes the control window size configurable (as a macro), sets the default window size at 10 sec and also fixes a compile error (for !CONFIG_FAIRSCHED case).

Ideally the window size needs to be determined at run time (based on number of users). I will address that if there is sufficient interest on a patch like this ..

---

diff -puN kernel/sched.c~window-fix kernel/sched.c
@@ -769,17 +769,24 @@ static inline int is_user_starving(struc
 	return 0;
 }
 
-/* Are we past the 1-sec control window? If so, all groups get to renew their
+#define WINDOW_SIZE	(10*HZ)
+
+/* Are we past the control window? If so, all groups get to renew their
  * expired tokens.
  */
-static inline void adjust_control_window(void)
+static inline void adjust_control_window(int force)
 {
 	struct rq *rq = this_rq();
 	unsigned long delta;
 
+	if (force) {
+		rq->last_update = jiffies;
+		return;
+	}
+
 	delta = jiffies - rq->last_update;
-	if (delta >= HZ)
-		rq->last_update += (delta/HZ) * HZ;
+	if (delta >= WINDOW_SIZE)
+		rq->last_update += (delta/WINDOW_SIZE) * WINDOW_SIZE;
 }
 
 /* Account group's cpu usage */

@@ -788,7 +795,7 @@ static inline void inc_cpu_usage(struct 
 	struct user_struct *user = p->user;
 	struct cpu_usage *cu;
 
-	adjust_control_window();
+	adjust_control_window(0);
 
 	if (!user->cpu_limit)
 		return;

@@ -803,7 +810,7 @@ static inline int task_over_cpu_limit(st
 	struct user_struct *user = p->user;
 	struct cpu_usage *cu;
 
-	adjust_control_window();
+	adjust_control_window(0);
 
 	if (!user->cpu_limit)
 	 	return 0;

@@ -811,7 +818,7 @@ static inline int task_over_cpu_limit(st
 	cu = per_cpu_ptr(user->cpu_usage, task_cpu(p));
 	if (cu->last_update != rq->last_update) {
 		/* Replenish tokens */
-		cu->tokens += user->cpu_limit * HZ / 100;
+		cu->tokens += user->cpu_limit * WINDOW_SIZE / 100;
 		cu->last_update = rq->last_update;
 	}
 

@@ -830,6 +837,7 @@ static int task_over_cpu_limit(struct ta
 static void set_tsk_starving(struct task_struct *p) { }
 static void clear_tsk_starving(struct task_struct *p) { }
 static int is_user_starving(struct task_struct *p) { return 0;}
+static inline void adjust_control_window(int force) { }
 
 #endif		/* CONFIG_FAIRSCHED */
 

@@ -3668,7 +3676,7 @@ pick_next_task:
 	}
 
 	if (task_over_cpu_limit(next))
-		rq->last_update = jiffies;
+		adjust_control_window(1);
 	if (!next->time_slice)
 		next->time_slice = task_timeslice(next);
 	clear_tsk_starving(next);

_

Regards,
vatsa

This patch tracks number of users in a system and divides cpu bandwidth equally among them.

---

diff -puN include/linux/sched.h~user-interface include/linux/sched.h
@@ -533,7 +533,18 @@ struct signal_struct {
 
 #ifdef CONFIG_FAIRSCHED
 struct cpu_usage;
-#endif
+
+int sched_alloc_user(struct user_struct *user);
+void sched_free_user(struct user_struct *user);
+void sched_move_task(void);
+
+#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(void) { }
+
+#endif /* CONFIG_FAIRSCHED */
 
 /*
  * Some day this will be a full-fledged user tracking system..

@@ -562,6 +573,7 @@ struct user_struct {
 #ifdef CONFIG_FAIRSCHED
 	int cpu_limit;
 	struct cpu_usage *cpu_usage;
+	struct list_head fair_sched_list;
 #endif
 };
 

diff -puN kernel/user.c~user-interface kernel/user.c
@@ -51,6 +51,10 @@ struct user_struct root_user = {
 	.uid_keyring	= &root_user_keyring,
 	.session_keyring = &root_session_keyring,
 #endif
+#ifdef CONFIG_FAIRSCHED
+	.cpu_limit = 0,		/* No limit */
+	.fair_sched_list = LIST_HEAD_INIT(root_user.fair_sched_list),
+#endif
 };
 
 /*

@@ -112,6 +116,7 @@ void free_uid(struct user_struct *up)
 	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 +158,8 @@ struct user_struct * alloc_uid(uid_t uid
 			return NULL;
 		}
 
+		sched_alloc_user(new);
+
 		/*
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..

@@ -163,6 +170,7 @@ struct user_struct * alloc_uid(uid_t uid
 			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;

@@ -186,6 +194,7 @@ void switch_uid(struct user_struct *new_
 	atomic_inc(&new_user->processes);
 	atomic_dec(&old_user->processes);
 	switch_uid_keyring(new_user);
+	sched_move_task();
 	current->user = new_user;
 
 	/*

diff -puN init/Kconfig~user-interface init/Kconfig
@@ -249,6 +249,13 @@ config CPUSETS
 
 	  Say N if unsure.
 
+config FAIRSCHED
+	bool "Fair user CPU scheduler"
+	depends on EXPERIMENTAL
+	help
+	  This options lets you allocate equal cpu bandwidth to each
+	  non-root user.
+
 config SYSFS_DEPRECATED
 	bool "Create deprecated sysfs files"
 	default y

_

Regards,
vatsa

Srivatsa,

1. If I interpret these numbers correctly, then your scheduler is not work-conservative, i.e. 766.74 + 766.73 >> 472.07 + 257.48
why does it slow down users so much?
2. compilation of kernel is quite CPU-bound task. So it's not that hard to be fair :) Can you please try some other applications?
e.g. pipe-based context switching, java Volano benchmark etc.

Thanks,
Kirill

You can't measure work-conservation by summing! Everything is ran _concurrently_. A proof of losing computing power is to show "MAX(new_algorithm execution_times) > MAX(old_algorithm execution_times)". Anyway... it still seems lots of power is lost: MAX(766,766) >> MAX(472,257).

Actually, I'd be very interested by a "fairness number" and believe so far no one as proposed such thing. Probably needs to take into account the loss of CPU power and the variance of execution time in between the sets of tasks which are supposed to be fair.

Another worthy benchmark would be :
(make -s -j4 bzImage) vs (nice make -s -j20 bzImage)

                          ^^^^

Regards,
Eric

Ok, I investigated this a bit. The "1-sec" control window was the killer. I guess it was causing too much of thrashing. I increased the control window to 10 sec [1] and I get decent results now.

NOTE : Since the patches don't support SMP load-balancing currently, all benchmarks were run on only ONE cpu (using cpuset's cpu_exclusive feature) and hence the numbers are indicative of UP performance.

First, results of kernel compilation:

-------------------------------------------------------------------------------
vatsa guest
(make -j4 bzImage) (make -j20 bzImage)
-------------------------------------------------------------------------------

2.6.20-rc5 767.16s (real) 495.98s (real)
2.6.20-rc5 + fairsched (W=10s) 765.89s (real) 764.89s (real)

-------------------------------------------------------------------------------

-------------------------------------------------------------------------------
vatsa guest
(make -j4 bzImage) (nice make -j20 bzImage)
-------------------------------------------------------------------------------

2.6.20-rc5 767.16s (real) 636.51s (real)
2.6.20-rc5 + fairsched (W=10s) 761.19s (real) 766.51s (real)

-------------------------------------------------------------------------------

Second, results of volanomark benchmark [2].

Both users, vatsa and guest, ran a copy of volano server on different ports. Each user then launched the volano client on respective ports and throughput of the client was measured. Ideally we want the throughput to be same for both user.

-------------------------------------------------------------------------------
vatsa guest
(volano server/client) (volano server/client)
-------------------------------------------------------------------------------

2.6.20-rc5 400000 msg in 39.495s 400000 msg in 39.528s

				      (10128 msg/sec)	      (10119 msg/sec)

2.6.20-rc5 + fairsched (W=10s) 400000 msg in 39.662s 400000 msg in 39.646s

				      (10085 msg/sec)	      (10089 msg/sec)

-------------------------------------------------------------------------------

Here we dont see much difference between vanilla kernel and the patch because number of threads spawned by both users are same.

Kirill, did you have any other specific volano configuration in mind?

Yeah, in my patch, I dont account/limit execution time of root tasks at all. That needs to be factored in when we distribute left over cycles to non-root users (which I dont think I have addressed in my current patch).

Kirill, I have provided volano numbers above. Did you have any specific volano configuration in mind to be tested?

Also do you have a pointer to a ready pipe-based benchmark I can use?

I have provide the result of above benchmark also.

References:

1. http://lkml.org/lkml/2007/01/31/138

2. Volanomark benchmark configuration details:

java.vendor        = IBM Corporation
java.vendor.url    = http://www.ibm.com/
java.version       = 1.4.2
java.class.version = 48.0
java.compiler      = j9jit22
os.name            = Linux
os.version         = 2.6.20-rc5-1k
os.arch            = amd64

VolanoMark version = 2.5.0.9

Messages sent      = 20000
Messages received  = 380000
Total messages     = 400000

Regards,
vatsa

As Kirill brought up, why does it take so much more time? Are you thrashing the cache?

Presumably this would be made generic, as in per-"group" rather than per user?

This is kind of important, no?

Chris

Yes, the default 1-sec control window I had was causing lot of thrashing. See http://lkml.org/lkml/2007/1/31/142

Ideally yes! But I am trying to apply the solution to an existing problem and later extend for other needs as well.

Yea again! I have again avoided it to keep the patch simple at first. Based on interest/response, I can address this later.

Regards,
vatsa