java - 非阻塞方法中的饥饿

Question

一段时间以来，我一直在阅读有关非阻塞方法的内容。这是所谓的无锁计数器的一段代码。

public class CasCounter {
private SimulatedCAS value;

public int getValue() {
    return value.get();
}

public int increment() {
    int v;
    do {
        v = value.get();
    }
    while (v != value.compareAndSwap(v, v + 1));
    return v + 1;
}

我只是想知道这个循环:

do {
    v = value.get();
}
while (v != value.compareAndSwap(v, v + 1));

人们说:

因此它会一次又一次地尝试，直到所有其他尝试更改该值的线程都已完成。这是无锁的，因为没有使用锁，但不是无锁的，因为它可能必须重试(这种情况很少见)不止一次(非常罕见)。

我的问题是:

他们怎么能这么确定呢？至于我，我看不出有任何理由说明这个循环不能是无限的，除非 JVM 有一些特殊的机制来解决这个问题。

Answer 1

循环可以是无限的(因为它会导致线程饥饿)，但发生这种情况的可能性非常小。为了让你饿死，你需要一些其他的线程来成功地改变你想要在你的阅读和你的商店之间更新的值，并让这种情况重复发生。

编写代码来触发饥饿是可能的，但对于真实的程序来说，这不太可能发生。

比较和交换通常在您认为不会经常发生写入冲突时使用。假设更新时有 50% 的机会“错过”，那么有 25% 的机会在两次循环中错过，而不到 0.1% 的机会在 10 次循环中没有更新成功。对于现实世界的例子，50% 的失误率非常高(基本上除了更新什么都不做)，随着失误率的降低，比如说 1% 那么两次尝试不成功的风险只有 0.01% 而在 3尝试 0.0001%。

用法类似下面的问题

将变量 a 设置为 0 并让两个线程同时用 a = a+1 更新它一百万次。最后，a 可能有 1000000(所有其他更新因覆盖而丢失)和 2000000(没有更新被覆盖)之间的任何答案。

越接近 2000000，CAS 使用的可能性就越大，因为这意味着 CAS 经常会看到预期值并能够设置新值。