何为面试必问的CAS算法？

CSA算法

- CAS(Compare-And-Swap) 算法是硬件对于并发的支持,针对多处理器操作而设计的处理器中的一种特殊指令,用于管理对共享数据的并发访问;
- CAS 是一种无锁的非阻塞算法（属于乐观锁）的实现;
- CAS 包含了三个操作数:
  - 进行比较的旧预估值: A
  - 需要读写的内存值: V
  - 将写入的更新值: B
  - 当且仅当 A == V 时, V = B, 否则,将不做任何操作,并且这个比较交换过程属于原子操作;
           

CAS算法简介

CAS是乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。　　　 
           

代码理解：

run(){
	System.out.println(num++);  // 1.把num读到寄存器存储在a  2.定义一个变量b使它等于a+1                    3.num=b
}

非原子性会造成的问题：
如果A线程执行到把num读到寄存器，此时b线程抢到资源，num还未加一，b执行后打印的为+1后的值，然后线程A继续执行，把寄存器中的a加一后，赋给num输出，打印的也为+1后的值。所以会造成输出两次相同数值的情况
解决办法：1.加同步锁，但是执行效率慢
		2.CAS算法：
		　假如：AtomicInteger(原子变量)里面的value原始值为3，即主内存中AtomicInteger的value为3，根据Java内存模型，线程A和线程B各自持有一份value的副本，值为3。 
线程A通过getIntVolatile(var1, var2)拿到value值3，这时线程A被挂起。 
线程B也通过getIntVolatile(var1, var2)方法获取到value值3，运气好，线程B没有被挂起，并执行compareAndSwapInt方法比较内存值也为3，成功修改内存值为2。 
这时线程A恢复，执行compareAndSwapInt方法比较，发现自己手里的值(3)和内存的值(2)不一致，说明该值已经被其它线程提前修改过了，那只能重新来一遍了。 （继续拿现在存的value的值）
重新获取value值，因为变量value被volatile修饰，所以其它线程对它的修改，线程A总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。
           

实现代码：(看)

public class CompareAndSwapDemo {
	public static void main(String[] args) {
		CompareAndSwap compareAndSwap = new CompareAndSwap();
		for (int i = 0; i < 10; i++) {
			new Thread(new Runnable() {
				@Override
				public void run() {

					int expect = compareAndSwap.get();
					boolean b = compareAndSwap.compareAndSwap(expect, new Random().nextInt(101));
					System.out.println(b);
				}
			}).start();
		}
	}
}

class CompareAndSwap {
	private int value;

	/**
	 * 获取值
	 * 
	 * @return
	 */
	public synchronized int get() {
		return value;
	}

	public synchronized boolean compareAndSwap(int expect, int newValue) {
        
		if (this.value == expect) {       //if内的代码经过底层加工(CPU指令代码完成)，为原子性的
			this.value = newValue;
			return true;
		}
		return false;
	}
}
           

ABA问题:

• 在CAS算法中，需要取出内存中某时刻的数据（由用户完成），在下一时刻比较并替换（由CPU完成，该操作是原子的）。这个时间差中，会导致数据的变化。

  假设如下事件序列：

  线程 1 从内存位置V中取出A。

  线程 2 从位置V中取出A。

  线程 2 进行了一些操作，将B写入位置V。

  线程 2 将A再次写入位置V。

  线程 1 进行CAS操作，发现位置V中仍然是A，操作成功。

尽管线程 1 的CAS操作成功，但不代表这个过程没有问题——对于线程 1 ，线程 2 的修改已经丢失。

典型的ABA问题，也是很明显的

如果变量V初次读取的时候是A，并且在准备赋值的时候检查到它仍然是A，那能说明它的值没有被其他线程修改过了吗？

如果在这段期间曾经被改成B，然后又改回A，那CAS操作就会误认为它从来没有被修改过。针对这种情况，java并发包中提供了一个带有标记的原子引用类AtomicStampedReference，它可以通过控制变量值的版本来保证CAS的正确性。AtomicStampedReference通过包装[E,Integer]的元组来对对象标记版本戳stamp，从而避免ABA问题。

public class AbaDemo {
	private static AtomicStampedReference<Integer> integer=new AtomicStampedReference<Integer>(0, 0);
	public static void main(String[] args) throws Exception{
		for(int i=0;i<100;i++) {		
			//Thread.sleep(10);
			new Thread(new Runnable() {
				@Override
				public void run() {
					while(true) {
						int stamp = integer.getStamp();
						Integer reference = integer.getReference();
						if(integer.compareAndSet(reference, reference+1, stamp, stamp+1)) {
							System.out.println(reference+1);
							break;
						}
					}
				}
			}).start();
		}
	}
}