乐观锁 CAS 实现原理

CAS: 比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

# 悲观锁和乐观锁

# 1. 悲观锁

悲观锁（Pessimistic Lock），顾名思义，就是很悲观，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会block直到它拿到锁。
悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。

# 悲观锁实现方式:

a 在获取资源准备操作时在第三个库插入一条数据,

b 在获取资源之前去第三个库查询是否存在, 存在不操作, 不存在就获取资源, 然后在第三个库插入一条数据.

# 2. 乐观锁

乐观锁（Optimistic Lock），顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是**在提交更新的时候会判断一下在此期间别人有没有去更新这个数据。**乐观锁适用于读多写少的应用场景，这样可以提高吞吐量。
乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。

# 乐观锁实现方式:

使用数据版本（Version）记录机制实现，这是乐观锁最常用的一种实现方式。何谓数据版本？即为数据增加一个版本标识，一般是通过为数据库表增加一个数字类型的 “version” 字段来实现。当读取数据时，将version字段的值一同读出，数据每更新一次，对此version值加一。当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的version值进行比对，如果数据库表当前版本号与第一次取出来的version值相等，则予以更新，否则认为是过期数据。

使用时间戳（timestamp）。乐观锁定的第二种实现方式和第一种差不多，同样是在需要乐观锁控制的table中增加一个字段，名称无所谓，字段类型使用时间戳（timestamp）, 和上面的version类似，也是在更新提交的时候检查当前数据库中数据的时间戳和自己更新前取到的时间戳进行对比，如果一致则OK，否则就是版本冲突。

# CAS运行方式

CAS操作逻辑如下：如果内存位置V的值等于预期的A值，则将该位置更新为新值B，否则不进行任何操作。许多CAS的操作是自旋的：如果操作不成功，会一直重试，直到操作成功为止。
有两个goroutineA和goroutineB，接下来我们简称 A 和 B，共享资源称为C
1. A 和 B 均保存 C 当前的值
2. A 尝试使用CAS（56，53）更新C的值
3. C目前为56，可以更新，然后更新成功
4. B尝试使用CAS（56，53）更新C的值
5. C已经为53，更新失败

# CAS源码

code

// CompareAndSwapUint32 executes the compare-and-swap operation for a uint32 value.
func CompareAndSwapUint32(addr *uint32, old, new uint32) (swapped bool)

1
2

实际代码文件在 Go / src / runtime / internal / atomic / asm_amd.s文件中
```
TEXT runtime∕internal∕atomic·Cas64(SB), NOSPLIT, $0-25
 MOVQ ptr+0(FP), BX
 MOVQ old+8(FP), AX
 MOVQ new+16(FP), CX
 LOCK
 CMPXCHGQ CX, 0(BX)
 SETEQ ret+24(FP)
 RET
```
1
2
3
4
5
6
7
8
- lock(一个命令前缀，在这里用于CMPXCHGQ)可以锁住总线保证多次内存操作的原子性。然后执行CMPXCHGQ
  
  cmpxchg %cx, %bx；如果AX与BX相等，则CX送BX且ZF置1；否则BX送CX，且ZF清0
  1. 拿AX(old) 与 BX(共享数据ptr) 做对比。
  2. 相等，则修改BX(共享数据ptr)，状态码ZX设置为 1 。
  3. 不相等，则将CX(new)置为目前BX(共享数据ptr)的值，状态码ZX设置为 0

# 问题

# 1. 如何保证原子性

既然CAS包含了Compare和Swap两个操作，它又如何保证原子性呢？
答案是：CAS是由CPU支持的原子操作，其原子性是在硬件层面进行保证的。

# 2. CAS的缺陷

CAS在共享资源竞争比较激烈的时候，每个goroutine会容易处于自旋状态，影响效率，在竞争激烈的时候推荐使用锁。
无法解决ABA问题
- ABA问题是无锁结构实现中常见的一种问题，可基本表述为：
进程P1读取了一个数值A P1被挂起(时间片耗尽、中断等)，进程P2开始执行 P2修改数值A为数值B，然后又修改回A P1被唤醒，比较后发现数值A没有变化，程序继续执行。

#Go #

上次更新: 2023/04/16, 18:35:33

← sync.Mutex 实现原理 defer实现原理→