STM and fairness

[Josef Svenningsson]

Tim, Simon,

Thanks for your detailed descriptions. Much of my understanding was
confirmed. I'll see if I can send you a patch with my suggested fix as
soon as my teaching is over.

Thanks,

Josef

On Mon, Mar 3, 2008 at 2:03 PM, Tim Harris (RESEARCH)
<tharris at microsoft.com> wrote:
> Hi,
>
>  At the moment we don't make any particular effort to make threads runnable in some specific order when they are unblocked.  The current implementation is simply what was easiest to write.
>
>  If I remember rightly threads blocked on TVars will initially be "half-woken", putting them on the same run-queue as their waker and leaving the STM data structures intact.  When scheduled they will check whether or not the TVars' contents differ from the values that caused them to block: if the values are unchanged then a thread can block again without needing to build up wait queue structures.  In Simon's example of 100 threads blocked on a single-cell TVar buffer, this would mean 99 of them are validated and block again without needing to re-execute the rest of the transaction containing the TVar access.  This will probably happen within a single OS thread so these are lightweight thread switches within the GHC run time rather than 99 OS thread switches.
>
>  At some point it might be nice to look at using run-time feedback about how individual TVars are used.  I suspect that, looking at it dynamically, there are a few simple policies that would apply to most TVars (wake-all / wake-one) with the caveat that anything other than "wake-all" must eventually fall back to "wake-all" to preserve the intended semantics for "retry".
>
>  NB -- when thinking about a shared buffer built over TVars there's also the possibility that a non-blocked thread will consume the resource ahead of a blocked thread that has been woken.  As with programming with locks/condition-variables, avoiding this case would need an explicit queue of consumers to be maintained by the application (and symmetrically for producers).
>
>  In any case, running threads in something approximating the same order they blocked sounds sensible to me.  The lists of threads blocked on a TVar are doubly-linked (right?) so wouldn't need to be explicitly reversed.
>
>  Tim
>
>
>
>
>
>
>
>
>  -----Original Message-----
>  From: Simon Peyton-Jones
>  Sent: 29 February 2008 20:06
>  To: Josef Svenningsson; glasgow-haskell-users at haskell.org
>  Cc: Tim Harris (RESEARCH)
>  Subject: RE: STM and fairness
>
>  | 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
>