STM and fairness

[Josef Svenningsson]

Sometime ago we had a discussion about the fairness of STM (some of it
quoted below) and the conclusion was that threads are woken up in the
wrong order when they are being unblocked from a TVar. The attached
patch fixes this. Could someone please apply it?

 Josef

PS. I sent this patch to glasgow-haskell-users a while ago but that's
obviously the wrong place and I think it got stuck in some filter.
Sorry about that.

 On Thu, Mar 6, 2008 at 12:39 AM, Josef Svenningsson
 <josef.svenningsson at gmail.com> wrote:
 > 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
 >  >
 >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch
Type: application/octet-stream
Size: 246116 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/cvs-ghc/attachments/20080409/cb3a3f6b/patch-0001.obj