[PATCH] A try for a more fair scheduler ...

[Davide Libenzi]

This patch try to achieve a better goodness() calculation through the
introduction of the concept of 'cpu time spent onto a processor', aka
probable cache footprint of the task.
Right now if we've a couple of cpu bound tasks with the classical editor
keyboard ticking, we can see the two cpu bound tasks swapped when the
editor task kicks in.
This is wrong coz the cpu bound task has probably run for a bunch of ms
and hence has a quite big memory footprint on the cpu.
While the editor task very likely run for a very short time by keeping the
footprint of the cpu bound tasks amlost intact.
This patch addresses in a better way even the proc change penalty problem
that, right now, is constant.
It's abvious that having to choose between the cpu bound task and the
editor task, the better candidate should be the one that has less memory
footprint aka the editor task.
So we can change the constant penalty into a constant plus an estimate of
the memory footprint.
The patch tracks the number of jiffies that a task run as :

JR = Jin - Jout

where Jin is the jiffies value when the task in kicked in and Jout is the
time when it's kicked out.
In a given time the value of the footprint is :

W = JR > (J - Jout) ? JR - (J - Jout): 0

where J is the current time in jiffies.
This means that if the task is run for 10 ms, 10 ms ago, it's current
weight will be zero.
This is quite clear coz the more a process does not run the more footprint
will lose.
I'm currently testing the patch by analyzing process migration and
latencies with the latsched patch :

http://www.xmailserver.org/linux-patches/lnxsched.html

Comments ?

- Davide

diff -Nru linux-2.4.12.vanilla/include/linux/sched.h linux-2.4.12.scx/include/linux/sched.h
--- linux-2.4.12.vanilla/include/linux/sched.h	Thu Oct 11 10:40:49 2001
+++ linux-2.4.12.scx/include/linux/sched.h	Thu Oct 18 17:11:35 2001
@@ -393,12 +393,14 @@
 	int (*notifier)(void *priv);
 	void *notifier_data;
 	sigset_t *notifier_mask;
-
+
 /* Thread group tracking */
    	u32 parent_exec_id;
    	u32 self_exec_id;
 /* Protection of (de-)allocation: mm, files, fs, tty */
 	spinlock_t alloc_lock;
+/* a better place for these brothers must be found */
+	unsigned long cpu_jtime, sched_jtime;
 };

 /*
diff -Nru linux-2.4.12.vanilla/kernel/fork.c linux-2.4.12.scx/kernel/fork.c
--- linux-2.4.12.vanilla/kernel/fork.c	Mon Oct  1 12:56:42 2001
+++ linux-2.4.12.scx/kernel/fork.c	Thu Oct 18 17:12:49 2001
@@ -687,6 +687,9 @@
 	if (!current->counter)
 		current->need_resched = 1;

+	p->cpu_jtime = 0;
+	p->sched_jtime = jiffies;
+
 	/*
 	 * Ok, add it to the run-queues and make it
 	 * visible to the rest of the system.
diff -Nru linux-2.4.12.vanilla/kernel/sched.c linux-2.4.12.scx/kernel/sched.c
--- linux-2.4.12.vanilla/kernel/sched.c	Tue Oct  9 19:00:29 2001
+++ linux-2.4.12.scx/kernel/sched.c	Thu Oct 18 17:15:48 2001
@@ -171,9 +171,15 @@
 #ifdef CONFIG_SMP
 		/* Give a largish advantage to the same processor...   */
 		/* (this is equivalent to penalizing other processors) */
-		if (p->processor == this_cpu)
+		if (p->processor == this_cpu) {
 			weight += PROC_CHANGE_PENALTY;
-#endif
+			if (p->cpu_jtime > jiffies)
+				weight += p->cpu_jtime - jiffies;
+		}
+#else	/* #ifdef CONFIG_SMP */
+		if (p->cpu_jtime > jiffies)
+			weight += p->cpu_jtime - jiffies;
+#endif	/* #ifdef CONFIG_SMP */

 		/* .. and a slight advantage to the current MM */
 		if (p->mm == this_mm || !p->mm)
@@ -382,7 +388,7 @@
  * delivered to the current task. In this case the remaining time
  * in jiffies will be returned, or 0 if the timer expired in time
  *
- * The current task state is guaranteed to be TASK_RUNNING when this
+ * The current task state is guaranteed to be TASK_RUNNING when this
  * routine returns.
  *
  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
@@ -574,7 +580,10 @@
 		case TASK_RUNNING:;
 	}
 	prev->need_resched = 0;
-
+	if (prev != idle_task(this_cpu)) {
+		prev->cpu_jtime -= prev->cpu_jtime > prev->sched_jtime ? prev->sched_jtime: 0;
+		prev->cpu_jtime += (jiffies - prev->sched_jtime) + jiffies;
+	}
 	/*
 	 * this is the scheduler proper:
 	 */
@@ -611,6 +620,7 @@
  	next->has_cpu = 1;
 	next->processor = this_cpu;
 #endif
+	next->sched_jtime = jiffies;
 	spin_unlock_irq(&runqueue_lock);

 	if (prev == next) {