锁机制：atomic 和 CAS

锁机制

常用的锁机制有两种：悲观锁、乐观锁

1、悲观锁

假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。
悲观锁的实现，往往依靠底层提供的锁机制。
悲观锁会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
主要有 互斥锁、自旋锁、读写锁、原子操作等。

2、乐观锁

假设不会发生并发冲突，每次不加锁而是假设没有冲突而去完成某项操作，只在提交操作时检查是否违反数据完整性。
如果因为冲突失败就重试，直到成功为止。
乐观锁大多是基于数据版本记录机制实现。
为数据增加一个版本标识，比如在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。
此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
乐观锁的缺点是不能解决脏读的问题。
在实际生产环境里边,如果并发量不大且不允许脏读，可以使用悲观锁解决并发问题。
主要有CAS等。
如果系统的并发非常大的话,悲观锁定会带来非常大的性能问题,所以我们就要选择乐观锁定的方法

3、锁机制存在的问题

在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。
一个线程持有锁会导致其它所有需要此锁的线程挂起。
如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。

4、CAS

4.1、CAS的基本原理

高并发服务器经常用到多线程编程，需要对共享数据进行操作，为了保证数据的正确性，有一种有效的方法就是加锁机制，但是这种方式存在以下一些缺点：

在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题；
一个线程锁持有锁会导致其它所有所有需要此锁的线程挂起；
如果一个优先级较高的线程等待一个优先级低的线程释放锁，会导致优先级倒置，引起性能风险；
为了解决多线程并行情况下使用锁造成性能损耗的问题,我们引入了CAS机制（Compare and Swap）

4.2、CAS结构

CAS包含三个操作数：

内存位置 (V) ------ 是个指针
预期原值 (A)
新值（B）
如果内存位置V内保存的值与预期原值相匹配，那么处理器会总动将内存位置V处的值更新为新值；否则处理器不做任何操作。

无论哪种情况，它都会返回内存位置原来保存的值。

示例如下,判断内存reg里的值是不是oldval,如果是的话,则对其赋值newval。

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if(old_reg_val == oldval)
     *reg = newval;
     
  return old_reg_val;
}

这个操作可以变种为返回bool值的形式(返回bool值的好处在于,调用者可以知道有没有更新成功) :

bool compare_and_swap (int* reg, int oldval, int newval)
{
  if(*reg == oldval)
  {
  	 *reg = newval;
  	 return true;
  }
  return false;
}

CAS是一种有名的无锁算法。无锁编程，即不适用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步。

4.3、CAS总结如下：

CAS（Compare and Swap）比较并替换，是线程并发运行时用到的一种技术；
CAS是原子操作，保证并发安全，而不能保证并发同步；
CAS是CPU的一个指令；
CAS是非阻塞的，轻量级的乐观锁；

4.4、ABA问题

4.4.1 所谓ABA问题如下：

线程P1在共享变量中读到值为A；
线程P1被抢占了，线程P2执行，P2把共享变量的值从A改成了B；
线程P3将共享变量又从B改回到A，此时被P1抢占；
P1回来看到共享变量里面的值没有被改变，于是继续执行；

4.4.2 现实场景：

小明银行卡里有100元，此时小明需要取50元，由于系统阻塞，取操作执行两次；
在第一次取操作执行成功后，银行卡里剩下50元，在第二次操作到来之前，小明妈妈往小明卡里转入50元；
第二次操作来临时，发现卡里余额100元，扣除50元，此时卡里还剩50元
小明血亏~~~
虽然P1以为内存地址中的变量值没有改变,继续执行了,但是这个会引发一些潜在的问题。ABA问题最容易发生在lock free的算法中的CAS,因为CAS判断的是指针的地址。如果这个地址被重用,问题就很大了。

为解决ABA为题,我们可以采用具有原子性的内存引用计数等等办法。

4.4.3 解决ABA问题

方法一：维基百科上给了一个解--使用double-CAS (双保险的CAS)

例如,在32位系统上,我们要检查64位的内容.一次用CAS检查双倍长度的值,前半部是指针,后半部分是一个计数器。只有这两个都一样,才算通过检查。

要给内存V处赋新的值，需要并把计数器累加1。这样一来,ABA发生时,虽然值一样,但是计数器就不一样(但是在32位的系统上,这个计数器会溢出回来又从1开始的,这还是会有ABA的问题)

方法二：我们可以在V对象上加上一个版本号，取V对象的时候连版本号也取出来，当V对象每次被修改的时候都将V的版本号进行改变，那样就可以知道V对象有没有被修改过。

4.5、 C/C++程序中，CAS的各种实现版本

GCC的CAS，GCC4.1+版本中支持CAS的原子操作。

1）bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...) 
2）type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

C++11中的CAS，C++11中的STL中的atomic类的函数可以让你跨平台。

template< class T > bool atomic_compare_exchange_weak( std::atomic* obj,T* expected, T desired ); 
template< class T > bool atomic_compare_exchange_weak( volatile std::atomic* obj,T* expected, T desired );

5、原子操作

5.1、概述

原子操作（atomic operation）指的是由多步操作组成的一个操作。如果该操作不能原子地执行，则要么执行完所有步骤，要么一步也不执行，不可能只执行所有步骤的一个子集。

现代操作系统中，一般都提供了原子操作来实现一些同步操作，所谓原子操作，也就是一个独立而不可分割的操作。在单核环境中，一般的意义下原子操作中线程不会被切换，线程切换要么在原子操作之前，要么在原子操作完成之后。更广泛的意义下原子操作是指一系列必须整体完成的操作步骤，如果任何一步操作没有完成，那么所有完成的步骤都必须回滚，这样就可以保证要么所有操作步骤都未完成，要么所有操作步骤都被完成。

例如在单核系统里，单个的机器指令可以看成是原子操作（如果有编译器优化、乱序执行等情况除外）；在多核系统中，单个的机器指令就不是原子操作，因为多核系统里是多指令流并行运行的，一个核在执行一个指令时，其他核同时执行的指令有可能操作同一块内存区域，从而出现数据竞争现象。多核系统中的原子操作通常使用内存栅障（memory barrier）来实现，即一个CPU核在执行原子操作时，其他CPU核必须停止对内存操作或者不对指定的内存进行操作，这样才能避免数据竞争问题。

在C++11之前，C++标准中并没有对原子操作进行规定。vs和gcc编译器提供了原子操作的api。

5.2、原子操作的底层实现

实现方式：基于缓存加锁与总线加锁。

1.总线加锁
所谓总线锁就是使用处理器提供的一个lock#信号，当一个处理器在总线上输出此信号时，其他处理器的请求会被阻塞住，那么该处理器可以独占共享内存。

但总线锁定把cpu和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以开销比较大。

2.缓存加锁
第二个机制是通过缓存锁定来保证原子性。在同一时刻，我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把CPU和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

频繁使用的内存会缓存在处理器的L1、L2和L3高速缓存里，那么原子操作就可以直接在处理器内部缓存中进行，并不需要声明总线锁，在Pentium 6和目前的处理器中可以使用“缓存锁定”的方式来实现复杂的原子性。所谓“缓存锁定”是指内存区域如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不在总线上声言LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效，在如图2-3所示的例子中，当CPU1修改缓存行中的i时使用了缓存锁定，那么CPU2就不能同时缓存i的缓存行。

但是有两种情况下处理器不会使用缓存锁定。

第一种情况是：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行（cache line）时，则处理器会调用总线锁定。

第二种情况是：有些处理器不支持缓存锁定。对于Intel 486和Pentium处理器，就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

针对以上两个机制，我们通过Intel处理器提供了很多Lock前缀的指令来实现。例如，位测试和修改指令：BTS、BTR、BTC；交换指令XADD、CMPXCHG，以及其他一些操作数和逻辑指令（如ADD、OR）等，被这些指令操作的内存区域就会加锁，导致其他处理器不能同时访问它。

5.3、C++11提供的原子操作：

C++11中在中定义了atomic模板类，atomic的模板参数类型可以为int、long、bool等等，C++中称为trivially copyable type。atomic_int、atomic_long为atomic模板实例化后的宏定义。atomic具体的原子操作函数可以参考 http://www.cplusplus.com/reference/atomic/atomic/?kw=atomic。

#include <stdio.h>
 
#if 0
 
gcc数值原子操作API原理及应用
n++类：
	type __sync_fetch_and_add(type* ptr, type value, ...);// m+n
	type __sync_fetch_and_sub(type* ptr, type value, ...);// m-n
	type __sync_fetch_and_or(type* ptr, type value, ...);  // m|n
	type __sync_fetch_and_and(type* ptr, type value, ...);// m&n
	type __sync_fetch_and_xor(type* ptr, type value, ...);// m^n
	type __sync_fetch_and_nand(type* ptr, type value, ...);// (~m)&n
	/* 对应的伪代码 */
	{tmp = *ptr; *ptr op = value; returntmp; }
	{tmp = *ptr; *ptr = (~tmp) & value; returntmp; }   // nand
 
++n类：
	type __sync_add_and_fetch(type* ptr, type value, ...);// m+n
	type __sync_sub_and_fetch(type* ptr, type value, ...);// m-n
	type __sync_or_and_fetch(type* ptr, type value, ...);// m|n
	type __sync_and_and_fetch(type* ptr, type value, ...);// m&n
	type __sync_xor_and_fetch(type* ptr, type value, ...);// m^n
	type __sync_nand_and_fetch(type* ptr, type value, ...);// (~m)&n
	/* 对应的伪代码 */
	{*ptr op = value; return*ptr; }
	{*ptr = (~*ptr) & value; return*ptr; }// nand
 
CAS类：
	bool__sync_bool_compare_and_swap(type* ptr, type oldval, type newval, ...);
	type __sync_val_compare_and_swap(type* ptr, type oldval, type newval, ...);
	/* 对应的伪代码 */
	{if (*ptr == oldval) { *ptr = newval; returntrue; } else { returnfalse; }}
	{if (*ptr == oldval) { *ptr = newval; }returnoldval; }
 
#endif
 
int main() 
{
	int num = 0;
 
	/*
	 * n++;
	 * __sync_fetch_and_add(10, 3) = 10
	 * num = 13
	 */
 
	num = 10;
	printf("__sync_fetch_and_add(%d, %d) = %d\n", 10, 3, __sync_fetch_and_add(&num, 3));
	printf("num = %d\n", num);
 
	/*
	 * ++n;
	 * __sync_and_add_and_fetch(10, 3) = 13
	 * num = 13
	 */
 
	num = 10;
	printf("__sync_and_add_and_fetch(%d, %d) = %d\n", 10, 3, __sync_add_and_fetch(&num, 3));
	printf("num = %d\n", num);
 
	/*
	 * CAS, match
	 * __sync_val_compare_and_swap(10, 10, 2) = 10
	 * num = 2
	 */
 
	num = 10;
	printf("__sync_val_compare_and_swap(%d, %d, %d) = %d\n", 10, 10, 2, __sync_val_compare_and_swap(&num, 10, 2));
	printf("num = %d\n", num);
 
	/*
	 * CAS, not match
	 * __sync_val_compare_and_swap(10, 3, 5) = 10
	 * num = 10
	 */
 
	num = 10;
	printf("__sync_val_compare_and_swap(%d, %d, %d) = %d\n", 10, 3, 5, __sync_val_compare_and_swap(&num, 1, 2));
	printf("num = %d\n", num);
 
	return 0;
}

资料：
https://blog.csdn.net/anyegongjuezjd/article/details/125919162
https://zhuanlan.zhihu.com/p/400817892?utm_id=0
https://zhuanlan.zhihu.com/p/590291482
https://blog.csdn.net/weixin_44479862/article/details/128058413
https://zhuanlan.zhihu.com/p/463913671

本栏目推荐文章
• 从C++CLI工程的依赖库引用问题看.Net加载程序集机制
• Go语言defer的延迟执行机制
• 基于k8s Deployment的弹性扩缩容及滚动发布机制详解
• 22-安全机制：Kubernete 如何保障集群安全？
• js 垃圾回收机制
• SpringBoot中使用SpringRetry实现重试机制(重试调用第三方API)
• 详解GaussDB(DWS)通信安全的小妙招：连接认证机制
• 什么是刷新缓存机制
• 消息缓存机制有什么好处
• 什么情况用到缓存机制

机制 atomic CAS机制atomic cas 机制cas 机制jvm cas 机制sso cas 原理 机制cas atomic atom cas atomically 前端atom