VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > c#编程 >
  • 并发编程 --- CAS原子操作

介绍

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

原理

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

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

  1. 读取内存的值
  2. 将内存的值与期望值比较
  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 实现无锁算法的例子。

CAS优缺点

优点:

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

缺点:

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

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

一般适用场景:

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

结论

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

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



相关教程