Controlling scheduling in Concurrent Haskell

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Controlling scheduling in Concurrent Haskell

Simon Peyton Jones
| Given that actually controlling priorities is not an option, adding
| blocking like that makes sense.  One can make a ring buffer instead of
a

Concerning priorities and scheduling (which affect both this shootout
thread, and perhaps Joel's timeleak program), one can take two
approaches

1.  Ask more of the runtime system; e.g. add thread priorities
2.  Program up a solution

The merit of (1) is that you get an "automatic" solution.  The problem
is that it might not be the right solution for your problem.  Whereas
(2) will fit your problem, but is less convenient.

Even the first paper on Concurrent Haskell discussed (2), in Section 4
"Control over scheduling".  
http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/p
apers/concurrent-haskell.ps.gz

Just to give an example, suppose you have zillions of threads, but you
want to ensure that at most 10 of them are running simultaneously else
their time slices are too spread out.  Just use a quantity semaphore
(QSem, discussed in the "Concurrent Haskell" paper).  Each thread grabs
permission from the semaphore before doing its work, and puts it back
when done.

How about fairness?  As Simon mentioned, MVars *do* have an undocumented
fairness property; waiting threads are serviced in
first-come-first-served order.   You'd have to check the QSem code, but
I believe that means that threads will be dealt with
first-come-first-served order for the quantity semaphore.  We should
probably document this property of MVars, and document fairness
guarantees of abstractions such as QSem.

| If 4 threads block trying to take an MVar, and a 5th thread puts a
value
| in the MVar, then *exactly one* of the 4 blocked threads is woken up
and
| scheduled to run.
|
| If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread
| commits a change to that TMVar, then *all 4 threads* are woken up and
| rescheduled.  This is what the Apache httpd server folks called the
| "thundering herd" problem when many processes are blocked waiting on
| socket 80.

Yes, that's precisely correct.  MVars guarantee a single wake-up,
whereas STM does not.  Again, this is a property that it'd be good to
document.


Of course none of this helps if you simply have too much work to do.  If
you have 100 threads, each with 1s of processing to do, then no amount
of fancy scheduling will get this done in less than 100s.

But I thought I'd mention the possibility of doing scheduling
explicitly.  It's often not hard, and has the property that it's more
robust to variations in the implementation.

Simon

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Controlling scheduling in Concurrent Haskell

haskell-2
I have a clarification below:

Simon Peyton-Jones wrote:

> | Given that actually controlling priorities is not an option, adding
> | blocking like that makes sense.  One can make a ring buffer instead of
> a
>
> Concerning priorities and scheduling (which affect both this shootout
> thread, and perhaps Joel's timeleak program), one can take two
> approaches
>
> 1.  Ask more of the runtime system; e.g. add thread priorities
> 2.  Program up a solution
>
> The merit of (1) is that you get an "automatic" solution.  The problem
> is that it might not be the right solution for your problem.  Whereas
> (2) will fit your problem, but is less convenient.
>
> Even the first paper on Concurrent Haskell discussed (2), in Section 4
> "Control over scheduling".  
> http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/p
> apers/concurrent-haskell.ps.gz
>
> Just to give an example, suppose you have zillions of threads, but you
> want to ensure that at most 10 of them are running simultaneously else
> their time slices are too spread out.  Just use a quantity semaphore
> (QSem, discussed in the "Concurrent Haskell" paper).  Each thread grabs
> permission from the semaphore before doing its work, and puts it back
> when done.

Starvation?

>
> How about fairness?  As Simon mentioned, MVars *do* have an undocumented
> fairness property; waiting threads are serviced in
> first-come-first-served order.   You'd have to check the QSem code, but
> I believe that means that threads will be dealt with
> first-come-first-served order for the quantity semaphore.  We should
> probably document this property of MVars, and document fairness
> guarantees of abstractions such as QSem.

Actually, what Simon Marlow said was:
>
> Furthermore, the thread to be woken up is always the first thread to
> block on the MVar.  That is, there's a kind of fairness built into MVars
> which isn't present in STM and TMVars.

Which is not FIFO fairness, it sound like "the first that came will be
the first to leave; the rest are shuffled".  Chorus: this should
possibly be documented.

The point of the Channel -> Ch optimization was that removing guarantees
sometimes improves speed.  The only way to get more guarantees without a
speed hit could be if the run-time system always imposes them anyway.
But since there is value in speed, making module *.MVar and *.MVar.Fair
might be interesting (similar for TMVar).

>
> | If 4 threads block trying to take an MVar, and a 5th thread puts a
> value
> | in the MVar, then *exactly one* of the 4 blocked threads is woken up
> and
> | scheduled to run.
> |
> | If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread
> | commits a change to that TMVar, then *all 4 threads* are woken up and
> | rescheduled.  This is what the Apache httpd server folks called the
> | "thundering herd" problem when many processes are blocked waiting on
> | socket 80.
>
> Yes, that's precisely correct.  MVars guarantee a single wake-up,
> whereas STM does not.  Again, this is a property that it'd be good to
> document.

Well, it is derivable from existing documentation, but it could be made
clearer.

> Of course none of this helps if you simply have too much work to do.  If
> you have 100 threads, each with 1s of processing to do, then no amount
> of fancy scheduling will get this done in less than 100s.

Of course

> But I thought I'd mention the possibility of doing scheduling
> explicitly.  It's often not hard, and has the property that it's more
> robust to variations in the implementation.
>
> Simon

Using QSem/QSemN for scheduling will not work well if there is
starvation.  That really really should be documented: whether or not
starvation is possible, regardless of other fairness.

Other documentation request: does "newQSem" create it with a quantity of
0 or 1 ?
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-QSem.html

Traditional (non-STM) locking code is very tricky and depends on all
these guarantees.  If something is not-guaranteed then it should be
explicitly documented as "you cannot depend on it".

--
Chris
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe