Index: Linux-2.6.X/fs/proc/array.c
diff -u Linux-2.6.X/fs/proc/array.c:1.1.1.4 Linux-2.6.X/fs/proc/array.c:1.1.1.4.22.1.4.1
--- Linux-2.6.X/fs/proc/array.c:1.1.1.4	Fri Jun  4 14:29:01 2004
+++ Linux-2.6.X/fs/proc/array.c	Thu Jun 17 14:00:58 2004
@@ -155,7 +155,6 @@
 	read_lock(&tasklist_lock);
 	buffer += sprintf(buffer,
 		"State:\t%s\n"
-		"SleepAVG:\t%lu%%\n"
 		"Tgid:\t%d\n"
 		"Pid:\t%d\n"
 		"PPid:\t%d\n"
@@ -163,7 +162,6 @@
 		"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->tgid,
 		p->pid, p->pid ? p->real_parent->pid : 0,
 		p->pid && p->ptrace ? p->parent->pid : 0,
@@ -427,3 +425,25 @@
 	return sprintf(buffer,"%d %d %d %d %d %d %d\n",
 		       size, resident, shared, text, lib, data, 0);
 }
+
+int task_cpu_sched_stats(struct task_struct *p, char *buffer)
+{
+	struct task_sched_stats stats;
+	unsigned long nvcsw, nivcsw, cnvcsw, cnivcsw; /* context switch counts */
+
+	read_lock(&tasklist_lock);
+	get_task_sched_stats(p, &stats);
+	nvcsw = p->nvcsw;
+	nivcsw = p-> nivcsw;
+	cnvcsw = p->cnvcsw;
+	cnivcsw = p->cnivcsw;
+	read_unlock(&tasklist_lock);
+	return sprintf(buffer,
+		"%llu (%llu) %llu (%llu) %llu (%llu) %llu %lu %lu %lu %lu @ %llu\n",
+		stats.total_sleep, stats.avg_sleep_per_cycle,
+		stats.total_cpu, stats.avg_cpu_per_cycle,
+		stats.total_delay, stats.avg_delay_per_cycle,
+		stats.cycle_count,
+		nvcsw, nivcsw, cnvcsw, cnivcsw,
+		stats.timestamp);
+}
Index: Linux-2.6.X/fs/proc/base.c
diff -u Linux-2.6.X/fs/proc/base.c:1.1.1.8 Linux-2.6.X/fs/proc/base.c:1.1.1.8.22.1
--- Linux-2.6.X/fs/proc/base.c:1.1.1.8	Tue Jun  8 19:10:54 2004
+++ Linux-2.6.X/fs/proc/base.c	Thu Jun 17 14:00:57 2004
@@ -83,6 +83,7 @@
 	PROC_TID_MAPS,
 	PROC_TID_MOUNTS,
 	PROC_TID_WCHAN,
+	PROC_TID_CPU_STATS,
 #ifdef CONFIG_SECURITY
 	PROC_TID_ATTR,
 	PROC_TID_ATTR_CURRENT,
@@ -145,6 +146,7 @@
 #ifdef CONFIG_KALLSYMS
 	E(PROC_TID_WCHAN,      "wchan",   S_IFREG|S_IRUGO),
 #endif
+	E(PROC_TID_CPU_STATS,  "cpustats",   S_IFREG|S_IRUGO),
 	{0,0,NULL,0}
 };
 
@@ -181,6 +183,7 @@
 int proc_pid_status(struct task_struct*,char*);
 int proc_pid_statm(struct task_struct*,char*);
 int proc_pid_cpu(struct task_struct*,char*);
+extern int task_cpu_sched_stats(struct task_struct *p, char *buffer);
 
 static int proc_fd_link(struct inode *inode, struct dentry **dentry, struct vfsmount **mnt)
 {
@@ -1375,6 +1378,10 @@
 			ei->op.proc_read = proc_pid_wchan;
 			break;
 #endif
+		case PROC_TID_CPU_STATS:
+			inode->i_fop = &proc_info_file_operations;
+			ei->op.proc_read = task_cpu_sched_stats;
+			break;
 		default:
 			printk("procfs: impossible type (%d)",p->type);
 			iput(inode);
Index: Linux-2.6.X/fs/proc/proc_misc.c
diff -u Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7 Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7.40.1
--- Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7	Mon May 24 11:55:32 2004
+++ Linux-2.6.X/fs/proc/proc_misc.c	Thu Jun 17 14:00:57 2004
@@ -44,6 +44,7 @@
 #include <linux/jiffies.h>
 #include <linux/sysrq.h>
 #include <linux/vmalloc.h>
+#include <linux/sched.h>
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
@@ -274,6 +275,37 @@
 	.release	= seq_release,
 };
 
+static int cpustats_read_proc(char *page, char **start, off_t off,
+				 int count, int *eof, void *data)
+{
+	int i;
+	int len = 0;
+	struct cpu_sched_stats total = {0, };
+
+	for_each_online_cpu(i) {
+		struct cpu_sched_stats stats;
+
+		get_cpu_sched_stats(i, &stats);
+		len += sprintf(page + len, "cpu%02d %llu %llu %llu %llu @ %llu\n", i,
+		stats.total_idle,
+		stats.total_busy,
+		stats.total_delay,
+		stats.nr_switches,
+		stats.timestamp);
+		total.total_idle += stats.total_idle;
+		total.total_busy += stats.total_busy;
+		total.total_delay += stats.total_delay;
+		total.nr_switches += stats.nr_switches;
+	}
+	len += sprintf(page + len, "total %llu %llu %llu %llu\n",
+		total.total_idle,
+		total.total_busy,
+		total.total_delay,
+		total.nr_switches);
+
+	return proc_calc_metrics(page, start, off, count, eof, len);
+}
+
 extern struct seq_operations vmstat_op;
 static int vmstat_open(struct inode *inode, struct file *file)
 {
@@ -676,6 +708,7 @@
 #endif
 		{"locks",	locks_read_proc},
 		{"execdomains",	execdomains_read_proc},
+		{"cpustats",	cpustats_read_proc},
 		{NULL,}
 	};
 	for (p = simple_ones; p->name; p++)
Index: Linux-2.6.X/include/linux/init_task.h
diff -u Linux-2.6.X/include/linux/init_task.h:1.1.1.4 Linux-2.6.X/include/linux/init_task.h:1.1.1.4.22.1.2.1
--- Linux-2.6.X/include/linux/init_task.h:1.1.1.4	Thu May  6 18:40:15 2004
+++ Linux-2.6.X/include/linux/init_task.h	Thu Jun 17 12:00:13 2004
@@ -71,7 +71,6 @@
 	.usage		= ATOMIC_INIT(2),				\
 	.flags		= 0,						\
 	.lock_depth	= -1,						\
-	.prio		= MAX_PRIO-20,					\
 	.static_prio	= MAX_PRIO-20,					\
 	.policy		= SCHED_NORMAL,					\
 	.cpus_allowed	= CPU_MASK_ALL,					\
@@ -112,6 +111,7 @@
 	.proc_lock	= SPIN_LOCK_UNLOCKED,				\
 	.switch_lock	= SPIN_LOCK_UNLOCKED,				\
 	.journal_info	= NULL,						\
+	.sched_timestamp = ((INITIAL_JIFFIES * NSEC_PER_SEC) / HZ),	\
 }
 
 
Index: Linux-2.6.X/include/linux/sched.h
diff -u Linux-2.6.X/include/linux/sched.h:1.1.1.10 Linux-2.6.X/include/linux/sched.h:1.1.1.10.2.1.2.1.2.1.2.1.2.3
--- Linux-2.6.X/include/linux/sched.h:1.1.1.10	Wed Jun 16 18:12:45 2004
+++ Linux-2.6.X/include/linux/sched.h	Thu Jun 24 16:09:22 2004
@@ -305,7 +305,7 @@
 
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
 
-#define rt_task(p)		((p)->prio < MAX_RT_PRIO)
+#define rt_task(p)		((p)->policy != SCHED_NORMAL)
 
 /*
  * Some day this will be a full-fledged user tracking system..
@@ -325,7 +325,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;
 
@@ -390,18 +389,20 @@
 
 	int lock_depth;		/* Lock depth */
 
-	int prio, static_prio;
+	int 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 long sched_timestamp;
+	unsigned long long avg_sleep_per_cycle;
+	unsigned long long avg_delay_per_cycle;
+	unsigned long long avg_cpu_per_cycle;
+	unsigned long long interactive_bonus, throughput_bonus, sub_cycle_count;
+	unsigned long long cycle_count, total_sleep, total_cpu, total_delay;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
-	unsigned int time_slice, first_time_slice;
+	unsigned int time_slice;
 
 	struct list_head tasks;
 	struct list_head ptrace_children;
@@ -673,6 +674,45 @@
 
 extern unsigned long long sched_clock(void);
 
+/*
+ * Scheduling statistics for a task/thread
+ */
+struct task_sched_stats {
+	unsigned long long timestamp;
+	unsigned long long avg_sleep_per_cycle;
+	unsigned long long avg_delay_per_cycle;
+	unsigned long long avg_cpu_per_cycle;
+	unsigned long long cycle_count;
+	unsigned long long total_sleep;
+	unsigned long long total_cpu;
+	unsigned long long total_delay;
+};
+
+/*
+ * Get "up to date" scheduling statistics for the given task
+ * This function should be used if reliable scheduling statistitcs are required
+ * outside the scheduler itself as the relevant fields in the task structure
+ * are not "up to date" NB the possible difference between those in the task
+ * structure and the correct values could be quite large for sleeping tasks.
+ */
+extern void get_task_sched_stats(const struct task_struct *tsk, struct task_sched_stats *stats);
+
+/*
+ * Scheduling statistics for a CPU
+ */
+struct cpu_sched_stats {
+	unsigned long long timestamp;
+	unsigned long long total_idle;
+	unsigned long long total_busy;
+	unsigned long long total_delay;
+	unsigned long long nr_switches;
+};
+
+/*
+ * Get scheduling statistics for the nominated CPU
+ */
+extern void get_cpu_sched_stats(unsigned int cpu, struct cpu_sched_stats *stats);
+
 #ifdef CONFIG_SMP
 extern void sched_balance_exec(void);
 #else
Index: Linux-2.6.X/include/linux/sysctl.h
diff -u Linux-2.6.X/include/linux/sysctl.h:1.1.1.10 Linux-2.6.X/include/linux/sysctl.h:1.1.1.10.36.1
--- Linux-2.6.X/include/linux/sysctl.h:1.1.1.10	Fri Jun  4 14:29:46 2004
+++ Linux-2.6.X/include/linux/sysctl.h	Thu Jun 17 14:47:42 2004
@@ -133,6 +133,7 @@
 	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_CPU_SCHED=66,	/* CPU scheduler stuff */
 };
 
 
Index: Linux-2.6.X/init/main.c
diff -u Linux-2.6.X/init/main.c:1.1.1.11 Linux-2.6.X/init/main.c:1.1.1.11.20.1
--- Linux-2.6.X/init/main.c:1.1.1.11	Tue Jun  8 19:12:17 2004
+++ Linux-2.6.X/init/main.c	Thu Jun 17 11:27:56 2004
@@ -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.X/kernel/sched.c
diff -u Linux-2.6.X/kernel/sched.c:1.1.1.11 Linux-2.6.X/kernel/sched.c:1.1.1.11.2.1.2.1.2.1.2.1.2.9
--- Linux-2.6.X/kernel/sched.c:1.1.1.11	Wed Jun 16 18:11:46 2004
+++ Linux-2.6.X/kernel/sched.c	Sun Jun 27 01:14:40 2004
@@ -16,6 +16,9 @@
  *		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-03	Single priority array, simplified interactive bonus
+ *		mechanism and throughput bonus mechanism by Peter Williams
+ *		(Courtesy of Aurema Pty Ltd, www.aurema.com)
  */
 
 #include <linux/mm.h>
@@ -43,12 +46,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,117 +63,147 @@
 #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)))
+
+int compute = 0;
 
 /*
- * Some helpers for converting nanosecond timing to jiffy resolution
+ * These are the 'tuning knobs' of the scheduler:
+ * Making MAX_TOTAL_BONUS bigger than 19 causes mysterious crashes during boot
+ * this causes the number of longs in the bitmap to increase from 5 to 6
+ * and that's a limit on bit map size P.W.
  */
-#define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 / HZ))
-#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ))
+#define MAX_TOTAL_BONUS 19
+#define MAX_MAX_IA_BONUS 10
+#define MAX_MAX_TPT_BONUS (MAX_TOTAL_BONUS - MAX_MAX_IA_BONUS)
+#define DEFAULT_MAX_IA_BONUS MAX_MAX_IA_BONUS
+#define DEFAULT_MAX_TPT_BONUS ((DEFAULT_MAX_IA_BONUS) / 2)
+static unsigned int max_ia_bonus = DEFAULT_MAX_IA_BONUS;
+static unsigned int initial_ia_bonus = 1;
+static unsigned int max_tpt_bonus = DEFAULT_MAX_TPT_BONUS;
 
 /*
- * 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)
+ * Define some mini Kalman filter for estimating various averages, etc.
+ * To make it more efficient the denominator of the fixed point rational
+ * numbers used to store the averages and the response half life will
+ * be chosen so that the fixed point rational number reperesentation
+ * of (1 - alpha) * i (where i is an integer) will be i.
+ * Some of this is defined in linux/sched.h
+ */
 
-#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
+/*
+ * Fixed denominator rational numbers for use by the CPU scheduler
+ */
+#define SCHED_AVG_OFFSET 8
+/*
+ * Get the rounded integer value of a scheduling statistic average field
+ * i.e. those fields whose names begin with avg_
+ */
+#define SCHED_AVG_RND(x) \
+	(((x) + (1 << (SCHED_AVG_OFFSET - 1))) >> (SCHED_AVG_OFFSET))
+#define SCHED_AVG_ALPHA ((1 << SCHED_AVG_OFFSET) - 1)
+#define SCHED_AVG_MUL(a, b) (((a) * (b)) >> SCHED_AVG_OFFSET)
+#define SCHED_AVG_REAL(a) ((a) << SCHED_AVG_OFFSET)
+#define SCHED_IA_BONUS_OFFSET 8
+#define SCHED_IA_BONUS_ALPHA ((1 << SCHED_IA_BONUS_OFFSET) - 1)
+#define SCHED_IA_BONUS_MUL(a, b) (((a) * (b)) >> SCHED_IA_BONUS_OFFSET)
+/*
+ * Get the rounded integer value of the interactive bonus
+ */
+#define SCHED_IA_BONUS_RND(x) \
+	(((x) + (1 << (SCHED_IA_BONUS_OFFSET - 1))) >> (SCHED_IA_BONUS_OFFSET))
 
-#define SCALE(v1,v1_max,v2_max) \
-	(v1) * (v2_max) / (v1_max)
+static inline void apply_sched_avg_decay(unsigned long long *valp)
+{
+	*valp = SCHED_AVG_MUL(*valp, SCHED_AVG_ALPHA);
+}
 
-#define DELTA(p) \
-	(SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA)
+static inline void update_sched_ia_bonus(struct task_struct *p, unsigned long long incr)
+{
+	p->interactive_bonus = SCHED_AVG_MUL(p->interactive_bonus, SCHED_AVG_ALPHA);
+	p->interactive_bonus += incr;
+}
 
-#define TASK_INTERACTIVE(p) \
-	((p)->prio <= (p)->static_prio - DELTA(p))
+#if BITS_PER_LONG < 64
+/*
+ * Assume that there's no 64 bit divide available
+ */
+static inline unsigned long long sched_div_64(unsigned long long a, unsigned long long b)
+{
+	if (a < b)
+		return 0;
+	/*
+	 * Scale down until b less than 32 bits so that we can do a divide
+	 */
+	while (b > ULONG_MAX) { a >>= 1; b >>= 1; }
 
-#define INTERACTIVE_SLEEP(p) \
-	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
-		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
+	do_div(a, (unsigned long)b);
+
+	return a;
+}
+#else
+#define sched_div_64(a, b) ((a) / (b))
+#endif
 
-#define HIGH_CREDIT(p) \
-	((p)->interactive_credit > CREDIT_LIMIT)
+#define PROPORTION_OFFSET 32
+#define PROPORTION_ONE ((unsigned long long)1 << PROPORTION_OFFSET)
+#define PROPORTION_OVERFLOW (((unsigned long long)1 << (64 - PROPORTION_OFFSET)) - 1)
+#define PROP_FM_PPT(a) (((unsigned long long)(a) * PROPORTION_ONE) / 1000)
+/*
+ * Convert a / b to a proportion in the range 0 to PROPORTION_ONE
+ * Requires a <= b or may get a divide by zero exception
+ */
+static inline unsigned long long calc_proportion(unsigned long long a, unsigned long long b)
+{
+	if (unlikely(a == b))
+		return PROPORTION_ONE;
 
-#define LOW_CREDIT(p) \
-	((p)->interactive_credit < -CREDIT_LIMIT)
+	while (a > PROPORTION_OVERFLOW) { a >>= 1; b >>= 1; }
 
-#define TASK_PREEMPTS_CURR(p, rq) \
-	((p)->prio < (rq)->curr->prio)
+	return sched_div_64(a << PROPORTION_OFFSET, b);
+}
 
 /*
- * 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.
+ * Map the given proportion to an unsigned long in the specified range
+ * Requires range < PROPORTION_ONE to avoid overflow
+ */
+static inline unsigned long map_proportion_rnd(unsigned long long prop, unsigned long range)
+{
+	return ((prop >> 1) * (range * 2 + 1)) >> PROPORTION_OFFSET;
+}
+
+/*
+ * Tasks that have a CPU usage rate greater than this threshold (in parts per
+ * thousand) are considered to be CPU bound and start to lose interactive bonus
+ * points
  */
+#define DEFAULT_CPU_HOG_THRESHOLD 900
+static unsigned int cpu_hog_threshold_ppt = DEFAULT_CPU_HOG_THRESHOLD;
+static unsigned long long cpu_hog_threshold = PROP_FM_PPT(DEFAULT_CPU_HOG_THRESHOLD);
 
-#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
-		((MAX_TIMESLICE - MIN_TIMESLICE) * \
-			(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))
+/*
+ * Tasks that would sleep for more than 900 parts per thousand of the time if
+ * they had the CPU to themselves are considered to be interactive provided
+ * that their average sleep duration per scheduling cycle isn't too long
+ */
+#define DEFAULT_IA_THRESHOLD 900
+static unsigned int ia_threshold_ppt = DEFAULT_IA_THRESHOLD;
+static unsigned long long ia_threshold = PROP_FM_PPT(DEFAULT_IA_THRESHOLD);
+#define LOWER_MAX_IA_SLEEP SCHED_AVG_REAL(15 * 60LL * NSEC_PER_SEC)
+#define UPPER_MAX_IA_SLEEP SCHED_AVG_REAL(2 * 60 * 60LL * NSEC_PER_SEC)
+
+/*
+ * What "base time slice" for nice 0 and  "average time slice" evaluated to
+ */
+#define MSECS_TO_JIFFIES(x) (((x) * (HZ * 2 + 1)) / 2000)
+#define MSECS_TO_JIFFIES_MIN_1(x) (MSECS_TO_JIFFIES(x) ? MSECS_TO_JIFFIES(x) : 1)
+#define DEFAULT_TIME_SLICE_MSECS 100
+#define MAX_TIME_SLICE_MSECS 1000
+	
+static unsigned int time_slice_ticks = MSECS_TO_JIFFIES_MIN_1(DEFAULT_TIME_SLICE_MSECS);
 
-static unsigned int task_timeslice(task_t *p)
+static inline unsigned int task_timeslice(const task_t *p)
 {
-	return BASE_TIMESLICE(p);
+	return time_slice_ticks;
 }
 
 #define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time)
@@ -184,15 +211,30 @@
 /*
  * These are the runqueue data structures:
  */
+#define IDLE_PRIO (MAX_PRIO + MAX_TOTAL_BONUS)
+#define NUM_PRIO_SLOTS (IDLE_PRIO + 1)
 
-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
+/*
+ * Is the run queue idle?
+ */
+#define RUNQUEUE_IDLE(rq) ((rq)->curr == (rq)->idle)
+
+/*
+ * Control values for niceness
+ */
+#define PROSPECTIVE_BASE_PROM_INTERVAL_MSECS ((DEFAULT_TIME_SLICE_MSECS * 110) / 100)
+#if (PROSPECTIVE_BASE_PROM_INTERVAL_MSECS > 0)
+#define BASE_PROM_INTERVAL_MSECS PROSPECTIVE_BASE_PROM_INTERVAL_MSECS
+#else
+#define BASE_PROM_INTERVAL_MSECS DEFAULT_TIME_SLICE_MSECS
+#endif
+static unsigned int base_prom_interval_ticks = MSECS_TO_JIFFIES_MIN_1(BASE_PROM_INTERVAL_MSECS);
 
 typedef struct runqueue runqueue_t;
 
-struct prio_array {
-	unsigned int nr_active;
-	unsigned long bitmap[BITMAP_SIZE];
-	struct list_head queue[MAX_PRIO];
+struct prio_slot {
+	unsigned int prio;
+	struct list_head queue;
 };
 
 /*
@@ -214,12 +256,16 @@
 	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 long long total_delay;
+	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;
+	DECLARE_BITMAP(bitmap, NUM_PRIO_SLOTS);
+	struct prio_slot queues[NUM_PRIO_SLOTS];
+	struct prio_slot *current_prio_slot;
+	unsigned long next_prom_due;
 	atomic_t nr_iowait;
 
 #ifdef CONFIG_SMP
@@ -253,6 +299,13 @@
 # define task_running(rq, p)		((rq)->curr == (p))
 #endif
 
+static inline unsigned long get_prom_interval(const struct runqueue *rq)
+{
+	if (rq->nr_running < 2)
+		return base_prom_interval_ticks;
+	return (rq->nr_running - 1) * base_prom_interval_ticks;
+}
+
 /*
  * 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
@@ -297,159 +350,201 @@
 	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 inline int preemption_warranted(unsigned int prio,
+	const 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 (prio >= rq->current_prio_slot->prio)
+		return 0;
+	if (!compute || rq->cache_ticks >= cache_decay_ticks ||
+		rt_task(p) || !p->mm || rq->curr == rq->idle)
+			return 1;
+	rq->preempted = 1;
+		return 0;
 }
 
-static void enqueue_task(struct task_struct *p, prio_array_t *array)
+static inline int task_queued(const 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)
+{
+	/*
+	 * If p is the last task in this priority slot then slotp will be
+	 * a pointer to the head of the list in the sunqueue structure
+	 */
+	struct list_head *slotp = p->run_list.next;
+
+	/*
+	 * Initialize after removal from the list so that list_empty() works
+	 * as a means for testing whether the task is runnable
+	 */
+	list_del_init(&p->run_list);
+	if (list_empty(slotp))
+		__clear_bit(list_entry(slotp, struct prio_slot, queue)->prio, task_rq(p)->bitmap);
+}
+
+static void enqueue_task(struct task_struct *p, runqueue_t *rq, int prio)
 {
-	list_add(&p->run_list, array->queue + p->prio);
-	__set_bit(p->prio, array->bitmap);
-	array->nr_active++;
-	p->array = array;
+	list_add_tail(&p->run_list, &rq->queues[prio].queue);
+	__set_bit(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 prio)
 {
-	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->queues[prio].queue);
+	__set_bit(prio, rq->bitmap);
 }
 
 /*
  * __activate_task - move a task to the runqueue.
  */
-static inline void __activate_task(task_t *p, runqueue_t *rq)
+static inline void __activate_task(task_t *p, runqueue_t *rq, int prio)
 {
-	enqueue_task(p, rq->active);
+	p->time_slice = task_timeslice(p);
+	enqueue_task(p, rq, prio);
 	rq->nr_running++;
 }
 
 /*
- * __activate_idle_task - move idle task to the _front_ of runqueue.
+ * Update various statistics for the end of a
+ * ((on_run_queue :-> on_cpu)* :-> sleep) cycle.
+ * We can't just do this in activate_task() as every invocation of that
+ * function is not the genuine end of a cycle.
  */
-static inline void __activate_idle_task(task_t *p, runqueue_t *rq)
+static void update_stats_for_cycle(task_t *p, const runqueue_t *rq)
 {
-	enqueue_task_head(p, rq->active);
-	rq->nr_running++;
+	unsigned long long delta;
+
+	apply_sched_avg_decay(&p->avg_delay_per_cycle);
+	apply_sched_avg_decay(&p->avg_cpu_per_cycle);
+	delta = (rq->timestamp_last_tick - p->sched_timestamp);
+	p->avg_sleep_per_cycle += delta;
+	p->total_sleep += delta;
+	/*
+	 * Do this second so that averages for all measures are for
+	 * the current cycle
+	 */
+	apply_sched_avg_decay(&p->avg_sleep_per_cycle);
+	p->sched_timestamp = rq->timestamp_last_tick;
+	p->sub_cycle_count = 0;
+	p->cycle_count++;
 }
 
-static void recalc_task_prio(task_t *p, unsigned long long now)
+static void reassess_cpu_boundness(task_t *p)
 {
-	unsigned long long __sleep_time = now - p->timestamp;
-	unsigned long sleep_time;
+	unsigned long long bonus;
+	unsigned long long off_cpu_avg;
 
-	if (__sleep_time > NS_MAX_SLEEP_AVG)
-		sleep_time = NS_MAX_SLEEP_AVG;
-	else
-		sleep_time = (unsigned long)__sleep_time;
+	/*
+	 * No point going any further if there's no bonus to lose
+	 */
+	if (p->interactive_bonus == 0)
+		return;
+	/*
+	 * If the maximum bonus is zero and this task has a bonus reduce it to
+	 * zero
+	 */
+	if (unlikely(max_ia_bonus == 0)) {
+		p->interactive_bonus = 0;
+		return;
+	}
+	/* No cpu use means not cpu bound and kernel threads keep their bonus
+	 * NB this also prevents divide by zero later if cpu is also zero
+	 */
+	if ((p->avg_cpu_per_cycle == 0) || (p->mm == NULL))
+		return;
+	off_cpu_avg = p->avg_sleep_per_cycle + p->avg_delay_per_cycle;
+	bonus = calc_proportion(p->avg_cpu_per_cycle,
+		p->avg_cpu_per_cycle + off_cpu_avg);
+	if (bonus > cpu_hog_threshold)
+		update_sched_ia_bonus(p, 0);
+}
+
+static void reassess_interactiveness(task_t *p)
+{
+	unsigned long long bonus;
 
-	if (likely(sleep_time > 0)) {
+	/*
+	 * If the maximum bonus is zero there's no point going any further
+	 */
+	if (unlikely(max_ia_bonus == 0)) {
+		p->interactive_bonus = 0;
+		return;
+	}
+	/*
+	 * Kernel tasks get the maximum bonus
+	 */
+	if (p->mm == NULL) {
+		p->interactive_bonus = max_ia_bonus;
+		return;
+	}
+	/*
+	 * No sleep means not interactive (in most cases), but
+	 * NB this also prevents divide by zero later if cpu is also zero
+	 */
+	if (p->avg_sleep_per_cycle == 0) {
+		if (p->avg_cpu_per_cycle == 0)
+			update_sched_ia_bonus(p, max_ia_bonus);
+		return;
+	} else if (p->avg_sleep_per_cycle > LOWER_MAX_IA_SLEEP) {
 		/*
-		 * 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;
+		 * Really long sleeps mean it's probably not interactive
+		 */
+		if (p->avg_sleep_per_cycle > UPPER_MAX_IA_SLEEP)
+			update_sched_ia_bonus(p, 0);
+		return;
+	}
+	bonus = calc_proportion(p->avg_sleep_per_cycle,
+		p->avg_sleep_per_cycle + p->avg_cpu_per_cycle);
+	if (bonus > ia_threshold)
+		update_sched_ia_bonus(p, bonus);
+	else if (p->sub_cycle_count == 0)
+		reassess_cpu_boundness(p);
+}
 
-			/*
-			 * 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 recalc_throughput_bonus(task_t *p, unsigned long long load)
+{
+	/*
+	 * If the maximum bonus is zero there's no point going any further
+	 * No delay means no bonus, but
+	 * NB this test also avoids a possible divide by zero error if
+	 * cpu is also zero
+	 */
+	if ((p->avg_delay_per_cycle == 0) || unlikely(max_tpt_bonus == 0)) {
+		p->throughput_bonus = 0;
+		return;
+	}
+	p->throughput_bonus = calc_proportion(p->avg_delay_per_cycle,
+		p->avg_delay_per_cycle + load * p->avg_cpu_per_cycle);
+}
 
-			/*
-			 * 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;
-				}
-			}
+/*
+ * effective_prio - return the priority that is based on the static
+ * priority but is modified by bonuses/penalties.
+ */
+static inline int effective_prio(const task_t *p)
+{
+	unsigned int miabl, mtpbl, base_prio, iab, tpb;
 
-			/*
-			 * 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;
+	if (rt_task(p))
+		return (MAX_USER_RT_PRIO - 1) - p->rt_priority;
 
-			if (p->sleep_avg > NS_MAX_SLEEP_AVG) {
-				p->sleep_avg = NS_MAX_SLEEP_AVG;
-				if (!HIGH_CREDIT(p))
-					p->interactive_credit++;
-			}
-		}
-	}
+	miabl = max_ia_bonus;
+	mtpbl = max_tpt_bonus;
+	base_prio = p->static_prio + (miabl + mtpbl);
+	iab = map_proportion_rnd(SCHED_IA_BONUS_RND(p->interactive_bonus), miabl);
+	tpb = map_proportion_rnd(p->throughput_bonus, mtpbl);
 
-	p->prio = effective_prio(p);
+	return base_prio - (iab + tpb);
 }
 
 /*
@@ -457,12 +552,13 @@
  *
  * Update all the scheduling statistics stuff. (sleep average
  * calculation, priority modifiers, etc.)
+ * return prio to allow preemption testing
  */
-static void activate_task(task_t *p, runqueue_t *rq, int local)
+static int activate_task(task_t *p, runqueue_t *rq, int local)
 {
-	unsigned long long now;
+	int prio = effective_prio(p);
+	unsigned long long now = sched_clock();
 
-	now = sched_clock();
 #ifdef CONFIG_SMP
 	if (!local) {
 		/* Compensate for drifting sched_clock */
@@ -471,34 +567,10 @@
 			+ rq->timestamp_last_tick;
 	}
 #endif
-
-	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->timestamp = now;
+	__activate_task(p, rq, prio);
 
-	__activate_task(p, rq);
+	return prio;
 }
 
 /*
@@ -509,8 +581,7 @@
 	rq->nr_running--;
 	if (p->state == TASK_UNINTERRUPTIBLE)
 		rq->nr_uninterruptible++;
-	dequeue_task(p, p->array);
-	p->array = NULL;
+	dequeue_task(p);
 }
 
 /*
@@ -583,7 +654,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 +685,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);
@@ -733,6 +804,7 @@
 	unsigned long flags;
 	long old_state;
 	runqueue_t *rq;
+	int prio;
 #ifdef CONFIG_SMP
 	unsigned long load, this_load;
 	struct sched_domain *sd;
@@ -744,7 +816,7 @@
 	if (!(old_state & state))
 		goto out;
 
-	if (p->array)
+	if (task_queued(p))
 		goto out_running;
 
 	cpu = task_cpu(p);
@@ -811,7 +883,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,16 +892,17 @@
 
 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;
-	}
 
 	/*
+	 * This is the end of one scheduling cycle and the start
+	 * of the next
+	 */
+	update_stats_for_cycle(p, rq);
+	recalc_throughput_bonus(p, rq->nr_running + 1);
+	reassess_interactiveness(p);
+	/*
 	 * Sync wakeups (i.e. those types of wakeups where the waker
 	 * has indicated that it will leave the CPU in short order)
 	 * don't trigger a preemption, if the woken up task will run on
@@ -837,9 +910,9 @@
 	 * the waker guarantees that the freshly woken up task is going
 	 * to be considered on this CPU.)
 	 */
-	activate_task(p, rq, cpu == this_cpu);
+	prio = activate_task(p, rq, cpu == this_cpu);
 	if (!sync || cpu != this_cpu) {
-		if (TASK_PREEMPTS_CURR(p, rq))
+		if (preemption_warranted(prio, p, rq))
 			resched_task(rq->curr);
 	}
 	success = 1;
@@ -866,6 +939,32 @@
 }
 
 /*
+ * Initialize the scheduling statistics counters
+ */
+static inline void initialize_stats(task_t *p)
+{
+	p->avg_sleep_per_cycle = 0;
+	p->avg_delay_per_cycle = 0;
+	p->avg_cpu_per_cycle = 0;
+	p->total_sleep = 0;
+	p->total_delay = 0;
+	p->total_cpu = 0;
+	p->cycle_count = 0;
+	p->sched_timestamp = 0 /* set this to current time later */;
+}
+
+/*
+ * Initialize the scheduling bonuses
+ */
+static inline void initialize_bonuses(task_t *p)
+{
+	p->interactive_bonus = (max_ia_bonus >= initial_ia_bonus) ?
+				initial_ia_bonus : max_ia_bonus;
+	p->throughput_bonus =  0;
+	p->sub_cycle_count = 0;
+}
+
+/*
  * Perform scheduler related setup for a newly forked process p.
  * p is forked by current.
  */
@@ -879,7 +978,6 @@
 	 */
 	p->state = TASK_RUNNING;
 	INIT_LIST_HEAD(&p->run_list);
-	p->array = NULL;
 	spin_lock_init(&p->switch_lock);
 #ifdef CONFIG_PREEMPT
 	/*
@@ -891,32 +989,14 @@
 	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.
+	 * Give the child a new timeslice
 	 */
-	local_irq_disable();
-	p->time_slice = (current->time_slice + 1) >> 1;
+	p->time_slice = task_timeslice(p);
 	/*
-	 * The remainder of the first timeslice might be recovered by
-	 * the parent if the child exits early enough.
+	 * Initialize the scheduling statistics and bonus counters
 	 */
-	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();
+	initialize_stats(p);
+	initialize_bonuses(p);
 }
 
 /*
@@ -932,65 +1012,47 @@
 
 	BUG_ON(p->state != TASK_RUNNING);
 
+	set_task_cpu(p, smp_processor_id());
+
 	/*
-	 * We decrease the sleep average of forking parents
-	 * and children as well, to keep max-interactive tasks
-	 * from forking tasks that are max-interactive.
+	 * Scheduling statistics compilation starts now
 	 */
-	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->sched_timestamp = rq->timestamp_last_tick;
 
-	p->prio = effective_prio(p);
-	set_task_cpu(p, smp_processor_id());
-
-	if (unlikely(!current->array))
-		__activate_task(p, rq);
+	/*
+	 * Now that the idle task is back on the run queue we need extra care
+	 * to make sure that its one and only fork() doesn't end up in the idle
+	 * priority slot.  Just testing for empty run list is no longer adequate.
+	 */
+	if (unlikely(!task_queued(current) || RUNQUEUE_IDLE(rq)))
+		__activate_task(p, rq, effective_prio(p));
 	else {
-		p->prio = current->prio;
+		/*
+		 * Put the child on the same list(s) as (but ahead of) the parent
+		 */
 		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.)
+/**
+ * (Optionally) log scheduler statistics at exit.
  */
+static int log_at_exit = 0;
 void fastcall sched_exit(task_t * p)
 {
-	unsigned long flags;
-	runqueue_t *rq;
+	struct task_sched_stats stats;
 
-	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);
-	task_rq_unlock(rq, &flags);
+	if (!log_at_exit)
+		return;
+
+	get_task_sched_stats(p, &stats);
+	printk("SCHED_EXIT[%d] (%s) %llu %llu %llu %llu %lu %lu %lu %lu\n",
+		p->pid, p->comm,
+		stats.total_sleep, stats.total_cpu, stats.total_delay,
+		stats.cycle_count,
+		p->nvcsw, p->nivcsw, p->cnvcsw, p->cnivcsw);
 }
 
 /**
@@ -1167,7 +1229,7 @@
 /*
  * find_idlest_cpu - find the least busy runqueue.
  */
-static int find_idlest_cpu(struct task_struct *p, int this_cpu,
+static int find_idlest_cpu(const struct task_struct *p, int this_cpu,
 			   struct sched_domain *sd)
 {
 	unsigned long load, min_load, this_load;
@@ -1253,38 +1315,34 @@
 		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);
 
+	/*
+	 * Scheduling statistics compilation starts now
+	 */
+	p->sched_timestamp = rq->timestamp_last_tick;
+
 	if (cpu == this_cpu) {
-		if (unlikely(!current->array))
-			__activate_task(p, rq);
+		/*
+		 * Now that the idle task is back on the run queue we need
+		 * extra care to make sure that its one and only fork() doesn't
+		 * end up in the idle priority slot.  Just testing for empty
+		 * run list is no longer adequate.
+		 */
+		if (unlikely(!task_queued(current) || RUNQUEUE_IDLE(rq)))
+			__activate_task(p, rq, effective_prio(p));
 		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 {
+		int prio = effective_prio(p);
 		/* Not the local CPU - must adjust timestamp */
 		p->timestamp = (p->timestamp - this_rq->timestamp_last_tick)
 					+ rq->timestamp_last_tick;
-		__activate_task(p, rq);
-		if (TASK_PREEMPTS_CURR(p, rq))
+		__activate_task(p, rq, prio);
+		if (preemption_warranted(prio, p, rq))
 			resched_task(rq->curr);
 	}
 
@@ -1376,22 +1434,28 @@
  * 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, int prio)
 {
-	dequeue_task(p, src_array);
+	unsigned long long delta;
+
+	dequeue_task(p);
 	src_rq->nr_running--;
+	delta = (src_rq->timestamp_last_tick - p->sched_timestamp);
+	p->avg_delay_per_cycle += delta;
+	p->total_delay += delta;
 	set_task_cpu(p, this_cpu);
 	this_rq->nr_running++;
-	enqueue_task(p, this_array);
+	p->sched_timestamp = this_rq->timestamp_last_tick;
+	enqueue_task(p, this_rq, prio);
 	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
+	 * Note that idle threads have a prio of IDLE_PRIO, for this test
 	 * to be always true for them.
 	 */
-	if (TASK_PREEMPTS_CURR(p, this_rq))
+	if (preemption_warranted(prio, p, this_rq))
 		resched_task(this_rq->curr);
 }
 
@@ -1399,7 +1463,7 @@
  * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
  */
 static inline
-int can_migrate_task(task_t *p, runqueue_t *rq, int this_cpu,
+int can_migrate_task(const task_t *p, runqueue_t *rq, int this_cpu,
 		     struct sched_domain *sd, enum idle_type idle)
 {
 	/*
@@ -1434,7 +1498,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 +1505,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, IDLE_PRIO, idx);
+	if (idx >= IDLE_PRIO)
 		goto out;
-	}
 
-	head = array->queue + idx;
+	head = &busiest->queues[idx].queue;
 	curr = head->prev;
 skip_queue:
 	tmp = list_entry(curr, task_t, run_list);
@@ -1486,7 +1528,7 @@
 		idx++;
 		goto skip_bitmap;
 	}
-	pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu);
+	pull_task(busiest, tmp, this_rq, this_cpu, idx);
 	pulled++;
 
 	/* We only want to steal up to the prescribed number of tasks. */
@@ -1645,7 +1687,7 @@
 /*
  * find_busiest_queue - find the busiest runqueue among the cpus in group.
  */
-static runqueue_t *find_busiest_queue(struct sched_group *group)
+static runqueue_t *find_busiest_queue(const struct sched_group *group)
 {
 	cpumask_t tmp;
 	unsigned long load, max_load = 0;
@@ -1924,6 +1966,11 @@
 		}
 	}
 }
+
+static inline int needs_idle_balance(const runqueue_t *rq)
+{
+	return rq->nr_running == 0;
+}
 #else
 /*
  * on UP we do not need to balance between CPUs:
@@ -1934,6 +1981,10 @@
 static inline void idle_balance(int cpu, runqueue_t *rq)
 {
 }
+static inline int needs_idle_balance(const runqueue_t *rq)
+{
+	return 0;
+}
 #endif
 
 static inline int wake_priority_sleeper(runqueue_t *rq)
@@ -1951,27 +2002,52 @@
 	return 0;
 }
 
+/*
+ * Are promotions due?
+ */
+static inline int promotions_due(const runqueue_t *rq)
+{
+	return time_after_eq(jiffies, rq->next_prom_due);
+}
+
+/* 
+ * Assume runqueue lock is NOT already held. 
+ */
+static void do_promotions(runqueue_t *rq)
+{
+	int idx = MAX_RT_PRIO;
+
+	spin_lock(&rq->lock);
+	for (;;) {
+		int new_prio;
+		idx = find_next_bit(rq->bitmap, IDLE_PRIO, idx + 1);
+		if (idx > (IDLE_PRIO - 1))
+			break;
+
+		new_prio = idx - 1;
+		__list_splice(&rq->queues[idx].queue, rq->queues[new_prio].queue.prev);
+		INIT_LIST_HEAD(&rq->queues[idx].queue);
+		__clear_bit(idx, rq->bitmap);
+		__set_bit(new_prio, rq->bitmap);
+		/*
+		 * If promotion occurs from the slot
+		 * associated with rq->current_prio_slot then the
+		 * current task will be one of those promoted
+		 * so we should update rq->current_prio_slot
+		 * This will only be true for at most one slot.
+		 */
+		if (unlikely(idx == rq->current_prio_slot->prio))
+			rq->current_prio_slot = rq->queues + new_prio;
+	}
+	rq->next_prom_due = (jiffies + get_prom_interval(rq));
+	spin_unlock(&rq->lock);
+}
+
 DEFINE_PER_CPU(struct kernel_stat, kstat);
 
 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,11 +2091,6 @@
 		cpustat->user += user_ticks;
 	cpustat->system += sys_ticks;
 
-	/* Task might have expired already, but not scheduled off yet */
-	if (p->array != rq->active) {
-		set_tsk_need_resched(p);
-		goto out;
-	}
 	spin_lock(&rq->lock);
 	/*
 	 * The task was running during this tick - update the
@@ -2035,62 +2106,52 @@
 		 */
 		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);
+			dequeue_task(p);
+			enqueue_task(p, rq, rq->current_prio_slot->prio);
 		}
 		goto out_unlock;
 	}
+	rq->cache_ticks++;
 	if (!--p->time_slice) {
-		dequeue_task(p, rq->active);
+		unsigned long long delta;
+
+		dequeue_task(p);
 		set_tsk_need_resched(p);
-		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 {
+		delta = (rq->timestamp_last_tick - p->sched_timestamp);
+		p->avg_cpu_per_cycle += delta;
+		p->total_cpu += delta;
+		p->sched_timestamp = rq->timestamp_last_tick;
+		recalc_throughput_bonus(p, rq->nr_running);
+		reassess_cpu_boundness(p);
 		/*
-		 * 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);
-		}
+		 * Arguably the interactive bonus should be updated here
+		 * as well.  But depends on whether we wish to encourage
+		 * interactive tasks to maintain a high bonus or CPU bound
+		 * tasks to lose some of there bonus?
+		 */
+		rq->current_prio_slot = rq->queues + effective_prio(p);
+		enqueue_task(p, rq, rq->current_prio_slot->prio);
+		goto out_unlock;
 	}
+	if (rq->preempted && rq->cache_ticks >= cache_decay_ticks)
+		set_tsk_need_resched(p);
 out_unlock:
 	spin_unlock(&rq->lock);
 out:
 	rebalance_tick(cpu, rq, NOT_IDLE);
+	if (unlikely(promotions_due(rq))) {
+		/*
+		 * If there's less than 2 SCHED_OTHER tasks defer the next promotion
+		 */
+		if ((rt_task(p) ? rq->nr_running - 1 : rq->nr_running) < 2)
+			rq->next_prom_due = (jiffies + get_prom_interval(rq));
+		else
+			do_promotions(rq);
+	}
 }
 
 #ifdef CONFIG_SCHED_SMT
@@ -2167,6 +2228,11 @@
 	}
 	return ret;
 }
+
+static inline int dependent_idle(const runqueue_t *rq, const task_t *p)
+{
+	return p == rq->idle;
+}
 #else
 static inline void wake_sleeping_dependent(int cpu, runqueue_t *rq)
 {
@@ -2176,6 +2242,11 @@
 {
 	return 0;
 }
+
+static inline int dependent_idle(const runqueue_t *rq, const task_t *p)
+{
+	return 0;
+}
 #endif
 
 /*
@@ -2186,11 +2257,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;
+	int cpu;
+	unsigned long long delta;
 
 	/*
 	 * Test if we are atomic.  Since do_exit() needs to call into
@@ -2210,19 +2278,6 @@
 	rq = this_rq();
 
 	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);
 
 	spin_lock_irq(&rq->lock);
 
@@ -2241,64 +2296,44 @@
 	}
 
 	cpu = smp_processor_id();
-	if (unlikely(!rq->nr_running)) {
+	if (unlikely(needs_idle_balance(rq)))
 		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;
+	rq->current_prio_slot = rq->queues + sched_find_first_bit(rq->bitmap);
+	next = list_entry(rq->current_prio_slot->queue.next, task_t, run_list);
+	if (dependent_idle(rq, next)) {
+		wake_sleeping_dependent(cpu, rq);
+		goto switch_tasks;
 	}
 
-	idx = sched_find_first_bit(array->bitmap);
-	queue = array->queue + idx;
-	next = list_entry(queue->next, task_t, run_list);
-
 	if (dependent_sleeper(cpu, rq, next)) {
+		rq->current_prio_slot = rq->queues + IDLE_PRIO;
 		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;
+	/*
+	 * Update estimate of average CPU time used per cycle
+	 */
+	delta = (rq->timestamp_last_tick - prev->sched_timestamp);
+	prev->avg_cpu_per_cycle += delta;
+	prev->total_cpu += delta;
+	prev->timestamp = prev->sched_timestamp = rq->timestamp_last_tick;
 
 	if (likely(prev != next)) {
-		next->timestamp = now;
+		rq->preempted = 0;
+		rq->cache_ticks = 0;
+		/*
+		 * Update estimate of average delay on run queue per cycle
+		 */
+		delta = (rq->timestamp_last_tick - next->sched_timestamp);
+		next->avg_delay_per_cycle += delta;
+		next->total_delay += delta;
+		next->timestamp = next->sched_timestamp = rq->timestamp_last_tick;
+		rq->total_delay += delta;
 		rq->nr_switches++;
 		rq->curr = next;
 		++*switch_count;
@@ -2560,9 +2595,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, delta;
 
 	if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
 		return;
@@ -2577,30 +2611,27 @@
 	 * it wont have any effect on scheduling until the task is
 	 * not SCHED_NORMAL:
 	 */
-	if (rt_task(p)) {
-		p->static_prio = NICE_TO_PRIO(nice);
-		goto out_unlock;
-	}
-	array = p->array;
-	if (array)
-		dequeue_task(p, array);
-
-	old_prio = p->prio;
-	new_prio = NICE_TO_PRIO(nice);
-	delta = new_prio - old_prio;
+	if ((queued = (!rt_task(p) && task_queued(p))))
+		dequeue_task(p);
+
+	delta = PRIO_TO_NICE(p->static_prio) - nice;
 	p->static_prio = NICE_TO_PRIO(nice);
-	p->prio += delta;
 
-	if (array) {
-		enqueue_task(p, array);
+	if (queued) {
+		int new_prio = effective_prio(p);
+
+		enqueue_task(p, rq, new_prio);
+		if (task_running(rq, p))
+			rq->current_prio_slot = rq->queues + new_prio;
+
 		/*
-		 * If the task increased its priority or is running and
-		 * lowered its priority, then reschedule its CPU:
+		 * If the task increased its setting or is running and lowered
+		 * its setting, then reschedule its CPU:
 		 */
-		if (delta < 0 || (delta > 0 && task_running(rq, p)))
+		if ((delta > 0) || ((delta < 0) && task_running(rq, p)))
 			resched_task(rq->curr);
 	}
-out_unlock:
+
 	task_rq_unlock(rq, &flags);
 }
 
@@ -2660,7 +2691,7 @@
  */
 int task_prio(task_t *p)
 {
-	return p->prio - MAX_RT_PRIO;
+	return effective_prio(p) - MAX_RT_PRIO;
 }
 
 /**
@@ -2697,13 +2728,9 @@
 /* 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)
-		p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;
-	else
-		p->prio = p->static_prio;
 }
 
 /*
@@ -2713,8 +2740,7 @@
 {
 	struct sched_param lp;
 	int retval = -EINVAL;
-	int oldprio;
-	prio_array_t *array;
+	int queued;
 	unsigned long flags;
 	runqueue_t *rq;
 	task_t *p;
@@ -2774,24 +2800,23 @@
 	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) {
-		__activate_task(p, task_rq(p));
+	if (queued) {
+		int prio = effective_prio(p);
+
+		__activate_task(p, task_rq(p), prio);
 		/*
 		 * Reschedule if we are currently running on this runqueue and
 		 * our priority decreased, or if we are not currently running on
 		 * this runqueue and our priority is higher than the current's
 		 */
-		if (task_running(rq, p)) {
-			if (p->prio > oldprio)
-				resched_task(rq->curr);
-		} else if (TASK_PREEMPTS_CURR(p, rq))
+		if (preemption_warranted(prio, p, rq))
 			resched_task(rq->curr);
+		if (task_running(rq, p))
+			rq->current_prio_slot = rq->queues + prio;
 	}
 
 out_unlock:
@@ -2980,6 +3005,99 @@
 	return real_len;
 }
 
+void get_task_sched_stats(const struct task_struct *tsk, struct task_sched_stats *stats)
+{
+	int on_runq = 0;
+	int on_cpu = 0;
+	unsigned long long timestamp;
+	runqueue_t *rq = this_rq_lock();
+
+	stats->timestamp = rq->timestamp_last_tick;
+	stats->avg_sleep_per_cycle = tsk->avg_sleep_per_cycle;
+	stats->avg_delay_per_cycle = tsk->avg_delay_per_cycle;
+	stats->avg_cpu_per_cycle = tsk->avg_cpu_per_cycle;
+	stats->cycle_count = tsk->cycle_count;
+	stats->total_sleep = tsk->total_sleep;
+	stats->total_cpu = tsk->total_cpu;
+	stats->total_delay = tsk->total_delay;
+	timestamp = tsk->sched_timestamp;
+	if ((on_runq = task_queued(tsk)))
+		on_cpu = rq->idle == tsk;
+
+	rq_unlock(rq);
+
+	/*
+	 * Update values to the previous tick (only)
+	 */
+	if (stats->timestamp > timestamp) {
+		unsigned long long delta = stats->timestamp - timestamp;
+
+		if (on_cpu) {
+			stats->avg_cpu_per_cycle += delta;
+			stats->total_cpu += delta;
+		} else if (on_runq) {
+			stats->avg_delay_per_cycle += delta;
+			stats->total_delay += delta;
+		} else {
+			stats->avg_sleep_per_cycle += delta;
+			stats->total_sleep += delta;
+		}
+	}
+	/*
+	 * Convert internal "real number" representation of average times
+	 * to integer values in nanoseconds
+	 */
+	stats->avg_sleep_per_cycle = SCHED_AVG_RND(stats->avg_sleep_per_cycle);
+	stats->avg_cpu_per_cycle = SCHED_AVG_RND(stats->avg_cpu_per_cycle);
+	stats->avg_delay_per_cycle = SCHED_AVG_RND(stats->avg_delay_per_cycle);
+}
+
+EXPORT_SYMBOL(get_task_sched_stats);
+
+/*
+ * Get scheduling statistics for the nominated CPU
+ */
+void get_cpu_sched_stats(unsigned int cpu, struct cpu_sched_stats *stats)
+{
+	int idle;
+	unsigned long long idle_timestamp;
+	runqueue_t *rq = cpu_rq(cpu);
+
+	/*
+	 * No need to crash the whole machine if they've asked for stats for
+	 * a non existent CPU, just send back zero.
+	 */
+	if (rq == NULL) {
+		stats->timestamp = 0;
+		stats->total_idle = 0;
+		stats->total_busy = 0;
+		stats->total_delay = 0;
+		stats->nr_switches = 0;
+
+		return;
+	}
+	local_irq_disable();
+	spin_lock(&rq->lock);
+	idle = rq->curr == rq->idle;
+	stats->timestamp = rq->timestamp_last_tick;
+	idle_timestamp = rq->idle->sched_timestamp;
+	stats->total_idle = rq->idle->total_cpu;
+	stats->total_busy = rq->idle->total_delay;
+	stats->total_delay = rq->total_delay;
+	stats->nr_switches = rq->nr_switches;
+	rq_unlock(rq);
+
+	/*
+	 * Update idle/busy time to the current tick
+	 */
+	if (idle)
+		stats->total_idle += (stats->timestamp - idle_timestamp);
+	else
+		stats->total_busy += (stats->timestamp - idle_timestamp);
+}
+
+EXPORT_SYMBOL(get_cpu_sched_stats);
+
 /**
  * sys_sched_yield - yield the current processor to other threads.
  *
@@ -2990,22 +3108,22 @@
 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);
-
+	if (likely(!rt_task(current))) {
+		/* If there's other tasks on this CPU make sure that as many of
+		 * them as possible/judicious get some CPU before this task
+		 */
+		dequeue_task(current);
+		rq->current_prio_slot = rq->queues + (IDLE_PRIO - 1);
+		enqueue_task(current, rq, rq->current_prio_slot->prio);
+	} else {
+		list_del_init(&current->run_list);
+		list_add_tail(&current->run_list, &rq->current_prio_slot->queue);
+	}
 	/*
 	 * Since we are going to call schedule() anyway, there's
 	 * no need to preempt or enable interrupts:
@@ -3261,10 +3379,25 @@
 
 	idle_rq->curr = idle_rq->idle = idle;
 	deactivate_task(idle, rq);
-	idle->array = NULL;
-	idle->prio = MAX_PRIO;
+	/*
+	 * Initialize scheduling statistics counters as they may provide
+	 * valuable about the CPU e.g. avg_cpu_time_per_cycle for the idle
+	 * task will be an estimate of the average time the CPU is idle
+	 */
+	initialize_stats(idle);
+	initialize_bonuses(idle);
+	idle->sched_timestamp = rq->timestamp_last_tick;
 	idle->state = TASK_RUNNING;
 	set_task_cpu(idle, cpu);
+	/*
+	 * Putting the idle process onto a run queue simplifies the selection of
+	 * the next task to run in schedule().
+	 */
+	list_add_tail(&idle->run_list, &idle_rq->queues[IDLE_PRIO].queue);
+	/*
+	 * The idle task is the current task on idle_rq
+	 */
+	idle_rq->current_prio_slot = idle_rq->queues + IDLE_PRIO;
 	double_rq_unlock(idle_rq, rq);
 	set_tsk_need_resched(idle);
 	local_irq_restore(flags);
@@ -3371,8 +3504,8 @@
 	if (!cpu_isset(dest_cpu, p->cpus_allowed))
 		goto out;
 
-	set_task_cpu(p, dest_cpu);
-	if (p->array) {
+	if (task_queued(p)) {
+		unsigned long long delta;
 		/*
 		 * Sync timestamp with rq_dest's before activating.
 		 * The same thing could be achieved by doing this step
@@ -3382,10 +3515,25 @@
 		p->timestamp = p->timestamp - rq_src->timestamp_last_tick
 				+ rq_dest->timestamp_last_tick;
 		deactivate_task(p, rq_src);
-		activate_task(p, rq_dest, 0);
-		if (TASK_PREEMPTS_CURR(p, rq_dest))
+		/*
+		 * Do set_task_cpu() AFTER we dequeue the task, since
+		 * dequeue_task() relies on task_cpu() always being accurate.
+		 */
+		set_task_cpu(p, dest_cpu);
+		delta = (rq_dest->timestamp_last_tick - p->sched_timestamp);
+		p->avg_delay_per_cycle += delta;
+		p->total_delay += delta;
+		if (preemption_warranted(activate_task(p, rq_dest, 0), p, rq_dest))
 			resched_task(rq_dest->curr);
+	} else {
+		unsigned long long delta;
+
+		set_task_cpu(p, dest_cpu);
+		delta = (rq_dest->timestamp_last_tick - p->sched_timestamp);
+		p->avg_sleep_per_cycle += delta;
+		p->total_sleep += delta;
 	}
+	p->sched_timestamp = rq_dest->timestamp_last_tick;
 
 out:
 	double_rq_unlock(rq_src, rq_dest);
@@ -3533,9 +3681,11 @@
 	 */
 	spin_lock_irqsave(&rq->lock, flags);
 
-	__setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1);
 	/* Add idle task to _front_ of it's priority queue */
-	__activate_idle_task(p, rq);
+	dequeue_task(p);
+	__setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1);
+	enqueue_task_head(p, rq, 0);
+	rq->nr_running++;
 
 	spin_unlock_irqrestore(&rq->lock, flags);
 }
@@ -3581,11 +3731,12 @@
 		rq = cpu_rq(cpu);
 		kthread_stop(rq->migration_thread);
 		rq->migration_thread = NULL;
-		/* Idle task back to normal (off runqueue, low prio) */
+		/* Idle task back to normal in IDLE_PRIO slot */
 		rq = task_rq_lock(rq->idle, &flags);
 		deactivate_task(rq->idle, rq);
-		rq->idle->static_prio = MAX_PRIO;
+		rq->idle->static_prio = IDLE_PRIO;
 		__setscheduler(rq->idle, SCHED_NORMAL, 0);
+		enqueue_task(rq->idle, rq, IDLE_PRIO);
 		task_rq_unlock(rq, &flags);
  		BUG_ON(rq->nr_running != 0);
 
@@ -3896,7 +4047,7 @@
 void __init sched_init(void)
 {
 	runqueue_t *rq;
-	int i, j, k;
+	int i, k;
 
 #ifdef CONFIG_SMP
 	/* Set up an initial dummy domain for early boot */
@@ -3917,13 +4068,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;
@@ -3935,15 +4084,17 @@
 #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 (k = 0; k <= IDLE_PRIO; k++) {
+			rq->queues[k].prio = k;
+			INIT_LIST_HEAD(&rq->queues[k].queue);
 		}
+		bitmap_zero(rq->bitmap, NUM_PRIO_SLOTS);
+		// delimiter for bitsearch
+		__set_bit(IDLE_PRIO, rq->bitmap);
+		rq->current_prio_slot = rq->queues + (IDLE_PRIO - 20);
+		rq->timestamp_last_tick = sched_clock();
+		rq->next_prom_due = (jiffies + get_prom_interval(rq));
+		rq->total_delay = 0;
 	}
 	/*
 	 * We have to do a little magic to get the first
@@ -4029,3 +4180,175 @@
 
 EXPORT_SYMBOL(__preempt_write_lock);
 #endif /* defined(CONFIG_SMP) && defined(CONFIG_PREEMPT) */
+
+#if defined(CONFIG_SYSCTL)
+/*
+ * CPU scheduler control via /proc/sys/cpusched/xxx
+ */
+enum
+{
+	CPU_SCHED_END_OF_LIST=0,
+	CPU_SCHED_TIME_SLICE=1,
+	CPU_SCHED_BASE_PROMOTION_INTERVAL,
+	CPU_SCHED_MAX_IA_BONUS,
+	CPU_SCHED_MAX_TPT_BONUS,
+	CPU_SCHED_IA_THRESHOLD,
+	CPU_SCHED_CPU_HOG_THRESHOLD,
+	CPU_SCHED_LOG_AT_EXIT,
+	CPU_SCHED_COMPUTE,
+	CPU_SCHED_INITIAL_IA_BONUS,
+};
+
+static const unsigned int zero = 0;
+static const unsigned int one = 1;
+#define min_milli_value zero
+static const unsigned int max_milli_value = 1000;
+#define min_max_ia_bonus zero
+static const unsigned int max_max_ia_bonus = MAX_MAX_IA_BONUS;
+#define min_max_tpt_bonus zero
+static const unsigned int max_max_tpt_bonus = MAX_MAX_TPT_BONUS;
+static unsigned int time_slice_msecs = DEFAULT_TIME_SLICE_MSECS;
+#define min_time_slice_msecs one
+static const unsigned int max_time_slice_msecs = MAX_TIME_SLICE_MSECS;
+static unsigned int base_prom_interval_msecs = BASE_PROM_INTERVAL_MSECS;
+#define min_base_prom_interval_msecs one
+static const unsigned int max_base_prom_interval_msecs = INT_MAX;
+
+static int proc_time_slice_msecs(ctl_table *ctp, int write, struct file *fp,
+				void __user *buffer, size_t *lenp)
+{
+	int res = proc_dointvec_minmax(ctp, write, fp, buffer, lenp);
+
+	if ((res == 0) && write)
+		time_slice_ticks = MSECS_TO_JIFFIES_MIN_1(time_slice_msecs);
+
+	return res;
+}
+
+static int proc_base_prom_interval_msecs(ctl_table *ctp, int write, struct file *fp,
+				void __user *buffer, size_t *lenp)
+{
+	int res = proc_dointvec_minmax(ctp, write, fp, buffer, lenp);
+
+	if ((res == 0) && write)
+		base_prom_interval_ticks = MSECS_TO_JIFFIES_MIN_1(base_prom_interval_msecs);
+
+	return res;
+}
+
+static int proc_cpu_hog_threshold(ctl_table *ctp, int write, struct file *fp,
+				void __user *buffer, size_t *lenp)
+{
+	int res = proc_dointvec_minmax(ctp, write, fp, buffer, lenp);
+
+	if ((res == 0) && write)
+		cpu_hog_threshold = calc_proportion(cpu_hog_threshold_ppt, 1000);
+
+	return res;
+}
+
+static int proc_ia_threshold(ctl_table *ctp, int write, struct file *fp,
+				void __user *buffer, size_t *lenp)
+{
+	int res = proc_dointvec_minmax(ctp, write, fp, buffer, lenp);
+
+	if ((res == 0) && write)
+		ia_threshold = calc_proportion(ia_threshold_ppt, 1000);
+
+	return res;
+}
+
+ctl_table cpu_sched_table[] = {
+	{
+		.ctl_name	= CPU_SCHED_TIME_SLICE,
+		.procname	= "time_slice",
+		.data		= &time_slice_msecs,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_time_slice_msecs,
+		.extra1		= (void *)&min_time_slice_msecs,
+		.extra2		= (void *)&max_time_slice_msecs
+	},
+	{
+		.ctl_name	= CPU_SCHED_BASE_PROMOTION_INTERVAL,
+		.procname	= "base_promotion_interval",
+		.data		= &base_prom_interval_msecs,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_base_prom_interval_msecs,
+		.extra1		= (void *)&min_base_prom_interval_msecs,
+		.extra2		= (void *)&max_base_prom_interval_msecs
+	},
+	{
+		.ctl_name	= CPU_SCHED_MAX_IA_BONUS,
+		.procname	= "max_ia_bonus",
+		.data		= &max_ia_bonus,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.extra1		= (void *)&min_max_ia_bonus,
+		.extra2		= (void *)&max_max_ia_bonus
+	},
+	{
+		.ctl_name	= CPU_SCHED_INITIAL_IA_BONUS,
+		.procname	= "initial_ia_bonus",
+		.data		= &initial_ia_bonus,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.extra1		= (void *)&min_max_ia_bonus,
+		.extra2		= (void *)&max_max_ia_bonus
+	},
+	{
+		.ctl_name	= CPU_SCHED_MAX_TPT_BONUS,
+		.procname	= "max_tpt_bonus",
+		.data		= &max_tpt_bonus,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.extra1		= (void *)&min_max_tpt_bonus,
+		.extra2		= (void *)&max_max_tpt_bonus
+	},
+	{
+		.ctl_name	= CPU_SCHED_IA_THRESHOLD,
+		.procname	= "ia_threshold",
+		.data		= &ia_threshold_ppt,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_ia_threshold,
+		.extra1		= (void *)&min_milli_value,
+		.extra2		= (void *)&max_milli_value
+	},
+	{
+		.ctl_name	= CPU_SCHED_CPU_HOG_THRESHOLD,
+		.procname	= "cpu_hog_threshold",
+		.data		= &cpu_hog_threshold_ppt,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_cpu_hog_threshold,
+		.extra1		= (void *)&min_milli_value,
+		.extra2		= (void *)&max_milli_value
+	},
+	{
+		.ctl_name	= CPU_SCHED_LOG_AT_EXIT,
+		.procname	= "log_at_exit",
+		.data		= &log_at_exit,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.extra1		= (void *)&zero,
+		.extra2		= (void *)&one
+	},
+	{
+		.ctl_name	= CPU_SCHED_COMPUTE,
+		.procname	= "compute",
+		.data		= &compute,
+		.maxlen		= sizeof (unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.extra1		= (void *)&zero,
+		.extra2		= (void *)&one
+	},
+	{ .ctl_name = CPU_SCHED_END_OF_LIST }
+};
+#endif
Index: Linux-2.6.X/kernel/sysctl.c
diff -u Linux-2.6.X/kernel/sysctl.c:1.1.1.9 Linux-2.6.X/kernel/sysctl.c:1.1.1.9.10.1
--- Linux-2.6.X/kernel/sysctl.c:1.1.1.9	Wed Jun 16 18:11:47 2004
+++ Linux-2.6.X/kernel/sysctl.c	Thu Jun 17 14:47:42 2004
@@ -142,6 +142,10 @@
 #ifdef CONFIG_UNIX98_PTYS
 extern ctl_table pty_table[];
 #endif
+/*
+ * CPU scheduler control variables (lives in sched.c)
+ */
+extern ctl_table cpu_sched_table[];
 
 /* /proc declarations: */
 
@@ -636,6 +640,12 @@
 		.mode		= 0444,
 		.proc_handler	= &proc_dointvec,
 	},
+	{
+		.ctl_name	= KERN_CPU_SCHED,
+		.procname	= "cpusched",
+		.mode		= 0555,
+		.child		= cpu_sched_table,
+	},
 	{ .ctl_name = 0 }
 };