CAS的理解

CAS的理解

什么是CAS？

compare and swap 比较并交换。

cas主要应用于解决多线程并行情况下使用锁造成性能损耗的一种机制。

提供一个地址，在执行执行时，会判断值是否正确。否则不执行，返回false。

什么是TAS？

TAS利用cas实现互斥。cas实现锁的原理

java使用UnSafe实现cas

@ForceInline
public final boolean compareAndSetBoolean(Object o, long offset,
                                          boolean expected,
                                          boolean x) {
    return compareAndSetByte(o, offset, bool2byte(expected), bool2byte(x));
}

CAS的ABA问题

例子

多线程进行幂等操作扣减库存

• T1 : 100->99 // 订单001下单扣减库存
• T2 : 100->99 // 订单001下单扣减库存（此处假设多线程cas竞争操作，理论一般不会多线程多次执行）
• T3: 99->100 // 订单002退货增加库存

以上多线程处理中：T1 和 T2 处理同一订单，会同时把库存100-> 99, 理论上只会有一个线程成功（使用了cas操作），但是在并发执行中 T3在T1执行后，将库存补充成100，T2误认为扣减未成功，就继续将100 -> 99了。

以上过程相当于一个订单，由于cas的ABA问题在并发扣减库存时，扣减了2次。

解决方案

除了对比值之外， 添加version。

JAVA中提供了两种解决方案实现。

• java.util.concurrent.atomic.AtomicMarkableReference#compareAndSet

    	private static class Pair<T> {
          final T reference;
          final boolean mark;
          private Pair(T reference, boolean mark) {
              this.reference = reference;
              this.mark = mark;
          }
          static <T> Pair<T> of(T reference, boolean mark) {
              return new Pair<T>(reference, mark);
          }
      }
  
  
  /**
   * Atomically sets the value of both the reference and mark
   * to the given update values if the
   * current reference is {@code ==} to the expected reference
   * and the current mark is equal to the expected mark.
   *
   * @param expectedReference the expected value of the reference
   * @param newReference the new value for the reference
   * @param expectedMark the expected value of the mark
   * @param newMark the new value for the mark
   * @return {@code true} if successful
   */
  public boolean compareAndSet(V       expectedReference,
                               V       newReference,
                               boolean expectedMark,
                               boolean newMark) {
      Pair<V> current = pair;
      return
          expectedReference == current.reference &&
          expectedMark == current.mark &&
          ((newReference == current.reference &&
            newMark == current.mark) ||
           casPair(current, Pair.of(newReference, newMark)));
  }
  

  在进行cas操作的时候比对Pair的mark。

• java.util.concurrent.atomic.AtomicStampedReference#compareAndSet

      private static class Pair<T> {
          final T reference;
          final int stamp;
          private Pair(T reference, int stamp) {
              this.reference = reference;
              this.stamp = stamp;
          }
          static <T> Pair<T> of(T reference, int stamp) {
              return new Pair<T>(reference, stamp);
          }
      }
  
  /**
   * Atomically sets the value of both the reference and stamp
   * to the given update values if the
   * current reference is {@code ==} to the expected reference
   * and the current stamp is equal to the expected stamp.
   *
   * @param expectedReference the expected value of the reference
   * @param newReference the new value for the reference
   * @param expectedStamp the expected value of the stamp
   * @param newStamp the new value for the stamp
   * @return {@code true} if successful
   */
  public boolean compareAndSet(V   expectedReference,
                               V   newReference,
                               int expectedStamp,
                               int newStamp) {
      Pair<V> current = pair;
      return
          expectedReference == current.reference &&
          expectedStamp == current.stamp &&
          ((newReference == current.reference &&
            newStamp == current.stamp) ||
           casPair(current, Pair.of(newReference, newStamp)));
  }
  

  在进行cas操作的时候比对Pair的stamp(相当于version)。