无障碍方法中的饥饿 [英] Starvation in non-blocking approaches

问题描述

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

I've been reading about non-blocking approaches for some time. Here is a piece of code for so called lock-free counter.

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;
}

}

我只是想知道这个循环:

I was just wondering about this loop:

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

人们说:

因此它会一次又一次尝试，直到所有其他试图更改值的线程都这样做为止.这是无锁的，因为未使用任何锁，但不是无锁的，因为它可能必须重试一次(这种情况很少见)(非常罕见).

So it tries again, and again, until all other threads trying to change the value have done so. This is lock free as no lock is used, but not blocking free as it may have to try again (which is rare) more than once (very rare).

我的问题是:

他们怎么能确定这一点?对我来说，除非JVM有一些特殊的机制可以解决这个问题，否则我看不出为什么这个循环不会无限长.

How can they be so sure about that? As for me I can't see any reason why this loop can't be infinite, unless JVM has some special mechanisms to solve this.

推荐答案

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

The loop can be infinite (since it can generate starvation for your thread), but the likelihood for that happening is very small. In order for you to get starvation you need some other thread succeeding in changing the value that you want to update between your read and your store and for that to happen repeatedly.

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

It would be possible to write code to trigger starvation but for real programs it would be unlikely to happen.

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

The compare and swap is usually used when you don't think you will have write conflicts very often. Say there is a 50% chance of "miss" when you update, then there is a 25% chance that you will miss in two loops and less than 0.1% chance that no update would succeed in 10 loops. For real world examples, a 50% miss rate is very high (basically not doing anything than updating), and as the miss rate is reduces, to say 1% then the risk of not succeeding in two tries is only 0.01% and in 3 tries 0.0001%.

用法类似于以下问题

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

Set a variable a to 0 and have two threads updating it with a = a+1 a million times each concurrently. At the end a could have any answer between 1000000 (every other update was lost due to overwrite) and 2000000 (no update was overwritten).

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

The closer to 2000000 you get the more likely the CAS usage is to work since that mean that quite often the CAS would see the expected value and be able to set with the new value.

这篇关于无障碍方法中的饥饿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！