使用原子CAS (比较和交换)操作实现getAndUpdate()的无锁实现

Question

我们使用新的内存管理器(不需要冻结对象)用Kotlin本机编写了以下类：

import kotlin.native.concurrent.AtomicReference

class AtomicRef<V>(initialValue: V) {

    private val atom = AtomicReference(initialValue)

    /**
     * Get the current value
     */
    fun get(): V = atom.get()

    /**
     * Atomically compare the current value with `expected`, 
     * and set it to `new` if the current and the expected values are the same.
     *
     * @return `true` if successful, `false` return indicates that
     *   the actual value was not equal to the expected value.
     */
    fun compareAndSet(expected: V, new: V): Boolean = 
        atom.compareAndSet(expected, new)

    /**
     * Atomically compare the current value with `expected`, 
     * and set it to `new` if the current and the expected values are the same.
     *
     * @return the witness value, 
     *   which will be the same as the `expected` value if successful.
     */
    fun compareAndExchange(expected: V, new: V): V =
        atom.compareAndSwap(expected, new)

    /**
     * Atomically updates the current value with the results 
     * of applying the given function, returning the previous value.
     *
     * @param updateFunction a side-effect-free function
     * @return the previous value
     */
    fun getAndUpdate(updateFunction: (V) -> V): V {
        while(true) {
            val prev = get()
            val next = updateFunction(prev)
            if (compareAndSet(prev, next)) return prev
        }
    }
}

compareAndSet和compareAndExchange实现将委托给相应的Kotlin stdlib AtomicReference方法(分别为compareAndSet和compareAndSwap )，这些方法提供了本机不带bug和不带活锁的实现。

getAndUpdate实现是众所周知的，可以在j.u.c.AtomicReference类或JetBrains的atomicfu库中找到。

我希望重写getAndUpdate()函数的实现，以使用compareAndExchange，并避免在每次循环迭代中调用get()。

我提出了以下实现：

    fun getAndUpdate(updateFunction: (V) -> V): V {
        var prev = get()
        while(true) {
            val expected = prev
            val next = updateFunction(expected)
            prev = compareAndExchange(expected, next)
            if (prev == expected) return prev
        }
    }

它是正确的吗?它的工作方式是否与使用compareAndSet的方法相同？

更新

我在带讨论的票证跟踪器中找到了一个OpenJDK，其中一个OpenJDK成员建议为AtomicInteger.getAndUpdate提供类似的Java实现：

公共最终int getAndUpdate(IntUnaryOperator updateFunction) { for (int = get()；){ int = updateFunction.applyAsInt (prev )；if (prev == ( prev = compareAndExchange(prev，next )返回prev；}当compareAndExchange被编译为本机指令时，这似乎是最优的。如果没有，并且硬件存在虚假的故障，compareAndExchange会被编译成一个循环，但是在失败时不会浪费额外的易失性读取，因为读取的值会返回给我们的循环。如果这不是compareAndExchange的一个很好的用例，那么什么是？它现在还没用。

上面的Java代码可以用Kotlin表示为：

fun getAndUpdate(updateFunction: (V) -> V): V {
    var prev = get()
    while (true) {
        val next = updateFunction(prev)
        val witnessed = compareAndExchange(prev, next)
        if (prev == witnessed) return prev
        prev = witnessed
    }
}

这与我计划用于getAndUpdate的代码非常接近。

Answer 1

可以使用getAndUpdate()方法重写compareAndExchange()函数，如下所示：

fun getAndUpdate(updateFunction: (V) -> V): V {
    var prev: V
    var next: V
    do {
       prev = compareAndExchange(null as V, null as V)
       next = updateFunction(prev)
    } while (!compareAndSet(prev, next))
    return prev
}

在这里，getAndUpdate()函数现在使用compareAndExchange()方法。它将尝试在循环中执行更新，直到compareAndSet()方法返回true为止，这意味着更新是成功的。使用空值调用compareAndExchange()方法以获得当前值，而不对其进行修改，从而有效地替换了get()调用。