mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: "Kevin O'Connor" <kevin@koconnor.net>
To: Ingo Molnar <mingo@elte.hu>
Cc: linux-kernel@vger.kernel.org
Subject: Re: [patch] Re: O(1) batch scheduler
Date: Thu, 11 Jul 2002 00:41:59 -0400	[thread overview]
Message-ID: <20020711004159.A5356@arizona.localdomain> (raw)
In-Reply-To: <Pine.LNX.4.44.0207110842520.3580-100000@localhost.localdomain>; from mingo@elte.hu on Thu, Jul 11, 2002 at 09:05:35AM +0200

On Thu, Jul 11, 2002 at 08:27:13AM +0200, Ingo Molnar wrote:
> 
> the problem with a pure weighted average (ie. no ->idle_count, just a
> weighted average calculated in the scheduler tick) is that with HZ=1000
> and a 32-bit word length the sampling gets too inaccurate. For the average
> to be meaningful it needs to be at least 'a few seconds worth' - which is
> 'a few thousands of events' - the rounding errors are pretty severe in
> that case.

Yes, I see where truncation could be a problem.  However, one should be
able to offset this with a larger base unit and with appropriate rounding.

On Thu, Jul 11, 2002 at 09:05:35AM +0200, Ingo Molnar wrote:
> 
> you can find my latest scheduler tree, against 2.5.25-vanilla, at:
> 
>         http://redhat.com/~mingo/O(1)-scheduler/sched-2.5.25-A7
> 
> note that in addition to the bugfix i've further simplified the
> idle-average calculation - simple, weightless running average is
> more than enough.

I looked through the A8 code, and I see that it is using a weighted average
with the last second having as much "weight" as all previous seconds.  This
is understandable (as a second is an eternity to a computer), but I wonder
how this interacts with the idle_ticks_left calculation.

Since idle_avg is only updated once a second, it will basically be around a
half-second outdated whenever it is queried.  With the smaller time
duration on idle_avg calculations, idle_avg will only describe the last 2
to 3 seconds of the CPU.  This means the statistic describes about two
seconds and is a half-second outdated - I wonder how useful this statistic
is.

Just for kicks, I wrote up a patch with a pure weighted average
calculation.  Again, I wasn't able to test this on a real kernel (I don't
have a development box I can risk 2.5 on yet).  However, I did run a bunch
of data through the two different algorithms.  The "hybrid" code matches
the pure weighted average code right after the hybrid code updates
idle_avg.  However, the pure weighted average code responds quicker to a
changing environment.  YMMV.

-Kevin


--- linux-2.5.25-b/kernel/sched.c	Wed Jul 10 23:55:47 2002
+++ linux-2.5.25-a/kernel/sched.c	Thu Jul 11 00:33:22 2002
@@ -166,14 +166,10 @@
 
 	/*
 	 * Per-CPU idle CPU time tracking:
-	 *
-	 * - idle_ticks_left counts back from HZ to 0.
-	 * - idle_count is the number of idle ticks in the last second.
-	 * - once it reaches 0, a new idle_avg is calculated.
 	 */
 	#define IDLE_TICKS (HZ)
 
-	unsigned int idle_ticks_left, idle_count, idle_avg;
+	unsigned int idle_avg;
 
 } ____cacheline_aligned;
 
@@ -926,21 +922,14 @@
 #if CONFIG_SMP
 	if (user_ticks || sys_ticks) {
 		/*
-		 * This code is rare, triggered only once per second:
+		 * Maintain a weighted average between 0 and 100000:
 		 */
-		if (--rq->idle_ticks_left <= 0) {
-			/*
-			 * Maintain a simple running average:
-			 */
-			rq->idle_avg += rq->idle_count;
-			rq->idle_avg >>= 1;
-
-			rq->idle_ticks_left = IDLE_TICKS;
-			rq->idle_count = 0;
-		}
+		int idle_count = 0;
+		if (p == rq->idle || p->policy == SCHED_BATCH)
+			idle_count = 100000;
+		rq->idle_avg = (rq->idle_avg * (IDLE_TICKS - 1)
+				+ idle_count + IDLE_TICKS/2) / IDLE_TICKS;
 	}
-	if (p == rq->idle || p->policy == SCHED_BATCH)
-		rq->idle_count++;
 #endif
 	if (p == rq->idle) {
 		if (local_bh_count(cpu) || local_irq_count(cpu) > 1)
@@ -2085,7 +2074,6 @@
 		spin_lock_init(&rq->lock);
 		INIT_LIST_HEAD(&rq->migration_queue);
 		INIT_LIST_HEAD(&rq->batch_queue);
-		rq->idle_ticks_left = IDLE_TICKS;
 
 		for (j = 0; j < 2; j++) {
 			array = rq->arrays + j;



-- 
 ------------------------------------------------------------------------
 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | kevin@koconnor.net                  'IMHO', 'FAQ', 'BTW', etc. !"    |
 ------------------------------------------------------------------------

      reply	other threads:[~2002-07-11  4:38 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2002-07-01  9:45 [patch] sched-2.5.24-D3, batch/idle priority scheduling, SCHED_BATCH Ingo Molnar
2002-07-10  2:30 ` O(1) batch scheduler Kevin O'Connor
2002-07-11  6:27   ` Ingo Molnar
2002-07-11  6:32   ` Ingo Molnar
2002-07-11  7:05   ` [patch] " Ingo Molnar
2002-07-11  4:41     ` Kevin O'Connor [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20020711004159.A5356@arizona.localdomain \
    --to=kevin@koconnor.net \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@elte.hu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®