STM and fairness
simonpj at microsoft.com
Fri Feb 29 15:06:10 EST 2008
| I'd like to know a bit about the STM implementation in GHC,
| specifically about how it tries to achieve fairness. I've been reading
| "Composable Memory Transactions" but it does not contain that much
| details on this specific matter. What I want to know boils down to
| this: what order are processes run which have been woken up from a
| call to retry?
Tim is the one who implemented this stuff, so I'm ccing him.
If threads queue up on a single MVar, it's obvious how to achieve fairness of a sort. Furthremore, if 100 threads are blocked on one MVar, the scheduler can wake up exactly one when the MVar is filled. With STM it's much less obvious.
First, a thread may block on a whole bunch of TVars; if any of them are changed, the thread should re-run. So there is no single list of threads to reverse or not reverse.
Second, if 100 threads are blocked on a TVar, t, waking up just one of them may not suffice -- it may read some more TVars and then retry again, re-blocking itself on t (plus some more). The only simple thing to do is to wake all of them up. In common situations (e.g. a buffer), we may wake up all 100 threads, only for 99 of them to lose the race and block again.
This arises from the fact that transactions do a wonderful thing, by letting you perform multiple operations atomically -- but that makes it harder to optimize.
All that said, you may well be right that one could do a better job of scheduling. For example, even though there may be lots of threads blocked on a TVar, and all must be made runnable, they could perhaps be run in the same order that they blocked, so the longest-blocked got to run first. I don't think we try to do that, but Tim would know.
By all means suggest a patch!
More information about the Glasgow-haskell-users