Scheduler hack for multi-threaded processes

classic Classic list List threaded Threaded
44 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Scheduler hack for multi-threaded processes

Martin Pieuchot
Applications using multiple threads often call sched_yield(2) to
indicate that one of the threads cannot make any progress because
it is waiting for a resource held by another one.

One example of this scenario is the _spinlock() implementation of
our librthread.  But if you look on https://codesearch.debian.net
you can find much more use cases, notably MySQL, PostgreSQL, JDK,
libreoffice, etc.

Now the problem with our current scheduler is that the priority of
a thread decreases when it is the "curproc" of a CPU.  So the threads
that don't run and sched_yield(2) end up having a higher priority than
the thread holding the resource.  Which means that it's really hard for
such multi-threaded applications to make progress, resulting in a lot of
IPIs numbers.
That'd also explain why if you have a more CPUs, let's say 4 instead
of 2, your application will more likely make some progress and you'll
see less sluttering/freezing.

So what the diff below does is that it penalizes the threads from
multi-threaded applications such that progress can be made.  It is
inspired from the recent scheduler work done by Michal Mazurek on
tech@.

I experimented with various values for "p_priority" and this one is
the one that generates fewer # IPIs when watching a HD video on firefox.
Because yes, with this diff, now I can.

I'd like to know if dereferencing ``p_p'' is safe without holding the
KERNEL_LOCK.

I'm also interested in hearing from more people using multi-threaded
applications.

Index: kern/sched_bsd.c
===================================================================
RCS file: /cvs/src/sys/kern/sched_bsd.c,v
retrieving revision 1.43
diff -u -p -r1.43 sched_bsd.c
--- kern/sched_bsd.c 9 Mar 2016 13:38:50 -0000 1.43
+++ kern/sched_bsd.c 19 Mar 2016 12:21:36 -0000
@@ -298,7 +298,16 @@ yield(void)
  int s;
 
  SCHED_LOCK(s);
- p->p_priority = p->p_usrpri;
+ /*
+ * If one of the threads of a multi-threaded process called
+ * sched_yield(2), drop its priority to ensure its siblings
+ * can make some progress.
+ */
+ if (TAILQ_FIRST(&p->p_p->ps_threads) == p &&
+    TAILQ_NEXT(p, p_thr_link) == NULL)
+ p->p_priority = p->p_usrpri;
+ else
+ p->p_priority = min(MAXPRI, p->p_usrpri * 2);
  p->p_stat = SRUN;
  setrunqueue(p);
  p->p_ru.ru_nvcsw++;

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Edd Barrett-3
On Sat, Mar 19, 2016 at 01:53:07PM +0100, Martin Pieuchot wrote:
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.

Works well here in firefox too.

Will run this diff for a few days and let you know if anything bad
happens.

--
Best Regards
Edd Barrett

http://www.theunixzoo.co.uk

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Todd Mortimer
In reply to this post by Martin Pieuchot
On Sat, Mar 19, 2016 at 01:53:07PM +0100, Martin Pieuchot wrote:
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.

Same result here: Video in firefox plays nicely with this patch, where
before it was choppy. Running amd64 in a 2xCPU VMware box.

Todd

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Miod Vallat
In reply to this post by Martin Pieuchot

> I'd like to know if dereferencing ``p_p'' is safe without holding the
> KERNEL_LOCK.

SCHED_LOCK is enough to access p_p->ps_threads,

The construct used to decide whether the process is multi-threaded
already appears twice in sys/kern¸ and your diff adds a third
instance. It is probably worth turning into a macro or an inline
function¸ to make sure there is no risk of the copies becoming
out-of-sync over time.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Philip Guenther-2
On Sat, Mar 19, 2016 at 9:18 AM, Miod Vallat <[hidden email]> wrote:
>
>> I'd like to know if dereferencing ``p_p'' is safe without holding the
>> KERNEL_LOCK.
>
> SCHED_LOCK is enough to access p_p->ps_threads,

Uh, not quite.

p_p itself is immutable for the life of a thread and can be
dereferenced without locks.

p_p->ps_threads (and p_thr_link) can only be modified by threads in
this process.  The result is that the test here can't claim the
process is single-threaded when it's multi-threaded.  (An "is MT"
result can go stale if there's no locking and the only other thread in
the process exits, but that's generally not an issue.)

If you really need to walk the p_p->ps_threads list, then you
currently need the kernel lock to keep the threads in it from
disappearing.


> The construct used to decide whether the process is multi-threaded
> already appears twice in sys/kern¸ and your diff adds a third
> instance. It is probably worth turning into a macro or an inline
> function¸ to make sure there is no risk of the copies becoming
> out-of-sync over time.

I like this idea.  Note that it should be a "am the only thread" or
"do I have sibling threads" kind of predicate and not an "is this
arbitrary process singled/multi-threaded?" test.


Philip Guenther

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Daniel Bolgheroni-3
In reply to this post by Martin Pieuchot
On Sat, Mar 19, 2016 at 01:53:07PM +0100, Martin Pieuchot wrote:
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.

YouTube on Firefox on ThinkPad T420: It's definitely better than before.
There is still very occasional, very very little image stuttering, but
doesn't break the audio or the flow anymore, which was very annoying.
Full screen works also.

Not related specifically to this patch, because it was happening before,
but: pausing a video does not work. The YouTube loading icon kicks in,
and even if the video returns, it's completely out of sync.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Christian Schulte
In reply to this post by Martin Pieuchot
The java based Netbeans IDE performs a lot of things in the background
using threads like indexing sources, downloading artifacts, unpacking
archives, compiling sources in addition to the normal java background
tasks like JIT compiling. This change approves UI responsiveness on my T60.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Christian Schulte
s/approves/improves/g

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Bob-2
In reply to this post by Martin Pieuchot

> I'm also interested in hearing from more people using multi-threaded
> applications.

I applied the patch to my old core duo p7570 running CURRENT/amd64.
Firefox is more responsive and youtube videos, previously impossible to
watch, run smoothly, even in full screen. Sumultaneously did some photo
editing work in gimp, ran gigabyte sized file transfers with sftp and took
a CVS update on ports without any hiccups. Browsing in Firefox remained
smooth although I heard a few glitchs in audio playback when scrolling
while a busy page was still loading, with load average hovering around
2.5 with 58 processes and 138 threads at the time. Otherwise smooth
sailing, very nice.

Bob

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Juan Francisco Cantero Hurtado
In reply to this post by Martin Pieuchot
On Sat, Mar 19, 2016 at 01:53:07PM +0100, Martin Pieuchot wrote:

> Applications using multiple threads often call sched_yield(2) to
> indicate that one of the threads cannot make any progress because
> it is waiting for a resource held by another one.
>
> One example of this scenario is the _spinlock() implementation of
> our librthread.  But if you look on https://codesearch.debian.net
> you can find much more use cases, notably MySQL, PostgreSQL, JDK,
> libreoffice, etc.
>
> Now the problem with our current scheduler is that the priority of
> a thread decreases when it is the "curproc" of a CPU.  So the threads
> that don't run and sched_yield(2) end up having a higher priority than
> the thread holding the resource.  Which means that it's really hard for
> such multi-threaded applications to make progress, resulting in a lot of
> IPIs numbers.
> That'd also explain why if you have a more CPUs, let's say 4 instead
> of 2, your application will more likely make some progress and you'll
> see less sluttering/freezing.
>
> So what the diff below does is that it penalizes the threads from
> multi-threaded applications such that progress can be made.  It is
> inspired from the recent scheduler work done by Michal Mazurek on
> tech@.
>
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.
>
> I'd like to know if dereferencing ``p_p'' is safe without holding the
> KERNEL_LOCK.
>
> I'm also interested in hearing from more people using multi-threaded
> applications.

In the ffmpeg test case, the frames-per-second increased 25%. The only
modification in the kernel was your patch.

--
Juan Francisco Cantero Hurtado http://juanfra.info

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Miod Vallat
In reply to this post by Philip Guenther-2

> p_p->ps_threads (and p_thr_link) can only be modified by threads in
> this process.  The result is that the test here can't claim the
> process is single-threaded when it's multi-threaded.  (An "is MT"
> result can go stale if there's no locking and the only other thread in
> the process exits, but that's generally not an issue.)
>
> If you really need to walk the p_p->ps_threads list, then you
> currently need the kernel lock to keep the threads in it from
> disappearing.

The proposed diff only peeks at the head of the list. But you're right,
the other code paths doing this (peek instead of full traversal) seem to
be under KERNEL_LOCK already.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Jonathan Matthew-4
In reply to this post by Martin Pieuchot
On Sat, Mar 19, 2016 at 01:53:07PM +0100, Martin Pieuchot wrote:

> Applications using multiple threads often call sched_yield(2) to
> indicate that one of the threads cannot make any progress because
> it is waiting for a resource held by another one.
>
> One example of this scenario is the _spinlock() implementation of
> our librthread.  But if you look on https://codesearch.debian.net
> you can find much more use cases, notably MySQL, PostgreSQL, JDK,
> libreoffice, etc.
>
> Now the problem with our current scheduler is that the priority of
> a thread decreases when it is the "curproc" of a CPU.  So the threads
> that don't run and sched_yield(2) end up having a higher priority than
> the thread holding the resource.  Which means that it's really hard for
> such multi-threaded applications to make progress, resulting in a lot of
> IPIs numbers.
> That'd also explain why if you have a more CPUs, let's say 4 instead
> of 2, your application will more likely make some progress and you'll
> see less sluttering/freezing.
>
> So what the diff below does is that it penalizes the threads from
> multi-threaded applications such that progress can be made.  It is
> inspired from the recent scheduler work done by Michal Mazurek on
> tech@.
>
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.
>
> I'd like to know if dereferencing ``p_p'' is safe without holding the
> KERNEL_LOCK.
>
> I'm also interested in hearing from more people using multi-threaded
> applications.


The benefits for web browsers seem to have been well covered, so I thought
I'd try mariadb out a bit.  On the second-crappiest amd64 box I still run
(a sun v20z) I get significantly better results with the mysql tests in
sysbench using the configuration specified here:
https://mariadb.com/kb/en/mariadb/sysbench-benchmark-setup/

On the select_random_points test, for example, with 3 threads (on a 2 cpu box)
running for 5 minutes, across 4 different runs:
before:
    read/write requests:                 554817 (1849.39 per sec.)
    read/write requests:                 582590 (1941.96 per sec.)
    read/write requests:                 573752 (1912.50 per sec.)
    read/write requests:                 571679 (1905.59 per sec.)

after:
    read/write requests:                 661234 (2204.11 per sec.)
    read/write requests:                 647648 (2158.82 per sec.)
    read/write requests:                 649752 (2165.83 per sec.)
    read/write requests:                 642049 (2140.16 per sec.)

Not a real database performance test, but it at least shows that it helps
things other than browsers.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Norman Golisz-3
In reply to this post by Martin Pieuchot
Hi Martin,

On Sat Mar 19 2016 13:53, Martin Pieuchot wrote:
> I'm also interested in hearing from more people using multi-threaded
> applications.

your patch - just like Michal's - improves the situation a lot.

Watching videos (HD) fullscreen in a browser without stuttering - the
GUI stays responsive as well.

Thank you both!

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Erling Westenvik-2
On Sun, Mar 20, 2016 at 09:04:22PM +0100, Norman Golisz wrote:
> Hi Martin,
>
> On Sat Mar 19 2016 13:53, Martin Pieuchot wrote:
> > I'm also interested in hearing from more people using multi-threaded
> > applications.
>
> your patch - just like Michal's - improves the situation a lot.

For now I've only applied Martin's patch. Are there any reasons not to
apply both?
 
> Watching videos (HD) fullscreen in a browser without stuttering - the
> GUI stays responsive as well.

I'm kinda stunned here. For years I've been telling my girlfriend, my
friends and my children that I cannot watch all those funny YouTube
videos they have insisted on sending me. Of course there was always the
possibility of viewing them through smtube, minitube, youtube-dl and
whatnot, but ...  but no, those were really not "realtime" options.

Then now all of a sudden I can play Peppa Pig episodes for my youngest
one. Full screen. HD. Flawlessly. On my old dual core ThinkPad t500 with
"only" 4GB RAM. In Firefox on OpenBSD!!! Woah...

>
> Thank you both!
>

Seconded. At least as long as my work schedule won't suffocate as a
result of spending too much time watching vidoes...

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Amit Kulkarni-5
In reply to this post by Bob-2
On Sat, Mar 19, 2016 at 4:35 PM, Bob <[hidden email]> wrote:

>
> I'm also interested in hearing from more people using multi-threaded
>> applications.
>>
>
> I applied the patch to my old core duo p7570 running CURRENT/amd64.
> Firefox is more responsive and youtube videos, previously impossible to
> watch, run smoothly, even in full screen. Sumultaneously did some photo
> editing work in gimp, ran gigabyte sized file transfers with sftp and took
> a CVS update on ports without any hiccups. Browsing in Firefox remained
> smooth although I heard a few glitchs in audio playback when scrolling
> while a busy page was still loading, with load average hovering around 2.5
> with 58 processes and 138 threads at the time. Otherwise smooth sailing,
> very nice.
>
> Bob
>
>
+1. Previously, when I did a cvs update with original scheduler code, doing
the ports update the machine always froze solid while doing cvs update,
taking 3 minutes to recover. This time with Martin's patch, the freezing
period seems to have decreased quite a bit, although the freeze still
happens. Stefan's amap diff and Bob's VFS/UVM diff also seems to have a
made a difference.

Pentium G2020 2.9GHz dual core Ivy bridge 22nm... 8 GB RAM

IMHO, this patch should go in!!!!!

Thanks
Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Mark Kettenis
> From: Amit Kulkarni <[hidden email]>
> Date: Sun, 20 Mar 2016 17:57:49 -0500
>
> On Sat, Mar 19, 2016 at 4:35 PM, Bob <[hidden email]> wrote:
>
> >
> > I'm also interested in hearing from more people using multi-threaded
> >> applications.
> >>
> >
> > I applied the patch to my old core duo p7570 running CURRENT/amd64.
> > Firefox is more responsive and youtube videos, previously impossible to
> > watch, run smoothly, even in full screen. Sumultaneously did some photo
> > editing work in gimp, ran gigabyte sized file transfers with sftp and took
> > a CVS update on ports without any hiccups. Browsing in Firefox remained
> > smooth although I heard a few glitchs in audio playback when scrolling
> > while a busy page was still loading, with load average hovering around 2.5
> > with 58 processes and 138 threads at the time. Otherwise smooth sailing,
> > very nice.
> >
> > Bob
> >
> >
> +1. Previously, when I did a cvs update with original scheduler code, doing
> the ports update the machine always froze solid while doing cvs update,
> taking 3 minutes to recover. This time with Martin's patch, the freezing
> period seems to have decreased quite a bit, although the freeze still
> happens. Stefan's amap diff and Bob's VFS/UVM diff also seems to have a
> made a difference.
>
> Pentium G2020 2.9GHz dual core Ivy bridge 22nm... 8 GB RAM
>
> IMHO, this patch should go in!!!!!

No.  It's a hack. It points out aproblem that should be investigated
deeper.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Christian Schulte
Am 03/21/16 um 01:29 schrieb Mark Kettenis:
>
> No.  It's a hack. It points out aproblem that should be investigated
> deeper.
>

Maybe that's not only thread related. This diff only makes a difference
with multi-threaded processes. It may be worth considering looking at
the process level as well.

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Mark Kettenis
In reply to this post by Martin Pieuchot
> Date: Sat, 19 Mar 2016 13:53:07 +0100
> From: Martin Pieuchot <[hidden email]>
>
> Applications using multiple threads often call sched_yield(2) to
> indicate that one of the threads cannot make any progress because
> it is waiting for a resource held by another one.
>
> One example of this scenario is the _spinlock() implementation of
> our librthread.  But if you look on https://codesearch.debian.net
> you can find much more use cases, notably MySQL, PostgreSQL, JDK,
> libreoffice, etc.
>
> Now the problem with our current scheduler is that the priority of
> a thread decreases when it is the "curproc" of a CPU.  So the threads
> that don't run and sched_yield(2) end up having a higher priority than
> the thread holding the resource.  Which means that it's really hard for
> such multi-threaded applications to make progress, resulting in a lot of
> IPIs numbers.
> That'd also explain why if you have a more CPUs, let's say 4 instead
> of 2, your application will more likely make some progress and you'll
> see less sluttering/freezing.
>
> So what the diff below does is that it penalizes the threads from
> multi-threaded applications such that progress can be made.  It is
> inspired from the recent scheduler work done by Michal Mazurek on
> tech@.
>
> I experimented with various values for "p_priority" and this one is
> the one that generates fewer # IPIs when watching a HD video on firefox.
> Because yes, with this diff, now I can.
>
> I'd like to know if dereferencing ``p_p'' is safe without holding the
> KERNEL_LOCK.
>
> I'm also interested in hearing from more people using multi-threaded
> applications.

This doesn't only change the sched_yield() behaviour, but also
modifies how in-kernel yield() calls behave for threaded processes.
That is probably not right.

> Index: kern/sched_bsd.c
> ===================================================================
> RCS file: /cvs/src/sys/kern/sched_bsd.c,v
> retrieving revision 1.43
> diff -u -p -r1.43 sched_bsd.c
> --- kern/sched_bsd.c 9 Mar 2016 13:38:50 -0000 1.43
> +++ kern/sched_bsd.c 19 Mar 2016 12:21:36 -0000
> @@ -298,7 +298,16 @@ yield(void)
>   int s;
>  
>   SCHED_LOCK(s);
> - p->p_priority = p->p_usrpri;
> + /*
> + * If one of the threads of a multi-threaded process called
> + * sched_yield(2), drop its priority to ensure its siblings
> + * can make some progress.
> + */
> + if (TAILQ_FIRST(&p->p_p->ps_threads) == p &&
> +    TAILQ_NEXT(p, p_thr_link) == NULL)
> + p->p_priority = p->p_usrpri;
> + else
> + p->p_priority = min(MAXPRI, p->p_usrpri * 2);
>   p->p_stat = SRUN;
>   setrunqueue(p);
>   p->p_ru.ru_nvcsw++;
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Douglas Ray
In reply to this post by Mark Kettenis
On 21/03/16 11:29 AM, Mark Kettenis wrote:
>> From: Amit Kulkarni <[hidden email]>
>> Date: Sun, 20 Mar 2016 17:57:49 -0500
...

>> +1. Previously, when I did a cvs update with original scheduler code, doing
>> the ports update the machine always froze solid while doing cvs update,
>> taking 3 minutes to recover. This time with Martin's patch, the freezing
>> period seems to have decreased quite a bit, although the freeze still
>> happens. Stefan's amap diff and Bob's VFS/UVM diff also seems to have a
>> made a difference.
>>
>> Pentium G2020 2.9GHz dual core Ivy bridge 22nm... 8 GB RAM
>>
>> IMHO, this patch should go in!!!!!
>
> No.  It's a hack. It points out aproblem that should be investigated
> deeper.
>

If it gives a significant performance improvement but is too distant
from a real solution, maybe it could be worth distributing in
package(s) form.

The team then has the option to actively promote it, or not; and
the package could be updated as new refinements are found.

Douglas

Reply | Threaded
Open this post in threaded view
|

Re: Scheduler hack for multi-threaded processes

Theo de Raadt
> >> IMHO, this patch should go in!!!!!
> >
> > No.  It's a hack. It points out aproblem that should be investigated
> > deeper.
> >
>
> If it gives a significant performance improvement but is too distant
> from a real solution, maybe it could be worth distributing in
> package(s) form.
>
> The team then has the option to actively promote it, or not; and
> the package could be updated as new refinements are found.

A package that modifies the kernel, RIGHT....

123