当前位置：首页 > news >正文

垃圾回收算法

news 2025/10/21 17:15:33

垃圾回收算法

🔴 垃圾回收算法概述 #JVM/垃圾回收

🔴 垃圾回收算法是JVM自动内存管理的核心机制，通过识别和回收不再使用的对象来释放内存空间。主要包括标记-清除、标记-复制、标记-整理三种基本算法，以及基于分代收集理论的优化策略。

🟠 GC Roots 可达性分析基础

🟠 GC Roots是垃圾回收的起点，通过可达性分析算法判断对象是否存活：

🟢 1. GC Roots 类型

🟢 虚拟机栈中的引用：局部变量表中的对象引用
🟢 方法区中的静态变量：static修饰的类变量
🟢 方法区中的常量：final修饰的常量引用
🟢 JNI引用：Java Native Interface中的对象引用
🟢 同步锁持有的对象：synchronized锁定的对象
🟢 系统类加载器：ClassLoader加载的类对象

🟡 2. 可达性分析过程

🟡 标记阶段：从GC Roots开始遍历，标记所有可达对象
🟡 清除阶段：回收未被标记的对象
🟡 分析特点：需要暂停所有应用线程（Stop The World）

🔴 三种基本垃圾回收算法

🔴 1. 标记-清除算法 (Mark-Sweep)

🔴 原理: 先标记所有需要回收的对象，然后统一回收被标记的对象

🔴 具体过程:

🔴 标记阶段：通过可达性分析，标记根可达的对象
🔴 清除阶段：递归遍历全堆，清除掉被标记需要回收的对象

🟠 优点:

🟠 实现简单，逻辑清晰
🟠 不需要移动对象，适合老年代

🟠 缺点:

🟠 内存碎片问题：导致大量不连续的内存碎片
🟠 分配效率低：需要分配大内存对象时，无法找到足够的连续内存
🟠 GC频率增加：可能触发另一次的垃圾收集动作

🟡 性能分析:

🟡 标记耗时：需要对每个根元素的整个引用链表遍历
🟡 清除耗时：递归遍历全堆时比较耗时

🟡 动态分区策略详解

🟡 动态分区策略是标记-清除算法中管理空闲内存块的重要机制：

🟢 1. 首次适应算法 (First Fit)

🟢 原理: 从内存起始位置开始搜索，分配第一个足够大的空闲块

🟢 具体过程:

🟢 步骤1：系统维护一个空闲块链表，链表中的每个节点代表一个空闲的内存块，按内存地址从低到高排列
🟢 步骤2：当需要分配内存时，从链表的第一个节点开始，逐个检查每个空闲块的大小
🟢 步骤3：找到第一个大小大于等于请求大小的空闲块时，立即停止搜索
🟢 步骤4：如果找到的空闲块大小正好等于请求大小，直接分配整个块
🟢 步骤5：如果找到的空闲块大小大于请求大小，将块分割成两部分：一部分分配给请求，另一部分作为新的空闲块
🟢 步骤6：更新空闲链表，删除已分配的空闲块节点，如果有分割则插入新的空闲块节点

🟡 优点:

🟡 实现简单：只需从空闲链表头开始顺序查找，逻辑清晰。
🟡 分配速度快：平均查找长度较短（尤其在空闲块多时）。
🟡 对小对象分配友好：小对象容易在前部被快速满足，适合频繁的小块分配场景。

🟡 缺点:

🟡 容易产生外部碎片：前部空闲块被频繁分割，留下许多无法利用的小碎片。
🟡 大块分配可能变慢：需要扫描多个小空闲块才能找到足够大的区域。
🟡 内存利用率低：碎片导致总体可用空间减少，需要定期进行紧缩或合并操作。

🟢 2. 最佳适应算法 (Best Fit)

🟢 原理: 搜索整个空闲链表，选择最小的满足要求的空闲块

🟢 具体过程:

🟢 步骤1：系统维护一个空闲块链表，链表中的每个节点代表一个空闲的内存块
🟢 步骤2：当需要分配内存时，遍历整个空闲块链表，检查每个空闲块的大小
🟢 步骤3：记录所有大小大于等于请求大小的空闲块，这些块都是候选块
🟢 步骤4：从所有候选块中选择大小最小的那个块进行分配
🟢 步骤5：如果选中的块大小正好等于请求大小，直接分配整个块
🟢 步骤6：如果选中的块大小大于请求大小，将块分割成两部分：一部分分配给请求，另一部分作为新的空闲块
🟢 步骤7：更新空闲链表，删除已分配的空闲块节点，如果有分割则插入新的空闲块节点

🟡 优点:

🟡 内存利用率高：选择最小满足要求的块，减少内存浪费，提高空间利用率。
🟡 适合大小差异大的对象：能更好地利用各种大小的空闲块，避免大块被小请求浪费。
🟡 碎片管理相对较好：通过选择最合适的块，减少不必要的分割操作。

🟡 缺点:

🟡 搜索时间长：需要遍历整个空闲链表，时间复杂度为O(n)，分配效率较低。
🟡 容易产生内部碎片：选择最小块可能导致剩余部分过小，形成无法利用的小碎片。
🟡 链表维护开销大：频繁的链表节点插入和删除操作，增加系统开销。

🟢 3. 最差适应算法 (Worst Fit)

🟢 原理: 搜索整个空闲链表，选择最大的空闲块进行分配

🟢 具体过程:

🟢 步骤1：系统维护一个空闲块链表，链表中的每个节点代表一个空闲的内存块
🟢 步骤2：当需要分配内存时，遍历整个空闲块链表，检查每个空闲块的大小
🟢 步骤3：记录所有大小大于等于请求大小的空闲块，这些块都是候选块
🟢 步骤4：从所有候选块中选择大小最大的那个块进行分配
🟢 步骤5：如果选中的块大小正好等于请求大小，直接分配整个块
🟢 步骤6：如果选中的块大小大于请求大小，将块分割成两部分：一部分分配给请求，另一部分作为新的空闲块
🟢 步骤7：更新空闲链表，删除已分配的空闲块节点，如果有分割则插入新的空闲块节点

🟡 优点:

🟡 剩余块相对较大：选择最大块分配后，剩余部分通常较大，便于后续大对象分配。
🟡 减少小碎片产生：避免大块被频繁分割，减少无法利用的小碎片。
🟡 适合大对象分配：大块优先分配策略，有利于大对象的连续内存需求。

🟡 缺点:

🟡 搜索时间长：需要遍历整个空闲链表，时间复杂度为O(n)，分配效率较低。
🟡 大块快速消耗：大空闲块容易被快速消耗殆尽，可能导致后续大对象无法分配。
🟡 内存利用率不高：选择最大块可能造成内存浪费，特别是当请求大小远小于块大小时。

🟢 4. 宁静适应算法 (Next Fit)

🟢 原理: 从上次分配的位置开始搜索，找到第一个满足要求的空闲块

🟢 具体过程:

🟢 步骤1：系统维护一个空闲块链表和一个游标指针，游标指针记录上次分配操作在链表中的位置
🟢 步骤2：当需要分配内存时，从游标指针指向的位置开始，逐个检查每个空闲块的大小
🟢 步骤3：如果找到大小大于等于请求大小的空闲块，立即停止搜索并分配该块
🟢 步骤4：如果遍历到链表末尾还没找到合适的块，则从头节点重新开始搜索
🟢 步骤5：如果找到的空闲块大小正好等于请求大小，直接分配整个块
🟢 步骤6：如果找到的空闲块大小大于请求大小，将块分割成两部分：一部分分配给请求，另一部分作为新的空闲块
🟢 步骤7：更新空闲链表，删除已分配的空闲块节点，如果有分割则插入新的空闲块节点
🟢 步骤8：更新游标指针，将其移动到新分配块在链表中的位置，为下次分配做准备

🟡 优点:

🟡 搜索效率适中：介于首次适应和最佳适应之间，平均查找长度较短。
🟡 内存分配相对均匀：通过游标指针的移动，避免总是在链表前部分配。
🟡 实现简单且性能稳定：逻辑清晰，不需要复杂的排序或比较操作。

🟡 缺点:

🟡 可能错过更合适的块：由于从固定位置开始搜索，可能错过前面更合适的空闲块。
🟡 内存利用率不如最佳适应：无法保证选择最优的空闲块，存在一定的内存浪费。
🟡 需要维护额外状态：需要维护游标指针，增加了算法的复杂度和内存开销。

🟡 算法选择建议

🟡 根据应用场景选择:

🟡 小对象频繁分配：选择首次适应算法
🟡 内存利用率要求高：选择最佳适应算法
🟡 大对象较多：选择最差适应算法
🟡 平衡性能和利用率：选择宁静适应算法

🔴 2. 标记-复制算法 (Mark-Copy)

🔴 原理: 将可用内存分为两块，每次只使用其中一块，垃圾回收时将存活对象复制到另一块

🔴 具体过程:

🔴 内存划分：将内存分为两个相等的区域
🔴 对象分配：只在其中一个区域分配对象
🔴 垃圾回收：将存活对象复制到另一个区域
🔴 区域交换：清空原区域，交换两个区域的角色

🟠 优点:

🟠 无内存碎片：复制后内存连续，无碎片问题
🟠 分配效率高：顺序分配，速度很快
🟠 适合年轻代：大部分对象朝生夕死

🟠 缺点:

🟠 内存利用率低：只能使用一半的内存空间
🟠 复制成本高：存活对象较多时复制开销大
🟠 不适合老年代：老年代对象存活率高

🟡 应用场景:

🟡 年轻代回收：Eden区和Survivor区之间的复制
🟡 小对象回收：适合对象生命周期短的情况

🔴 3. 标记-整理算法 (Mark-Compact)

🔴 原理: 标记存活对象后，将所有存活对象向一端移动，然后清理边界外的内存

🔴 具体过程:

🔴 标记阶段：标记所有需要回收的对象
🔴 整理阶段：将存活对象向内存一端移动
🔴 清理阶段：清理边界外的内存空间

🟠 优点:

🟠 无内存碎片：整理后内存连续
🟠 内存利用率高：可以使用全部内存空间
🟠 适合老年代：老年代对象移动成本相对较低

🟠 缺点:

🟠 移动成本高：需要移动大量对象
🟠 更新引用：需要更新所有指向移动对象的引用
🟠 实现复杂：算法实现相对复杂

🟡 整理策略:

🟡 随机整理：随机选择整理方向
🟡 线性整理：按线性顺序整理
🟡 滑动整理：滑动窗口式整理

🟡 整理策略详解

🟡 整理策略是标记-整理算法中决定如何移动存活对象的关键机制：

🟢 1. 随机整理 (Random Compaction)

🟢 原理: 将存活对象移动到堆中伪随机或均匀分布的位置，保证每个对象自身连续，同时打乱对象顺序，降低热点压力并控制碎片。

🟢 核心特征:

🟢 移动方向：可随机（低→高或高→低）
🟢 对象顺序：被打乱（随机化）
🟢 新地址分配：由随机/均匀分布决定
🟢 最终布局：对象连续，但顺序无规律

🟡 适用场景：小规模整理，对对象顺序无严格要求；老年代碎片较多时可缓解热点问题

🟢 2. 线性整理 (Linear Compaction)

🟢 原理: 按线性顺序将存活对象全部移动到堆的一端，堆另一端形成连续空闲空间。

🟢 核心特征:

🟢 移动方向：固定（低→高）
🟢 对象顺序：与原堆顺序一致
🟢 新地址分配：线性递增
🟢 最终布局：连续、有序

🟡 适用场景：大规模整理，需要保证对象顺序或分配连续空间

🟢 3. 滑动整理 (Sliding Compaction)

🟢 原理: 使用滑动窗口逐步将存活对象向堆的一端移动，空闲空间被集中在另一端。

🟢 核心特征:

🟢 移动方向：固定（滑动式）
🟢 对象顺序：与原堆顺序一致
🟢 新地址分配：通过滑动计算
🟢 最终布局：连续、有序

🟡 适用场景：中等规模整理，保持局部性和顺序

🟡 整理策略对比总结

特征	线性整理	滑动整理	随机整理
移动方向	固定（低→高）	固定（滑动式）	可随机（低→高或高→低）
对象顺序	与原堆顺序一致	与原堆顺序一致	顺序被打乱
新地址分配	线性递增	滑动计算	随机/均匀分布决定
最终布局	连续、有序	连续、有序	连续、顺序无规律
实现复杂度	中等	高	低
适用规模	大规模	中等规模	小规模

🟠 典型整理算法详解

🟠 1. 双指针回收算法 (Two-Finger Algorithm)

🟠 原理: 使用两个指针从堆的两端向中间移动，交换可达对象和垃圾对象

🟠 具体过程:

🟠 第一次遍历：计算每个可达对象的新地址（压缩到堆的一端）
🟠 记录偏移量：记录每个对象的新地址和偏移量
🟠 对象移动：将对象移动到新位置
🟠 第二次遍历：更新对象的引用关系，根据新地址更新引用

🟡 特点:

🟡 需要依赖可达对象和空闲对象空间的大小
🟡 需要分两次遍历完成
🟡 适合对象大小相对均匀的情况

🟠 2. Lisp2算法 (Three-Pointer Algorithm)

🟠 原理: 使用三个指针进行三次遍历的整理算法

🟠 具体过程:

🟠 第一次遍历：计算每个对象的新地址
🟠 第二次遍历：更新所有引用关系
🟠 第三次遍历：移动对象到新位置

🟡 特点:

🟡 三次遍历，算法复杂度较高
🟡 适合对象大小差异较大的情况
🟡 实现相对简单，易于理解

🟠 3. 引线整理算法 (Threaded Compaction)

🟠 原理: 在对象移动过程中建立引线，减少遍历次数

🟡 特点:

🟡 减少遍历次数，提高效率
🟡 实现复杂，需要额外的引线结构
🟡 适合大规模对象整理

🟠 4. 单次遍历算法 (One-Pass Algorithm)

🟠 原理: 在一次遍历中完成标记、计算地址、更新引用和移动对象

🟡 特点:

🟡 只需要一次遍历，效率最高
🟡 实现复杂，需要精心设计
🟡 适合对性能要求极高的场景

🔴 分代收集理论

🔴 分代收集理论是现代垃圾回收器的基础，基于对象生命周期的统计规律：

🟠 1. 弱分代假说 (Weak Generational Hypothesis)

🟠 核心观点: 绝大多数对象朝生夕死

🟠 统计规律:

🟠 大部分对象在创建后很快就会被回收
🟠 只有少数对象能够存活较长时间
🟠 年轻代对象回收频率高，但回收速度快

🟡 应用策略:

🟡 对年轻代使用复制算法
🟡 频繁进行Minor GC
🟡 优化年轻代的内存分配

🟠 2. 强分代假说 (Strong Generational Hypothesis)

🟠 核心观点: 年龄越久的对象越难以消亡

🟠 统计规律:

🟠 存活时间长的对象更可能继续存活
🟠 老年代对象回收频率低，但回收时间长
🟠 不同年龄的对象有不同的回收特点

🟡 应用策略:

🟡 对老年代使用标记-清除或标记-整理算法
🟡 减少老年代GC频率
🟡 优化老年代的内存管理

🟡 3. 跨代引用假说 (Intergenerational Reference Hypothesis)

🟡 核心观点: 跨代引用相对于同代引用来说只是极少数

🟡 应用策略:

🟡 使用记忆集(Remembered Set)记录跨代引用
🟡 减少跨代引用的扫描范围
🟡 提高分代GC的效率

🔴 垃圾回收算法面试问题

🔴 高频问题

🔴 核心问题：

"请详细说明垃圾回收的三种基本算法及其优缺点？"
- 标记-清除：实现简单但产生内存碎片
- 标记-复制：无碎片但内存利用率低
- 标记-整理：无碎片且利用率高但移动成本高
"什么是GC Roots？哪些对象可以作为GC Roots？"
- GC Roots是垃圾回收的起点
- 包括虚拟机栈引用、方法区静态变量、常量、JNI引用等
"为什么说标记-复制算法适合年轻代？"
- 年轻代对象大部分朝生夕死，存活率低
- 复制成本相对较低，且能避免内存碎片

🟠 中频问题：

"标记-清除算法为什么会产生内存碎片？如何解决？"
- 对象回收后留下不连续空间
- 通过标记-整理算法或分区收集解决
"分代收集理论的三个假说分别是什么？"
- 弱分代假说：绝大多数对象朝生夕死
- 强分代假说：年龄越久的对象越难以消亡
- 跨代引用假说：跨代引用只是极少数
"双指针回收算法和Lisp2算法有什么区别？"
- 双指针：两次遍历，适合对象大小均匀
- Lisp2：三次遍历，适合对象大小差异大