CAS与乐观锁

1 什么是乐观锁？

说到乐观锁，就不得不先提起悲观锁(Pessimistic Lock)，或者说是悲观并发控制(Pessimistic Concurrency Control，PCC)。悲观锁认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。而乐观版本控制(Optimistic Concurrency Control，OCC)与之相反，认为多线程同时修改共享资源的概率低，因此在访问共享资源前并不加锁，而是在更新数据时验证操作时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。

2 如何实现乐观锁？

实现乐观锁的方式有CAS和版本号机制

2.1 compare-and-swap(CAS)

CAS是一种原子操作，在对一个数据进行更新前，需要先持有这个数据原有值的备份，在进行更新前CAS会比较该数据当前值与备份值是否相同，如果不同则认为被更改，放弃对数据的更新。由于是原子操作，如果有多个线程同时修改一个数据，将会只有一个线程成功。（原子操作通过总线仲裁机制/MESI协议等保证）
CAS过程可以用以下C代码表示：

int cas(long *addr, long old, long new) 
{
    /* Executes atomically. */
    if(*addr != old)
        return 0;
    *addr = new;
    return 1;
}

ABA问题

ABA问题是无锁结构实现中的常见问题，试想两个线程基于cas访问变量A，线程1读取A的值后被挂起，线程2修改A为数值B又改回了A，之后线程1被唤醒，CAS的条件仍然满足，线程1修改了A的变量继续运行。如果只需要考虑开头和结尾一致，这个问题并不重要。
在CAS操作中，由于比较的多是指针，这个问题将会变得更加严重。详见：https://zh.wikipedia.org/zh-hans/比较并交换

2.2 版本号方式

简单来说就是给线程访问的数据增加一个版本标识，可以是版本号也可以是时间戳，当读取数据时将版本号一同读出作为备份，在更新数据之前检查版本号是否和备份相同，如果相同则更新数据，如果不同则认为中间有修改放弃更新。