Bad interactive behaviour in 2.5.65-66 (sched.c)

Bad interactive behaviour in 2.5.65-66 (sched.c)

[Peter Lundkvist]

Hi,

I have seen long delays when starting e.g. xterm from my
window manager (sawfish) either by keyboard-shortcut or by
menu command (by mouse) starting from 2.5.65. Sometimes it
starts immediately, sometimes after up to 2 seconds (idle
system). If I start a new xterm from xterm it always start
immediately. 2.5.64 always behaved OK.

My first try to solve this problem  was to use some
scheduler parameters from 2.6.64:
    #define MAX_TIMESLICE         (300 * HZ / 1000)
    #define CHILD_PENALTY         95
    #define MAX_SLEEP_AVG         (2*HZ)
    #define STARVATION_LIMIT      (2*HZ)

but got the same behaviour.

2nd try was to use sched.c, sched.h from 2.5.64 in a
2.5.66 build + one line patch in fork.c:
-       p->last_run = jiffies;
+       p->sleep_timestamp = jiffies;

Now the system behaves as it should!

My system is a P-III 700 (Inspiron 4000),
and Debian (X is running at nice = -10).

Best regards,
Peter Lundkvist

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Robert Love]

On Sat, 2003-03-29 at 16:32, Peter Lundkvist wrote:

> I have seen long delays when starting e.g. xterm from my
> window manager (sawfish) either by keyboard-shortcut or by
> menu command (by mouse) starting from 2.5.65. Sometimes it
> starts immediately, sometimes after up to 2 seconds (idle
> system). If I start a new xterm from xterm it always start
> immediately. 2.5.64 always behaved OK.

You are not alone...

> My first try to solve this problem  was to use some
> scheduler parameters from 2.6.64:
>     #define MAX_TIMESLICE         (300 * HZ / 1000)
>     #define CHILD_PENALTY         95
>     #define MAX_SLEEP_AVG         (2*HZ)
>     #define STARVATION_LIMIT      (2*HZ)
> 
> but got the same behaviour.

Expected.

> 2nd try was to use sched.c, sched.h from 2.5.64 in a
> 2.5.66 build + one line patch in fork.c:
> -       p->last_run = jiffies;
> +       p->sleep_timestamp = jiffies;
> 
> Now the system behaves as it should!

This seems to confirm it was one of the interactivity changes that went
into 2.5.65.  I figured as much but it is nice to get confirmation. 
Thank you for trying this.

Now to figure out which one...

> My system is a P-III 700 (Inspiron 4000),
> and Debian (X is running at nice = -10).

I wonder if the reniced X is a factor?

	Robert Love

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Felipe Alfaro Solana]

On Sun, 2003-03-30 at 00:23, Robert Love wrote:
> This seems to confirm it was one of the interactivity changes that went
> into 2.5.65.  I figured as much but it is nice to get confirmation. 
> Thank you for trying this.
> 
> Now to figure out which one...
> 
> > My system is a P-III 700 (Inspiron 4000),
> > and Debian (X is running at nice = -10).
> 
> I wonder if the reniced X is a factor?

Theoretically, with interactivity enhancaments, you'll never need to
renice X. In fact, I'm running X with no renice and it feels pretty
snappy.

> 
> ______________________________________________________________________
>        Felipe Alfaro Solana
>    Linux Registered User #287198
> http://counter.li.org

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Robert Love]

On Sat, 2003-03-29 at 20:21, Felipe Alfaro Solana wrote:

> Theoretically, with interactivity enhancaments, you'll never need to
> renice X. In fact, I'm running X with no renice and it feels pretty
> snappy.

I know.

I was wondering, since we are working on an actual bug here, whether or
not renicing X is leading to a starvation issue between X and whatever
is starving.  I have seen it before.

My system is responsive, too, and I do not renice X.  But it might
help.  Or it might cause starvation issues.  We have a bug somewhere...

	Robert Love

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Con Kolivas]

On Sun, 30 Mar 2003 12:05, Robert Love wrote:
> On Sat, 2003-03-29 at 20:21, Felipe Alfaro Solana wrote:
> > Theoretically, with interactivity enhancaments, you'll never need to
> > renice X. In fact, I'm running X with no renice and it feels pretty
> > snappy.
>
> I know.
>
> I was wondering, since we are working on an actual bug here, whether or
> not renicing X is leading to a starvation issue between X and whatever
> is starving.  I have seen it before.
>
> My system is responsive, too, and I do not renice X.  But it might
> help.  Or it might cause starvation issues.  We have a bug somewhere...

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.

Con

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Robert Love]

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.

We do have a problem, though.  Nearly indefinite starvation and all sort
of weird effects like bash not able to create a new process... its a
bug.

Renicing X, aside from some weird client-server starvation issues with
stuff like multimedia programs, should not cause any problem.  It should
help, in fact.  But, you are right, its not needed in the current
scheduler.

	Robert Love

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Tom Sightler]

On Sat, 2003-03-29 at 21:46, Robert Love wrote:
> Well, I do not necessarily think that renicing X is the problem.  Just
> an idea.
> 
> We do have a problem, though.  Nearly indefinite starvation and all sort
> of weird effects like bash not able to create a new process... its a
> bug.

On my system I get a starvation issue with just about any CPU intensive
task.  For example if create a bzip'd tar file from the linux kernel
source with the command:

tar cvp linux | bzip2 -9 > linux.tar.bz2

During this entire time I can switch between different windows and
everything seems great, but if a try to do something like run 'ps ax' or
login to another virtual terminal, or start almost any other program, it
takes 30-45 seconds or longer.

With 2.5.64 doing the same 'tar | bzip2' command above takes nearly the
same length of time, but I can go about my business of running other
programs without any of the above issue.  It's basically seems that the
one process is starving out everything else.

Don't know if this info helps, but it's 100% reproducible on my machine
(a Dell C810 laptop with a 1.13Ghz P3) with both 2.5.65 & 66.

Later,
Tom

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Andrew Morton]

Tom Sightler <ttsig@tuxyturvy.com> wrote:
>
> On my system I get a starvation issue with just about any CPU intensive
> task.  For example if create a bzip'd tar file from the linux kernel
> source with the command:
> 
> tar cvp linux | bzip2 -9 > linux.tar.bz2
> 

Ingo has determined that Linus's backboost trick is causing at least some
of these problems. Please test and report upon the below patch.

I have another workload which is showing starvation with or without this
patch - it is the bitkeeper verification step in a `bk clone' on a
uniprocessor kernel.  Still poking at that one.






From: Ingo Molnar <mingo@elte.hu>

the patch below fixes George's setiathome problems (as expected).  It
essentially turns off Linus' improvement, but i dont think it can be fixed
sanely.

the problem with setiathome is that it displays something every now and
then - so it gets a backboost from X, and hovers at a relatively high
priority.



 kernel/sched.c |   13 +------------
 1 files changed, 1 insertion(+), 12 deletions(-)

diff -puN kernel/sched.c~sched-interactivity-backboost-revert kernel/sched.c
--- 25/kernel/sched.c~sched-interactivity-backboost-revert	2003-03-28 22:30:08.000000000 -0800
+++ 25-akpm/kernel/sched.c	2003-03-28 22:30:08.000000000 -0800
@@ -379,19 +379,8 @@ static inline int activate_task(task_t *
 		 * boosting tasks that are related to maximum-interactive
 		 * tasks.
 		 */
-		if (sleep_avg > MAX_SLEEP_AVG) {
-			if (!in_interrupt()) {
-				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;
-				}
-			}
+		if (sleep_avg > MAX_SLEEP_AVG)
 			sleep_avg = MAX_SLEEP_AVG;
-		}
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
 			p->prio = effective_prio(p);

_

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Tom Sightler]

On Sun, 2003-03-30 at 00:23, Andrew Morton wrote:
> Tom Sightler <ttsig@tuxyturvy.com> wrote:
> >
> > On my system I get a starvation issue with just about any CPU intensive
> > task.  For example if create a bzip'd tar file from the linux kernel
> > source with the command:
> > 
> > tar cvp linux | bzip2 -9 > linux.tar.bz2
> > 
> 
> Ingo has determined that Linus's backboost trick is causing at least some
> of these problems. Please test and report upon the below patch.

OK, this definitely makes a big difference for my test cases which
include that 'tar' above as well as a run of dvd::rip.  Without this
patch everything else on my system drops to a total crawl, especially
which dvd::rip is running, dvd::rip itself won't even switch tabs.  With
this patch everything seems quite normal and snappy.

I'll try a few more test cases but backing this out certainly seems to
restore the system to the same behavior as 2.5.64.  BTW, I'm running
this on 2.5.65-mm4.  I would have tested on 2.5.66-mm1 but for some
reason my system locks solid after only a few minutes with it.  I
haven't tried to track that down yet.

Later,
Tom
 

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Jeremy Fitzhardinge]

On Sat, 2003-03-29 at 21:23, Andrew Morton wrote:
> Tom Sightler <ttsig@tuxyturvy.com> wrote:
> >
> > On my system I get a starvation issue with just about any CPU intensive
> > task.  For example if create a bzip'd tar file from the linux kernel
> > source with the command:
> > 
> > tar cvp linux | bzip2 -9 > linux.tar.bz2
> > 
> 
> Ingo has determined that Linus's backboost trick is causing at least some
> of these problems. Please test and report upon the below patch.
>[...]
> From: Ingo Molnar <mingo@elte.hu>
> 
> the patch below fixes George's setiathome problems (as expected).  It
> essentially turns off Linus' improvement, but i dont think it can be fixed
> sanely.
> 
> the problem with setiathome is that it displays something every now and
> then - so it gets a backboost from X, and hovers at a relatively high
> priority.

This fixes the starvation I was getting with xmms visualizers, which
have a similar usage pattern: they're mostly CPU-bound, but they talk to
the X server for drawing.

	J

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Jens Axboe]

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.

-- 
Jens Axboe

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Con Kolivas]

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.

Con

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Mike Galbraith]

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 
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 
io_load, applying even the tiniest percentage of a timeslice penalty per 
activation and no other limits _dramatically_  affects the benchmark 
numbers.  (try it and you'll see. I posted a [ugly but useful for 
experimentation] patch which allows you to set these things and/or disable 
them from /proc/sys/sched)

I'm trying something right now that I think might work.  I set 
MAX_SLEEP_AVG to 10*60*HZ , start init out at max, and never allow it to 
degrade.  Everyone else is subject to boost and degradation, with the 
maximum boost being MAX_SLEEP_AVG/20 (which is still a good long sleep, and 
the max that one sleep can boost you is one priority).  When you start a 
cpu hogging task, it should drop in priority just fine, and rapid context 
switchers shouldn't gain such an advantage.  We'll see.  Tricky part is 
setting CHILD_PENALTY to the right number such that fork()->fork() kind of 
tasks don't drop down too low and have to crawl back up.  Contest falls 
into this category.

Anyway, I think that inverting the problem might cure most of the symptoms ;-)

         -Mike 

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Jens Axboe]

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.

> 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 

Irk, that sounds like a really ugly bandaid.

I'm wondering why the scheduler guys aren't all over this problem,
getting it fixed.

-- 
Jens Axboe

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Mike Galbraith]

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.

It's only horrible when you trigger the problems, otherwise it's wonderful.

> > 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
>
>Irk, that sounds like a really ugly bandaid.

Nope, it's a really ugly _tourniquet_ ;-)

>I'm wondering why the scheduler guys aren't all over this problem,
>getting it fixed.

I think they are.

         -Mike  

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Felipe Alfaro Solana]

On Mon, 2003-03-31 at 09:05, Mike Galbraith wrote:
> > > 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.
> 
> It's only horrible when you trigger the problems, otherwise it's wonderful.

With scheduler tunables (in -mm, for example), setting min_timeslice =
max_timeslice = 25 helps a lot with those problems (at least for me) :-)

> > > 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
> >
> >Irk, that sounds like a really ugly bandaid.
> 
> Nope, it's a really ugly _tourniquet_ ;-)
> 
> >I'm wondering why the scheduler guys aren't all over this problem,
> >getting it fixed.
> 
> I think they are.

I hope so ;-)

        Felipe Alfaro Solana
   Linux Registered User #287198
http://counter.li.org

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Nick Piggin]

Mike Galbraith wrote:

> At 08:35 AM 3/31/2003 +0200, Jens Axboe wrote:
>
>> 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.
>
>
> It's only horrible when you trigger the problems, otherwise it's 
> wonderful. 

Heh heh, yeah the anticipatory io scheduler is like that too ;)

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Mike Galbraith]

At 06:54 PM 3/31/2003 +1000, Nick Piggin wrote:


>Mike Galbraith wrote:
>
>>At 08:35 AM 3/31/2003 +0200, Jens Axboe wrote:
>>
>>>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.
>>
>>
>>It's only horrible when you trigger the problems, otherwise it's wonderful.
>
>Heh heh, yeah the anticipatory io scheduler is like that too ;)

I gave 2.5.67-mm4 a go yesterday, and let it fsck my old 10gig ext3-ified 
source partition (1k bs, 333k files).  MAJOR improvement over deadline for 
this job.  With the deadline scheduler, it takes 30 minutes to fsck this 
partition, and when pdflush starts it's dinky little writes, it sounds like 
the heads are about to fly through the chassis.  The anticipatory scheduler 
cuts fsck time in half, and the disk is no longer screams in (seek) 
agony.  15 minutes still seems like ages when you're waiting, but it beats 
the HECK out of 30 minutes :)  Nice work.

         -Mike 

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Mike Galbraith]

[-- 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);
 

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Felipe Alfaro Solana]

On Sun, 2003-03-30 at 04:05, Robert Love wrote:
> I was wondering, since we are working on an actual bug here, whether or
> not renicing X is leading to a starvation issue between X and whatever
> is starving.  I have seen it before.
> 
> My system is responsive, too, and I do not renice X.  But it might
> help.  Or it might cause starvation issues.  We have a bug somewhere...

I'm gonna try renicing X to see how it behaves...

________________________________________________________________________
        Felipe Alfaro Solana
   Linux Registered User #287198
http://counter.li.org

Re: Bad interactive behaviour in 2.5.65-66 (sched.c)

[Mika Liljeberg]

On Sun, 2003-03-30 at 01:23, Robert Love wrote:
> I wonder if the reniced X is a factor?

I had some interactivity problems with X reniced to -10. It seemed to me
that X was pre-empting the clients and flushing changes to screen too
quickly. It was probably losing out on some screen update optimizations.
I took out the renice and now the system behaves much better.

	MikaL