- 浏览: 98004 次
- 性别:
- 来自: 深圳
文章分类
最新评论
简介:
Java™ 5.0 第一次让使用 Java 语言开发非阻塞算法成为可能,java.util.concurrent
包充分地利用了这个功能。非阻塞算法属于并发算法,它们可以安全地派生它们的线程,不通过锁定派生,而是通过低级的原子性的硬件原生形式 —— 例如比较和交换
。非阻塞算法的设计与实现极为困难,但是它们能够提供更好的吞吐率,对生存问题(例如死锁和优先级反转)也能提供更好的防御。在这期的 Java 理论与实践
中,并发性大师 Brian Goetz 演示了几种比较简单的非阻塞算法的工作方式。
本文的标签: concurrency
发布日期:
2006 年 5 月 18 日
级别:
高级
访问情况
2910 次浏览
建议:
0 (添加评论
)
在不只一个线程访问一个互斥的变量时,所有线程都必须使用同步,否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized
关键字(也称为内在锁
),它强制实行互斥,确保执行 synchronized
块的线程的动作,能够被后来执行受相同锁保护的 synchronized
块的其他线程看到。在使用得当的时候,内在锁可以让程序做到线程安全,但是在使用锁定保护短的代码路径,而且线程频繁地争用锁的时候,锁定可能成为相当繁重的操作。
在 “流行的原子” 一文中,我们研究了原子变量 ,原子变量提供了原子性的读-写-修改操作,可以在不使用锁的情况下安全地更新共享变量。原子变量的内存语义与 volatile 变量类似,但是因为它们也可以被原子性地修改,所以可以把它们用作不使用锁的并发算法的基础。
清单 1 中的 Counter
是线程安全的,但是使用锁的需求带来的性能成本困扰了一些开发人员。但是锁是必需的,因为虽然增加看起来是单一操作,但实际是三个独立操作的简化:检索值,给值加 1,再写回值。(在 getValue
方法上也需要同步,以保证调用 getValue
的线程看到的是最新的值。虽然许多开发人员勉强地使自己相信忽略锁定需求是可以接受的,但忽略锁定需求并不是好策略。)
在多个线程同时请求同一个锁时,会有一个线程获胜并得到锁,而其他线程被阻塞。JVM 实现阻塞的方式通常是挂起阻塞的线程,过一会儿再重新调度它。由此造成的上下文切换相对于锁保护的少数几条指令来说,会造成相当大的延迟。
public final class Counter { private long value = 0; public synchronized long getValue() { return value; } public synchronized long increment() { return ++value; } } |
清单 2 中的 NonblockingCounter
显示了一种最简单的非阻塞算法:使用 AtomicInteger
的 compareAndSet()
(CAS)方法的计数器。compareAndSet()
方法规定 “将这个变量更新为新值,但是如果从我上次看到这个变量之后其他线程修改了它的值,那么更新就失败”(请参阅 “流行的原子”
获得关于原子变量以及 “比较和设置” 的更多解释。)
public class NonblockingCounter { private AtomicInteger value; public int getValue() { return value.get(); } public int increment() { int v; do { v = value.get(); while (!value.compareAndSet(v, v + 1)); return v + 1; } } |
原子变量类之所以被称为原子的 ,是因为它们提供了对数字和对象引用的细粒度的原子更新,但是在作为非阻塞算法的基本构造块的意义上,它们也是原子的。非阻塞算法作为科研的主题,已经有 20 多年了,但是直到 Java 5.0 出现,在 Java 语言中才成为可能。
现代的处理器提供了特殊的指令,可以自动更新共享数据,而且能够检测到其他线程的干扰,而 compareAndSet()
就用这些代替了锁定。(如果要做的只是递增计数器,那么 AtomicInteger
提供了进行递增的方法,但是这些方法基于 compareAndSet()
,例如 NonblockingCounter.increment()
)。
非阻塞版本相对于基于锁的版本有几个性能优势。首先,它用硬件的原生形态代替 JVM 的锁定代码路径,从而在更细的粒度层次上(独立的内存位置)进行同步,失败的线程也可以立即重试,而不会被挂起后重新调度。更细的粒度降低了争用的机会, 不用重新调度就能重试的能力也降低了争用的成本。即使有少量失败的 CAS 操作,这种方法仍然会比由于锁争用造成的重新调度快得多。
NonblockingCounter
这个示例可能简单了些,但是它演示了所有非阻塞算法的一个基本特征 —— 有些算法步骤的执行是要冒险的,因为知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作乐观算法
,因为它们继续操作的假设是不会有干扰。如果发现干扰,就会回退并重试。在计数器的示例中,冒险的步骤是递增 —— 它检索旧值并在旧值上加一,希望在计算更新期间值不会变化。如果它的希望落空,就会再次检索值,并重做递增计算。
非阻塞算法稍微复杂一些的示例是清单 3 中的 ConcurrentStack
。ConcurrentStack
中的 push()
和 pop()
操作在结构上与 NonblockingCounter
上相似,只是做的工作有些冒险,希望在 “提交” 工作的时候,底层假设没有失效。push()
方法观察当前最顶的节点,构建一个新节点放在堆栈上,然后,如果最顶端的节点在初始观察之后没有变化,那么就安装新节点。如果 CAS 失败,意味着另一个线程已经修改了堆栈,那么过程就会重新开始。
public class ConcurrentStack<E> { AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(); public void push(E item) { Node<E> newHead = new Node<E>(item); Node<E> oldHead; do { oldHead = head.get(); newHead.next = oldHead; } while (!head.compareAndSet(oldHead, newHead)); } public E pop() { Node<E> oldHead; Node<E> newHead; do { oldHead = head.get(); if (oldHead == null) return null; newHead = oldHead.next; } while (!head.compareAndSet(oldHead,newHead)); return oldHead.item; } static class Node<E> { final E item; Node<E> next; public Node(E item) { this.item = item; } } } |
在轻度到中度的争用情况下,非阻塞算法的性能会超越阻塞算法,因为 CAS 的多数时间都在第一次尝试时就成功,而发生争用时的开销也不涉及线程挂起和上下文切换,只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多(这句话肯定是真的,因为没有争用的锁涉及 CAS 加上额外的处理),而争用的 CAS 比争用的锁获取涉及更短的延迟。
在高度争用的情况下(即有多个线程不断争用一个内存位置的时候),基于锁的算法开始提供比非阻塞算法更好的吞吐率,因为当线程阻塞时,它就会停止争用,耐 心地等候轮到自己,从而避免了进一步争用。但是,这么高的争用程度并不常见,因为多数时候,线程会把线程本地的计算与争用共享数据的操作分开,从而给其他 线程使用共享数据的机会。(这么高的争用程度也表明需要重新检查算法,朝着更少共享数据的方向努力。)“流行的原子” 中的图在这方面就有点儿让人困惑,因为被测量的程序中发生的争用极其密集,看起来即使对数量很少的线程,锁定也是更好的解决方案。
目前为止的示例(计数器和堆栈)都是非常简单的非阻塞算法,一旦掌握了在循环中使用 CAS,就可以容易地模仿它们。对于更复杂的数据结构,非阻塞算法要比这些简单示例复杂得多,因为修改链表、树或哈希表可能涉及对多个指针的更新。CAS 支持对单一指针的原子性条件更新,但是不支持两个以上的指针。所以,要构建一个非阻塞的链表、树或哈希表,需要找到一种方式,可以用 CAS 更新多个指针,同时不会让数据结构处于不一致的状态。
在链表的尾部插入元素,通常涉及对两个指针的更新:“尾” 指针总是指向列表中的最后一个元素,“下一个” 指针从过去的最后一个元素指向新插入的元素。因为需要更新两个指针,所以需要两个 CAS。在独立的 CAS 中更新两个指针带来了两个需要考虑的潜在问题:如果第一个 CAS 成功,而第二个 CAS 失败,会发生什么?如果其他线程在第一个和第二个 CAS 之间企图访问链表,会发生什么?
对于非复杂数据结构,构建非阻塞算法的 “技巧” 是确保数据结构总处于一致的状态(甚至包括在线程开始修改数据结构和它完成修改之间),还要确保其他线程不仅能够判断出第一个线程已经完成了更新还是处在 更新的中途,还能够判断出如果第一个线程走向 AWOL,完成更新还需要什么操作。如果线程发现了处在更新中途的数据结构,它就可以 “帮助” 正在执行更新的线程完成更新,然后再进行自己的操作。当第一个线程回来试图完成自己的更新时,会发现不再需要了,返回即可,因为 CAS 会检测到帮助线程的干预(在这种情况下,是建设性的干预)。
这种 “帮助邻居” 的要求,对于让数据结构免受单个线程失败的影响,是必需的。如果线程发现数据结构正处在被其他线程更新的中途,然后就等候其他线程完成更新,那么如果其他 线程在操作中途失败,这个线程就可能永远等候下去。即使不出现故障,这种方式也会提供糟糕的性能,因为新到达的线程必须放弃处理器,导致上下文切换,或者 等到自己的时间片过期(而这更糟)。
清单 4 的 LinkedQueue
显示了 Michael-Scott 非阻塞队列算法的插入操作,它是由 ConcurrentLinkedQueue
实现的:
清单 4. Michael-Scott 非阻塞队列算法中的插入
public class LinkedQueue <E> { private static class Node <E> { final E item; final AtomicReference<Node<E>> next; Node(E item, Node<E> next) { this.item = item; this.next = new AtomicReference<Node<E>>(next); } } private AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(new Node<E>(null, null)); private AtomicReference<Node<E>> tail = head; public boolean put(E item) { Node<E> newNode = new Node<E>(item, null); while (true) { Node<E> curTail = tail.get(); Node<E> residue = curTail.next.get(); if (curTail == tail.get()) { if (residue == null) /* A */ { if (curTail.next.compareAndSet(null, newNode)) /* C */ { tail.compareAndSet(curTail, newNode) /* D */ ; return true; } } else { tail.compareAndSet(curTail, residue) /* B */; } } } } } |
像许多队列算法一样,空队列只包含一个假节点。头指针总是指向假节点;尾指针总指向最后一个节点或倒数第二个节点。图 1 演示了正常情况下有两个元素的队列:
如 清单 4 所示,插入一个元素涉及两个指针更新,这两个更新都是通过 CAS 进行的:从队列当前的最后节点(C)链接到新节点,并把尾指针移动到新的最后一个节点(D)。如果第一步失败,那么队列的状态不变,插入线程会继续重试, 直到成功。一旦操作成功,插入被当成生效,其他线程就可以看到修改。还需要把尾指针移动到新节点的位置上,但是这项工作可以看成是 “清理工作”,因为任何处在这种情况下的线程都可以判断出是否需要这种清理,也知道如何进行清理。
队列总是处于两种状态之一:正常状态(或称静止状态,图 1
和 图 3
)
或中间状态(图 2)。在插入操作之前和第二个 CAS(D)成功之后,队列处在静止状态;在第一个
CAS(C)成功之后,队列处在中间状态。在静止状态时,尾指针指向的链接节点的 next 字段总为 null,而在中间状态时,这个字段为非
null。任何线程通过比较 tail.next
是否为 null,就可以判断出队列的状态,这是让线程可以帮助其他线程 “完成” 操作的关键。
图 2. 处在插入中间状态的队列,在新元素插入之后,尾指针更新之前
插入操作在插入新元素(A)之前,先检查队列是否处在中间状态,如 清单 4 所示。如果是在中间状态,那么肯定有其他线程已经处在元素插入的中途,在步骤(C)和(D)之间。不必等候其他线程完成,当前线程就可以 “帮助” 它完成操作,把尾指针向前移动(B)。如果有必要,它还会继续检查尾指针并向前移动指针,直到队列处于静止状态,这时它就可以开始自己的插入了。
第一个 CAS(C)可能因为两个线程竞争访问队列当前的最后一个元素而失败;在这种情况下,没有发生修改,失去 CAS 的线程会重新装入尾指针并再次尝试。如果第二个 CAS(D)失败,插入线程不需要重试 —— 因为其他线程已经在步骤(B)中替它完成了这个操作!
如果深入 JVM 和操作系统,会发现非阻塞算法无处不在。垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集;调度器使用非阻塞算法有效地调度线程和进程,实现内在锁。在 Mustang(Java 6.0)中,基于锁的 SynchronousQueue
算法被新的非阻塞版本代替。很少有开发人员会直接使用 SynchronousQueue
,但是通过 Executors.newCachedThreadPool()
工厂构建的线程池用它作为工作队列。比较缓存线程池性能的对比测试显示,新的非阻塞同步队列实现提供了几乎是当前实现 3 倍的速度。在 Mustang 的后续版本(代码名称为 Dolphin)中,已经规划了进一步的改进。
非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练,而且要证明算法的正确也极为困难。但是在 Java 版本之间并发性能上的众多改进来自对非阻塞算法的采用,而且随着并发性能变得越来越重要,可以预见在 Java 平台的未来发行版中,会使用更多的非阻塞算法。
学习
-
您可以参阅本文在 developerWorks 全球站点上的 英文原文
。
- “流行的原子
” (developerWorks,Brian Goetz,2004 年 11 月):描述了 Java 5.0 中加入的原子变量类,以及比较-交换操作。
- “Scalable Synchronous Queues
”(ACM SIGPLAN 关于并行编程的原则与实践的讨论会,William N. Scherer III、Doug Lea 和 Michael L. Scott,2006 年 3 月):描述了 Java 6 中新增的
SynchronousQueue
实现的构建和性能优势。
- “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queues
”(Maged M. Michael 和 Michael L. Scott,关于分布式计算原则的讨论会,1996):详细介绍了本文的 清单 4
中演示的非阻塞链接队列的构建。
-
Java Concurrency in Practice
(Addison-Wesley Professional,Brian Goetz、Tim Peierls、Joshua
Bloch、Joseph Bowbeer、David Holmes 和 Doug Lea,2006 年 6 月):一份用 Java
语言开发并发程序的 how-to 手册,包括构建和编辑线程安全的类和程序,避免生存风险,管理性能和测试并发应用程序。
-
Java 技术专区
:数百篇关于 Java 编程各方面的文章。
获得产品和技术
-
JDK 5.0 Update 6
:得到 JDK 5.0 的最新更新。
讨论
-
参与论坛讨论
。
-
developerWorks blog
:加入 developerWorks 社区。
Brian Goetz 作为专业的软件开发人员已经超过 18 年了。他是 Quiotix 的首席顾问,这是家软件开发和咨询公司,位于加州 Los Altos,他还效力于多个 JCP 专家组。Brian 的力作 Java Concurrency In Practice 将于 2006 年初由 Addison-Wesley 出版。请参阅 Brian 在流行的行业出版物上 已经发表和即将发表的文章 。
原文地址:http://www.ibm.com/developerworks/cn/java/j-jtp04186/
发表评论
-
如何正确对用户密码进行加密?
2017-03-26 10:18 1501本文介绍了对密码哈希加密的基础知识,以及什么是正确的加密方式 ... -
HTTP,HTTP2.0,SPDY,HTTPS看这篇就够了
2016-11-30 14:53 576作为一个经常和web打交道的程序员,了解这些协议是必须的,本 ... -
Java I/O模型
2016-10-24 17:42 346Java I/O模型 同步 vs. 异步 同步I/O 每 ... -
如何使代码审查更高效
2016-10-22 07:14 691本文要点 代码审查 ... -
Java并发的四种风味:Thread、Executor、ForkJoin和Actor
2016-09-28 20:04 424本文由 ImportNew - shen ... -
从LongAdder 看更高效的无锁实现
2015-12-08 15:27 645接触到AtomicLong的原因是在看guava的Loadi ... -
分布式系统的事务处理
2014-02-15 20:49 7242014年1月20日 陈皓 当我们在生产线上用一台服 ... -
Linux文件系统十问,你知道吗?
2013-08-20 17:31 872作者:yanfei,腾讯后台架构师,参与项目为搜搜网页开发 ... -
Spring AOP 实现原理与 CGLIB 应用
2013-02-19 15:16 919Spring AOP 实现原理 ... -
JTA 深度历险 - 原理与实现
2012-09-05 16:07 719JTA 深度历险 - 原理 ... -
CAP理论十二年回顾:"规则"变了
2012-08-31 14:58 856CAP理 ... -
XA事务处理
2012-04-06 17:23 970为了说明X/Open XA接口在J ... -
敏捷开发中高质量 Java 代码开发实践
2012-02-18 11:13 886概述 Java 项目开发过程中,由于开发人员的经 ... -
(转)Java 理论与实践: 流行的原子
2011-05-23 17:10 594Java 理论与实践: 流行的原子 新原子类是 ja ...
相关推荐
非阻塞算法是一种在多线程环境中用于处理并发问题的技术,它避免了使用传统的锁定机制,如Java中的`synchronized`关键字。在Java 5.0及以上版本,通过引入`java.util.concurrent`包,非阻塞算法得以实现,这主要归功...
j-concurrent 00 IBM developerWorks...35 Java 理论与实践 非阻塞算法简介.mht 36 Java 理论与实践 处理 InterruptedException.mht 37 Java 理论与实践 正确使用 Volatile 变量.mht 38 使用泛型和并发改善集合.mht
- **非阻塞算法**:书中介绍了一些非阻塞算法的设计原理,如CAS(Compare and Swap)操作等,这些算法可以提高程序的性能和扩展性。 - **性能优化**:并发编程不仅仅是关于多线程,还包括如何优化代码以充分利用多核...
4. **IO与NIO**:Java的IO流提供了读写文件、网络通信等功能,而NIO(New IO)引入了非阻塞I/O,提高了数据传输效率。 5. **多线程**:Java内置了丰富的多线程支持,包括Thread类、Runnable接口以及并发包下的工具...
5. IO与NIO:文件操作、流、字符编码、非阻塞I/O模型。 6. 多线程:线程的创建与同步、线程池、并发工具类。 7. 网络编程:套接字、HTTP客户端、服务器编程。 8. 设计模式:单例、工厂、观察者、装饰器、代理等23种...
分布式Java应用:基础与实践 在当今的互联网时代,分布式系统已经成为企业级应用程序开发的...《分布式java应用:基础与实践》这本书正是为此目的而编写,旨在为Java开发者提供全面的分布式系统理论知识和实践经验。
分布式JAVA应用基础与实践是Java开发领域中的一个重要主题,它涉及到如何通过网络连接将多个独立的Java应用程序协同工作,以实现更大规模、更高性能、更可靠的服务。在本教程中,我们将深入探讨Java在分布式环境中的...
6. **网络编程**:多人在线游戏需要网络编程技能,Java的Socket编程提供了基础的网络通信功能,而NIO(非阻塞I/O)则可以处理大量的并发连接。 7. **数据结构与算法**:高效的数据结构(如数组、链表、树、图)和...
7. **输入输出(IO)与NIO**:了解文件操作、流的概念,以及非阻塞IO模型对性能的影响。 8. **多线程编程**:掌握线程的创建、同步与通信,理解死锁和活锁的概念。 9. **网络编程**:TCP/IP协议的理解,Socket编程...
9. **IO与NIO**: 文件读写、网络通信等挑战可能需要使用Java的IO流或者NIO(非阻塞I/O)进行数据交换。理解流的层次结构和选择合适的IO模型可以提高程序效率。 10. **异常处理**: 学习如何有效地捕获和处理异常是...
6. **I/O优化**:文件读写、网络通信等I/O操作的优化,如使用NIO(非阻塞I/O)提升性能。 7. **类加载器和类初始化**:了解类加载过程,防止不必要的类加载和初始化,减少启动时间和内存占用。 视频教程可能通过...
Java核心面试知识整理包括了对JVM内存区域、...总结而言,这份面试知识点整理为Java开发者提供了一个全面、系统的复习框架,帮助面试者巩固和加深对Java核心技术的理解,以便在面试中展现出扎实的理论基础和实践能力。
- 文件与IO操作:学习NIO(非阻塞IO)和File类,提高文件操作效率。 - 设计模式:了解工厂、单例、装饰器、观察者等常见设计模式,提升代码复用性和可维护性。 3. **Java面试重点** - 垃圾回收与内存管理:理解...
在这个项目中,可能包括了三种常见的调度算法:先来先服务(FCFS)、短作业优先(SJF)和优先级调度。 1. **先来先服务(FCFS)算法**:这是最简单的调度算法,按照进程到达的顺序进行执行。FCFS保证了进程的执行...
Java的Socket和ServerSocket类提供了基础的TCP/IP通信机制,而更高层次的NIO(非阻塞I/O)或Netty框架可以进一步优化网络性能。 5. **DataStructure模块**:为了支持大规模数据处理,Jogak云算法可能需要高效的数据...
7. **IO流与NIO**:Java的输入/输出流(IO)和非阻塞I/O(NIO)库用于读写文件、网络通信等,是处理数据输入输出的关键。 8. **多线程编程**:Java内置了对多线程的支持,可以方便地创建和管理多个执行线程,实现...