[Haskell-cafe] 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