4

I'd like a function

takeAnyMVar :: NonEmpty (MVar a) -> IO (MVar a, a)

which waits on multiple MVars simultaneously and returns the first MVar (and its value) that becomes available.

In particular, it should only cause a single one of the MVars in the input list to be in an empty state that wasn't empty before.

I have an implementation, but it is both inefficient and incorrect:

import Data.List.NonEmpty          -- from semigroups
import Control.Concurrent.Async    -- from async
import Control.Concurrent.MVar
import Control.Applicative
import Data.Foldable

takeAnyMVar :: NonEmpty (MVar a) -> IO (MVar a, a)
takeAnyMVar = runConcurrently . foldr1 (<|>) . fmap (Concurrently . takeMVar')
    where
        takeMVar' mvar = takeMVar mvar >>= \val -> return (mvar, val)

It's inefficient because it has to start a new thread for every MVar in the list.

It is incorrect, because multiple threads might take their MVar and leave it in an empty state before they can be cancelled by the (<|>) operator (which calls race in the end). One of them will succeed and return its result, the others will discard their results but leave their MVars empty.

On Windows, there is the WaitForMultipleObjects function, which allows to wait on multiple wait handles. I suspect there is something similar in other operating systems.

Given that MVar is probably implemented in terms of OS primitives, it should be possible to write a function with the above sematics. But maybe you need access to the implementation of MVar in order to do that.

The same applies to Chan, QSem, MSem, and other concurrency primitives.

Tobias Brandt
  • 3,393
  • 18
  • 28
  • 4
    I don't really think there is a good way. We can recommend alternatives, but to do that well we need to know a bit of context about what you're trying to achieve. Probably the answer is "just use `STM`", but it's really hard to give blind advice that's also good. – Daniel Wagner Jul 01 '15 at 17:49
  • 1
    This is pretty much the exact problem that STM is supposed to solve. Use software transactions and you can trivially wait on multiple conditions simultaneously. – MathematicalOrchid Jul 01 '15 at 18:09
  • @DanielWagner, @MathematicalOrchid `STM` only operates on memory, not external resources like files, window handles, GUI events, etc. How do I synchronize an existing source of events (e.g. a native GUI framework) using `STM`? – Tobias Brandt Jul 01 '15 at 18:15
  • You can either use `tryTakeMVar` (perhaps with a blocking `setTimeout`) or choose to block on a single `takeMVar`. Thirding the choice to use `STM` for at least part of your solution. You've basically already imported that with [`waitAny`](http://hackage.haskell.org/package/async-2.0.2/docs/src/Control-Concurrent-Async.html#waitAny). Be aware that the semantics there are subtly different than what I think you want; your `takeAnyVar` will return the *leftmost* full variable, i.e. your function will be biased to the left rather than a round-robin type thing. – jberryman Jul 01 '15 at 18:17
  • 3
    "How do I synchronize an existing source of events (e.g. a native GUI framework) using STM" The same way you'd use `MVar` right? Have the file-handling or GUI bits of your code do a `atomically . putTMVar` or something. – jberryman Jul 01 '15 at 18:25
  • 1
    Perhaps also of interest: [How do I watch multiple files/sockets to become readable/writable in Haskell?](http://stackoverflow.com/q/11744527/791604). Note that the answer there doesn't involve `STM` at all, and is why I am hesitant to try to suggest an answer without understanding what concerns you are trying to address. Please give us further details about what you want to do. (Or, to use other jargon that you may be familiar with: this question reeks of an X/Y problem.) – Daniel Wagner Jul 01 '15 at 19:19

1 Answers1

4

If your function is the only consumer (and runs in just one thread), I guess that with base-4.8 you could use readMVar in the threads and empty only the TVar that is being returned, keeping the others untouched.

As suggested by @DanielWagner, STM would be much simpler.

import qualified Data.Foldable as F
import Data.List.NonEmpty
import Control.Concurrent.STM.TMVar
import Control.Monad
import Control.Monad.STM

takeAnyMVar :: NonEmpty (TMVar a) -> STM (TMVar a, a)
takeAnyMVar = F.foldr1 orElse . fmap (\t -> liftM ((,) t) $ takeTMVar t)

Here we simply try to takeTMVar each of them, combined with orElse. If all are empty, STM will be smart enough to wait until one of them becomes full and then restart the transaction.

Petr
  • 62,528
  • 13
  • 153
  • 317
  • If I use `readMVar` there is still a race condition, because another thread might have taken the `MVar` after the succeeding `readMVar` but before the `takeMVar` that empties it. This could block `takeAnyMVar` indefinitely even though some of the `MVar`s could be available. Your `STM` solution works, however. – Tobias Brandt Jul 06 '15 at 18:40
  • 1
    @TobiasBrandt You're right, if you have multiple threads that consume the variables, it won't work - that's why I wrote _if your function is the only consumer_ (I should better have written _if there is only one consuming thread_). – Petr Jul 06 '15 at 19:51