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

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

我们今天来看看第二种垃圾回收方法:

标记-整理回收算法

双指针整理算法

使用两个指针,一个从前向后遍历,我们称之为free指针,接着使用另一个指针,我们称之为scan指针,他从后像前遍历,当free 遇到空闲且大小合适的内存块时,将scan 所指向的内存拷贝到free 中,当free  和 sacn 指针相遇或者产生交互,我们就完成了这一次的标记-整理回收工作。

至于这个两个指针的交互地点,是回收器预预先计算出该区域整理完成后存活对象的“高水位”标记。

伪代码:

此算法吞吐量较低,因为大多数对象总是成簇诞生,成簇死亡的。所以这个算法效果良好。

lisp 2 整理算法

从名字就可以感受到这是一种历史悠久的算法了,思想就是标记-整理算法。不过他更加的原始,更加的简单,因为这个算法诞生的时候还没有高速缓存,分页管理,所以这个算法在硬件上的优化并不是那么近乎人意的。下来直接上伪代码,至于模拟代码,我会在基础四个算法学习完成后统一进行编写。

这个算法总共需要遍历三次堆空间。

@在标记阶段结束后,回收器会计算出每个存活对象的最终地址,并且保存。

@回收器更新引用

@最后一次,移动对象

引线整理算法:

这个思想更简单,将所有对象和引用的共享内存以类似“双向链表”的形式串连起来。进行三次遍历。

@建立后向引用

@建立前向引用

@复制对象到新地址

最后一种标记-整理算法

单次遍历算法

这个算法有很多衍生的版本,我们来讨论Abuaiadh [2004] 的哪个版本,这是一个基于并行式,万物静止的算法。

这个算法虽然只遍历一次,但是却产生较大的空间占用量。

首先,他需要算个向量。

#标记向量

#偏移向量

#整理之后的向量

这个算法通过一次遍历,同时构建偏移向量,然后选定新的位置,并且复制数据到新的位置。

ff

小结:

我们来说说各算法的缺陷吧

双指针算法:只能处理大小统一内存

引线算法:破坏指针,不可并发

 

 

本文固定链接: http://zmrlinux.com/2016/08/06/%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%ba%8c%ef%bc%89-%e6%a0%87%e8%ae%b0-%e6%95%b4%e7%90%86%e5%9b%9e%e6%94%b6%e7%ae%97%e6%b3%95/ | Kernel & Me

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