CAS и неблокирующий счетчик

Question

Я читал JCIP Брайана Гетца.Он объясняет реализацию неблокирующего счетчика, используя инструкцию CAS.Я не мог понять, как происходит приращение с использованием инструкции CAS.Может ли кто-нибудь помочь мне понять это.

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

Answer 1

value.compareAndSwap(v, v + 1) эквивалентно следующему, за исключением того, что весь блок является атомарным: (см. сравнение и замена для деталей)

int old = value.val;
if (old == v) {
  value.val = v + 1;
}
return old;

Теперь v = value.get() получает текущее значение счетчика, и, если никто не пытается обновить счетчик одновременно, old == v будет истинным, поэтому значение установлено на v+1 (т.е. увеличивается) и old возвращается. Цикл заканчивается с v == old.

Предположим, кто-то еще увеличил счетчик сразу после того, как мы сделали v = value.get(), тогда old == v будет ложным, и метод немедленно вернет old, что является обновленным значением. Начиная с v != old, цикл продолжается.

Answer 2

Метод compareAndSwap() будет выполнять следующие операции атомарно:

- determine if `value` is equal to `v`
- if so, it will set `value` to `v+1`
- it returns whatever `value` was when the method was entered (whether or not `value` was updated)

Вызывающий может проверить, было ли value ожидаемым, когда он вызвал compareAndSwap(). Если это так, то вызывающая сторона знает, что она обновлена. Если это не то, что ожидалось, вызывающая сторона знает, что она не была обновлена, и попытается снова, используя «новое» текущее значение value в качестве ожидаемого (это то, что делает цикл).

Таким образом, вызывающая сторона может знать, что операция приращения не теряется другим потоком, который пытается изменить value в тот же момент.