论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf

所需积分/C币:10 2019-08-20 03:22:59 288KB .PDF
收藏 收藏
举报

嵌入式Java虚拟机的垃圾回收算法的研究,刘健培,,在嵌入式系统中,需要分析什么样的垃圾回收机制能够适应嵌入式系统的特点,满足系统对于稳定性和性能的要求。本文阐述了嵌入式Jav
山国科技记义在绳 http://www.paper.edu.cn 然后作上标 (2)清除阶段。这个阶段从堆空间起始位置査找所有的对象,将没有打上标记的对象所 占用的空间回收。 其执行过程如下:首先,从系统的根集root出发,遍历对象引用图,当所找的对象没 有被标记时,则给对象打上标记。当所有的可达对象都标记完成后,就进入到清除阶段。在 清除阶段,从对象块链头开始,査找所有的未标一记对象并从链中清除掉,从而回收空间 在标记清除算法中,由于大量的对象块回收,可能造成有用对象间存在着大量的空闲块, 而这些块又不足以分配给对象,因而会出现大量的内存碎片。 24分代收集算法 通过对堆分配的对象的生命期的分析,有以下两个特点: (1)创建的大部分对象都具有很短的生命期,这些对象被创建后很快就会死亡 (2)创建的部分对象却具有非常长的生命期,这些对象创建后会生存很长时间。 基于这两点,可以采用不同的策略来分别管理年轻和年老的对象,从而避免了在内存压 缩的时候对象的不必要移动,也可以避免在简单的拷贝收集算法中每次都把这些生命周期都 艮长的对象来回拷贝,消耗大量的吋间。分代收集算法( generation- based Algorithm)是基 于以上的研究提出米的,其基本思想是将可用的内存堆划分成两个或者更多更小的子堆或者 称为代,不同代中采用相对独立的垃圾收集算法。对象首先在最年轻代中进行分配,同时最 年轻的那一代也进行最频繁的垃圾收集。因为大多数对象都是短暂出现的,只有很小部分的 年轻对象可以在它们经历第一次收集后还存活。如果一个最年轻的对象经历了好几次垃圾收 集后仍然存活,那么这个对象就成长为寿命更高的一代,它被转移到力外一个子堆中去。由 于年龄更高的一代相对比较稳定,生命期也更长,因而对这一代的攻集都没有年轻的那一代 频繁。每当对象在所属的年龄层中变得成熟之后,它们就被转移到史高的年龄层中去。 分代回收算法在大多数时候都只需要对新生代进行垃圾回收,有效减少了标记阶段的计 算量和停顿吋间,有较高的垃圾回收率,并且该算法还有个附加的好处,就是快速内存分 配。因为空闲内存都集中在一个连续的区域,在分配时只需要进行一次指针的增量移动,而 不需要维持一个空闲空间表,并在分配时查找大小合适的空闲空间。 分代收集算法贔然减小了停顿的时间,但是并不一定能够提高整个垃圾冋收的效率,这 需要用户针对不同应用种类设置参数,来调整新旧牛代的尺寸比例,从而优化垃圾回收。在 旧生代中始终有部分的空闲内存空间无法加以利用,存在空间的浪费。另外,该算法还需要 实现与拦截,记录指向新生代的引用,作为判断其中存活对象的依据,这也需要额外的时间 和空间消耗。 2.5增量收集算法 为了保证程序的实时性,系统必须是可预测的,这要求系统在最坏情况下延迟时间短 可跳跃,而且事件必须要在可预测的时间内发生。交互式系统对此并没有严格的要求,大多 数时候这种延迟并不足以引起用户的注意,但在实时系统中对此就有较高的要求。 垃圾收集一般都会停止整个程序的运行来査找和收集垃圾对象,它们可能在程序执行的 任意时刻暂停,并且暂停的时间乜无法确定。这种垃圾收集暂停有时候长得让用户都注意到 了。垃圾收集也可能使得程序对事件响应迟钝,无法满足实时系统的要求。如果一种垃圾收 集算法可能导致用户察觉到停顿或者使得程序无法适合实吋系统的要求,这种算法被称为破 坏性的。为了减少垃圾收集和明桷释放对象之间的潜在差距,设计垃圾收集算法的一个基本 山国科技记义在绳 http://www.paper.edu.cn 目标就是使本质上的破坏性尽可能少,如果可能的话,尽可能清除这种破坏性。 达到(或试图达到〕非破坏性垃圾收集的方法是使用增量垃圾收集算法( (Incremental Algorithm)。增量垃圾收集器就是不试图一次性发现并回收所有不可触及的对象,而是每次 发现并回收一部分。因为每次都只有堆的一部分执行垃圾收集,因此理论上说每一次收集会 持续更短的时间。如果有一个这样的支持渐进式收集方法的收集器,每次可以保证(或至少 非常接近)不超过一个最大时间长度,就可以让Jaⅵa虚拟机适合实时环境。限时壇量垃圾 收集器在用户环境中也令人满意,因为这样的收集器可以清除用户可察觉得到的垃圾收集停 顿 增量垃圾收集算法最适合」 (1)服务器应用程序,特别是高可用性的应用程序 (2)处理非常大的"活的"对象数据集的应用程序; (3)不希望有用户可感觉到的暂停的应用程序,如游戏、动画或交互式应用程序。 增量收集算法比较典型的是火车算法( Train Algorithm)和三色标记算法(Tri- color Marking Algorithm) 火车算法采用的方法是将堆划分成固定大小的小块,称为车厢;将车厢连接起来的一组 车厢就称为火车,垃圾收集每一次回收一个车厢或者整列火车。对每一节车相采用如下的收 集策略 (1)如果没有对整火车中的对象的外部引用,则回收此列火车的所有车厢 (2)递归转移被火车外引用的对象到引用它的那列火车 (3)递归转移破火车内引用的对象到本列火车的尾列车厢; (4)冋收没有被外部引用的火车车厢。 色标记算法的基本思想是将堆中的对象标记为三种颜色,不同的颜色代表着对象处于 不同的状态 (1)白色:表小对象没有被跟踪遍历,在遍历完成后他们是可以被收集的,对象创建时 标记为白色 (2)灰色:表示对象是活动的,而且将会被遍历到; (3)黑色:表示对象是活动的,而且已经被遍历完成。 对对象引用图遍历的过程就是将对象划分成标记为黑色的对象和标记为白色的对象。遍 历完成后不会存在灰色的对象,而白色的对象是没有被遍历到的对象也就是垃圾,可以回收。 在垃圾收集开始时,除了根以外的对象都是白色。扫描开始后,首先是根直接指向的对 象的颜色变为灰色,当这些对象被扫描完后,它们的颜色变为黑色,并且它们所引用的对象 由白色变为灰色,此操作继续下去,直到没有灰色对象为止。这时,白色对象是可以被回收 的,黑色对象是活动的 在增量垃圾收集过程中,每当程序分配对象空间时,回收程序可按规定遍历部分灰色对 象,转而继续执行原程序,程序在执行吋又有可能修改已有对象的教据域,可能导致黑色对 象对白色对象的引用,而黑色对象只能够对灰色对象的引用,这就要求保持对象遍历的·致 性。可以采用以下的两个措施: (1)防止增变器看到白色对象; (2)告知收集器仟何黑色对象对白色对象的引用,以便跟踪。 3.嵌入式系统的垃圾回收算法分析 山国科技记义在绳 http://www.paper.edu.cn 3.1嵌入式系统的内存管理特点 以上分析的各种叵收方法中,都不同程度地存在着一些不足。理想情况下,系统设计者 应能选择合适的内存回收算法以更好地满足系统要求。在嵌入式领域內,这种灵活性至关重 要,针对不同用途的嵌入式系统要有不同的设计方法 对」具体的嵌入式系统,往往在以卜四个方面有不同的要求: (1)运行时环境的特征; (2)硬件特征以及嵌入式环境的限制; (3)希望拥有的性能; (4)存储资源严重紧张时候如何处理。 些嵌入式系统的运行时环璄特征决定其垃圾回收算法必须满足“硬实时”或者“软实 时”的要求。但是,由实时回收附加的复杂性,空间和时间负载往往与嵌入式系统的其他要 求相互抵触。对于有较高的处理要求而实时响应不太重要的情况,虚拟机可以采用较保守的 算法。相反,如果实时响应很重要,可代之釆用增量式内存凹收的主动算法。 嵌入式系统中RAM和ROM都是紧缺资源,存储限制使得那些拷贝算法、自适应性算 法以及协同算法等复杂算法不适用于嵌入式系统。引用计数算法中引用计数的计算需要对象 拥有一个用米计算引用计数的域,这个域一般是一个指针或者其他可以代表一个有效地址的 值;标记—紧缩算法和标记清除算法屮需要一个bi或者几个bit来标忐对象的标记信息 三色算法以及反向标记算法可能需要几个bit。这些由回收器内部带来的存储需求必须尽可 能的维持在一个很小的范围之内。 嵌入式Java应用程序一般要和用户交互,这要求一个快速的垃圾回收算法,提供可预 知的性能。所以,需要周期的执行“部分”垃圾回收从而使待当每个单元释放的时候不全于 执行一次回收算法,同时,当算法执行的时候不应该有可被觉察的停止或者速度下降。提高 可预知性可以通过堆分段技术来解决,可采用“分代”回收算法。 存储紧张时系统大败是无法容忍的,大多数嵌入式系统无可交换的虚拟內存机制,这意 味着访问任何一块內存有固定的开销,同时它也减少了标记一清除算法和拷贝算法在回收垃 圾之前访问活动单元的代价;另一方面,这同时意味着堆不能被扩展,当存储到一个非常低 的水平,收集器不能依靠虚拟存储来作为一个临时解决小法。 32适合嵌入式系统的垃圾回收优化技术 针对上述嵌入式设备的特点和目前Java虛拟机所采用的垃圾回收策略,我们选择了 种自适应的分代垃圾回收算法( Dynamic Generational GC)。由于嵌入式设备内存资源十分宝 贵,而分代垃圾回收算法中将内存空间分为不同的代,每代所占的的内存空间是固定的。这 样,程序运行时,如果某代中的对象较少,该代中空闲的内存空间就不能被其他代利用,造 成内存空间的浪费。 因此,我们采用一种自适应的算法来克服分代垃圾回收算法的上述缺点。所谓自适应是 指所有的堆空间在初始化时都归属于辈份最低的子孙代,此时的内存管理没有分代的概念。 但是我们仍然要记求每个内存对象的年龄,即该内存对象所经历的垃圾回收的次数。当某个 对象的年龄达到了升级的要求时,我们就会试图在该对象所在的代空间的头部分出块适当 大小的空间,在适当的时候将对象拷贝过水,并把对象和它所占的内存空间一起标记为父亲, 系统会对已经标记为父亲的空间采取不同于其子孙的垃圾回收策略。这就象父亲代在程序网 开始运行时是不存在的,随着程序的执行父亲代被动态的分配出来(这就是所谓的 山国科技记义在绳 http://www.paper.edu.cn Dynamic),并随着当前系统中父亲代对象所占据空间大小的变化而变化(即自适应)的 这样即避免了垃圾回收器对生命周期较长的内存对象的重复操作,达到了分代垃圾回收 的目的;又使父亲代空间的容量与其中的对象大小相匹配,充分利用了可用的内存空间。 另外,为了实现 Dynamic Generational GC和进一步提高虚拟机的性能,我们还采取了 其他几项优化技术,包括: (1)立即升级:如果一个对象本身已位于代的首部,它又成为父亲,则可立即将该对象 和它占据的空间划归为父亲代,而无须拷贝 (2)空间预留,延迟升级:由于父辈空间必须在子孙辈之前,如果某个不位于首部的对 象成为父亲,而子孙代头部的这部分空间又被其它对象占据,则我们只将该首部空 间标记为预留,经过一段时间后,该父亲对象一定可以在首部得到足够的空闲空间 这时,再将它拷贝进米,并真正成为父亲 (3)使用堆栈记录标记路径:使用一个堆栈来记录标记路径上每一个节点用于路径回 溯,并且该堆栈可以动态扩展,以保证其不会溢出。这样就可以使用一个循环来完 成所有内存对象的标记,彻底避免了使用递归调用来标记对象而带来的递归栈溢 出,重复扫措等问题。 (4)对内存进行分时扫描:对整个需要垃圾回收的Java堆空间扫描并不一次完成,而 是一旦发现堆中凵有足够的空附空间来满足应用程序的需求时就停止。剩下的工作 可以在虚拟机运行的间歇分为多次完成。 (5)在对象压缩中嵌入指针回溯算法:使用指针回溯算法代替目前压缩算法中 breakable的功能这样就不用维护 breakable,执行压缩操作时也不用耗费大量的时 间去填充和查找 brcaktablc 4.总结 垃圾回收是Java语言的一大特色,因为它使得Java语言成为一种简单而安全的语言。 但是垃圾回收并不是Java的创举,早在10多年前,在Lisp语言和函数式语言等领域,垃 圾回收已经逐渐成熟,但是今天垃圾收集己经成为许多现代程序设计语言内存管理系统的重 要部分。由于嵌入式系统中计算和内存资源的限制,需要对己有的嵌入式Java虚拟机中的 垃圾回收算法和技术进行改造,从而适应需求。本章首先谈了玩圾收集对内存分配与管理中 起到的作用,然后综述了比较流行的,使用于Java虚拟机的实现中的几种垃圾回收算法。 最后提出了一种改进的分代式垃圾回收算法 参考文献 1严东华,张凯.lava虚拟机及其移植[冂].北京坦大学学报,2002,38(5):64~67 2 Jones R, Lins R Garbage Collection, Algorithms for Automatic Dynamic Memory ManagementM. Wiley, 1996: 262-270 3 Venners B. Inside the Java Virtual Machine[M]. The McGraw-Hill Companies InC, 2000: 239-257 14 Wallace M, Runciman C An Incremental Garbage Collector for Embedded Real-time Systeins[C]. Proceedings of Chalmers Winter Meeting, 1993-06 [5]堪宁,覃征.基于嵌入式Java虚拟机的垃圾凹收算法[J].计算机应用,2005,25(1):36-38 Research of generation algorithm on embedded Vm Liu jianpei -6 山国科技记义在绳 http://www.paper.edu.cn Department of Computer Science and Technology, Beijing University of Posts and Telecommunications, Bcijing, PRC,(100876) Abstract In embedded systems, it is needed to analyze what kind of garbage collection strategy can adapt to the embedded system and content with the stability and performance. This paper compares th characteristics of garbage collection mechanism in embedded Java virtual machine, analyzes the strengths and shortcomings, introduces garbage collection optimization technology applicable to embedded systems based on the analysis of the features of embedded system memory management Keywords: Embedded system Java virtual machine Garbage collection Generation algorithm 作者简介:刘健培,男,1983年生,硕十研究生,主要硏究方向是嵌入式实时操作系统 计算机网络和通信办议。

...展开详情
试读 7P 论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf 10积分/C币 立即下载
    1/7
    论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf第1页
    论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf第2页
    论文研究-嵌入式Java虚拟机的垃圾回收算法的研究 .pdf第3页

    试读已结束,剩余4页未读...

    10积分/C币 立即下载 >