No atomic read on MVar?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

No atomic read on MVar?

p.k.f.holzenspies@utwente.nl
Dear GHCers,

I ran face first into an assumption I had made on MVar operations (in
Control.Concurrent); I had assumed there to be an atomic read (i.e.
non-destructive read, as opposed to destructive consume/take). The following
program illustrates what I had in mind.

testAtomic :: IO ()
testAtomic = do
        var <- newMVar 0
        putStrLn("Fork")
        forkIO (putMVar var 1 >> putStrLn "X")
        yield
        r1 <- readMVar var
        putStrLn("1")
        r2 <- takeMVar var
        putStrLn("2")
        r3 <- takeMVar var
        putStrLn("Result: " ++ show [r1,r2,r3])

If readMVar had been atomic, the result would be program termination with a
result of [0,0,1] being output. However, readMVar simply combines takeMVar
and putMVar, so the reading of r1 blocks after the takeMVar, because upon
taking the MVar, the blocked thread wakes up, puts 1 in var and prints X.
readMVar does not terminate for r1 (i.e. "1" is never printed).

I have now implemented my variable as a pair of MVars, one of which serves as
a lock on the other. Both for performance reasons and for deadlock analysis,
I would really like an atomic read on MVars, though. Does it exist? If not,
why not?

Regards,
Philip
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: No atomic read on MVar?

Simon Marlow-7
Philip K.F. Hölzenspies wrote:

>
> I ran face first into an assumption I had made on MVar operations (in
> Control.Concurrent); I had assumed there to be an atomic read (i.e.
> non-destructive read, as opposed to destructive consume/take). The following
> program illustrates what I had in mind.
>
> testAtomic :: IO ()
> testAtomic = do
> var <- newMVar 0
> putStrLn("Fork")
> forkIO (putMVar var 1 >> putStrLn "X")
> yield
> r1 <- readMVar var
> putStrLn("1")
> r2 <- takeMVar var
> putStrLn("2")
> r3 <- takeMVar var
> putStrLn("Result: " ++ show [r1,r2,r3])
>
> If readMVar had been atomic, the result would be program termination with a
> result of [0,0,1] being output. However, readMVar simply combines takeMVar
> and putMVar, so the reading of r1 blocks after the takeMVar, because upon
> taking the MVar, the blocked thread wakes up, puts 1 in var and prints X.
> readMVar does not terminate for r1 (i.e. "1" is never printed).
>
> I have now implemented my variable as a pair of MVars, one of which serves as
> a lock on the other. Both for performance reasons and for deadlock analysis,
> I would really like an atomic read on MVars, though. Does it exist? If not,
> why not?

It would be slightly annoying to implement, because it needs changes in
putMVar too: if there are blocked readMVars, then putMVar would have to
wake them all up.  Right now an MVar can only have one type of blocked
thread attached to it at a time, either takeMVars or putMVars, and putMVar
only has to wake a single thread.

Perhaps you should be using STM?

I suppose the answer to "why doesn't atomic readMVar exist" is that MVar is
intended to be a basic low-level synchronisation abstraction, on which you
can build larger abstractions (which you have indeed done).  On other other
hand, we're always interested in getting good value out of the building
blocks, so when there are useful operations we can add without adding
distributed complexity, that's often a good idea.  I'm not sure that atomic
readMVar falls into this category, though.

Cheers,
        Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: No atomic read on MVar?

David Menendez-2
In reply to this post by p.k.f.holzenspies@utwente.nl
On Mon, Nov 3, 2008 at 6:29 AM, Philip K.F. Hölzenspies
<[hidden email]> wrote:
>
> I have now implemented my variable as a pair of MVars, one of which serves as
> a lock on the other. Both for performance reasons and for deadlock analysis,
> I would really like an atomic read on MVars, though. Does it exist? If not,
> why not?

Have you considered using STM? All the operations on TMVars are atomic.

--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: No atomic read on MVar?

Arnar Birgisson
On Mon, Nov 3, 2008 at 23:51, David Menendez <[hidden email]> wrote:
> On Mon, Nov 3, 2008 at 6:29 AM, Philip K.F. Hölzenspies
> <[hidden email]> wrote:
>>
>> I have now implemented my variable as a pair of MVars, one of which serves as
>> a lock on the other. Both for performance reasons and for deadlock analysis,
>> I would really like an atomic read on MVars, though. Does it exist? If not,
>> why not?
>
> Have you considered using STM? All the operations on TMVars are atomic.

I will second this. At the very least, if you only need atomic
read/write operations you can use TMVars and make aliases that compose
with atomically:

takeMVar = atomically . takeTMVar
putMVar = atomically . putTMVar

etc.

cheers,
Arnar
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: No atomic read on MVar?

haskell-2
It is true that STM's TMVars (which are TVar (Maybe _)) allow atomic readTMVar.

They are not a great replacement for MVars for serious performance reasons.

MVars have "wake one" semantics: There can be many threads stopped and waiting
on a particular MVar to be filled/emptied.  These are actually in a FIFO queue.
  Filling or emptying it will cause the next thread in the FIFO queue to run,
and leave the others to sleep. [1]

TVars (and TMVars, and all STM threads) have "wake all" semantics: All threads
which are stopped after a "retry" that are monitoring a particular TVar will be
woken when the TVar is changed by the next STM commit.  This will cause the
"thundering herd" problem that plagued big Apache web servers with the original
multi-process model [2].

To understand MVars and Simon's comments on the atomic read proposal I went and
read the code in [3] to see it first hand.  The putMVar# and tryPutMVar#
operations, when a take operation is blocked, will perform the take operation
and then wake the blocked thread.  The takeMVar# and tryTakeMVar# do the
reverse.  So adding an atomicRead# operation would mean that on filling the MVar
that all the atomicRead# that are waiting might need to be woken (or perhaps
just those at the front of the FIFO).  This is a fairly large change.

The desire to atomically read an MVar could be expressed by
   (1) Use STM and lose the "wake one" performance
   (2) Use an (MVar ()) guarding the (MVar a)
   (3) Use an (MVar ()) guarding an (IORef a)

Where (3) has a performance advantage to (2) and (3) is safe when only the right
operations are exposed.

I started looking at this with the opinion that "readMVar" and "withMVar" should
have atomic semantics, i.e. edit PrimOps.cmm to add these operations.  Now I am
leaning to taking (3) and packaging this as a new module that exposes the safe
operations.

Cheers,
   Chris


[1]
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-MVar.html#v%3AtakeMVar

[2] http://www.google.co.uk/search?q="thundering+herd"+apache

[3] http://darcs.haskell.org/ghc/rts/PrimOps.cmm
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: No atomic read on MVar?

p.k.f.holzenspies@utwente.nl
In reply to this post by Arnar Birgisson
L.S.,

First off, obviously, many thanks for all these usefull replies. A special
thanks to Chris. Your e-mail was very insightfull and instructive. I did, in
the end, decide to do my own queuing and scheduling using MVar () signaling,
guarding MVar a things. I want to avoid IORefs, because for my application, I
will later try to move on to distributed memory. Using MVars (or variations
thereof, but at least variables with mutexed inter-thread behaviour) should
help me when I start distributing threads over processors with segmented
memories.

Considering that I'm not very well versed in cmm, I can not fully appreciate
the implementation impact of having atomic reads. They just seem intuitive. I
see them somewhat like the isEmptyMVar, but I see there is a difficulty due
to blocking. Essentially, instead of having one single suspended-readers
queue - as is currently the case, from what I've understood - there could be
a queue for readers (non-destructive and atomic) and for takers
(destructive). Whenever something is putMVar'ed into an empty MVar, the read
queue is processed first (all waiting threads are handed the newly produced
value and woken up), after which the first of the take-queue is woken up and
given the value, leaving the MVar empty again.

When discussing efficiency in the context of this suggestion, please also
consider the memory and concurrency sides of things. Surely, there will be
more concurrency (more threads are woken up, because readMVars are queued
with higher priority and always awoken), but I have a lingering suspicion
that there may also be more sharing (because readMVars are clumped together).
I would have to see profiling data on this sharing business, but I imagine
quite a few cases where "a value" is good enough and it need not necessarily
be "the value that should be in the MVar considering the exact order of
arrival of threads at the mutex."

My two cents ;)

Regards,
Philip
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users