并发编程 --- CAS原子操作-526互联

介绍

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

原理

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

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

读取内存的值
将内存的值与期望值比较
如果相等，则将内存值更新为新值

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

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

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，并返回减少后的值。
示例代码:

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

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

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 实现无锁算法的例子。