Scheduler improvements

classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Gregor Best
Hi Alexandre,

> [...]
> This change is unclear for me; AFAIU, it removes the mechanism
> which makes processes wake up with a priority depending on what  
> they are blocked on.
> [...]

Where do you see that? The code I removed/changed simply calulated the queue from
which to remove `p` and removed it from there (similar for insertion). That needed
to be changed to modify the RB tree used as a new runqueue.

> [...]
> For instance processes waking up from poll(2) or audio read/write
> won't be prioritized any longer. If so, this would hurt audio and
> other interactive processes but would improve cpu-intesive
> bloatware.
> [...]

They weren't prioritised with the old version of this code either.

> [...]
> this change is unrelated to the rest isn't it?
> [...]

Yes, it is. I changed it because 100ms time slices felt a bit too large,
but the rest of the patch will of course work without this bit.

Thanks for taking your time to look at this :)

--
    Gregor Best

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Gregor Best
In reply to this post by Mark Kettenis
> [...]
> I don't think changing the idle loop like this is ok.  You want to
> continue checking whether the runqueue is empty in between
> cpu_idle_enter() and cpu_idle_leave().
> [...]

Fair point. I'll change that :)

--
    Gregor Best

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Ville Valkonen
In reply to this post by Gregor Best
Hi,

Seems to be a bit snappier, though more thorough testing needed. Many web pages
became more usable after the patch (chrome as browser) and some gains in
desktop too. System is amd64 @ Intel(R) Core(TM)2 Duo CPU T5870 @ 2.00GHz and
4G RAM.

--
cheers,
Ville

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Marc Espie-2
In reply to this post by Gregor Best
log2 should probably be scrapped, since you're reinventing ffs.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Christiano F. Haesbaert
On 8 October 2012 11:24, Marc Espie <[hidden email]> wrote:
> log2 should probably be scrapped, since you're reinventing ffs.
>

That is actually my code, back then I failed at finding an ffs.

I'll try to have a look at the code this week.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Alexandre Ratchov-2
In reply to this post by Gregor Best
On Sat, Oct 06, 2012 at 10:38:34PM +0200, Gregor Best wrote:

> Hi Alexandre,
>
> > [...]
> > This change is unclear for me; AFAIU, it removes the mechanism
> > which makes processes wake up with a priority depending on what  
> > they are blocked on.
> > [...]
>
> Where do you see that? The code I removed/changed simply calulated the queue from
> which to remove `p` and removed it from there (similar for insertion). That needed
> to be changed to modify the RB tree used as a new runqueue.
>
> > [...]
> > For instance processes waking up from poll(2) or audio read/write
> > won't be prioritized any longer. If so, this would hurt audio and
> > other interactive processes but would improve cpu-intesive
> > bloatware.
> > [...]
>
> They weren't prioritised with the old version of this code either.
>

AFAIU, when a process waits for an event (with tsleep(9)), it
provides the priority of the event it's waiting for (eg an audio
interrupt). When the event occurs, the process is put in the
runnable queue calculated from the priority. This way, interactive
processes (i.e. waiting for external events) are prioritized during
the event processing.

This mechanism ensures audio and midi are usable without having to
manually tweak priorities. Furthermore, priorities changed
depending on what the process is doing.

The most notable exception to above "rule" is the poll(2)
implementation, which still ignores priorities; it may need to be
fixed one day, but this is not the most urgent problem hurting
interactive processes.
[A
-- Alexandre

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Christiano F. Haesbaert
On Oct 8, 2012 6:33 PM, "Alexandre Ratchov" <[hidden email]> wrote:

>
> On Sat, Oct 06, 2012 at 10:38:34PM +0200, Gregor Best wrote:
> > Hi Alexandre,
> >
> > > [...]
> > > This change is unclear for me; AFAIU, it removes the mechanism
> > > which makes processes wake up with a priority depending on what
> > > they are blocked on.
> > > [...]
> >
> > Where do you see that? The code I removed/changed simply calulated the
queue from
> > which to remove `p` and removed it from there (similar for insertion).
That needed

> > to be changed to modify the RB tree used as a new runqueue.
> >
> > > [...]
> > > For instance processes waking up from poll(2) or audio read/write
> > > won't be prioritized any longer. If so, this would hurt audio and
> > > other interactive processes but would improve cpu-intesive
> > > bloatware.
> > > [...]
> >
> > They weren't prioritised with the old version of this code either.
> >
>
> AFAIU, when a process waits for an event (with tsleep(9)), it
> provides the priority of the event it's waiting for (eg an audio
> interrupt). When the event occurs, the process is put in the
> runnable queue calculated from the priority. This way, interactive
> processes (i.e. waiting for external events) are prioritized during
> the event processing.
>
> This mechanism ensures audio and midi are usable without having to
> manually tweak priorities. Furthermore, priorities changed
> depending on what the process is doing.
>
> The most notable exception to above "rule" is the poll(2)
> implementation, which still ignores priorities; it may need to be
> fixed one day, but this is not the most urgent problem hurting
> interactive processes.
> [A
> -- Alexandre
>

Ratchov is correct, when a process sleeps you specify the priority you
should have when waking up. I think george was referring to the old version
of his code.

The 4.4 bsd scheduler relies heavily on these priority boosts, i still
didnt have a look at George's code, but an equivalent mechanism is usually
needed. On cfs scheduling for example the processes forces a new delta
calculation and gets a fraction proportional to all other runnables
processes.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Gregor Best
In reply to this post by Alexandre Ratchov-2
On Mon, Oct 08, 2012 at 06:28:53PM +0200, Alexandre Ratchov wrote:
> [...]
> AFAIU, when a process waits for an event (with tsleep(9)), it
> provides the priority of the event it's waiting for (eg an audio
> interrupt). When the event occurs, the process is put in the
> runnable queue calculated from the priority. This way, interactive
> processes (i.e. waiting for external events) are prioritized during
> the event processing.
> [...]

I haven't noticed any degradation in performance with media-stuff (quite
the contrary, actually), but you have a point. I'll change the
deadline-calculation to also take the sleep priority into account.
Thanks for the explanation :)

--
    Gregor Best

[demime 1.01d removed an attachment of type application/pgp-signature]

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Ted Unangst-6
In reply to this post by Gregor Best
On Mon, Oct 08, 2012 at 18:43, Christiano F. Haesbaert wrote:

> Ratchov is correct, when a process sleeps you specify the priority you
> should have when waking up. I think george was referring to the old version
> of his code.
>
> The 4.4 bsd scheduler relies heavily on these priority boosts, i still
> didnt have a look at George's code, but an equivalent mechanism is usually
> needed. On cfs scheduling for example the processes forces a new delta
> calculation and gets a fraction proportional to all other runnables
> processes.

I've wondered how effective (or more importantly, accurate) these
priorities are.  Maintenance has been somewhat haphazard, e.g., I have
no idea when the last use of PVFS was removed, but there aren't any
left except for the definition in param.h.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Marc Espie-2
In reply to this post by Gregor Best
On Sun, Oct 07, 2012 at 04:04:16PM +0200, Gregor Best wrote:
> > [...]
> > I don't think changing the idle loop like this is ok.  You want to
> > continue checking whether the runqueue is empty in between
> > cpu_idle_enter() and cpu_idle_leave().
> > [...]
>
> Fair point. I'll change that :)

Your diff doesn't pass userland compiles.
You're adding a dependency on tree.h in proc.h.

In kernel land on amd64, that's okay, since machine/param.h will pull
machine/cpu.h which pulls sys/sched.h which now pulls sys/tree.h,

but it definitely doesn't fly in userland... my build crashed & burned
in libc...

assuming that's okay (not usually a kernel guy), you can go include
sys/tree.h directly in proc.h...

Please, please, please, don't vanish into the woods for the next 6 months.

Try splitting up your diff and working them into pieces kernel hackers can
work with...

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler improvements

Gregor Best
On Mon, Oct 08, 2012 at 07:42:13PM +0200, Marc Espie wrote:

> [...]
> Your diff doesn't pass userland compiles.
> You're adding a dependency on tree.h in proc.h.
>
> In kernel land on amd64, that's okay, since machine/param.h will pull
> machine/cpu.h which pulls sys/sched.h which now pulls sys/tree.h,
>
> but it definitely doesn't fly in userland... my build crashed & burned
> in libc...
>
> assuming that's okay (not usually a kernel guy), you can go include
> sys/tree.h directly in proc.h...
> [...]

I think wrapping all the things that need sys/tree.h in #ifdef KERNEL
should do the trick since they don't really make sense in userland
anyway.

> Please, please, please, don't vanish into the woods for the next 6 months.
> [...]

Since I now have way more space time on my hands than before, that
should not be an issue anymore, don't worry :)

> Try splitting up your diff and working them into pieces kernel hackers can
> work with...
> [...]

I will. Actually, the diff is a bunch of seperate git commits on my
machine, so that shouldn't be too hard to do.

--
    Gregor Best

12