[Haskell-cafe] Re: Controlling scheduling in Concurrent Haskell
haskell at list.mightyreason.com
Wed Jan 4 06:39:33 EST 2006
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
> Concerning priorities and scheduling (which affect both this shootout
> thread, and perhaps Joel's timeleak program), one can take two
> 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".
> 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.
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
> | in the MVar, then *exactly one* of the 4 blocked threads is woken up
> | 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
Well, it is derivable from existing documentation, but it could be made
> 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.
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 ?
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".
More information about the Haskell-Cafe