CAS是 "比较和交换 "的意思,该算法在设计并发算法时较为常用,CAS算法的本质是将变量的实际值与变量的预期值进行比较,如果实际值与预期值相符,则将变量的实际值赋值成传入的新值。例如我知道这个变量应该是3,我想把它改成4,但是由于这是一个多线程环境,我知道其他人可能正在处理同一个变量,所以我首先检查这个变量的值是否和我想的一样是3,如果是,那么我就把它改成4,如果我看到这个变量现在是5,那么这意味着其他人正在处理它,所以让我现在不要碰它。
当多个线程同时使用CAS操作一个变量时,只有一个线程会成功更新,其余的会更新失败,更新失败的线程不会被暂停,而是继续尝试操作,当然,更新失败的线程也可以提前返回,所以CAS算法是非阻塞的,基于上述原则,CAS操作可以在没有锁的帮助下实现适当的并发处理。
ABA问题
ABA问题是CAS算法的一个缺点。实现CAS算法的一个重要前提是在某一时刻取出内存中的数据,并在下一时刻进行比较和替换,在这个时间差中,数据可能发生变化。假设有两个线程需要对内存中的一个变量进行CAS操作,线程一首先从内存中获得变量A的值a,线程二也从内存中获得变量A的值a,并将变量A的值a修改为b,完成一系列操作之后将b再改为a,此时,线程一进行CAS操作,发现内存中变量A的值仍然是a,于是认为与预期值一致,操作成功。虽然线程一的CAS操作是成功的,但这并不意味着这个过程中没有问题。
ABA问题可以通过版本号来解决,每一次数据被修改,都会带来一个版本号。如果版本号与数据版本一致,则数据被修改,版本号为+1,否则执行失败,因为每次操作的版本号都会增加,所以不需要担心ABA问题。
使用java模拟CAS算法;
class CompareAndSwap { private int value; //获取内存值 public synchronized int get() { return value; } //交换 public synchronized int compareAndSwap(int expectedValue, int newValue) { //获得内存值 int oldValue = value; //比较 if (oldValue == expectedValue) { this.value = newValue; } return oldValue; } //cas public synchronized boolean compareAndSet(int expectedValue, int newValue) { return expectedValue == compareAndSwap(expectedValue, newValue); } } public class TestCompareAndSwap { private static CompareAndSwap cas = new CompareAndSwap(); public static void main(String[] args) { for (int i = 0; i < 10; i++) { new Thread(new Runnable() { public void run() { int expectedValue = cas.get(); boolean b = cas.compareAndSet(expectedValue, (int) (Math.random() * 101)); System.out.println(b); } }).start(); } } }