<div dir="ltr"><div dir="ltr"><div>>IIRC, MVars (in Haskell anyway) also have some fairness guarantees, which I don't see otherwise mentioned in the discussion so far.</div><div><br></div><div>Looking at given mutex implementation I guess fairness controlled by the primitive itself. More particular: </div><div>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).</div><div>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. </div><div><br></div><div>> 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</div><div><br></div><div>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.</div><div><br></div><div>> If what you're after is *composable* concurrency, simpler locks won't get you that.</div><div><br></div><div>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).</div><div><br></div><div>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).</div><div><br></div><div>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.</div><div><br></div><div>>async exceptions, you're in the same situation with MVars as you are with all resource-acquiring IO actions in Haskell.</div><div><br></div><div>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.</div><div><br></div></div></div><br><div class="gmail_quote"><div dir="ltr">чт, 20 дек. 2018 г. в 01:16, Ian Denhardt <<a href="mailto:ian@zenhack.net">ian@zenhack.net</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">A few thoughts:<br>
<br>
* IIRC, MVars (in Haskell anyway) also have some fairness guarantees,<br>
which I don't see otherwise mentioned in the discussion so far.<br>
Compare to STM, where large transactions are susceptible to<br>
starvation.<br>
* If the goal is to have a simpler base primitive on which to build,<br>
everything has to boil down to compare-and-swap,<br>
load-linked/store-conditional, etc -- whatever the machine provides.<br>
When you start talking about even mutexes and semaphores, you're<br>
already dealing with higher-level abstractions, so the thinking about<br>
what's the right "primitive" seems silly to me at that point; you<br>
should be thinking about what the high-level (user) code should be<br>
able to do, and then figure out how to meet in the middle.<br>
* If what you're after is *composable* concurrency, simpler locks won't<br>
get you that. STM is the best general solution I've seen for this, and<br>
if you're doing concurrency stuff in Haskell, I would say use STM<br>
unless you have a specific reason to do something else.<br>
* Re: async exceptions, you're in the same situation with MVars as you<br>
are with all resource-acquiring IO actions in Haskell. `withMVar` and<br>
friends cover async-exception safety, and you can't get rid of mask and<br>
friends by swapping out MVars with another primitive anyway, because<br>
you still need them for acquiring other (non-concurrency related)<br>
resources, like files.<br>
<br>
-Ian<br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><span style="font-family:arial;font-size:small">Sincerely, Stanislav Chernichkin.</span><br></div></div>