CAS(compare-and-swap)简介
通常提到并发编程,在数据的一致性上面,都会考虑用加锁方式在解决。在这里,对锁的解决方案就不多提了,其优势在于编程简单,java里面解决方案很多,synchronized关键字或者Lock都能提供原子化操作语意,c/c++也能简单的使用mutex来方便解决。但其劣势也非常明显,加锁其实并不耗时间,但是其容易造成资源等待,等待是非常耗时的,不合理的设计还容易造成死锁。在查看java.util.concurrent里面的并发容器源代码的时候,发现其实现均是lock-free的,遂深入了解一下lock-free的原子操作。
CAS(compare-and-swap)的原理是比较地址上的值是否是期望的值,如果是,则更新该地址上的值为一个新的值。用c语言描述就是下面模型
bool compare_and_swap(T *ptr, T old_value, T new_value)
{
if(ptr && *ptr == old_value)
{
*ptr = new_value;
return true;
}
return false;
}
注意,这只是描述CAS操作,他并不是用C语言实现的一个function,而是在底层操作系统提供的原子化操作,换种说法,你可以将其看成是一条机器命令的封装。
下面,就来说一下CAS操作在java,c/c++的支持。
在GCC4.1版本之后,包含在stdlib.h中,可以使用bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)和type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)两个函数。
在C++11之后,可以使用stl中atomic类,1)template< class T > bool atomic_compare_exchange_weak( std::atomic<T>* obj,T* expected, T desired );
2)template< class T > bool atomic_compare_exchange_weak( volatile std::atomic<T>* obj,T* expected, T desired );两个函数
比较经典的实例,比如多线程对一个值进行加操作,则可以类似下面的写法:
void atomic_add(int *ptr, int to_add)
{
do
{
int old_value = *ptr;
int new_value = old_value + to_add;
}while(!__sync_bool_compare_and_swap(ptr, old_value, new_value))
}
在java中sun.misc.Unsafe类中,有unsafe.compareAndSwapInt等方法