Re: Concurrent MVars for Guile

[Mateusz Kowalczyk]

On 02/09/13 08:55, Mark H Weaver wrote:
> Hello all,
> 
> I've attached a preliminary implementation of MVars à la Concurrent
> Haskell for Guile.  I made a few small changes to the API to better
> match Scheme conventions, and added atomicity guarantees for 'read-mvar'
> and 'swap-mvar'.  I also added the interface 'try-read-mvar'.
> 
> Note that the fairness of this implementation relies upon the fairness
> of Guile's mutexes and condition variables, which I have not checked.
> 
> Comments and suggestions welcome.
> 
> I was thinking that maybe we should add something like this to core
> Guile.  What do you think?
> 
>      Mark
> 
> 

Hi all,

We've just had a little discussion in the #guile IRC channel about this
and I'm seeking some confirmation.

First of all, let's quickly outline something that Guilers might not be
familiar with: MVars are based on an important property of the GHC's
(GHC is the main Haskell compiler) thread scheduling mechanism, that is
its fairness policy. GHC uses a round-robin scheduler which means that
all threads will eventually get to run (although not with equal CPU
slices). A book by Simon Marlow, the person who has for many many years
been the main brain behind GHC's RTS says this:

“No thread can be blocked indefinitely on an MVar unless another thread
holds that MVar indefinitely”.[1]

Further down we find out the consequences of this guarantee: “A
consequence of the fairness implementation is that, when multiple
threads are blocked in takeMVar and another thread does a putMVar, only
one of the blocked threads becomes unblocked”. I think it's rather clear
why this property is desirable: we don't want to wake every thread
waiting on an MVar whenever we put into it or we'll have a huge
performance hit. As Simon himself says, these properties are why we
simply aren't using STM instead.

Keeping all this in mind, my questions are:

What's Guile's scheduling policy? Can we get a single wakeup and this
kind of fairness guarantee?

Unfortunately, Mark was not able to tell me what's the case. If this is
to make it into core language as Mark suggests, I think it's important
that it's first confirmed that the foundation on which MVars are built
upon is actually present in Guile. I'm posting on this list in an
attempt to find the person who knows how Guile's scheduler works and can
answer my questions.

Of course tests can be written and it can be eyed whether or not the
behaviour seems similar but I think a definitive ‘yes, we do this’ or
‘no, we don't do this’ is still necessary. In case that Guile does _not_
support such scheduling, I think it's important to note this in any
relevant documentation.

You can find examples of simple programs one could try to implement as
part of tests for this in Chapters 7 and 8 of [1].

Thanks

[1]: http://chimera.labs.oreilly.com/books/1230000000929
-- 
Mateusz K.

0x2ADA9A97.asc
Description: application/pgp-keys