[PATCH][RFC] sched: Isochronous class for unprivileged soft rt scheduling

[Con Kolivas <kernel@kolivas.org>]

[-- Attachment #1.1: Type: text/plain, Size: 2233 bytes --]

This patch for 2.6.11-rc1 provides a method of providing real time
scheduling to unprivileged users which increasingly is desired for
multimedia workloads.

It does this by adding a new scheduling class called SCHED_ISO or
Isochronous scheduling which means "same time" scheduling. This class
does not require superuser privileges and is starvation free. The
scheduling class no. 4 was chosen since there are quite a few userspace
applications already supporting 3 and 4 for SCHED_BATCH and SCHED_ISO
respectively on non-mainline kernels. As a way of immediately providing
support for current userspace apps, any unprivileged user starting an
application requesting SCHED_RR or SCHED_FIFO will be demoted to
SCHED_ISO. This may or may not be worth removing later.

The SCHED_ISO class runs as SCHED_RR effectively at a priority just
above all SCHED_NORMAL tasks and below all true real time tasks. Once a
cpu usage limit is exceeded by tasks of this class (per cpu), SCHED_ISO
tasks will then run as SCHED_NORMAL until the cpu usage drops to 90% of
the cpu limit.

By default the cpu limit is set to 70% which literature suggests should
provide good real time behaviour for most applications without gross
unfairness. This cpu limit is calculated as a decaying average over 5
seconds. These limits are configurable with the tunables
/proc/sys/kernel/iso_cpu
/proc/sys/kernel/iso_period

iso_cpu can be set to 100 which would allow all unprivileged users
access to unrestricted SCHED_RR behaviour. OSX provides a similar class
to SCHED_ISO and uses 90% as its cpu limit.

The sysrq-n combination which converts all user real-time tasks to
SCHED_NORMAL also will affect SCHED_ISO tasks.

Currently the round robin interval is set to 10ms which is a cache
friendly timeslice. It may be worth making this configurable or smaller,
and it would also be possible to implement SCHED_ISO of a FIFO nature as
well.

For testing, the userspace tool schedtool available here:
http://freequaos.host.sk/schedtool/
can be used as a wrapper to start SCHED_ISO tasks
schedtool -I -e xmms
for example

Patch also available here:
http://ck.kolivas.org/patches/SCHED_ISO/

Comments and testing welcome.

Signed-off-by: Con Kolivas <kernel@kolivas.org>


[-- Attachment #1.2: 2.6.11-rc1-iso-0501182249.diff --]
[-- Type: text/x-diff, Size: 16226 bytes --]

Index: linux-2.6.11-rc1/include/linux/init_task.h
===================================================================
--- linux-2.6.11-rc1.orig/include/linux/init_task.h	2005-01-16 22:43:47.000000000 +1100
+++ linux-2.6.11-rc1/include/linux/init_task.h	2005-01-16 22:45:23.000000000 +1100
@@ -80,6 +80,7 @@
 	.mm		= NULL,						\
 	.active_mm	= &init_mm,					\
 	.run_list	= LIST_HEAD_INIT(tsk.run_list),			\
+	.iso_list	= LIST_HEAD_INIT(tsk.iso_list),			\
 	.time_slice	= HZ,						\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
 	.ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children),		\
Index: linux-2.6.11-rc1/include/linux/sched.h
===================================================================
--- linux-2.6.11-rc1.orig/include/linux/sched.h	2005-01-16 22:43:47.000000000 +1100
+++ linux-2.6.11-rc1/include/linux/sched.h	2005-01-18 22:48:05.000000000 +1100
@@ -130,6 +130,18 @@
 #define SCHED_NORMAL		0
 #define SCHED_FIFO		1
 #define SCHED_RR		2
+/* policy 3 reserved for SCHED_BATCH */
+#define SCHED_ISO		4
+
+extern int iso_cpu, iso_period;
+
+#define SCHED_RANGE(policy)	((policy) == SCHED_NORMAL || \
+				(policy) == SCHED_FIFO || \
+				(policy) == SCHED_RR || \
+				(policy) == SCHED_ISO)
+
+#define SCHED_RT(policy)	((policy) == SCHED_FIFO || \
+				(policy) == SCHED_RR)
 
 struct sched_param {
 	int sched_priority;
@@ -359,6 +371,7 @@
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
 
 #define rt_task(p)		(unlikely((p)->prio < MAX_RT_PRIO))
+#define iso_task(p)		(unlikely((p)->policy == SCHED_ISO))
 
 /*
  * Some day this will be a full-fledged user tracking system..
@@ -536,6 +549,7 @@
 
 	int prio, static_prio;
 	struct list_head run_list;
+	struct list_head iso_list;
 	prio_array_t *array;
 
 	unsigned long sleep_avg;
Index: linux-2.6.11-rc1/include/linux/sysctl.h
===================================================================
--- linux-2.6.11-rc1.orig/include/linux/sysctl.h	2005-01-16 22:43:47.000000000 +1100
+++ linux-2.6.11-rc1/include/linux/sysctl.h	2005-01-16 22:45:23.000000000 +1100
@@ -135,6 +135,8 @@
 	KERN_HZ_TIMER=65,	/* int: hz timer on or off */
 	KERN_UNKNOWN_NMI_PANIC=66, /* int: unknown nmi panic flag */
 	KERN_BOOTLOADER_TYPE=67, /* int: boot loader type */
+	KERN_ISO_CPU=68,	/* int: cpu% allowed by SCHED_ISO class */
+	KERN_ISO_PERIOD=69,	/* int: seconds over which SCHED_ISO cpu is decayed */
 };
 
 
Index: linux-2.6.11-rc1/kernel/sched.c
===================================================================
--- linux-2.6.11-rc1.orig/kernel/sched.c	2005-01-16 22:43:47.000000000 +1100
+++ linux-2.6.11-rc1/kernel/sched.c	2005-01-18 22:48:47.000000000 +1100
@@ -149,9 +149,6 @@
 	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
 		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
 
-#define TASK_PREEMPTS_CURR(p, rq) \
-	((p)->prio < (rq)->curr->prio)
-
 /*
  * task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
  * to time slice values: [800ms ... 100ms ... 5ms]
@@ -171,6 +168,10 @@
 	else
 		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
 }
+
+int iso_cpu = 70;	/* The soft %cpu limit on SCHED_ISO tasks */
+int iso_period = 5;	/* The time over which SCHED_ISO cpu decays */
+
 #define task_hot(p, now, sd) ((long long) ((now) - (p)->last_ran)	\
 				< (long long) (sd)->cache_hot_time)
 
@@ -206,6 +207,16 @@
 #ifdef CONFIG_SMP
 	unsigned long cpu_load;
 #endif
+	unsigned long iso_ticks;
+	struct list_head iso_queue;
+	int iso_refractory;
+	/* 
+	 * Refractory is the flag that we've hit the maximum iso cpu and are
+	 * in the refractory period where SCHED_ISO tasks can only run as
+	 * SCHED_NORMAL until their cpu usage drops to 90% of their iso_cpu
+	 * limit.
+	 */
+
 	unsigned long long nr_switches;
 
 	/*
@@ -297,6 +308,19 @@
 # define task_running(rq, p)		((rq)->curr == (p))
 #endif
 
+static inline int task_preempts_curr(task_t *p, runqueue_t *rq)
+{
+	if ((!iso_task(p) && !iso_task(rq->curr)) || rq->iso_refractory ||
+		rt_task(p) || rt_task(rq->curr)) {
+			if (p->prio < rq->curr->prio)
+				return 1;
+			return 0;
+	}
+	if (iso_task(p) && !iso_task(rq->curr))
+		return 1;
+	return 0;
+}
+
 /*
  * task_rq_lock - lock the runqueue a given task resides on and disable
  * interrupts.  Note the ordering: we can safely lookup the task_rq without
@@ -560,17 +584,40 @@
 #define sched_info_switch(t, next)	do { } while (0)
 #endif /* CONFIG_SCHEDSTATS */
 
+static inline int iso_queued(runqueue_t *rq)
+{
+	return !list_empty(&rq->iso_queue);
+}
+
+static inline void dequeue_iso_task(struct task_struct *p)
+{
+	list_del_init(&p->iso_list);
+}
+
 /*
  * Adding/removing a task to/from a priority array:
  */
 static void dequeue_task(struct task_struct *p, prio_array_t *array)
 {
 	array->nr_active--;
+	if (iso_task(p))
+		dequeue_iso_task(p);
 	list_del(&p->run_list);
 	if (list_empty(array->queue + p->prio))
 		__clear_bit(p->prio, array->bitmap);
 }
 
+/*
+ * SCHED_ISO tasks are queued at both runqueues. Their actual priority is
+ * either better than SCHED_NORMAL if below starvation limits, or
+ * the underlying SCHED_NORMAL dynamic priority.
+ */
+static void enqueue_iso_task(struct task_struct *p)
+{
+	runqueue_t *rq = task_rq(p);
+	list_add_tail(&p->iso_list, &rq->iso_queue);
+}
+
 static void enqueue_task(struct task_struct *p, prio_array_t *array)
 {
 	sched_info_queued(p);
@@ -578,6 +625,14 @@
 	__set_bit(p->prio, array->bitmap);
 	array->nr_active++;
 	p->array = array;
+	if (iso_task(p))
+		enqueue_iso_task(p);
+}
+
+static void requeue_iso_task(struct task_struct *p)
+{
+	runqueue_t *rq = task_rq(p);
+	list_move_tail(&p->iso_list, &rq->iso_queue);
 }
 
 /*
@@ -587,6 +642,8 @@
 static void requeue_task(struct task_struct *p, prio_array_t *array)
 {
 	list_move_tail(&p->run_list, array->queue + p->prio);
+	if (iso_task(p))
+		requeue_iso_task(p);
 }
 
 static inline void enqueue_task_head(struct task_struct *p, prio_array_t *array)
@@ -1101,7 +1158,7 @@
 	 */
 	activate_task(p, rq, cpu == this_cpu);
 	if (!sync || cpu != this_cpu) {
-		if (TASK_PREEMPTS_CURR(p, rq))
+		if (task_preempts_curr(p, rq))
 			resched_task(rq->curr);
 	}
 	success = 1;
@@ -1146,6 +1203,7 @@
 	 */
 	p->state = TASK_RUNNING;
 	INIT_LIST_HEAD(&p->run_list);
+	INIT_LIST_HEAD(&p->iso_list);
 	p->array = NULL;
 	spin_lock_init(&p->switch_lock);
 #ifdef CONFIG_SCHEDSTATS
@@ -1235,6 +1293,8 @@
 				p->array = current->array;
 				p->array->nr_active++;
 				rq->nr_running++;
+				if (iso_task(p))
+					enqueue_iso_task(p);
 			}
 			set_need_resched();
 		} else
@@ -1257,7 +1317,7 @@
 		p->timestamp = (p->timestamp - this_rq->timestamp_last_tick)
 					+ rq->timestamp_last_tick;
 		__activate_task(p, rq);
-		if (TASK_PREEMPTS_CURR(p, rq))
+		if (task_preempts_curr(p, rq))
 			resched_task(rq->curr);
 
 		schedstat_inc(rq, wunt_moved);
@@ -1634,7 +1694,7 @@
 	 * Note that idle threads have a prio of MAX_PRIO, for this test
 	 * to be always true for them.
 	 */
-	if (TASK_PREEMPTS_CURR(p, this_rq))
+	if (task_preempts_curr(p, this_rq))
 		resched_task(this_rq->curr);
 }
 
@@ -2392,6 +2452,39 @@
 		cpustat->steal = cputime64_add(cpustat->steal, steal64);
 }
 
+static inline int inc_iso_ticks(runqueue_t *rq, task_t *p)
+{
+	int ret = 0;
+	if (rq->iso_ticks < (iso_period * HZ * 100 - 99))
+		rq->iso_ticks += 100;
+	spin_lock(&rq->lock);
+	if (!rq->iso_refractory && (rq->iso_ticks /
+		((iso_period * HZ) + 1) > iso_cpu)) {
+			rq->iso_refractory = 1;
+			if (iso_queued(rq))
+				ret = 1;
+		}
+	spin_unlock(&rq->lock);
+	return ret;
+}
+
+static inline int dec_iso_ticks(runqueue_t *rq, task_t *p)
+{
+	int ret = 0;
+	if (rq->iso_ticks) 
+		rq->iso_ticks = rq->iso_ticks * (iso_period * HZ - 1) /
+			(iso_period * HZ);
+	spin_lock(&rq->lock);
+	if (rq->iso_refractory && (rq->iso_ticks /
+		((iso_period * HZ) + 1) < (iso_cpu * 9 / 10))) {
+			rq->iso_refractory = 0;
+			if (iso_queued(rq)) 
+				ret = 1;
+	}
+	spin_unlock(&rq->lock);
+	return ret;
+}
+
 /*
  * This function gets called by the timer code, with HZ frequency.
  * We call it with interrupts disabled.
@@ -2404,8 +2497,13 @@
 	int cpu = smp_processor_id();
 	runqueue_t *rq = this_rq();
 	task_t *p = current;
+	int iso_change;
 
 	rq->timestamp_last_tick = sched_clock();
+	if (iso_task(p) && !rq->iso_refractory)
+		iso_change = inc_iso_ticks(rq, p);
+	else 
+		iso_change = dec_iso_ticks(rq, p);
 
 	if (p == rq->idle) {
 		if (wake_priority_sleeper(rq))
@@ -2420,6 +2518,7 @@
 		goto out;
 	}
 	spin_lock(&rq->lock);
+
 	/*
 	 * The task was running during this tick - update the
 	 * time slice counter. Note: we do not update a thread's
@@ -2442,6 +2541,39 @@
 		}
 		goto out_unlock;
 	}
+
+	if (unlikely(iso_change)) {
+		/*
+		 * A SCHED_ISO task was running and the soft cpu limit
+		 * was hit, or SCHED_ISO task(s) are waiting and the 
+		 * refractory period has ended. Reschedule to start ISO
+		 * tasks as SCHED_NORMAL in the former case and to allow
+		 * SCHED_ISO tasks to preempt in the latter.
+		 */
+		set_tsk_need_resched(p);
+		dequeue_task(p, rq->active);
+		p->prio = effective_prio(p);
+		p->time_slice = task_timeslice(p);
+		p->first_time_slice = 0;
+		enqueue_task(p, rq->active);
+		goto out_unlock;
+	}
+
+	if (iso_task(p) && !rq->iso_refractory) {
+		if (!--p->time_slice) {
+			p->time_slice = task_timeslice(p);
+			p->first_time_slice = 0;
+			set_tsk_need_resched(p);
+
+			/* put it at the end of the queue: */
+			requeue_task(p, rq->active);
+		} else if (!(p->time_slice % GRANULARITY)) {
+			requeue_task(p, rq->active);
+			set_tsk_need_resched(p);
+		}
+		goto out_unlock;
+	}
+
 	if (!--p->time_slice) {
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
@@ -2489,6 +2621,30 @@
 	rebalance_tick(cpu, rq, NOT_IDLE);
 }
 
+static inline int iso_ready(runqueue_t *rq)
+{
+	if (iso_queued(rq) && !rq->iso_refractory)
+		return 1;
+	return 0;
+}
+
+/*
+ * When a SCHED_ISO task is ready to be scheduled, we re-queue it with an
+ * effective prio of MAX_RT_PRIO for userspace to know its relative prio.
+ */
+static task_t* queue_iso(runqueue_t *rq, prio_array_t *array)
+{
+	task_t *p = list_entry(rq->iso_queue.next, task_t, iso_list);
+	prio_array_t *old_array = p->array;
+	list_del(&p->run_list);
+	if (list_empty(old_array->queue + p->prio))
+		__clear_bit(p->prio, old_array->bitmap);
+	p->prio = MAX_RT_PRIO;
+	list_add_tail(&p->run_list, array->queue + p->prio);
+	__set_bit(p->prio, array->bitmap);
+	return p;
+}
+
 #ifdef CONFIG_SCHED_SMT
 static inline void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
 {
@@ -2540,7 +2696,7 @@
 	struct sched_domain *sd = this_rq->sd;
 	cpumask_t sibling_map;
 	prio_array_t *array;
-	int ret = 0, i;
+	int ret = 0, i, idx;
 	task_t *p;
 
 	if (!(sd->flags & SD_SHARE_CPUPOWER))
@@ -2567,8 +2723,11 @@
 		array = this_rq->expired;
 	BUG_ON(!array->nr_active);
 
-	p = list_entry(array->queue[sched_find_first_bit(array->bitmap)].next,
-		task_t, run_list);
+	idx = sched_find_first_bit(array->bitmap);
+	if (unlikely(iso_ready(this_rq) && idx >= MAX_RT_PRIO))
+		p = queue_iso(this_rq, array);
+	else
+		p = list_entry(array->queue[idx].next, task_t, run_list);
 
 	for_each_cpu_mask(i, sibling_map) {
 		runqueue_t *smt_rq = cpu_rq(i);
@@ -2584,7 +2743,7 @@
 		 */
 		if (((smt_curr->time_slice * (100 - sd->per_cpu_gain) / 100) >
 			task_timeslice(p) || rt_task(smt_curr)) &&
-			p->mm && smt_curr->mm && !rt_task(p))
+			p->mm && smt_curr->mm && !rt_task(p) && !iso_task(p))
 				ret = 1;
 
 		/*
@@ -2594,8 +2753,9 @@
 		 */
 		if ((((p->time_slice * (100 - sd->per_cpu_gain) / 100) >
 			task_timeslice(smt_curr) || rt_task(p)) &&
-			smt_curr->mm && p->mm && !rt_task(smt_curr)) ||
-			(smt_curr == smt_rq->idle && smt_rq->nr_running))
+			smt_curr->mm && p->mm && !rt_task(smt_curr) &&
+			!iso_task(smt_curr)) || (smt_curr == smt_rq->idle &&
+			smt_rq->nr_running))
 				resched_task(smt_curr);
 	}
 out_unlock:
@@ -2767,8 +2927,12 @@
 		schedstat_inc(rq, sched_noswitch);
 
 	idx = sched_find_first_bit(array->bitmap);
-	queue = array->queue + idx;
-	next = list_entry(queue->next, task_t, run_list);
+	if (unlikely(iso_ready(rq) && idx >= MAX_RT_PRIO))
+		next = queue_iso(rq, array);
+	else {
+		queue = array->queue + idx;
+		next = list_entry(queue->next, task_t, run_list);
+	}
 
 	if (!rt_task(next) && next->activated > 0) {
 		unsigned long long delta = now - next->timestamp;
@@ -3213,7 +3377,7 @@
 	BUG_ON(p->array);
 	p->policy = policy;
 	p->rt_priority = prio;
-	if (policy != SCHED_NORMAL)
+	if (SCHED_RT(policy))
 		p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;
 	else
 		p->prio = p->static_prio;
@@ -3238,9 +3402,8 @@
 	/* double check policy once rq lock held */
 	if (policy < 0)
 		policy = oldpolicy = p->policy;
-	else if (policy != SCHED_FIFO && policy != SCHED_RR &&
-				policy != SCHED_NORMAL)
-			return -EINVAL;
+	else if (!SCHED_RANGE(policy))
+		return -EINVAL;
 	/*
 	 * Valid priorities for SCHED_FIFO and SCHED_RR are
 	 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL is 0.
@@ -3248,12 +3411,16 @@
 	if (param->sched_priority < 0 ||
 	    param->sched_priority > MAX_USER_RT_PRIO-1)
 		return -EINVAL;
-	if ((policy == SCHED_NORMAL) != (param->sched_priority == 0))
+	if ((!SCHED_RT(policy)) != (param->sched_priority == 0))
 		return -EINVAL;
 
-	if ((policy == SCHED_FIFO || policy == SCHED_RR) &&
-	    !capable(CAP_SYS_NICE))
-		return -EPERM;
+	if (SCHED_RT(policy) && !capable(CAP_SYS_NICE))
+		/*
+		 * If the caller requested an RT policy without having the
+		 * necessary rights, we downgrade the policy to SCHED_ISO.
+		 * Temporary hack for testing.
+		 */
+		policy = SCHED_ISO;
 	if ((current->euid != p->euid) && (current->euid != p->uid) &&
 	    !capable(CAP_SYS_NICE))
 		return -EPERM;
@@ -3287,7 +3454,7 @@
 		if (task_running(rq, p)) {
 			if (p->prio > oldprio)
 				resched_task(rq->curr);
-		} else if (TASK_PREEMPTS_CURR(p, rq))
+		} else if (task_preempts_curr(p, rq))
 			resched_task(rq->curr);
 	}
 	task_rq_unlock(rq, &flags);
@@ -3714,6 +3881,7 @@
 		ret = MAX_USER_RT_PRIO-1;
 		break;
 	case SCHED_NORMAL:
+	case SCHED_ISO:
 		ret = 0;
 		break;
 	}
@@ -3737,6 +3905,7 @@
 		ret = 1;
 		break;
 	case SCHED_NORMAL:
+	case SCHED_ISO:
 		ret = 0;
 	}
 	return ret;
@@ -4010,7 +4179,7 @@
 				+ rq_dest->timestamp_last_tick;
 		deactivate_task(p, rq_src);
 		activate_task(p, rq_dest, 0);
-		if (TASK_PREEMPTS_CURR(p, rq_dest))
+		if (task_preempts_curr(p, rq_dest))
 			resched_task(rq_dest->curr);
 	}
 
@@ -4792,6 +4961,7 @@
 		rq->active = rq->arrays;
 		rq->expired = rq->arrays + 1;
 		rq->best_expired_prio = MAX_PRIO;
+		rq->iso_refractory = rq->iso_ticks = 0;
 
 #ifdef CONFIG_SMP
 		rq->sd = &sched_domain_dummy;
@@ -4812,6 +4982,7 @@
 			// delimiter for bitsearch
 			__set_bit(MAX_PRIO, array->bitmap);
 		}
+		INIT_LIST_HEAD(&rq->iso_queue);
 	}
 
 	/*
@@ -4861,7 +5032,7 @@
 
 	read_lock_irq(&tasklist_lock);
 	for_each_process (p) {
-		if (!rt_task(p))
+		if (!rt_task(p) && !iso_task(p))
 			continue;
 
 		rq = task_rq_lock(p, &flags);
Index: linux-2.6.11-rc1/kernel/sysctl.c
===================================================================
--- linux-2.6.11-rc1.orig/kernel/sysctl.c	2005-01-16 22:43:47.000000000 +1100
+++ linux-2.6.11-rc1/kernel/sysctl.c	2005-01-16 22:45:23.000000000 +1100
@@ -219,6 +219,11 @@
 	{ .ctl_name = 0 }
 };
 
+/* Constants for minimum and maximum testing in vm_table.
+   We use these as one-element integer vectors. */
+static int zero;
+static int one_hundred = 100;
+
 static ctl_table kern_table[] = {
 	{
 		.ctl_name	= KERN_OSTYPE,
@@ -633,15 +638,28 @@
 		.proc_handler	= &proc_dointvec,
 	},
 #endif
+	{
+		.ctl_name	= KERN_ISO_CPU,
+		.procname	= "iso_cpu",
+		.data		= &iso_cpu,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+		.extra2		= &one_hundred,
+	},
+	{
+		.ctl_name	= KERN_ISO_PERIOD,
+		.procname	= "iso_period",
+		.data		= &iso_period,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
 	{ .ctl_name = 0 }
 };
 
-/* Constants for minimum and maximum testing in vm_table.
-   We use these as one-element integer vectors. */
-static int zero;
-static int one_hundred = 100;
-
-
 static ctl_table vm_table[] = {
 	{
 		.ctl_name	= VM_OVERCOMMIT_MEMORY,





[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]