Resource management through virtualization - the scheduler

I have long believed that general-purpose resource management is best done by virtualizing the subsystem responsible for the resource in question.

Here, I present a virtualization of the scheduler which allows the construction of CPU compartments and confinement of processes within them. The scheduler is virtualized in the sense that it is possible to have more than one scheduler running on the system, and each new guest scheduler runs as a process on the host scheduler. Thus, it competes for CPU time as a single process, and the processes confined to the guest compete against each other for the CPU time given to the guest scheduler.

For example, given three CPU hogs, one of which is running directly on the host scheduler, and two of which are confined to a guest scheduler, the CPU hog on the host will compete with the guest scheduler for CPU time, and each will receive half. The two hogs inside the guest scheduler will then compete for the half of the CPU given to the guest scheduler, each receiving 1/4 of the CPU.

This has uses aside from the resource control which motivated it:
The guest scheduler doesn't need to be the standard Linux
scheduler - if you feel the current scheduler doesn't do justice to your workload, you can write your own, load it in as a guest, and put your workload into it.
The guest can be a bug-fixed version of the host - move your
workload into it and see if your bug is fixed. If not, move your workload back out, unload the scheduler, and try again. If so, you can leave everything as is, and you don't have to reboot.

Each guest scheduler creates a "sched group" (I would have used "sched domain", but the NUMA people beat me to it). In addition, there is a sched group for the host scheduler. These are represented in /proc as /proc/sched-groups/<n>, where <n> is the pid of the process creating the sched group. The host sched group is /proc/sched-groups/0, and is created at boot time.

The /proc/sched-groups/<n> directory contains the current /proc/<pid> directories for all processes inside the sched group. sched group 0 initially contains all of the processes on the system. As the /proc/<pid> directories have moved, symlinks are left behind for compatibility.

A new sched group is created by a process opening /proc/schedulers/guest_o1_scheduler, as with
% /proc/schedulers/guest_o1_scheduler
This interface is somewhat hokey, and better suggestions would be appreciated. However, this does have the property that the container initially has the scheduling properties of this process, such as nice level, priority, scheduling policy, processor affinity, etc. These can be manipulated after the fact just as any other process.

Processes are confined to a compartment by moving them from one /proc/sched-group/<n> directory to another. New processes also inherit the compartment of their parent.

To make this concrete, here is a session producing the 50-25-25 CPU split described above:

        # This cat will become the guest scheduler by opening guest_o1_scheduler
	usermode:~# cat /proc/schedulers/guest_o1_scheduler &
	Created sched_group 290 ('guest_o1_scheduler')
	# This is now /proc/sched-groups/290/
	[1] 290
	# Create three CPU hogs
	usermode:~# bash -c 'while true; do true; done' &
	[2] 292
	usermode:~# bash -c 'while true; do true; done' &
	[3] 293
	usermode:~# bash -c 'while true; do true; done' &
	[4] 294
	# Move 293 and 294 into the compartment, leaving 292 on the host
	# scheduler
	usermode:~# mv /proc/sched-groups/0/293 /proc/sched-groups/290/
	usermode:~# mv /proc/sched-groups/0/294 /proc/sched-groups/290/
	# ...wait a bit...
	usermode:~# ps uax
	...
	root       292 49.1  0.7  2324  996 tty0     R    21:51  14:40 bash -c 
	root       293 24.7  0.7  2324  996 tty0     R    21:51   7:23 bash -c 
	root       294 24.7  0.7  2324  996 tty0     R    21:51   7:23 bash -c 
	...

More arbitrary divisions of CPU can be made by having the guest schedulers be SMP with more than one virtual processor. This could also be adjusted on the fly by adding CPU hotplug support.

Compartments can be nested, and don't require root privileges to create. What does require root is loading the guests into the kernel in the first place. In the absence of a reentrant scheduler, new instances are made available by modprobing more instances of the scheduler module into the kernel. However, given the presence of available guests, activating one is a non-privileged operation.

The design of this is that there is a scheduler struct pointer in each task struct. This contains the entry points for the scheduler that is controlling it. Every scheduler operation now goes through p->scheduler.task_ops.<function>. Moving a process from one sched group to another causes its scheduler to be changed.

When a new sched group is created, it creates another thread, which will be the idle thread of the guest scheduler. The original process remains with its scheduler. When it gets CPU time from the host, it switches to the idle thread of the guest scheduler. When the guest idle thread runs again, instead of sleeping, it switches back to the container process, which sleeps in the host scheduler.

Clock ticks are handled such that the host scheduler gets to see them first, getting a chance to schedule away from the compartment. When the compartment next runs, it will handle the tick on its own, and have a chance to make its own scheduling decisions.

The implementation is as follows:
The O(1) scheduler algorithm was split out from sched.c and moved
to o1_sched.c. This is the code that we want duplicated, and the code that remains in sched.c is stuff like system call entry points and primitives which are independent of the actual algorithm, which shouldn't be duplicated.

The scheduling primitives were made static and used to fill a
structure of function pointers in the scheduler struct. Their names were also changed so as not to conflict with the new macros in sched.h which call through the scheduler struct. For example, schedule() in sched.h is now

	#define schedule() current->scheduler->task_ops.schedule()

and the scheduler is now
static asmlinkage void __sched o1_schedule(void)

o1_sched.c is now linked into two intermediate object files, a host and a guest, with either host_sched.c and guest_sched.c. These two customize the scheduler struct as either a host or a guest scheduler. The output of this is either guest_o1_sched.o (when CONFIG_GUEST_SCHED == y) or guest_o1_scheduler.ko (when CONFIG_GUEST_SCHED == m). When built into the kernel, you get one guest scheduler, which is registered at boot time. Thus, it is recommended to make it modular, and modprobe it whenever you need a new compartment.

modprobe is somewhat reluctant to load the same module twice, so using the -o switch to modprobe is needed to give each instance a different name:
% modprobe -o guest1 modprobe guest_o1_scheduler
at which point, you'd open /proc/schedulers/guest1 to activate it.

I've broken this into three patches -
guest-sched-prep - adds the procfs changes and makes the single
host scheduler use it, adds the sched.h changes, the sched.c redeclarations, and the scheduler struct, but doesn't change the system's behavior.
guest-sched-movement - creates o1_sched.c by splitting the
relevant code from sched.c
guest-sched-guest - adds guest support by adding the necessary
build changes (along with the kbuild nastiness that seems to be a hallmark of my work, sigh) and the code in guest_sched.c which actually virtualizes the scheduler.

Patches 1 and 3 are attached; patch 2 is code movement with no functional changes and is way too large to post to LKML. It can be found at http://www.user-mode-linux.org/~jdike/guest-sched-movement

Here are diffstats:

guest-sched-prep:

 arch/um/kernel/skas/process_kern.c |    2 
 arch/um/kernel/tt/process_kern.c   |    2 
 fs/proc/base.c                     |  201 +++++++++++++++++++++++++++++++++++--
 include/linux/init_task.h          |    1 
 include/linux/kernel_stat.h        |   11 +-
 include/linux/sched.h              |  122 +++++++++++++++++++---
 kernel/Makefile                    |    7 -
 kernel/host_sched.c                |   10 +
 kernel/sched.c                     |  142 ++++++++++++++++++--------
 kernel/sched_group.c               |  138 +++++++++++++++++++++++++
 10 files changed, 560 insertions(+), 76 deletions(-)

guest-sched-movement:

 Makefile   |    2 
 o1_sched.c | 3506 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sched.c    | 3510 -------------------------------------------------------------
 3 files changed, 3512 insertions(+), 3506 deletions(-)

guest-sched-guest:

 arch/um/defconfig             |    1 
 arch/um/kernel/ksyms.c        |    4 +
 arch/um/kernel/process_kern.c |    2 
 arch/um/kernel/signal_kern.c  |    2 
 arch/um/kernel/time_kern.c    |    2 
 include/linux/rcupdate.h      |    2 
 include/linux/sched.h         |    2 
 init/Kconfig                  |    4 +
 kernel/Makefile               |   32 +++++++++
 kernel/acct.c                 |    3 
 kernel/fork.c                 |    4 +
 kernel/guest_sched.c          |  143 ++++++++++++++++++++++++++++++++++++++++++
 kernel/o1_sched.c             |   26 +++++++
 kernel/profile.c              |    2 
 kernel/rcupdate.c             |    7 ++
 kernel/sched_group.c          |   52 +++++++++++++++
 mm/memory.c                   |    2 
 17 files changed, 288 insertions(+), 2 deletions(-)

The lots of little changes in -guest are a bunch of EXPORT_SYMBOLS of random crap that were needed to get the scheduler loading as a module.

I've build and tested this with UML (2.6.11-bk8, but it should be fine with anything near that). I think that there one or two minor unportabilities that will prevent this from working as-is on other arches. However, there's nothing intrinsically arch-dependent here.

Jeff

Index: guest-sched-2.6.11/arch/um/kernel/skas/process_kern.c
===================================================================
@@ -47,8 +47,6 @@
 	return(current->thread.prev_sched);
 }
 
-extern void schedule_tail(struct task_struct *prev);
-
 void new_thread_handler(int sig)
 {
 	int (*fn)(void *), n;

Index: guest-sched-2.6.11/arch/um/kernel/tt/process_kern.c
===================================================================
@@ -123,8 +123,6 @@
 		panic("read failed in suspend_new_thread, err = %d", -err);
 }
 
-void schedule_tail(task_t *prev);
-
 static void new_thread_handler(int sig)
 {
 	unsigned long disable;

Index: guest-sched-2.6.11/include/linux/init_task.h
===================================================================
@@ -111,6 +111,7 @@
 	.switch_lock	= SPIN_LOCK_UNLOCKED,				\
 	.journal_info	= NULL,						\
 	.cpu_timers	= INIT_CPU_TIMERS(tsk.cpu_timers),		\
+        .scheduler	= &o1_scheduler,				\
 }
 
 

Index: guest-sched-2.6.11/include/linux/kernel_stat.h
===================================================================
@@ -36,7 +36,7 @@
 /* Must have preemption disabled for this to be meaningful. */
 #define kstat_this_cpu	__get_cpu_var(kstat)
 
-extern unsigned long long nr_context_switches(void);
+#define nr_context_switches() current->scheduler->task_ops.nr_context_switches()
 
 /*
  * Number of interrupts per specific IRQ source, since bootup

@@ -52,8 +52,11 @@
 	return sum;
 }
 
-extern void account_user_time(struct task_struct *, cputime_t);
-extern void account_system_time(struct task_struct *, int, cputime_t);
-extern void account_steal_time(struct task_struct *, cputime_t);
+#define account_user_time(task, t) \
+        (task)->scheduler->task_ops.account_user_time(task, t)
+#define account_system_time(task, o, t) \
+        (task)->scheduler->task_ops.account_system_time(task, o, t)
+#define account_steal_time(task, t) \
+        (task)->scheduler->task_ops.account_steal_time(task, t)
 
 #endif /* _LINUX_KERNEL_STAT_H */

Index: guest-sched-2.6.11/kernel/Makefile
===================================================================
@@ -2,12 +2,13 @@
 # Makefile for the linux kernel.
 #
 
-obj-y     = sched.o fork.o exec_domain.o panic.o printk.o profile.o \
-	    exit.o itimer.o time.o softirq.o resource.o \
+obj-y     = sched.o host_sched.o fork.o exec_domain.o panic.o printk.o \
+	    profile.o exit.o itimer.o time.o softirq.o resource.o \
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o
+	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o \
+	    sched_group.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o

Index: guest-sched-2.6.11/kernel/host_sched.c
===================================================================
@@ -0,0 +1,10 @@
+#include <linux/sched.h>
+
+int init_sched_instance(struct scheduler *scheduler)
+{
+	return register_sched_group(0, scheduler);
+}
+
+void uninit_sched_instance(struct scheduler *scheduler)
+{
+}

Index: guest-sched-2.6.11/arch/um/defconfig
===================================================================
@@ -6,6 +6,7 @@
 CONFIG_GENERIC_HARDIRQS=y
 CONFIG_USERMODE=y
 CONFIG_MMU=y
+# CONFIG_GUEST_SCHED is not set
 CONFIG_UID16=y
 CONFIG_RWSEM_GENERIC_SPINLOCK=y
 CONFIG_GENERIC_CALIBRATE_DELAY=y

Index: guest-sched-2.6.11/arch/um/kernel/ksyms.c
===================================================================
@@ -122,6 +122,10 @@
 EXPORT_SYMBOL(kmap_atomic_to_page);
 #endif
 
+#ifdef CONFIG_MODE_SKAS
+EXPORT_SYMBOL(switch_mm_skas);
+#endif
+
 /*
  * Overrides for Emacs so that we follow Linus's tabbing style.
  * Emacs will notice this stuff at the end of the file and automatically

Index: guest-sched-2.6.11/arch/um/kernel/process_kern.c
===================================================================
@@ -129,6 +129,8 @@
 			   switch_to_skas(prev, next)));
 }
 
+EXPORT_SYMBOL(_switch_to);
+
 int interrupt_end(void)
 {
 	if(need_resched()) schedule();

Index: guest-sched-2.6.11/arch/um/kernel/signal_kern.c
===================================================================
@@ -146,6 +146,8 @@
 	return(kern_do_signal(&current->thread.regs, &current->blocked));
 }
 
+EXPORT_SYMBOL(do_signal);
+
 /*
  * Atomically swap in the new signal mask, and wait for a signal.
  */

Index: guest-sched-2.6.11/arch/um/kernel/time_kern.c
===================================================================
@@ -39,6 +39,8 @@
 	return (unsigned long long)jiffies_64 * (1000000000 / HZ);
 }
 
+EXPORT_SYMBOL(sched_clock);
+
 /* Changed at early boot */
 int timer_irq_inited = 0;
 

Index: guest-sched-2.6.11/include/linux/rcupdate.h
===================================================================
@@ -123,6 +123,8 @@
 	rdp->passed_quiesc = 1;
 }
 
+extern void rcu_qsctr_inc_fn(int cpu);
+
 static inline int __rcu_pending(struct rcu_ctrlblk *rcp,
 						struct rcu_data *rdp)
 {

Index: guest-sched-2.6.11/include/linux/sched.h
===================================================================
@@ -263,6 +263,8 @@
         void (*sched_init_fn)(void);
         int (*task_curr)(const task_t *p);
         void (*init_idle)(task_t *idle, int cpu);
+        void (*sched_add_task)(struct task_struct *p);
+        void (*sched_remove_task)(struct task_struct *p);
 };
 
 struct scheduler {

Index: guest-sched-2.6.11/init/Kconfig
===================================================================
@@ -369,6 +369,10 @@
 	  no dummy operations need be executed.
 	  Zero means use compiler's default.
 
+config GUEST_SCHED
+	tristate "Guest scheduler"
+	default n
+
 endmenu		# General setup
 
 config TINY_SHMEM

Index: guest-sched-2.6.11/kernel/Makefile
===================================================================
@@ -2,7 +2,8 @@
 # Makefile for the linux kernel.
 #
 
-obj-y     = sched.o o1_sched.o host_sched.o fork.o exec_domain.o panic.o printk.o \
+obj-y     = sched.o host_o1_sched.o fork.o exec_domain.o panic.o printk.o \
+	    profile.o exit.o itimer.o time.o softirq.o resource.o \
 	    profile.o exit.o itimer.o time.o softirq.o resource.o \
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \

@@ -30,6 +31,35 @@
 obj-$(CONFIG_GENERIC_HARDIRQS) += irq/
 obj-$(CONFIG_SECCOMP) += seccomp.o
 
+ifeq ($(CONFIG_GUEST_SCHED),y)
+obj-$(CONFIG_GUEST_SCHED) += guest_o1_sched.o
+
+else
+obj-$(CONFIG_GUEST_SCHED) += guest_o1_scheduler.o
+endif
+
+$(obj)/guest_o1_scheduler.o : $(obj)/guest_sched.o $(obj)/o1_sched2.o
+	$(call if_changed,link_multi-$(CONFIG_GUEST_SCHED))
+
+$(obj)/o1_sched2.o : $(obj)/o1_sched2.c
+	$(call if_changed_rule,cc_o_c)
+
+$(obj)/o1_sched2.c : $(obj)/o1_sched.c
+	ln -sf $(notdir $<) $@
+
+$(obj)/host_o1_scheduler.o : $(obj)/%_o1_scheduler.o : $(obj)/%_sched.o $(obj)/o1_sched.o
+	$(call if_changed,link_multi-y)
+
+host_o1_scheduler-y := o1_sched.o host_sched.o
+guest_o1_scheduler-y := o1_sched2.o guest_sched.o
+
+localize = init_sched_instance uninit_sched_instance \
+	$(if $(findstring host,$(1)),,o1_scheduler)
+
+$(obj)/guest_o1_sched.o $(obj)/host_o1_sched.o : $(obj)/%_o1_sched.o : $(obj)/%_o1_scheduler.o 
+	objcopy $(foreach s,$(call localize,$<),--localize-symbol=$(s)) $< $@
+
+
 ifneq ($(CONFIG_IA64),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
 # needed for x86 only.  Why this used to be enabled for all architectures is beyond

Index: guest-sched-2.6.11/kernel/acct.c
===================================================================
@@ -54,6 +54,7 @@
 #include <linux/jiffies.h>
 #include <linux/times.h>
 #include <linux/syscalls.h>
+#include <linux/module.h>
 #include <asm/uaccess.h>
 #include <asm/div64.h>
 #include <linux/blkdev.h> /* sector_div */

@@ -547,6 +548,8 @@
 	}
 }
 
+EXPORT_SYMBOL(acct_update_integrals);
+
 /*
  * acct_clear_integrals
  *    - clear the mm integral fields in task_struct

Index: guest-sched-2.6.11/kernel/fork.c
===================================================================
@@ -103,6 +103,8 @@
 		free_task(tsk);
 }
 
+EXPORT_SYMBOL(__put_task_struct);
+
 void __init fork_init(unsigned long mempages)
 {
 #ifndef __HAVE_ARCH_TASK_STRUCT_ALLOCATOR

@@ -341,6 +343,8 @@
 	free_mm(mm);
 }
 
+EXPORT_SYMBOL(__mmdrop);
+
 /*
  * Decrement the use count and release all resources for an mm.
  */

Index: guest-sched-2.6.11/kernel/o1_sched.c
===================================================================
@@ -711,6 +711,16 @@
 	__activate_task(p, rq);
 }
 
+static void o1_sched_add_task(task_t *p)
+{
+	unsigned long flags;
+	runqueue_t *rq;
+        
+	rq = task_rq_lock(p, &flags);
+        activate_task(p, rq, 0);
+        task_rq_unlock(rq, &flags);
+}
+
 /*
  * deactivate_task - remove a task from the runqueue.
  */

@@ -721,6 +731,16 @@
 	p->array = NULL;
 }
 
+static void o1_sched_remove_task(struct task_struct *p)
+{
+	unsigned long flags;
+	runqueue_t *rq;
+        
+	rq = task_rq_lock(p, &flags);
+        deactivate_task(p, rq);
+        task_rq_unlock(rq, &flags);
+}
+
 /*
  * resched_task - mark a task 'to be rescheduled now'.
  *

@@ -2678,7 +2698,7 @@
 		schedstat_inc(rq, sched_goidle);
 	prefetch(next);
 	clear_tsk_need_resched(prev);
-	rcu_qsctr_inc(task_cpu(prev));
+	rcu_qsctr_inc_fn(task_cpu(prev));
 
 	update_cpu_clock(prev, rq, now);
 

@@ -3480,6 +3500,8 @@
                 .sched_init_fn		= o1_sched_init,
                 .task_curr		= o1_task_curr,
                 .init_idle		= o1_init_idle,
+                .sched_add_task		= o1_sched_add_task,
+                .sched_remove_task	= o1_sched_remove_task,
 	},
 };
 

@@ -3504,3 +3526,5 @@
 }
 
 postcore_initcall(init_scheduler);
+
+MODULE_LICENSE("GPL");

Index: guest-sched-2.6.11/kernel/profile.c
===================================================================
@@ -379,6 +379,8 @@
 }
 #endif /* !CONFIG_SMP */
 
+EXPORT_SYMBOL(profile_hit);
+
 void profile_tick(int type, struct pt_regs *regs)
 {
 	if (type == CPU_PROFILING && timer_hook)

Index: guest-sched-2.6.11/kernel/rcupdate.c
===================================================================
@@ -72,6 +72,13 @@
 static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL};
 static int maxbatch = 10;
 
+void rcu_qsctr_inc_fn(int cpu)
+{
+        rcu_qsctr_inc(cpu);
+}
+
+EXPORT_SYMBOL(rcu_qsctr_inc_fn);
+
 /**
  * call_rcu - Queue an RCU callback for invocation after a grace period.
  * @head: structure to be used for queueing the RCU updates.

Index: guest-sched-2.6.11/mm/memory.c
===================================================================
@@ -2269,6 +2269,8 @@
 	}
 }
 
+EXPORT_SYMBOL(update_mem_hiwater);
+
 #if !defined(__HAVE_ARCH_GATE_AREA)
 
 #if defined(AT_SYSINFO_EHDR)