From: Mike Galbraith <efault@gmx.de>
To: Jens Axboe <axboe@suse.de>
Cc: Con Kolivas <kernel@kolivas.org>, Robert Love <rml@tech9.net>,
Felipe Alfaro Solana <felipe_alfaro@linuxmail.org>,
Peter Lundkvist <p.lundkvist@telia.com>,
akpm@digeo.com, mingo@elte.hu,
LKML <linux-kernel@vger.kernel.org>
Subject: Re: Bad interactive behaviour in 2.5.65-66 (sched.c)
Date: Fri, 18 Apr 2003 15:58:41 +0200 [thread overview]
Message-ID: <5.2.0.9.2.20030418145953.00cb4068@pop.gmx.net> (raw)
In-Reply-To: <20030331063548.GQ917@suse.de>
[-- Attachment #1: Type: text/plain, Size: 3320 bytes --]
At 08:35 AM 3/31/2003 +0200, Jens Axboe wrote:
>On Mon, Mar 31 2003, Mike Galbraith wrote:
> > At 07:06 AM 3/31/2003 +1000, Con Kolivas wrote:
> > >On Mon, 31 Mar 2003 00:14, Jens Axboe wrote:
> > >> On Sat, Mar 29 2003, Robert Love wrote:
> > >> > On Sat, 2003-03-29 at 21:33, Con Kolivas wrote:
> > >> > > Are you sure this should be called a bug? Basically X is an
> > >interactive
> > >> > > process. If it now is "interactive for a priority -10 process" then
> > >it
> > >> > > should be hogging the cpu time no? The priority -10 was a workaround
> > >> > > for lack of interactivity estimation on the old scheduler.
> > >> >
> > >> > Well, I do not necessarily think that renicing X is the problem. Just
> > >> > an idea.
> > >>
> > >> I see the exact same behaviour here (systems appears fine, cpu intensive
> > >> app running, attempting to start anything _new_ stalls for ages), and I
> > >> definitely don't play X renice tricks.
> > >>
> > >> It basically made 2.5 unusable here, waiting minutes for an ls to even
> > >> start displaying _anything_ is totally unacceptable.
> > >
> > >I guess I should have trusted my own benchmark that was showing this was
> > >worse
> > >for system responsiveness.
> >
> > I don't think it's really bad for system responsiveness. I think the
>
>What drugs are you on? 2.5.65/66 is the worst interactive kernel I've
>ever used, it would be _embarassing_ to release a 2.6-test with such a
>rudimentary flaw in it. IOW, a big show stopper.
Hehehe... try the attached if you're brave. It took me a loooong time to
get backboost to work right. Mainly because backboost wasn't really broken
:))) This patch _needs_ backboost to work, (see sleep_avg_tick()) and it
does seem to do the job very nicely.
> > problem is just that the sample is too small. The proof is that simply
> > doing sleep_time %= HZ cures most of my woes. WRT contest and it's
The real problem is that there is no information in the fact that you were
in lala land for a year or so. Just because you slept through lunch,
there's nothing that says you'll be a good mood afterward. The useful
information is the fact that someone else got a chance at the cpu, and
you're only a really nice guy if you share a lot. Take a look at what I
did to activate_task()... if you slept for a short time, use that
information. If you slept for a long time, you get exactly what you need
to finish your time slice. This isn't subject to the number of tasks
queued up, so the mistakes are smaller. I also dispose of mistakes faster
to make sure that interactive tasks (which aren't once they start running a
lot) don't eat ages of cpu. With this patch, I can get more than one task
from a make -j30 bzImage in an ext3 partition to run concurrently, _and_ X
is wonderful as well (gee, I really can have my cake and eat it too:).
> Irk, that sounds like a really ugly bandaid.
Well, it was just tossing the most damaging part of the problem into the
bit bucket.
Anyway, anyone who thinks the scheduler is still unfair, or el-sucko in any
way should feel free to beat upon this experiment. I really like this
one... think I'll even keep my fingers off it for a few minutes ;-)
-Mike
Yeah, some of it _is_ gratuitous, but heck, it's almost pure research. (no
kaBoOMs... yet)
[-- Attachment #2: 2567sched.diff --]
[-- Type: application/octet-stream, Size: 7824 bytes --]
--- kernel/sched.c.org Thu Apr 17 05:38:40 2003
+++ kernel/sched.c Fri Apr 18 13:35:40 2003
@@ -66,14 +66,15 @@
*/
#define MIN_TIMESLICE ( 10 * HZ / 1000)
#define MAX_TIMESLICE (200 * HZ / 1000)
-#define CHILD_PENALTY 50
+#define CHILD_PENALTY 75
#define PARENT_PENALTY 100
#define EXIT_WEIGHT 3
#define PRIO_BONUS_RATIO 25
#define INTERACTIVE_DELTA 2
-#define MAX_SLEEP_AVG (10*HZ)
-#define STARVATION_LIMIT (10*HZ)
+#define MAX_SLEEP_AVG (10 * HZ)
+#define STARVATION_LIMIT (MAX_SLEEP_AVG / 2)
#define NODE_THRESHOLD 125
+#define TIMESLICE_GRANULARITY (HZ/20 ?: 1)
/*
* If a task is 'interactive' then we reinsert it in the active
@@ -124,12 +125,17 @@
* task_timeslice() is the interface that is used by the scheduler.
*/
-#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
- ((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)/(MAX_USER_PRIO - 1)))
+#define BASE_TIMESLICE(p) \
+ (MAX_TIMESLICE * (MAX_PRIO-(p)->static_prio)/MAX_USER_PRIO)
static inline unsigned int task_timeslice(task_t *p)
{
- return BASE_TIMESLICE(p);
+ unsigned int time_slice = BASE_TIMESLICE(p);
+
+ if (time_slice < MIN_TIMESLICE)
+ time_slice = MIN_TIMESLICE;
+
+ return time_slice;
}
/*
@@ -279,6 +285,7 @@
*/
static inline void dequeue_task(struct task_struct *p, prio_array_t *array)
{
+ p->array = NULL;
array->nr_active--;
list_del(&p->run_list);
if (list_empty(array->queue + p->prio))
@@ -340,13 +347,16 @@
* Update all the scheduling statistics stuff. (sleep average
* calculation, priority modifiers, etc.)
*/
+#define MAY_BACKBOOST \
+ (!in_interrupt() && !TASK_NICE(current) && !TASK_NICE(p))
+
static inline int activate_task(task_t *p, runqueue_t *rq)
{
long sleep_time = jiffies - p->last_run - 1;
int requeue_waker = 0;
if (sleep_time > 0) {
- int sleep_avg;
+ int sleep_avg = p->sleep_avg;
/*
* This code gives a bonus to interactive tasks.
@@ -356,7 +366,7 @@
* spends sleeping, the higher the average gets - and the
* higher the priority boost gets as well.
*/
- sleep_avg = p->sleep_avg + sleep_time;
+ sleep_avg += min(sleep_time, (long) p->time_slice);
/*
* 'Overflow' bonus ticks go to the waker as well, so the
@@ -364,8 +374,23 @@
* boosting tasks that are related to maximum-interactive
* tasks.
*/
- if (sleep_avg > MAX_SLEEP_AVG)
+ if (sleep_avg > MAX_SLEEP_AVG) {
+ if (MAY_BACKBOOST) {
+#if 0
+ printk(KERN_DEBUG "%lu: %d boosted %d by %d\n",
+ jiffies, p->pid, current->pid, sleep_avg-MAX_SLEEP_AVG);
+#endif
+ sleep_avg += current->sleep_avg - MAX_SLEEP_AVG;
+ if (sleep_avg > MAX_SLEEP_AVG)
+ sleep_avg = MAX_SLEEP_AVG;
+
+ if (current->sleep_avg != sleep_avg) {
+ current->sleep_avg = sleep_avg;
+ requeue_waker = 1;
+ }
+ }
sleep_avg = MAX_SLEEP_AVG;
+ }
if (p->sleep_avg != sleep_avg) {
p->sleep_avg = sleep_avg;
p->prio = effective_prio(p);
@@ -381,11 +406,10 @@
*/
static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
{
- nr_running_dec(rq);
+ dequeue_task(p, p->array);
if (p->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
- dequeue_task(p, p->array);
- p->array = NULL;
+ nr_running_dec(rq);
}
/*
@@ -569,7 +593,10 @@
* from forking tasks that are max-interactive.
*/
current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
- p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+ if (likely(current->parent->pid > 1))
+ p->sleep_avg = current->sleep_avg * CHILD_PENALTY / 100;
+ else
+ p->sleep_avg = current->sleep_avg = MAX_SLEEP_AVG;
p->prio = effective_prio(p);
set_task_cpu(p, smp_processor_id());
@@ -596,22 +623,20 @@
*/
void sched_exit(task_t * p)
{
- unsigned long flags;
-
- local_irq_save(flags);
if (p->first_time_slice) {
p->parent->time_slice += p->time_slice;
if (unlikely(p->parent->time_slice > MAX_TIMESLICE))
p->parent->time_slice = MAX_TIMESLICE;
}
- local_irq_restore(flags);
/*
* If the child was a (relative-) CPU hog then decrease
* the sleep_avg of the parent as well.
*/
- if (p->sleep_avg < p->parent->sleep_avg)
+#if 0
+ if (p->parent->pid > 1 && p->sleep_avg < p->parent->sleep_avg)
p->parent->sleep_avg = (p->parent->sleep_avg * EXIT_WEIGHT +
- p->sleep_avg) / (EXIT_WEIGHT + 1);
+ p->sleep_avg) / MAX_USER_PRIO;
+#endif
}
/**
@@ -1161,14 +1186,29 @@
*
* To guarantee that this does not starve expired tasks we ignore the
* interactivity of a task if the first expired task had to wait more
- * than a 'reasonable' amount of time. This deadline timeout is
- * load-dependent, as the frequency of array switched decreases with
- * increasing number of running tasks:
+ * than a 'reasonable' amount of time.
*/
#define EXPIRED_STARVING(rq) \
- (STARVATION_LIMIT && ((rq)->expired_timestamp && \
- (jiffies - (rq)->expired_timestamp >= \
- STARVATION_LIMIT * ((rq)->nr_running) + 1)))
+ (STARVATION_LIMIT && (rq)->expired_timestamp && \
+ time_after(jiffies, (rq)->expired_timestamp + STARVATION_LIMIT))
+
+/*
+ * Scale the cpu usage penalty for tasks which are not niced to below
+ * zero by their nice value and interactivity. Simply because a task
+ * has been nice recently does NOT mean it should be allowed 3 seconds
+ * of cpu before it will be expired.
+ */
+static inline void sleep_avg_tick(task_t *p)
+{
+ int bias = 1, nice = TASK_NICE(p);
+
+ if (nice >= 0)
+ bias += p->static_prio - p->prio + nice - INTERACTIVE_DELTA;
+ if (bias <= 0)
+ bias = 1;
+ if (p->sleep_avg >= bias)
+ p->sleep_avg -= bias;
+}
/*
* This function gets called by the timer code, with HZ frequency.
@@ -1203,12 +1243,13 @@
kstat_cpu(cpu).cpustat.user += user_ticks;
kstat_cpu(cpu).cpustat.system += sys_ticks;
+ spin_lock(&rq->lock);
/* Task might have expired already, but not scheduled off yet */
- if (p->array != rq->active) {
- set_tsk_need_resched(p);
- return;
+ if (p->array != rq->active || p->state != TASK_RUNNING) {
+ if (p->state > TASK_UNINTERRUPTIBLE)
+ set_tsk_need_resched(p);
+ goto out;
}
- spin_lock(&rq->lock);
/*
* The task was running during this tick - update the
* time slice counter and the sleep average. Note: we
@@ -1217,8 +1258,6 @@
* it possible for interactive tasks to use up their
* timeslices at their highest priority levels.
*/
- if (p->sleep_avg)
- p->sleep_avg--;
if (unlikely(rt_task(p))) {
/*
* RR tasks need a special form of timeslice management.
@@ -1235,6 +1274,7 @@
}
goto out;
}
+ sleep_avg_tick(p);
if (!--p->time_slice) {
dequeue_task(p, rq->active);
set_tsk_need_resched(p);
@@ -1248,6 +1288,26 @@
enqueue_task(p, rq->expired);
} else
enqueue_task(p, rq->active);
+ goto out;
+ }
+ /*
+ * Prevent a too long timeslice allowing a task to monopolize
+ * the CPU. We do this by splitting up the timeslice into
+ * smaller pieces.
+ *
+ * Note: this does not mean the task's timeslices expire or
+ * get lost in any way, they just might be preempted by
+ * another task of equal priority. (one with higher
+ * priority would have preempted this task already.) We
+ * requeue this task to the end of the list on this priority
+ * level, which is in essence a round-robin of tasks with
+ * equal priority.
+ */
+ if (!(p->time_slice % TIMESLICE_GRANULARITY)) {
+ dequeue_task(p, rq->active);
+ set_tsk_need_resched(p);
+ p->prio = effective_prio(p);
+ enqueue_task(p, rq->active);
}
out:
spin_unlock(&rq->lock);
@@ -1669,7 +1729,7 @@
*/
int task_prio(task_t *p)
{
- return p->prio - MAX_USER_RT_PRIO;
+ return p->prio - MAX_RT_PRIO;
}
/**
@@ -2525,6 +2585,7 @@
rq = this_rq();
rq->curr = current;
rq->idle = current;
+ current->sleep_avg = MAX_SLEEP_AVG;
set_task_cpu(current, smp_processor_id());
wake_up_forked_process(current);
next prev parent reply other threads:[~2003-04-18 13:42 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-03-29 21:32 Peter Lundkvist
2003-03-29 23:23 ` Robert Love
2003-03-30 1:21 ` Felipe Alfaro Solana
2003-03-30 2:05 ` Robert Love
2003-03-30 2:33 ` Con Kolivas
2003-03-30 2:46 ` Robert Love
2003-03-30 3:58 ` Tom Sightler
2003-03-30 5:23 ` Andrew Morton
2003-03-30 19:24 ` Tom Sightler
2003-04-01 1:41 ` Jeremy Fitzhardinge
2003-03-30 14:14 ` Jens Axboe
2003-03-30 21:06 ` Con Kolivas
2003-03-31 2:23 ` Mike Galbraith
2003-03-31 6:35 ` Jens Axboe
2003-03-31 7:05 ` Mike Galbraith
2003-03-31 8:46 ` Felipe Alfaro Solana
2003-03-31 8:54 ` Nick Piggin
2003-04-20 3:55 ` Mike Galbraith
2003-04-18 13:58 ` Mike Galbraith [this message]
2003-03-30 10:16 ` Felipe Alfaro Solana
2003-03-30 11:18 ` Mika Liljeberg
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=5.2.0.9.2.20030418145953.00cb4068@pop.gmx.net \
--to=efault@gmx.de \
--cc=akpm@digeo.com \
--cc=axboe@suse.de \
--cc=felipe_alfaro@linuxmail.org \
--cc=kernel@kolivas.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
--cc=p.lundkvist@telia.com \
--cc=rml@tech9.net \
/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®