英文:
Does the following lock-free code exhibit a race-condition?
问题
在Kubernetes Go repo on Github.com中，有一个无锁的HighWaterMark数据结构实现。该代码依赖原子操作来实现无数据竞争的线程安全代码。
// HighWaterMark是一个用于跟踪某个数量的最大值的线程安全对象。
type HighWaterMark int64
// Update仅在'current'是迄今为止观察到的最高值时返回true。
func (hwm *HighWaterMark) Update(current int64) bool {
for {
old := atomic.LoadInt64((*int64)(hwm))
if current <= old {
return false
}
if atomic.CompareAndSwapInt64((*int64)(hwm), old, current) {
return true
}
}
}
该代码依赖于标准库中的atomic.LoadInt64和atomic.CompareAndSwapInt64函数来实现无数据竞争的代码...我相信它确实做到了，但我认为还存在另一个竞争条件的问题。
如果两个竞争的线程（goroutines）正在执行此代码，存在一种边缘情况，即在第一个线程中的atomic.LoadInt64之后，第二个线程可能已经交换出一个更高的值。但在第一个线程认为current int64实际上比old int64大之后，将会发生一次交换。由于观察到了过时的old值，这个交换将有效地降低存储的值。
英文:
Within the Kubernetes Go repo on Github.com,
There is a lock-free implementation of a HighWaterMark data-structure. This code relies on atomic operations to achieve thread-safe code that is free of data races.
// HighWaterMark is a thread-safe object for tracking the maximum value seen
// for some quantity.
type HighWaterMark int64
// Update returns true if and only if 'current' is the highest value ever seen.
func (hwm *HighWaterMark) Update(current int64) bool {
for {
old := atomic.LoadInt64((*int64)(hwm))
if current <= old {
return false
}
if atomic.CompareAndSwapInt64((*int64)(hwm), old, current) {
return true
}
}
}
This code relies on the atomic.LoadInt64 and atomic.CompareAndSwapInt64 functions within the standard library to achieve data race free code...which I believe it does but I believe there is another problem of a race condition.
If two competing threads (goroutines) are executing such code there exists an edge case where after the atomic.LoadInt64 occurs in the first thread, the second thread could have swapped out for a higher value. But after the first thread thinks the current int64 is actually larger than the old int64 a swap will happen. This swap would then effectively lower the stored value due to observing a stale old value.
答案1
得分: 1
如果另一个线程在中间插入，CompareAndSwap 将失败，循环将重新开始。
将 CompareAndSwap 想象为：
if actual == expected {
actual = newval
}
但是以原子方式执行。
因此，这段代码的含义是：
old = hwm // 以线程安全的原子读取方式执行
if old < current {
如果 hwm == old，则将 hwm 设置为 current // 原子比较并设置值
}
当 CAS（CompareAndSwap）失败时，它返回 false，导致循环重新开始，直到满足以下条件之一：
a) "current" 不大于 hwm
或者
b) 成功执行 Load，然后在没有其他线程插入的情况下执行 CompareAndSwap
英文:
If another thread got in the middle, the CompareAndSwap would fail and the loop would start over.
Think of CompareAndSwap as
if actual == expected {
actual = newval
}
but done atomically
So this code says:
old = hwm // but done in a thread safe atomic read way
if old < current {
set hwm to current if hwm == old // atomically compare and then set value
}
when CAS (CompareAndSwap) fails, it returns false, causing the loop to start over until either:
a) "current" is not bigger than hwm
or
b) It successfully performs Load and then CompareAndSwap without another thread in the middle
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论