[PATCH] O(1) CPU time accounting

[Rik van Riel]

Hi Jim,

this incremental patch (over your O(1) CPU time patch) makes
nice levels work again, though they are fairly steep now:

  PID USER     PRI  NI  SIZE  RSS SWAP SHARE STAT %CPU %MEM   TIME COMMAND
  848 riel      22   0  1284  276 1008  1260 R    92.8  0.0  23:56 loop
  849 riel      23   5  1284  276 1008  1260 R N   4.2  0.0   1:05 loop
  850 riel      24  10  1284  276 1008  1260 R N   1.3  0.0   0:21 loop
  851 riel      32  15  1284  276 1008  1260 R N   0.7  0.0   0:12 loop
  852 riel      32  19  1284  276 1008  1260 R N   0.5  0.0   0:09 loop

This might be a decent basis for an O(1) per-user fair
scheduler, after some more balancing and cleaning up of
excess code.

cheers,

Rik
-- 
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://distro.conectiva.com/
Current spamtrap:  <a href=mailto:"[e-mail]">[e-mail]</a>

===== kernel/sched.c 1.138 vs edited =====
--- 1.138/kernel/sched.c	Tue Oct 29 15:55:16 2002
+++ edited/kernel/sched.c	Tue Nov  5 14:41:18 2002
@@ -72,6 +72,7 @@
 #define INTERACTIVE_DELTA	2
 #define MAX_SLEEP_AVG		(2*HZ)
 #define STARVATION_LIMIT	(2*HZ)
+#define MAX_DEMOTION		10

 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -125,17 +126,27 @@
 #define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
 	((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)/(MAX_USER_PRIO - 1)))

+#define TIMESLICE_DOWN(prio) (MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) *prio / MAX_DEMOTION))
+
+#define TIMESLICE_UP(prio) MIN_TIMESLICE
+
 static inline unsigned int task_timeslice(task_t *p)
 {
+	int priority;
+	unsigned int timeslice;
 	/*
 	 * The more favorable priority the shorter the time slice.
 	 * For 100 Hz clock this gives a range 10 - 191 ms.
 	 * For 1000 Hz clock this gives 1 - 157 ms.
 	 */
-	if (HZ > 100)
-		return(((p)->prio - MAX_RT_PRIO)*4 + 1);
+	priority = p->prio - p->static_prio;
+
+	if (priority >= 0)
+		timeslice = TIMESLICE_DOWN(priority);
 	else
-		return(((p)->prio - MAX_RT_PRIO)/2 + 1);
+		timeslice = TIMESLICE_UP(priority);
+
+	return timeslice;
 }

 /*
@@ -310,13 +321,15 @@
 static inline int effective_prio(task_t *p)
 {
 	int bonus, prio;
-
+
 	prio =  p->static_prio + (10 * p->run_avg/MAX_RUN_AVG) - 5;
 	prio = (p->prio*3 + prio)/4;
 	if (prio < MAX_RT_PRIO)
 		prio = MAX_RT_PRIO;
 	if (prio > MAX_PRIO-1)
 		prio = MAX_PRIO-1;
+	if (prio > p->static_prio + MAX_DEMOTION)
+		prio = p->static_prio + MAX_DEMOTION;
 	return prio;
 }

@@ -1034,6 +1047,8 @@
 		set_tsk_need_resched(p);
 		if (p->prio < MAX_PRIO-1)
 			p->prio++;
+		if (p->prio < p->static_prio)
+			p->prio = p->static_prio;
 		p->time_slice = task_timeslice(p);
 		p->first_time_slice = 0;
 		enqueue_task(p, rq->active);