首页 > 编程语言 >垃圾回收算法

垃圾回收算法

时间:2024-09-28 13:00:58浏览次数:7  
标签:garbage 对象 回收 计数 算法 垃圾 root 引用

垃圾回收算法分为跟踪式垃圾回收(Tracing garbage collection)和引用计数(Reference counting)两大类。

跟踪式垃圾回收

跟踪式垃圾回收的基本原理是先认定一些对象为root,比如全局变量和栈变量。然后跟踪(trace)哪些对象是从这些root可达的,而剩下的从这些root不可达的对象就是garbage,可以被回收。

最简单的方法就是mark-and-sweep。首先stop the world,然后从root开始标记哪些对象是从root可达的(mark),最后把那些没有标记的对象回收(sweep)。缺点就是需要stop the world,即停止一切其他工作,只进行垃圾回收。

这篇文章说mark-and-sweep不能做到on-the-fly是因为“在不同阶段标记清扫法的标志位 0 和 1 有不同的含义,那么新增的对象无论标记为什么都有可能意外删除这个对象”:https://zhuanlan.zhihu.com/p/105495961。但是我觉得新增对象统一染成黑色,下次GC的时候所有对象都变成白色再从根开始染成黑色就行了,这样做的缺点就是新增对象要等到。

我觉得三色标记法(tri-color marking)跟mark-and-sweep基本上是一回事,里面的gray set有点像广度优先搜索的队列。新增对象需要到下次GC才能释放的问题仍然存在。

引用计数

使用引用计数进行垃圾回收时,为每个对象保存其被引用的次数,如果引用次数为0,就说明这个对象不可达,就可以被当成垃圾回收掉了。

但是引用计数法存在一些问题。引用计数法需要为每个对象额外存储引用计数,因此会增大空间开销,尤其是当对象比较小的时候。此外,引用计数法需要经常进行加减操作,而且在多线程程序中,引用计数的加减还需要是原子操作,这就引入了很高的额外时间开销。此外,如果当发现引用计数变成0之后当场将其释放掉,那么会导致程序的实时性变差,因为可能会一下子释放很多对象,不过这可以通过将释放的工作交给其他线程做来解决,但是会增加开销,并且减弱垃圾回收的及时性。

以上的问题都是开销方面的。引用计数的一个最致命的问题是,当存在循环引用时,引用计数法将无法将这些循环引用的对象释放,因为它们的引用计数都不是0。一种缓解这种情况的方法是当需要进行双向引用时(例如双向链表),将其中一个引用设置成弱引用,即只引用它,而不增加其引用计数,从而避免了一部分循环引用。但是这种方法不能完全解决循环引用的问题。还有一种方法是周期性进行跟踪式垃圾回收,将不可达的环删掉,如果环的内存占用低,可以减少进行跟踪式垃圾回收的频率。

关于如何回收环,有很多现有的研究。比较基础的是这个:

Lins, Rafael D. "Cyclic reference counting with lazy mark-scan." Information Processing Letters 44.4 (1992): 215-220.

基本原理是,一个garbage cycle只有在当一个对象的引用计数被减到非0值时才会产生,因为如果引用计数被加了,那肯定就不是garbage,如果引用计数被减到0了,就是非环的garbage。因此,当一个对象的引用计数被减到非0值时,将其作为candidate root of a garbage cycle,存入root buffer里。在合适的时机,Garbage collector会从root buffer里拿出一个candidate,从它开始进行深度优先搜索,搜到从这个root可达的所有对象,然后对这些对象的每条出边,都将其指向的对象的引用计数减一,这样如果这些对象的引用计数都减为0了,就说明没有其他外部对象引用了这些对象,这些对象就构成了一个garbage cycle,可以回收掉。如果有某个对象的引用计数不为0,就说明有某个外部对象引用了这个对象,因此就不能进行回收,要把所有引用计数复原。但是在这种情况下,这个算法的复杂度是$O(n^2)$的(图片来源是[Bacon and Rajan 2001]的Fig. 1):

最快的stop the world的好像是这个:

Bacon, David F., and Vadakkedathu T. Rajan. "Concurrent cycle collection in reference counted systems." European Conference on Object-Oriented Programming. Springer, Berlin, Heidelberg, 2001.

跟[Lins 1992]不同,[Bacon and Rajan 2001]的最坏时间复杂度是$O(N+E)$的,其中$N$是对象数,$E$是引用数。这个算法与[Lins 1992]的主要区别是,[Lins 1992]是将candidate一个一个从root buffer里拿出来处理,如果发现不能回收,那么就恢复引用计数,然后拿出下一个candidate继续处理,而[Bacon and Rajan 2001]是一次性将整个root buffer里的所有candidate一起处理,从而避免了重复减某一条边指向的对象的引用计数,从而把复杂度控制在$O(N+E)$。[Bacon and Rajan 2001]将垃圾回收分为了三个阶段:MarkRootsScanRootsCollectRoots。灰色代表可能是环的成员,黑色代表可能正在使用所以不能被释放,白色表示是garbage cycle的成员。

MarkRoots:把所有root buffer里的candidate拿出来,做深度优先搜索MarkGrayMarkGray跟[Lins 1992]一致),把所有可达的对象都标记成灰色,并且将这些对象的出边指向的对象的引用计数都减一。

ScanRoots:对每个Markgray访问到的节点,如果它是灰色的而且引用计数不为0,那么这个节点不是garbage,需要将它以及所有它可达的节点都染成黑色,并且将这些重新被染成黑色的节点的所有出边指向的节点的引用计数都加一。如果它是灰色且引用计数为0,那么就把这个节点染成白色,注意这个时候不代表这个节点就是garbage了,因为后续可能有父节点被染成黑色从而将这个节点重新染成黑色,但是由于一个节点的颜色最多改变常数次,所以不影响复杂度。

CollectRoots:经过ScanRoots之后,所有灰色节点要么被染成黑色,说明其不能被释放,要么被染成白色,说明所有引用它的节点也都是白色的,这些白色的节点都是garbage,可以被释放。

可以看出,其实这种方法也算是一种启发式的跟踪式垃圾回收。

最快的on-the-fly的好像是这个:

Paz, Harel, et al. "An efficient on-the-fly cycle collection." ACM Transactions on Programming Languages and Systems (TOPLAS) 29.4 (2007): 20-es.

这篇论文还没看。

参考文献

https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

https://en.wikipedia.org/wiki/Tracing_garbage_collection

https://en.wikipedia.org/wiki/Reference_counting

标签:garbage,对象,回收,计数,算法,垃圾,root,引用
From: https://www.cnblogs.com/searchstar/p/18437338

相关文章

  • 【风光不确定】基于多时间尺度滚动优化算法的主动配电网研究【IEEE33节点】(Matlab代码
    目录......
  • 8592 KMP算法
    首先,我们需要理解KMP算法的基本思想。KMP算法是一种改进的字符串匹配算法,它的主要思想是利用已经部分匹配的这个有效信息,使得后续的匹配中,尽量减少字符串的回溯,提高匹配效率。KMP算法的关键在于通过一个next数组,保存模式串中前后缀的最长的共有元素的长度。当模式串中的字符......
  • AI大模型算法工程师就业宝典—— 高薪入职攻略与转行秘籍!
    从ChatGPT到新近的GPT-4,GPT模型的发展表明,AI正在向着“类⼈化”⽅向迅速发展。GPT-4具备深度阅读和识图能⼒,能够出⾊地通过专业考试并完成复杂指令,向⼈类引以为傲的“创造⼒”发起挑战。现有的就业结构即将发⽣重⼤变化,社会⽣产⼒的快速提升将催⽣新的⾏业和岗位机会。如......
  • 代码随想录算法训练营第二天| 209.长度最小的子数组、59.螺旋矩阵II 、区间和、开发
    209.长度最小的子数组此题注重理解,同时我将res一开始初始化为sums的长度加一(因为不可能为此长度)INT32_MAX是一个常量,代表32位有符号整数的最大值classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){inti=0,j=0;//i为起始位置,j为......
  • 【算法】二叉树中的 DFS
     【ps】本篇有6 道 leetcode OJ。 目录一、算法简介二、相关例题1)计算布尔二叉树的值.1-题目解析.2-代码编写2)求根节点到叶节点数字之和.1-题目解析.2-代码编写3)二叉树剪枝.1-题目解析.2-代码编写4)验证二叉搜索树.1-题目解析.2-代码编写5)二叉......
  • 【开题报告】基于Springboot+vue基于推荐算法的高校就业管理系统(程序+源码+论文) 计算
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着高等教育的普及与就业市场的日益竞争,高校毕业生面临的就业压力日益增大。传统的高校就业管理方式往往依赖于线下招聘会、简历投递等低效手段,难以......
  • 基于冲突动态监测算法的健身房预约管理系统
    系统展示用户前台界面管理员后台界面系统背景  随着健身热潮的兴起,健身房管理面临着日益增长的会员需求与资源分配的挑战。传统的人工预约方式不仅效率低下,且容易出现时间冲突和资源浪费的情况。为了解决这一问题,基于冲突动态监测算法的健身房预约管理系统......
  • 开普勒优化算法:一种开普勒行星运动定律的元启发式算法
    目录1.摘要2.算法原理3.结果展示4.参考文献5.代码获取1.摘要这项研究介绍了开普勒优化算法(KOA),这是一种基于物理的新元启发式算法,灵感来源于开普勒行星运动定律。KOA通过模拟行星的位置和速度来寻找优化问题的解决方案,其中每个行星代表一个候选解,这些候选解会根据......
  • 算法题:用队列实现一个链表
    下面是添加了注释的ListNode类和LinkedListQueue类,以帮助理解每个部分的功能和目的://定义链表节点类,用于存储队列中的元素classListNode{intval;//存储节点的值ListNodenext;//指向下一个节点的指针//构造函数,用于创建新的节点ListNod......
  • 嵌入式学习--数据结构+算法
    嵌入式学习--数据结构+算法数据结构1.1数据1.2逻辑结构1.3存储结构1)顺序存储结构2)链式存储结构1.4操作(数据的运算)算法2.1算法与程序2.2算法与数据结构2.3算法的特性2.4如何评价一个算法的好坏?2.5时间复杂度2.6空间复杂度数据结构数据的逻辑结构、存储结构、......