当前位置: 首页 > 内存管理 > 正文

内存管理器(二十一)标记-清扫回收算法

内存回收一共有四种基本的算法及若干高级算法:

标记-清扫,标记-复制,标记-整理,引用计数。

任何自动内存管理都需要面临三个基本任务:

1.为新对象分配空间。

2.确定存活时间。

3.回收死亡对象所占空间。

讨论前提:

多线程条件下,只有一个回收线程。

垃圾回收前提:

“万物静止式”回收,所有的资源分配器都会静止,回收线程开始运作,从资源分配器的角度来看回收过程是原子的。

回收方式:

通过“万物静止”获取“堆”的一个快照,然后回收资源。

标记-清扫算法:

这个算法分为两个阶段:

第一阶段:

追踪阶段:回收器从根集合开始遍历对象图,标记每一个遇到的对象。

第二阶段:

清扫阶段:回收器检查堆中的每一个对象,将所有未标记的对象作为垃圾回收。

这个算法是一种“间接”的回收方式。

在这里分配器和回收器普遍具的几个行为:

分配器:

@创建,分配资源方法。

@读,读取已经分配资源的方法。

@写,修改已经分配资源内容。

这个算法思想还是比较简单的:先来一个伪代码:

以上是最简单的标记-清扫算法

接着我们它来看看三色抽象。

三色抽象:

Dijkstra 提出了三色抽象,真是个神人,哪哪都有他。

三色抽象将对象划分为三种颜色,白色,灰色,黑色。

颜色意义:

白色:可能死亡对象,所有未被扫描的对象都是白色。

灰色:初次扫描时的状态,此时他们为中间状态。

黑色:处理完成的节点,(确定存活)为黑色。

wKiom1cOJa3hZTMZAAE0jG6pWTc560.jpg-wm_1-wmp_4-s_172615938

从根开始遍历进行标记,初步采用的是深度有先法。

初次遍历的节点都会被染成灰色,进栈,然后出栈被标记查询有无子节点或者是否叶子节点做出相应的处理,全部处理完成的存活节点为黑色,而所有的节点最后只会变成白色或黑色。

最后遍历结构释放所有非黑色的节点。

对于此算法的优化

1.使用位图标记

@标记过程只需读取存活对象的指针不会修改任何读对象

@对于不包含引用的对象,同样不会读取别的东西

位图的优势,许多证据表明,很多内存都是连续的簇,使用位图可以成块的回收资源,而遍历的方式极有可能产生页换出,高速缓存被刷新。这是不可饶恕的失误。

2.使用懒惰清扫

@不主动清扫,局部性原理,延时清理,很简单。

3.优化高速缓存不命中的问题

首先,我们清楚两个问题,高速缓存是按照FIFO原理活动的,而标记过程是按照LIFO过程遍历的,这就导致一个问题,高速缓存不命中。

会是欧

例如:

高速缓存可以存储两个单位:

高速存储单位              预读单位        下一个读取单位

第一次      1   2                              无                      4

第二次     2    4                            2  5                       5

我们发现2其实是在缓存中的,并且我们预读了单位2 5 ,而将4 换出了高速缓存,如果不这样做,则2被换出,4 5进高速缓存,下一次回到2节点,再将2 换入,非常的不方便。

标记-清扫算法小结

在这个算法下:

@不会引入额外的开销。

@吞吐量非常高,最主要的消耗在于追踪指针。

@整体位图优于局部位图。

@安全性好,不需要使用移动操作。

本文固定链接: http://zmrlinux.com/2016/08/05/%e5%86%85%e5%ad%98%e7%ae%a1%e7%90%86%e5%99%a8%ef%bc%88%e4%ba%8c%e5%8d%81%e4%b8%80%ef%bc%89%e6%a0%87%e8%ae%b0-%e6%b8%85%e6%89%ab%e5%9b%9e%e6%94%b6%e7%ae%97%e6%b3%95/ | Kernel & Me

该日志由 root 于2016年08月05日发表在 内存管理 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 内存管理器(二十一)标记-清扫回收算法 | Kernel & Me