Coin163

首页 > 非阻塞同步机制与CAS操作

非阻塞同步机制与CAS操作

2020腾讯云8月秒杀活动,优惠非常大!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1040

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
入口地址https://www.aliyun.com/minisite/goods

锁的劣势

    Java在JDK1.5之前都是靠synchronized关键字保证同步的,这种通过使用一致的锁定协议来协调对共享状态的访问,可以确保无论哪个线程 持有守护变量的锁,都采用独占的方式来访问这些变量,如果出现多个线程同时访问锁,那第一些线线程将被挂起,当线程恢复执行时,必须等待其它线程执行完他 们的时间片以后才能被调度执行,在挂起和恢复执行过程中存在着很大的开销。锁还存在着其它一些缺点,当一个线程正在等待锁时,它不能做任何事。如果一个线 程在持有锁的情况下被延迟执行,那么所有需要这个锁的线程都无法执行下去。如果被阻塞的线程优先级高,而持有锁的线程优先级低,将会导致优先级反转 (Priority Inversion)。

 

volatile的优势

    与锁相比,volatile变量是一和更轻量级的同步机制,因为在使用这些变量时不会发生上下文切换和线程调度等操作,但是volatile变量也存在一些局限:不能用于构建原子的复合操作,因此当一个变量依赖旧值时就不能使用volatile变量

 

悲观锁和乐观锁

独占锁是一种悲观锁,synchronized就是一种独占锁,它假设最坏的情况,并且只有在确保其它线程不会造成干扰的情况下执行,会导致其它所 有需要锁的线程挂起,等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为 冲突失败就重试,直到成功为止。

 

CAS操作

    Compare and Swap,比较并操作,CPU指令,在大多数处理器架构,包括IA32、Space中采用的都是CAS指令,CAS的语义是“我认为V的值应该为A,如果 是,那么将V的值更新为B,否则不修改并告诉V的值实际为多少”,CAS是项乐观锁技术,当多个线程尝试使用CAS同时更新同一个变量时,只有其中一个线 程能更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。CAS有3个操作数,内存值V,旧的预期值 A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。

 

JVM对CAS的支持

    在JDK1.5之前,如果不编写明确的代码就无法执行CAS操作,在JDK1.5中引入了底层的支持,在int、long和对象的引用等类型上都公开了 CAS的操作,并且JVM把它们编译为底层硬件提供的最有效的方法,在运行CAS的平台上,运行时把它们编译为相应的机器指令,如果处理器不支持CAS指 令,那么JVM将使用自旋锁。在原子类变量中,如java.util.concurrent.atomic中的AtomicXXX,都使用了这些底层的 JVM支持为数字类型的引用类型提供一种高效的CAS操作,而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些 原子变量类。

 

下面代码说明了CAS的语义(并不是真正的实现,CAS的实现是调用native方法):

复制代码
/**
 * Huisou.com Inc.
 * Copyright (c) 2011-2012 All Rights Reserved.
 */

package thread;

import org.apache.http.annotation.GuardedBy;
import org.apache.http.annotation.ThreadSafe;

/**
 * @description
 * 
 * @author chenzehe
 * @email hljuczh@163.com
 * @create 2013-1-6 上午09:02:47
 */
@ThreadSafe
public class SimulatedCAS {
    @GuardedBy("this")
    private int    value;
    
    public synchronized int get() {
        return value;
    }
    
    public synchronized int comparedAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (oldValue == expectedValue) {
            value = newValue;
        }
        return oldValue;
    }
    
    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return (expectedValue == comparedAndSwap(expectedValue, newValue));
    }
}
复制代码

 下面代码演示了非阻塞计数器:

 

 

 

 

复制代码
/**
 * Huisou.com Inc.
 * Copyright (c) 2011-2012 All Rights Reserved.
 */

package thread;

/**
 * @description
 * 
 * @author chenzehe
 * @email hljuczh@163.com
 * @create 2013-1-6 上午09:48:52
 */

public class CasCounnter {
    private SimulatedCAS    value;
    
    public int getValue() {
        return value.get();
    }
    
    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.comparedAndSwap(v, v + 1));
        return v + 1;
    }
}
复制代码

 AtomicInteger中实现自增的代码为:

复制代码
public final int getAndIncrement() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return current;
        }
}

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
复制代码

表面上看起来,基于CAS的计数器似乎比基于锁的计数器在性能上更差一些,因为它还要执行更多的操作和更复杂的控制流,并且还依赖看似复杂的CAS 操作,实际上,当竞争程度不高时,基于CAS的计数器在性能上远远超过了基于锁的计数器,而在没有竞争时甚至更高,如果要快速获取无竞争的锁,那么至少需 要一次CAS操作加上与其它锁相关的操作,因此基于锁的计数即使在最好的情况下也会比基于CAS的计数器在一般情况下执行更多的操作。由于CAS在大多数 情况下都能执行成功,因此硬件能够正确的预测while循环中的分支,从而把控制逻辑的开锁降到最低。

 

锁与原子变量的性能比较

    在高度竞争的情况下,锁的性能将超过原子变量的性能,但在更真实的竞争情况下,原子变量的性能将超过锁的性能,这是因为锁在发竞争时会挂起线程,从而降低 了CPU的使用率和共享内存总线上的同步通信量,另一方面,如果使用原子变量,那么发出调用的类负责对竞争进行管理,在遇到竞争时立即重试,这通常是种正 确的做法,但是在竞争激烈环境下会导致更多的竞争。在实际的情况中,任何一个程序都不会除了竞争锁或原子变量而什么事都不做,不会达到很高的竞争,所以在 更常见的情况下,原子变量的效率会更高,在可伸缩性上要高于锁。

 

非阻塞算法

    如果在某个算法中,一个线程的失败或挂起不会引起其它线程也失败或挂起,那么这个算法就被称为非阻塞算法;如果在算法的每个步骤中都存在每个线程能够执行 下去,那么这种算法称为无锁算法(Lock-Free)。如果在算法中仅将CAS用于协调线程之间的操作,并且能正确的实现,那么它即是一种非阻塞算法, 也是一种无锁算法。在非阻塞算法中通常不会出现死锁和优先级反转问题,但可能出现饥饿和活锁问题,因为在算法中会反复的重试。

下面代码为非阻塞的栈(使用Treiber算法):

复制代码
package thread;
import java.util.concurrent.atomic.AtomicReference;
public class ConcurrentStack<T> {
    private AtomicReference<Node<T>>    stacks    = new AtomicReference<Node<T>>();
    public T push(T e) {
        Node<T> oldNode, newNode;
        for (;;) { // 这里的处理非常的特别,也是必须如此的。
            oldNode = stacks.get();
            newNode = new Node<T>(e, oldNode);
            if (stacks.compareAndSet(oldNode, newNode)) {
                return e;
            }
        }
    }    
    public T pop() {
        Node<T> oldNode, newNode;
        do{
                        oldNode = stacks.get();
                        if(oldNode==null){
                              return null;
                        }
            newNode = oldNode.next;
                }while(!stacks.compareAndSet(oldNode, newNode));
                 return oldNode.object;
    }    
    private static final class Node<T> {
        private T        object;        
        private Node<T>    next;        
        private Node(T object, Node<T> next) {
            this.object = object;
            this.next = next;
        }
    }    
}
复制代码

     如果在算法中的节点可以被循环使用,那么在使用CAS指令时就会出现这种问题,主要指在没有垃圾回收机制的环境中,在CAS操作中,在更新之前先判断V的 值是否仍然A,如果是的话就继续执行更新操作,但是有的时候还需要知道“自从上次看到V的值为A以后,这个值是否发生了变化?”,在某些算法中,如果V的 值先由A变成B,再由B变成A,那么仍然认为是发生了变化,并需要重新执行算法中的步骤。在这种情况下,即使链表的头节点仍然指向之前观察到的节点,但也 不足以说明链表的内容没有变化。如果通过垃圾回收机制仍然无法避免ABA问题,那么还有下面简单方案:不是更新某个引用的值,而是更新两个值,包括一个引 用和一个版本号,即使这个值由A变为B,然后为变为A,版本号也是不同的。AtomicStampedReference和 AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference更新一个“对象-引 用”二元组,通过在引用上加上“版本号”,从而避免ABA问题,AtomicMarkableReference将更新一个“对象引用-布尔值”的二元 组。


转自:http://www.cnblogs.com/chenying99/archive/2013/07/23/3207828.html

原文

锁的劣势     Java在JDK1.5之前都是靠synchronized关键字保证同步的,这种通过使用一致的锁定协议来协调对共享状态的访问,可以确保无论哪个线程 持有守护变量的锁,都采用独占的方式来访问这些

------分隔线----------------------------
相关推荐