英文:
Recursive locking in Go
问题
Go的sync
包中有一个Mutex
。不幸的是,它不支持递归。在Go中实现递归锁的最佳方法是什么?
英文:
Go's sync
package has a Mutex
. Unfortunately it's not recursive. What's the best way to implement recursive locks in Go?
答案1
得分: 44
对不起,我不能直接回答你的问题:
依我之见,在Go中实现递归锁的最佳方法是不要实现它们,而是重新设计你的代码,以避免在第一次使用它们时就不需要它们。我认为,对它们的渴望可能表明在某个(未知的)问题上采用了错误的方法。
作为对上述观点的间接“证明”:如果递归锁是处理互斥锁的一些常见/正确方法,那么它迟早会被包含在标准库中。
最后但同样重要的是:Go开发团队的Russ Cox在这里写道https://groups.google.com/d/msg/golang-nuts/XqW1qcuZgKg/Ui3nQkeLV80J:
>递归(又名可重入)互斥锁是一个坏主意。
>使用互斥锁的根本原因是互斥锁保护不变量,可能是内部不变量,如“对于环的所有元素,p.Prev.Next == p”,或者是外部不变量,如“我的局部变量x等于p.Prev。”
>
>锁定互斥锁断言“我需要保持不变量”和“我将暂时破坏这些不变量”。释放互斥锁断言“我不再依赖这些不变量”和“如果我破坏了它们,我已经恢复了它们”。
>
>理解互斥锁保护不变量对于确定何时需要互斥锁以及何时不需要互斥锁至关重要。例如,使用原子递增和递减指令更新的共享计数器是否需要互斥锁?这取决于不变量。如果唯一的不变量是计数器在i增加和d减少后具有值i-d,则指令的原子性确保了不变量;不需要互斥锁。但是,如果计数器必须与其他数据结构同步(例如,它计算列表上的元素数),则单个操作的原子性是不够的。其他东西,通常是互斥锁,必须保护更高级别的不变量。这就是为什么Go中的映射操作不能保证是原子的原因:它会增加开销,而在典型情况下没有好处。
>
>让我们来看看递归互斥锁。
>假设我们有这样的代码:
func F() {
mu.Lock()
...做一些事情...
G()
...做更多的事情...
mu.Unlock()
}
func G() {
mu.Lock()
...做一些事情...
mu.Unlock()
}
>通常情况下,当调用mu.Lock返回时,调用代码现在可以假设受保护的不变量保持不变,直到调用mu.Unlock。
>
>递归互斥锁的实现会使G的mu.Lock和mu.Unlock调用在从F或任何其他当前线程已经持有mu的上下文中调用时成为无操作。如果mu使用这样的实现,那么当mu.Lock在G内部返回时,不变量可能存在或不存在。这取决于F在调用G之前做了什么。也许F甚至没有意识到G需要这些不变量,并且已经破坏了它们(在复杂代码中完全可能)。
>
>递归互斥锁不能保护不变量。
>互斥锁只有一个工作,递归互斥锁不能做到这一点。
>
>它们还存在更简单的问题,比如如果你写了这样的代码:
func F() {
mu.Lock()
...做一些事情
}
>在单线程测试中,你永远不会发现这个错误。
>但这只是更大问题的特例,即它们对互斥锁所要保护的不变量没有任何保证。
>
>如果你需要实现可以在持有或不持有互斥锁的情况下调用的功能,最清晰的做法是编写两个版本。例如,代替上面的G,你可以写:
//在已经持有mu的情况下调用。
//调用者必须小心确保...
func g() {
...做一些事情...
}
func G() {
mu.Lock()
g()
mu.Unlock()
}
>或者如果它们都是未导出的,g和gLocked。
>
>我相信我们最终会需要TryLock;请随时为此发送CL。带超时的锁似乎不是很重要,但如果有一个清晰的实现(我不知道有没有),那么也许可以接受。请不要发送实现递归互斥锁的CL。
>
>递归互斥锁只是一个错误,只不过是一个容易引发错误的舒适之地。
>Russ
英文:
I'm sorry to not answer your question directly:
IMHO, the best way how to implement recursive locks in Go is to not implement them, but rather redesign your code to not need them in the first place. It's probable, I think, that the desire for them indicates a wrong approach to some (unknown here) problem is being used.
As an indirect "proof" of the above claim: Would a recursive lock be a common/correct approach to the/some usual situations involving mutexes, it would be sooner or later included in the standard library.
And finally, last but not least: What Russ Cox from the Go development team wrote here https://groups.google.com/d/msg/golang-nuts/XqW1qcuZgKg/Ui3nQkeLV80J:
> Recursive (aka reentrant) mutexes are a bad idea.
> The fundamental reason to use a mutex is that mutexes
> protect invariants, perhaps internal invariants like
> "p.Prev.Next == p for all elements of the ring", or perhaps
> external invariants like "my local variable x is equal to p.Prev."
>
> Locking a mutex asserts "I need the invariants to hold"
> and perhaps "I will temporarily break those invariants."
> Releasing the mutex asserts "I no longer depend on those
> invariants" and "If I broke them, I have restored them."
>
> Understanding that mutexes protect invariants is essential to
> identifying where mutexes are needed and where they are not.
> For example, does a shared counter updated with atomic
> increment and decrement instructions need a mutex?
> It depends on the invariants. If the only invariant is that
> the counter has value i - d after i increments and d decrements,
> then the atmocity of the instructions ensures the
> invariants; no mutex is needed. But if the counter must be
> in sync with some other data structure (perhaps it counts
> the number of elements on a list), then the atomicity of
> the individual operations is not enough. Something else,
> often a mutex, must protect the higher-level invariant.
> This is the reason that operations on maps in Go are not
> guaranteed to be atomic: it would add expense without
> benefit in typical cases.
>
> Let's take a look at recursive mutexes.
> Suppose we have code like this:
func F() {
mu.Lock()
... do some stuff ...
G()
... do some more stuff ...
mu.Unlock()
}
func G() {
mu.Lock()
... do some stuff ...
mu.Unlock()
}
> Normally, when a call to mu.Lock returns, the calling code
> can now assume that the protected invariants hold, until
> it calls mu.Unlock.
>
> A recursive mutex implementation would make G's mu.Lock
> and mu.Unlock calls be no-ops when called from within F
> or any other context where the current thread already holds mu.
> If mu used such an implementation, then when mu.Lock
> returns inside G, the invariants may or may not hold. It depends
> on what F has done before calling G. Maybe F didn't even realize
> that G needed those invariants and has broken them (entirely
> possible, especially in complex code).
>
> Recursive mutexes do not protect invariants.
> Mutexes have only one job, and recursive mutexes don't do it.
>
> There are simpler problems with them, like if you wrote
func F() {
mu.Lock()
... do some stuff
}
> you'd never find the bug in single-threaded testing.
> But that's just a special case of the bigger problem,
> which is that they provide no guarantees at all about
> the invariants that the mutex is meant to protect.
>
> If you need to implement functionality that can be called
> with or without holding a mutex, the clearest thing to do
> is to write two versions. For example, instead of the above G,
> you could write:
// To be called with mu already held.
// Caller must be careful to ensure that ...
func g() {
... do some stuff ...
}
func G() {
mu.Lock()
g()
mu.Unlock()
}
> or if they're both unexported, g and gLocked.
>
> I am sure that we'll need TryLock eventually; feel free to
> send us a CL for that. Lock with timeout seems less essential
> but if there were a clean implementation (I don't know of one)
> then maybe it would be okay. Please don't send a CL that
> implements recursive mutexes.
>
> Recursive mutexes are just a mistake, nothing more than
> a comfortable home for bugs.
> Russ
答案2
得分: 6
你可以很容易地使用sync.Mutex和sync.Cond来创建一个递归锁。在这里的附录A中有一些想法。
除了Go运行时不公开任何关于goroutine Id的概念之外。这是为了防止人们在goroutine本地存储中做一些愚蠢的事情,也可能表明设计者认为如果你需要goroutine Id,那么你做错了。
当然,如果你真的想要,你可以使用一点C来从运行时中获取goroutine Id。你可能想阅读那个线程,看看Go的设计者为什么认为这是一个坏主意。
英文:
You could quite easily make a recursive lock out of a sync.Mutex and a sync.Cond. See Appendix A here for some ideas.
Except for the fact that the Go runtime doesn't expose any notion of goroutine Id. This is to stop people doing silly things with goroutine local storage, and probably indicates that the designers think that if you need a goroutine Id you are doing it wrong.
You can of course dig the goroutine Id out of the runtime with a bit of C if you really want to. You might want to read that thread to see why the designers of Go think it is a bad idea.
答案3
得分: -14
如已经确定,从并发的角度来看,这是一个可怕、可怕、可怕和可怕的想法。
无论如何,由于你的问题实际上是关于Go的类型系统,这里是如何定义一个具有递归方法的类型。
type Foo struct{}
func (f Foo) Bar() { fmt.Println("bar") }
type FooChain struct {
Foo
child *FooChain
}
func (f FooChain) Bar() {
if f.child != nil {
f.child.Bar()
}
f.Foo.Bar()
}
func main() {
fmt.Println("no children")
f := new(FooChain)
f.Bar()
for i := 0; i < 10; i++ {
f = &FooChain{Foo{}, f}
}
fmt.Println("with children")
f.Bar()
}
http://play.golang.org/p/mPBHKpgxnd
英文:
as was already established, this is a miserable, horrible, awful, and terrible idea from a concurrency perspective.
Anyway, since your question is really about Go's type system, here's how you would define a type with a recursive method.
type Foo struct{}
func (f Foo) Bar() { fmt.Println("bar") }
type FooChain struct {
Foo
child *FooChain
}
func (f FooChain) Bar() {
if f.child != nil {
f.child.Bar()
}
f.Foo.Bar()
}
func main() {
fmt.Println("no children")
f := new(FooChain)
f.Bar()
for i := 0; i < 10; i++ {
f = &FooChain{Foo{}, f}
}
fmt.Println("with children")
f.Bar()
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论