1 定义

CAS(compare and swap)顾名思义,是比较和交换的意思,它是操作系统自带的基于CPU指令级别封装的一种算法。 在x86 体系下的linux中使用 cmpxchgl指令完成的。 下面我们就CAS原理和具体是实现进行分析。

2 原理

说道CAS算法,不得不提到乐观锁,也许CAS是乐观锁最好的一种实现。先来了解下乐观锁,乐观锁即是假设每次读取数据时其它线程都没修改数据,直接对数据进行更新操作。实际实现后,乐观锁可以在不加锁(即不用挂起其它线程),在保证数据一致性的前提下,对数据进行更新操作。

c++中实现cas用的是这样一个函数:

[boolean] compare_and_swap(x, addr, e );

chart 2-1 Principle of algorithm CAS

函数的参数有三个,新值x,地址addr, 旧值e, 先从内存中读取addr地址的值e1,比较e1和e是否相当相等,相等则替换成新值x,返回true, 不相等则重新从地址addr中取值,返回false,不断重试,直至返回true。