mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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);
 

  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®