While we are in the process of revising the Mutex infrastructure [1] to use dedicated primitives rather than rely on counting via a semaphore, I want to raise the question of simple versus recursive mutexes. This isn't something I know much about, except that some people strongly believe recursive mutexes are evil, including David Butenhof who apparently was the guy who added recursive mutexes to POSIX "on a dare [...] but nobody was supposed to use recursive mutexes." [1]. There are two interesting discussion on stockoverflow [2][3]. But btw I disagree with Tall Jeff [3] says "The difference between a recursive and non-recursive mutex has to do with ownership. " I think he confuses a simple-mutex and binary-semaphore, as do a some commenters. "Prefer Simple Mutex Over Recursive Mutex" [4] demonstrates some performance considerations and advises "a recursive mutex is dangerous because you lose sense of locking scope. It costs more than a simple mutex." "Recursive Locks Will Kill You!" [5] provides some thread safety guidelines. Finally, there is a paper "Ad Hoc Synchronization Considered harmful" [6], which I haven't read yet since I wanted to get this post out before heading to bed, but I hope to tomorrow. [1] http://www.zaval.org/resources/library/butenhof1.html [2] http://stackoverflow.com/questions/2415082/when-to-use-recursive-mutex [3] http://stackoverflow.com/questions/187761/recursive-lock-mutex-vs-non-recurs... [4] http://askldjd.com/2009/10/26/prefer-simple-mutex-over-recursive-mutex/ [5] http://www.fieryrobot.com/blog/2008/10/14/recursive-locks-will-kill-you/ [6] https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Xiong.pdf So our existing Mutex implementation happens to be recursive, and I'm not suggesting we change that. However if we should consider *not* baking the *assumption* of recursion into the primitives, so the same primitives could *also* be used for a SimpleMutex class. The logic to provide recursion for Mutex is only [ owner = activeProcess ] which is easily done in-image. So I propose introducing aquire/release primitives based off the existing critical section primitives with the recursion removed. cheers -ben
Hi Ben, On Tue, Feb 2, 2016 at 9:54 AM, Ben Coman <btc@openinworld.com> wrote:
While we are in the process of revising the Mutex infrastructure [1] to use dedicated primitives rather than rely on counting via a semaphore, I want to raise the question of simple versus recursive mutexes.
This isn't something I know much about, except that some people strongly believe recursive mutexes are evil, including David Butenhof who apparently was the guy who added recursive mutexes to POSIX "on a dare [...] but nobody was supposed to use recursive mutexes." [1].
There are two interesting discussion on stockoverflow [2][3]. But btw I disagree with Tall Jeff [3] says "The difference between a recursive and non-recursive mutex has to do with ownership. " I think he confuses a simple-mutex and binary-semaphore, as do a some commenters.
"Prefer Simple Mutex Over Recursive Mutex" [4] demonstrates some performance considerations and advises "a recursive mutex is dangerous because you lose sense of locking scope. It costs more than a simple mutex."
"Recursive Locks Will Kill You!" [5] provides some thread safety guidelines.
Finally, there is a paper "Ad Hoc Synchronization Considered harmful" [6], which I haven't read yet since I wanted to get this post out before heading to bed, but I hope to tomorrow.
[1] http://www.zaval.org/resources/library/butenhof1.html [2] http://stackoverflow.com/questions/2415082/when-to-use-recursive-mutex [3] http://stackoverflow.com/questions/187761/recursive-lock-mutex-vs-non-recurs... [4] http://askldjd.com/2009/10/26/prefer-simple-mutex-over-recursive-mutex/ [5] http://www.fieryrobot.com/blog/2008/10/14/recursive-locks-will-kill-you/ [6] https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Xiong.pdf
So our existing Mutex implementation happens to be recursive, and I'm not suggesting we change that. However if we should consider *not* baking the *assumption* of recursion into the primitives, so the same primitives could *also* be used for a SimpleMutex class. The logic to provide recursion for Mutex is only [ owner = activeProcess ] which is easily done in-image.
So I propose introducing aquire/release primitives based off the existing critical section primitives with the recursion removed.
We have two sets of primitives, the queueing semaphore ones, signal and wait, #85 & #86, which are not recursive, and new ones, #185, #186 & #187 that support ownership, and hence support recursion. It makes no sense to remove the recursion support. That's what the primitives are for, to provide ownership support as efficiently as possible. Please don't be led by the problems others may have in other systems, and instead be led by how we're doing. Squeak and Pharo (and Smalltalk) have had recursive owned critical sections for decades and no one (e.g. from demanding industrial control applications) has complained that these recursive critical sections are problematic. Remember we have closures and hence ensure: and good unwinding support. The new primitives give us a streamlined and hack-free implementation which doesn't depend on the niceties of what are suspension points as do the pre-primitive implementations. So I see no rationale for gelding these primitives. Show me a paper on a Smalltalk app that says "recursive locks will kill you" and I'll reconsider, but in thirty years I've not seen a complaint. The complaints I have seen are - queueing Semaphores should or should not be priority queues, depending on requirements. In VW #85 & #86 were changed so that Semaphore is a priority queue. This has been good for some folks but bad for others. One should have the choice, but the current Squeak/Pharo/Smalltalk-80 default that they are /not/ priority queues is the right default - we suffer from deadlock due to priority inversion. A high-priority process spinning trying to gain access to a lock held by a low-priority process can shut out the low-priority process from releasing its lock. This is minimised by the new recursive lock primitives, but may still be a possibility. We should work on creating test cases. Positively the test cases that Andreas developed for me at Qwaq when I developed the recursive locking primitives no longer fail. I've not had time to investigate. - preempting a lower-priority process by a higher-priority process causes the preempted process to yield to others at the same priority. This is a bug which has been fixed in VW and in Cog. It is an option in Cog but it should be enabled. See SmalltalkImage>>processPreemptionYields. Smalltalk processPreemptionYields should answer false. cheers -ben
HTH _,,,^..^,,,_ best, Eliot
On Wed, Feb 3, 2016 at 2:35 AM, Eliot Miranda <eliot.miranda@gmail.com> wrote:
Hi Ben,
On Tue, Feb 2, 2016 at 9:54 AM, Ben Coman <btc@openinworld.com> wrote:
While we are in the process of revising the Mutex infrastructure [1] to use dedicated primitives rather than rely on counting via a semaphore, I want to raise the question of simple versus recursive mutexes.
This isn't something I know much about, except that some people strongly believe recursive mutexes are evil, including David Butenhof who apparently was the guy who added recursive mutexes to POSIX "on a dare [...] but nobody was supposed to use recursive mutexes." [1].
There are two interesting discussion on stockoverflow [2][3]. But btw I disagree with Tall Jeff [3] says "The difference between a recursive and non-recursive mutex has to do with ownership. " I think he confuses a simple-mutex and binary-semaphore, as do a some commenters.
"Prefer Simple Mutex Over Recursive Mutex" [4] demonstrates some performance considerations and advises "a recursive mutex is dangerous because you lose sense of locking scope. It costs more than a simple mutex."
"Recursive Locks Will Kill You!" [5] provides some thread safety guidelines.
Finally, there is a paper "Ad Hoc Synchronization Considered harmful" [6], which I haven't read yet since I wanted to get this post out before heading to bed, but I hope to tomorrow.
[1] http://www.zaval.org/resources/library/butenhof1.html [2] http://stackoverflow.com/questions/2415082/when-to-use-recursive-mutex [3] http://stackoverflow.com/questions/187761/recursive-lock-mutex-vs-non-recurs... [4] http://askldjd.com/2009/10/26/prefer-simple-mutex-over-recursive-mutex/ [5] http://www.fieryrobot.com/blog/2008/10/14/recursive-locks-will-kill-you/ [6] https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Xiong.pdf
So our existing Mutex implementation happens to be recursive, and I'm not suggesting we change that. However if we should consider *not* baking the *assumption* of recursion into the primitives, so the same primitives could *also* be used for a SimpleMutex class. The logic to provide recursion for Mutex is only [ owner = activeProcess ] which is easily done in-image.
So I propose introducing aquire/release primitives based off the existing critical section primitives with the recursion removed.
We have two sets of primitives, the queueing semaphore ones, signal and wait, #85 & #86, which are not recursive, and new ones, #185, #186 & #187 that support ownership, and hence support recursion. It makes no sense to remove the recursion support. That's what the primitives are for, to provide ownership support as efficiently as possible. Please don't be led by the problems others may have in other systems, and instead be led by how we're doing. Squeak and Pharo (and Smalltalk) have had recursive owned critical sections for decades and no one (e.g. from demanding industrial control applications) has complained that these recursive critical sections are problematic.
I respect your deep experience, but there is an engineering principle that "just because it works, doesn't mean its correct. It may just be reinforcing some misconceptions" ;) Several reasons why people may not complain... 1. the expectation its been there so long that its correct 2. the expectation expert people worked on it so its correct 3. subtle bugs remain latent or trigger infrequently, thus hard to isolate 4. when bugs arise, they are fixed pragmatically without deeper philosophical consideration 5. coincidently other good programming practices avoided problematic situations 6. Threads run concurrently and co-operatively, so maybe in practice there are less issues than a parallel and pre-emptive systems.
Remember we have closures and hence ensure: and good unwinding support.
I take it you refer to ensuring locks are required and released the same number of times. This is not related to my concern.
The new primitives give us a streamlined and hack-free implementation which doesn't depend on the niceties of what are suspension points as do the pre-primitive implementations. So I see no rationale for gelding these primitives.
I would think a thread doing an in-image (owner = activeProcess) test would be unaffected by suspension points since it doesn't change any state and only the same thread would have set owner via the primitive.
Show me a paper on a Smalltalk app that says "recursive locks will kill you" and I'll reconsider, but in thirty years I've not seen a complaint.
I cannot. There seems very limited literature on concurrency in Smalltalk. It was hard coming up with a concise example of my own, so its a bit contrived, but here goes... Imagine an invariant requirement for a value always be even. Each time work is done, the value increases monotonically. However the value must be odd while the work is done. Object subclass: #A instanceVariableNames: 'alwaysEven relaxInvariant' classVariableNames: '' package: 'ANExample' A>>initialize relaxInvariant := Mutex new. alwaysEven := 0. A>>logMe: aString Transcript crShow: self className, aString A>>doCriticalWork self logMe: ' did some work' A>>displayNext relaxInvariant critical: [ alwaysEven := alwaysEven + 1. self doCriticalWork. alwaysEven := alwaysEven + 1 ]. self logMe: ' produced even number ' , self alwaysEven printString A>>alwaysEven ^ relaxInvariant critical: [ alwaysEven ] Now "(A new) displayNext; displayNext" produces... A did some work A produced even number 2 A did some work A produced even number 4 and all is well. Now assume that exists deep in the system library, programmed by a core-dev. So Along I come as and end-user and for my own project need B just like A but additionally need to do a bit more work. A subclass: #B instanceVariableNames: '' classVariableNames: '' package: 'ANExample' B>>doCriticalWork super doCriticalWork. self logMe: ' produced odd number ' , (self alwaysEven + 1) printString. Read that last line again. Its fairly obvious what behaviour to expect. Now "(B new) displayNext; displayNext" produces... B did some work B produced odd number 2 B produced even number 2 B did some work B produced odd number 4 B produced even number 4 So do I dare complain the mutex that was expected to protect the invariant is broken? Or do I assume its my own stupid fault for not fully comprehending the internals of the system library? Here the aberrant behaviour is clear, but in a complex system the defect may subtly corrupt data so it doesn't misbehave until later with the effect distant from the cause. Alternatively, using a non-recursive mutex... Mutex subclass: #SimpleMutex instanceVariableNames: '' classVariableNames: '' package: 'Kernel-Processes' SimpleMutex>>critical: aBlock Processor activeProcess == owner ifTrue: [self error: 'recursive locks will kill you' ]. ^ super critical: aBlock B subclass: #C instanceVariableNames: '' classVariableNames: '' package: 'ANExample' C>>initialize relaxInvariant := SimpleMutex new. alwaysEven := 0. Now "(C new) displayNext; displayNext" produces... C did some work Error: recursive locks will kill you So here it fails *early*. This may be good for some folks and bad for others, but one should have the choice. ;) I feel like saying that it would be better for a concurrency neophyte to start with the rigour of a SimpleMutex and stick with it as long as possible, for what they would learn along the way about cases a recursive lock is really needed. But really I don't know, or whether I'd be just snatching arguments to support my view. Now I don't propose to change the existing primitiveXXXCriticalSection, but it seems the logic for those is reverse for the #aquire message that Dennis wants to use ( "lock acquire" currently will be returning false when it aquires the lock) . I thought you'd hinted it might be possible to add some primitives such that "lock acquire" returns true, and maybe those could be non-recursive. We would still need to evaluate what the actual performance impact was.
The complaints I have seen are
- queueing Semaphores should or should not be priority queues, depending on requirements. In VW #85 & #86 were changed so that Semaphore is a priority queue. This has been good for some folks but bad for others. One should have the choice, but the current Squeak/Pharo/Smalltalk-80 default that they are /not/ priority queues is the right default
- we suffer from deadlock due to priority inversion. A high-priority process spinning trying to gain access to a lock held by a low-priority process can shut out the low-priority process from releasing its lock. This is minimised by the new recursive lock primitives, but may still be a possibility. We should work on creating test cases. Positively the test cases that Andreas developed for me at Qwaq when I developed the recursive locking primitives no longer fail. I've not had time to investigate.
Can you provide these? Sounds like a puzzle I might like to chew on.
- preempting a lower-priority process by a higher-priority process causes the preempted process to yield to others at the same priority. This is a bug which has been fixed in VW and in Cog. It is an option in Cog but it should be enabled. See SmalltalkImage>>processPreemptionYields. Smalltalk processPreemptionYields should answer false.
In 50564, Smalltalk vm processPreemptionYields --> true. cheers -ben
Hi Ben. 2016-02-04 18:16 GMT+01:00 Ben Coman <btc@openinworld.com>:
SimpleMutex>>critical: aBlock Processor activeProcess == owner ifTrue: [self error: 'recursive locks will kill you' ]. ^ super critical: aBlock
This can be easily implemented with current primitive (I use inverted version here): SimpleMutex>>critical: aBlock acquiredHere := lock acquire. acquiredHere ifFalse: [self error: 'recursive locks will kill you' ]. ... So what you want to change?
On Fri, Feb 5, 2016 at 1:16 AM, Ben Coman <btc@openinworld.com> wrote:
On Wed, Feb 3, 2016 at 2:35 AM, Eliot Miranda <eliot.miranda@gmail.com> wrote:
Hi Ben,
On Tue, Feb 2, 2016 at 9:54 AM, Ben Coman <btc@openinworld.com> wrote:
While we are in the process of revising the Mutex infrastructure [1] to use dedicated primitives rather than rely on counting via a semaphore, I want to raise the question of simple versus recursive mutexes.
This isn't something I know much about, except that some people strongly believe recursive mutexes are evil, including David Butenhof who apparently was the guy who added recursive mutexes to POSIX "on a dare [...] but nobody was supposed to use recursive mutexes." [1].
There are two interesting discussion on stockoverflow [2][3]. But btw I disagree with Tall Jeff [3] says "The difference between a recursive and non-recursive mutex has to do with ownership. " I think he confuses a simple-mutex and binary-semaphore, as do a some commenters.
"Prefer Simple Mutex Over Recursive Mutex" [4] demonstrates some performance considerations and advises "a recursive mutex is dangerous because you lose sense of locking scope. It costs more than a simple mutex."
"Recursive Locks Will Kill You!" [5] provides some thread safety guidelines.
Finally, there is a paper "Ad Hoc Synchronization Considered harmful" [6], which I haven't read yet since I wanted to get this post out before heading to bed, but I hope to tomorrow.
[1] http://www.zaval.org/resources/library/butenhof1.html [2] http://stackoverflow.com/questions/2415082/when-to-use-recursive-mutex [3] http://stackoverflow.com/questions/187761/recursive-lock-mutex-vs-non-recurs... [4] http://askldjd.com/2009/10/26/prefer-simple-mutex-over-recursive-mutex/ [5] http://www.fieryrobot.com/blog/2008/10/14/recursive-locks-will-kill-you/ [6] https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Xiong.pdf
So our existing Mutex implementation happens to be recursive, and I'm not suggesting we change that. However if we should consider *not* baking the *assumption* of recursion into the primitives, so the same primitives could *also* be used for a SimpleMutex class. The logic to provide recursion for Mutex is only [ owner = activeProcess ] which is easily done in-image.
So I propose introducing aquire/release primitives based off the existing critical section primitives with the recursion removed.
We have two sets of primitives, the queueing semaphore ones, signal and wait, #85 & #86, which are not recursive, and new ones, #185, #186 & #187 that support ownership, and hence support recursion. It makes no sense to remove the recursion support. That's what the primitives are for, to provide ownership support as efficiently as possible. Please don't be led by the problems others may have in other systems, and instead be led by how we're doing. Squeak and Pharo (and Smalltalk) have had recursive owned critical sections for decades and no one (e.g. from demanding industrial control applications) has complained that these recursive critical sections are problematic.
I respect your deep experience, but there is an engineering principle that "just because it works, doesn't mean its correct. It may just be reinforcing some misconceptions" ;)
Several reasons why people may not complain... 1. the expectation its been there so long that its correct 2. the expectation expert people worked on it so its correct 3. subtle bugs remain latent or trigger infrequently, thus hard to isolate 4. when bugs arise, they are fixed pragmatically without deeper philosophical consideration 5. coincidently other good programming practices avoided problematic situations 6. Threads run concurrently and co-operatively, so maybe in practice there are less issues than a parallel and pre-emptive systems.
Okay class... your new word for the day is "hubris". It was hubris for me to lay it out like that. It was easy to think I could do better from a distant hand waving perspective, but having spent a few hours in the trenches playing concretely with the primitive code, I've realised the current primitiveEnterCriticalSection is optimum.
I would think a thread doing an in-image (owner = activeProcess) test would be unaffected by suspension points since it doesn't change any state and only the same thread would have set owner via the primitive.
The new primitives give us a streamlined and hack-free implementation which doesn't depend on the niceties of what are suspension points as do the pre-primitive implementations. So I see no rationale for gelding these primitives.
You are right. Actually, as Dennis indicated, the existing primitive already provides everything needed... RecursiveMutex>>critical: aBlock ^self primitiveEnterCriticalSection ifTrue: [aBlock value] ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]] SimpleMutex>>critical: aBlock ^self primitiveEnterCriticalSection ifTrue: [self error: 'recursive primitives will kill you'] ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]] duh, me! Well, it was a useful learning process for me to play with the primitive. I'm may have some further thoughts on the exit primitive, but they are still forming, so I'll leave for a separate post. cheers -ben
On Sat, Feb 6, 2016 at 8:28 AM, Ben Coman <btc@openinworld.com> wrote:
On Fri, Feb 5, 2016 at 1:16 AM, Ben Coman <btc@openinworld.com> wrote:
On Wed, Feb 3, 2016 at 2:35 AM, Eliot Miranda <eliot.miranda@gmail.com> wrote:
Hi Ben,
On Tue, Feb 2, 2016 at 9:54 AM, Ben Coman <btc@openinworld.com> wrote:
While we are in the process of revising the Mutex infrastructure [1] to use dedicated primitives rather than rely on counting via a semaphore, I want to raise the question of simple versus recursive mutexes.
This isn't something I know much about, except that some people strongly believe recursive mutexes are evil, including David Butenhof who apparently was the guy who added recursive mutexes to POSIX "on a dare [...] but nobody was supposed to use recursive mutexes." [1].
There are two interesting discussion on stockoverflow [2][3]. But btw I disagree with Tall Jeff [3] says "The difference between a recursive and non-recursive mutex has to do with ownership. " I think he confuses a simple-mutex and binary-semaphore, as do a some commenters.
"Prefer Simple Mutex Over Recursive Mutex" [4] demonstrates some performance considerations and advises "a recursive mutex is dangerous because you lose sense of locking scope. It costs more than a simple mutex."
"Recursive Locks Will Kill You!" [5] provides some thread safety guidelines.
Finally, there is a paper "Ad Hoc Synchronization Considered harmful" [6], which I haven't read yet since I wanted to get this post out before heading to bed, but I hope to tomorrow.
[1] http://www.zaval.org/resources/library/butenhof1.html [2] http://stackoverflow.com/questions/2415082/when-to-use-recursive-mutex [3] http://stackoverflow.com/questions/187761/recursive-lock-mutex-vs-non-recurs... [4] http://askldjd.com/2009/10/26/prefer-simple-mutex-over-recursive-mutex/ [5] http://www.fieryrobot.com/blog/2008/10/14/recursive-locks-will-kill-you/ [6] https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Xiong.pdf
So our existing Mutex implementation happens to be recursive, and I'm not suggesting we change that. However if we should consider *not* baking the *assumption* of recursion into the primitives, so the same primitives could *also* be used for a SimpleMutex class. The logic to provide recursion for Mutex is only [ owner = activeProcess ] which is easily done in-image.
So I propose introducing aquire/release primitives based off the existing critical section primitives with the recursion removed.
We have two sets of primitives, the queueing semaphore ones, signal and wait, #85 & #86, which are not recursive, and new ones, #185, #186 & #187 that support ownership, and hence support recursion. It makes no sense to remove the recursion support. That's what the primitives are for, to provide ownership support as efficiently as possible. Please don't be led by the problems others may have in other systems, and instead be led by how we're doing. Squeak and Pharo (and Smalltalk) have had recursive owned critical sections for decades and no one (e.g. from demanding industrial control applications) has complained that these recursive critical sections are problematic.
I respect your deep experience, but there is an engineering principle that "just because it works, doesn't mean its correct. It may just be reinforcing some misconceptions" ;)
Several reasons why people may not complain... 1. the expectation its been there so long that its correct 2. the expectation expert people worked on it so its correct 3. subtle bugs remain latent or trigger infrequently, thus hard to isolate 4. when bugs arise, they are fixed pragmatically without deeper philosophical consideration 5. coincidently other good programming practices avoided problematic situations 6. Threads run concurrently and co-operatively, so maybe in practice there are less issues than a parallel and pre-emptive systems.
Okay class... your new word for the day is "hubris". It was hubris for me to lay it out like that. It was easy to think I could do better from a distant hand waving perspective, but having spent a few hours in the trenches playing concretely with the primitive code, I've realised the current primitiveEnterCriticalSection is optimum.
I would think a thread doing an in-image (owner = activeProcess) test would be unaffected by suspension points since it doesn't change any state and only the same thread would have set owner via the primitive.
The new primitives give us a streamlined and hack-free implementation which doesn't depend on the niceties of what are suspension points as do the pre-primitive implementations. So I see no rationale for gelding these primitives.
You are right. Actually, as Dennis indicated, the existing primitive already provides everything needed...
RecursiveMutex>>critical: aBlock ^self primitiveEnterCriticalSection ifTrue: [aBlock value] ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]]
SimpleMutex>>critical: aBlock ^self primitiveEnterCriticalSection ifTrue: [self error: 'recursive primitives will kill you'] ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]]
Dennis, I no longer think we need a new primitive for #acquire. We should just use 186. Regarding the inverted logic, we either live with it, or perhaps name it something like #acquiredAgain. For example we might have... Mutex>>criticalNew: aBlock lock acquiredAgain ifTrue: [aBlock value] "recursive" ifFalse: [ aBlock ensure: [ lock release] ]. "first time" OwnedLockTest>>testAcquireLockTwiceFromSameProcess | acquiredAgain | self fork: [ lock acquiredAgain. acquiredAgain := lock acquiredAgain ]. self waitLastProcessFinished. self assert: acquiredAgain description: 'acquiring lock twice should return true' but I'm not sure about my #acquiredAgain suggestion and hope to hear what others think. cheers -ben
participants (3)
-
Ben Coman -
Denis Kudriashov -
Eliot Miranda