（计算机应用技术专业论文）嵌入式内存管理垃圾搜集器实时算法研究.pdf

摘要 摘要 随着嵌入式实时软件系统的规模越来越大，复杂度迅速增加，内存管理也越 来越重要，用垃圾搜集器( g c ) 进行自动内存管理克服了人工内存管理所导致的 潜在危险，例如内存泄漏，指针悬挂，内存碎片等。然而，传统的g c 在运行时需 要停止所有进程的执行，这显然是不适合实时系统的。因此对垃圾搜集器的实时 化的研究，将其应用于大规模嵌入式实时系统软件的开发，可以提高嵌入式实时 软件开发的效率，对于缩短开发周期，提高系统安全可靠性方面具有重要的意义。 论文论述了垃圾搜集器对嵌入式实时系统的作用和意义，介绍了实时垃圾搜 集器的发展演变历程，几种具有代表性的垃圾搜集器算法和实时垃圾搜集器策略。 由于嵌入式实时系统往往存在于资源有限的环境中，论文着重研究了如何在保证 垃圾搜集器实时性的条件下，降低系统内存需求的方法。主要的贡献和创新之处 包括： 1 全面系统地总结了实时垃圾搜集器发展演变的历程和分布式垃圾搜集器的发 展现状。嵌入式实时系统往往应用在资源有限的环境中，在分析了现有的实时 垃圾搜集器的基础上，提出了动态g c 策略，该策略使g c 在执行过程中可以 动态地根据任务的状态来依次处理各任务的内存空间，从而在保证系统硬实时 的条件下降低了系统的内存需求，另外，动态延迟法使g c 在任务都变为非活 动状态时再回收其内存空间，可以节余一定的非周期任务服务器时间片用以调 度非周期任务，从而提高了系统灵活性。 2 在调度策略上提出了用e d f 调度g c 的方法，通过内存分析和仿真实验证明如 果系统中的任务数不多，即不考虑调度开销的条件下，用e d f 调度g c 可以在 保证系统硬实时任务满足时限的条件下进一步降低系统内存需求，并且使系统 可调度非周期任务，灵活性更高。 3 系统研究了当前混杂垃圾搜集器算法。提出了渐进式回收循环垃圾的方法，可 以在当前g c 循环中渐进地回收循环垃圾以供系统重用，从而降低了系统内存 需求。还提出了引用计数与时间戳的混杂g c 算法，该算法同样可以在保证系 统实时性的条件下，在当前g c 循环中局部回收循环垃圾并及时供系统重用， 从而降低系统内存需求，而且该算法的执行时间与系统全局对象数无关，因此 与采用全局标记清除算法的g c 策略相比，该算法更适用于大规模系统。 摘要 4 系统研究了分布式垃圾搜集器的发展现状和几种典型的分布式g c 策略。提出 了基于关键引用验证的分布式垃圾搜集器，该算法可以在最短时间内回收循环 垃圾，因而保证节点内存不会被耗尽，从而使算法具有一定的实时性，该算法 尽管需要一些存储开销为代价，但其它开销较小，易于实现，并具有很好的容 错性，因而综合性能较高。还提出了面向角色的混杂g c 算法，与现有的面向 角色系统的分布式垃圾搜集器相比，该算法具有容错性，更加适用于大规模系 统。 目前国内外研究机构对实时垃圾搜集器的研究还处于发展阶段，存在许多待 解决的问题。本文分别对实时垃圾搜集器的调度策略，混杂垃圾搜集器算法以及 分布式垃圾搜集器等几个方面进行了深入的研究和实践，并提出了自己的算法策 略，为提高实时垃圾搜集器性能作出了应有的贡献。 关键词：实时，垃圾搜集器，调度，混杂算法，分布式系统 i i a b s t r a c t w i t hc o n 幛l 蹴t ) ro f 锄出e d d e dr e a l t i m e s y s t e m sg r o w sr a p i d l y , m e m o 巧 m a n a g e m e n ti sm o r ea n dm o r ei m p o r t a n t a u t o m a t i cs t o r a g em a n a g e m e n t , 0 rg a r b a g e c o n e c t i o n ( i e g c ) c a na v o i dp r o d u c i n gm e m o r yl e a k sa n dd a n g l i n gp o i n t e r s a i l d n l 锄卿盘a j 弘僦c o m p a r e dw i t hm a n u a lm e m o r ym a n a g e m e n t h o w e v e r , 们d l t l o n a l g a r b a g ec o l l e c t o rk n o w n 嬲s t o p t h e - w o r l d g c n e e d sa l lm u t a t o r ss t o p 删w h 锄n w o r k s o b 啊伽s l yi ti sn o tc o m p a t i b l ew i t hr e a l - t i m ep r o g r a m m i n g t h u s ，r c s e a r c h o t r e a l t i n l e 础a g ec o l l e c t i o na n da p p l y i n g i ti n t od e v e l o p m e n to fs o f t w a r e0 fl a r g e s c a l e e m b e d d e ds v s t 锄c a ne n h a n c et h ee f f i c i e n c y i ti si m p o r t a n tt os h o r t e nd e v e l o p m 髓t c v c l ea 1 1 de n h a n c et h es a f e t ya n dr e l i a b i l i t yo fe m b e d d e d r e a l - t i m es y s t e i i l s t h i sd i s s e r t a t i o ni n 仃o i i u c 懿f u n c t i o no fg a r b a g ec o l l e c t i o na n dh i s t o r y o fr e a l - t i m e g a r b a g ec o i l e c t i o n s o m et y p i c a la l g o r i t h m sa n ds t r a t e g i e s o fr e a l - 恤eg a r b a g e 训枷o na r ei i 灯o d u c e d s i n c ei ne m b e d d e ds y s t e m sr e s o u r c e ss u c h 嬲c p u a n d m 锄o “a r e1 砌t e d ，t h ed i s s e r t a t i o ne m p h a s i z e so nr e d u c i n gm e m o r yr e q l l l r e i l l e n t o i s v s t 锄o nt h ec o n d i t i o nt h a t r e a l t i m e t a s k sm e e tt h e i rd e a d l i n e s t h em 锄 c o n t 曲u t i o n so ft h i sd i s s e r t a t i o na t e a sf o l l o w s ： 1 d c 、，e l o p m 饥to f r e a l t i m eg a r b a g ec o l l e c t i o na n dd i s t r i b u t e dg a r b a g ec o l l e c n o n a r e 跚m m 撕z c d s i n c ei n 伽曲e d d e dr e a l - t i m es y s t e m s r e s o u r c e sa r el i m i t e d ，ad y i l a m i c 鳓a g ec o l l e c t i o ni sp r o p o s e d t h ep r o p o s e dg c c a n p r o c e s sm e m o r ys p a c e o te a c n t a s kd y n 锄i c a l l yb a s e do nt h ev a r i a n c eo fa m o u n to fl i v eo b j e c t s ，t h u s r e d u c e m 锄0 r yr e q u i r e i i l 吼tu n d e rt h e c o n d i t i o nt h a tm u t a t o r sm e e t st h e i r d e a d l l n e s f m 蹦n o r e ，i fg cd e f e r sp r o c e s s i n ga c t i v et a s k su n t i lt h e s t a t e so ft a s k sb e m e i i l a c t i v e m o r ct i i n es l i c eo fa p e r i o d i cs e r v e rc a nb es a v e df o ra p e r i o d l ct a s k s a n d f l e x i b i l i t yo fs y s t e mi se n h a n c e d 2 s c h e d u l i n gs 触e g yi sp r o p o s e d t h a tm u t a t o r sa n dg ca r es c h e d u l e du n d e re d f r i s p r o v e db ym e m o r ya n a l y s i sa n ds i m u l a t i o nt h a ti f t a s k sa r el i m i t e d ，e d fs c h e d u l e d s v s t e m sc a l lb em o r ep o r t a b l ea n ds y s t e mm e m o r yr e q u i r e m e n t c a nb et u | 姐e r r c d u c e d 唧a r e dw i t ho t h e rs c h e d u l i n gs t r a t e g i e sb a s e d o nr ma l g o r i t h m 蚰d 盯 t h ec o n d i t i o nt h a tm u t a t o r sm e e t t h e i rd e a d l i n e s i i i a b s t r a c t 3 h y b r i dg a r b a g ec o l l e c t i o n sa g er e s e a r c h e ds y s t e m a t i c a l l ya n da na l g o r i t h mo f i n c r e m e n t a lc o l l e c t i n gc y c l i cg a r b a g ei sp r o p o s e d g a r b a g ec o l l e c t i o nc a l lc o l l e c t p a r t i a lc y c l i cg a r b a g ed u r i n gt h eg cc y c l ef o rr e u s ea n dt h e r e f o r er e d u c em e m o r y r e q u i r e m e n t ah y b r i dg a r b a g ec o l l e c t i o nb a s e do nt i m e s t a m pi sa l s op r o p o s e d t h i s a l g o r i t h ma l s oc a np a r t l yc o l l e c tc y c l i cg a r b a g ew h e nd e a d l i n e so fr e a l - t i m et a s k s a l eg u a r a n t e e d f u r t h e r m o r e ，t h ep r o p o s e dg cf i t sf o rl a r g e - s c a l es y s t e mc o m p a r e d 丽mh y b r i dg cb a s e do i lm a r k - s w e e pa l g o r i t h ms i n c ee x e c u t i o nt i m eo fg ci s t m c o n c e m e dw i mo b j e c t so fs y s t e m 4 s o m et y p i c a ld i s t r i b u t e dg a r b a g ec o l l e c t i o n sa r er e s e a r c h e da n dar e a l - t i m e d i s t r i b u t e dg a r b a g ec o l l e c t i o nb a s e do nv e r i f i c a t i o no fc r i t i c a lr e f e r e n c ei sp r o p o s e d t h ea l g o r i t h mc a l ld e t e c ta n dr e c l a i mc y c l i cd i s t r i b u t e dg a r b a g ea tt h es h o r t e s tt i m e t oa v o i ds t o r a g es p a c e sa r ee x h a u s t e d , t h u si ti ss o f tr e a l - t i m e t h o u g ht h ea l g o r i t h m r e q u i r e sm o r em e m o r ys p a c e , i ti sf a u l t - t o l e r a n c ea n de a s yt ob ei m p l e m e n t e d 谢l l o wo v e r h e a d ah y b r i dd i s t r i b u t e dg a r b a g ec o l l e c t i o no fa c t i v eo b j e c t si sa l s o p r o p o s e da n di t i s f a u l t - t o l e r a n c ea n df i t sf o rl a r g e s c a l es y s t e mc o m p a r e dw i t h p r e v i o u sw o r k a tp r e s e n t , t h er e s e a r c h e so nr e a l t i m eg a r b a g ec o l l e c t i o na l ei nt h es t a g eo f d e v e l o p m e n t ，a n dt h e r ea r em a n yp r o b l e m st ob er e s o l v e d s c h e d u l i n gs t r a t e g yo f r e a l - t i m eg a r b a g ec o l l e c t i o n , h y b r i dg a r b a g ec o l l e c t i o na n dd i s t r i b u t e d g a r b a g e c o l l e c t i o na r er e s e a r c h e di nd e p t ha n dn e wa l g o r i t h m sa r ep r o p o s e d , w h i c hm a y c o n t r i b u t et oe n h a n c e m e n to f p e r f o r m a n c eo f r e a l t i m eg a r b a g ec o l l e c t i o n k e y w o r d s ：r e a l t i m e ，g a r b a g ec o l l e c t i o n , s c h e d u l i n g , h y b r i da l g o r i t h m , d i s t r i b u t e d s y s t e m i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：硷刍 日期：加9 年乡月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝金 一导师签名： 日期：纠年6 月i i e t 第一章绪论 1 1 课题研究背景 1 1 1 嵌入式实时系统介绍 第一章绪论 一般地说，实时系统是能及时响应外部发生的随机事件，并以足够快的速度 完成对事件处理的计算机应用系统。 在实时系统中，系统的正确性不仅取决于系统计算结果的正确性，而且取决 于正确结果产生的时间，因此系统设计者关心系统行为的确定性。 实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。 硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的 截止期限是无论如何都必须得到满足，否则就会出现灾难性的后果，比如航天中 的宇宙飞船的控制就是现实中这样的系统。而有实时特性但又非硬实时的系统都 可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来 说，一个任务能够得到有确保的处理时间，到达系统的事件也能够在截止期限到 来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就 是一种软实时系统。 嵌入式系统是指以应用为中心、以计算机技术为基础、软硬件可剪裁、适应 应用环境对功能、实时性、可靠性、成本、体积、功耗等严格约束的专用计算机 系统。严格说来，嵌入式系统和实时系统是不同的概念，嵌入式是指系统的存在 形态，而实时是指系统的时间特性。在实际工程中，嵌入式系统往往有实时要求， 而实时系统也往往以嵌入式的形式出现，故在本文中实时系统和嵌入式实时系统 表达的是相同的意义。 综观嵌入式实时系统的发展历程，可以发现嵌入式实时系统的特点及发展趋 势主要有以下几点。 1 实时性。实时性是实时系统最重要的特性，实时系统的任务都有一个截止时限， 硬实时系统要求任务必须严格满足截止时限的要求，否则一旦任务超出其时 限，就有可能造成人民财产和生命的重大损失，例如在航空航天、重要工程控 制等领域。而在软实时系统中，如果任务超出其截止时限则会在一定程度上影 电子科技大学博士学位论文 响系统性能。 2 资源有限。由于应用环境的限制，嵌入式实时系统拥有的资源是有限的，主要 表现在对整个计算机系统的体积、功耗、c p u 的处理能力、存储器的容量和性 能等方面都有较多的限制。 3 规模越来越大，系统越来越复杂。随着用户需求不断增加，嵌入式实时系统的 规模不断增大，系统复杂度不断提高，并且有从单机走向分布式系统的趋势。 随着嵌入式实时系统的快速发展，嵌入式实时系统的功能也越来越复杂，而 软件是实现嵌入式实时系统功能的关键，随着嵌入式实时系统软件的规模也越来 越复杂，能有效地开发大规模软件系统具有越来越重要的意义，同时对于软件系 统安全性可靠性的关注也日益增加。近年来，c 撑和j a v a 1 - 刁已经日益成为主流的 软件开发语言，应用范围非常广泛，其原因在于与传统的c 语言相比，它们的可 移植性更好，安全可靠性更高，对于大规模软件系统的开发效率更高。c 和j a v a 语言有一个共同特征，就是都应用了动态内存管理，即用垃圾搜集器来自动回收 系统中的无用内存，而无须象c 语言一样人工分配及回收内存，这样就避免了传 统内存管理的缺陷，使得软件开发中的缺陷及错误的概率大大降低，从而使系统 的安全可靠性得到很大提高。 1 1 2 传统内存管理的缺陷 传统的内存管理，即人工内存管理要求程序设计者人工使用内存操作函数分 配和回收内存，例如在c 语言中，内存分配函数是m a l l o c 0 ，相应的内存释放函数 是f r e e ( ) 。每块内存在分配使用结束后，都需要调用相应的内存释放函数进行内存 释放才可以使其为系统重用，任何对于内存管理不当的操作都有可能引起如下的 系统错误。 1 内存泄漏( m e m o r yl e a k ) ：内存泄漏指由于疏忽或错误造成程序未能释放已经 不再使用的内存的情况。一般我们常说的内存泄漏是指堆内存的泄漏。堆内存 是指程序从堆中分配的，大小任意的( 内存块的大小可以在程序运行期决定) ， 使用完后必须显式释放的内存。应用程序一般使用m a l l o c ，r e a l l o c ，n e w 等函 数从堆中分配到一块内存，使用完后，程序必须负责相应的调用f r e e 或d e l e t e 释放该内存块，否则，这块内存就不能被再次使用。内存泄漏会因为减少可用 内存的数量从而降低计算机的性能。在最糟糕的情况下，系统内存资源耗尽， 或过多的可用内存被分配掉导致全部或部分设备停止正常工作，或者应用程序 2 第一章绪论 崩溃。 2 指针悬挂( d a n g l i n gp o i n t e r s ) ：指针所指向的存储区的生存期已经结束，但是 指针的生存期还没有结束，导致存储区的数据已经被释放，指针所指的区域是 个随机值的这种错误，这叫指针悬挂，而这个指针就叫空悬指针。因此，当分 配的内存空间被回收后，指向它的指针也必须被回收或初始化，否则由于指针 指向一块未分配的内存空间，系统可能出现无法预期的错误。例如在c 语言中， 如果程序设计者误对一块m a l l o c 0 分配的内存空间调用两次f r e e 0 函数，则会导 致无法预期的情况发生。 3 内存碎片( m e m o r yf r a g m e n t ) ：由于不同的任务需要不同大小的内存，若应用 程序频繁申请与释放“随机大小的内存，则会导致尽管系统中有足够的空白 内存空间，却难以找到连续的一段符合所需分配内存大小的空间以供系统分 配，这些细小的无法被分配的空白内存被称为内存碎片。内存碎片过多会导致 系统性能急剧降低，甚至由于无法找到可供分配的内存块而导致系统崩溃。 在传统的人工内存管理中，各种内存管理操作必须非常谨慎，否则就容易导 致系统出错，而随着软件系统规模越来越大，系统复杂度越来越高，保证人工内 存管理正确性的难度也日益增大。如图1 1 所示，当软件规模较大时，内存的分配 和释放可能分布在不同的模块中，而这些程序模块又由不同的程序员完成，如果 这些程序员之间的配合和协调不够完善的话，就很容易导致忘记释放内存或者多 次释放同一内存等情况，从而造成系统出现如上所列的各种内存错误。 模块1模块2 模块n 图1 - 1 大型软件系统内存操作示例 目前软件设计大量的错误都来自于内存管理，它对大规模软件系统的安全可 靠性提出了严峻的挑战。为避免人工内存管理所可能导致的内存泄漏，指针悬挂， 内存碎片等等潜在的危险，以c j | j 和j a v a 语言为代表的主流程序设计语言开始采 用自动内存管理，即垃圾搜集器来自动回收无用内存，这不仅使程序员从烦琐的 3 电子科技大学博士学位论文 内存管理操作中解放出来，而且降低了软件程序的错误率，提高了系统的安全可 靠性。 1 1 3 实时垃圾搜集器 垃圾搜集器( g a r b a g ec o l l e c t i o n ，简称为g c ) 是一种内存动态管理软件，负 责垃圾对象占据内存空间的自动识别和回收，在应用g c 管理内存的系统中，应用 程序无须人工释放内存，对无用内存的分辨和回收都由系统自动完成，因而在应 用程序中大部分容易导致系统错误的内存管理代码都可以去除，从而降低应用程 序的开发复杂度，提高系统的安全性。 然而，随着计算机软件的发展，嵌入式实时软件系统也日益规模化复杂化， 尽管垃圾搜集器有许多优点，它却仍然不能应用于实时系统的软件开发中。使用 垃圾搜集器管理内存的j a v a 和c 幅言不能用于实时软件开发，在嵌入式实时领 域，主流的开发语言仍然是c ，其主要的原因是垃圾搜集器的实时化还面临着许多 问题和困难。 毫无疑问，内存管理必然需要一些系统开销，包括额外的储存空间需求，额 外的执行时间需求，而对于嵌入式实时系统所面临的有限的内存资源和严格的任 务时限的要求，实时垃圾搜集器不仅需要完成其自身工作，即辨认并回收系统中 无用内存，而且必须保证满足实时任务的时限要求，并且在运行中还要保证任何 时候系统内存资源不会耗尽，防止系统无法分配内存而暂停任务执行的情况发生。 实时任务最重要的特征是实时性，实时系统被分为软实时系统和硬实时系统，垃 圾搜集器和实时任务都有平均情况开销和最坏情况开销，特别在需要严格保证任 务时限的硬实时系统中，垃圾搜集器的运行要求在最坏情况下仍然能保证实时任 务在其时限内完成。因此，如何保证实时任务的时限要求( 特别是在硬实时系统 中) 贯穿了整个实时垃圾搜集器的发展历史。 垃圾搜集器对无用内存的分辨方法迄今为止没有发生什么变化，各种垃圾搜 集器都遵循着这样的方式，即系统从一组指针或堆栈开始遍历内存，这组指针或 堆栈被称为根结点，系统所有的对象都被这组根结点直接或间接引用。g c 从这组 根结点开始遍历，所有根结点可到达的对象都被称为活动对象，这类对象被认为 是系统仍然使用的而加以保留，相反，把所有这组指针不能到达的对象被称为非 活动对象或死对象，这类对象就被看作是垃圾，它们所占据的内存空间就被g c 重 新回收以供系统重新分配。如图1 2 所示。 4 第一章绪论 根指针 图1 2 无法从根指针到达的对象是垃圾对象 1 2 研究目的和意义 随着计算机技术的快速发展，嵌入式实时系统的应用范围也日益广泛，涉及 到人类生活的诸多方面，如数字通信、信息家电、航空航天、工业过程控制及军 事电子等。近年嵌入式实时系统保持持续高速增长，调查数据表明嵌入式实时系 统的年增长率约为1 8 ，大约是整个信息产业平均增长率的两倍，目前世界上大 约有2 亿台通用计算机，而嵌入式处理器大约有6 0 亿个，嵌入式实时系统是二十 一世纪信息产业的重要增长点。 在传统软件开发领域，近年来，c 舟和j a v a 以其可移植性、高效率、安全可 靠性日益成为主流的程序设计语言，其中一个重要原因在于它们都应用了垃圾搜 集器进行自动内存管理【3 ，4 1 。这样就避免了人工内存管理所带来的内存泄漏、指针 悬挂和内存碎片等潜在的危险，从而不仅在很大程度上减轻了程序员的工作复杂 度，而且降低了软件设计中人工内存管理带来的系统错误，提高了系统安全性， 特别对于大规模软件开发提高了开发效率，加快了软件产品的生产周期。随着嵌 入式实时系统的快速增长，嵌入式软件规模和复杂度也迅速增加，人们自然希望 能将具有如此优点的垃圾搜集器应用于嵌入式软件的开发设计中，从而提高嵌入 式实时系统的开发效率和安全性。然而，由于嵌入式实时系统具有实时性的特点， 这就要求垃圾搜集器在完成垃圾搜集任务的条件下，还需要保证系统中实时任务 满足其时限要求，而垃圾搜集器的运行本身就需要占用一定的时间开销，另一方 面，嵌入式实时系统往往运行在资源有限的环境中，考虑到还需要尽可能降低资 源开销，使得开发出满足实时系统要求的实时垃圾搜集器面临着许多困难。 本文致力于垃圾搜集器的实时化性能研究，在保证垃圾搜集器满足实时任务 特别是硬实时任务的时限要求条件下，尽可能减小对嵌入式实时系统有限资源特 5 电子科技大学博士学位论文 别是内存资源的占用，并研究了分布式实时垃圾搜集器的算法，使实时g c 性能更 佳，更适合于大规模系统的开发。本文的研究成果对于在不远的将来把实时垃圾 搜集器应用于大规模嵌入式实时系统软件的开发，提高嵌入式实时软件开发的效 率，缩短开发周期，提高系统安全可靠性方面具有重要的意义。 1 3 国内外研究现状 由于实时系统在航空航天领域有着非常广泛的应用，随着j a v a 在大型软件开 发领域的巨大发展，近年来实时j a v a 在航空航天领域的应用研究也日渐兴起，其 中具有代表性的是以下两个项目。 一是美国卡内基美隆大学同s u n m i c r o s y s t e m s 公司、t i m e s y s 公司以及n a s a 的“喷气推进实验室( j e tp r o p u l s i o nl a b o r a t o r i e s ，简称为j p l ) 的共同合作项目 “g o l d e n g a t e ”。该项目从2 0 0 3 年1 月启动，用实时j a v a 为开发平台，实现和已 发射上天的“火星流浪者 相似的开发原型，目的是为了证明j a v a 的飞行价值， 评估实时j a v a 是否可以满足航天系统的实时要求。该项目的系统平台如图1 3 所 示。 a p p l i c a t i o n s r t s j ( r e a l - t i m es p e c i f i c a t i o nf o r j a v a ) r t l i n u x h a r d w a r e 图1 - 3g o l d e n g a t e 项目系统软件平台 另一个项目“a r c h i t e c t u r ef o re n h a n c e dr e p r o g r a m m a b i l i t ya n do p e r a b i l i t y ( a e r o ) 是欧洲太空总署联合a s t r i u m 、a i c a sg m b h 和l i n k o p i n g 大学等机构共 同建立的，该项目同样基于实时j a v a ，开发面向卫星应用的软件开发平台。项目 使用实时j a v a 虚拟机a e r o v m 为所有的j a v a 操作提供硬实时保障。 事实上，从j a v a 语言发布不久，实时j a v a 的概念就已经被提出，不过直到9 8 年才出现第一款比较有影响力的实时j a 、，a 产品，臣l l p e r cj v m 5 1 。1 9 9 9 年， g r e g b o l l e l a 带领的实时j a v a 专家组制定出实时j a v a 规范( r t s j ) 的初版【6 1 ，并于2 0 0 1 年正式发布1 0 版本。之后，出现了一些符合r t s j 规范的实时j a v a 平台，女n j r a t e t t l ， o v m ，f l e x 8 1 ，j a m a i c av m 9 】，a n dm a c k i n a c ，而分布式实时j a v a 的研究刚处于起步阶 6 第一章绪论 段，目前仅有少数人在此方面做了一些工作【l 2 1 。相比之下，国内在这个领域的 研究还非常少，仅有少数几篇文章涉及实时j a v a 的范畴【1 3 1 卯。 实时j a v a 采用基于区域的内存管理方式，把内存分为若干个区域即堆内存， 作用域内存和永久内存。垃圾搜集器仅仅检测并回收堆内存中的对象，永久内存 从不被回收。作用域内存由实时任务使用，只有在全部实时任务完成后才被整体 回收。r t s j 的存储管理模式有许多缺陷，其模型太复杂，对程序员提出了很多要 求和限制，例如程序员需要指定实时任务使用的内存空间，还要防止指针在不同 区域间的引用超出某些限制。这种基于区域的策略需要随时检查不同区域间对象 引用的合法性，会带来很多额外的开销，即使有一些努力试图减少这种开销【1 6 ，1 7 】， 但效果并不明显。因此，基于r t s j 的上述缺陷，许多研究人员都认为一个设计优 良的实时垃圾搜集器应当是更好的选择。 由于最早的g c 在运行时需要暂停系统所有任务的运行，直到g c 完成其工作， 这显然不适合实时系统，为此渐进式g c 算法被提出，其中b a k d l 8 】的渐进式垃圾搜 集器代表了传统的实时g c 。他采用了拷贝算法，并把g c 的工作分成很多小片段与 实时任务交替运行。这样，g c 的执行不会使实时任务的执行中断，从而保证任务 的实时性。然而，由于g c 工作是由任务分配内存或指针操作触发的，这种方式又 被称为基于工作的g c ，虽然单个片段的g c 操作所占用的处理器时间很短，但如果 许多内存或指针操作集中在一起，累积起来的g c 执行时间就会过长，从而可能导 致实时任务超过时限。因此，这种基于工作的g c 只适合于软实时系统，无法严格 保证硬实时系统任务的时限要求。 为了满足硬实时系统严格的时限要求，人们开始考虑把g c 当作一个单独的任 务参与调度，以保证实时任务的执行时间。h e n r i k s s o n 0 9 】提出了半调度策略。当系 统中没有硬实时任务运行时，g c 才运行，这样就可以保证硬实时任务的时限要求。 然而这种算法需要较高的系统内存需求。 近十年来，人们提出了可以保证硬实时任务时限的g c 模型，称为基于时间的 g c 。g c 被作为一个单独的实时任务参与调度，g c 的执行不再由任务的操作触发， 而在系统分配的时间片内执行。具有代表性的主要有以下几种算法，b a c o n 2 0 , 2 1 1 等人提出了一种基于最小任务利用率【翻的渐进的标记清除算法。k i m l 2 3 】等人设计 了一种基于非周期任务服务器的调度算法，该算法利用实时系统中经典的非周期 服务器策略，使用非周期服务器提供的时间片来执行g c ，并使其优先权最高。 r o b e r t z 2 4 】等人提出了时间触发的g c ，g c 只有一个必要的参数就是时限，也只有 时限可以控制g c 的执行过程，因此，他的算法可以动态调整时限，具有较好的可 7 电子科技大学博士学位论文 移植性。 分布式系统由许多结点组成，分布式垃圾搜集器更加复杂【2 ”5 1 ，并且分布式 系统中影响实时性的因素很多，例如消息传递的时间花费的不确定性使分布式g c 的实时化变得更为复杂，其中具有代表性的是r u d a h c s 【3 6 提出的实时分布式g c 模 型，他的模型基于拷贝算法。事实上，由于在他的算法中，一次全局g c 的循环需 要全部结点的本地g c 依次完成后才能结束，因此如果结点数较多，全局g c 的执行 时间就会过长，从而导致某些结点中的内存可能耗尽，因此，r u d a l i c s 的算法也不 适合于大规模分布式系统。l 趾d 3 4 】等人提出了分组分布式g c 策略，把系统结点分 为若干组进行并发处理，该算法具有一定的容错性，也能较快回收小规模的分布 式垃圾，但对于跨多个结点的大型分布式垃圾回收效率较低，系统开销也大。 f e s s a n t 3 习和r y u 【3 7 】提出了基于时间戳的分布式垃圾搜集器，也可以回收全部垃圾， 且具有容错性，然而它们回收分布式循环垃圾( c y c l i cg a r b a g e ) 的延迟时间难以确 定。在面向对象的系统中，活动对象不仅有静态数据，还包含可执行的进程， k a f u r a 3 8 ，3 9 】和p 瑚l j t 即】都提出了面向活动对象的分布式垃圾搜集器算法，它们的全 局g c 都基于标记清除算法，因而不适用于大规模分布式系统。 1 4 本文的主要工作 本文的工作主要是在国防重点预研基金项目( 4 1 3 1 5 0 4 0 1 0 6 ) 和8 6 3 国家高技 术研究发展计划( 2 0 0 6 a a 0 1 2 1 3 7 ) 的资助下完成的。几年来，作者对单处理器实 时垃圾搜集器的性能到分布式实时垃圾搜集器进行了较为深入而系统的研究，本 文是对这些研究工作的一个总结。主要包括以下几个方面： 1 分析了垃圾搜集器的几种主要的算法，归纳了各种垃圾搜集器算法的优点 和缺点，总结了实时垃圾搜集器发展演变的历程； 2 分析了实时垃圾搜集器的调度算法，针对硬实时系统，提出了在保证任务 实时性的前提下，减小系统内存需求量的垃圾搜集器机制； 3 分析了现有的混杂垃圾搜集器算法，结合实时调度提出了利用混杂垃圾搜 集器进一步降低系统内存需求的算法； 4 分析了现有的各种分布式垃圾搜集器算法，提出了一种基于关键引用验证 的分布式垃圾搜集器算法，该算法可以及时回收循环垃圾，适合于大规模 分布式系统； 5 研究了面向活动对象的分布式垃圾搜集器，并提出了一种简化的算法。 第一章绪论 1 5 本文的组织 本论文由六个章节组成，各章安排组织如下： 第一章绪论 本章首先对本文的研究背景和技术背景知识进行了介绍，阐述了实时垃圾搜集 器的概念，指出了对实时垃圾搜集器的研究目的及其对大规模实时软件的开发所 具有的重要研究意义，然后对国内外的相关研究工作进行了概述，最后简要介绍 了本文的主要工作。 第二章实时垃圾搜集器的发展 本章首先介绍了拷贝算法、引用计数算法和标记清除算法这几种主要的垃圾搜 集算法，接下来介绍了最早期的暂停系统的垃圾搜集器，接着出现的适合软实时 的渐进式垃圾搜集器，也被称为基于工作的垃圾搜集器。接着介绍了近年来从基 于工作的垃圾搜集器到基于时间的垃圾搜集器的演变，并介绍了几种代表性的基 于时间的并发垃圾搜集器算法。 第三章实时垃圾搜集器的调度策略 本章在对几种主要的实时垃圾搜集器的调度策略进行分析的基础上，特别是详 细分析了k i m 所提出的调度算法，提出了合理配置参数降低内存需求的策略，并 在实验中证实与k i m 的算法相比该策略在减小内存需求的性能上更佳。本章还从 另一角度提出用动态调度垃圾搜集器算法( d y n a m i cg a r b a g ec o l l e c t i o ns c h e d u l i n g 算法，简称为d g c s 算法) 可以进一步降低内存需求，并作了相应仿真。最后， 与上述基于r m 调度策略相对照，本章还分析了在任务数量有限的条件下，用e d f 调度垃圾搜集器和实时任务可以使系统内存需求更小。 第四章混杂实时垃圾搜集器策略 本章主要介绍了当前对混杂垃圾搜集器算法的一些研究成果，并在此基础上提 出了用混杂垃圾搜集器算法与实时调度相结合的策略，可以降低系统内存需求。 并提出了一种引用计数与时间戳的混杂垃圾搜集器算法，比较适合于大规模系统。 第五章分布式实时垃圾搜集器 本章首先介绍了目前分布式垃圾搜集器的研究现状，在此基础上提出了一种基 于关键引用验证的分布式垃圾搜集器算法( v e r i f i c a t i o no f c r i t i c a lr e f e r e n c e 算法， 简称为v c r 算法) ，并对该算法作了详细的分析和说明，与以往的分布式垃圾搜 集器算法相比，该算法可以在最短时间内回收循环垃圾，适用于大规模分布式系 统，综合性能更优。另外，本章还介绍了面向活动对象的分布式垃圾搜集器与一 9 电子科技大学博士学位论文 般的垃圾搜集器的区别，并提出了一种混杂的面向活动对象的垃圾搜集器算法。 第六章全文总结 本章对全文的内容进行总结，指出了本文工作的创新之处和不足之处，并对 本文相关研究内容的下一步工作和未来研究方向也提出了意见。 1 0 第二章实时垃圾搜集器的发展 第二章实时垃圾搜集器的发展 用垃圾搜集器自动管理内存，可以避免人工管理内存所导致的内存泄漏和指 针悬挂等错误，最早的垃圾搜集器是不具备实时性的暂停全局g c ，而后出现了具 有软实时性的渐进式g c ，为了满足硬实时任务的时限要求，近年来出现了基于时 间的g c 。 本章介绍了实时垃圾搜集器的发展历程，首先介绍了几种主要的垃圾搜集器 算法，接着介绍了渐进式垃圾搜集器，最后介绍了几种典型的具有硬实时特性的 基于时间的垃圾搜集器算法。 2 1 几种主要的垃圾搜集器算法 垃圾搜集器算法主要分为引用计数算法( r e f e r e n c ec o u n t i n g ) 和追踪类算法 ( t r a c i n g ) ，而追踪类算法又分为标记清除算法( m a r k - s w e e p ) 和拷贝算法( c o p y i n g ) ， 本节中主要对这三种垃圾搜集器算法作了大致介绍。 另外，在多数程序语言中，大多数对象生存时间较短，少数对象生存时间较 长，基于这个事实，文献 4 1 4 6 提出了基于年代的垃圾搜集器。内存空间被分为 若干个区域【4 7 】，分别存放生存期不同的对象。由于新老区域的g c 操作不同，为 识别区域间的指针，需要有一个写屏蔽对指针进行检查【4 3 ，4 1 1 。由于最坏响应时 间难以确定，因此基于年代的g c 不适合于硬实时系统，在本文中不作详细讨论。 2 1 1 标记清除算法 标记清除算法和下一节要介绍的拷贝算法都属于追踪类算法【5 2 1 ，追踪类算法 是指垃圾搜集器从一组根节点开始，依次遍历所有可到达和不可到达的对象，从 而判断哪些是活动对象，哪些是垃圾的算法类。 第一个标记清除算法发表在文献 5 3 d p 。标