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. !" |
------------------------------------------------------------------------
prev parent 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®