-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
For my sins I've included what I thought was necessary for this patch.
The interactivity for tasks is based on the sleep avg accumulated divided by
the running time of the task. However since the accumulated time is not
linear with time it now works on the premise that running time is an
exponential function entirely. Pat Erley was the genius who implemented this
simple exponential function in surprisingly low overhead integer maths.
Also added was some jiffy wrap logic (as if anyone would still be running my
patch in 50 days :P).
Long sleepers were reclassified as idle according to the new exponential
logic.
If you test, please note this works better at 1000Hz.
Attached also is my bastardised version of Ingo's timeslice granularity patch.
This round robins tasks on the active array every 10ms, which _might_ be
detrimental in throughput applications but has not been benchmarked. However
for desktops it does wonders to smoothing out the jerkiness of X and I highly
recommend using this in combination with the O1int patch.
This is very close to all the logic I wanted to implement. It might need more
tuning... Note parent penalty, child penalty and exit weight (uppercase) no
longer do anything.
Please test and comment.
Con
P.S. In the words of Zwane - there is always a corner case. Corner case I
think I still need to tackle is the application that spins madly waiting for
it's child to start, and in the process it is the parent that is starving the
child by being higher priority than it. This seems to be a coding style
anomaly brought out by the scheduler.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE+/SSSF6dfvkL3i1gRArK1AJ93sHl+I8J0qaOesShdJLvU1YENPgCglJhv
mxFcs8sAun1QNw0gz2tLJ2Q=
=S5PH
-----END PGP SIGNATURE-----
On Sat, 28 Jun 2003 15:16, Con Kolivas wrote:
> For my sins I've included what I thought was necessary for this patch.
>
> The interactivity for tasks is based on the sleep avg accumulated divided
> by the running time of the task. However since the accumulated time is not
> linear with time it now works on the premise that running time is an
> exponential function entirely. Pat Erley was the genius who implemented
> this simple exponential function in surprisingly low overhead integer
> maths.
>
> Also added was some jiffy wrap logic (as if anyone would still be running
> my patch in 50 days :P).
>
> Long sleepers were reclassified as idle according to the new exponential
> logic.
>
> If you test, please note this works better at 1000Hz.
>
> Attached also is my bastardised version of Ingo's timeslice granularity
> patch. This round robins tasks on the active array every 10ms, which
> _might_ be detrimental in throughput applications but has not been
> benchmarked. However for desktops it does wonders to smoothing out the
> jerkiness of X and I highly recommend using this in combination with the
> O1int patch.
>
> This is very close to all the logic I wanted to implement. It might need
> more tuning... Note parent penalty, child penalty and exit weight
> (uppercase) no longer do anything.
>
> Please test and comment.
>
> Con
>
> P.S. In the words of Zwane - there is always a corner case. Corner case I
> think I still need to tackle is the application that spins madly waiting
> for it's child to start, and in the process it is the parent that is
> starving the child by being higher priority than it. This seems to be a
> coding style anomaly brought out by the scheduler.
And just for good measure here is the latest with a slight addition that helps
X smoothness over time. It gives the sleep_avg a little headroom so it
doesn't drop from interactive as easily with bursts of cpu activity.
Con
On Sat, 2003-06-28 at 18:30, Con Kolivas wrote:
> On Sat, 28 Jun 2003 15:16, Con Kolivas wrote:
> > For my sins I've included what I thought was necessary for this patch.
> >
> And just for good measure here is the latest with a slight addition that helps
> X smoothness over time. It gives the sleep_avg a little headroom so it
> doesn't drop from interactive as easily with bursts of cpu activity.
Have not tried this one, but previous had the same issues on this HT
box. Reverted the two patches, and I have no mouse jerkyness or laggy
redraw of windows.
Anyhow, will it be a wise move to try and get a scheduler that works
fine for both UP and SMP ?
Regards,
--
Martin Schlemmer
On Sat, 2003-06-28 at 07:16, Con Kolivas wrote:
> The interactivity for tasks is based on the sleep avg accumulated divided by
> the running time of the task. However since the accumulated time is not
> linear with time it now works on the premise that running time is an
> exponential function entirely. Pat Erley was the genius who implemented this
> simple exponential function in surprisingly low overhead integer maths.
>
> Also added was some jiffy wrap logic (as if anyone would still be running my
> patch in 50 days :P).
>
> Long sleepers were reclassified as idle according to the new exponential
> logic.
>
> If you test, please note this works better at 1000Hz.
Currently testing on 2.5.73-mm2, with both patches (patch-O1int and
patch-granularity) plus HZ=1000. The result is quite impressive. Under
load, X still suffer a little lag and behaves a little worse than the
combo patch from Mike Galbraith + Ingo, but now XMMS doesn't skip even
when clicking a link inside Evolution.
Please, let me more time to work with this new patched kernel a little
bit more to see if I can find any strange issues.
On Sat, 2003-06-28 at 18:30, Con Kolivas wrote:
> On Sat, 28 Jun 2003 15:16, Con Kolivas wrote:
> > For my sins I've included what I thought was necessary for this patch.
> >
> > The interactivity for tasks is based on the sleep avg accumulated divided
> > by the running time of the task. However since the accumulated time is not
> > linear with time it now works on the premise that running time is an
> > exponential function entirely. Pat Erley was the genius who implemented
> > this simple exponential function in surprisingly low overhead integer
> > maths.
> >
> > Also added was some jiffy wrap logic (as if anyone would still be running
> > my patch in 50 days :P).
> >
> > Long sleepers were reclassified as idle according to the new exponential
> > logic.
> >
> > If you test, please note this works better at 1000Hz.
> >
> > Attached also is my bastardised version of Ingo's timeslice granularity
> > patch. This round robins tasks on the active array every 10ms, which
> > _might_ be detrimental in throughput applications but has not been
> > benchmarked. However for desktops it does wonders to smoothing out the
> > jerkiness of X and I highly recommend using this in combination with the
> > O1int patch.
> >
> > This is very close to all the logic I wanted to implement. It might need
> > more tuning... Note parent penalty, child penalty and exit weight
> > (uppercase) no longer do anything.
> >
> > Please test and comment.
> >
> > Con
> >
> > P.S. In the words of Zwane - there is always a corner case. Corner case I
> > think I still need to tackle is the application that spins madly waiting
> > for it's child to start, and in the process it is the parent that is
> > starving the child by being higher priority than it. This seems to be a
> > coding style anomaly brought out by the scheduler.
>
> And just for good measure here is the latest with a slight addition that helps
> X smoothness over time. It gives the sleep_avg a little headroom so it
> doesn't drop from interactive as easily with bursts of cpu activity.
OK, now testing this one :-)
2.5.73-mm2 + latest patch-O1int + patch-granularity + 1000HZ...
Feels a little bit better than the previous one. X under load is
smoother. This is starting to get interesting ;-)
I made a small error when I sent Con a piece of magic I wrote up to help the sleep period.
what it says right now:
/kernel/sched.c around line 325
sleep_period = (sleep_period *
17 * sleep_period / ((17 * sleep_period / (5 * tau) + 2) * 5 * tau));
----------------------------------------------------------^
it should be:
sleep_period = (sleep_period *
17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
--------------------------------------------------------------^
stupid parenthesis.
a little background. what this essentially is is a taylor approximation of the function ln(66x+1) normalized. ln(66x+1) happens to do a great job oas a weighting function on the range of 0 to 1, and because the input only happens to range from 0 to 1, only 2 terms were needed to do a 'good enough' job.
Pat
--
On Sat, 2003-06-28 at 17:26, pat erley wrote:
> I made a small error when I sent Con a piece of magic I wrote up to help the sleep period.
>
> what it says right now:
>
> /kernel/sched.c around line 325
>
>
> sleep_period = (sleep_period *
> 17 * sleep_period / ((17 * sleep_period / (5 * tau) + 2) * 5 * tau));
> ----------------------------------------------------------^
>
> it should be:
>
> sleep_period = (sleep_period *
> 17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
> --------------------------------------------------------------^
>
> stupid parenthesis.
>
> a little background. what this essentially is is a taylor approximation of the function ln(66x+1) normalized. ln(66x+1) happens to do a great job oas a weighting function on the range of 0 to 1, and because the input only happens to range from 0 to 1, only 2 terms were needed to do a 'good enough' job.
>
> Pat
I did your correction and I got a kernel panic(attempting to kill init)
on boot. It didn't flushed to disk, so it isn't attached, but it panics
at effective_prio+0xcc/0xe0.
With objdump I could see it traps a division by 0:
cc: f7 fb idiv %ebx
I remember cleary %ebx being 0 on the panic report.
And I tracked down and the code is on this else in effective_prio:
----------- sched.c 341-----------------
else {
sleep_period = (sleep_period *
17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
if (!sleep_period)
return p->static_prio;
}
--------------------------------------
I don't have the time now to track this further today, but what happens
if sleep_period is too small and tau is too big?
Could this (17 * sleep_period / (5 * tau + 2) give 0 and so a division
by 0?
abs
Roberto
On Sun, 29 Jun 2003 03:22, Martin Schlemmer wrote:
> On Sat, 2003-06-28 at 18:30, Con Kolivas wrote:
> > On Sat, 28 Jun 2003 15:16, Con Kolivas wrote:
> > > For my sins I've included what I thought was necessary for this patch.
> >
> > And just for good measure here is the latest with a slight addition that
> > helps X smoothness over time. It gives the sleep_avg a little headroom so
> > it doesn't drop from interactive as easily with bursts of cpu activity.
>
> Have not tried this one, but previous had the same issues on this HT
> box. Reverted the two patches, and I have no mouse jerkyness or laggy
> redraw of windows.
>
> Anyhow, will it be a wise move to try and get a scheduler that works
> fine for both UP and SMP ?
Indeed. I wasn't trying to make a UP only patch, and it was not finished
(nothing ever is really).
Con
On Sun, 29 Jun 2003 08:45, Roberto Orenstein wrote:
> On Sat, 2003-06-28 at 17:26, pat erley wrote:
> > I made a small error when I sent Con a piece of magic I wrote up to help
> > the sleep period.
> >
> > what it says right now:
> >
> > /kernel/sched.c around line 325
> >
> >
> > sleep_period = (sleep_period *
> > 17 * sleep_period / ((17 * sleep_period / (5 * tau) + 2) * 5 * tau));
> > ----------------------------------------------------------^
> >
> > it should be:
> >
> > sleep_period = (sleep_period *
> > 17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
> > --------------------------------------------------------------^
> >
> > stupid parenthesis.
> >
> > a little background. what this essentially is is a taylor approximation
> > of the function ln(66x+1) normalized. ln(66x+1) happens to do a great
> > job oas a weighting function on the range of 0 to 1, and because the
> > input only happens to range from 0 to 1, only 2 terms were needed to do a
> > 'good enough' job.
> >
> > Pat
>
> I did your correction and I got a kernel panic(attempting to kill init)
> on boot. It didn't flushed to disk, so it isn't attached, but it panics
> at effective_prio+0xcc/0xe0.
> With objdump I could see it traps a division by 0:
> cc: f7 fb idiv %ebx
>
> I remember cleary %ebx being 0 on the panic report.
> And I tracked down and the code is on this else in effective_prio:
> ----------- sched.c 341-----------------
> else {
> sleep_period = (sleep_period *
> 17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
> if (!sleep_period)
> return p->static_prio;
> }
> --------------------------------------
>
> I don't have the time now to track this further today, but what happens
> if sleep_period is too small and tau is too big?
> Could this (17 * sleep_period / (5 * tau + 2) give 0 and so a division
> by 0?
This will give a divide by zero.
I will put together a new patch soon with this correction and appropriate
logic.
Con
On Sun, 29 Jun 2003 11:32, Con Kolivas wrote:
> On Sun, 29 Jun 2003 08:45, Roberto Orenstein wrote:
> > On Sat, 2003-06-28 at 17:26, pat erley wrote:
> > > I made a small error when I sent Con a piece of magic I wrote up to
> > > help the sleep period.
> > >
> > > what it says right now:
> > >
> > > /kernel/sched.c around line 325
> > >
> > >
> > > sleep_period = (sleep_period *
> > > 17 * sleep_period / ((17 * sleep_period / (5 * tau) + 2) * 5 * tau));
> > > ----------------------------------------------------------^
> > >
> > > it should be:
> > >
> > > sleep_period = (sleep_period *
> > > 17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
> > > --------------------------------------------------------------^
> > >
> > > stupid parenthesis.
> > >
> > > a little background. what this essentially is is a taylor
> > > approximation of the function ln(66x+1) normalized. ln(66x+1) happens
> > > to do a great job oas a weighting function on the range of 0 to 1, and
> > > because the input only happens to range from 0 to 1, only 2 terms were
> > > needed to do a 'good enough' job.
> > >
> > > Pat
> >
> > I did your correction and I got a kernel panic(attempting to kill init)
> > on boot. It didn't flushed to disk, so it isn't attached, but it panics
> > at effective_prio+0xcc/0xe0.
> > With objdump I could see it traps a division by 0:
> > cc: f7 fb idiv %ebx
> >
> > I remember cleary %ebx being 0 on the panic report.
> > And I tracked down and the code is on this else in effective_prio:
> > ----------- sched.c 341-----------------
> > else {
> > sleep_period = (sleep_period *
> > 17 * sleep_period / ((17 * sleep_period / (5 * tau + 2)) * 5 * tau));
> > if (!sleep_period)
> > return p->static_prio;
> > }
> > --------------------------------------
> >
> > I don't have the time now to track this further today, but what happens
> > if sleep_period is too small and tau is too big?
> > Could this (17 * sleep_period / (5 * tau + 2) give 0 and so a division
> > by 0?
>
> This will give a divide by zero.
>
> I will put together a new patch soon with this correction and appropriate
> logic.
Further inspection of this code shows to me that the current version will do
the job adequately. The full function Pat put together is a little more
complicated and unfortunately falls over with integer logic. This one is a
reasonable enough approximation.
So to summarise, if you still wish to test/use this patch, continue using the
patch as posted unmodified called:
patch-O1int-0306290223
Con
Summary:
A patch to reduce audio skipping and X jerking under load.
It's looking seriously like I'm talking to myelf here, but just in case there
are lurkers testing this patch, there's a big bug that made it think jiffy
wraparound was occurring so interactive tasks weren't receiving the boost
they deserved. Here is a patch with the fix in.
How to use if you're still thinking of testing:
Use with Hz 1000, and use the granularity patch I posted as well for smoothing
X off.
Con
Con Kolivas <[email protected]> wrote:
>
> It's looking seriously like I'm talking to myelf here
Let me know when it is sufficiently cooked and I'll give it a run
in -mm.
We obviously have issues in there still, and it is good that you
guys are working it.
Greetings,
At 03:35 PM 6/30/2003 +1000, Con Kolivas wrote:
>Summary:
>A patch to reduce audio skipping and X jerking under load.
I took it out for a quick spin. It kills thud graveyard dead. That's the
good news, now for the bad ;-) With a make -j5 running, kasteroids
stutters enough to be pretty annoying. The patched kernel is making
booboos wrt cc1's priority often enough to nail kasteroids pretty
hard. The mouse pointer also jerks around quite a bit,...
>It's looking seriously like I'm talking to myelf here, but just in case there
>are lurkers testing this patch, there's a big bug that made it think jiffy
>wraparound was occurring so interactive tasks weren't receiving the boost
>they deserved. Here is a patch with the fix in.
>
>How to use if you're still thinking of testing:
>Use with Hz 1000, and use the granularity patch I posted as well for
>smoothing
>X off.
...but I'm not using that, because I wanted to see the pure effects of this
patch.
-Mike
On Mon, 2003-06-30 at 07:35, Con Kolivas wrote:
> A patch to reduce audio skipping and X jerking under load.
Can't make XMMS skip audio with "while true; do a = 2; done" while
playing moving windows under an X session.
> It's looking seriously like I'm talking to myelf here, but just in case there
> are lurkers testing this patch, there's a big bug that made it think jiffy
> wraparound was occurring so interactive tasks weren't receiving the boost
> they deserved. Here is a patch with the fix in.
Well, you're not talking to yourself. We're listening and testing:
2.5.73-mm2 + patch-O1int + patch-granularity + patch-1000HZ. With this
new version of the patch, the mouse cursor jumpiness has returned again,
altough in much less extent than in previous versions: it's more
difficult to reproduce, but it's present just when logging onto my KDE
session on a Red Hat Linux 9 box. For the rest of the session, it's
pretty hard difficult to make the mouse cursor to turn jumpy.
> How to use if you're still thinking of testing:
> Use with Hz 1000, and use the granularity patch I posted as well for smoothing
> X off.
Under heavy load (3 simulatenous consoles doing while true; do a=2;
done), X feels smooth, but moving windows aggresively, makes X go jerky
for a few seconds and some process do starve a little when repainting.
Anyways, at a first glance, it looks really good :-)
On Monday 30 June 2003 07:35, Con Kolivas wrote:
Hi Con,
> A patch to reduce audio skipping and X jerking under load.
> It's looking seriously like I'm talking to myelf here, but just in case
> there are lurkers testing this patch, there's a big bug that made it think
> jiffy wraparound was occurring so interactive tasks weren't receiving the
> boost they deserved. Here is a patch with the fix in.
> How to use if you're still thinking of testing:
> Use with Hz 1000, and use the granularity patch I posted as well for
> smoothing X off.
using 2.5.73-mm2, 1000HZ, patch-O1int-0306301522, patch-granularity-0306271314
"make -j16 bzImage modules" of a 2.5.73-mm2 tree makes XMMS skip easily, X is
not very smooth, mouse jumps, X is sometimes not accepting anything for 5-10
seconds every 1-2 minutes, everything freezes, also XMMS, Kmail freezes, an
Xterm needs ~40 seconds to open. If the machine is totally idle, Kmail
freezes also for ~5 seconds. Tried running X with 0, -1 and -11 w/o much
difference.
I still like Felipe's O(1) patch.
Machine: Celeron 1,3GHz, 512MB RAM, 512MB SWAP, IDE (UDMA100), ext3fs, X4.3,
WindowMaker.
Please, can we invite Ingo to this thread? I think it is now _really_ the time
to get this fixed up :)
ciao, Marc
Marc-Christian Petersen <[email protected]> wrote:
>
> "make -j16 bzImage modules" of a 2.5.73-mm2 tree makes XMMS skip easily
Well it would. Try not to do that. We shouldn't optimise
for things which basically nobody would do.
`make -j2' would be more interesting.
On Mon, 30 Jun 2003 17:57, Mike Galbraith wrote:
> Greetings,
>
> At 03:35 PM 6/30/2003 +1000, Con Kolivas wrote:
> >Summary:
> >A patch to reduce audio skipping and X jerking under load.
>
> I took it out for a quick spin. It kills thud graveyard dead. That's the
> good news, now for the bad ;-) With a make -j5 running, kasteroids
> stutters enough to be pretty annoying. The patched kernel is making
> booboos wrt cc1's priority often enough to nail kasteroids pretty
> hard. The mouse pointer also jerks around quite a bit,...
Consider it not optimised yet. The workings are still evolving but are now
close. It errs on the too-easy to get a bonus in the early ms after an app
has started at the moment.
>
> >It's looking seriously like I'm talking to myelf here, but just in case
> > there are lurkers testing this patch, there's a big bug that made it
> > think jiffy wraparound was occurring so interactive tasks weren't
> > receiving the boost they deserved. Here is a patch with the fix in.
> >
> >How to use if you're still thinking of testing:
> >Use with Hz 1000, and use the granularity patch I posted as well for
> >smoothing
> >X off.
>
> ...but I'm not using that, because I wanted to see the pure effects of this
> patch.
Good point. If it's going to be developed properly it should only include what
is likely to be used with it.
Con
On Monday 30 June 2003 11:47, Andrew Morton wrote:
Hi Andrew,
> > "make -j16 bzImage modules" of a 2.5.73-mm2 tree makes XMMS skip easily
> Well it would. Try not to do that. We shouldn't optimise
> for things which basically nobody would do.
> `make -j2' would be more interesting.
Well, it shouldn't *imho*. And it is possible. Currently I am running
2.4.20-wolk4.3 and I do "make -j32 bzImage modules" and I cannot make XMMS
skip doesn't matter what I do, it is not possible. Even X is smooth, kmail
does not freeze, an Xterm needs ~4 seconds to open.
My tree uses the O(1) from Andrea including the fixes.
Now I've tried your suggestion, "make -j2" with .73-mm2 + the mentioned
patches. Three skips during the whole compilation (bzImage modules).
ciao, Marc
Marc-Christian Petersen <[email protected]> wrote:
>
> Now I've tried your suggestion, "make -j2" with .73-mm2 + the mentioned
> patches. Three skips during the whole compilation (bzImage modules).
And what happens without the scheduler patches?
At 08:16 PM 6/30/2003 +1000, Con Kolivas wrote:
>Consider it not optimised yet. The workings are still evolving but are now
>close. It errs on the too-easy to get a bonus in the early ms after an app
>has started at the moment.
Yeah, that's the way it looks from here too. It's getting it right more
often than wrong, that's encouraging.
-Mike
At 11:39 AM 6/30/2003 +0200, Marc-Christian Petersen wrote:
>Please, can we invite Ingo to this thread? I think it is now _really_ the
>time
>to get this fixed up :)
The giants all seem to be busy... are munchkins stackable? ;-)
>At 11:39 AM 6/30/2003 +0200, Marc-Christian Petersen wrote:
>>Please, can we invite Ingo to this thread? I think it is now _really_ the
>>time
>>to get this fixed up :)
>
>The giants all seem to be busy... are munchkins stackable? ;-)
Ok this munchkin has some more to contribute.
Here is the next patch which shows a large improvement. Gone is the
unnecessary exponential function (sorry Pat it was fun), and now the patch
will start calculating interactivity from the first time an application is
activated.
This takes away the X jerkiness evident in the previous patches (yes I do
believe you MCP). No granularity patch is needed either.
Please test the bejeesus out of this one; MCP your test case is the most
valuable.
Con
On Mon, 30 Jun 2003, Mike Galbraith wrote:
> At 11:39 AM 6/30/2003 +0200, Marc-Christian Petersen wrote:
>
> >Please, can we invite Ingo to this thread? I think it is now _really_ the
> >time
> >to get this fixed up :)
>
> The giants all seem to be busy... are munchkins stackable? ;-)
Ingo, when you come back from Mars :) ... what has been changed from the
very first versions of 2.5.x ? I was able to run unrealistic `make -j`
(among other crap) and still have a liquid desktop back then ...
- Davide
On Monday 30 June 2003 12:17, Andrew Morton wrote:
Hi Andrew,
> > Now I've tried your suggestion, "make -j2" with .73-mm2 + the mentioned
> > patches. Three skips during the whole compilation (bzImage modules).
> And what happens without the scheduler patches?
Not countable XMMS skips (read: too many)
ciao, Marc
On Monday 30 June 2003 15:38, Con Kolivas wrote:
Moin Con,
> Ok this munchkin has some more to contribute.
hehe.
> Here is the next patch which shows a large improvement. Gone is the
> unnecessary exponential function (sorry Pat it was fun), and now the patch
> will start calculating interactivity from the first time an application is
> activated.
nice.
> This takes away the X jerkiness evident in the previous patches (yes I do
> believe you MCP). No granularity patch is needed either.
ok.
> Please test the bejeesus out of this one; MCP your test case is the most
> valuable.
tyvm :) I'll give it a try in ~30 mins.
ciao, Marc