要学好网站开发要会什么,做门户网站需要学什么软件,经典网站模板,WordPress优化速度插件Java/Python/Go不同开发语言基础数据结构和相关操作总结 1. 常见gc方式1.1 gc判断对象是否存活1.2 引用计数法1.2 标记-清除算法1.3 复制算法1.4 标记-压缩算法1.5 分代收集算法 2. java的gc方式以及垃圾回收器2.1 gc方式2.1 gc回收器2.1.1 Serial收集器2.1.2 ParNew收集器2.1.… Java/Python/Go不同开发语言基础数据结构和相关操作总结 1. 常见gc方式1.1 gc判断对象是否存活1.2 引用计数法1.2 标记-清除算法1.3 复制算法1.4 标记-压缩算法1.5 分代收集算法 2. java的gc方式以及垃圾回收器2.1 gc方式2.1 gc回收器2.1.1 Serial收集器2.1.2 ParNew收集器2.1.3 Parallel Scavenge 收集器2.1.4 Parallel Old 收集器2.1.5 CMS收集器2.1.6 G1收集器 3. python的gc方式以及垃圾回收器3.1 gc方式3.2 gc回收器 4. go的gc方式以及垃圾回收器4.1 gc方式4.1.1 三色标记法4.1.2 gc工作原理 4.2 gc回收器 5. 疑问和思考6. 参考文档 由于最近频繁在java、python、go三种开发语言中不断切换有时候针对基础的数据结构和日常操作搞混了因此本文进行相关梳理。文中涉及的相关数据结构和日常操作并不复杂权当增强记忆和理解。通过整理常见的gc方法进行内存回收并梳理不同开发语言对于gc的使用方式以及相关利弊。 1. 常见gc方式
垃圾收集(Garbage Collection) 通常被称为GC它诞生于1960年 MIT 的 Lisp 语言经过半个多世纪目前已经十分成熟了。 jvm 中程序计数器、虚拟机栈、本地方法栈都是随线程而生随线程而灭栈帧随着方法的进入和退出做入栈和出栈操作实现了自动的内存清理。 返回java常见gc方式
1.1 gc判断对象是否存活
gc需要判断对象是否存活以判断是否能够进行回收。判断对象是否存活一般有两种方式 引用计数 每个对象有一个引用计数属性新增一个引用时计数加1引用释放时计数减1计数为0时可以回收。此方法简单无法解决对象相互循环引用的问题。 可达性分析(Reachability Analysis) 从GC Roots开始向下搜索搜索所走过的路径称为引用链。当一个对象到GC Roots没有任何引用链相连时则证明此对象是不可用的是不可达对象。
1.2 引用计数法
通过对每个对象维护一个引用计数器来判断对象是否可回收。当引用计数器为0时对象被认为是垃圾可以被回收。 优点实现简单垃圾对象便于辨识判定效率高回收没有延迟性。
缺点
需要单独的字段存储计数器这样的做法增加了存储空间的开销。每次赋值都需要更新计数器伴随着加法和减法操作这增加了时间开销。引用计数器还有一个严重的问题即无法处理循环引用的问题这是一条致命的缺陷
1.2 标记-清除算法
“标记-清除”(Mark-Sweep)算法如它的名字一样算法分为标记和清除两个阶段首先标记出所有需要回收的对象在标记完成后统一回收掉所有被标记的对象。之所以说它是最基础的收集算法是因为后续的收集算法都是基于这种思路并对其缺点进行改进而得到的
它的主要缺点有两个
一个是效率问题标记和清除过程的效率都不高另外一个是空间问题标记清除之后会产生大量不连续的内存碎片空间碎片太多可能会导致当程序在以后的运行过程中需要分配较大对象时无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作 1.3 复制算法
“复制”(Copying)的收集算法它将可用内存按容量划分为大小相等的两块每次只使用其中的一块。当这一块的内存用完了就将还存活着的对象复制到另外一块上面然后再把已使用过的内存空间一次清理掉
优点:
每次都是对其中的一块进行内存回收内存分配时也就不用考虑内存碎片等复杂情况只要移动堆顶指针按顺序分配内存即可实现简单运行高效。
缺点
将内存缩小为原来的一半持续复制长生存期的对象则导致效率降低 1.4 标记-压缩算法
根据老年代的特点有人提出了另外一种标记-压缩(Mark-Compact)算法标记过程仍然与标记-清除算法一样但后续步骤不是直接对可回收对象进行清理而是让所有存活的对象都向一端移动然后直接清理掉端边界以外的内存
1.5 分代收集算法
GC分代的基本假设绝大部分对象的生命周期都非常短暂存活时间短。 “分代收集”(Generational Collection)算法把Java堆分为新生代和老年代这样就可以根据各个年代的特点采用最适当的收集算法。
在新生代中每次垃圾收集时都发现有大批对象死去只有少量存活那就选用复制算法只需要付出少量存活对象的复制成本就可以完成收集老年代中因为对象存活率高、没有额外空间对它进行分配担保就必须使用**“标记-清理或标记-压缩”**算法来进行回收
2. java的gc方式以及垃圾回收器
2.1 gc方式 常见gc方式 中介绍的gc方式java都在使用相关的工作原理参考
2.1 gc回收器
如果说收集算法是内存回收的方法论垃圾收集器就是内存回收的具体实现
2.1.1 Serial收集器
串行收集器是最古老最稳定以及效率高的收集器可能会产生较长的停顿只使用一个线程去回收新生代、老年代串行回收新生代使用复制算法老年代使用标记-压缩算法垃圾收集的过程中会Stop The World(服务暂停)
参数控制-XX:UseSerialGC 指定收集器为Serial收集器
2.1.2 ParNew收集器
ParNew收集器其实就是Serial收集器的多线程版本新生代使用复制算法并行收集老年代使用标记-压缩算法串行收集
参数控制 -XX:UseParNewGC 指定收集器为ParNew收集器 -XX:ParallelGCThreads 限制线程数量
2.1.3 Parallel Scavenge 收集器
Parallel Scavenge收集器类似ParNew收集器Parallel收集器更关注系统的吞吐量。可以通过参数来打开自适应调节策略虚拟机会根据当前系统的运行情况收集性能监控信息动态调整这些参数以提供最合适的停顿时间或最大的吞吐量也可以通过参数控制GC的时间不大于多少毫秒或者比例新生代使用复制算法老年代使用标记-压缩
参数控制-XX:UseParallelGC 使用Parallel收集器老年代串行
2.1.4 Parallel Old 收集器
Parallel Old是Parallel Scavenge收集器的老年代版本使用多线程和标记压缩算法。这个收集器是在JDK 1.6中才开始提供
参数控制 -XX:UseParallelOldGC 使用Parallel收集器老年代并行
2.1.5 CMS收集器
CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的收集器。目前很大一部分的Java应用都集中在互联网站或B/S系统的服务端上这类应用尤其重视服务的响应速度希望系统停顿时间最短以给用户带来较好的体验。
从名字(包含Mark Sweep)上就可以看出CMS收集器是基于标记-清除算法实现的它的运作过程相对于前面几种收集器来说要更复杂一些 整个过程分为4个步骤包括
初始标记(CMS initial mark)并发标记(CMS concurrent mark)重新标记(CMS remark)并发清除(CMS concurrent sweep) 其中初始标记、重新标记这两个步骤仍然需要Stop The World。初始标记仅仅只是标记一下GC Roots能直接关联到的对象速度很快并发标记阶段就是进行GC Roots Tracing的过程而重新标记阶段则是为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录这个阶段的停顿时间一般会比初始标记阶段稍长一些但远比并发标记的时间短。
由于整个过程中耗时最长的并发标记和并发清除过程中收集器线程都可以与用户线程一起工作所以总体上来说CMS收集器的内存回收过程是与用户线程一起并发地执行。老年代收集器新生代使用ParNew
优点:并发收集、低停顿 缺点产生大量空间碎片、并发阶段会降低吞吐量
参数控制
-XX:UseConcMarkSweepGC 使用CMS收集器 -XX:UseCMSCompactAtFullCollection Full GC后进行一次碎片整理整理过程是独占的会引起停顿时间变长 -XX:CMSFullGCsBeforeCompaction 设置进行几次Full GC后进行一次碎片整理 -XX:ParallelCMSThreads 设定CMS的线程数量(一般情况约等于可用CPU数量) 2.1.6 G1收集器
G1是目前技术发展的最前沿成果之一HotSpot开发团队赋予它的使命是未来可以替换掉JDK1.5中发布的CMS收集器。与CMS收集器相比G1收集器有以下特点
空间整合G1收集器采用标记-压缩算法不会产生内存空间碎片。分配大对象时不会因为无法找到连续空间而提前触发下一次GC。 可预测停顿这是G1的另一大优势降低停顿时间是G1和CMS的共同关注点但G1除了追求低停顿外还能建立可预测的停顿时间模型能让使用者明确指定在一个长度为N毫秒的时间片段内消耗在垃圾收集上的时间不得超过N毫秒这几乎已经是实时JavaRTSJ的垃圾收集器的特征了。 上面提到的垃圾收集器收集的范围都是整个新生代或者老年代而G1不再是这样。使用G1收集器时Java堆的内存布局与其他收集器有很大差别它将整个Java堆划分为多个大小相等的独立区域Region虽然还保留有新生代和老年代的概念但新生代和老年代不再是物理隔阂了它们都是一部分(可以不连续)Region的集合。
收集步骤
标记阶段首先初始标记(Initial-Mark),这个阶段是停顿的(Stop the World Event)并且会触发一次普通Mintor GC对应GC log:GC pause (young) (inital-mark)
Root Region Scanning程序运行过程中会回收survivor区(存活到老年代)这一过程必须在young GC之前完成。Concurrent Marking在整个堆中进行并发标记(和应用程序并发执行)此过程可能被young GC中断。在并发标记阶段若发现区域对象中的所有对象都是垃圾那个这个区域会被立即回收(图中打X)。同时并发标记过程中会计算每个区域的对象活性(区域中存活对象的比例)。 Remark, 再标记会有短暂停顿(STW)。再标记阶段是用来收集 并发标记阶段 产生新的垃圾(并发阶段和应用程序一同运行)G1中采用了比CMS更快的初始快照算法:snapshot-at-the-beginning (SATB)。
清理阶段 Copy/Clean up多线程清除失活对象会有STW。G1将回收区域的存活对象拷贝到新区域清除Remember Sets并发清空回收区域并把它返回到空闲区域链表中。 复制/清除过程后。回收区域的活性对象已经被集中回收到深蓝色和深绿色区域。
3. python的gc方式以及垃圾回收器
3.1 gc方式
主要通过引用计数Reference Counting进行垃圾回收通过标记清除解决循环对象的循环依赖问题在循环引用对象的回收中整个应用程序会被暂停为了减少应用程序暂停的时间Python 通过“分代回收”(Generational Collection)以空间换时间的方法提高垃圾回收效率。
3.2 gc回收器
python没有提供类似java复杂的gc回收器而是可以通过gc模块提供垃圾回收器的接口进行gc的控制。
此模块提供可选的垃圾回收器的接口提供的功能包括关闭收集器、调整收集频率、设置调试选项。它同时提供对回收器找到但是无法释放的不可达对象的访问。由于 Python 使用了带有引用计数的回收器如果你确定你的程序不会产生循环引用你可以关闭回收器。可以通过调用 gc.disable() 关闭自动垃圾回收。若要调试一个存在内存泄漏的程序调用 gc.set_debug(gc.DEBUG_LEAK) 需要注意的是它包含 gc.DEBUG_SAVEALL 使得被垃圾回收的对象会被存放在 gc.garbage 中以待检查。
import gc
import pprintclass Graph:def __init__(self, name):self.name nameself.next Nonedef set_next(self, next):print(Linking nodes {}.next {}.format(self, next))self.next nextdef __repr__(self):return {}({}).format(self.__class__.__name__, self.name)# 构造一个引用循环。
one Graph(one)
two Graph(two)
three Graph(three)
one.set_next(two)
two.set_next(three)
three.set_next(one)print()
print(three refers to:)
for r in gc.get_referents(three):pprint.pprint(r)4. go的gc方式以及垃圾回收器
当前Golang使用的垃圾回收机制是三色标记法配合写屏障和辅助GC三色标记法是标记-清除法的一种增强版本。
4.1 gc方式
4.1.1 三色标记法
三色标记法是对标记阶段的改进原理如下
初始状态所有对象都是白色。从root根出发扫描所有根对象下图a,b将他们引用的对象标记为灰色图中AB 分析灰色对象是否引用了其他对象。如果没有引用其它对象则将该灰色对象标记为黑色上图中A如果有引用则将它变为黑色的同时将它引用的对象也变为灰色上图中B引用了D重复步骤3直到灰色对象队列为空。此时白色对象即为垃圾进行回收。
4.1.2 gc工作原理
GC工作的完整流程
Mark: 包含两部分:Mark Prepare: 初始化GC任务包括开启写屏障(write barrier)和辅助GC(mutator assist)统计root对象的任务数量等。这个过程需要STWGC Drains: 扫描所有root对象包括全局指针和goroutine(G)栈上的指针扫描对应G栈时需停止该G)将其加入标记队列(灰色队列)并循环处理灰色队列的对象直到灰色队列为空。该过程后台并行执行Mark Termination: 完成标记工作重新扫描(re-scan)全局指针和栈。因为Mark和用户程序是并行的所以在Mark过程中可能会有新的对象分配和指针赋值这个时候就需要通过写屏障write barrier记录下来re-scan 再检查一下。这个过程也是会STW的。Sweep: 按照标记结果回收所有的白色对象该过程后台并行执行Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC。
写屏障(Write Barrier) 在每一轮GC开始时会初始化一个叫做“屏障”的东西然后由它记录第一次scan时各个对象的状态以便和第二次re-scan进行比对引用状态变化的对象被标记为灰色以防止丢失将屏障前后状态未变化对象继续处理。
辅助GC Go 语⾔如果发现扫描后回收的速度跟不上分配的速度它依然会把⽤户逻辑暂停⽤户逻辑暂停了以后也就意味着不会有新的对象出现同时会把⽤户线程抢过来加⼊到垃圾回收⾥⾯加快垃圾回收的速度。这样⼀来原来的并发还是变成了STW还是得把⽤户线程暂停掉要不然扫描和回收没完没了了停不下来因为新分配对象⽐回收快所以这种东⻄叫做辅助回收。
4.2 gc回收器
go没有提供类似java复杂的gc回收器
5. 疑问和思考
暂无
6. 参考文档
图解常见 GC 算法和垃圾收集器
