一、无锁算法
CAS（比较与交换，Compare and swap） 是一种有名的无锁算法。无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。实现非阻塞同步的方案称为“无锁编程算法”（ Non-blocking algorithm）。
相对应的，独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
使用lock实现线程同步有很多缺点：
* 产生竞争时，线程被阻塞等待，无法做到线程实时响应。
* dead lock，死锁。
* live lock。
* 优先级翻转。
* 使用不当，造成性能下降。
当然在部分情况下，目前来看，无锁编程并不能替代 lock。
二、实现级别
非同步阻塞的实现可以分成三个级别：wait-free/lock-free/obstruction-free。
wait-free
是最理想的模式，整个操作保证每个线程在有限步骤下完成。
保证系统级吞吐（system-wide throughput）以及无线程饥饿。
截止2011年，没有多少具体的实现。即使实现了，也需要依赖于具体CPU。
lock-free
允许个别线程饥饿，但保证系统级吞吐。确保至少有一个线程能够继续执行。
wait-free的算法必定也是lock-free的。
obstruction-free
在任何时间点，一个线程被隔离为一个事务进行执行（其他线程suspended），并且在有限步骤内完成。在执行过程中，一旦发现数据被修改（采用时间戳、版本号），则回滚。也叫做乐观锁，即乐观并发控制(OOC)。事务的过程是：1读取，并写时间戳；2准备写入，版本校验；3校验通过则写入，校验不通过，则回滚。
lock-free必定是obstruction-free的。
三、CAS算法
因而在大部分情况下，java中使用Atomic包中的incrementAndGet的性能比用synchronized高出几倍。
四、ABA问题
thread1意图对val=1进行操作变成2，cas(val,1,2)。
thread1先读取val=1；thread1被抢占（preempted），让thread2运行。
thread2 修改val=3，又修改回1。
thread1继续执行，发现期望值与“原值”（其实被修改过了）相同，完成CAS操作。
使用CAS会造成ABA问题，特别是在使用指针操作一些并发数据结构时。
解决方案
ABAʹ：添加额外的标记用来指示是否被修改。
从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3380.html