CompareAndSet

link
Q: AtomicInteger底层原理？什么是CAS, 怎么使用CAS?

Atomic*

• AtomicInteger对int类型的封装，提供原子性的读取和更新操作

// 不能保证原子性
public class MyApp {
    private int count = 0;
    public void upateVisitors() 
    {
       ++count; //increment the visitors count
    }
}

// 保证原子性但性能很差
public class MyApp {
    private int count = 0;
    public synchronized void upateVisitors() 
    {
       ++count; //increment the visitors count
    }
}

// 保证原子性，同时提升性能
public class MyApp {
    private AtomicInteger count = new AtomicInteger(0);
    public void upateVisitors() 
    {
       count.incrementAndGet(); //increment the visitors count
    }
}

• 底层用的CAS技术实现

Compare the value of the primitive to the value we have got in hand. 对比已有的值
If the values do not match it means some thread in between has changed the value. Else it will go ahead and swap the value with new value. 如果不匹配说明有其他线程修改了这个值然后返回，否则交换新的值

// jdk8  之前
public final long incrementAndGet() {
    for (;;) {
        long current = get();
        long next = current + 1;
        if (compareAndSet(current, next))
          return next;
    }
}
// jdk8
public final long incrementAndGet() {
    return unsafe.getAndAddLong(this, valueOffset, 1L) + 1L;
}
// JIT编译器会转化为优化的指令序列，在X86的机器上就是一个CPU 指令LOCK XADD，比代码级别的cas loop性能更好

LongAdder

替代AtomicLong的方案
When no contention is present AtomicLong performs better
This class is usually preferable to AtomicLong when multiple threads update a common sum that is used for purposes such as collecting statistics, not for fine-grained synchronization control
LongAdder will allocate Cells (a final class declared in abstract class Striped64) to avoid contention which consumes memory. So in case we have a tight memory budget we should prefer AtomicLong

CAS原理

There are 3 parameters for a CAS operation:
1、A memory location V where value has to be replaced
2、Old value A which was read by thread last time
3、New value B which should be written over V

CAS says “I think V should have the value A; if it does, put B there, otherwise don’t change it but tell me I was wrong.” CAS is an optimistic technique—it proceeds with the update in the hope of success, and can detect failure if another thread has updated the variable since it was last examined.

@Linkhowtodoinjava.com/core-java/multi-threading/compare-and-swap-cas-algorithm

public final int getAndIncrement() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return current;
    }
}

// 上述的CAS代码中，当多个线程调用compareAndSet时，只有一个线程会成功，其他失败，然后进入for循环继续尝试，这个就是自旋锁的逻辑，锁内部的逻辑时间不能太长，否则会导致其他线程一直循环消耗CPU资源
// The confusing infinite loop for(;;) will only really loop if many threads are writing to the variable at the same time. Under very heavy load it may loop around several times but it should complete quite quickly.

CAS使用

• Atomic*FieldUpdater

  public class CASDemo {
      private static final AtomicLongFieldUpdater<CASDemo> UPDATER = AtomicLongFieldUpdater.newUpdater(CASDemo.class, "lock");
  
      private volatile long lock;
  
      public void acquireLock() {
          Long id = Thread.currentThread().getId();
          System.out.println(String.format("线程%s进入获取锁", id));
          while (!UPDATER.compareAndSet(this, 0L, id)) {
          }
          System.out.println(String.format("线程%s获取锁", id));
      }
  
      public void releaseLock() {
          Long id = Thread.currentThread().getId();
          System.out.println(String.format("线程%s进入释放锁", id));
          while (!UPDATER.compareAndSet(this, id, 0L)) {
          }
          System.out.println(String.format("线程%s释放锁", id));
      }
  
      public static void main(String[] args) {
          CASDemo demo = new CASDemo();
          Runnable runnable = () -> {
              demo.acquireLock();
              for (int i = 0; i < 3; i++) {
                  System.out.println(i);
                  try {
                      Thread.sleep(100);
                  } catch (InterruptedException e) {
                      e.printStackTrace();
                  }
              }
              demo.releaseLock();
          };
          new Thread(runnable).start();
          new Thread(runnable).start();
      }
  }
  // 不使用acquireLock、releaseLock的输出结果
  0
  0
  1
  1
  2
  2
  // 使用acquireLock、releaseLock的输出结果
  线程11进入获取锁
  线程12进入获取锁
  线程11获取锁
  0
  1
  2
  线程11进入释放锁
  线程11释放锁
  线程12获取锁
  0
  1
  2
  线程12进入释放锁
  线程12释放锁

lock-free机制

link

ABA 问题