java - 无障碍方法中的饥饿

我已经阅读了一段时间的非阻塞方法。这是所谓的无锁计数器的一段代码。

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有一些特殊的机制可以解决这个问题，否则我看不出为什么这个循环不能无限长的原因。

最佳答案

循环可以是无限的(因为它可以为您的线程产生饥饿)，但是这种情况发生的可能性很小。为了使您挨饿，您需要一些其他线程来成功更改您要在读取和存储之间更新的值，并使其重复发生。

可能会编写代码来触发饥饿，但对于实际程序而言，这不太可能发生。

当您认为自己不会经常发生写冲突时，通常使用比较和交换。假设您更新时有50％的“未命中”机会，那么有25％的机会您将在两个循环中错过，而有0.1％的机会没有更新会在10个循环中成功。对于现实世界中的示例，50％的未命中率非常高(基本上没有做任何事情都只能进行更新)，并且随着未命中率的降低(例如1％)，两次尝试均不成功的风险仅为0.01％，而3次失败尝试0.0001％。

用法类似于以下问题

将变量a设置为0，并让两个线程同时以a = a + 1对其进行一百万次更新。最后，答案可能介于1000000(由于覆盖而丢失所有其他更新)到2000000(没有覆盖任何更新)之间。

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