Fasting in non-blocking approaches

Question

I read about non-blocking approaches for some time. Here is a code snippet for a so-called block 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'm just curious about this loop:

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

People says:

So, he tries again and again until all the other threads trying to change the value have done so. This is blocked because the lock is not used, but not blocked, as you may need to retry (which is rare) more than once (very rarely).

My question is:

How can they be so sure of this? For me, I see no reason why this loop cannot be infinite, unless the JVM has special mechanisms to solve this problem.

Answer 1

The cycle can be endless (since it can generate hunger for your flow), but the likelihood of this happening is very small. In order for you to get hunger, you will need another thread that will change the value you want to update between your reading and your store, and repeat for that.

One could write code to cause hunger, but for real programs this is unlikely to happen.

Comparison and swap are usually used when you do not think that you will have write conflicts very often. Let's say that there is a 50% chance of a “miss” during the upgrade, that is, a 25% chance that you will miss two loops and a less than 0.1% chance that the upgrade will fail in 10 cycles. For examples in the real world, 50% of missed rates are very high (basically they do nothing but update), and since the miss speed decreases, say, 1%, the risk of not succeeding in two attempts is only 0.01%, and in 3 tries 0.0001%.

Usage is similar to the following problem

Set the variable a to 0 and add two threads, updating them with a = a + 1 million times each at a time. At the end, a can have any response between 1,000,000 (every other update was lost due to overwriting) and 2,000,000 (the update was not overwritten).

The closer you get to 2,000,000, the more likely you are to use CAS, as this means that CAS often sees the expected value and can set a new value.

Answer 2

Change I think I have a satisfactory answer. The bit that confused me was "v! = CompareAndSwap". In valid code, CAS returns true if the value is equal to the expression being compared. Thus, even if the first thread is interrupted between get and CAS, the second thread will be successfully replaced and exit the method, so the first thread will be able to execute CAS.

Of course, it is possible that if two threads call this method an infinite number of times, one of them will not be able to run CAS at all, especially if it has a lower priority, but this is one of the risks of unfair blocking (the probability is very low). As I said, the queue mechanism can solve this problem.

Sorry for the initial erroneous assumptions.