并发编程 --- CAS原子操作

介绍

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

原理

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

CAS 操作有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 是无锁算法的基石，所以高性能高并发系统中还是比较重要的

目录

介绍

原理

示例

CAS优缺点

结论