`
liulanghan110
  • 浏览: 1075521 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

非阻塞同步机制与CAS操作

    博客分类:
  • JAVA
阅读更多

 

锁的劣势

    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://chenzehe.iteye.com/blog/1762893

分享到:
评论

相关推荐

    Java并发编程之原子变量与非阻塞同步机制

    Java并发编程是多线程环境下确保程序正确执行的关键技术,其中原子变量和非阻塞同步机制扮演着重要角色。非阻塞算法不同于传统的基于锁的同步机制,它们允许线程在不阻塞其他线程的情况下进行操作,提高了系统的并发...

    学习非阻塞的同步机制CAS

    学习非阻塞的同步机制CAS 现代的处理器都包含对并发的支持,其中最通用的方法就是比较并交换(compare and swap),简称CAS。CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。如果内存位置的...

    非阻塞算法简介1

    而非阻塞算法通过循环检测(自旋)和CAS操作,减少了线程阻塞的几率,从而提高了系统整体的吞吐量。 然而,非阻塞算法并不总是性能上的最优解。过度依赖自旋等待可能导致CPU资源的浪费,尤其是在锁竞争激烈或锁持有...

    JAVA CAS深度分析

    3. CAS 操作的应用:JAVA 中的 CAS 操作主要应用于 java.util.concurrent 包中,用于实现非阻塞算法,即非阻塞的线程安全机制。 4. CAS 操作的原理分析:CAS 操作可以通过分析 CPU 底层指令来理解,例如 Intel x86 ...

    Linux驱动开发之旅(三)--非阻塞的锁机制

    本文将深入探讨非阻塞的锁机制,特别是在“Linux驱动开发之旅(三)”中提及的3_mutex,这种锁机制允许任务在无法获取锁时立即返回,而不是等待。这种方式可以提高系统的响应性和效率,特别是在实时性要求较高的系统...

    Java理论与实践:非阻塞算法简介

    非阻塞算法的核心在于原子操作,如比较并交换(Compare and Swap,简称CAS)。`AtomicInteger`类中的`compareAndSet()`方法就是一个例子。这个方法尝试将变量的值从旧值更新为新值,但只有在当前值等于预期的旧值时...

    Java 多线程与并发(8-26)-JUC原子类- CAS, Unsafe和原子类详解.pdf

    线程安全的实现方法主要有三种:互斥同步(例如synchronized和ReentrantLock)、非阻塞同步(例如CAS、AtomicXXXX)和无同步方案(例如栈封闭、Thread Local、可重入代码)。互斥同步会使用锁机制来保证共享数据的...

    cas.tar.gz_CAS_Mutex_multithread_semphore

    文件名"cas"可能是指Cas自旋锁(Compare and Swap Spin Lock),这是一种基于CAS操作实现的非阻塞锁。 学习和理解这些概念对于提升多线程编程的能力至关重要,它们可以帮助开发者编写出更加高效、并发性能更强的...

    探索Java并发的基石:同步机制的全面解析

    ### Java 并发基石:同步机制的全面解析 #### Java 的并发编程背景 Java作为一种广泛应用的编程语言,自1995年由Sun Microsystems(现属于Oracle公司)发布以来,已经发展成为一种支持跨平台性、面向对象编程、多...

    15 原子性轻量级实现—深入理解Atomic与CAS.pdf

    在Java中,`Atomic`类提供了一种轻量级的、非阻塞的原子性操作实现,以提高并发性能。 `Atomic`类位于`java.util.concurrent.atomic`包中,包括如`AtomicInteger`、`AtomicLong`、`AtomicBoolean`等,分别对应不同...

    深入分析Java并发编程之CAS

    首先,CAS操作的原理是:在执行更新操作前,先比较当前变量的值是否与预期值相等,如果相等则更新,否则不做任何操作。这种乐观锁策略假设并发冲突较少,可以减少锁带来的同步开销。在Java中,CAS操作是通过`Unsafe`...

    CAS学习手册-JAVA程序员必备

    为了解决这个问题,我们可以使用`synchronized`关键字或者`Lock`实现线程安全的自增,但这些同步机制会引入性能问题,因为它们可能导致线程阻塞和上下文切换。 2. **Atomic类的解决方案** `AtomicInteger`等原子类...

    java并发之原子操作类和非阻塞算法

    与传统的锁机制不同,非阻塞算法在数据竞争时不会导致线程阻塞,而是通过循环检测和重试来实现数据一致性。这种算法在多核处理器环境下表现出更好的可扩展性,因为它减少了线程间的同步等待,降低了上下文切换的开销...

    多线程 教程 各种锁 半成品的CAS 临界区 信号量 事件 互斥锁 队列

    **信号量(Semaphore)**:信号量是一种用于控制多个线程对共享资源访问的同步机制。它可以是整型变量,当资源可用时,值为正;当资源全部被占用时,值为零。线程在进入临界区前需要尝试获取信号量,信号量非零则可...

    niling:可同步的CAS数据

    理解这一模型对于实现类似CAS的同步机制至关重要。 4. **数据同步**:在多线程环境中,数据同步是确保多个线程正确访问共享数据的关键。"niling"可能提供了一种在JavaScript环境中同步数据的方法,防止数据在并发...

    高性能并行计算中的同步策略.pptx

    1. **非阻塞同步原语**:如无锁交换和无锁比较交换 (CAS),允许线程在不阻塞的情况下协作访问共享资源。这些原语提高了吞吐量和并发性,尤其是在频繁更新共享资源的情况下。 2. **数据结构限制**:通过将并发限制在...

    Java语言中非阻塞算法的实现.zip

    - `CopyOnWriteArrayList`和`CopyOnWriteArraySet`:这两个容器在添加元素时会复制原有数组并创建新数组,写操作不会影响到读操作,从而实现了非阻塞。适用于读多写少的场景。 3. **锁支持**: - `ReentrantLock`...

    Java 全栈知识点问题汇总(3).pdf

    非阻塞同步,如基于CAS(Compare-and-Swap)操作的乐观锁,尝试进行操作并检测冲突,若无冲突则成功,若有冲突则重试,直到成功。Java.util.concurrent.atomic包中的类如AtomicInteger、AtomicLong等提供了基于CAS...

    Java线程同步与 Java 并发设施.pdf

    虽然CAS操作不会导致线程阻塞,但它们仍然具有一定的开销,因为它们需要不断地尝试并更新共享变量,直到成功。尽管如此,由于避免了锁的使用,原子类在某些情况下可以提供更好的性能。 同步操作对性能的影响是多...

Global site tag (gtag.js) - Google Analytics