右键断点或者断点设置
或者
debug运行
在箭头处切换线程
垃圾收集 Garbage Collection 通常被称为“GC”,它诞生于1960年 MIT 的 Lisp 语言,经过半个多世纪,目前已经十分成熟了。
jvm 中,程序计数器、虚拟机栈、本地方法栈都是随线程而生随线程而灭,栈帧随着方法的进入和退出做入栈和出栈操作,实现了自动的内存清理,因此,我们的内存垃圾回收主要集中于 java 堆和方法区中,在程序运行期间,这部分内存的分配和使用都是动态的.
判断对象是否存活一般有两种方式:
在Java语言中,GC Roots包括:
“标记-清除”(Mark-Sweep)算法,如它的名字一样,算法分为“标记”和“清除”两个阶段:首先标记出所有需要回收的对象,在标记完成后统一回收掉所有被标记的对象。之所以说它是最基础的收集算法,是因为后续的收集算法都是基于这种思路并对其缺点进行改进而得到的。
它的主要缺点有两个:一个是效率问题,标记和清除过程的效率都不高;另外一个是空间问题,标记清除之后会产生大量不连续的内存碎片,空间碎片太多可能会导致,当程序在以后的运行过程中需要分配较大对象时无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。
“复制”(Copying)的收集算法,它将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉。
这样使得每次都是对其中的一块进行内存回收,内存分配时也就不用考虑内存碎片等复杂情况,只要移动堆顶指针,按顺序分配内存即可,实现简单,运行高效。只是这种算法的代价是将内存缩小为原来的一半,持续复制长生存期的对象则导致效率降低。
复制收集算法在对象存活率较高时就要执行较多的复制操作,效率将会变低。更关键的是,如果不想浪费50%的空间,就需要有额外的空间进行分配担保,以应对被使用的内存中所有对象都100%存活的极端情况,所以在老年代一般不能直接选用这种算法。
根据老年代的特点,有人提出了另外一种“标记-整理”(Mark-Compact)算法,标记过程仍然与“标记-清除”算法一样,但后续步骤不是直接对可回收对象进行清理,而是让所有存活的对象都向一端移动,然后直接清理掉端边界以外的内存
GC分代的基本假设:绝大部分对象的生命周期都非常短暂,存活时间短。
“分代收集”(Generational Collection)算法,把Java堆分为新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中,每次垃圾收集时都发现有大批对象死去,只有少量存活,那就选用复制算法,只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保,就必须使用“标记-清理”或“标记-整理”算法来进行回收。
如果说收集算法是内存回收的方法论,垃圾收集器就是内存回收的具体实现
串行收集器是最古老,最稳定以及效率高的收集器,可能会产生较长的停顿,只使用一个线程去回收。新生代、老年代使用串行回收;新生代复制算法、老年代标记-压缩;垃圾收集的过程中会Stop The World(服务暂停)
参数控制:
ParNew收集器其实就是Serial收集器的多线程版本。新生代并行,老年代串行;新生代复制算法、老年代标记-压缩
参数控制:
Parallel Scavenge收集器类似ParNew收集器,Parallel收集器更关注系统的吞吐量。可以通过参数来打开自适应调节策略,虚拟机会根据当前系统的运行情况收集性能监控信息,动态调整这些参数以提供最合适的停顿时间或最大的吞吐量;也可以通过参数控制GC的时间不大于多少毫秒或者比例;新生代复制算法、老年代标记-压缩
参数控制:
Parallel Old是Parallel Scavenge收集器的老年代版本,使用多线程和“标记-整理”算法。这个收集器是在JDK 1.6中才开始提供
参数控制:
CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的收集器。目前很大一部分的Java应用都集中在互联网站或B/S系统的服务端上,这类应用尤其重视服务的响应速度,希望系统停顿时间最短,以给用户带来较好的体验。
从名字(包含“Mark Sweep”)上就可以看出CMS收集器是基于“标记-清除”算法实现的,它的运作过程相对于前面几种收集器来说要更复杂一些,整个过程分为4个步骤,包括:
其中初始标记、重新标记这两个步骤仍然需要“Stop The World”。初始标记仅仅只是标记一下GC Roots能直接关联到的对象,速度很快,并发标记阶段就是进行GC Roots Tracing的过程,而重新标记阶段则是为了修正并发标记期间,因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录,这个阶段的停顿时间一般会比初始标记阶段稍长一些,但远比并发标记的时间短。
由于整个过程中耗时最长的并发标记和并发清除过程中,收集器线程都可以与用户线程一起工作,所以总体上来说,CMS收集器的内存回收过程是与用户线程一起并发地执行。老年代收集器(新生代使用ParNew)
优点:并发收集、低停顿
缺点:产生大量空间碎片、并发阶段会降低吞吐量
参数控制:
G1是目前技术发展的最前沿成果之一,HotSpot开发团队赋予它的使命是未来可以替换掉JDK1.5中发布的CMS收集器。与CMS收集器相比G1收集器有以下特点:
上面提到的垃圾收集器,收集的范围都是整个新生代或者老年代,而G1不再是这样。使用G1收集器时,Java堆的内存布局与其他收集器有很大差别,它将整个Java堆划分为多个大小相等的独立区域(Region),虽然还保留有新生代和老年代的概念,但新生代和老年代不再是物理隔阂了,它们都是一部分(可以不连续)Region的集合。
G1的新生代收集跟ParNew类似,当新生代占用达到一定比例的时候,开始出发收集。和CMS类似,G1收集器收集老年代对象会有短暂停顿。
收集步骤:
标记阶段,首先初始标记(Initial-Mark),这个阶段是停顿的(Stop the World Event),并且会触发一次普通Mintor GC。对应GC log:GC pause (young) (inital-mark)
Root Region Scanning,程序运行过程中会回收survivor区(存活到老年代),这一过程必须在young GC之前完成。
Concurrent Marking,在整个堆中进行并发标记(和应用程序并发执行),此过程可能被young GC中断。在并发标记阶段,若发现区域对象中的所有对象都是垃圾,那个这个区域会被立即回收(图中打X)。同时,并发标记过程中,会计算每个区域的对象活性(区域中存活对象的比例)。
![Concurrent Marking](Java-JVM-GC算法&垃圾收集器/Concurrent Marking.png)
Remark, 再标记,会有短暂停顿(STW)。再标记阶段是用来收集 并发标记阶段 产生新的垃圾(并发阶段和应用程序一同运行);G1中采用了比CMS更快的初始快照算法:snapshot-at-the-beginning (SATB)。
Copy/Clean up,多线程清除失活对象,会有STW。G1将回收区域的存活对象拷贝到新区域,清除Remember Sets,并发清空回收区域并把它返回到空闲区域链表中。
新生代GC策略 | 年老代GC策略 | 说明 | |
---|---|---|---|
组合1 | Serial | Serial Old | Serial和Serial Old都是单线程进行GC,特点就是GC时暂停所有应用线程。 |
组合2 | Serial | CMS+Serial Old | CMS(Concurrent Mark Sweep)是并发GC,实现GC线程和应用线程并发工作,不需要暂停所有应用线程。另外,当CMS进行GC失败时,会自动使用Serial Old策略进行GC。 |
组合3 | ParNew | CMS | 使用-XX:+UseParNewGC选项来开启。ParNew是Serial的并行版本,可以指定GC线程数,默认GC线程数为CPU的数量。可以使用-XX:ParallelGCThreads选项指定GC的线程数。 \n如果指定了选项-XX:+UseConcMarkSweepGC选项,则新生代默认使用ParNew GC策略。 |
组合4 | ParNew | Serial Old | 使用-XX:+UseParNewGC选项来开启。新生代使用ParNew GC策略,年老代默认使用Serial Old GC策略。 |
组合5 | Parallel Scavenge | Serial Old | Parallel Scavenge策略主要是关注一个可控的吞吐量:应用程序运行时间 / (应用程序运行时间 + GC时间),可见这会使得CPU的利用率尽可能的高,适用于后台持久运行的应用程序,而不适用于交互较多的应用程序。 |
组合6 | Parallel Scavenge | Parallel Old | Parallel Old是Serial Old的并行版本 |
组合7 | G1GC | G1GC | -XX:+UnlockExperimentalVMOptions -XX:+UseG1GC #开启 \n -XX:MaxGCPauseMillis =50 #暂停时间目标 \n -XX:GCPauseIntervalMillis =200 #暂停间隔目标 \n -XX:+G1YoungGenSize=512m #年轻代大小 \n -XX:SurvivorRatio=6 #幸存区比例 |
时间:2020/07/19 01:44:26
图中展示了七种作用于不同分代的收集器,如果两个收集器之间存在连线,就说明它们可以搭配使用。在JDK8时将 Serial+CMS,ParNew+Serial Old 这两个组合声明为废弃,并在 JDK9 中完全取消了这些组合的支持
先明确一些概念
串行(Serial)
并行(Parallel):指多条垃圾收集线程并行工作,但此时用户线程仍然处于等待状态
暂停式(Stop the world)
并发(Concurrent):指用户线程与垃圾收集线程同时执行
压缩(Compacting)和非压缩(Non-Compacting):这一组概念是指,在垃圾回收结束之后,是否需要把所有的存活对象挪到一起,占据一个连续空间。在Compacting之后,也意味着可用内存占据了一个连续的空间,这个时候就可以使用bump-the-pointer的分配内存技术。在这种技术中,只需要持有一个指针指向已分配内存的尾部。每次分配的时候只需要检查剩余空闲空间能否容纳新的对象,而后分配内存并且将指针指向新的尾部。这种Compacting的计数,在一些算法中需要付出额外的代价,这个代价要么是需要额外的内存空间,要么是额外的回收时间。
并发和并行是一对比较容易搞混的概念。并发是指,垃圾回收和应用可以在一段时间内同时运行,这个概念和操作系统上的概念是一致的。在HotSpot中,并发垃圾回收算法中大部分垃圾回收的工作都是在并发的情况下完成的,但是并不能完全免除Stop-the-world。并行是指利用多个CPU,多个线程同时进行垃圾回收。
在衡量一个垃圾回收算法上,最为主要的两个度量是:
可以看到一个有趣的地方:暂停时间和吞吐量对堆的大小要求是不一样的。暂停时间要想短,那么应该有更小堆;而吞吐量要大,需要更大的堆。
新生代,标记-复制算法,单线程。进行垃圾收集时,必须暂停其他所有工作线程,直到它收集结束
ParNew 本质上是 Serial 收集器的多线程并行版本
新生代,标记复制算法,多线程,主要关注吞吐量
吞吐量=运行用户代码时间/(运行用户代码时间+运行垃圾收集时间)
老年代,标记-整理算法,单线程,是 Serial 收集器的老年代版本
用处有如下 2 个
老年代,标记-整理算法,多线程,是 Parallel Scavenge 收集器的老年代版本
在注重吞吐量或者处理器资源较为稀缺的场合,都可以优先考虑 Parallel Scavenge 加 Parallel Old 收集器这个组合
老年代,标记-清除算法,多线程,主要关注延迟
运作过程分为4个步骤
收集器 | 收集对象和算法 | 收集器类型 | 说明 | 适用场景 |
---|---|---|---|---|
Serial | 新生代,复制算法 | 单线程 | 简单高效;适合内存不大的情况 | |
ParNew | 新生代,复制算法 | 并行的多线程收集器 | ParNew垃圾收集器是Serial收集器的多线程版本 | 搭配CMS垃圾回收器的首选 |
Parallel Scavenge吞吐量优先收集器 | 新生代,复制算法 | 并行的多线程收集器 | 类似ParNew,更加关注吞吐量,达到一个可控制的吞吐量 | 本身是Server级别多CPU机器上的默认GC方式,主要适合后台运算不需要太多交互的任务 |
收集器 | 收集对象和算法 | 收集器类型 | 说明 | 适用场景 |
---|---|---|---|---|
Serial Old | 老年代,标记整理算法 | 单线程 | Client模式下虚拟机使用 | |
Parallel Old | 老年代,标记整理算法 | 并行的多线程收集器 | Paraller Scavenge收集器的老年代版本,为了配置Parallel Svavenge的面向吞吐量的特性而开发的对应组合 | 在注重吞吐量以及CPU资源敏感的场合采用 |
CMS | 老年代,标记清除算法 | 并行与并发收集器 | 尽可能的缩短垃圾收集时用户线程停止时间;缺点在于,1.内存碎片,2.需要更多CPU资源,3.浮动垃圾问题,需要更大的堆空间 | 重视服务的相应速度,系统停顿时间和用户体验的互联网网站或者B/S系统。互联网后端目前cms是主流的垃圾回收器 |
G1 | 跨新生代和老年代;标记整理+化整为零 | 并行与并发收集器 | JDK1.7才正式引入,采用分区回收的思维,基本不牺牲吞吐量的前提下完成低停顿的内存回收;可预测的停顿是其最大的优势 |
转自:http://www.cnblogs.com/ityouknow/p/5603287.html
类的加载指的是将类的 .class 文件中的二进制数据读入到内存中,将其放在运行时数据区的方法区内,然后在堆区创建一个 java.lang.Class 对象,用来封装类在方法区内的数据结构。类的加载的最终产品是位于堆区中的 Class 对象,Class 对象封装了类在方法区内的数据结构,并且向 Java 程序员提供了访问方法区内的数据结构的接口。
类加载器并不需要等到某个类被“首次主动使用”时再加载它,JVM 规范允许类加载器在预料某个类将要被使用时就预先加载它,如果在预先加载的过程中遇到了 .class 文件缺失或存在错误,类加载器必须在程序首次主动使用该类时才报告错误(LinkageError 错误)如果这个类一直没有被程序主动使用,那么类加载器就不会报告错误
加载 .class 文件的方式
– 从本地系统中直接加载
– 通过网络下载 .class 文件
– 从 zip、jar 等归档文件中加载 .class 文件
– 从专有数据库中提取 .class 文件
– 将 Java 源文件动态编译为 .class 文件
其中类加载的过程包括了加载、验证、准备、解析、初始化五个阶段。在这五个阶段中,加载、验证、准备和初始化这四个阶段发生的顺序是确定的,而解析阶段则不一定,它在某些情况下可以在初始化阶段之后开始,这是为了支持Java语言的运行时绑定(也成为动态绑定或晚期绑定)。另外注意这里的几个阶段是按顺序开始,而不是按顺序进行或完成,因为这些阶段通常都是互相交叉地混合进行的,通常在一个阶段执行的过程中调用或激活另一个阶段。
加载时类加载过程的第一个阶段,在加载阶段,虚拟机需要完成以下三件事情:
相对于类加载的其他阶段而言,加载阶段(准确地说,是加载阶段获取类的二进制字节流的动作)是可控性最强的阶段,因为开发人员既可以使用系统提供的类加载器来完成加载,也可以自定义自己的类加载器来完成加载。
加载阶段完成后,虚拟机外部的二进制字节流就按照虚拟机所需的格式存储在方法区之中,而且在 Java 堆中也创建一个 java.lang.Class 类的对象,这样便可以通过该对象访问方法区中的这些数据。
验证是连接阶段的第一步,这一阶段的目的是为了确保 Class 文件的字节流中包含的信息符合当前虚拟机的要求,并且不会危害虚拟机自身的安全。验证阶段大致会完成 4 个阶段的检验动作:
验证阶段是非常重要的,但不是必须的,它对程序运行期没有影响,如果所引用的类经过反复验证,那么可以考虑采用 -Xverifynone
参数来关闭大部分的类验证措施,以缩短虚拟机类加载的时间。
准备阶段是正式为类变量分配内存并设置类变量初始值的阶段,这些内存都将在方法区中分配。对于该阶段有以下几点需要注意:
这时候进行内存分配的仅包括类变量(static),而不包括实例变量,实例变量会在对象实例化时随着对象一块分配在 Java 堆中。
这里所设置的初始值通常情况下是数据类型默认的零值(如 0、0L、null、false 等),而不是被在 Java 代码中被显式地赋予的值。
假设一个类变量的定义为:public static int value = 3;
那么变量 value 在准备阶段过后的初始值为 0,而不是 3,因为这时候尚未开始执行任何 Java 方法,而把 value 赋值为 3 的 putstatic 指令是在程序编译后,存放于类构造器 <clinit>()
方法之中的,所以把 value 赋值为 3 的动作将在初始化阶段才会执行。
这里还需要注意如下几点:
如果类字段的字段属性表中存在 ConstantValue 属性,即同时被 final 和 static 修饰,那么在准备阶段变量 value 就会被初始化为 ConstValue 属性所指定的值。
假设上面的类变量 value 被定义为: public static final int value = 3;
编译时 Javac 将会为 value 生成 ConstantValue 属性,在准备阶段虚拟机就会根据 ConstantValue 的设置将 value 赋值为 3。回忆上一篇博文中对象被动引用的第 2 个例子,便是这种情况。我们可以理解为 static final 常量在编译期就将其结果放入了调用它的类的常量池中
解析阶段是虚拟机将常量池内的符号引用替换为直接引用的过程,解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用点限定符7类符号引用进行。符号引用就是一组符号来描述目标,可以是任何字面量。
直接引用就是直接指向目标的指针、相对偏移量或一个间接定位到目标的句柄。
初始化,为类的静态变量赋予正确的初始值,JVM 负责对类进行初始化,主要对类变量进行初始化。在 Java 中对类变量进行初始值设定有两种方式:
JVM 初始化步骤
类初始化时机:只有当对类的主动使用的时候才会导致类的初始化,类的主动使用包括以下六种:
Class.forName(“com.shengsiyuan.Test”)
)结束生命周期
在如下几种情况下,Java虚拟机将结束生命周期
System.exit()
方法寻找类加载器,先来一个小例子
1 | package com.neo.classloader; |
运行后,输出结果:
1 | sun.misc.Launcher$AppClassLoader@64fef26a |
从上面的结果可以看出,并没有获取到 ExtClassLoader 的父 Loader,原因是 Bootstrap Loader(引导类加载器)是用 C 语言实现的,找不到一个确定的返回父 Loader 的方式,于是就返回 null。
这几种类加载器的层次关系如下图所示:
注意:这里父类加载器并不是通过继承关系来实现的,而是采用组合实现的。
站在 Java 虚拟机的角度来讲,只存在两种不同的类加载器:启动类加载器:它使用 C++ 实现(这里仅限于 Hotspot,也就是 JDK1.5 之后默认的虚拟机,有很多其他的虚拟机是用 Java 语言实现的),是虚拟机自身的一部分;所有其他的类加载器:这些类加载器都由 Java 语言实现,独立于虚拟机之外,并且全部继承自抽象类 java.lang.ClassLoader,这些类加载器需要由启动类加载器加载到内存中之后才能去加载其他的类。
站在 Java 开发人员的角度来看,类加载器可以大致划分为以下三类:
JDK\jre\lib
(JDK代表JDK的安装目录,下同)下,或被 -Xbootclasspath
参数指定的路径中的,并且能被虚拟机识别的类库(如 rt.jar,所有的 java.* 开头的类均被 Bootstrap ClassLoader 加载)。启动类加载器是无法被 Java 程序直接引用的。DK\jre\lib\ext
目录中,或者由 java.ext.dirs 系统变量指定的路径中的所有类库(如 javax.* 开头的类),开发者可以直接使用扩展类加载器。应用程序都是由这三种类加载器互相配合进行加载的,如果有必要,我们还可以加入自定义的类加载器。因为 JVM 自带的 ClassLoader 只是懂得从本地文件系统加载标准的 java class 文件,因此如果编写了自己的 ClassLoader,便可以做到如下几点:
JVM 类加载机制
类加载有三种方式:
Class.forName()
方法动态加载ClassLoader.loadClass()
方法动态加载例子:
1 | package com.neo.classloader; |
demo类
1 | public class Test2 { |
分别切换加载方式,会有不同的输出结果。
Class.forName()
和 ClassLoader.loadClass()
区别:
Class.forName()
:将类的 .class 文件加载到 jvm 中之外,还会对类进行解释,执行类中的 static 块;ClassLoader.loadClass()
:只干一件事情,就是将 .class 文件加载到 jvm 中,不会执行 static 中的内容,只有在 newInstance 才会去执行 static 块。注:Class.forName(name, initialize, loader)
带参函数也可控制是否加载 static 块。并且只有调用了 newInstance()
方法采用调用构造函数,创建类的对象。
双亲委派模型的工作流程是:如果一个类加载器收到了类加载的请求,它首先不会自己去尝试加载这个类,而是把请求委托给父加载器去完成,依次向上,因此,所有的类加载请求最终都应该被传递到顶层的启动类加载器中,只有当父加载器在它的搜索范围中没有找到所需的类时,即无法完成该加载,子加载器才会尝试自己去加载该类。
双亲委派机制:
ClassLoader 源码分析:
1 | public Class<?> loadClass(String name)throws ClassNotFoundException { |
双亲委派模型意义:
通常情况下,我们都是直接使用系统类加载器。但是,有的时候,我们也需要自定义类加载器。比如应用是通过网络来传输 Java 类的字节码,为保证安全性,这些字节码经过了加密处理,这时系统类加载器就无法对其进行加载,这样则需要自定义类加载器来实现。自定义类加载器一般都是继承自 ClassLoader 类,从上面对 loadClass 方法来分析来看,我们只需要重写 findClass 方法即可。下面我们通过一个示例来演示自定义类加载器的流程:
1 | package com.neo.classloader; |
自定义类加载器的核心在于对字节码文件的获取,如果是加密的字节码则需要在该类中对文件进行解密。由于这里只是演示,我并未对 class 文件进行加密,因此没有解密的过程。这里有几点需要注意:
任何一个Maven项目都需要定义POM元素packaging(如果不写则默认值为jar)。顾名思义,该元素决定了项目的打包方式。实际的情形中,如果你不声明该元素,Maven会帮你生成一个JAR包;如果你定义该元素的值为war,那你会得到一个WAR包;如果定义其值为POM(比如是一个父模块),那什么包都不会生成。除此之外,Maven默认还支持一些其他的流行打包格式,例如ejb3和ear。你不需要了解具体的打包细节,你所需要做的就是告诉Maven,”我是个什么类型的项目“,这就是约定优于配置的力量。
为了更好的理解Maven的默认打包方式,我们不妨来看看简单的声明背后发生了什么,对一个jar项目执行mvn package操作,会看到如下的输出:
1 | [INFO] --- maven-jar-plugin:2.3.1:jar (default-jar) @ git-demo --- |
相比之下,对一个war项目执行mvn package操作,输出是这样的:
1 | [INFO] --- maven-war-plugin:2.1:war (default-war) @ webapp-demo --- |
对应于同样的package生命周期阶段,Maven为jar项目调用了maven-jar-plugin,为war项目调用了maven-war-plugin,换言之,packaging直接影响Maven的构建生命周期。了解这一点非常重要,特别是当你需要自定义打包行为的时候,你就必须知道去配置哪个插件。一个常见的例子就是在打包war项目的时候排除某些web资源文件,这时就应该配置maven-war-plugin如下:
1 | <plugin> |
maven-jar-plugin
1 | <build> |
转自:http://ifeve.com/amdahls-law/
阿姆达尔定律可以用来计算处理器平行运算之后效率提升的能力。阿姆达尔定律因Gene Amdal 在1967年提出这个定律而得名。绝大多数使用并行或并发系统的开发者有一种并发或并行可能会带来提速的感觉,甚至不知道阿姆达尔定律。不管怎样,了解阿姆达尔定律还是有用的。
我会首先以算术的方式介绍阿姆达尔定律定律,然后再用图表演示一下。
一个程序(或者一个算法)可以按照是否可以被并行化分为下面两个部分:
假设一个程序处理磁盘上的文件。这个程序的一小部分用来扫描路径和在内存中创建文件目录。做完这些后,每个文件交个一个单独的线程去处理。扫描路径和创建文件目录的部分不可以被并行化,不过处理文件的过程可以。
程序串行(非并行)执行的总时间我们记为T。时间T包括不可以被并行和可以被并行部分的时间。不可以被并行的部分我们记为B。那么可以被并行的部分就是T-B。下面的列表总结了这些定义:
从上面可以得出:
1 | T = B + (T – B) |
首先,这个看起来可能有一点奇怪,程序的可并行部分在上面这个公式中并没有自己的标识。然而,由于这个公式中可并行可以用总时间T 和 B(不可并行部分)表示出来,这个公式实际上已经从概念上得到了简化,也即是指以这种方式减少了变量的个数。
T- B 是可并行化的部分,以并行的方式执行可以提高程序的运行速度。可以提速多少取决于有多少线程或者多少个CPU来执行。线程或者CPU的个数我们记为N。可并行化部分被执行的最快时间可以通过下面的公式计算出来:
1 | (T – B ) / N |
或者通过这种方式
1 | (1 / N) * (T – B) |
维基中使用的是第二种方式。
根据阿姆达尔定律,当一个程序的可并行部分使用N个线程或CPU执行时,执行的总时间为:
1 | T(N) = B + ( T – B ) / N |
T(N)指的是在并行因子为N时的总执行时间。因此,T(1)就执行在并行因子为1时程序的总执行时间。使用T(1)代替T,阿姆达尔定律定律看起来像这样:
1 | T(N) = B + (T(1) – B) / N |
表达的意思都是是一样的。
为了更好的理解阿姆达尔定律,让我们来看一个计算的例子。执行一个程序的总时间设为1.程序的不可并行化占40%,按总时间1计算,就是0.4.可并行部分就是1 – 0.4 = 0.6.
在并行因子为2的情况下,程序的执行时间将会是:
1 | T(2) = 0.4 + ( 1 - 0.4 ) / 2 |
在并行因子为5的情况下,程序的执行时间将会是:
1 | T(5) = 0.4 + ( 1 - 0.4 ) / 5 |
为了更好地理解阿姆达尔定律,我会尝试演示这个定定律是如何诞生的。
首先,一个程序可以被分割为两部分,一部分为不可并行部分B,一部分为可并行部分1 – B。如下图:
![amdahl’ s law1.png](Java-并发性和多线程-27.阿姆达尔定律/amdahl’ s law1.png)
在顶部被带有分割线的那条直线代表总时间 T(1)。
下面你可以看到在并行因子为2的情况下的执行时间:
![amdahl’s law2.png](Java-并发性和多线程-27.阿姆达尔定律/amdahl’s law2.png)
并行因子为3的情况:
![amdahl’ s law3.png](Java-并发性和多线程-27.阿姆达尔定律/amdahl’ s law3.png)
从阿姆达尔定律可以看出,程序的可并行化部分可以通过使用更多的硬件(更多的线程或CPU)运行更快。对于不可并行化的部分,只能通过优化代码来达到提速的目的。因此,你可以通过优化不可并行化部分来提高你的程序的运行速度和并行能力。你可以对不可并行化在算法上做一点改动,如果有可能,你也可以把一些移到可并行化放的部分。
如果你优化一个程序的串行化部分,你也可以使用阿姆达尔定律来计算程序优化后的执行时间。如果不可并行部分通过一个因子O来优化,那么阿姆达尔定律看起来就像这样:
1 | T(O, N) = B / O + (1 - B / O) / N |
记住,现在程序的不可并行化部分占了B / O的时间,所以,可并行化部分就占了1 - B / O的时间.
如果B为0.1,O为2,N为5,计算看起来就像这样:
1 | T(2,5) = 0.4 / 2 + (1 - 0.4 / 2) / 5 |
到目前为止,我们只用阿姆达尔定律计算了一个程序或算法在优化后或者并行化后的执行时间。我们也可以使用阿姆达尔定律计算加速比(speedup),也就是经过优化后或者串行化后的程序或算法比原来快了多少。
如果旧版本的程序或算法的执行时间为T,那么增速比就是:
1 | Speedup = T / T(O , N); |
为了计算执行时间,我们常常把T设为1,加速比为原来时间的一个分数。公式大致像下面这样:
1 | Speedup = 1 / T(O,N) |
如果我们使用阿姆达尔定律来代替T(O,N),我们可以得到下面的公式:
1 | Speedup = 1 / ( B / O + (1 - B / O) / N) |
如果B = 0.4, O = 2, N = 5, 计算变成下面这样:
1 | Speedup = 1 / ( 0.4 / 2 + (1 - 0.4 / 2) / 5) |
上面的计算结果可以看出,如果你通过一个因子2来优化不可并行化部分,一个因子5来并行化可并行化部分,这个程序或算法的最新优化版本最多可以比原来的版本快2.77777倍。
虽然阿姆达尔定律允许你并行化一个算法的理论加速比,但是不要过度依赖这样的计算。在实际场景中,当你优化或并行化一个算法时,可以有很多的因子可以被考虑进来。
内存的速度,CPU缓存,磁盘,网卡等可能都是一个限制因子。如果一个算法的最新版本是并行化的,但是导致了大量的CPU缓存浪费,你可能不会再使用x N个CPU来获得x N的期望加速。如果你的内存总线(memory bus),磁盘,网卡或者网络连接都处于高负载状态,也是一样的情况。
我们的建议是,使用阿姆达尔定律定律来指导我们优化程序,而不是用来测量优化带来的实际加速比。记住,有时候一个高度串行化的算法胜过一个并行化的算法,因为串行化版本不需要进行协调管理(上下文切换),而且一个单个的CPU在底层硬件工作(CPU管道、CPU缓存等)上的一致性可能更好。
转自:http://ifeve.com/non-blocking-algorithms/
在并发上下文中,非阻塞算法是一种允许线程在阻塞其他线程的情况下访问共享状态的算法。在绝大多数项目中,在算法中如果一个线程的挂起没有导致其它的线程挂起,我们就说这个算法是非阻塞的。
为了更好的理解阻塞算法和非阻塞算法之间的区别,我会先讲解阻塞算法然后再讲解非阻塞算法。
一个阻塞并发算法一般分下面两步:
很多算法和并发数据结构都是阻塞的。例如,java.util.concurrent.BlockingQueue的不同实现都是阻塞数据结构。如果一个线程要往一个阻塞队列中插入一个元素,队列中没有足够的空间,执行插入操作的线程就会阻塞直到队列中有了可以存放插入元素的空间。
下图演示了一个阻塞算法保证一个共享数据结构的行为:
一个非阻塞并发算法一般包含下面两步:
Java也包含几个非阻塞数据结构。AtomicBoolean,AtomicInteger,AtomicLong,AtomicReference都是非阻塞数据结构的例子。
下图演示了一个非阻塞算法保证一个共享数据结构的行为:
阻塞算法和非阻塞算法的主要不同在于上面两部分描述的它们的行为的第二步。换句话说,它们之间的不同在于当请求操作不能够执行时阻塞算法和非阻塞算法会怎么做。
阻塞算法会阻塞线程知道请求操作可以被执行。非阻塞算法会通知请求线程操作不能够被执行,并返回。
一个使用了阻塞算法的线程可能会阻塞直到有可能去处理请求。通常,其它线程的动作使第一个线程执行请求的动作成为了可能。 如果,由于某些原因线程被阻塞在程序某处,因此不能让第一个线程的请求动作被执行,第一个线程会阻塞——可能一直阻塞或者直到其他线程执行完必要的动作。
例如,如果一个线程产生往一个已经满了的阻塞队列里插入一个元素,这个线程就会阻塞,直到其他线程从这个阻塞队列中取走了一些元素。如果由于某些原因,从阻塞队列中取元素的线程假定被阻塞在了程序的某处,那么,尝试往阻塞队列中添加新元素的线程就会阻塞,要么一直阻塞下去,要么知道从阻塞队列中取元素的线程最终从阻塞队列中取走了一个元素。
在一个多线程系统中,线程间通常通过一些数据结构”交流“。例如可以是任何的数据结构,从变量到更高级的俄数据结构(队列,栈等)。为了确保正确,并发线程在访问这些数据结构的时候,这些数据结构必须由一些并发算法来保证。这些并发算法让这些数据结构成为并发数据结构。
如果某个算法确保一个并发数据结构是阻塞的,它就被称为是一个阻塞算法。这个数据结构也被称为是一个阻塞,并发数据结构。
如果某个算法确保一个并发数据结构是非阻塞的,它就被称为是一个非阻塞算法。这个数据结构也被称为是一个非阻塞,并发数据结构。
每个并发数据结构被设计用来支持一个特定的通信方法。使用哪种并发数据结构取决于你的通信需要。在接下里的部分,我会引入一些非阻塞并发数据结构,并讲解它们各自的适用场景。通过这些并发数据结构工作原理的讲解应该能在非阻塞数据结构的设计和实现上一些启发。
Java中的volatile变量是直接从主存中读取值的变量。当一个新的值赋给一个volatile变量时,这个值总是会被立即写回到主存中去。这样就确保了,一个volatile变量最新的值总是对跑在其他CPU上的线程可见。其他线程每次会从主存中读取变量的值,而不是比如线程所运行CPU的CPU缓存中。
colatile变量是非阻塞的。修改一个volatile变量的值是一耳光原子操作。它不能够被中断。不过,在一个volatile变量上的一个 read-update-write 顺序的操作不是原子的。因此,下面的代码如果由多个线程执行可能导致竞态条件。
1 | volatile myVar = 0; |
首先,myVar这个volatile变量的值被从主存中读出来赋给了temp变量。然后,temp变量自增1。然后,temp变量的值又赋给了myVar这个volatile变量这意味着它会被写回到主存中。
如果两个线程执行这段代码,然后它们都读取myVar的值,加1后,把它的值写回到主存。这样就存在myVar仅被加1,而没有被加2的风险。
你可能认为你不会写像上面这样的代码,但是在实践中上面的代码等同于如下的代码:
1 | myVar++; |
执行上面的代码时,myVar的值读到一个CPU寄存器或者一个本地CPU缓存中,myVar加1,然后这个CPU寄存器或者CPU缓存中的值被写回到主存中。
在一些场景下,你仅有一个线程在向一个共享变量写,多个线程在读这个变量。当仅有一个线程在更新一个变量,不管有多少个线程在读这个变量,都不会发生竞态条件。因此,无论时候当仅有一个线程在写一个共享变量时,你可以把这个变量声明为volatile。
当多个线程在一个共享变量上执行一个 read-update-write 的顺序操作时才会发生竞态条件。如果你只有一个线程在执行一个 raed-update-write 的顺序操作,其他线程都在执行读操作,将不会发生竞态条件。
下面是一个单个写线程的例子,它没有采取同步手段但任然是并发的。
1 | public class SingleWriterCounter{ |
多个线程访问同一个Counter实例,只要仅有一个线程调用inc()方法,这里,我不是说在某一时刻一个线程,我的意思是,仅有相同的,单个的线程被允许去调用inc()>方法。多个线程可以调用count()方法。这样的场景将不会发生任何竞态条件。
下图,说明了线程是如何访问count这个volatile变量的。
使用多个volatile变量去创建数据结构是可以的,构建出的数据结构中每一个volatile变量仅被一个单个的线程写,被多个线程读。每个volatile变量可能被一个不同的线程写(但仅有一个)。使用像这样的数据结构多个线程可以使用这些volatile变量以一个非阻塞的方法彼此发送信息。
下面是一个简单的例子:
1 | public class DoubleWriterCounter{ |
如你所见,DoubleWriterCoounter现在包含两个volatile变量以及两对自增和读方法。在某一时刻,仅有一个单个的线程可以调用inc(),仅有一个单个的线程可以访问incB()。不过不同的线程可以同时调用incA()和incB()。countA()和countB()可以被多个线程调用。这将不会引发竞态条件。
DoubleWriterCoounter可以被用来比如线程间通信。countA和countB可以分别用来存储生产的任务数和消费的任务数。下图,展示了两个线程通过类似于上面的一个数据结构进行通信的。
聪明的读者应该已经意识到使用两个SingleWriterCounter可以达到使用DoubleWriterCoounter的效果。如果需要,你甚至可以使用多个线程和SingleWriterCounter实例。
如果你确实需要多个线程区写同一个共享变量,volatile变量是不合适的。你将会需要一些类型的排它锁(悲观锁)访问这个变量。下面代码演示了使用Java中的同步块进行排他访问的。
1 | public class SynchronizedCounter{ |
注意,,inc()和count()方法都包含一个同步块。这也是我们像避免的东西——同步块和 wait()-notify 调用等。
我们可以使用一种Java的原子变量来代替这两个同步块。在这个例子是AtomicLong。下面是SynchronizedCounter类的AtomicLong实现版本。
1 | import java.util.concurrent.atomic.AtomicLong; |
这个版本仅仅是上一个版本的线程安全版本。这一版我们感兴趣的是inc()方法的实现。inc()方法中不再含有一个同步块。而是被下面这些代码替代:
1 | boolean updated = false; |
上面这些代码并不是一个原子操作。也就是说,对于两个不同的线程去调用inc()方法,然后执行long prevCount = this.count.get()语句,因此获得了这个计数器的上一个count。但是,上面的代码并没有包含任何的竞态条件。
秘密就在于while循环里的第二行代码。compareAndSet()方法调用是一个原子操作。它用一个期望值和AtomicLong 内部的值去比较,如果这两个值相等,就把AtomicLong内部值替换为一个新值。compareAndSet()通常被CPU中的compare-and-swap指令直接支持。因此,不需要去同步,也不需要去挂起线程。
假设,这个AtomicLong的内部值是20,。然后,两个线程去读这个值,都尝试调用compareAndSet(20, 20 + 1)。尽管compareAndSet()是一个原子操作,这个方法也会被这两个线程相继执行(某一个时刻只有一个)。
第一个线程会使用期望值20(这个计数器的上一个值)与AtomicLong的内部值进行比较。由于两个值是相等的,AtomicLong会更新它的内部值至21(20 + 1 )。变量updated被修改为true,while循环结束。
现在,第二个线程调用compareAndSet(20, 20 + 1)。由于AtomicLong的内部值不再是20,这个调用将不会成功。AtomicLong的值不会再被修改为21。变量,updated被修改为false,线程将会再次在while循环外自旋。这段时间,它会读到值21并企图把值更新为22。如果在此期间没有其它线程调用inc()。第二次迭代将会成功更新AtomicLong的内部值到22。
上一部分展现的代码被称为乐观锁(optimistic locking)。乐观锁区别于传统的锁,有时也被称为悲观锁。传统的锁会使用同步块或其他类型的锁阻塞对临界区域的访问。一个同步块或锁可能会导致线程挂起。
乐观锁允许所有的线程在不发生阻塞的情况下创建一份共享内存的拷贝。这些线程接下来可能会对它们的拷贝进行修改,并企图把它们修改后的版本写回到共享内存中。如果没有其它线程对共享内存做任何修改, CAS操作就允许线程将它的变化写回到共享内存中去。如果,另一个线程已经修改了共享内存,这个线程将不得不再次获得一个新的拷贝,在新的拷贝上做出修改,并尝试再次把它们写回到共享内存中去。
称之为“乐观锁”的原因就是,线程获得它们想修改的数据的拷贝并做出修改,在乐观的假在此期间没有线程对共享内存做出修改的情况下。当这个乐观假设成立时,这个线程仅仅在无锁的情况下完成共享内存的更新。当这个假设不成立时,线程所做的工作就会被丢弃,但任然不使用锁。
乐观锁使用于共享内存竞用不是非常高的情况。如果共享内存上的内容非常多,仅仅因为更新共享内存失败,就用浪费大量的CPU周期用在拷贝和修改上。但是,如果砸共享内存上有大量的内容,无论如何,你都要把你的代码设计的产生的争用更低。
我们这里提到的乐观锁机制是非阻塞的。如果一个线程获得了一份共享内存的拷贝,当尝试修改时,发生了阻塞,其它线程去访问这块内存区域不会发生阻塞。
对于一个传统的加锁/解锁模式,当一个线程持有一个锁时,其它所有的线程都会一直阻塞直到持有锁的线程再次释放掉这个锁。如果持有锁的这个线程被阻塞在某处,这个锁将很长一段时间不能被释放,甚至可能一直不能被释放。
简单的CAS乐观锁可以用于共享数据结果,这样一来,整个数据结构都可以通过一个单个的CAS操作被替换成为一个新的数据结构。尽管,使用一个修改后的拷贝来替换真个数据结构并不总是可行的。
假设,这个共享数据结构是队列。每当线程尝试从向队列中插入或从队列中取出元素时,都必须拷贝这个队列然后在拷贝上做出期望的修改。我们可以通过使用一个AtomicReference来达到同样的目的。拷贝引用,拷贝和修改队列,尝试替换在AtomicReference中的引用让它指向新创建的队列。
然而,一个大的数据结构可能会需要大量的内存和CPU周期来复制。这会使你的程序占用大量的内存和浪费大量的时间再拷贝操作上。这将会降低你的程序的性能,特别是这个数据结构的竞用非常高情况下。更进一步说,一个线程花费在拷贝和修改这个数据结构上的时间越长,其它线程在此期间修改这个数据结构的可能性就越大。如你所知,如果另一个线程修改了这个数据结构在它被拷贝后,其它所有的线程都不等不再次执行 拷贝-修改 操作。这将会增大性能影响和内存浪费,甚至更多。
接下来的部分将会讲解一种实现非阻塞数据结构的方法,这种数据结构可以被并发修改,而不仅仅是拷贝和修改。
用来替换拷贝和修改整个数据结构,一个线程可以共享它们对共享数据结构预期的修改。一个线程向对修改某个数据结构的过程变成了下面这样:
如你所见,第二步可以阻塞其他线程提交一个预期的修改。因此,第二步实际的工作是作为这个数据结构的一个锁。如果一个线程已经成功提交了一个预期的修改,其他线程就不可以再提交一个预期的修改直到第一个预期的修改执行完毕。
如果一个线程提交了一个预期的修改,然后做一些其它的工作时发生阻塞,这时候,这个共享数据结构实际上是被锁住的。其它线程可以检测到它们不能够提交一个预期的修改,然后回去做一些其它的事情。很明显,我们需要解决这个问题。
为了避免一个已经提交的预期修改可以锁住共享数据结构,一个已经提交的预期修改必须包含足够的信息让其他线程来完成这次修改。因此,如果一个提交了预期修改的线程从未完成这次修改,其他线程可以在它的支持下完成这次修改,保证这个共享数据结构对其他线程可用。
下图说明了上面描述的非阻塞算法的蓝图:
修改必须被当做一个或多个CAS操作来执行。因此,如果两个线程尝试去完成同一个预期修改,仅有一个线程可以所有的CAS操作。一旦一条CAS操作完成后,再次企图完成这个CAS操作都不会“得逞”。
上面演示的算法可以称之为A-B-A问题。A-B-A问题指的是一个变量被从A修改到了B,然后又被修改回A的一种情景。其他线程对于这种情况却一无所知。
如果线程A检查正在进行的数据更新,拷贝,被线程调度器挂起,一个线程B在此期可能可以访问这个共享数据结构。如果线程对这个数据结构执行了全部的更新,移除了它的预期修改,这样看起来,好像线程A自从拷贝了这个数据结构以来没有对它做任何的修改。然而,一个修改确实已经发生了。当线程A继续基于现在已经过期的数据拷贝执行它的更新时,这个数据修改已经被线程B的修改破坏。
下图说明了上面提到的A-B-A问题:
A-B-A通常的解决方法就是不再仅仅替换指向一个预期修改对象的指针,而是指针结合一个计数器,然后使用一个单个的CAS操作来替换指针 + 计数器。这在支持指针的语言像C和C++中是可行的。因此,尽管当前修改指针被设置回指向 “不是正在进行的修改”(no ongoing modification),指针 + 计数器的计数器部分将会被自增,使修改对其它线程是可见的。
在Java中,你不能将一个引用和一个计数器归并在一起形成一个单个的变量。不过Java提供了AtomicStampedReference类,利用这个类可以使用一个CAS操作自动的替换一个引用和一个标记(stamp)。
下面的代码意在在如何实现非阻塞算法上一些启发。这个模板基于这篇教程所讲的东西。
注意:在非阻塞算法方面,我并不是一位专家,所以,下面的模板可能错误。不要基于我提供的模板实现自己的非阻塞算法。这个模板意在给你一个关于非阻塞算法大致是什么样子的一个idea。如果,你想实现自己的非阻塞算法,首先学习一些实际的工业水平的非阻塞算法的时间,在实践中学习更多关于非阻塞算法实现的知识。
1 | import java.util.concurrent.atomic.AtomicBoolean; |
正确的设计和实现非阻塞算法是不容易的。在尝试设计你的非阻塞算法之前,看一看是否已经有人设计了一种非阻塞算法正满足你的需求。
Java已经提供了一些非阻塞实现(比如 ConcurrentLinkedQueue),相信在Java未来的版本中会带来更多的非阻塞算法的实现。
除了Java内置非阻塞数据结构还有很多开源的非阻塞数据结构可以使用。例如,LAMX Disrupter和Cliff Click实现的非阻塞 HashMap。查看我的Java concurrency references page查看更多的资源。
非阻塞算法和阻塞算法相比有几个好处。下面让我们分别看一下:
非阻塞算法的第一个好处是,给了线程一个选择当它们请求的动作不能够被执行时做些什么。不再是被阻塞在那,请求线程关于做什么有了一个选择。有时候,一个线程什么也不能做。在这种情况下,它可以选择阻塞或自我等待,像这样把CPU的使用权让给其它的任务。不过至少给了请求线程一个选择的机会。
在一个单个的CPU系统可能会挂起一个不能执行请求动作的线程,这样可以让其它线程获得CPU的使用权。不过即使在一个单个的CPU系统阻塞可能导致死锁,线程饥饿等并发问题。
非阻塞算法的第二个好处是,一个线程的挂起不能导致其它线程挂起。这也意味着不会发生死锁。两个线程不能互相彼此等待来获得被对方持有的锁。因为线程不会阻塞当它们不能执行它们的请求动作时,它们不能阻塞互相等待。非阻塞算法任然可能产生活锁(live lock),两个线程一直请求一些动作,但一直被告知不能够被执行(因为其他线程的动作)。
挂起和恢复一个线程的代价是昂贵的。没错,随着时间的推移,操作系统和线程库已经越来越高效,线程挂起和恢复的成本也不断降低。不过,线程的挂起和户对任然需要付出很高的代价。
无论什么时候,一个线程阻塞,就会被挂起。因此,引起了线程挂起和恢复过载。由于使用非阻塞算法线程不会被挂起,这种过载就不会发生。这就意味着CPU有可能花更多时间在执行实际的业务逻辑上而不是上下文切换。
在一个多个CPU的系统上,阻塞算法会对阻塞算法产生重要的影响。运行在CPUA上的一个线程阻塞等待运行在CPU B上的一个线程。这就降低了程序天生就具备的并行水平。当然,CPU A可以调度其他线程去运行,但是挂起和激活线程(上下文切换)的代价是昂贵的。需要挂起的线程越少越好。
在这里我们提到的延迟指的是一个请求产生到线程实际的执行它之间的时间。因为在非阻塞算法中线程不会被挂起,它们就不需要付昂贵的,缓慢的线程激活成本。这就意味着当一个请求执行时可以得到更快的响应,减少它们的响应延迟。
非阻塞算法通常忙等待直到请求动作可以被执行来降低延迟。当然,在一个非阻塞数据数据结构有着很高的线程争用的系统中,CPU可能在它们忙等待期间停止消耗大量的CPU周期。这一点需要牢牢记住。非阻塞算法可能不是最好的选择如果你的数据结构哦有着很高的线程争用。不过,也常常存在通过重构你的程序来达到更低的线程争用。
转自:http://ifeve.com/anatomy-of-a-synchronizer/
虽然许多同步器(如锁,信号量,阻塞队列等)功能上各不相同,但它们的内部设计上却差别不大。换句话说,它们内部的的基础部分是相同(或相似)的。了解这些基础部件能在设计同步器的时候给我们大大的帮助。这就是本文要细说的内容。
注:本文的内容是哥本哈根信息技术大学一个由Jakob Jenkov,Toke Johansen和Lars Bjørn参与的M.Sc.学生项目的部分成果。在此项目期间我们咨询Doug Lea是否知道类似的研究。有趣的是在开发Java 5并发工具包期间他已经提出了类似的结论。Doug Lea的研究,我相信,在《Java Concurrency in Practice》一书中有描述。这本书有一章“剖析同步器”就类似于本文,但不尽相同。
大部分同步器都是用来保护某个区域(临界区)的代码,这些代码可能会被多线程并发访问。要实现这个目标,同步器一般要支持下列功能:
并不是所有同步器都包含上述部分,也有些并不完全遵照上面的内容。但通常你能从中发现这些部分的一或多个。
同步器中的状态是用来确定某个线程是否有访问权限。在Lock中,状态是boolean类型的,表示当前Lock对象是否处于锁定状态。在BoundedSemaphore中,内部状态包含一个计数器(int类型)和一个上限(int类型),分别表示当前已经获取的许可数和最大可获取的许可数。BlockingQueue的状态是该队列中元素列表以及队列的最大容量。
下面是Lock和BoundedSemaphore中的两个代码片段。
1 | public class Lock{ |
访问条件决定调用test-and-set-state方法的线程是否可以对状态进行设置。访问条件一般是基于同步器状态的。通常是放在一个while循环里,以避免虚假唤醒问题。访问条件的计算结果要么是true要么是false。
Lock中的访问条件只是简单地检查isLocked的值。根据执行的动作是“获取”还是“释放”,BoundedSemaphore中实际上有两个访问条件。如果某个线程想“获取”许可,将检查signals变量是否达到上限;如果某个线程想“释放”许可,将检查signals变量是否为0。
这里有两个来自Lock和BoundedSemaphore的代码片段,它们都有访问条件。注意观察条件是怎样在while循环中检查的。
1 | public class Lock{ |
1 | public class BoundedSemaphore { |
一旦一个线程获得了临界区的访问权限,它得改变同步器的状态,让其它线程阻塞,防止它们进入临界区。换而言之,这个状态表示正有一个线程在执行临界区的代码。其它线程想要访问临界区的时候,该状态应该影响到访问条件的结果。
在Lock中,通过代码设置isLocked = true来改变状态,在信号量中,改变状态的是signals–或signals++;
这里有两个状态变化的代码片段:
1 | public class Lock{ |
1 | public class BoundedSemaphore { |
一旦某个线程改变了同步器的状态,可能需要通知其它等待的线程状态已经变了。因为也许这个状态的变化会让其它线程的访问条件变为true。
通知策略通常分为三种:
通知所有等待的线程非常简单。所有等待的线程都调用的同一个对象上的wait()方法,某个线程想要通知它们只需在这个对象上调用notifyAll()方法。
通知等待线程中的任意一个也很简单,只需将notifyAll()调用换成notify()即可。调用notify方法没办法确定唤醒的是哪一个线程,也就是“等待线程中的任意一个”。
有时候可能需要通知指定的线程而非任意一个等待的线程。例如,如果你想保证线程被通知的顺序与它们进入同步块的顺序一致,或按某种优先级的顺序来通知。想要实现这种需求,每个等待的线程必须在其自有的对象上调用wait()。当通知线程想要通知某个特定的等待线程时,调用该线程自有对象的notify()方法即可。饥饿和公平中有这样的例子。
下面是通知策略的一个例子(通知任意一个等待线程):
1 | public class Lock{ |
同步器中最常见的有两种类型的方法,test-and-set是第一种(set是另一种)。Test-and-set的意思是,调用这个方法的线程检查访问条件,如若满足,该线程设置同步器的内部状态来表示它已经获得了访问权限。
状态的改变通常使其它试图获取访问权限的线程计算条件状态时得到false的结果,但并不一定总是如此。例如,在读写锁中,获取读锁的线程会更新读写锁的状态来表示它获取到了读锁,但是,只要没有线程请求写锁,其它请求读锁的线程也能成功。
test-and-set很有必要是原子的,也就是说在某个线程检查和设置状态期间,不允许有其它线程在test-and-set方法中执行。
test-and-set方法的程序流通常遵照下面的顺序:
下面的ReadWriteLock类的lockWrite()方法展示了test-and-set方法。调用lockWrite()的线程在检查之前先设置状态(writeRequests++)。然后检查canGrantWriteAccess()中的访问条件,如果检查通过,在退出方法之前再次设置内部状态。这个方法中没有去通知等待线程。
1 | public class ReadWriteLock{ |
下面的BoundedSemaphore类有两个test-and-set方法:take()和release()。两个方法都有检查和设置内部状态。
1 | public class BoundedSemaphore { |
set方法是同步器中常见的第二种方法。set方法仅是设置同步器的内部状态,而不先做检查。set方法的一个典型例子是Lock类中的unlock()方法。持有锁的某个线程总是能够成功解锁,而不需要检查该锁是否处于解锁状态。
set方法的程序流通常如下:
这里是unlock()方法的一个例子:
1 | public class Lock{ |
转自:http://ifeve.com/thread-pools/
线程池(Thread Pool)对于限制应用程序中同一时刻运行的线程数很有用。因为每启动一个新线程都会有相应的性能开销,每个线程都需要给栈分配一些内存等等。
我们可以把并发执行的任务传递给一个线程池,来替代为每个并发执行的任务都启动一个新的线程。只要池里有空闲的线程,任务就会分配给一个线程执行。在线程池的内部,任务被插入一个阻塞队列(Blocking Queue),线程池里的线程会去取这个队列里的任务。当一个新任务插入队列时,一个空闲线程就会成功的从队列中取出任务并且执行它。
线程池经常应用在多线程服务器上。每个通过网络到达服务器的连接都被包装成一个任务并且传递给线程池。线程池的线程会并发的处理连接上的请求。以后会再深入有关 Java 实现多线程服务器的细节。
Java 5 在 java.util.concurrent 包中自带了内置的线程池,所以你不用非得实现自己的线程池。你可以阅读我写的 java.util.concurrent.ExecutorService 的文章以了解更多有关内置线程池的知识。不过无论如何,知道一点关于线程池实现的知识总是有用的。
这里有一个简单的线程池实现:
1 | public class ThreadPool { |
(校注:原文有编译错误,我修改了下)
1 | public class PoolThread extends Thread { |
线程池的实现由两部分组成。类 ThreadPool 是线程池的公开接口,而类 PoolThread 用来实现执行任务的子线程。
为了执行一个任务,方法 ThreadPool.execute(Runnable r) 用 Runnable 的实现作为调用参数。在内部,Runnable 对象被放入 阻塞队列 (Blocking Queue),等待着被子线程取出队列。
一个空闲的 PoolThread 线程会把 Runnable 对象从队列中取出并执行。你可以在 PoolThread.run() 方法里看到这些代码。执行完毕后,PoolThread 进入循环并且尝试从队列中再取出一个任务,直到线程终止。
调用 ThreadPool.stop() 方法可以停止 ThreadPool。在内部,调用 stop 先会标记 isStopped 成员变量(为 true)。然后,线程池的每一个子线程都调用 PoolThread.stop() 方法停止运行。注意,如果线程池的 execute() 在 stop() 之后调用,execute() 方法会抛出 IllegalStateException 异常。
子线程会在完成当前执行的任务后停止。注意 PoolThread.stop() 方法中调用了 this.interrupt()。它确保阻塞在 taskQueue.dequeue() 里的 wait() 调用的线程能够跳出 wait() 调用(校对注:因为执行了中断interrupt,它能够打断这个调用),并且抛出一个 InterruptedException 异常离开 dequeue() 方法。这个异常在 PoolThread.run() 方法中被截获、报告,然后再检查 isStopped 变量。由于 isStopped 的值是 true, 因此 PoolThread.run() 方法退出,子线程终止。
转自:http://ifeve.com/blocking-queues/
阻塞队列与普通队列的区别在于,当队列是空的时,从队列中获取元素的操作将会被阻塞,或者当队列是满时,往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞,直到其他的线程往空的队列插入新的元素。同样,试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞,直到其他的线程使队列重新变得空闲起来,如从队列中移除一个或者多个元素,或者完全清空队列,下图展示了如何通过阻塞队列来合作:
线程1往阻塞队列中添加元素,而线程2从阻塞队列中移除元素
从5.0开始,JDK在java.util.concurrent包里提供了阻塞队列的官方实现。尽管JDK中已经包含了阻塞队列的官方实现,但是熟悉其背后的原理还是很有帮助的。
##阻塞队列的实现
阻塞队列的实现类似于带上限的Semaphore的实现。下面是阻塞队列的一个简单实现
1 | public class BlockingQueue { |
必须注意到,在enqueue和dequeue方法内部,只有队列的大小等于上限(limit)或者下限(0)时,才调用notifyAll方法。如果队列的大小既不等于上限,也不等于下限,任何线程调用enqueue或者dequeue方法时,都不会阻塞,都能够正常的往队列中添加或者移除元素。
转自:http://ifeve.com/semaphore/
Semaphore(信号量) 是一个线程同步结构,用于在线程间传递信号,以避免出现信号丢失(译者注:下文会具体介绍),或者像锁一样用于保护一个关键区域。自从5.0开始,jdk在java.util.concurrent包里提供了Semaphore 的官方实现,因此大家不需要自己去实现Semaphore。但是还是很有必要去熟悉如何使用Semaphore及其背后的原理
本文的涉及的主题如下:
下面是一个信号量的简单实现:
1 | public class Semaphore { |
Take方法发出一个被存放在Semaphore内部的信号,而Release方法则等待一个信号,当其接收到信号后,标记位signal被清空,然后该方法终止。
使用这个semaphore可以避免错失某些信号通知。用take方法来代替notify,release方法来代替wait。如果某线程在调用release等待之前调用take方法,那么调用release方法的线程仍然知道take方法已经被某个线程调用过了,因为该Semaphore内部保存了take方法发出的信号。而wait和notify方法就没有这样的功能。
当用semaphore来产生信号时,take和release这两个方法名看起来有点奇怪。这两个名字来源于后面把semaphore当做锁的例子,后面会详细介绍这个例子,在该例子中,take和release这两个名字会变得很合理。
下面的例子中,两个线程通过Semaphore发出的信号来通知对方
1 | Semaphore semaphore = new Semaphore(); |
上面提到的Semaphore的简单实现并没有计算通过调用take方法所产生信号的数量。可以把它改造成具有计数功能的Semaphore。下面是一个可计数的Semaphore的简单实现。
1 | public class CountingSemaphore { |
上面的CountingSemaphore并没有限制信号的数量。下面的代码将CountingSemaphore改造成一个信号数量有上限的BoundedSemaphore。
1 | public class BoundedSemaphore { |
在BoundedSemaphore中,当已经产生的信号数量达到了上限,take方法将阻塞新的信号产生请求,直到某个线程调用release方法后,被阻塞于take方法的线程才能传递自己的信号。
当信号量的数量上限是1时,Semaphore可以被当做锁来使用。通过take和release方法来保护关键区域。请看下面的例子:
1 | BoundedSemaphore semaphore = new BoundedSemaphore(1); |
在前面的例子中,Semaphore被用来在多个线程之间传递信号,这种情况下,take和release分别被不同的线程调用。但是在锁这个例子中,take和release方法将被同一线程调用,因为只允许一个线程来获取信号(允许进入关键区域的信号),其它调用take方法获取信号的线程将被阻塞,知道第一个调用take方法的线程调用release方法来释放信号。对release方法的调用永远不会被阻塞,这是因为任何一个线程都是先调用take方法,然后再调用release。
通过有上限的Semaphore可以限制进入某代码块的线程数量。设想一下,在上面的例子中,如果BoundedSemaphore 上限设为5将会发生什么?意味着允许5个线程同时访问关键区域,但是你必须保证,这个5个线程不会互相冲突。否则你的应用程序将不能正常运行。
必须注意,release方法应当在finally块中被执行。这样可以保在关键区域的代码抛出异常的情况下,信号也一定会被释放。