O(1) batch scheduler

From: Kevin O'Connor (kevin@koconnor.net)
Date: Tue Jul 09 2002 - 21:30:21 EST

Hi Ingo,

I looked through your sched-2.5.25-A5 patch, and I'm confused by the
idle_count array. It calculates the idle average of the last 9 seconds -
but why not just use a weighted average. A weighted average is going to be
very close to the true average, and where it differs the weighted average
should be preferable.

Incremental patch (untested):

--- kernel/sched.c Tue Jul 9 22:06:38 2002
+++ ../linux-2.5.25-a/kernel/sched.c Tue Jul 9 22:23:41 2002
@@ -171,7 +171,7 @@
         #define IDLE_TICKS (HZ)
 
         int idle_ticks_left;
- int idle_count[IDLE_SLOTS];
+ int idle_count;
         int idle_avg;
 
 } ____cacheline_aligned;
@@ -886,17 +886,6 @@
 #define BUSY_REBALANCE_TICK (HZ/4 ?: 1)
 #define IDLE_REBALANCE_TICK (HZ/1000 ?: 1)
 
-static inline int recalc_idle_avg(runqueue_t *rq)
-{
- int i, count = 0, avg;
-
- for (i = 1; i < IDLE_SLOTS; i++)
- count += rq->idle_count[i];
-
- avg = count / (IDLE_SLOTS - 1);
- return avg;
-}
-
 static inline void idle_tick(runqueue_t *rq)
 {
         if (jiffies % IDLE_REBALANCE_TICK)
@@ -938,17 +927,13 @@
                  * This code is rare, triggered only once per second:
                  */
                 if (--rq->idle_ticks_left <= 0) {
- int i;
-
- rq->idle_ticks_left = IDLE_TICKS;
- for (i = IDLE_SLOTS-1; i > 0; i--)
- rq->idle_count[i] = rq->idle_count[i-1];
- rq->idle_count[0] = 0;
- rq->idle_avg = recalc_idle_avg(rq);
+ rq->idle_avg = (rq->idle_avg * (IDLE_SLOTS - 1)
+ + rq->idle_count) / IDLE_SLOTS;
+ rq->idle_count = 0;
                 }
         }
         if (p == rq->idle || p->policy == SCHED_BATCH)
- rq->idle_count[0]++;
+ rq->idle_count++;
 #endif
         if (p == rq->idle) {
                 if (local_bh_count(cpu) || local_irq_count(cpu) > 1) 

-- 
 ------------------------------------------------------------------------
 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | kevin@koconnor.net                  'IMHO', 'FAQ', 'BTW', etc. !"    |
 ------------------------------------------------------------------------
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

This archive was generated by hypermail 2b29 : Mon Jul 15 2002 - 22:00:16 EST