Re: [PATCH] Staircase scheduler v7.4

[Wes Janzen <superchkn@sbcglobal.net>]

Hi Con,

I don't know what's going on but 2.6.7-mm2 with the staircase v7.4 (with 
or without staircase7.4-1) takes about 3 hours to get from loading the 
kernel from grub to the login prompt.  Now I realize my K6-2 400 isn't 
state of the art...  I don't have this problem running 2.6.7-mm2.

It just pauses after starting nearly every service for an extended 
period of time.  It responds to sys-rq keys but just seems to be doing 
nothing while waiting.

Any suggestions?

Thanks,

Wes Janzen

Con Kolivas wrote:

> This is a scheduler policy rewrite designed to be interactive by 
> design without tweaks or tuning and be lean and extensible for all 
> sorts of settings. (see previous announcements for more detail).
>
> Patches (including incrementals from previous versions) against 2.6.7 
> and 2.6.7-mm2 can be downloaded from:
> http://ck.kolivas.org/patches/2.6/
>
> At this point all known bugs that have come up from testers have been 
> addressed. For testers of this patch please note that renicing tasks 
> to -ve values will not improve the behaviour of games and the like 
> (usually it worsens it). Users will be rewarded by judicious use of 
> +nice values as nice has profound effects with this scheduler.
>
> Note, for multiuser machines and servers I recommend disabling 
> interactive mode:
> echo 0 > /proc/sys/kernel/interactive
>
>
> Changes since v7.3
>
> A very difficult to track (and reproduce) bug was finally sorted out 
> where a task that forked repeated cpu bound tasks for just the right 
> duration before they stopped would be able to DoS other tasks. 
> Basically since every time the parent would go to sleep it would wake 
> up back at it's best priority it meant the children would run only for 
> as long as needed to stay at that same priority thus hogging all cpu 
> resources. This was addressed using the existing infrastructure 
> already in place in staircase. It deals with ultra short running tasks 
> by making each next wakeup actually continue as though they are still 
> running their first timeslice. Thus their priority drops over time in 
> spite of repeated wakeups. Great thanks to Pauli Virtanen for his 
> testing and help in nailing this.
>
> The other change involves a design issue with the behaviour of the 
> O(1) scheduler. If task a is preempted by a higher priority task b, 
> task a gets requeued to run after all tasks of the same priority as 
> itself. Preempted tasks are now flagged as having that happen and will 
> go ahead of other tasks getting to continue where it left off. This 
> tends to smooth out the jitter of things like X and audio somewhat, 
> and because they may run again if task b runs only briefly it helps 
> preserve cache. Thus on preliminary benchmarks I've found a slight 
> improvement in throughput under heavy load.
>
> Attached is the patch against 2.6.7.
>
> Regards,
> Con
>
>------------------------------------------------------------------------
>
>Index: linux-2.6.7-staircase/fs/proc/array.c
>===================================================================
>--- linux-2.6.7-staircase.orig/fs/proc/array.c	2004-06-25 02:24:28.106117207 +1000
>+++ linux-2.6.7-staircase/fs/proc/array.c	2004-06-25 02:24:33.881209658 +1000
>@@ -155,7 +155,7 @@
> 	read_lock(&tasklist_lock);
> 	buffer += sprintf(buffer,
> 		"State:\t%s\n"
>-		"SleepAVG:\t%lu%%\n"
>+		"Burst:\t%d\n"
> 		"Tgid:\t%d\n"
> 		"Pid:\t%d\n"
> 		"PPid:\t%d\n"
>@@ -163,7 +163,7 @@
> 		"Uid:\t%d\t%d\t%d\t%d\n"
> 		"Gid:\t%d\t%d\t%d\t%d\n",
> 		get_task_state(p),
>-		(p->sleep_avg/1024)*100/(1020000000/1024),
>+		p->burst,
> 	       	p->tgid,
> 		p->pid, p->pid ? p->real_parent->pid : 0,
> 		p->pid && p->ptrace ? p->parent->pid : 0,
>Index: linux-2.6.7-staircase/include/linux/sched.h
>===================================================================
>--- linux-2.6.7-staircase.orig/include/linux/sched.h	2004-06-25 02:24:28.113116107 +1000
>+++ linux-2.6.7-staircase/include/linux/sched.h	2004-06-25 02:24:34.720077833 +1000
>@@ -164,6 +164,7 @@
> 
> void io_schedule(void);
> long io_schedule_timeout(long timeout);
>+extern int interactive, compute;
> 
> extern void cpu_init (void);
> extern void trap_init(void);
>@@ -325,7 +326,6 @@
> extern struct user_struct root_user;
> #define INIT_USER (&root_user)
> 
>-typedef struct prio_array prio_array_t;
> struct backing_dev_info;
> struct reclaim_state;
> 
>@@ -392,16 +392,13 @@
> 
> 	int prio, static_prio;
> 	struct list_head run_list;
>-	prio_array_t *array;
>-
>-	unsigned long sleep_avg;
>-	long interactive_credit;
> 	unsigned long long timestamp;
>-	int activated;
>+	unsigned long runtime, totalrun;
>+	unsigned int burst;
> 
> 	unsigned long policy;
> 	cpumask_t cpus_allowed;
>-	unsigned int time_slice, first_time_slice;
>+	unsigned int slice, time_slice;
> 
> 	struct list_head tasks;
> 	struct list_head ptrace_children;
>@@ -549,6 +546,8 @@
> #define PF_SWAPOFF	0x00080000	/* I am in swapoff */
> #define PF_LESS_THROTTLE 0x00100000	/* Throttle me less: I clean memory */
> #define PF_SYNCWRITE	0x00200000	/* I am doing a sync write */
>+#define PF_FORKED	0x00400000	/* I have just forked */
>+#define PF_PREEMPTED	0x00800000	/* I have just been preempted */
> 
> #ifdef CONFIG_SMP
> #define SCHED_LOAD_SCALE	128UL	/* increase resolution of load */
>@@ -742,7 +741,6 @@
>  }
> #endif
> extern void FASTCALL(sched_fork(task_t * p));
>-extern void FASTCALL(sched_exit(task_t * p));
> 
> extern int in_group_p(gid_t);
> extern int in_egroup_p(gid_t);
>Index: linux-2.6.7-staircase/include/linux/sysctl.h
>===================================================================
>--- linux-2.6.7-staircase.orig/include/linux/sysctl.h	2004-06-25 02:24:28.113116107 +1000
>+++ linux-2.6.7-staircase/include/linux/sysctl.h	2004-06-25 02:24:33.884209187 +1000
>@@ -133,6 +133,8 @@
> 	KERN_NGROUPS_MAX=63,	/* int: NGROUPS_MAX */
> 	KERN_SPARC_SCONS_PWROFF=64, /* int: serial console power-off halt */
> 	KERN_HZ_TIMER=65,	/* int: hz timer on or off */
>+	KERN_INTERACTIVE=66,	/* interactive tasks can have cpu bursts */
>+	KERN_COMPUTE=67,	/* adjust timeslices for a compute server */
> };
> 
> 
>Index: linux-2.6.7-staircase/init/main.c
>===================================================================
>--- linux-2.6.7-staircase.orig/init/main.c	2004-06-25 02:24:28.108116892 +1000
>+++ linux-2.6.7-staircase/init/main.c	2004-06-25 02:24:33.885209030 +1000
>@@ -314,8 +314,15 @@
> #define smp_init()	do { } while (0)
> #endif
> 
>+unsigned long cache_decay_ticks;
> static inline void setup_per_cpu_areas(void) { }
>-static inline void smp_prepare_cpus(unsigned int maxcpus) { }
>+static void smp_prepare_cpus(unsigned int maxcpus)
>+{
>+	// Generic 2 tick cache_decay for uniprocessor
>+	cache_decay_ticks = 2;
>+	printk("Generic cache decay timeout: %ld msecs.\n",
>+		(cache_decay_ticks * 1000 / HZ));
>+}
> 
> #else
> 
>Index: linux-2.6.7-staircase/kernel/exit.c
>===================================================================
>--- linux-2.6.7-staircase.orig/kernel/exit.c	2004-06-25 02:24:28.111116421 +1000
>+++ linux-2.6.7-staircase/kernel/exit.c	2004-06-25 02:24:33.887208715 +1000
>@@ -96,7 +96,6 @@
> 	p->parent->cmaj_flt += p->maj_flt + p->cmaj_flt;
> 	p->parent->cnvcsw += p->nvcsw + p->cnvcsw;
> 	p->parent->cnivcsw += p->nivcsw + p->cnivcsw;
>-	sched_exit(p);
> 	write_unlock_irq(&tasklist_lock);
> 	spin_unlock(&p->proc_lock);
> 	proc_pid_flush(proc_dentry);
>Index: linux-2.6.7-staircase/kernel/sched.c
>===================================================================
>--- linux-2.6.7-staircase.orig/kernel/sched.c	2004-06-25 02:24:28.110116578 +1000
>+++ linux-2.6.7-staircase/kernel/sched.c	2004-06-25 02:24:34.722077519 +1000
>@@ -16,6 +16,8 @@
>  *		by Davide Libenzi, preemptible kernel bits by Robert Love.
>  *  2003-09-03	Interactivity tuning by Con Kolivas.
>  *  2004-04-02	Scheduler domains code by Nick Piggin
>+ *  2004-06-11	New staircase scheduling policy by Con Kolivas with help
>+ *		from William Lee Irwin III, Zwane Mwaikambo & Peter Williams.
>  */
> 
> #include <linux/mm.h>
>@@ -43,12 +45,6 @@
> 
> #include <asm/unistd.h>
> 
>-#ifdef CONFIG_NUMA
>-#define cpu_to_node_mask(cpu) node_to_cpumask(cpu_to_node(cpu))
>-#else
>-#define cpu_to_node_mask(cpu) (cpu_online_map)
>-#endif
>-
> /*
>  * Convert user-nice values [ -20 ... 0 ... 19 ]
>  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
>@@ -66,118 +62,20 @@
> #define USER_PRIO(p)		((p)-MAX_RT_PRIO)
> #define TASK_USER_PRIO(p)	USER_PRIO((p)->static_prio)
> #define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
>-#define AVG_TIMESLICE	(MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) *\
>-			(MAX_PRIO-1-NICE_TO_PRIO(0))/(MAX_USER_PRIO - 1)))
> 
> /*
>  * Some helpers for converting nanosecond timing to jiffy resolution
>  */
> #define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 / HZ))
>-#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ))
>-
>-/*
>- * These are the 'tuning knobs' of the scheduler:
>- *
>- * Minimum timeslice is 10 msecs, default timeslice is 100 msecs,
>- * maximum timeslice is 200 msecs. Timeslices get refilled after
>- * they expire.
>- */
>-#define MIN_TIMESLICE		( 10 * HZ / 1000)
>-#define MAX_TIMESLICE		(200 * HZ / 1000)
>-#define ON_RUNQUEUE_WEIGHT	 30
>-#define CHILD_PENALTY		 95
>-#define PARENT_PENALTY		100
>-#define EXIT_WEIGHT		  3
>-#define PRIO_BONUS_RATIO	 25
>-#define MAX_BONUS		(MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
>-#define INTERACTIVE_DELTA	  2
>-#define MAX_SLEEP_AVG		(AVG_TIMESLICE * MAX_BONUS)
>-#define STARVATION_LIMIT	(MAX_SLEEP_AVG)
>-#define NS_MAX_SLEEP_AVG	(JIFFIES_TO_NS(MAX_SLEEP_AVG))
>-#define CREDIT_LIMIT		100
>-
>-/*
>- * If a task is 'interactive' then we reinsert it in the active
>- * array after it has expired its current timeslice. (it will not
>- * continue to run immediately, it will still roundrobin with
>- * other interactive tasks.)
>- *
>- * This part scales the interactivity limit depending on niceness.
>- *
>- * We scale it linearly, offset by the INTERACTIVE_DELTA delta.
>- * Here are a few examples of different nice levels:
>- *
>- *  TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
>- *  TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
>- *  TASK_INTERACTIVE(  0): [1,1,1,1,0,0,0,0,0,0,0]
>- *  TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
>- *  TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
>- *
>- * (the X axis represents the possible -5 ... 0 ... +5 dynamic
>- *  priority range a task can explore, a value of '1' means the
>- *  task is rated interactive.)
>- *
>- * Ie. nice +19 tasks can never get 'interactive' enough to be
>- * reinserted into the active array. And only heavily CPU-hog nice -20
>- * tasks will be expired. Default nice 0 tasks are somewhere between,
>- * it takes some effort for them to get interactive, but it's not
>- * too hard.
>- */
>-
>-#define CURRENT_BONUS(p) \
>-	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
>-		MAX_SLEEP_AVG)
>-
>-#ifdef CONFIG_SMP
>-#define TIMESLICE_GRANULARITY(p)	(MIN_TIMESLICE * \
>-		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)) * \
>-			num_online_cpus())
>-#else
>-#define TIMESLICE_GRANULARITY(p)	(MIN_TIMESLICE * \
>-		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))
>-#endif
>-
>-#define SCALE(v1,v1_max,v2_max) \
>-	(v1) * (v2_max) / (v1_max)
>-
>-#define DELTA(p) \
>-	(SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA)
> 
>-#define TASK_INTERACTIVE(p) \
>-	((p)->prio <= (p)->static_prio - DELTA(p))
>-
>-#define INTERACTIVE_SLEEP(p) \
>-	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
>-		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
>-
>-#define HIGH_CREDIT(p) \
>-	((p)->interactive_credit > CREDIT_LIMIT)
>-
>-#define LOW_CREDIT(p) \
>-	((p)->interactive_credit < -CREDIT_LIMIT)
>-
>-#define TASK_PREEMPTS_CURR(p, rq) \
>-	((p)->prio < (rq)->curr->prio)
>-
>-/*
>- * BASE_TIMESLICE scales user-nice values [ -20 ... 19 ]
>- * to time slice values.
>- *
>- * The higher a thread's priority, the bigger timeslices
>- * it gets during one round of execution. But even the lowest
>- * priority thread gets MIN_TIMESLICE worth of execution time.
>- *
>- * task_timeslice() is the interface that is used by the scheduler.
>+int compute = 0;
>+/* 
>+ *This is the time all tasks within the same priority round robin.
>+ *compute setting is reserved for dedicated computational scheduling
>+ *and has ten times larger intervals.
>  */
>-
>-#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
>-		((MAX_TIMESLICE - MIN_TIMESLICE) * \
>-			(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))
>-
>-static unsigned int task_timeslice(task_t *p)
>-{
>-	return BASE_TIMESLICE(p);
>-}
>+#define _RR_INTERVAL		((10 * HZ / 1000) ? : 1)
>+#define RR_INTERVAL		(_RR_INTERVAL * (1 + 9 * compute))
> 
> #define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time)
> 
>@@ -185,16 +83,8 @@
>  * These are the runqueue data structures:
>  */
> 
>-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>-
> typedef struct runqueue runqueue_t;
> 
>-struct prio_array {
>-	unsigned int nr_active;
>-	unsigned long bitmap[BITMAP_SIZE];
>-	struct list_head queue[MAX_PRIO];
>-};
>-
> /*
>  * This is the main, per-CPU runqueue data structure.
>  *
>@@ -214,12 +104,13 @@
> 	unsigned long cpu_load;
> #endif
> 	unsigned long long nr_switches;
>-	unsigned long expired_timestamp, nr_uninterruptible;
>+	unsigned long nr_uninterruptible;
> 	unsigned long long timestamp_last_tick;
>+	unsigned int cache_ticks, preempted;
> 	task_t *curr, *idle;
> 	struct mm_struct *prev_mm;
>-	prio_array_t *active, *expired, arrays[2];
>-	int best_expired_prio;
>+	unsigned long bitmap[BITS_TO_LONGS(MAX_PRIO+1)];
>+	struct list_head queue[MAX_PRIO + 1];
> 	atomic_t nr_iowait;
> 
> #ifdef CONFIG_SMP
>@@ -297,67 +188,53 @@
> 	spin_unlock_irq(&rq->lock);
> }
> 
>-/*
>- * Adding/removing a task to/from a priority array:
>- */
>-static void dequeue_task(struct task_struct *p, prio_array_t *array)
>+static int task_preempts_curr(struct task_struct *p, runqueue_t *rq)
> {
>-	array->nr_active--;
>-	list_del(&p->run_list);
>-	if (list_empty(array->queue + p->prio))
>-		__clear_bit(p->prio, array->bitmap);
>+	if (p->prio >= rq->curr->prio)
>+		return 0;
>+	if (!compute || rq->cache_ticks >= cache_decay_ticks ||
>+		rt_task(p) || !p->mm || rq->curr == rq->idle) {
>+			rq->curr->flags |= PF_PREEMPTED;
>+			return 1;
>+	}
>+	rq->preempted = 1;
>+		return 0;
> }
> 
>-static void enqueue_task(struct task_struct *p, prio_array_t *array)
>+static inline int task_queued(task_t *task)
> {
>-	list_add_tail(&p->run_list, array->queue + p->prio);
>-	__set_bit(p->prio, array->bitmap);
>-	array->nr_active++;
>-	p->array = array;
>+	return !list_empty(&task->run_list);
> }
> 
> /*
>- * Used by the migration code - we pull tasks from the head of the
>- * remote queue so we want these tasks to show up at the head of the
>- * local queue:
>+ * Adding/removing a task to/from a runqueue:
>  */
>-static inline void enqueue_task_head(struct task_struct *p, prio_array_t *array)
>+static void dequeue_task(struct task_struct *p, runqueue_t *rq)
> {
>-	list_add(&p->run_list, array->queue + p->prio);
>-	__set_bit(p->prio, array->bitmap);
>-	array->nr_active++;
>-	p->array = array;
>+	list_del_init(&p->run_list);
>+	if (list_empty(rq->queue + p->prio))
>+		__clear_bit(p->prio, rq->bitmap);
>+}
>+
>+static void enqueue_task(struct task_struct *p, runqueue_t *rq)
>+{
>+	if (rq->curr->flags & PF_PREEMPTED) {
>+		rq->curr->flags &= ~PF_PREEMPTED;
>+		list_add(&p->run_list, rq->queue + p->prio);
>+	} else
>+		list_add_tail(&p->run_list, rq->queue + p->prio);
>+	__set_bit(p->prio, rq->bitmap);
> }
> 
> /*
>- * effective_prio - return the priority that is based on the static
>- * priority but is modified by bonuses/penalties.
>- *
>- * We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
>- * into the -5 ... 0 ... +5 bonus/penalty range.
>- *
>- * We use 25% of the full 0...39 priority range so that:
>- *
>- * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
>- * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
>- *
>- * Both properties are important to certain workloads.
>+ * Used by the migration code - we pull tasks from the head of the
>+ * remote queue so we want these tasks to show up at the head of the
>+ * local queue:
>  */
>-static int effective_prio(task_t *p)
>+static inline void enqueue_task_head(struct task_struct *p, runqueue_t *rq)
> {
>-	int bonus, prio;
>-
>-	if (rt_task(p))
>-		return p->prio;
>-
>-	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
>-
>-	prio = p->static_prio - bonus;
>-	if (prio < MAX_RT_PRIO)
>-		prio = MAX_RT_PRIO;
>-	if (prio > MAX_PRIO-1)
>-		prio = MAX_PRIO-1;
>-	return prio;
>+	list_add(&p->run_list, rq->queue + p->prio);
>+	__set_bit(p->prio, rq->bitmap);
> }
> 
> /*
>@@ -365,7 +242,7 @@
>  */
> static inline void __activate_task(task_t *p, runqueue_t *rq)
> {
>-	enqueue_task(p, rq->active);
>+	enqueue_task(p, rq);
> 	rq->nr_running++;
> }
> 
>@@ -374,95 +251,109 @@
>  */
> static inline void __activate_idle_task(task_t *p, runqueue_t *rq)
> {
>-	enqueue_task_head(p, rq->active);
>+	enqueue_task_head(p, rq);
> 	rq->nr_running++;
> }
> 
>-static void recalc_task_prio(task_t *p, unsigned long long now)
>+// burst - extra intervals an interactive task can run for at best priority
>+static unsigned int burst(task_t *p)
> {
>-	unsigned long long __sleep_time = now - p->timestamp;
>-	unsigned long sleep_time;
>-
>-	if (__sleep_time > NS_MAX_SLEEP_AVG)
>-		sleep_time = NS_MAX_SLEEP_AVG;
>+	unsigned int task_user_prio;
>+	if (rt_task(p))
>+		return p->burst;
>+	task_user_prio = TASK_USER_PRIO(p);
>+	if (likely(task_user_prio < 40))
>+		return 39 - task_user_prio;
> 	else
>-		sleep_time = (unsigned long)__sleep_time;
>+		return 0;
>+}
> 
>-	if (likely(sleep_time > 0)) {
>-		/*
>-		 * User tasks that sleep a long time are categorised as
>-		 * idle and will get just interactive status to stay active &
>-		 * prevent them suddenly becoming cpu hogs and starving
>-		 * other processes.
>-		 */
>-		if (p->mm && p->activated != -1 &&
>-			sleep_time > INTERACTIVE_SLEEP(p)) {
>-				p->sleep_avg = JIFFIES_TO_NS(MAX_SLEEP_AVG -
>-						AVG_TIMESLICE);
>-				if (!HIGH_CREDIT(p))
>-					p->interactive_credit++;
>-		} else {
>-			/*
>-			 * The lower the sleep avg a task has the more
>-			 * rapidly it will rise with sleep time.
>-			 */
>-			sleep_time *= (MAX_BONUS - CURRENT_BONUS(p)) ? : 1;
>+static void inc_burst(task_t *p)
>+{
>+	unsigned int best_burst;
>+	best_burst = burst(p);
>+	if (p->burst < best_burst)
>+		p->burst++;
>+}
> 
>-			/*
>-			 * Tasks with low interactive_credit are limited to
>-			 * one timeslice worth of sleep avg bonus.
>-			 */
>-			if (LOW_CREDIT(p) &&
>-			    sleep_time > JIFFIES_TO_NS(task_timeslice(p)))
>-				sleep_time = JIFFIES_TO_NS(task_timeslice(p));
>+static void dec_burst(task_t *p)
>+{
>+	if (p->burst)
>+		p->burst--;
>+}
> 
>-			/*
>-			 * Non high_credit tasks waking from uninterruptible
>-			 * sleep are limited in their sleep_avg rise as they
>-			 * are likely to be cpu hogs waiting on I/O
>-			 */
>-			if (p->activated == -1 && !HIGH_CREDIT(p) && p->mm) {
>-				if (p->sleep_avg >= INTERACTIVE_SLEEP(p))
>-					sleep_time = 0;
>-				else if (p->sleep_avg + sleep_time >=
>-						INTERACTIVE_SLEEP(p)) {
>-					p->sleep_avg = INTERACTIVE_SLEEP(p);
>-					sleep_time = 0;
>-				}
>-			}
>+// slice - the duration a task runs before losing burst
>+static unsigned int slice(task_t *p)
>+{
>+	unsigned int slice = RR_INTERVAL;
>+	if (!rt_task(p))
>+		slice += burst(p) * RR_INTERVAL;
>+	return slice;
>+}
> 
>-			/*
>-			 * This code gives a bonus to interactive tasks.
>-			 *
>-			 * The boost works by updating the 'average sleep time'
>-			 * value here, based on ->timestamp. The more time a
>-			 * task spends sleeping, the higher the average gets -
>-			 * and the higher the priority boost gets as well.
>-			 */
>-			p->sleep_avg += sleep_time;
>+// interactive - interactive tasks get longer intervals at best priority
>+int interactive = 1;
> 
>-			if (p->sleep_avg > NS_MAX_SLEEP_AVG) {
>-				p->sleep_avg = NS_MAX_SLEEP_AVG;
>-				if (!HIGH_CREDIT(p))
>-					p->interactive_credit++;
>+/*
>+ * effective_prio - dynamic priority dependent on burst.
>+ * The priority normally decreases by one each RR_INTERVAL.
>+ * As the burst increases the priority stays at the top "stair" or
>+ * priority for longer.
>+ */
>+static int effective_prio(task_t *p)
>+{
>+	int prio;
>+	unsigned int full_slice, used_slice, first_slice;
>+	unsigned int best_burst;
>+	if (rt_task(p))
>+		return p->prio;
>+
>+	best_burst = burst(p);
>+	full_slice = slice(p);
>+	used_slice = full_slice - p->slice;
>+	if (p->burst > best_burst)
>+		p->burst = best_burst;
>+	first_slice = RR_INTERVAL;
>+	if (interactive && !compute)
>+		first_slice *= (p->burst + 1);
>+	prio = MAX_PRIO - 1 - best_burst;
>+
>+	if (used_slice < first_slice)
>+		return prio;
>+	prio += 1 + (used_slice - first_slice) / RR_INTERVAL;
>+	if (prio > MAX_PRIO - 1)
>+		prio = MAX_PRIO - 1;
>+	return prio;
>+}
>+
>+static void recalc_task_prio(task_t *p, unsigned long long now)
>+{
>+	unsigned long sleep_time = now - p->timestamp;
>+	unsigned long run_time = NS_TO_JIFFIES(p->runtime);
>+	unsigned long total_run = NS_TO_JIFFIES(p->totalrun) + run_time;
>+	if ((!run_time && NS_TO_JIFFIES(p->runtime + sleep_time) <
>+		RR_INTERVAL) || p->flags & PF_FORKED) {
>+			p->flags &= ~PF_FORKED;
>+			if (p->slice - total_run < 1) {
>+				p->totalrun = 0;
>+				dec_burst(p);
>+			} else {
>+				p->totalrun += p->runtime;
>+				p->slice -= NS_TO_JIFFIES(p->totalrun);
> 			}
>-		}
>+	} else {
>+		inc_burst(p);
>+		p->runtime = 0;
>+		p->totalrun = 0;
> 	}
>-
>-	p->prio = effective_prio(p);
> }
> 
> /*
>  * activate_task - move a task to the runqueue and do priority recalculation
>- *
>- * Update all the scheduling statistics stuff. (sleep average
>- * calculation, priority modifiers, etc.)
>  */
> static void activate_task(task_t *p, runqueue_t *rq, int local)
> {
>-	unsigned long long now;
>-
>-	now = sched_clock();
>+	unsigned long long now = sched_clock();
> #ifdef CONFIG_SMP
> 	if (!local) {
> 		/* Compensate for drifting sched_clock */
>@@ -471,33 +362,11 @@
> 			+ rq->timestamp_last_tick;
> 	}
> #endif
>-
>+	p->slice = slice(p);
> 	recalc_task_prio(p, now);
>-
>-	/*
>-	 * This checks to make sure it's not an uninterruptible task
>-	 * that is now waking up.
>-	 */
>-	if (!p->activated) {
>-		/*
>-		 * Tasks which were woken up by interrupts (ie. hw events)
>-		 * are most likely of interactive nature. So we give them
>-		 * the credit of extending their sleep time to the period
>-		 * of time they spend on the runqueue, waiting for execution
>-		 * on a CPU, first time around:
>-		 */
>-		if (in_interrupt())
>-			p->activated = 2;
>-		else {
>-			/*
>-			 * Normal first-time wakeups get a credit too for
>-			 * on-runqueue time, but it will be weighted down:
>-			 */
>-			p->activated = 1;
>-		}
>-	}
>+	p->prio = effective_prio(p);
>+	p->time_slice = RR_INTERVAL;
> 	p->timestamp = now;
>-
> 	__activate_task(p, rq);
> }
> 
>@@ -509,8 +378,7 @@
> 	rq->nr_running--;
> 	if (p->state == TASK_UNINTERRUPTIBLE)
> 		rq->nr_uninterruptible++;
>-	dequeue_task(p, p->array);
>-	p->array = NULL;
>+	dequeue_task(p, rq);
> }
> 
> /*
>@@ -583,7 +451,7 @@
> 	 * If the task is not on a runqueue (and not running), then
> 	 * it is sufficient to simply update the task's cpu field.
> 	 */
>-	if (!p->array && !task_running(rq, p)) {
>+	if (!task_queued(p) && !task_running(rq, p)) {
> 		set_task_cpu(p, dest_cpu);
> 		return 0;
> 	}
>@@ -614,7 +482,7 @@
> repeat:
> 	rq = task_rq_lock(p, &flags);
> 	/* Must be off runqueue entirely, not preempted. */
>-	if (unlikely(p->array)) {
>+	if (unlikely(task_queued(p))) {
> 		/* If it's preempted, we yield.  It could be a while. */
> 		preempted = !task_running(rq, p);
> 		task_rq_unlock(rq, &flags);
>@@ -744,7 +612,7 @@
> 	if (!(old_state & state))
> 		goto out;
> 
>-	if (p->array)
>+	if (task_queued(p))
> 		goto out_running;
> 
> 	cpu = task_cpu(p);
>@@ -811,7 +679,7 @@
> 		old_state = p->state;
> 		if (!(old_state & state))
> 			goto out;
>-		if (p->array)
>+		if (task_queued(p))
> 			goto out_running;
> 
> 		this_cpu = smp_processor_id();
>@@ -820,14 +688,8 @@
> 
> out_activate:
> #endif /* CONFIG_SMP */
>-	if (old_state == TASK_UNINTERRUPTIBLE) {
>+	if (old_state == TASK_UNINTERRUPTIBLE)
> 		rq->nr_uninterruptible--;
>-		/*
>-		 * Tasks on involuntary sleep don't earn
>-		 * sleep_avg beyond just interactive state.
>-		 */
>-		p->activated = -1;
>-	}
> 
> 	/*
> 	 * Sync wakeups (i.e. those types of wakeups where the waker
>@@ -839,7 +701,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;
>@@ -879,7 +741,6 @@
> 	 */
> 	p->state = TASK_RUNNING;
> 	INIT_LIST_HEAD(&p->run_list);
>-	p->array = NULL;
> 	spin_lock_init(&p->switch_lock);
> #ifdef CONFIG_PREEMPT
> 	/*
>@@ -890,33 +751,6 @@
> 	 */
> 	p->thread_info->preempt_count = 1;
> #endif
>-	/*
>-	 * Share the timeslice between parent and child, thus the
>-	 * total amount of pending timeslices in the system doesn't change,
>-	 * resulting in more scheduling fairness.
>-	 */
>-	local_irq_disable();
>-	p->time_slice = (current->time_slice + 1) >> 1;
>-	/*
>-	 * The remainder of the first timeslice might be recovered by
>-	 * the parent if the child exits early enough.
>-	 */
>-	p->first_time_slice = 1;
>-	current->time_slice >>= 1;
>-	p->timestamp = sched_clock();
>-	if (!current->time_slice) {
>-		/*
>-		 * This case is rare, it happens when the parent has only
>-		 * a single jiffy left from its timeslice. Taking the
>-		 * runqueue lock is not a problem.
>-		 */
>-		current->time_slice = 1;
>-		preempt_disable();
>-		scheduler_tick(0, 0);
>-		local_irq_enable();
>-		preempt_enable();
>-	} else
>-		local_irq_enable();
> }
> 
> /*
>@@ -930,66 +764,14 @@
> 	unsigned long flags;
> 	runqueue_t *rq = task_rq_lock(current, &flags);
> 
>+	//Forked process gets no burst to prevent fork bombs.
>+	p->burst = 0;
> 	BUG_ON(p->state != TASK_RUNNING);
> 
>-	/*
>-	 * We decrease the sleep average of forking parents
>-	 * and children as well, to keep max-interactive tasks
>-	 * from forking tasks that are max-interactive.
>-	 */
>-	current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) *
>-		PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
>-
>-	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
>-		CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
>-
>-	p->interactive_credit = 0;
>-
>-	p->prio = effective_prio(p);
> 	set_task_cpu(p, smp_processor_id());
> 
>-	if (unlikely(!current->array))
>-		__activate_task(p, rq);
>-	else {
>-		p->prio = current->prio;
>-		list_add_tail(&p->run_list, &current->run_list);
>-		p->array = current->array;
>-		p->array->nr_active++;
>-		rq->nr_running++;
>-	}
>-	task_rq_unlock(rq, &flags);
>-}
>-
>-/*
>- * Potentially available exiting-child timeslices are
>- * retrieved here - this way the parent does not get
>- * penalized for creating too many threads.
>- *
>- * (this cannot be used to 'generate' timeslices
>- * artificially, because any timeslice recovered here
>- * was given away by the parent in the first place.)
>- */
>-void fastcall sched_exit(task_t * p)
>-{
>-	unsigned long flags;
>-	runqueue_t *rq;
>-
>-	local_irq_save(flags);
>-	if (p->first_time_slice) {
>-		p->parent->time_slice += p->time_slice;
>-		if (unlikely(p->parent->time_slice > MAX_TIMESLICE))
>-			p->parent->time_slice = MAX_TIMESLICE;
>-	}
>-	local_irq_restore(flags);
>-	/*
>-	 * If the child was a (relative-) CPU hog then decrease
>-	 * the sleep_avg of the parent as well.
>-	 */
>-	rq = task_rq_lock(p->parent, &flags);
>-	if (p->sleep_avg < p->parent->sleep_avg)
>-		p->parent->sleep_avg = p->parent->sleep_avg /
>-		(EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
>-		(EXIT_WEIGHT + 1);
>+	__activate_task(p, rq);
>+	current->flags |= PF_FORKED;
> 	task_rq_unlock(rq, &flags);
> }
> 
>@@ -1253,30 +1035,16 @@
> 		double_rq_unlock(this_rq, rq);
> 		goto lock_again;
> 	}
>-	/*
>-	 * We decrease the sleep average of forking parents
>-	 * and children as well, to keep max-interactive tasks
>-	 * from forking tasks that are max-interactive.
>-	 */
>-	current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) *
>-		PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
>-
>-	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
>-		CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
>-
>-	p->interactive_credit = 0;
> 
> 	p->prio = effective_prio(p);
> 	set_task_cpu(p, cpu);
> 
> 	if (cpu == this_cpu) {
>-		if (unlikely(!current->array))
>+		if (unlikely(!task_queued(current)))
> 			__activate_task(p, rq);
> 		else {
> 			p->prio = current->prio;
> 			list_add_tail(&p->run_list, &current->run_list);
>-			p->array = current->array;
>-			p->array->nr_active++;
> 			rq->nr_running++;
> 		}
> 	} else {
>@@ -1284,7 +1052,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);
> 	}
> 
>@@ -1376,22 +1144,22 @@
>  * pull_task - move a task from a remote runqueue to the local runqueue.
>  * Both runqueues must be locked.
>  */
>-static inline
>-void pull_task(runqueue_t *src_rq, prio_array_t *src_array, task_t *p,
>-	       runqueue_t *this_rq, prio_array_t *this_array, int this_cpu)
>+static inline 
>+void pull_task(runqueue_t *src_rq, task_t *p, 
>+		runqueue_t *this_rq, int this_cpu)
> {
>-	dequeue_task(p, src_array);
>+	dequeue_task(p, src_rq);
> 	src_rq->nr_running--;
> 	set_task_cpu(p, this_cpu);
> 	this_rq->nr_running++;
>-	enqueue_task(p, this_array);
>+	enqueue_task(p, this_rq);
> 	p->timestamp = (p->timestamp - src_rq->timestamp_last_tick)
> 				+ this_rq->timestamp_last_tick;
> 	/*
> 	 * 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);
> }
> 
>@@ -1434,7 +1202,6 @@
> 		      unsigned long max_nr_move, struct sched_domain *sd,
> 		      enum idle_type idle)
> {
>-	prio_array_t *array, *dst_array;
> 	struct list_head *head, *curr;
> 	int idx, pulled = 0;
> 	task_t *tmp;
>@@ -1442,38 +1209,17 @@
> 	if (max_nr_move <= 0 || busiest->nr_running <= 1)
> 		goto out;
> 
>-	/*
>-	 * We first consider expired tasks. Those will likely not be
>-	 * executed in the near future, and they are most likely to
>-	 * be cache-cold, thus switching CPUs has the least effect
>-	 * on them.
>-	 */
>-	if (busiest->expired->nr_active) {
>-		array = busiest->expired;
>-		dst_array = this_rq->expired;
>-	} else {
>-		array = busiest->active;
>-		dst_array = this_rq->active;
>-	}
>-
>-new_array:
> 	/* Start searching at priority 0: */
> 	idx = 0;
> skip_bitmap:
> 	if (!idx)
>-		idx = sched_find_first_bit(array->bitmap);
>+		idx = sched_find_first_bit(busiest->bitmap);
> 	else
>-		idx = find_next_bit(array->bitmap, MAX_PRIO, idx);
>-	if (idx >= MAX_PRIO) {
>-		if (array == busiest->expired && busiest->active->nr_active) {
>-			array = busiest->active;
>-			dst_array = this_rq->active;
>-			goto new_array;
>-		}
>+		idx = find_next_bit(busiest->bitmap, MAX_PRIO, idx);
>+	if (idx >= MAX_PRIO) 
> 		goto out;
>-	}
> 
>-	head = array->queue + idx;
>+	head = busiest->queue + idx;
> 	curr = head->prev;
> skip_queue:
> 	tmp = list_entry(curr, task_t, run_list);
>@@ -1486,7 +1232,7 @@
> 		idx++;
> 		goto skip_bitmap;
> 	}
>-	pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu);
>+	pull_task(busiest, tmp, this_rq, this_cpu);
> 	pulled++;
> 
> 	/* We only want to steal up to the prescribed number of tasks. */
>@@ -1956,22 +1702,6 @@
> EXPORT_PER_CPU_SYMBOL(kstat);
> 
> /*
>- * We place interactive tasks back into the active array, if possible.
>- *
>- * To guarantee that this does not starve expired tasks we ignore the
>- * interactivity of a task if the first expired task had to wait more
>- * than a 'reasonable' amount of time. This deadline timeout is
>- * load-dependent, as the frequency of array switched decreases with
>- * increasing number of running tasks. We also ignore the interactivity
>- * if a better static_prio task has expired:
>- */
>-#define EXPIRED_STARVING(rq) \
>-	((STARVATION_LIMIT && ((rq)->expired_timestamp && \
>-		(jiffies - (rq)->expired_timestamp >= \
>-			STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
>-			((rq)->curr->static_prio > (rq)->best_expired_prio))
>-
>-/*
>  * This function gets called by the timer code, with HZ frequency.
>  * We call it with interrupts disabled.
>  *
>@@ -2015,78 +1745,36 @@
> 		cpustat->user += user_ticks;
> 	cpustat->system += sys_ticks;
> 
>-	/* Task might have expired already, but not scheduled off yet */
>-	if (p->array != rq->active) {
>+	spin_lock(&rq->lock);
>+	// SCHED_FIFO tasks never run out of timeslice.
>+	if (unlikely(p->policy == SCHED_FIFO))
>+		goto out_unlock;
>+	rq->cache_ticks++;
>+	// Tasks lose burst each time they use up a full slice().
>+	if (!--p->slice) {
> 		set_tsk_need_resched(p);
>-		goto out;
>+		dequeue_task(p, rq);
>+		dec_burst(p);
>+		p->slice = slice(p);
>+		p->prio = effective_prio(p);
>+		p->time_slice = RR_INTERVAL;
>+		enqueue_task(p, rq);
>+		goto out_unlock;
> 	}
>-	spin_lock(&rq->lock);
> 	/*
>-	 * The task was running during this tick - update the
>-	 * time slice counter. Note: we do not update a thread's
>-	 * priority until it either goes to sleep or uses up its
>-	 * timeslice. This makes it possible for interactive tasks
>-	 * to use up their timeslices at their highest priority levels.
>+	 * Tasks that run out of time_slice but still have slice left get
>+	 * requeued with a lower priority && RR_INTERVAL time_slice.
> 	 */
>-	if (unlikely(rt_task(p))) {
>-		/*
>-		 * RR tasks need a special form of timeslice management.
>-		 * FIFO tasks have no timeslices.
>-		 */
>-		if ((p->policy == SCHED_RR) && !--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: */
>-			dequeue_task(p, rq->active);
>-			enqueue_task(p, rq->active);
>-		}
>-		goto out_unlock;
>-	}
> 	if (!--p->time_slice) {
>-		dequeue_task(p, rq->active);
> 		set_tsk_need_resched(p);
>+		dequeue_task(p, rq);
> 		p->prio = effective_prio(p);
>-		p->time_slice = task_timeslice(p);
>-		p->first_time_slice = 0;
>-
>-		if (!rq->expired_timestamp)
>-			rq->expired_timestamp = jiffies;
>-		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
>-			enqueue_task(p, rq->expired);
>-			if (p->static_prio < rq->best_expired_prio)
>-				rq->best_expired_prio = p->static_prio;
>-		} else
>-			enqueue_task(p, rq->active);
>-	} else {
>-		/*
>-		 * Prevent a too long timeslice allowing a task to monopolize
>-		 * the CPU. We do this by splitting up the timeslice into
>-		 * smaller pieces.
>-		 *
>-		 * Note: this does not mean the task's timeslices expire or
>-		 * get lost in any way, they just might be preempted by
>-		 * another task of equal priority. (one with higher
>-		 * priority would have preempted this task already.) We
>-		 * requeue this task to the end of the list on this priority
>-		 * level, which is in essence a round-robin of tasks with
>-		 * equal priority.
>-		 *
>-		 * This only applies to tasks in the interactive
>-		 * delta range with at least TIMESLICE_GRANULARITY to requeue.
>-		 */
>-		if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
>-			p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
>-			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
>-			(p->array == rq->active)) {
>-
>-			dequeue_task(p, rq->active);
>-			set_tsk_need_resched(p);
>-			p->prio = effective_prio(p);
>-			enqueue_task(p, rq->active);
>-		}
>+		p->time_slice = RR_INTERVAL;
>+		enqueue_task(p, rq);
>+		goto out_unlock;
> 	}
>+	if (rq->preempted && rq->cache_ticks >= cache_decay_ticks)
>+		set_tsk_need_resched(p);
> out_unlock:
> 	spin_unlock(&rq->lock);
> out:
>@@ -2149,8 +1837,8 @@
> 		 * task from using an unfair proportion of the
> 		 * physical cpu's resources. -ck
> 		 */
>-		if (((smt_curr->time_slice * (100 - sd->per_cpu_gain) / 100) >
>-			task_timeslice(p) || rt_task(smt_curr)) &&
>+		if (((smt_curr->slice * (100 - sd->per_cpu_gain) / 100) >
>+			slice(p) || rt_task(smt_curr)) &&
> 			p->mm && smt_curr->mm && !rt_task(p))
> 				ret = 1;
> 
>@@ -2159,8 +1847,8 @@
> 		 * or wake it up if it has been put to sleep for priority
> 		 * reasons.
> 		 */
>-		if ((((p->time_slice * (100 - sd->per_cpu_gain) / 100) >
>-			task_timeslice(smt_curr) || rt_task(p)) &&
>+		if ((((p->slice * (100 - sd->per_cpu_gain) / 100) > 
>+			slice(smt_curr) || rt_task(p)) && 
> 			smt_curr->mm && p->mm && !rt_task(smt_curr)) ||
> 			(smt_curr == smt_rq->idle && smt_rq->nr_running))
> 				resched_task(smt_curr);
>@@ -2186,10 +1874,8 @@
> 	long *switch_count;
> 	task_t *prev, *next;
> 	runqueue_t *rq;
>-	prio_array_t *array;
> 	struct list_head *queue;
> 	unsigned long long now;
>-	unsigned long run_time;
> 	int cpu, idx;
> 
> 	/*
>@@ -2211,19 +1897,8 @@
> 
> 	release_kernel_lock(prev);
> 	now = sched_clock();
>-	if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
>-		run_time = now - prev->timestamp;
>-	else
>-		run_time = NS_MAX_SLEEP_AVG;
>-
>-	/*
>-	 * Tasks with interactive credits get charged less run_time
>-	 * at high sleep_avg to delay them losing their interactive
>-	 * status
>-	 */
>-	if (HIGH_CREDIT(prev))
>-		run_time /= (CURRENT_BONUS(prev) ? : 1);
> 
>+	prev->runtime = now - prev->timestamp;
> 	spin_lock_irq(&rq->lock);
> 
> 	/*
>@@ -2245,59 +1920,26 @@
> 		idle_balance(cpu, rq);
> 		if (!rq->nr_running) {
> 			next = rq->idle;
>-			rq->expired_timestamp = 0;
> 			wake_sleeping_dependent(cpu, rq);
> 			goto switch_tasks;
> 		}
> 	}
> 
>-	array = rq->active;
>-	if (unlikely(!array->nr_active)) {
>-		/*
>-		 * Switch the active and expired arrays.
>-		 */
>-		rq->active = rq->expired;
>-		rq->expired = array;
>-		array = rq->active;
>-		rq->expired_timestamp = 0;
>-		rq->best_expired_prio = MAX_PRIO;
>-	}
>-
>-	idx = sched_find_first_bit(array->bitmap);
>-	queue = array->queue + idx;
>+	idx = sched_find_first_bit(rq->bitmap);
>+	queue = rq->queue + idx;
> 	next = list_entry(queue->next, task_t, run_list);
> 
>-	if (dependent_sleeper(cpu, rq, next)) {
>+	if (dependent_sleeper(cpu, rq, next))
> 		next = rq->idle;
>-		goto switch_tasks;
>-	}
>-
>-	if (!rt_task(next) && next->activated > 0) {
>-		unsigned long long delta = now - next->timestamp;
>-
>-		if (next->activated == 1)
>-			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
>-
>-		array = next->array;
>-		dequeue_task(next, array);
>-		recalc_task_prio(next, next->timestamp + delta);
>-		enqueue_task(next, array);
>-	}
>-	next->activated = 0;
> switch_tasks:
> 	prefetch(next);
> 	clear_tsk_need_resched(prev);
> 	RCU_qsctr(task_cpu(prev))++;
>-
>-	prev->sleep_avg -= run_time;
>-	if ((long)prev->sleep_avg <= 0) {
>-		prev->sleep_avg = 0;
>-		if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
>-			prev->interactive_credit--;
>-	}
> 	prev->timestamp = now;
> 
> 	if (likely(prev != next)) {
>+		rq->preempted = 0;
>+		rq->cache_ticks = 0;
> 		next->timestamp = now;
> 		rq->nr_switches++;
> 		rq->curr = next;
>@@ -2560,9 +2202,8 @@
> void set_user_nice(task_t *p, long nice)
> {
> 	unsigned long flags;
>-	prio_array_t *array;
> 	runqueue_t *rq;
>-	int old_prio, new_prio, delta;
>+	int queued, old_prio, new_prio, delta;
> 
> 	if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
> 		return;
>@@ -2581,9 +2222,8 @@
> 		p->static_prio = NICE_TO_PRIO(nice);
> 		goto out_unlock;
> 	}
>-	array = p->array;
>-	if (array)
>-		dequeue_task(p, array);
>+	if ((queued = task_queued(p)))
>+		dequeue_task(p, rq);
> 
> 	old_prio = p->prio;
> 	new_prio = NICE_TO_PRIO(nice);
>@@ -2591,8 +2231,8 @@
> 	p->static_prio = NICE_TO_PRIO(nice);
> 	p->prio += delta;
> 
>-	if (array) {
>-		enqueue_task(p, array);
>+	if (queued) {
>+		enqueue_task(p, rq);
> 		/*
> 		 * If the task increased its priority or is running and
> 		 * lowered its priority, then reschedule its CPU:
>@@ -2697,7 +2337,7 @@
> /* Actually do priority change: must hold rq lock. */
> static void __setscheduler(struct task_struct *p, int policy, int prio)
> {
>-	BUG_ON(p->array);
>+	BUG_ON(task_queued(p));
> 	p->policy = policy;
> 	p->rt_priority = prio;
> 	if (policy != SCHED_NORMAL)
>@@ -2713,8 +2353,7 @@
> {
> 	struct sched_param lp;
> 	int retval = -EINVAL;
>-	int oldprio;
>-	prio_array_t *array;
>+	int queued, oldprio;
> 	unsigned long flags;
> 	runqueue_t *rq;
> 	task_t *p;
>@@ -2774,13 +2413,12 @@
> 	if (retval)
> 		goto out_unlock;
> 
>-	array = p->array;
>-	if (array)
>+	if ((queued = task_queued(p)))
> 		deactivate_task(p, task_rq(p));
> 	retval = 0;
> 	oldprio = p->prio;
> 	__setscheduler(p, policy, lp.sched_priority);
>-	if (array) {
>+	if (queued) {
> 		__activate_task(p, task_rq(p));
> 		/*
> 		 * Reschedule if we are currently running on this runqueue and
>@@ -2790,7 +2428,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);
> 	}
> 
>@@ -2983,28 +2621,19 @@
> /**
>  * sys_sched_yield - yield the current processor to other threads.
>  *
>- * this function yields the current CPU by moving the calling thread
>- * to the expired array. If there are no other threads running on this
>  * CPU then this function will return.
>  */
> asmlinkage long sys_sched_yield(void)
> {
> 	runqueue_t *rq = this_rq_lock();
>-	prio_array_t *array = current->array;
>-	prio_array_t *target = rq->expired;
>-
>-	/*
>-	 * We implement yielding by moving the task into the expired
>-	 * queue.
>-	 *
>-	 * (special rule: RT tasks will just roundrobin in the active
>-	 *  array.)
>-	 */
>-	if (unlikely(rt_task(current)))
>-		target = rq->active;
> 
>-	dequeue_task(current, array);
>-	enqueue_task(current, target);
>+	dequeue_task(current, rq);
>+ 	current->slice = slice(current);
>+ 	current->time_slice = RR_INTERVAL;
>+	if (!rt_task(current))
>+		current->prio = MAX_PRIO - 1;
>+	current->burst = 0;
>+	enqueue_task(current, rq);
> 
> 	/*
> 	 * Since we are going to call schedule() anyway, there's
>@@ -3143,7 +2772,7 @@
> 		goto out_unlock;
> 
> 	jiffies_to_timespec(p->policy & SCHED_FIFO ?
>-				0 : task_timeslice(p), &t);
>+				0 : slice(p), &t);
> 	read_unlock(&tasklist_lock);
> 	retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
> out_nounlock:
>@@ -3261,9 +2890,9 @@
> 
> 	idle_rq->curr = idle_rq->idle = idle;
> 	deactivate_task(idle, rq);
>-	idle->array = NULL;
> 	idle->prio = MAX_PRIO;
> 	idle->state = TASK_RUNNING;
>+	idle->burst = 0;
> 	set_task_cpu(idle, cpu);
> 	double_rq_unlock(idle_rq, rq);
> 	set_tsk_need_resched(idle);
>@@ -3372,7 +3001,7 @@
> 		goto out;
> 
> 	set_task_cpu(p, dest_cpu);
>-	if (p->array) {
>+	if (task_queued(p)) {
> 		/*
> 		 * Sync timestamp with rq_dest's before activating.
> 		 * The same thing could be achieved by doing this step
>@@ -3383,7 +3012,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);
> 	}
> 
>@@ -3896,7 +3525,7 @@
> void __init sched_init(void)
> {
> 	runqueue_t *rq;
>-	int i, j, k;
>+	int i, j;
> 
> #ifdef CONFIG_SMP
> 	/* Set up an initial dummy domain for early boot */
>@@ -3917,13 +3546,11 @@
> #endif
> 
> 	for (i = 0; i < NR_CPUS; i++) {
>-		prio_array_t *array;
>-
> 		rq = cpu_rq(i);
> 		spin_lock_init(&rq->lock);
>-		rq->active = rq->arrays;
>-		rq->expired = rq->arrays + 1;
>-		rq->best_expired_prio = MAX_PRIO;
>+		
>+		rq->cache_ticks = 0;
>+		rq->preempted = 0;
> 
> #ifdef CONFIG_SMP
> 		rq->sd = &sched_domain_init;
>@@ -3934,16 +3561,11 @@
> 		INIT_LIST_HEAD(&rq->migration_queue);
> #endif
> 		atomic_set(&rq->nr_iowait, 0);
>-
>-		for (j = 0; j < 2; j++) {
>-			array = rq->arrays + j;
>-			for (k = 0; k < MAX_PRIO; k++) {
>-				INIT_LIST_HEAD(array->queue + k);
>-				__clear_bit(k, array->bitmap);
>-			}
>-			// delimiter for bitsearch
>-			__set_bit(MAX_PRIO, array->bitmap);
>-		}
>+		for (j = 0; j <= MAX_PRIO; j++)
>+			INIT_LIST_HEAD(&rq->queue[j]);
>+		memset(rq->bitmap, 0, BITS_TO_LONGS(MAX_PRIO+1)*sizeof(long));
>+		// delimiter for bitsearch
>+		__set_bit(MAX_PRIO, rq->bitmap);
> 	}
> 	/*
> 	 * We have to do a little magic to get the first
>Index: linux-2.6.7-staircase/kernel/sysctl.c
>===================================================================
>--- linux-2.6.7-staircase.orig/kernel/sysctl.c	2004-06-25 02:24:28.112116264 +1000
>+++ linux-2.6.7-staircase/kernel/sysctl.c	2004-06-25 02:24:33.895207459 +1000
>@@ -636,6 +636,22 @@
> 		.mode		= 0444,
> 		.proc_handler	= &proc_dointvec,
> 	},
>+	{
>+		.ctl_name	= KERN_INTERACTIVE,
>+		.procname	= "interactive",
>+		.data		= &interactive,
>+		.maxlen		= sizeof (int),
>+		.mode		= 0644,
>+		.proc_handler	= &proc_dointvec,
>+	},
>+	{
>+		.ctl_name	= KERN_COMPUTE,
>+		.procname	= "compute",
>+		.data		= &compute,
>+		.maxlen		= sizeof (int),
>+		.mode		= 0644,
>+		.proc_handler	= &proc_dointvec,
>+	},
> 	{ .ctl_name = 0 }
> };
> 
>  
>