一、标记-清除算法:
1、标记清除算法的概念:
标记-清除算法是现代垃圾回收算法的思想基础。标记-清除算法将垃圾回收分为两个阶段:标记阶段和清除阶段。一种可行的实现是,在标记阶段,首先通过根节点,标记所有从根节点开始的可达对象。因此,未被标记的对象就是未被引用的垃圾对象;然后,在清除阶段,清除所有未被标记的对象。
2、标记-清除算法详解:
它的做法是当堆中的有效内存空间(available memory)被耗尽的时候,就会停止整个程序(也被成为stop the world),然后进行两项工作,第一项则是标记,第二项则是清除。
- 标记:标记的过程其实就是,遍历所有的GC Roots,然后将所有GC Roots可达的对象标记为存活的对象。
- 清除:清除的过程将遍历堆中所有的对象,将没有标记的对象全部清除掉。
也就是说,就是当程序运行期间,若可以使用的内存被耗尽的时候,GC线程就会被触发并将程序暂停,随后将依旧存活的对象标记一遍,最终再将堆中所有没被标记的对象全部清除掉,接下来便让程序恢复运行。
来看下面这张图:
上图代表的是程序运行期间所有对象的状态,它们的标志位全部是0(也就是未标记,以下默认0就是未标记,1为已标记),假设这会儿有效内存空间耗尽了,JVM将会停止应用程序的运行并开启GC线程,然后开始进行标记工作,按照根搜索算法,标记完以后,对象的状态如下图:
上图中可以看到,按照根搜索算法,所有从root对象可达的对象就被标记为了存活的对象,此时已经完成了第一阶段标记。接下来,就要执行第二阶段清除了,那么清除完以后,剩下的对象以及对象的状态如下图所示:
上图可以看到,没有被标记的对象将会回收清除掉,而被标记的对象将会留下,并且会将标记位重新归0。接下来就不用说了,唤醒停止的程序线程,让程序继续运行即可。
疑问:为什么非要停止程序的运行呢?
答:
这个其实也不难理解,假设我们的程序与GC线程是一起运行的,各位试想这样一种场景。
假设我们刚标记完图中最右边的那个对象,暂且记为A,结果此时在程序当中又new了一个新对象B,且A对象可以到达B对象。但是由于此时A对象已经标记结束,B对象此时的标记位依然是0,因为它错过了标记阶段。因此当接下来轮到清除阶段的时候,新对象B将会被苦逼的清除掉。如此一来,不难想象结果,GC线程将会导致程序无法正常工作。
上面的结果当然令人无法接受,我们刚new了一个对象,结果经过一次GC,忽然变成null了,这还怎么玩?
3、标记-清除算法的缺点:
(1)首先,它的缺点就是效率比较低(递归与全堆对象遍历),导致stop the world的时间比较长,尤其对于交互式的应用程序来说简直是无法接受。试想一下,如果你玩一个网站,这个网站一个小时就挂五分钟,你还玩吗?
(2)第二点主要的缺点,则是这种方式清理出来的空闲内存是不连续的,这点不难理解,我们的死亡对象都是随即的出现在内存的各个角落的,现在把它们清除之后,内存的布局自然会乱七八糟。而为了应付这一点,JVM就不得不维持一个内存的空闲列表,这又是一种开销。而且在分配数组对象的时候,寻找连续的内存空间会不太好找。
二、复制算法:(新生代的GC算法)
复制算法的概念:
将原有的内存空间分为两块,每次只使用其中一块,在垃圾回收时,将正在使用的内存中的存活对象复制到未使用的内存块中,之后,清除正在使用的内存块中的所有对象,交换两个内存的角色,完成垃圾回收。
- 与标记-清除算法相比,复制算法是一种相对高效的回收方法
- 不适用于存活对象较多的场合,如老年代(复制算法适合做新生代的GC)
- 复制算法的最大的问题是:空间的浪费
复制算法使得每次都只对整个半区进行内存回收,内存分配时也就不用考虑内存碎片等复杂情况,只要移动堆顶指针,按顺序分配内存即可,实现简单,运行高效。只是这种算法的代价是将内存缩小为原来的一半,这个太要命了。
所以从以上描述不难看出,复制算法要想使用,最起码对象的存活率要非常低才行,而且最重要的是,我们必须要克服50%内存的浪费。
现在的商业虚拟机都采用这种收集算法来回收新生代,新生代中的对象98%都是“朝生夕死”的,所以并不需要按照1:1的比例来划分内存空间,而是将内存分为一块比较大的Eden空间和两块较小的Survivor空间,每次使用Eden和其中一块Survivor。当回收时,将Eden和Survivor中还存活着的对象一次性地复制到另外一块Survivor空间上,最后清理掉Eden和刚才用过的Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8:1,也就是说,每次新生代中可用内存空间为整个新生代容量的90%(80%+10%),只有10%的空间会被浪费。
当然,98%的对象可回收只是一般场景下的数据,我们没有办法保证每次回收都只有不多于10%的对象存活,当Survivor空间不够用时,需要依赖于老年代进行分配担保,所以大对象直接进入老年代。整个过程如下图所示:
上图中,绿色箭头的位置代表的是大对象,大对象直接进入老年代。
根据上面的复制算法,现在我们来看下面的这个gc日志的数字,就应该能看得懂了吧:
上方GC日志中,新生代的可用空间是13824K(eden区的12288K+from space的1536K)。而根据内存的地址计算得知,新生代的总空间为15M,而这个15M的空间是 = 13824K +to space 的 1536K。
三、标记-整理算法:(老年代的GC算法)
引入:
如果在对象存活率较高时就要进行较多的复制操作,效率将会变低。更关键的是,如果不想浪费50%的空间,就需要有额外的空间进行分配担保,以应对被使用的内存中所有对象都100%存活的极端情况,所以在老年代一般不能直接选中这种算法。
概念:
标记-压缩算法适合用于存活对象较多的场合,如老年代。它在标记-清除算法的基础上做了一些优化。和标记-清除算法一样,标记-压缩算法也首先需要从根节点开始,对所有可达对象做一次标记;但之后,它并不简单的清理未标记的对象,而是将所有的存活对象压缩到内存的一端;之后,清理边界外所有的空间。
- 标记:它的第一个阶段与标记/清除算法是一模一样的,均是遍历GC Roots,然后将存活的对象标记。
- 整理:移动所有存活的对象,且按照内存地址次序依次排列,然后将末端内存地址以后的内存全部回收。因此,第二阶段才称为整理阶段。
上图中可以看到,标记的存活对象将会被整理,按照内存地址依次排列,而未被标记的内存会被清理掉。如此一来,当我们需要给新对象分配内存时,JVM只需要持有一个内存的起始地址即可,这比维护一个空闲列表显然少了许多开销。
标记/整理算法不仅可以弥补标记/清除算法当中,内存区域分散的缺点,也消除了复制算法当中,内存减半的高额代价。
- 但是,标记/整理算法唯一的缺点就是效率也不高。
不仅要标记所有存活对象,还要整理所有存活对象的引用地址。从效率上来说,标记/整理算法要低于复制算法。
标记-清除算法、复制算法、标记整理算法的总结:
三个算法都基于根搜索算法去判断一个对象是否应该被回收,而支撑根搜索算法可以正常工作的理论依据,就是语法中变量作用域的相关内容。因此,要想防止内存泄露,最根本的办法就是掌握好变量作用域,而不应该使用C/C++式内存管理方式。
在GC线程开启时,或者说GC过程开始时,它们都要暂停应用程序(stop the world)。
它们的区别如下:(>表示前者要优于后者,=表示两者效果一样)
(1)效率:复制算法>标记/整理算法>标记/清除算法(此处的效率只是简单的对比时间复杂度,实际情况不一定如此)。
(2)内存整齐度:复制算法=标记/整理算法>标记/清除算法。
(3)内存利用率:标记/整理算法=标记/清除算法>复制算法。
注1:可以看到标记/清除算法是比较落后的算法了,但是后两种算法却是在此基础上建立的。
注2:时间与空间不可兼得。
四、分代收集算法:(新生代的GC+老年代的GC)
当前商业虚拟机的GC都是采用的“分代收集算法”,这并不是什么新的思想,只是根据对象的存活周期的不同将内存划分为几块儿。一般是把Java堆分为新生代和老年代:短命对象归为新生代,长命对象归为老年代。
- 少量对象存活,适合复制算法:在新生代中,每次GC时都发现有大批对象死去,只有少量存活,那就选用复制算法,只需要付出少量存活对象的复制成本就可以完成GC。
- 大量对象存活,适合用标记-清理/标记-整理:在老年代中,因为对象存活率高、没有额外空间对他进行分配担保,就必须使用“标记-清理”/“标记-整理”算法进行GC。
注:老年代的对象中,有一小部分是因为在新生代回收时,老年代做担保,进来的对象;绝大部分对象是因为很多次GC都没有被回收掉而进入老年代。
九、Stop-The-World:
1、Stop-The-World概念:
Java中一种全局暂停的现象。
全局停顿,所有Java代码停止,native代码可以执行,但不能和JVM交互
多半情况下是由于GC引起。
少数情况下由其他情况下引起,如:Dump线程、死锁检查、堆Dump。
2、GC时为什么会有全局停顿?
(1)避免无法彻底清理干净
打个比方:类比在聚会,突然GC要过来打扫房间,聚会时很乱,又有新的垃圾产生,房间永远打扫不干净,只有让大家停止活动了,才能将房间打扫干净。
况且,如果没有全局停顿,会给GC线程造成很大的负担,GC算法的难度也会增加,GC很难去判断哪些是垃圾。
(2)GC的工作必须在一个能确保一致性的快照中进行。
这里的一致性的意思是:在整个分析期间整个执行系统看起来就像被冻结在某个时间点上,不可以出现分析过程中对象引用关系还在不断变化的情况,该点不满足的话分析结果的准确性无法得到保证。
这点是导致GC进行时必须停顿所有Java执行线程的其中一个重要原因。
3、Stop-The-World的危害:
长时间服务停止,没有响应(将用户正常工作的线程全部暂停掉)
遇到HA系统,可能引起主备切换,严重危害生产环境。
备注:HA:High Available, 高可用性集群。
比如上面的这主机和备机:现在是主机在工作,此时如果主机正在GC造成长时间停顿,那么备机就会监测到主机没有工作,于是备机开始工作了;但是主机不工作只是暂时的,当GC结束之后,主机又开始工作了,那么这样的话,主机和备机就同时工作了。主机和备机同时工作其实是非常危险的,很有可能会导致应用程序不一致、不能提供正常的服务等,进而影响生产环境。
代码举例:
(1)打印日志的代码:(每隔100ms打印一条)
public static class PrintThread extends Thread{ public static final long starttime=System.currentTimeMillis(); @Override public void run(){ try{ while(true){ long t=System.currentTimeMillis()-starttime; System.out.println("time:"+t); Thread.sleep(100); } }catch(Exception e){ } }}
上方代码中,是负责打印日志的代码,每隔100ms打印一条,并计算打印的时间。
(2)工作线程的代码:(工作线程,专门用来消耗内存)
public static class MyThread extends Thread{ HashMapmap=new HashMap (); @Override public void run(){ try{ while(true){ if(map.size()*512/1024/1024>=450){ //如果map消耗的内存消耗大于450时,那就清理内存 System.out.println("=====准备清理=====:"+map.size()); map.clear(); } for(int i=0;i<1024;i++){ map.put(System.nanoTime(), new byte[512]); } Thread.sleep(1); } }catch(Exception e){ e.printStackTrace(); } }}
然后,我们设置gc的参数为:
-Xmx512M -Xms512M -XX:+UseSerialGC -Xloggc:gc.log -XX:+PrintGCDetails -Xmn1m -XX:PretenureSizeThreshold=50 -XX:MaxTenuringThreshold=1
打印日志如下:
上图中,红色字体代表的正在GC。按道理来说,应该是每隔100ms会打印输出一条日志,但是当执行GC的时候,会出现全局停顿的情况,导致没有按时输出。
下篇文章中,我们将对各种垃圾收集器进行介绍。