Java中作用域内存的程序插装与运行时

理论计算机科学电子笔记113（2005）105-121www.elsevier.com/locate/entcsJava中作用域内存的程序插装与运行时D. 加伯韦茨基角Nakhli2 S.约维因3HZorgati4摘要提出了一种分析、监控Java动态内存分配的方法。它首先包括执行指针和转义分析来检测内存范围。这些信息用于自动地对Java程序进行插装，从而通过基于区域的内存管理器来分配和释放内存。我们的源代码仪表充分利用范围分析的结果，通过动态映射分配的地方，在运行时通过注册机制的区域堆栈。此外，它允许使用不同的作用域内存管理器实现来执行相同的转换后的程序，并在不更改转换后的代码的情况下执行不同的运行时分析。特别是，我们考虑一类管理器，处理由固定大小的内存块组成的可变大小的区域，我们为区域内和区域间的碎片化提供分析模型。这些模型可用于在运行时观察和控制碎片，开销可以忽略不计我们描述了一个原型工具，实现我们的方法。关键词：Java，内存管理，运行时分析，实时和嵌入式系统。1介绍嵌入式和实时软件行业的当前趋势是领先的-使用面向对象的编程语言，如Java。从软件工程的角度来看，1阿根廷布宜诺斯艾利斯大学计算机科学学院。电子邮件：diegog@dc.uba.ar。部分由项目ANCyT资助PICT 11738和IBM Eclipse创新资助。2Verimag，France. 电子邮件：chaker. imag.fr。3法国VERIMAG。电子邮件：sergio. imag.fr。D YNAMO（Min. Resear ch，France）和MADEJA（RhoCogne-Alpes，France）。4法 国 VERIMAG和突尼斯大学计算机科学系。电邮地址：hichem . imag.fr。1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.01.031106D. Garbervetsky等人理论计算机科学电子笔记113（2005）105在面向对象的设计中，最重要的是将抽象封装到通过明确定义的接口进行通信的对象中。由于程序员控制的内存管理抑制了模块化，面向对象的语言，如Java，提供了内置的垃圾收集[15]（GC），即在程序最后一次使用后自动回收堆分配的存储然而，在实时嵌入式系统中没有使用自动内存管理。其主要原因是，具有动态内存回收的软件的时间行为是非常难以预测的。针对实时嵌入式应用，已经提出了几种GC算法。例如，[12]提出在执行低优先级任务期间使用增量复制算法[6]。 为了确保高优先级任务不会耗尽内存，必须预先分配足够的存储空间。此外，垃圾收集时间在低优先级任务之间的共享并不明显。[18]将增量标记和清除算法用于JVM，该JVM将对象分配为小内存块的集合。该算法的不足之处在于，每个分配块所需的增量数量取决于整个可达内存的大小。 [16]适应经典的引用计数算法[7]。它的响应时间取决于在必须收集非引用循环时可访问对象的总数。 [13]提出了一个适应的picoJava-II硬件实现[11]第11章：我的女人 这种方法是不可移植的，它不能确保可预测的执行时间。为了克服当前GC算法的缺点，RTSJ [4]提出了一个基于“作用域内存”概念的内存管理API这个想法是在与计算单元（方法或线程）的生命周期相关联的区域[10，19]中分配对象。 区域在以下情况下被释放 相应的单位完成其执行。然而，确定对象的范围是困难的。因此，使用RTSJ API编程容易出错。 为了避免直接使用RTSJ API，[9]建议自动编译Java程序，并通过调用RTSJ作用域内存API来替换（只要可能）Java新语句。这样做需要分析程序以确定动态分配对象的生存期。它们的方法基于引用的加权图，其中节点是分配点，弧表示点到关系，权重对应于调用链中的深度。粗略地说，权重与作用域相关联，并且动态编程用于最小化权重，即，将任何分配点绑定到对象的分配点的最小深度，transitively指向在前者创建的某个对象[9]为求方便起见，使用了一个profiler。因此，不能保证图在所有可能的情况下都过度近似对象的可能引用D. Garbervetsky等人理论计算机科学电子笔记113（2005）105107Ble跑步。因此，不一定遵守作用域内存规则，该规则强制由API实现执行相应的运行时检查，并具有隐含的运行时开销。此外，仪器是这样的，每个创建站点被静态地分配给固定区域。 这种技术可以使物体的寿命大大超过需要的时间。在这里，我们提出了一种方法，试图解决这两个问题。 第一步是将指针和转义分析技术[3，8，17]应用于程序以合成作用域。使用指针和转义分析，可以保守地确定对象是“转义”还是被方法“捕获”直观地说，当一个对象的生存期比方法的生存期长时，它会转义方法，所以当方法完成它的转义时，它不能被收集。 当可以安全地收集对象时，该方法将捕获该对象在其执行结束时。基于上述信息，我们合成了一个内存组织，该组织将内存区域与每个方法相关联，以这种方式，由作用域内存管理方案施加的限制通过执行来实现。因此，可以安全地消除运行时检查以提高性能。为了检测程序，我们定义了一个API，它避免了RTSJ在每次创建新的内存作用域时创建一个可运行对象的开销我们的仪器充分利用的范围分析的结果，通过动态映射创建网站的区域堆栈在运行时通过注册机制。这允许在运行时根据给定的性能标准（例如，最小化存储器碎片），而不改变源代码级插装。我们还解决了监控和评估运行时性能的作用域内存管理器的问题。在本文中，我们专注于基于区域的内存管理器，它处理由固定大小的内存块组成的可变大小区域。对于这类管理器，我们提供了几种分配算法的区域内和区域间碎片化的分析模型（例如，第一适合和最适合）。这些模型可用于在运行时观察和控制碎片，开销可以忽略不计。运行时分析还允许调整参数以适应程序的需要最后，我们描述了一个原型工具，实现我们的方法。2预赛在[17]之后，我们定义一个程序为一个集合{m0，m1，. . 的方法。方法m有一个参数列表Pm。每个语句都用一个标签=def方法×N来标识，它唯一地表征了它的位置。方法m的调用图是有向图CGm=，其中108D. Garbervetsky等人理论计算机科学电子笔记113（2005）105∈∈××∈N=方法表示程序方法，E =（方法标签方法）表示调用关系。（c，l，m）E表示方法c在位置l调用方法m。我们假设我们可以在编译时为每个调用确定将调用哪个方法，不能有多个可能的可调用方法。支持继承和后期绑定超出了本工作的范围由于目前我们不处理递归程序，因此可以通过展开调用图来获得有限的调用树CTm=。此展开是通过克隆具有多个父节点的节点来完成的N=M方法CT=Label+×M方法表示从根节点开始的路径，E=（方法CT×Label×方法CT）设 α ∈Labe l+.Letα =αJ.i ， i∈N ， 我 们 定 义 t rim （ α ） =αJ.Letl∈Label使得α = α1.l. α2，且l不出现在α i 中，i = 1，2.我们定义n（α，l）=α1.l，suff（α，l）=l.α2. 我们定义last（α.l）=l，first（l. α） =1。Label+on到M方法的投影m th（）是递归的定义为mth（m.i）=m和mth（α. m. i）=mth（α）.m。这些操作自然地扩展到调用树的节点。我们定义路径（CTm）为CTm 的路径集合，predm（ρ）为CTm的子树，由所有形式为ρJ.mth（first（ρ））的路，使得ρJ.ρ∈路（CTm）。控制流图（CFG）是有向图G=其中N是节点的集合，E是边的集合。入口和出口是指示唯一开始和结束点的特殊节点。给定一个方法m，Gm是m的CFG，它传递地包含m调用的每个方法的CFG。每个节点n N对应一个语句，并有一个标签标签l+。请注意，由于每次调用方法时都会在控制流程图中进行宏扩展，因此标签由CT m中的相应路径及其相对位置组成。按照惯例，m是主要的方法.因此，Gm0是程序的控制流程图，CTm0是它的调用树.我们把程序中创建对象的每一个地方（由Labe l +定义）（即有一个new或一个newA语句）称为C r e ation Site。为了简单起见，我们假设new语句只创建对象实例。构造函数被假定为单独调用对构造函数的调用被处理就像其他方法调用一样。CSm表示从方法m控制流程图的入口点可到达的创建站点的集合我们将 调 用 程 序 中 每 一 个 有 方 法 调 用 的 地 方 （由Label+ 定 义 ）。Callsm表示Gm中的方法调用的集合。例2.1在图1中，我们给出了一个激励性的例子。方法m0的调用图和调用树如图2所示。我们示例中每个方法的创建站点是：D. Garbervetsky等人理论计算机科学电子笔记113（2005）105109public int findDuplicate（intfindDuplicate）{1：RefO h = new RefO（）;2：Object[] a = m1（mc）;3：Object[] e = m2（2*mc，h）;}public int findDuplicate（int[] nums）{3：Object[]f= newAObject[n]4：for（j=1;j =n;j++）{5：if（j% 3 == 0）{6：c = newA [j*2+1];}一曰：整数i;否则{第二章：intn = new int n（）;第七章：c =new;第三章：Object[] b =newA Object[k];}第四章：for（i=1;i =k;i++）{第八章：[4];第五章：b[i-1]= m2（i，l）;第九章：s.ref= d;}第十章：f[j-1]= c;第六章：Object[] c = newA[9];}第七章：返回b;十一：return f;}}publicint findDuplicate（int []nums）{2：对象c、d;class RefO {public Object ref;}Fig. 1. 激励的例子110D. Garbervetsky等人理论计算机科学电子笔记113（2005）105{图二、建议示例中方法m的调用图和调用树CS m0=m 0。1， m0。2.m 1。2，m 0. 2.m 1。3，m0. 2.m 1。5.m2。3,m 0. 2.m 1。5.m2。6，m 0. 2.m 1。5.m2。7， m 0.2.m 1。5.m2。8,m 0. 2.m 1。6，m 0. 3.m 2。3，m 0. 3.m 2。3，m 0. 3.m 2。6，m 0. 3.m 2。7，m 0. 3.m 2。8}CS m1={m1. 3，m 1。5.m2。3，m 1。5.m2。6，m 1。5.m2。7，m 1。5.m2。8，m 1。（六）CS m2={m2. 3，m 2。6，m 2。7，m 2。8}我们示例中每个方法的调用位置是：D. Garbervetsky等人理论计算机科学电子笔记113（2005）105111调用m0={m 0. 2，m 0. （3）调用m1={m1. （五）调用m2={}Q3作用域内存管理在Java的实时规范（RTSJ）[4]中，作用域内存管理是基于在与可运行对象的生命周期相关联的区域中分配对象的思想。 这种方法对对象相互引用的方式施加了限制，以避免出现悬空引用。一个对象o1，属于一个区域r，只有当以下条件之一成立时，才能指向另一个对象o2：o2属于r;o 2属于一个当r是活动的时是活动的区域;o 2在堆中;o 2在在不朽的（或静态的）记忆中。 对象o1不能指向对象o2在区域r如果：o1在堆中;o 1在不朽内存中;r在o1在运行时，区域活动与计算单元（例如，方法或线程）。在单线程程序中，每个区域与一个方法相关联，存在一个区域堆栈，其中活动区域的数量和顺序与调用堆栈中每个方法的外观完全对应。在多线程程序中，区域与线程和方法相关联，有一个区域树，其分支与每个执行线程相关。在本文中，我们假设线程不共享区域，即线程只通过不朽内存进行交互[4]。使用作用域内存管理进行编程是困难且容易出错的。一种解决方案是静态地检查程序是否满足上述限制。 这种方法在[10]中得到了遵循，其中提出了一个类型系统。 在这里，我们建议通过静态分析来自动推断作用域，并通过适当的基于区域的分配来自动检测程序，这样，作用域内存管理方案所施加的限制就可以通过构造来实现。3.1推断作用域为了推断作用域信息，我们使用指针和转义分析[3，8，17]。这是一种静态分析技术，可以发现对象本身之间以及对象和方法之间的关系。它已被用于几个应用，如同步删除，消除运行时112D. Garbervetsky等人理论计算机科学电子笔记113（2005）105→→检查、堆栈和作用域分配等。在这里，我们感兴趣的是保守地确定一个对象是当对象的生存期长于方法的生存期时，对象将转义方法设escape：MethodP（CreationSite）为返回转义的创建站点的函数一种方法。 当一个对象在方法执行结束时可以被安全地收集时，它就被方法捕获了。设capture：MethodP（CreationSite）为返回由方法捕获的创建站点的函数。图3.第三章。 逃逸分析为创建网站m 0. 1，m 1. 2，m 1。3，m 2。3，m 2。6和m 2。8为了简单起见，我们在这里不解释这两个函数是如何计算的。感兴趣的读者可以参考[3，8，17]。相反，我们使用我们的例子来说明该技术。例3.1逃逸并被捕获的创建点如下：return（m）={}escape（m 1）={m 1. 3，m 1。5.m2。3，m 1。5.m2。6，m 1。5.m2。（七）escape（m 2）={m 2. 3，m 2。6，m 2。7，m 2。8}D. Garbervetsky等人理论计算机科学电子笔记113（2005）105113{capture（m 0）=m0. 2.m 1。3，m 0. 2.m 1。5.m2。3，m0. 2.m 1。5.m2。6,m 0. 2.m 1。5.m2。7，m 0. 3.m 2。3，m 0. 3.m 2。6，m 0.3.m 2。7，m0. 3.m 2。8}capture（m 1）={m 1. 5.m2。8，m 1。（六）capture（m2）={}让我们考虑几个案例。例如，m 1。3从m1逃脱。这是因为M1。3是分配给b的对象的创建位置（在图3中表示为从节点b到节点m 1的双向弧）。3），它由方法m1返回（因此从m1逃逸）（描述为从b到标记的RV5）。创作地点m 2。3从m2逃脱。这是因为m2的第6行中分配的内存首先被c引用，然后被一个条目引用f（第11行），由m2返回。 因为当m 1在第5行调用m 2时，返回的对象被分配给b的一个条目，并且b由m 1返回，所以我们有m 1。5.m2。六次逃脱。另外，m 0. 2.m 1。5.m2。6被m0捕获。是的，M2。8从m2逃逸，因为分配的内存由s引用，s作为参数传递给m2，但是，在这种情况下，创建站点由m1和m0捕获，这取决于相应的调用链。Q设m是一个方法，l∈Callsm，我们定义：register（l）={last（cs）|cs∈capture（mth（l））先捕获（cs）= l}示例3.2在示例中注册到调用站点的创建站点如下：寄存器（m 0. 2）={m 1. 3，m 2。3，m 2。6，m 2。（七）寄存器（m 0. 3）={m 2. 3，m 2。6，m 2。7，m 2。8}寄存器（m 1. 5）={m 2. 8}Q3.2合成内存区域基于上述信息，我们可以合成一个内存组织，它将内存区域rm与每个方法m相关联，以满足作用域内存管理方案所施加的限制。逃逸分析的性质确保了由方法m捕获的创建点分配的对象的生命周期不超过M本身。也就是说，m所捕获的对象不能被调用m的方法（传递地）所捕获的对象所指向。因此，引用的内存可以在m终止后安全地回收。5rv代表返回值。114D. Garbervetsky等人理论计算机科学电子笔记113（2005）105∈∈设cs是一个创建站点，m是一个方法，使得cs捕获（m），即m=mth（first（cs））。我们定义reclaim（cs）为程序调用树的子树，该调用树由以cs为su的路径组成，即：reclaim（cs）=predm0（trim（cs））={φ（ρ，m）|ρ ∈ paths（CT m0）trim（cs）= suff（ρ，m）}换句话说，mth（ρ）是一个调用堆栈，mth（（ρ，m））是堆栈中包含所有方法的部分，在这些方法中可以安全地分配cs所需的内存。如果在方法n的第i行分配对象o，其中n.i=last（cs），当调用栈为mth（ρ）时，则o可以安全地分配在任何区域rmJ中，其中mJ出现在调用堆栈的前缀中，直到方法m。3.3API和程序转换为了在程序级执行作用域内存管理，我们提出了一个API，它与[2，4]中描述的RTSJ API有两个主要的区别。首先，在我们的API中，内存作用域没有绑定到可运行对象。 在这一点上，我们的API更接近于RC库[10]。 第二，API不指定分配对象的唯一区域，而是一组与调用堆栈的前缀中的方法对应的区域。在运行时分配对象的实际区域被排除在实现之外。我们将在下一节讨论这个问题。API见表1。输入（r）将r推入区域堆栈结束（）收集顶部区域current（）返回顶部区域determineAllocationSite（CS）在CSnewInstance（l，c）创建一个C类对象newAInstance（l，c，n）相同，但对于维数为n的数组表1作用域内存API。程序转换如下。 让m成为一个方法。• 对enter（rm）和exit的调用插入在方法的开头和结尾。• 设l=m.i Label为新C（resp. newA C[n]）语句。第i行中的语句被替换为对newInstance（l，c）的调用（resp. ne w I n s t a n c e （l，c，n））。D. Garbervetsky等人理论计算机科学电子笔记113（2005）105115∈∈• 回想一下，在分析中通过调用树中的路径来区分创建位点。由于标签为l的newInstance只携带l作为参数，而不是调用链，因此需要动态更改捕获信息，以便能够在运行时计算reclaim（）。为此，我们将一个方法捕获的创建站点集注册到对应的呼叫站点。 设l为m =mth（l）。如果reg是ter（l）n，则todetermineAllocationSite（register（l））插入在l之前。因此，在newInstance（l，c）处，其中mth（l）=m，我们有<$（ρ，m）reclaim（cs）i <$σ=mth（ρ）是调用堆栈，并且last（cs）register（l）。因此，对象实例可以分配在 σ（σ，m）。示例3.3表2显示了示例的插装代码。Q3.4代码检测的属性在[9]中提出的使用RTSJ API [4]的插装中，每个创建站点通过在分配位置使用RTSJ方法getOuterScope（）直接访问外部作用域来静态分配给固定区域这意味着，当一个创建站点被不同的方法（在不同的调用链中）捕获时，推断的作用域必然是与更接近调用树的根的捕获方法相对应的作用域。因此，这种方法倾向于生成更大尺寸的更少区域，特别是在调用树根附近，从而最大化对象相反，我们的插装充分利用了调用链方面的范围分析的结果，通过注册机制在运行时动态地将创建站点映射到区域堆栈分配对象的实际区域由实现确定。一种可能的策略是，总是在捕获对象的方法的区域中分配对象这种策略产生的区域的大小往往是更大的调用树的叶子，也就是说，那些方法具有较短的生命周期，而不是接近根。换句话说，它最小化了已分配内存的生存期。例3.4例如，考虑生成点m 2. 8在我们的例子中（见图3）。[9]的插装将始终在与方法m0相关联的区域r0我们的配置将动态地选择分配内存区域r0或r1内，这取决于调用者m0或m1，分别。Q我们的方法允许使用不同的作用域内存管理器实现来执行相同的转换程序。 特别是，我们的API可以116D. Garbervetsky等人理论计算机科学电子笔记113（2005）105类RegisterExample{final static String[]m0_2= {“m1_3” ， “m2_3” ， “m2_6” ，“m2_7”}; final static String[]m0_3= {“m2_3” ， “m2_6” ，“m2_7”，“m2_8”}; final static String[]m1_5= {“m2_8”};}public intfindDuplicate（intfindDuplicate）{System. out. println（new System. out. println（））;RefO h =（RefO）ScopedMemory.newAInstance（“m0_3”，RefO.class，1）; Object[]a; ScopedMemory.determineAllocationSite（RegisterExample.m0_2）;a = m1（mc）;Object[] i;ScopedMemory.determineAllocationSite（RegisterExample.m0_3）; e = m2（2 * mc，h）;System. out. println（）;}public int findDuplicate（int [] nums）{intfindDuplicate（“nums”）; intfindDuplicate（“nums”）;RefOl =（RefO）ScopedMemory.newAInstance（“m1_2”，RefO. class，1）;Objectb[]=（Object[]）ScopedMemory.newAInstance（“m1_3”，Object[].class，k）;for（i=1;i<=k;i++）{i = m2（i，l）;b[i-}System. out. println（）;返回b;}int [] m2（intn， ints）{ScopedMemory.enter（new Region（“m2”））;intj;Object[]f=（Object[]）ScopedMemory.newAInstance（“m2_3”，Object[].class，n）;for（j=1;j<=n;j++）{if（j%3）{C =（C []） ScopedMemory.newAInstance（“m2_6”，C [].class，j* 2 +1）;}否则{c =（m2_7） ScopedMemory.newAInstance（“m2_7”，m2_7 [].class，1）;}d =（m2_8） ScopedMemory.newAInstance（“m2_8”，m2_8].class，4）;s.ref =d;f[j -1]=c;}ScopedMemory.exit（）;returnf;}表2示例的插装代码直接在RTSJ和RC提出的建议之上实施。所有这些实例化在功能上都是等效的。然而，它们可能会表现出不同的性能相对于不同的定量参数，如区域大小，分配时间和内存碎片。在下一节中，我们将讨论几种可能的实现，并重点分析碎片问题。D. Garbervetsky等人理论计算机科学电子笔记113（2005）105117我我关于我们⎨4运行时分析在本节中，我们将描述一个框架，用于分析不同的基于区域的内存分配算法在运行时的行为，这些算法可用于实现作用域内存API。特别是，我们考虑处理由固定大小的内存块组成的可变大小区域的分配算法。这些算法通常管理块的链表，其中根据第一或最佳策略分配对象[20]。前者将对象分配到第一个块中，那里有足够的空间。后者搜索具有最小可用空间的块。这些算法的兴趣在于分配时间在块的数量上是线性的，而区域删除在分配对象的数量上是线性的（因为调用方法然而，他们介绍内存碎片，即（暂时）不可用的空闲内存的漏洞。预测一个区域中的区块和物体的数量是困难的，本文的范围。在[5]中描述了用于过度近似这些数字的静态分析技术。在这里，我们专注于分析的问题，分析内存碎片的分配算法的运行时行为。4.1区域内碎片化如果下一次分配满足以下条件，则在一系列分配之后区域的未使用空间被视为(1) 没有一个空片段大于要分配的对象的大小，并且需要向该区域添加新的内存块，并且(2) 空的空间的总量大于对象的大小。现在，设ω=o1···o n是要在区域中分配的对象序列。我们用R表示该区域的块集，用R i表示在分配对象o i之前与该区域相关联的块集。 序列R1，···，Rn+1的计算如下。初始时，R1=B1。假设R i是B1，. B mi.设freek是块Bk中的空空间，Ki是具有足够空空间来分配对象oi的块的索引的集合，即，K i={k ∈ [1，m i] |free k− size（o i）≥ 0}。然后，Ri+1 =<$Ri<${Bmi+1}如果Ki=1，否则，我会。[6]如果通过静态分析消除了对finalizer的调用，则成本可以保持不变118D. Garbervetsky等人理论计算机科学电子笔记113（2005）105一期+1一期+1免费的⎨≤我我k∈[1，mi]我我我设“i”是K i上的全序，它给出了根据搜索策略具有足够空间来分配o i的R i块的排序。例如，对于first-fit，“i”使得a“i b i ≤ a ≤ b，对于所有a，b ∈ Ki，而对于best-fit，“i”使得a“i b i ≤ free a ≤ free b，对于所有a，b ∈ Ki。自由k的值计算如下。最初，free1=size（B1）。为我i≥1，若Ki≥1，1freek−size（oi）ifk=minGKi，如果Ki=0，freek=I游离钾我否则，游离钾=size（Bk）−size（oi）ifk=mi+1，我们定义freei=Ki自由湾否则，请执行以下操作。设f（R，ω）为ω产生的R的区域内碎裂。它是序列f1，···，fn，使得：f=无约束iifKi=无约束i−size（oi）≥0000元，否则4.2区域间碎片化实际分配对象的区域由区域间分配策略选择.这里我们考虑三种可能的方法：（1）总是在捕获方法之一中分配（即，到注册创建站点的方法）;（2）在（调用堆栈的）前缀中的第一个区域中向后分配，其中有足够的空闲空间用于对象（区域间第一适合）;（3）在（调用堆栈的相应前缀中）留下最小可能剩余空间的区域中分配（区域间最佳适合）。令r=R mi1. R mip是与创建站点相关联的区域堆栈的前缀。当在Γ中分配新对象需要分配时，Γ中未使用的内存被认为是“区域间碎片”。一个新的内存块到某个区域R mij，1 ≤j≤ p，而有足够的在某些其它区域Rmik，1j中的连续自由空间创建的对象。k≤p，对于新D. Garbervetsky等人理论计算机科学电子笔记113（2005）105119由ω产生的Γ的区域间碎裂，记为F（Γ，ω），可以类似于f（R，ω）来定义。5原型工具我们已经开发了一个软件原型，它提供了几乎完全自动的工具支持，通过我们的API将Java程序转换为具有受控内存管理的程序，并分析其运行时行为的不同分配算法。图4显示了该工具的结构。见图4。 工具套件为了生成转换后的程序，我们进行如下操作。我们首先使用FlexHarpoon计数器[1]进行逃逸分析。Flex的输出用于计算捕获函数。我们已经开发了一个Eclipse插件，它将原始程序和捕获函数作为输入，遍历程序的语法树，并生成转换后的程序。转换后的代码可以很容易地集成到测试套件中， 提供了一个软件平台（Java类），其中包含用于执行程序的适当包装器。测试平台通过使用上一节中介绍的碎片模型模拟不同内存分配算法的行为。这些类的开发方式使得它们可以以多种方式进行参数化，特别是通过不同的分配策略、内存块分析的输出以JChart库实现的图表形式给出。图5显示了对于给定的块大小和区域内分配策略，由转换程序的单次运行产生的区域内片段化。X轴表示存储器访问的序列，120D. Garbervetsky等人理论计算机科学电子笔记113（2005）105是对象分配。y轴示出了区域内碎片化比率，即，总区域内碎片化的百分比（即， 所有区域的总和）表示所有区域中分配的内存总量。 是还可以以不同的存储块大小多次运行变换后的代码，但是用于相同的分配序列。在图6中，x轴表示块大小，y轴表示所有区域上的最小、最大和平均区域内碎片化。该工具还提供了计算和输出算法执行的操作数量的功能。图五、针对给定块大小的区域内分段6结论和今后的工作我们提出了一种在源代码级的程序插装技术，它将基于堆分配的Java程序转换为具有作用域内存管理的程序。我们的方法通过构造来确保范围规则，并通过消除运行时检查来减少运行时开销。我们的仪器oembellers一个轻量级的机制，收集信息和控制内存分配在运行时。在本文中，我们重点使用它来分析不同的分配算法的内存碎片。然而，它可以用于其他目的，例如测量对象数量，区域大小，分配时间等。运行时分析的结果允许根据给定的性能标准（例如，最小化碎片比率）。应该注意的是，这可以在完全不接触转换后的程序的情况下完成。D. Garbervetsky等人理论计算机科学电子笔记113（2005）105121图六、不同块大小的最大/最小/平均区域内碎片我们目前正在RTSJ和RC API之上实现我们的API，并将其集成到TurboJ编译器中[14]。未来的工作包括扩展我们的方法来处理多线程和递归，以及[5]中给出的静态估计的运行时验证引用[1] MIT.程序分析和编译组。Flex编译器基础结构。http：//www.juex-compiler.csail.mit.edu/。[2] W. Beebee和M.里纳德 实时java的作用域内存实现 在EMSOFT 2001，卷LNCS 2211，2001年10月。[3] B.布兰切特面向对象语言的转义分析：在Java中的应用。 ACM SIGPLAN Notices，34（10）：20[4] G. Bollella和J. Gosling。Java的实时规范。Addison-Wesley Longman出版公司股份有限公司、两千[5] V. Braberman，D. Garbervetsky和S.尤文关于动态内存利用的综合参数规范。2004年提交公共行动[6] R. A.布鲁克斯在股票硬件上的实时垃圾收集中，交易数据空间以减少时间和代码空间。在LISP和函数式编程研讨会上，第256-262页。ACM Press，1984.[7] D. R.布朗布里奇组合子机的循环引用计数。函数式编程语言和计算机体系结构会议，LNCS 201，第273-288页，1985年。[8] J-D崔，M。古普塔，M。J.塞拉诺，V.C. Sreedhar和S. P. Midki 逃逸分析Java.见OOPSLA，第1-19页[9] M. Deters和R. K.塞隆自动发现实时Java的作用域内存区域。在Proc. of the 3rd Int. symposiumon Memory management，第25-35页。ACM Press，2002.122D. Garbervetsky等人理论计算机科学电子笔记113（2005）105[10] D. Gay和A.艾肯区域语言支持。 在SIGPLAN PLDI 01，第70-80页，2001中。[11] Jr. H. G.贝克跑步机：实时垃圾收集没有晕车。ACM SIGPLAN Notices，27（3）：66[12] R.亨里克森嵌入式系统中的垃圾收集调度。PhD.论文，隆德理工学院，1998年7月。[13] T. Higuera，V. Issarny，M.班戈湾Cabillic，J-Ph. Lesot，and F. 帕兰 实时Java的内存管理：使用硬件支持的高效解决方案。实时系统杂志，2002年。[14] Silicomp 研 究 所 。 Turboj.Javatonativecompiler.www.ri.silicomp.fr/adv-dvt/java/turbo/index.htm。[15] R. Jones和R.琳丝垃圾收集。自动动态内存管理算法。John Wiley and Sons，1996年。[16] T. Ritzau和P. Fritzon。减少硬实时垃圾收集中的内存开销。在EMSOFT'02，法国格勒诺布尔。LNCS 2491，2002年。[17] A. Salcianu和M.里纳德多线程程序的指针和转义分析。ACM SIGPLAN Notices，36（7）：12[18] F.西伯特在Java的非移动垃圾收集器中消除外部碎片。2000年的案例[19] M. Tofte和J-P. Talpin。基于区域的内存管理。信息与计算，1997年。[20] P. R.威尔逊，M。S. Johnstone，M. Neely和D.博尔斯 动态存储分配研究综述 和批判性评论记忆管理国际研讨会，英国苏格兰金罗斯，1995年9月。