转载

CAS自旋锁

 我们常说的 CAS 自旋锁是什么

CAS与ABA问题

回顾JAVA中的CAS

用AtomicStampedReference解决ABA问题

CAS(Compare and swap),即比较并交换 ,也是实现我们平时所说的 【自旋锁或乐观锁】的核心操作。

CAS有3个操作数, 内存值V,旧的预期值A,要修改的新值B 。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。

public final boolean compareAndSet(boolean expect, boolean update)

它的实现很简单, 【就是用 一个预期的值内存值 进行比较,如果两个值相等,就用预期的值替换内存值,并返回 true。否则,返回 false】

保证原子操作

任何技术的出现都是为了解决某些特定的问题, CAS 要解决的问题就是保证原子操作 。原子操作是什么,原子就是最小不可拆分的,原子操作就是最小不可拆分的操作,也就是说操作一旦开始,就不能被打断,知道操作完成。在多线程环境下,原子操作是保证线程安全的重要手段。举个例子来说,假设有两个线程在工作,都想对某个值做修改,就拿自增操作来说吧,要对一个整数 i 进行自增操作,需要基本的三个步骤:

1、读取 i 的当前值;

2、对 i 值进行加 1 操作;

3、将 i 值写回内存;

假设两个进程都读取了 i 的当前值,假设是 0,这时候 A 线程对 i 加 1 了,B 线程也 加 1,最后 i 的是 1 ,而不是 2。这就是因为自增操作不是原子操作,分成的这三个步骤可以被干扰。如下面这个例子,10个线程,每个线程都执行 10000 次 i++ 操作,我们期望的值是 100,000,但是很遗憾,结果总是小于 100,000 的。

static int i = 0;

public static void add()
{
	i++;
}

private static class Plus implements Runnable {
	@Override
	public void run()
	{
		for ( int k = 0; k < 10000; k++ )
		{
			add();
		}
	}
}

public static void main( String[] args ) throws InterruptedException
{
	Thread[] threads = new Thread[10];
	for ( int i = 0; i < 10; i++ )
	{
		threads[i] = new Thread( new Plus() );
		threads[i].start();
	}
	for ( int i = 0; i < 10; i++ )
	{
		threads[i].join();
	}
	System.out.println( i );
}

既然这样,那怎么办。没错,也许你已经想到了,可以加锁或者利用 synchronized 实现,例如,将 add() 方法修改为如下这样:

public synchronized static void add(){
	i++;
}

或者,加锁操作,例如下面使用 ReentrantLock (可重入锁)实现。

private static Lock lock = new ReentrantLock();

public static void add(){
	lock.lock();
	i++;
	lock.unlock();
}

CAS 实现自旋锁

既然用锁或 synchronized 关键字可以实现原子操作,那么为什么还要用 CAS 呢,因为 【加锁或使用 synchronized 关键字带来的性能损耗较大】 ,而用 【CAS 可以实现乐观锁】 ,它实际上是直接利用了 CPU 层面的指令,所以性能很高。

上面也说了,CAS 是实现自旋锁的基础, 【CAS 利用 CPU 指令保证了操作的原子性 ,以达到锁的效果】 ,至于自旋呢,看字面意思也很明白,自己旋转,翻译成人话就是循环, 【一般是用一个无限循环实现。这样一来,一个无限循环中,执行一个 CAS 操作,当操作成功,返回 true 时,循环结束;当返回 false 时,接着执行循环,继续尝试 CAS 操作,直到返回 true】

其实 JDK 中有好多地方用到了 CAS ,尤其是java.util.concurrent包下,比如 CountDownLatch、Semaphore、ReentrantLock 中,再比如 java.util.concurrent.atomic 包下,相信大家都用到过 Atomic* ,比如 AtomicBoolean、AtomicInteger 等。

这里拿 AtomicBoolean 来举个例子,因为它足够简单。

public class AtomicBoolean implements java.io.Serializable {
    private static final long serialVersionUID = 4654671469794556979L;

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset(AtomicBoolean.class.getDeclaredField("value"));
        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    private volatile int value;

    public final boolean get() {
        return value != 0;
    }

    public final boolean compareAndSet(boolean expect, boolean update) {
        int e = expect ? 1 : 0;
        int u = update ? 1 : 0;

        return unsafe.compareAndSwapInt(this, valueOffset, e, u);
    }
}

这里面又几个关键方法和属性。

1、使用了 sun.misc.Unsafe 对象 ,这个类 提供了一系列 直接操作内存对象 的方法 ,只是在 jdk 内部使用,不建议开发者使用;

2、value 表示实际值,可以看到 get 方法实际是根据 value 是否等于0来判断布尔值的,这里的 value 定义为 volatile,因为 volatile 可以保证内存可见性,也就是 value 值只要发生变化,其他线程是马上可以看到变化后的值的;下一篇会讲一下 volatile 可见性问题,欢迎关注

3、valueOffset 是 value 值的内存偏移量,用 unsafe.objectFieldOffset 方法获得,用作后面的 compareAndSet 方法;

4、 compareAndSet 方法,这就是实现 CAS 的核心方法了,在使用这个方法时,只需要传递期望值和待更新的值即可 ,而它里面调用了 unsafe.compareAndSwapInt(this, valueOffset, e, u) 方法,它是个 native 方法,用 c++ 实现,具体的代码就不贴了,总之是利用了 CPU 的 cmpxchg 指令完成比较并替换,当然根据具体的系统版本不同,实现起来也有所区别,感兴趣的可以自行搜一下相关文章。

使用场景

CAS 适合简单对象的操作,比如布尔值、整型值等;

CAS 适合冲突较少的情况, 如果太多线程在同时自旋,那么长时间循环会导致 CPU 开销很大

ABA问题:

线程1准备用CAS将变量的值由A替换为B,在此之前,线程2将变量的值由A替换为C,又由C替换为A,然后线程1执行CAS时发现变量的值仍然为A,所以CAS成功。 但实际上这时的现场已经和最初不同了,尽管CAS成功,但可能存在潜藏的问题。

例如 下面的例子

现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:

head.compareAndSet(A,B);

在T1执行上面这条指令之前,线程T2介入,将A、B出栈,再pushD、C、A,此时堆栈结构如下图,而对象B此时处于游离状态:

此时轮到线程T1执行CAS操作,检测发现栈顶仍为A,所以CAS成功,栈顶变为B,但实际上B.next为null,所以此时的情况变为:

其中堆栈中只有B一个元素,C和D组成的链表不再存在于堆栈中,平白无故就把C、D丢掉了。

以上就是由于ABA问题带来的隐患, 各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记 ,避免并发操作带来的问题,并发包下倒是有 AtomicStampedReference 提供了根据版本号判断的实现,可以解决一部分问题。它通过包装[E,Integer]的元组来对对象标记版本戳stamp,从而避免ABA问题,例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新,AtomicInteger会成功执行CAS操作,而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABA {
        private static AtomicInteger atomicInt = new AtomicInteger(100);
        private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(100, 0);

		
        public static void main(String[] args) throws InterruptedException {
		
                Thread intT1 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                atomicInt.compareAndSet(100, 101);
                                atomicInt.compareAndSet(101, 100);
                        }
                });

                Thread intT2 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                try {
                                        TimeUnit.SECONDS.sleep(1);
                                } catch (InterruptedException e) {
                                }
                                boolean c3 = atomicInt.compareAndSet(100, 101);
                                System.out.println(c3); // true
                        }
                });

                intT1.start();
                intT2.start();
                intT1.join();
                intT2.join();

                Thread refT1 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                try {
                                        TimeUnit.SECONDS.sleep(1);
                                } catch (InterruptedException e) {
                                }
                                atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                                atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                        }
                });

                Thread refT2 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                int stamp = atomicStampedRef.getStamp();
                                try {
                                        TimeUnit.SECONDS.sleep(2);
                                } catch (InterruptedException e) {
                                }
                                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                                System.out.println(c3); // false
                        }
                });

                refT1.start();
                refT2.start();
        }
}

。。

原文  https://uule.iteye.com/blog/2435465
正文到此结束
Loading...