2023-04-21
并发编程
00
请注意,本文编写于 341 天前,最后修改于 341 天前,其中某些信息可能已经过时。

目录

介绍
原理
示例
CAS优缺点
结论

介绍

CAS(Compare And Swap) 是一种无锁算法的实现手段,中文名称为比较并交换。它由 CPU 的原子指令实现,可以在多线程环境下实现无锁的数据结构。

原理

CAS 的原理是:它会先比较内存中的某个值是否和预期值相同,如果相同则更新这个值,否则不做任何操作。这整个过程是原子的,所以可以在多线程环境下实现无锁的数据结构。

CAS 操作有3个原子性操作:

  1. 读取内存的值
  2. 将内存的值与期望值比较
  3. 如果相等,则将内存值更新为新值

这三个操作一起完成,中间不会被线程切换打断。这就保证了比较和交换的原子性。

使用C#伪代码实现如下:

csharp
bool Cas(ref object obj, object expected, object newValue) { object oldValue = obj; if (oldValue == expected) { obj = newValue; return true; } return false; }

解释如下:

  • C#使用ref关键字来表示要操作的内存地址obj
  • oldValue = obj读取内存值,obj = newValue更新内存值。
  • 其他逻辑与伪代码相同,先读取内存值oldValue,然后判断是否等于期望值expected,如果相等则更新内存值为newValue并返回true,否则返回false。
  • CAS操作包含读内存值、比较内存值与期望值、更新内存值三个原子步骤。这三步作为一个整体执行,中间不会被中断,保证比较和交换的原子性。
  • 该方法尝试使用CAS操作更新obj的值,当且仅当obj的值等于expected时才更新,否则不做任何操作。

示例

C# 中提供了 Interlocked 类来实现 CAS 操作。主要包含以下几个方法:

  • Interlocked.CompareExchange(ref val, newValue, comparand):如果 val 等于 comparand,则将 val 的值更新为 newValue,并返回 comparand,否则返回 val 的当前值。
  • Interlocked.Exchange(ref val, newValue):将 val 的值更新为 newValue,并返回 val 的旧值。
  • Interlocked.Increment(ref val):将 val 的值增加 1,并返回增加后的值。
  • Interlocked.Decrement(ref val):将 val 的值减少 1,并返回减少后的值。 示例代码:
csharp
int val = 0; Interlocked.CompareExchange(ref val, 1, 0); // val = 1, 返回 0 Interlocked.CompareExchange(ref val, 2, 1); // val 保持 1, 返回 1 Interlocked.Increment(ref val); // val = 2, 返回 2 Interlocked.Decrement(ref val); // val = 1, 返回 1

这些方法可以实现无锁数据结构,例如无锁队列:

csharp
public class LockFreeQueue<T> { private T[] array; private int head; private int tail; public void Enqueue(T obj) { int tail = Interlocked.Increment(ref this.tail); this.array[tail % this.array.Length] = obj; } public T Dequeue() { int head = Interlocked.Increment(ref this.head); return this.array[head % this.array.Length]; } }

通过 Interlocked 类的原子操作实现了无锁入队出队,这是一个典型的使用 CAS 实现无锁算法的例子。

CAS优缺点

优点:

  • 无锁,实现高并发的数据结构。CAS 是实现无锁算法的关键手段。
  • 原子操作,线程安全,不会引起数据竞争。
  • 简单高效,只需要硬件支持,性能很高。

缺点:

  • ABA 问题。如果一个值从 A 改为 B,又改回 A,那么 CAS 操作会误认为值没有改变。常用的解决方法是使用版本号。
  • 只能保证一个共享变量的原子操作。如果对多个共享变量操作,则需要使用锁。
  • 资源浪费。当 CAS 失败时,会进行重试,消耗 CPU 资源。
  • 只能在某些平台使用。需要硬件对 CAS 操作的支持,一些低端硬件并不支持 CAS

综上,CAS 是实现无锁算法的关键手段,有很高的性能,但是也存在一定的问题,需要权衡使用。

一般适用场景:

  • 当对一个共享变量的原子操作时,使用 CAS
  • 当操作多个共享变量时,使用锁可能性能更高。
  • 如果硬件不支持 CAS,也不得不使用锁。

结论

CAS 是实现无锁算法的关键手段,性能高并发度高,但是也存在一定问题,需要权衡使用。一般来说,当操作一个共享变量时使用 CAS,操作多个共享变量时使用锁可能更高效。如果硬件不支持 CAS,也只能使用锁。

此外,CAS 和锁是两种不同的同步原语,各有优缺点,需要根据实际情况选择使用。CAS 是无锁算法的基石,所以高性能高并发系统中还是比较重要的

本文作者:Peter.Pan

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!