MVar is very low level. You almost never want to use it directly unless you're building a higher level synchronization mechanism from scratch. On Wed, Dec 19, 2018 at 4:34 PM Bryan Richter wrote:

Interesting. I have indeed seen enough cases of "Blocked indefinitely on MVar" to suggest they might be difficult to handle correctly!

On Wed, Dec 19, 2018, 23:02 Станислав Черничкин

...

Recently I had an interesting discussion on MVars with cats-effect library designers. Cats-effect brings MVar synchronization primitive along with other IO stuff to the Scala programming language. I tried to persuade them to include some Control.Concurrent.MVar’s functions to the library but has failed completely. Moreover, now I think that MVar is a poor choice for basic synchronization primitive. Your may find discussion here https://github.com/typelevel/cats-effect/issues/451 and event try to advocate, tl;dr. Anyway, what is so wrong with MVar?

1. It’s complex. Each MVar has 2 state transitions, each may block.

2. It does not play well in presence of asynchronous exceptions. More specifically, `take` and `put` operations should be balanced (each `take` must be followed by `put`) this force programmer to mask asynchronous exceptions during the MVar acquisition and since `take` function may block, this will delay task cancelation. Well, you may argue what the `takeMVar` function is actually interruptible, but I’m going to show an easier approach which renders interpretability magic unnecessary.

What could be the sensible alternative? Guy from the cats-effect suggested me IVar + atomic reference (IORef). This pattern separates concern of blocking (synchronization) from the atomic mutation. So everything can be represented as atomic reference with IVar inside. Just look at this beautiful mutex implementation https://github.com/ovotech/fs2-kafka/blob/master/src/main/scala/fs2/kafka/in... (By ”beautiful” I mean approach itself of course, but not the Scala’s syntax. Scala is one of most ugliest girls after C++ I was forced to date with by my employer for money. Thankfully he didn’t force me to do the same things with her grandma Java).

For people who don’t read Scala, the approach is fairly simple. Each thread which want to touch mutex, will create IVar, atomically swap it in the IORef masked (note, that IORef’s operations non-blocking), unmask and wait for previous become available IVar *unmasked*. Then it will either perform it’s operations or fail due to the interruption or exception and trigger newly installed IVar anyway. It just works. Without any «interruptible» magic.

So, which benefits can we get?

1. Simpler implementation of basic primitives. Obliviously IORef is fairly simple. IVar is also mind be simpler than MVar, and possibly faster (just “possibly”, I don’t know how it’s implemented, but I guess lesser state transitions implies less logic).

2. Simplified deadlock analysis. Really, we have only IVar with only one state transition and only one potentially blocking operation.

3. Magicless support of interruptions. We don’t need to separate mask/uninterruptibleMask anymore, because all updates are non-blocking, and all waits are unmasked. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

-- brandon s allbery kf8nh allbery.b@gmail.com

IIRC, MVars (in Haskell anyway) also have some fairness guarantees, which I don't see otherwise mentioned in the discussion so far.

Looking at given mutex implementation I guess fairness controlled by the primitive itself. More particular: 1. Each thread which trying to obtain mutex will wait for one I-Var exclusively (no competing threads waits shared I-Var hence there is no space for “unfair” schedule). 2. I-Var’s swapped by atomic ‘getAndSet’ which is likely can be implemented over CAS or LL/SC and will be as fair as hardware could be.

If the goal is to have a simpler base primitive on which to build, everything has to boil down to compare-and-swap, load-linked/store-conditional, etc

I had this discussion with a Cats guys, but I still can’t understand how it’s possible to implement generic non-busy waiting with CAS/LL-SC only. Ok, somewhere at deeper level it’s actually CAS/LL-SC, but one of the threads should be able to HLT (privileged instruction). Otherwise non-busy waiting would not be possible. Speaking other words, generic locking strategy should allow you to deadlock. How would you implement non-busy deadlock without HLT? Probably I’m missing something, and I’ll be grateful if anyone clarifies. Because I was told multiple times that CAS/LL-SC is enough along, but I can’t figure out myself.

If what you're after is *composable* concurrency, simpler locks won't get you that.

Composability is not a point at all currently. I’m not after composability I’m after completeness. Let me speculate a bit and presume that any sufficiently complex composable system (i.e. such a system which would hold some “correctness” properties over allowed composition operations) will necessary be incomplete (i.e. some “correct” expressions will be inexpressible due to the lack of compositions rules and there is no way to supplement the system without making it controversial). This is my very personal interpretation of the Godel Theorem and pure speculation, but look, every non-Turing complete language will prohibit correct programs, on the other hand, every Turing complete will allow you to write non-terminating programs (contradictions). I believe, same property holds with concurrency. If some system prohibits you from deadlocks, it will also prohibit you from some correct synchronization strategies (once again, it’s my speculations, maybe there is a proof of contrary, but I haven't found them yet). Standing from this point, it’s worth to have some complete and controversial (uncomposable) API at low level and having several composable implementations over it with their restrictions.

async exceptions, you're in the same situation with MVars as you are with all resource-acquiring IO actions in Haskell.

In my opinion they are completely different. In one case we should provide guaranteed resource release, so we want to make resource acquisition atomic. In other case we want to make wait operation interruptible (hence – non-atomic unless acquisition consists of only one operation). Consider `mask $ \restore -> do { x <- resourceAcquisition; interruptibleOperation; onException (restore $ f x) (resorceRelease<1> x); resorceRelease<2> x }`. In case of interruption we will neither get to resorceRelease<1> nor to resorceRelease<2> (that is why uninterruptibleMask was introduced). Its tempting to consider a MVar as a resource, but resources don’t like interruptions, they should be separated. чт, 20 дек. 2018 г. в 01:16, Ian Denhardt :

A few thoughts:

* IIRC, MVars (in Haskell anyway) also have some fairness guarantees, which I don't see otherwise mentioned in the discussion so far. Compare to STM, where large transactions are susceptible to starvation. * If the goal is to have a simpler base primitive on which to build, everything has to boil down to compare-and-swap, load-linked/store-conditional, etc -- whatever the machine provides. When you start talking about even mutexes and semaphores, you're already dealing with higher-level abstractions, so the thinking about what's the right "primitive" seems silly to me at that point; you should be thinking about what the high-level (user) code should be able to do, and then figure out how to meet in the middle. * If what you're after is *composable* concurrency, simpler locks won't get you that. STM is the best general solution I've seen for this, and if you're doing concurrency stuff in Haskell, I would say use STM unless you have a specific reason to do something else. * Re: async exceptions, you're in the same situation with MVars as you are with all resource-acquiring IO actions in Haskell. `withMVar` and friends cover async-exception safety, and you can't get rid of mask and friends by swapping out MVars with another primitive anyway, because you still need them for acquiring other (non-concurrency related) resources, like files.

-Ian

-- Sincerely, Stanislav Chernichkin.

Am 26.12.18 um 00:04 schrieb Станислав Черничкин:

Ok, somewhere at deeper level it’s actually CAS/LL-SC, but one of the threads should be able to HLT (privileged instruction). Otherwise non-busy waiting would not be possible.

HLT stops the entire processor, including operating system. No way a user process should ever execute *that*. What actually happens is that threads are simply not scheduled, with strongly implementation-dependent means of making them runnable again (some schedulers require that you state runnability upfront, in the form of a mutex, futex, semaphore, monitor, or whatever; others allow one thread to change the runnability of another thread post-hoc).

Composability is not a point at all currently. I’m not after composability I’m after completeness. Let me speculate a bit and presume that any sufficiently complex composable system (i.e. such a system which would hold some “correctness” properties over allowed composition operations) will necessary be incomplete (i.e. some “correct” expressions will be inexpressible due to the lack of compositions rules and there is no way to supplement the system without making it controversial).

This is my very personal interpretation of the Godel Theorem and pure speculation,

The computer science equivalent of the Godel Theorem is "undecidability". That's well-trodden ground. In practice, the options are: 1. Giving up correctness is not very useful. (There are extremely rare exceptions - be prepared to strongly defend any a suggestion of that kind.) 2. Giving up completeness can still be useful. You do not get true universality, but you get a correctness guarantee. 3. You can still have both correctness and completeness. If your heuristics are good, you'll get a result in the vast majority of cases in practice. The cases that don't work out will simply run into an endless loop; just add a timeout to the computation. Obviously, you don't want such an approach for time-critical stuff like thread scheduling, but it's been used successfully e.g. for type systems that are more powerful than Hindley-Milner. 4. Do not solve the problem at all. E.g. don't prevent deadlocks by inspecting code and determining whether it can deadlock or not; detect deadlocks after they happen and report them as errors.

but look, every non-Turing complete language will prohibit correct programs, on the other hand, every Turing complete will allow you to write non-terminating programs (contradictions). I believe, same property holds with concurrency.

You get into undecidability issues at the point where an algorithm needs to analyze a program for termination. So people have been using algorithms don't inspect programs, but which inspect data (Haskell's infinite data structures would be categorized as program in this discussion, because it's code that will return finite portions of the infinite data structure). Even with finite data, algorithms can be undecidable. It's rare and usually doesn't happen, but it can happen if the data structure somehow expresses a Turing-complete language. Note that compilers and such never actually analyze the full program, they just apply patterns that a programmer has decided preserve semantics. (Mistakes here usually lead to compiler bugs.)

If some system prohibits you from deadlocks, it will also prohibit you from some correct synchronization strategies (once again, it’s my speculations, maybe there is a proof of contrary, but I haven't found them yet).

Correct, but this is only a problem in practice if you need a locking scheme that can express undecidable locking strategies. I am not a grand master of locking strategies, but I see locking strategies move from semaphores (undecidable) towards higher-level constructs that do not allow all kinds of locking anymore. I don't think that futures etc. exclude deadlocks by construction, but I do see that deadlocks have become a less common problem.

Standing from this point, it’s worth to have some complete and controversial (uncomposable) API at low level and having several composable implementations over it with their restrictions.

That's one of today's difficult goals: Designing a locking API that's both composable and useful. I'm not sure whether such a thing has even been thought of yet.

On Dec 28, 2018, at 12:44 PM, Bertram Felgenhauer via Haskell-Cafe wrote:

This is awkward to fix. Basically, when abandoning the lock before it has been released by the previous owner, we need a new thread to wait for the 'current' IVar and notify the 'next' one, since the current thread is being interrupted.

I think that work can be delegated to the waiting thread, by making locks (really barriers) optionally chain to a parent barrier that also needs to be waited for (recursively). This is cheap, because unless threads are actually interrupted, the chain is always one deep. When a thread is interrupted, the next thread will wait for 2 barriers, ... -- Viktor. module Main (main) where import Control.Concurrent.MVar -- should be an IVar import Control.Concurrent import Control.Exception (bracket) import Data.IORef -- Really a recursive barrier newtype Lock = Lock (MVar (Maybe Lock)) type Mutex = IORef Lock type Chain = IORef (Maybe Lock) newMutex :: IO Mutex newMutex = Lock <$> newMVar Nothing >>= newIORef withMutex :: Mutex -> IO a -> IO a withMutex m = bracket swapShared signalPrivate . (\act -> (>> act) . waitChain . snd) where -- Return a new IORef containing the old barrier from the mutex, and a new -- barrier, that has been atomically swapped into the old mutex. swapShared :: IO (Lock, Chain) swapShared = Lock <$> newEmptyMVar >>= \b' -> atomicModifyIORef m (\b -> (b', b)) >>= \b -> newIORef (Just b) >>= \chain -> return (b', chain) signalPrivate :: (Lock, Chain) -> IO () signalPrivate (Lock b, chain) = readIORef chain >>= putMVar b -- The last barrier that we were waiting on (if we're interrupted) -- will be left in our chain as a "continuation" for whoever -- next gets the mutex. It may be already signalled by the time they -- see it, and that's OK. On normal return it will be 'Nothing'. waitChain :: Chain -> IO () waitChain c = readIORef c >>= go where go = mapM_ $ \(Lock a) -> readMVar a >>= \b -> writeIORef c b >> go b mkThread :: Mutex -> String -> IO ThreadId mkThread m name = do tid <- forkIO $ withMutex m $ do putStrLn $ unwords ["thread", name, "running"] threadDelay 200000 putStrLn $ unwords ["thread", name, "stopping"] yield return tid main :: IO () main = do m <- newMutex _ <- mkThread m "A" threadB <- mkThread m "B" _ <- mkThread m "C" killThread threadB threadDelay 1000000

Having no sense of either history or implementation. On Sat, Dec 29, 2018 at 5:43 AM Serguey Zefirov wrote:

MVar and IVar things are from dataflow programming, I believe, from Id90 programming language (read about it, it's fascinating). They were ued there with greate success (linear scaling on CM-5, no less; they had to invent throttling to tame huge parallelism available). MVar were used for synchronization and IVars to provide a kind of call-by-need in a lenient language. Mind that Id90 was not as sofisticated as Haskell today and these things were used as a coordination tool between huge number of small threads of execution, with no I/O and all threads must work to completion.

Thus, they are, as usually happens, not general purpose yet very useful. I consider them "baby-STM".

But what it takes to consider them harmful is beyond me.

чт, 20 дек. 2018 г. в 00:02, Станислав Черничкин :

...

Recently I had an interesting discussion on MVars with cats-effect library designers. Cats-effect brings MVar synchronization primitive along with other IO stuff to the Scala programming language. I tried to persuade them to include some Control.Concurrent.MVar’s functions to the library but has failed completely. Moreover, now I think that MVar is a poor choice for basic synchronization primitive. Your may find discussion here https://github.com/typelevel/cats-effect/issues/451 and event try to advocate, tl;dr. Anyway, what is so wrong with MVar?

1. It’s complex. Each MVar has 2 state transitions, each may block.

2. It does not play well in presence of asynchronous exceptions. More specifically, `take` and `put` operations should be balanced (each `take` must be followed by `put`) this force programmer to mask asynchronous exceptions during the MVar acquisition and since `take` function may block, this will delay task cancelation. Well, you may argue what the `takeMVar` function is actually interruptible, but I’m going to show an easier approach which renders interpretability magic unnecessary.

What could be the sensible alternative? Guy from the cats-effect suggested me IVar + atomic reference (IORef). This pattern separates concern of blocking (synchronization) from the atomic mutation. So everything can be represented as atomic reference with IVar inside. Just look at this beautiful mutex implementation https://github.com/ovotech/fs2-kafka/blob/master/src/main/scala/fs2/kafka/in... (By ”beautiful” I mean approach itself of course, but not the Scala’s syntax. Scala is one of most ugliest girls after C++ I was forced to date with by my employer for money. Thankfully he didn’t force me to do the same things with her grandma Java).

For people who don’t read Scala, the approach is fairly simple. Each thread which want to touch mutex, will create IVar, atomically swap it in the IORef masked (note, that IORef’s operations non-blocking), unmask and wait for previous become available IVar *unmasked*. Then it will either perform it’s operations or fail due to the interruption or exception and trigger newly installed IVar anyway. It just works. Without any «interruptible» magic.

So, which benefits can we get?

1. Simpler implementation of basic primitives. Obliviously IORef is fairly simple. IVar is also mind be simpler than MVar, and possibly faster (just “possibly”, I don’t know how it’s implemented, but I guess lesser state transitions implies less logic).

2. Simplified deadlock analysis. Really, we have only IVar with only one state transition and only one potentially blocking operation.

3. Magicless support of interruptions. We don’t need to separate mask/uninterruptibleMask anymore, because all updates are non-blocking, and all waits are unmasked. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

-- brandon s allbery kf8nh allbery.b@gmail.com