硬件同步原语（CAS）理论

在Java并发编程中，常常出现一些因为线程安全问题而需要加锁来保证同步，而在Java5之后，出现了新的并发包，它的出现使得同步效率更加高效，而所有concurrent包的理论基础都是基于硬件同步原语理论，它是基于Cpu硬件的同步，效率比软件中通过锁定（排它锁）效率高。

 

大多数现代处理器都包含对多处理的支持。当然这种支持包括多处理器可以共享外部设备和主内存，同时它通常还包括对指令系统的增加来支持多处理的特殊要求。特别是，几乎每个现代处理器都有通过可以检测或阻止其他处理器的并发访问的方式来更新共享变量的指令。

比较并交换 (CAS)

支持并发的第一个处理器提供原子的测试并设置操作，通常在单位上运行这项操作。现在的处理器（包括 Intel 和 Sparc 处理器）使用的最通用的方法是实现名为 比较并转换 或 CAS 的原语。（在 Intel 处理器中，比较并交换通过指令的 cmpxchg 系列实现。PowerPC 处理器有一对名为“加载并保留”和“条件存储”的指令，它们实现相同的目地；MIPS 与 PowerPC 处理器相似，除了第一个指令称为“加载链接”。）

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无 论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”

通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新值 B，然后使用 CAS 将 V 的值从 A 改为 B。如果 V 处的值尚未同时更改，则 CAS 操作成功。

类似于 CAS 的指令允许算法执行读-修改-写操作，而无需害怕其他线程同时修改变量，因为如果其他线程修改变量，那么 CAS 会检测它（并失败），算法可以对该操作重新计算。清单 3 说明了 CAS 操作的行为（而不是性能特征），但是 CAS 的价值是它可以在硬件中实现，并且是极轻量级的（在大多数处理器中）：

清单 3. 说明比较并交换的行为（而不是性能）的代码

				
        
public class SimulatedCAS {
    private int value;
    
    public synchronized int getValue() { return value; }
    
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        if (value == expectedValue) 
            value = newValue;
        return value;
    }
}
      

 

使用 CAS 实现计数器

基于 CAS 的并发算法称为 无锁定 算 法，因为线程不必再等待锁定（有时称为互斥或关键部分，这取决于线程平台的术语）。无论 CAS 操作成功还是失败，在任何一种情况中，它都在可预知的时间内完成。如果 CAS 失败，调用者可以重试 CAS 操作或采取其他适合的操作。清单 4 显示了重新编写的计数器类来使用 CAS 替代锁定：

清单 4. 使用比较并交换实现计数器

				
        
public class CasCounter {
    private SimulatedCAS value;
    public int getValue() {
        return value.getValue();
    }
    public int increment() {
        int oldValue = value.getValue();
        while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue)
            oldValue = value.getValue();
        return oldValue + 1;
    }
}
      

回页首

无锁定且无等待算法

如果每个线程在其他线程任意延迟（或甚至失败）时都将持续进行操作，就可以说该算法是 无等待 的。与此形成对比的是， 无锁定 算法要求仅 某个 线程总是执行操作。（无等待的另一种定义是保证每个线程在其有限的步骤中正确计算自己的操作，而不管其他线程的操作、计时、交叉或速度。这一限制可以是系统中线程数的函数；例如，如果有 10 个线程，每个线程都执行一次 CasCounter.increment() 操作，最坏的情况下，每个线程将必须重试最多九次，才能完成增加。）

再过去的 15 年里，人们已经对无等待且无锁定算法（也称为 无阻塞算法 ） 进行了大量研究，许多人通用数据结构已经发现了无阻塞算法。无阻塞算法被广泛用于操作系统和 JVM 级别，进行诸如线程和进程调度等任务。虽然它们的实现比较复杂，但相对于基于锁定的备选算法，它们有许多优点：可以避免优先级倒置和死锁等危险，竞争比较 便宜，协调发生在更细的粒度级别，允许更高程度的并行机制等等

评论

4 楼 fbwfbi 2015-07-31  

fengchuizhuming 写道

楼主的完全正确。鉴定完毕

楼上完全错误，已证明。 CAS 有两种形式，一种是不管操作成功与否，都是返回原值（旧），另一种就是就是返回True 或 False ， 楼主给出的代码描述是错的。标准的如下：

引用

CAS原子操作在维基百科中的代码描述如下:
   1: int compare_and_swap(int* reg, int oldval, int newval)
   2: {
   3:   ATOMIC();
   4:   int old_reg_val = *reg;
   5:   if (old_reg_val == oldval)
   6:      *reg = newval;
   7:   END_ATOMIC();
   8:   return old_reg_val;
   9: }
也就是检查内存*reg里的值是不是oldval，如果是的话，则对其赋值newval。上面的代码总是返回old_reg_value，调用者如果需要知道是否更新成功还需要做进一步判断，为了方便，它可以变种为直接返回是否更新成功，如下：
   1: bool compare_and_swap (int *accum, int *dest, int newval)
   2: {
   3:   if ( *accum == *dest ) {
   4:       *dest = newval;
   5:       return true;
   6:   }
   7:   return false;
   8: }

3 楼 fengchuizhuming 2014-12-05  

楼主的完全正确。鉴定完毕

2 楼 bhtbed 2013-01-17  

一楼请考虑多线程的情况，这个value会被其他线程在其他地方改变，在int oldValue = value.getValue();之后，while之前 线程调度发生的时候。
不过这个while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue)确实有问题，当成功的时候，increase会增加2，不是1.

另外，之所以很多实现返回bool，是为了更清楚到底成功没，像你这样的实现并不清楚CAS到底是否成功。
C#的实现是：bool CompareExchange(ref object location, object value,object newValue)。
感觉更好，通过传入ref，即能修改值为最新值，同时bool返回是否设置新值成功。

1 楼 youfengkai 2011-02-10  

while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue)
            oldValue = value.getValue();
        return oldValue + 1;
这个例子让我很晕,费解.


value.compareAndSwap(oldValue, oldValue + 1) != oldValue,这个不是恒等式么?