（计算机科学与技术专业论文）jejava芯片系统对象存储管理的研究和实现.pdf

困防科学技术大学研究生院学位论史摘要i 微电子技术、软件技术和i n t e r n e t 的迅猛发展，使计算机系统的重心从原来的主机转向了网络，传统的p c 由于其体积大，价格高难以满足人们对i n t e r n e t随时随地访问的要求，能够访问i n t e r n e t 的嵌入式设备成为发展的一个热点。随着i n t e r n e t 而得到广泛使用的j a v a 已经成为网页制作中不可缺少的部分，它也是许多分布式系统软件结构的基础，它还可能成为信息设备互连标准的基础。因此支持j a v a 程序的运行是访问i n t e r n e t 的嵌入式设备应具有的一个重要功能。j e j a v a 芯片系统是我们设计的一种面向嵌入式应用并且直接支持j a v a 虚拟机指令的微处理器系统。对象存储管理是j e j a v a 芯片系统实现的关键技术之一，它主要包括三方面内容：对象的创建、垃圾回收、物理存储器的管理。，)本文首先介绍了存储管理技术和垃圾回收技术的发展现状，而后简要介绍了j e j a v a 芯片系统。在此基础之上，详细讨论了j e j a v a 芯片系统中对象存储管理系统的设计和实现。j a v a 虚拟机指令系统中有四种对象创建指令，对象创建不仅包括分配存储空间还要填写相应的数据结构，这类指令难以用硬件实现。在j e j a v a 芯片系统中采用指令自陷、调用系统例程的方法实现，空间分配等工作由存储管理中的对象创建模块完成。自动的垃圾回收是j a v a 语言的一大特色。j e j a v a 芯片系统采用三色法实现垃圾回收。为了实现精确遍历，我们提出了一种称为对放法的新的对象域组织方法，实现了对象的精确遍历；同时通过g c 点的设置，有效的减少了栈遍历时占用的内存。为了满足嵌入式系统实时性要求高的特点，系统还支持异步的垃圾回收，本文给出了实现策略。i 物理存储器的管理主要包括存储器的组织、分配和去配。结合j a v a 程序的应用特点，本文提出了弋种段式和段页式混合的存储器组织方案，并且给出了存储器分配和去配算法。本文还介绍了r o m 映像产生程序的工作过程。本文最后给出了测试结果和进一步工作的方向。【关键词】：j e - j a v a 芯片系统对象存储管理异步垃圾回收第l 页国防午斗学技术大学研究生院学位论文a b s t r a c tw i t ht h ed e v e l o p m e n to fm i c r o e l e c t r o n i c s 、s 0 1 c a r et e c h n i q u e sa n di n t e m e t ，t h ef o c u so fc o m p u t e rs y s t e mt u r n sf r o mh o s tt on e t w o r k ，c o n v e n f i o n a ip cc a l ln o tm e e tt h ed e m a n do fp e o p l et oa c c e s si n t e r n e tf r e e l yf o rb o t hi t sb u l ka n di t sc o s t l i n e s s ，e m b e d d e dd e v i c ew h i c hc a na c c e s si n t e m e tb e c o m e st h eh o t p o t j a v a ，w h i c hg r o w su pw i t ht h ed e v e l o p m e n to fi n t e r a c t ，h a sb e c o m ev i t a lp a r to fh o m e p a g e ，i ta l s ob e c o m e st h eb a s eo f s o f t w a r ea r c h i t e c t u r ei nd i s t r i b u t e ds y s t e m s ，f u r t h e r m o r ei tw i l lb et h eb a s eo fi n t e r e o n n e c t i o ns t a n d a r do fi n f o r m a t i o nd e v i c e s u p p o r t i n gt h ej a v ai so n eo ft h ei m p o r tf u n c t i o no fe m b e d d e dd e v i c et oa c c e s si n t e r n e t j e - j a v ac h i ps y s t e mi sak i n do fm i c r o p r o c e s s o rs y s t e mw h i c hc a ns u p p o r tj a v av i r t u a l i n s t r u c t i o na n db ea p p l i e di ne m b e d d e ds y s t e m o b j e c tm e m o r ym a n a g e m e n ti so n eo fk e yt e c h n i q u e si nj e j a v ac h i ps y s t e m ，i ti n c l u d e st h r e ep a r t ：o b j e c tc r e a t i o n 、g a r b a g ec o l l e c t i o n 、m e m o r ym a n a g e m e n t i nt h i sp a p e r ，m e m o r ym a n a g e m e n ta n dg a r b a g ec o l l e c t i o nt e c h n i q u e sa r ef i r s td i s c u s s e d ，t h e nj e j a v ac h i ps y s t e mi si n t r o d u c e d t h ed e s i g na n di m p l e m e n t a t i o no fo b j e c tm e m o r ym a n a g e m e n ti nj e j a v aa r ed i s c u s s e di nd e t a i l s o b j e c tc r e a t i o ni n s t r u c t i o n sa r ed i 币c u l tt oi m p l e m e n tw i t hh a r d w a r e b yi n s t m c t i o nt r a p ，t h e s ei n s t r u c t i o n sa r ei m p l e m e n t e db ys y s t e mr o u t i n e o b j e c tc r e a t i o ni n c l u d e sa l l o c a t i n gm e m o r ya n dn 】u pd a t es t r u c t u r e ，t h e s ea r ed o n eb yo b j e c tc r e a t i o nm o d u l ei nm e m o r ym a n a g e m e n ts y s t e m j e j a v au s et r i c o l o ra l g o r i t h mt oi m p l e m e n tg a r b a g ec o l l e c t i o n i no r d e rt oi m p l e m e n tn o n - c o n s e r v a t i v et r a c i n g ，af l e wm e t h o do fo b j e c tf i e l dm a p p i n gi sp r e s e n t e d ：t h r o u g hc a r e f u l l yc h o o s i n gg cp o i n t ，m e m o r yw h i c hi st a k e nu pw h e nc a r r yo u ts t a c kt r a c i n gi sc u td o w ne v i d e n t l y j e j a v ac h i ps y s t e ms u p p o r t sa s y n c h r o n o u sg a r b a g ec o l l e c t i o n ，i m p l e m e n ts t r a t e g i e sa r ed i s c u s s e di nt h i sp a p e r i nt h i sp a p e rah o v e lm e m o r yo r g a n i z a t i o nt e c h n o f o g y w h i c hh y b r i d iz e st h es e g m e n ts c h e m ea n ds e g m e n t p a g es c h e m e i sp u t f o r w a r d ，t h ea l g o r i t h m o f a l l o c a t i n ga n dd e a l l o c a t i n ga r ep r e s e n t e dt o o t h ef l o wo fr o mm a p p i n gc r e a t i o ni sg i v e n a tl a s tt e s tr e s u l t sa n df u t u r ew o r ka r ee x p o u n d e d k e yw o r dl j e j a v ac h i ps y s t e mo b j e c ts t o r a g em a n a g e m e n ta s y n c h r o n o u sg a r b a g ec o l l e c t i o n第2 页国防科学技术大学研究生院学位论文1 1课题背景第一章引言微电子技术、软件技术和i n t e m e t 的迅猛发展，使计算机应用领域出现了两个重要的转变。首先，计算机已经从专业人员使用的设备变成了大众生活、娱乐的消费热点。其次，i n t e m e t 的迅速发展使计算机系统的重心从原来的主机转向了网络。与这两个发展趋势相适应，各种各样能够访问i n t e m e t 的非p c 类设备应运产生，主要包括n c ，信息家电，智能电话，机顶盒等等。i d c 权威数据指出，非p c 的l a d 占所有l a d 的比率将从1 9 9 6 年的1 1 提高到2 0 0 0年的2 0 。j a v a 是随着i n t e m e t 发展起来的，用j a v a 语言编写的a p p l e t 程序几乎成为网页制作中不可缺少的部分，j a v a 在大型分布式软件和嵌入式系统中也占有一席之地，还可能成为信息设备互连标准的基础。因此支持j a v a 语言是对访问i n t e r n e t 的各种非p c 设备的必然要求。一般是在宿主机平台上用软件解释的方式执行j a v a 程序。解释执行实现简币、可移植性强，但存在速度慢的缺点。提高速度的一种途径是采用即时编泽技术：j a v a 虚拟机在第一次执行j a v a 程序代码时，将代码编译为宿主机本地代码，重复执行该段代码时，可直接在宿主机上执行。即时编译技术能够有效提高j a v a 代码的执行速度：但编译后的代码要占用空间，如果代码仅执行一次，反而会降低效率。这些软件实现的j a v a 虚拟机的般都比较庞大( j d k i 1 2 软件包的可执行代码有2 m 字节以上) ，不适合在没有硬盘系统的便携式i n t e m e t访问没备中应用。直接支持j a v a 指令j a v a 微处理器不仅可以有效提高程序执行速度，并且可以嵌入到非p c 类设备中售缸满足应用要求。国际上的许多公司已经提出了一些能直接支持j a v a 程序运行的微处理器( 即j a v a 芯片) ，例如s u n 公司提出的p i c o j a v a 芯片，a d v a n c e ll o g i c 公司提出的t i n y 2 j 微处理器，p a t r i o t 公司提出的p c s1 0 0 0 微处理器等等。渤向吖i 俄二 犰池哩。百kj a v a 芯片系统是一个基于面向堆栈、面向对象咐微处理器系统，与传统基于结构化程序设计的微处理器系统在微处理器体系结构、软硬件接口和操作系统等方面有重大区别。因此对j a v a 芯片系统实现的关键技术进行研究极具现实意义。1 2j a v a 技术介绍本节介绍了j a v a 语言的历史、特点和实现的基本过程。第3 页国防科学技术大学研究生院学位论文1 2 1j a v a 语言介绍j a v a 的历史可以追溯到1 9 9 1 年，s u n 公司的j a m e sg o s l i n g 发现传统的程序设计语言在安全性和操作系统依赖性等方面并不适合家用消费类电子产品，为此开发了被称为o a k 的程序设计语言。1 9 9 4 年下半年，i n t e m e t 的迅猛发展使s u n 公司将o a k 重新以i n t e m e t 为目标进行了改进，并称为j a v a 。j a v a 在网络上的优势使它成为i n t e m e t 上受欢迎的开发与编程语言。随着j a v a 语言成功的推出，s u n 公司又发布了j a v a b e a r l s ，j i n i 等将j a v a 应用于分布式系统的软件结构。在j a v a 语言的开发环境上，s u n 公司连续推出j d k 系列的软件包，目前已经到j d k l 2 0 ，m i c r o s o f t 公司也推出了v i s u a lj + + 1 1 ，v j6 0 ，i b m 公司的v i s u a la g ef o rj a v a 等。根据s l n 公司的定义，j a v a 是一种具有“简单、面向对象、分布式、解释型、健壮、安全、体系结构中立、可移植、高性能、多线程、动态”等各种特性的语言。s u n 公司对j a v a 的定义描述了j a v a 语言和运行环境的特点。作为种编程语言，j a v a 语言既可以编写一般的应用程序，也可以用来创建一种支持网络交互的应用小程序( a p p l e t ) ，具有较高的可移植性：另外，j a v a 还包括j a v a 语言的丌发和执行环境。c + + 语静电是一种常见的面向对象程序设计语言，j a v a 语言继承了它的许多特性，但也做了很大改动，与c + + 相比，j a v a 具有以下特点：面向对象j a v a 语言支持面向对象程序设计。与c + + 语言相比，它比较简单( 比如不支持多重继承，不支持操作符重载) ，而且没有面向结构化程序设计的痕迹。可移植性好j a v a 应用程序是一种与具体平台无关的类文件，它在j a v a 虚拟机上运行。而c + + 语言编写的源程序必须经过重新编译才可以移植到其他的平台上，仅仅具有源程序级可移植性。程序代码短j a v a 虚拟机指令是面向堆栈的，没有传统面向寄存器指令中的寄存器地址，j a v a 虚拟机指令还有许多面向对象指令，因此编译出来的j a v a 程序要比完成同样功能的c 或c + + 代码短。安全性j a v a 的执行代码在运行前应经过j a v a 虚拟机中的代码检验器的检验，以保证指令序列的合法性。c + + 语言则没有这种机制。j a v a 中用对象引用取代了指针，对内存的访问通过对象引用来实现，没有直接的内存访问操作或是指针的算术运算，从而有效的避免c 或c + + 语言中因指针越界造成的错误。自动的内存管理j a v a 语言中引入垃圾回收机制，减轻了应用程序员的负担，也有效的避免了c 或c + + 语言中因显式调用“f r e e ( ) ”例程释放内存可能发生的错误。动态链接j a v a 源程序中的类经过编译，形成独立的类文件，拥有独立的名字空间只有在运行时才进行链接。这使j a v a 应用程序具有动态链接性。而c 或c + + 程序必须经过编译并正确的连接库文件，形成一段完整的可执行代码，而后才可以执行。第4 页闻鼽科学技术人学研究生院学位论文支持多线程j a v a 语言全面支持多线程程序设计。现有的j a v a 开发工具中般包含一个线程包，支持用户级线程的调度执行。1 2 2j a v a 的运行机制同传统的编译型语言一样，j a v a 语言源程序首先需要进行编译；所不同的足编译产生的j a v a 应用程序是种具有统一格式的类文件。j a v a 类文件的执行经过以下四个步骤：装载、验证、链接、执行。首先，j a v a虚拟机装入系统类、指定类和运行该类所用到的其他类：接着，根据虚拟机规范验证类文件是否合法；随后，j a v a 虚拟机链接装入的类，将名字引用转换为实际的地址引用；最后开始执行指定类的m a i n 方法中的第一条指令。在一股宿主机上的j a v a 运行过程如下图( 注：j a v a 虚拟机简称j v m ) 。j a v a程序是在j a v a 虚拟机上运行，因此具有良好的平台无关性。j a v a 语言源程序中一般包括一个或多个类的定义，编译器的任务是生成每个类对应的类文件。类文件由常数池、方法、域以及接口等结构组成，记录类的名字、类包含的域和方法、继承的接口、超类等信息。常数池是类文件中的重要结构，存放方法运行时的辅助信息。方法中的代码( c o d e ) 包含了虚拟机指令和对常数池的索引。由于j a v a 语言的语法简单，类文件又有良好的结构性，因此，它的编译器比较简单，如s u n 公司j d k 中的j a v a c ，仅有2 5 k 字节。1 2 3j a v a 应用程序接口( a p i )j a v a 的a p i 是一组可供程序直接调用的类，类中包含了用于系统功能调用的基本方法( 如字符串操作，数学函数) 以及程序设计辅助工具( 如散列表，堆栈等) 。具体来说，a p 中的类可以归为两大类库：j a v a 类库和h o t j a v a 类库。j a v a类库中主要包括的是一些用于系统功能调用的类；h o t j a v a 类库主要用于浏览器环境。j a v a 类库中的类又可以分为3 个子类库：j a v a 基础语言类库( j a v a 1 a n g ) 、j a v a 实用工具类库( j a v a u t i l + ) 、输入输出类库( j a v a i o ) 。j a v a 1 a n g 类库中包含了j a v a 语言设计的基本类，其中o b j e c t 和c l a s s 最重要的两个类。o b j e c t 类第，页固聃科学救术人学研究生院学位埝史是类层次结构中所有类的超类；c l a s s 类是类的模板，所有的类对象都是它的实例。程序员通过调用a p i 中提供的类或对象方法获得系统服务。a p i 中的类是由j a v a 语言编写的，因此a p i 具有良好的平台无关性，通过扩展a p i 类库，可为程序提供更多的服务。s u n 推出的j a v a 开发工具集j d k ( j a v ad e v e l o p m e n tk i t ) 中实现了a p i 类库中的部分类。1 。3 现有j a v a 虚拟机实现技术j a v a 虚拟机是j a v a 应用程序的运行平台，它屏蔽了宿主机的特征，确保j a v a 程序可以在不同的宿主机上运行。j a v a 虚拟机一般完成三方面的功能：执行j a v a 虚拟机指令、实现一部分a p 、与宿主机相关的a p i 交由宿主机操作系统实现。图1 2 指出了在一般宿主机上应用程序、j d k和j a v a 虚拟机之间的关系。j a v a 虚拟杌的功能是支持类文件的运行。从其内部看，它是一组功能单元的集合，s u n 公司j a v a 虚拟机规范中没有对功能的实现做具体规定，因此可以在不同宿主机平台上灵活实现j a v a 虚拟机。现有的实现主要有三种方式。1 3 1 解释执行j a v a 虚拟机指令由一个字节的操作码( 又称字节代码) ，以及不定长的操作数组成。格式如下：o 8i 操作码j 操作数，、操作数：操作数ns u n 公司最初推出的j d k 中采用软件逐条解释字节码的方式执行j a v a 程序。解释型的j a v a 虚拟机是在宿主机和操作系统的支持下由软件实现的。虚拟机包括字节代码解释器、对象管理器、堆栈管理器、j a v a 应用程序a p i 。从功能实现的完整性上考虑，还包括宿主机和操作系统提供的软硬件支持。解释型的虚拟机结构如图1 3 。第6 页国防科学技术大学研究生院学位论文字节代码解释器对方法代码中的指令进行解码，而后调用相应的功能单元；所有的操作和结果均是面向堆栈的，堆栈管理器一般用软件实现；对象管理模块完成对象管理，包括分配新的对象，解析类、对象和方法：j a v aa p i 是一个类库，为j a v a 应用程序提供标准服务。这些服务最终都通过宿主机接口由操作系统或直接用硬件实现。解释执行j a v a 程序存在速度慢的严重缺点，这是阻碍j a v a 同c 、c + + 等作为大型应用程序语言竞争的重要原因。1 3 2 即时编译( j i t )即时编译( j i t ) 是提高j a v a 程序运行速度的有效办法，类文件中的方法代码第一次被调用时，j a v a 虚拟机将方法代码编泽为宿主机机器代码，运行时将不再需要用解释器条一条解释执行，而足出宿主机直接执行编译后的机器代码。即时编译的方式下，j a v a 程序的执行速度可与c 或c h 程序速度相比。为进一步提高j a v a 程序的运行速度，j o s e p h ，等人提出种加入注解以实现编洋优化的策略。在源程序编泽生成类文件的同时，还生成相应的注解，这些注解保留了更多的源程序信息，使得在j i t 时可以利用这些注解对程序的编译进行更高效的优化，以进一步提高程序的执行效率。注解和类文件是分开存放的，对那些不支持注解优化的编译器没有影响。即时编译保证类文件的跨平台特征，并且有效提高程序执行速度，但是它存在以下缺点：类文件代码编译后的机器代码需要占用空间，注解的方式将占用更多的空间。对于资源较为紧张的系统( 如嵌入式系统) 是不合适的。大量的a p p l e t 代码可能只在宿主机上运行一次，编译后的代码没有重用性。同解释执行一样，即时编译技术同样需要在宿主机和操作系统支持下实现，不适合在嵌入式系统中应用。编译执行还有另一种方式：类文件首先被转换为c 或c + + 等高级语言，而后利用现有的c 或c + + 编译器编译为本地代码执行，这增加了一个预处理过程，但可以提高代码执行速度。该方式的特点与一般j i t 相似。第7 页国防科学技术人学研究生院学位论文l _ 3 3j a v a 微处理器系统j a v a 由于其安全，代码短小等特点在嵌入式硬件平台上也极具竞争力，但效率低、实时性差的缺陷一直阻碍它在嵌入式系统中的应用。设计直接支持j a v a虚拟机指令的微处理器，是提高j a v a 程序运行速度有效的办法，也是j a v a 技术面向嵌入式系统发展的要求。s u n 公司提出的p i c o j a v a 芯片是一种典型的j a v a 微处理器系统，包括能直接执行j a v a 虚拟机指令的微处理器芯片和相关的操作系统。该芯片主要面向高端嵌入式系统，在与i n t e m e t 相连的设备中也有潜在的应用前景。它具有以下特点：在标准j a v a 虚拟机字节码的基础上扩充1 1 5 条指令具有一个堆栈c a c h e ，可有效提高面向堆栈指令的性能提出同时发射多条简单指令的指令“折叠( f o l d i n g ) ”技术实现在硬件支持下的世代垃圾回收p i c o j a v a 芯片虽然能比较有效地支持j a v a 程序的运行，但它存在以下缺点：硬件不能直接支持j a v a 虚拟机指令系统中常用的面向对象指令，需要通过自陷方式用软件实现，影响系统的性能扩充指令系统将引起操作系统的可移植性降低指令“折叠”技术所需的硬件比较复杂，但是效果并不理想对操作系统的设计没有进行深入研究。通过对上述j a v a 语言的介绍和已有j a v a 虚拟机的分析可以看出，已有的j a v a实现技术还不能完全满足新一代嵌入式系统的要求。为了掌握j a v a 芯片中的关键技术，我们设计了j e j a v a 芯片系统。对象存储管理是j e j a v a 芯片系统中的关键技术之一。存储管理的效率直接影响系统性能。垃圾回收是造成程序执行和响应时间不可预测的重要原因，而因此引起的实时性差的特点影响了j a v a 在嵌入式系统中的应用。研究满足一定实时性要求的垃圾回收算法是面向嵌入式系统的必然要求。1 4 本文研究的主要内容本文主要研究j e 。j a v a 芯片系统中对象存储管理子系统的设计和实现。具体包括：对象创建指令的实现垃圾回收算法和精确扫描的实现j e j a v a 芯片系统异步垃圾回收方案的设计物理存储器的管理和地址映射第8 贝国防 学技术人：# 研究生院学位论土1 5 已做的工作和取得的成果通读了j a v a 虚拟机规范、存储器管理和垃圾回收的相关资料以及k a t i e ( 一种软件实现的j a v a 虚拟机) 的源代码。实现了j a v a 语言中的四条对象创建指令和物理存储器管理器。改进了垃圾回收过程中g c 点的设置方法，既减少了存储开销又能保证精确回收的需要。采用“对放法”的对象域组织方式，杜绝了传统保守扫描中内存泄露的问题。采用段式和段页式混合方式组织物理存储器，在对象的访问速度和存储器的利用率之间取得了较好的平衡。提出了在硬件支持下的异步垃圾回收的策略，并进行了初步实现。实现了创建系统程序r o m 映像的软件。上述工作和成果具体表现在本硕士学位论文中。1 6 论文的组织与结构本论文重点介绍j e j a v a 芯片系统中对象存储管理方案的设计和相关的存储分配和垃圾回收技术。沦文共分七章。第一嚣为引言，介绍课题背景、j a v a 的历史和特点、j a v a 语言和j a v a 虚拟机的相关知识。第二章介绍存储管理技术研究现状，分析已有的存储分配和垃圾回收算法。第三章介绍我们设计的j e j a v a 芯片系统软硬件，使读者对j e j a v a 芯片系统有一个整体认识，并了解存储管理在j e j a v a 芯片系统中的重要作用。第四章介绍j e j a v a 芯片系统中对象创建指令的实现、垃圾回收算法和实现中的一些细节问题。第五章介绍对象的访问和物理存储器的管理。第六章介绍系统类的装载和链接程序。第七章为结束语。读者通过阅读论文可对本人所作的工作有一个较为全面的了解，希望本文对正在从事j a v a 实现技术研究的同志有所帮助。第9 负围防科学技术人学研究生院学位论义第二章存储管理技术研究现状2 1 内存管理技术研究现状在程序的运行过程中需要动态的分配存储器空间，而存储器空i 到是比较关键的系统资源，所以需要及时释放程序执行不再需要的存储器空间以提高存储器的利用率。由于动态分配存储器是系统中常用的例程之，所以存储器的分配和回收技术一直是计算机研究中的重点。存储器的分配和回收一般由特定的内核程序完成，用于内存分配的内核程序称为内存分配器。下面我们介绍不同的内存分配器并分析它们采用的内存分配方法。2 1 1 资源映射图分配法算法描述资源映射图是一组记录空闲内存的偶对 的集合。一开始，资源映射图只有一个项，它的b a s e 是内存池的基址，s i z e 是内存池的大小。随着应用程序不断的分配和释放内存，内存池被逐渐打碎。内存分配器为每段连续的空闲内存分配一个偶对。资源映射图按基址顺序组织，这样就可以很容易连接两个邻接的空闲内存区。对资源映射图，可用如下三种策略之一束满足分配请求：最先匹配，从第一个可以满足请求的空闲块中分配内存。这是最快的算法，但是可能会引起较多的碎片。最佳匹配，选择可以满足请求的空州块中最小的一个分配。该策略的缺点是可能造成若干非常小的不可用的空闲块。最差匹配，如果没有正合适的空闲块，选择可满足请求的空闲块中最大的个。分析资源映射图是一种简单的分配器，它有如下优点：算法易于实现。它精确地分配请求所需要的内存，内部碎片小。分配器完成邻接空闲块的合并，有利于内存的再利用。然而，资源映射图分配法也存在缺点：外部碎片严重。资源图的管理复杂。为了合并邻接的空闲块，分配器必须按基址升序排列它们。排序的代价很高。分配器为找到足够大的空闲块必须对资源映射图进行线性搜索。随着碎片的增加，极端情况下搜索耗时甚大。第1 0 页固防科学技术人学研究生院学位论义通常可以将映射图的每一项存放在空闲块的前几个字节中。这种方法不需要额外的内存，也不需要动态分配映射图，而只需要一个指向第一个空闲块的全局指针，每一个空闲块保存它自身的大小和下一个空闲块的指针，这种方法要求空闲块至少有两个字大小的空间( 一个放大小，一个放指针) 。2 1 2 简单二次幂次空闲表算法描述该算法使用组空闲表，每张表存放某一特定尺寸的空闲块，空闲块大小均为2 的整次幂。每个空闲块有一个字大小的头结构，可用空f b j 不包括这个字。当内存块空闲时，这个字存放指向下一个空闲块的指针；当内存块被分配后，可以存放内存块的大小。m a l l o c 例程负责分配内存，其中一参数为请求的大小。分配器根据请求的大小挑选尺寸最小可以满足陔请求的空闲表进行分配。这一计算过程附加额外的头结构大小并将得到的结果取整为2 次幂。如3 2 字节的内存块可以满足旺2 8 字节的请求。分配器将空闲块从相应的空闲块链表中删除，并在头结构中记录空闲表的指针，然后将第一个字节的指针作为返回值返回。当用户释放内存时使用由m a l l o c 返回的指针作为参数调用f r e e 例程，用户不必指定释放的内存大小。f r e e 例程将指针减去4 得到头结构的指针，在从头结构中获得空闲衷的指针，并将该内存加入到空闲表中。分配器可以预先为每个空闲表分配一定数量的内存块，也可以先让它们为空，然后在需要时调页面绒动态分配器动念，匕成那些内存块。因此，如粜某个空闲表为空，分配器处理相应尺寸的m a l l o c 例程时由三种可能：阻塞请求，直至有相应尺寸的内存块释放。用更大的不为空的空闲表的内存块满足请求。向页面级分配器申请分配页面，并创建相应尺寸的内存块。分析上述算法简单而且快速。其最大的优点是避免了资源映射图算法中漫长的线性搜索过程，彻底清除了碎片问题。另一个优点就是f r e e 例程不再需要内存块大小这个参数，该算法的缺点：算法中的f r e e 例程不允许释放部分分配的内存，将请求的大小取整到2 次幂可能浪费内存，引起较多的内部碎片。该算法不能将相邻的空闲块拼接起来满足大块的分配请求。每个内存块的大小一直都是固定的，只能用大的内存块满足小内存块的分配请求。2 1 3m c k u s i c k k a r e l s 分配器h 俨算法描述k i r km c k u s i c k 和m i c h a lk a r e l s 共同提出了一个改进的2 次幂分配器，许多u n i x 系统都使用了该分配器，如4 4 b s d ，d i g i t a lu n i x 等。该改进算法避免某些情况下的空间浪费，如分配请求恰好是2 的整次幂的情况：优化取整的计算，对编译时已知的尺寸省去了计算时间。第1 i 贞国防科学技术人学研究生院学垃论义m c k u s i c k k a r e l s 算法将被管理的内存组织成一组连续的页面，并且同一页面内的所有内存块大小是一样的( 都是2 的整次幂) ；它用一个页面使用数组( k m e m s i z e s 1 ) 管理页面，每个页面可以是如下三种情况之一：空闲：相应的k m e m s i z e s 1 中的元素是指向下一个空闲页面的指针。被划为特定大小的内存块：k m e m s i z e s 是内存块大小。跨页面内存块的一部分：该内存块首页相应的k m e m s i z e s 元素保存内存块大小。m a l l o c 例程负责分配内存，首先对请求的尺寸进行取整( 分配的内存块无头信息) ，并从相应的空闲链表中删除它。如果空闲链表为空，就调用m a l l o c函数为请求分配一个或多个页面，并分割成相应大小的内存块。因为在同一个页面上的内存块大小相同，分配的内存块无需头结构来保存指向空间链表的指针。f r e e 例程将内存块地址低位掩盖掉即可获得页面基址，再通过对应的k m e m s i z e s 元素找到内存块的尺寸。内存块头结构的去除避免了内存的浪费，尤其是那些恰好为2 的整次幂的分配请求。分析m c k u s i c k k a r e l s 算法比简单2 次幂分配器有了明显的改进。它更快，占内存更少，对大内存块请求和小内存块请求同样有效。然而，算法仍然有许多2；欠幂算法中固有的缺点：不能将内存从一个空闲链表移至另一个空闲链表，这使得分配器在突发使用模式下很不稳定。这种模式会在很短时川内消耗大量的某一犬小的内存块。并且算法仍无法向分页系统返回页面。2 1 4 伙伴算法算法描述伙伴算法是一种将空闲块合并技术融入：次霉算法的分配算法。它的基本思想是通过不断对分大内存块来获得小内存块，并尽可能地合并空闲块。当一个内存块被对分后，一个部分称为另一部分的伙伴。分配器使用一张位图来维护内存中每一块的使用情况，如果某位置l ，则相应内存块正在使用。伙伴系统还为每一种可能大小的内存块( 2 的整次幂) 维护一个空闲链表。请求必须先被取整为2 的整次幂。如果对应的空闲链表有可用的内存块，分配器将直接使用它们：空闲链表为空时才进行对分。每个请求同时更新位图，反映内存块的新状态，在合并时，分配器通过位图获知内存块的伙伴是否为空闲。内存块的基址和尺寸是定位其伙伴的全部信息。分析伙伴算法非常适合于合并空闲块，并提供了非常好的灵活性，使内存可以以不同的尺寸再利用。该算法的最大缺点是其性能低。每释放一次内存块，分配器要对不用的内存块尽可能地进行合并，当分配与释放交替进行时，算法可能对刚合并的内存块进行分裂。合并过程递归进行，最坏情况下性能极差。另一个缺点是释放例程需要内存块的基址和大小作为参数。第1 2 贝闽斯科学技术人学研究生院学位论立2 1 5s v r 4l a z y 伙伴算法算法描述f 常的伙伴系统在每次释放时都经过两个步骤：l 、内存块加入空闲链表中，以便其他请求可以再次使用它。2 、在位图中标记内存块为空闲，并且尽可能将与其伙伴合并，这就是合并操作。l a z y 伙伴系统执行步骤l 标记内存块为局域空闲。是否执行步骤2 决定于该时刻的状态。在任何时刻共有一种类型的内存块( 称为内存块类) 共有n 块，其中有a 个内存块为活动内存块，l 个内存块为局域空闲块，g 个内存块为全局空闲块( 在位图中标已为空闲，可以合并的) 。n = a + l + g根据这些参数值的不同，一各内存块类有如下3 个状态：l a z y ：内存块的消耗处于平稳状念( 分配和释放是均衡的) ，没有必要进行合并。r e c l a i m i n g ：消耗进入临界状态，需要进行合并。a c c e l e r a t e d ：消耗进入不稳定状态，分配器必须更快的进行合并。决定内存块类的关键参数称为s l a c k ，定义为s l a c k = n 一2 l g 。s l a c k 大于等于：时，系统处于l a z y 状态：等于l 时处于r e c l a i m i n g 状念；为0 时处于a c c e l e r a t e d状念。算法保证s l a c k 不会变为负值。当释放内存块时，s v r 4 分配器将其加入空闲块链表并根据当前状态进行下一步操作：处于l a z y 状念，分配器不在位图中标记内存块为空闲。这样的内存块称为延迟内存块，而在其头结构中作相应标记。它可以满足相同大小的分配请求，但不能与伙伴合并。处于r e c l a i m i n g 状态，分配器在位图中标i 己内存块为空闲，并进行可能的合并。如果处于a c c e l e r a t e d 状念，分配器合并两个内存块，一个是刚释放的那个内存块，另一个是可供合并的延迟内存块之一。分配器将合并后的内存块释放给下一级尺寸的空闲链表，然后检查新内存块类的状态并决定是否继续合并。所有这些操作都会重新计算s l a c k 的值。为了有效的实现算法，空闲链表组织成双向链表结构。延迟内存块放在队头，非延迟的内存块放在队尾。这样延迟内存块被优先分配( 分配它们不需要更新位图) 。此外，在a c c e l e r a t e d 状态下，另一个延迟内存块可以很快从队头查到。如果队头是非延迟块，则说明没有延迟内存块。分析相对于基本伙伴系统而言，l a z y 伙伴系统有一些实质性的改进。在稳定状态下，所有的空闲链表均处于l a z y 状态，不花费任何时间迸行分裂或合并。但是，l a z y 伙伴系统的性能变化很大，在最坏性能下比l a z y 更差。第1 3 颤困聃科学技术人学研究生院学位论文内存的分配和回收从计算机诞生之日起就是被关注的焦点，人们已经提出了各种算法。每种算法有它的优点和不足，在设计具体算法时应该根据应用的特点在算法复杂性和性能上进行折衷。2 2垃圾回收技术的研究现状早在6 0 年代，垃圾回收技术就应用于l i s p 、s m a l l t a l k 等高级语言的实现中：近年来，随着j a v a 技术的发展，垃圾回收技术又一次成为研究的热点。在传统的高级语言( 如c 语言) 中，应用程序通过显式调用f r e e 例程释放不再使用的内存。这种方式给予程序员管理内存的权力，并被许多程序员认为是提高程序性能、减轻系统负担的手段。但是，程序员的疏漏可能导致系统崩溃。由系统对内存进行跟踪，从而保留被程序使用的内存而回收不再为程序( 线程) 使用的内存，这过程称为垃圾回收，它是避免上述情况发生的有效手段。垃圾回收的目标是那些不再为程序所使用的内存。在某确定时刻，内存块是否能为程序所使用，等价于程序中是否仍然持有指向该内存的引用。当系统中不再含有指向该内存块的引用时内存不可能再次被程序所使用，这样的内存块就作为垃圾被回收重用。垃圾回收的各种算法都是基于这一点进行的。下面讨论单处理机环境下的各种垃圾回收技术。垃圾回收针对已经分配出去的内存块，在以下的叙述中将用对象来指代内存块。2 2 1 基本的垃圾回收算法引用计数法( r e f e r e n c ee o u l l t )垃圾回收最直接的办法是引用计数法。引用计数法是在对象中设置引用计数域，根据引用数决定对象是否被程序引用。对象的引用数随着程序运行而改变。例如：当执行对引用类型变量p 的赋值操作p = q 时，p 中原来指向的对象的引用数将减一，q 指向的对象引用数将加一。当引用数为零时，表明对象不再被引用，可以回收。引用计数法的优点是比较直观，垃圾回收与程序执行自然交织起来。但引用计数法存在较为严重的缺点。-引用计数法在较大程度上干扰了应用程序，每一次引用的改变都要进行计数的修改。而且在对象引用计数变为零时可能会引起一系列回收，在这种情况下，程序的中断时间将没有上限，也就不能满足当前应用对于实时性的要求。程序中会有局部变量的存在，这些局部变量在生存期问频繁的进行引用的改变，每次都需要改变引用计数，带来巨大的开销。-引用计数会引起浮动垃圾的存在。由于两个或两个以上无用对象之i 刨的引用可能会成环，虽然应用程序已经不再有指向该对象环的引用，环中对象的引用计数仍然不会为零，因此不会被回收。这种无法回收利用的浮动垃圾会随着程序的运行越来越多，造成严重的内存泄漏。由于引用计数法存在上述两种严重的缺陷，因此系统中一般不单独采用引用计数法。第1 4 负困防毒 学让术人学研究生虢学位论义标记清除法( m a r k & s w e e p )标记清除法分为两个步骤完成：1 、标记过程，该过程确定哪些对象仍然被程序所引用并且予以逐一标记；2 、清除过程，将没有标记的对象收回系统。由于对象之间存在引用，这些引用和对象形成一个连通图，称为对象访问图，其中对象对应于连通图中的顶点，引用对应于连通图中饧。标记过程是对象访问图的遍历过程。遍历从一些系统程序可直接引用的对象丌始，需要探测出对象中包含的引用，并逐步延伸到所有已分配的内存。系统直接引用到内存被称为根集，通过根集可以找到所有可以被当前系统中的程序引用的对象。标记清除法消除了浮动垃圾的存在，同时克服了引用计数法对应用程序的干扰，垃圾回收对应用程序来说是透明的。但是，标记清除法的标记过程需要遍历整个内存空间，耗时较长，而为了保证系统的i f 确运行该过程不可被中断，因此也不适应实时性的需要：标记清除法在回收对象时只是简单的将对象放入空闲链表中，没有考虑到内存碎片问题。无用对象和使用中的对象在物理上是交织在一起的，这不利于访问局部性的实现，比如对于页式虚存系统，对象可能散落在不同的页面中。釜造成频繁的换页而影响系统性能。詹j 脯问标记压缩法标记压缩法旨在克服标记清除法存在的碎片问题，它同样包括标记和回收两个过程。与标记清除法不同的是，第二步不再是简单的将无用对象放入空闲袭，而是要对某些对象进行移动，使萨在使用的对象连续存放在低地址端，i 仃空闲内存变为高地址段连续的一大块。标记压缩法具有以下优点，成功的解决了碎片问题，使分配不同大小的对象变得容易。利于访问局部性的实现。标记压缩法也存在严重问题。与标记压缩法相比，它的性能较差。标记压缩法不仅存在清除法中臃长的标记过程，而且压缩过程也很漫长，一般要经历两到三个过程：首先需要计算对象的新地址，而后还要修改程序中相应的引用，最后移动对象到新地址处。 各枢直接修改程序中的岛i 用涉及到程序的运行，一般的做法是增加一个对象入口表，程序中保留的是对对象入口表表项的引用，而由对象入口表存放内存地址。对象入口表的引入又增加了对象的