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) <[EMAIL PROTECTED]> 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@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 > _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
