STM and fairness

[Simon Peyton-Jones]

| 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!

Simon