嵌入式内存管理垃圾搜集器实时算法研究

论文摘要

随着嵌入式实时软件系统的规模越来越大，复杂度迅速增加，内存管理也越来越重要，用垃圾搜集器(GC)进行自动内存管理克服了人工内存管理所导致的潜在危险，例如内存泄漏，指针悬挂，内存碎片等。然而，传统的GC在运行时需要停止所有进程的执行，这显然是不适合实时系统的。因此对垃圾搜集器的实时化的研究，将其应用于大规模嵌入式实时系统软件的开发，可以提高嵌入式实时软件开发的效率，对于缩短开发周期，提高系统安全可靠性方面具有重要的意义。论文论述了垃圾搜集器对嵌入式实时系统的作用和意义，介绍了实时垃圾搜集器的发展演变历程，几种具有代表性的垃圾搜集器算法和实时垃圾搜集器策略。由于嵌入式实时系统往往存在于资源有限的环境中，论文着重研究了如何在保证垃圾搜集器实时性的条件下，降低系统内存需求的方法。主要的贡献和创新之处包括：1．全面系统地总结了实时垃圾搜集器发展演变的历程和分布式垃圾搜集器的发展现状。嵌入式实时系统往往应用在资源有限的环境中，在分析了现有的实时垃圾搜集器的基础上，提出了动态GC策略，该策略使GC在执行过程中可以动态地根据任务的状态来依次处理各任务的内存空间，从而在保证系统硬实时的条件下降低了系统的内存需求，另外，动态延迟法使GC在任务都变为非活动状态时再回收其内存空间，可以节余一定的非周期任务服务器时间片用以调度非周期任务，从而提高了系统灵活性。2．在调度策略上提出了用EDF调度GC的方法，通过内存分析和仿真实验证明如果系统中的任务数不多，即不考虑调度开销的条件下，用EDF调度GC可以在保证系统硬实时任务满足时限的条件下进一步降低系统内存需求，并且使系统可调度非周期任务，灵活性更高。3．系统研究了当前混杂垃圾搜集器算法。提出了渐进式回收循环垃圾的方法，可以在当前GC循环中渐进地回收循环垃圾以供系统重用，从而降低了系统内存需求。还提出了引用计数与时间戳的混杂GC算法，该算法同样可以在保证系统实时性的条件下，在当前GC循环中局部回收循环垃圾并及时供系统重用，从而降低系统内存需求，而且该算法的执行时间与系统全局对象数无关，因此与采用全局标记清除算法的GC策略相比，该算法更适用于大规模系统。4．系统研究了分布式垃圾搜集器的发展现状和几种典型的分布式GC策略。提出了基于关键引用验证的分布式垃圾搜集器，该算法可以在最短时间内回收循环垃圾，因而保证节点内存不会被耗尽，从而使算法具有一定的实时性，该算法尽管需要一些存储开销为代价，但其它开销较小，易于实现，并具有很好的容错性，因而综合性能较高。还提出了面向角色的混杂GC算法，与现有的面向角色系统的分布式垃圾搜集器相比，该算法具有容错性，更加适用于大规模系统。目前国内外研究机构对实时垃圾搜集器的研究还处于发展阶段，存在许多待解决的问题。本文分别对实时垃圾搜集器的调度策略，混杂垃圾搜集器算法以及分布式垃圾搜集器等几个方面进行了深入的研究和实践，并提出了自己的算法策略，为提高实时垃圾搜集器性能作出了应有的贡献。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 嵌入式实时系统介绍
• 1.1.2 传统内存管理的缺陷
• 1.1.3 实时垃圾搜集器
• 1.2 研究目的和意义
• 1.3 国内外研究现状
• 1.4 本文的主要工作
• 1.5 本文的组织
• 第二章 实时垃圾搜集器的发展
• 2.1 几种主要的垃圾搜集器算法
• 2.1.1 标记清除算法
• 2.1.2 拷贝算法
• 2.1.3 引用计数算法
• 2.1.4 三种垃圾搜集器算法的比较
• 2.2 渐进式垃圾搜集器
• 2.3 基于时间的GC
• 2.3.1 半调度策略
• 2.3.2 基于非周期任务服务器的并发式GC
• 2.3.3 时间触发的GC
• 2.4 本章小结
• 第三章 实时垃圾搜集器的调度策略
• 3.1 实时调度算法
• 3.1.1 调度周期性任务
• 3.1.2 调度非周期任务
• 3.2 GC实时调度模型
• 3.2.1 符号及系统定义
• 3.2.2 垃圾搜集器和实时任务的关系模型
• 3.3 基于间发服务器（SS）的实时GC策略
• 3.3.1 策略说明
• 3.3.1.1 GC算法
• 3.3.1.2 调度策略
• 3.3.2 内存分析
• k^*估值上限以降低系统内存需求'>3.4 减小L_k^*估值上限以降低系统内存需求
• 3.4.1 三步骤计算法
• 3.4.2 三步骤法实例说明
• 3.5 基于精确参数配置的实时GC策略
• 3.5.1 GC调度策略
• 3.5.2 精确参数配置法
• 3.5.3 仿真实验
• 3.6 动态GC策略
• 3.6.1 基于年代的GC算法
• 3.6.2 DGCS算法描述
• 3.6.3 仿真实验
• 3.6.4 动态调度非周期任务和GC
• 3.7 用EDF调度垃圾搜集器
• 3.7.1 算法描述
• 3.7.2 仿真实验
• 3.7.3 EDF和RM调度任务的延迟抖动比较分析
• 3.8 本章小结
• 第四章 混杂实时垃圾搜集器策略
• 4.1 混杂垃圾搜集器介绍
• 4.1.1 拷贝和标记清除混杂GC
• 4.1.2 引用计数和标记清除混杂GC
• 4.2 渐进式回收循环垃圾以降低系统内存需求
• 4.2.1 GC策略
• 4.2.2 内存分析
• 4.2.3 仿真实验
• 4.3 引用计数与时间戳的混杂GC算法
• 4.3.1 算法描述
• 4.3.2 仿真实验
• 4.4 本章小结
• 第五章 分布式实时垃圾搜集器
• 5.1 分布式拷贝垃圾搜集器
• 5.2 分组分布式垃圾搜集器
• 5.3 基于时间戳的分布式垃圾搜集器
• 5.3.1 带中心服务器的分布式GC
• 5.3.2 反向查询回收分布式循环垃圾
• 5.4 基于关键引用验证的分布式实时垃圾搜集器
• 5.4.1 VCR算法描述
• 5.4.2 关键引用的验证过程
• 5.4.3 性能分析
• 5.5 面向活动对象的分布式垃圾搜集器
• 5.5.1 面向活动对象的GC
• 5.5.2 面向角色的混杂GC
• 5.6 本章小结
• 第六章 全文总结
• 致谢
• 参考文献
• 攻博期间取得的研究成果