[Haskell-cafe] Re: Controlling scheduling in Concurrent Haskell

[Chris Kuklewicz]

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