（计算机科学与技术专业论文）java操作系统的存储优化技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 存储管理是j a v a 操作系统最核心和最关键的技术之一，存储管理的优化将对 j a v a o s 在嵌入式领域中的应用产生巨大的推进作用。目前j a v a 操作系统存储管理 存在着没有利用系统特点来优化垃圾收集、不适应多任务环境和进程间通信对垃 圾收集造成影响等问题。这些问题导致了j a v a 操作系统整体性能的下降和安全性 的不足，从而影响了它们在交互式领域和其他方面的应用。本文针对j a v a o s 存储 管理的问题，在传统垃圾收集技术的基础之上，分别面向系统超级特权级、多任 务环境和进程间通信等三个方面对存储管理进行了改进和优化，并将这些设计实 现在了j u n i c o m 的存储管理原型系统上。评测结果显示这些优化确实能够改进系 统性能并提高系统的实时性。 本文首先研究了操作系统特权级对垃圾收集的便利，具体分析了利用脏页信 息优化分代式垃圾收集算法的可能性，在此基础上设计并实现了一个高效的系统 级垃圾收集算法f l s p 。测试数据表明，这种垃圾收集算法能够提高1 3 的系统性 能，并且使垃圾收集的平均停顿时间缩短5 0 。同时本文还发掘了其他两种能够 被垃圾收集利用的特权级便利，分析了它们特点和用途。然后本文针对多任务环 境的特点，设计了一种任务独立的全局垃圾收集策略，并研究了动态的确定垃圾 收集时机和选择垃圾收集任务的方法。这种垃圾收集策略能够利用任务调度来隐 藏垃圾收集的延迟，通过在合适的时机选择垃圾较多的任务进行收集，提高垃圾 收集的吞吐量和收集效率。最后针对共享的进程间通信机制存在的安全性和垃圾 收集方面的问题，本文设计了一种安全高效的进程间通信机制m s p ，并解决了它 所产生的共享堆收集和虚地址漏洞的问题。测试数据表明，m s p 进程间通信机制 安全性好，并且在传递大对象时具有明显的性能优势。 主题词：j a v a 操作系统，存储管理，垃圾收集，f l s p ，j u n i c o r n ，多任务， 进程问通信，m s p ，交换堆，虚地址漏洞 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t m e m o r ym a n a g e m e n ti so n eo ft h em o s ti m p o r t a n tt e c h n i q u e si nj a v ao p e r a t i n g s y s t e m i tw i l lg r e a t l yi m p r o v ej a v a o s a p p l y i n gi ne m b e d d e ds y s t e m si fm e m o r y m a n a g e m e n ti so p t i m i z e d c u r r e n t l yt h em e m o r ym a n a g e m e n to fj a v a o s e sh a st h r e e m a j o rp r o b l e m s ：w i t h o mu s i n gs y s t e mp r i v i l e g e d o p e r a t i o n st oi m p r o v eg a r b a g e c o l l e c t i o n ；b e i n gu n s u i t a b l ef o rm u l t i - t a s ke n v i r o n m e n t ；i n t e r - p r o c e s sc o m m u n i c a t i o n a f f e c t i n go ng c t h e s ep r o b l e m sc a u s et h el o wp e r f o r m a n c ea n dl a c k i n go fs e c u r i t yo f j a v a o s e s i ti nt u r na f f e c t st h e i ra p p l y i n gi ni n t e r a c t i v er e a l ma n do t h e rr e a l m s i no r d e r t os o l v et h e s ep r o b l e m s ，b a s e do nt r a d i t i o n a lg ca l g o r i t h m s ，t h i sp a p e rr e d e s i g na n d o p t i m i z em e m o r ym a n a g e m e n tf r o mt h r e ea s p e c t s ：o p e r a t i n gs y s t e mp r i v i l e g eo r i e n t e d ； m u l t i - t a s ke n v i r o n m e n to r i e n t e da n di p co r i e n t e d t h e s ed e s i g na n do p t i m i z a t i o n sa l e i m p l e m e n t e di nt h em e m o r ym a n a g e m e n to fj u n i c o mw h i c hi so u rj a v a o sp r o t o t y p e f i r s t l yt h i sp a p e rs t u d i e st h ea d v a n t a g e sb r o u g h tb ys y s t e mp r i v i l e g et og c u s i n g d i r t yp a g ei n f o r m a t i o nt oo p t i m i z eg e n e r a t i o n a lg ca l g o r i t h mi sc a r e f u l l ya n a l y z e d b a s e do nt h ea n a l y s i s ，t h i sp a p e rd e s i g na n di m p l e m e n t sf l s pw h i c hi sah i g h p e r f o r m a n c es y s t e m l e v e lg ca l g o r i t h m t e s t i n gr e s u l ts h o w sf l s pc a ni m p r o v e s y s t e mp e r f o r m a n c eb y1 3 a n dr e d u c e5 0 o fg ct i m e w ea l s od i s c o v e ro t h e rt w o s y s t e ml e v e lp r i v i l e g e do p e r a t i o n ，a n a l y z i n gt h e i rc h a r a c t e r i s t i ca n da p p l i c a t i o n t h e n t h i sp a p e rd e s i g n sat a s k - i n d e p e n d e n tg l o b a lg cs t r a t e g yf o rm u l t i - t a s ke n v i r o n m e n t w ep r e s e n tm e t h o d st od y n a m i c a l l yc a l c u l a t eg ct i m ea n dg ct a s k t h i ss t r a t e g yc a n m d eg cd e l a yb ym a k i n gu s eo ft a s ks c h e d u l i n g f i n a l l y , t oa d d r e s s i n gt h es e c u r i t ya n d g cp r o b l e m sc a u s e db ys h a r i n gi p c ，t h i sp a p e rd e s i g n sas a f ea n de f f e c t i v ei p c m e c h a n i s mm s p , a n ds o l v et h ep r o b l e m so fc o l l e c t i n ge x c h a n g e - h e a pa n dv i r t u a l a d d r e s sh o l ec a u s e db ym s et e s t i n gr e s u l t ss h o wm s pi sah i g hs e c u r i t yi p c m e c h a n i s m ，a n dp e r f o r m se s p e c i a l l yw e l lw h e np a s s i n gl a r g ed a t ao b j e c t s k e yw o r d s ：j a v a o s ，m e m o r ym a n a g e m e n t ，g a r b a g ec o l l e c t i o n ，f l s p ， j u n i c o r n ，m u l t i t a s k ，i p c ，m s p ，e x c h a n g eh e a p ，v i r t u a la d d r e s sh o l e 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表4 1 通过w r i t eb a r r i e r 获得的重复指针的比例1 9 表4 2s p e c 测试程序在一次垃圾收集周期内d i r t y 页面的比例2 1 表4 3g e n m s 和f l s p 的程序运行时间和平均停顿时间测试数据2 3 表4 4 两种分代式垃圾收集算法主收集时间的比较2 5 表5 1 系统空闲时间计算表3 7 表6 1 对空指针判断的修改4 4 表6 2m s p 通信接口4 4 表6 3 交换堆的收集算法4 6 表6 4 三种通信机制安全性比较4 8 表7 1j u n i c o r n 存储管理系统接口5 5 表7 2 直接修改内存的j a v a 代码5 7 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 文章结构图5 图2 1单地址空间下任务堆的布局7 图3 1 引用计数。9 图3 2 标记清扫1 0 图3 3 半区复制11 图3 4 分代式垃圾收集对象引用关系1 2 图3 5 记忆集1 3 图3 6 有三个分代的分代式垃圾收集算法1 4 图3 7 垃圾收集的一致性问题1 4 图4 1 页表项l8 图4 2w r i t eb a r r i e r 实现代码19 图4 3a l l o c a t e h o l e 算法。2 0 图4 4q u e u e l i b s 的设计2 2 图4 5g e n m s 与f l s p 程序运行时间的比较。2 4 图4 6g e n m s 与f l s p 平均停顿时间的比较。2 5 图5 1基于任务独立的类装载器实现的任务隔离2 9 图5 2 多优先级时间片轮转法3 0 图5 3 任务独立的全局垃圾收集策略3 3 图5 4 垃圾收集线程状态图3 4 图5 5 安全控制机制流程图3 6 图5 6 用栈的升高量来描述垃圾的多少3 8 图6 1j u n i c o m 进程状态图4 2 图6 2m s p 进程间通信机制4 3 图6 3 虚地址漏洞问题4 7 图6 4r m i 方式与m s p 方式通信延迟的比较4 9 图6 5r m i 方式与m s p 方式吞吐量的比较5 0 图7 1j u n i c o m 体系结构5 1 图7 2 动态编译器工作过程5 3 图7 3 存储管理系统的软件结构5 5 图7 4 对象模型5 6 图7 5 l o c a l s p a c e 内存分配策略5 8 图7 6 线性地址转换过程5 9 第v 页 国防科学技术大学研究生院硕士学位论文 图7 7 在进入i d l e 线程时首先调用e n t e r l d l e o 函数6 1 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 兰垒垒握佳丕缝鲍盔篮选丝这查狃窒 学位论文作者签名：区k l 日期： 加口7 年 i ，月誓日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使f + 1 学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电予 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： ! 垒垒握丝鍪统鳆壶焦选丝挞苤透窒 学位论文作者签名： 国坦 日期：m 。7 年i 月留日 作者指导教师签名：二二j 丝乙l 日期：劲7 年，2 月研日 国防科学技术大学研究生院硕士学位论文 1 1 1 选题背景 第一章绪论 1 1 背景 针对日益普及的嵌入式移动计算，人们希望通过利用类型安全的面向对象的 虚拟化语言技术来构筑软件运行平台，从而满足移动计算对系统安全性和易移植 性的要求。j a v a 语言是一种具有良好安全性、面向对象特性的使用广泛的虚拟化 语言，具有很好的跨平台可移植性。基于j a v a 语言开发的j a v a 操作系统可以有效 集成原有操作系统加r u n t i m e 运行时系统的架构功能，并且在安全性和跨平台性方 面具有更强的优势。 目前基于j a v a 语言开发的纯j a v a 操作系统包括j a v ao s t l 4 】、j n o d e 操作系统 【1 9 】和操作系统【1 3 】等。此外类似系统还有微软基于其c 掣语言开发的s i n g u l a r i t y 操作系统i l j 。此类操作系统构建在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 a v a 操作系统的存储管理 都是简单的使用应用程序集的垃圾收集算法，这些垃圾收集算法因为不能适应操 作系统环境，从而严重的限制了整个系统性能。 垃圾收集是一个比较老的研究课题，它是伴随着l i s p 语言的产生而产生的。 目前的垃圾收集算法主要是针对包括j a v a 虚拟机在内的各种虚拟机的，我们称之 为应用程序级垃圾收集算法。应用程序级垃圾收集算法的设计是面向虚拟机环境 的，这种环境与j a v a 操作系统的环境有所不同。它们的不同点和对垃圾收集的影 响主要有以下几个方面： 一、操作系统是直接运行在硬件平台上的，能够管理各种系统资源，可以查 看任意的硬件信息和获得最高执行权限。而虚拟机是运行在操作系统平台上的， 第1 页 国防科学技术大学研究生院硕士学位论文 它的权限受到操纵系统的限制，它只能通过操作系统的a p i 接口访问硬件和系统 资源。这一点使得传统的垃圾收集算法不可能利用操作系统的优势优化垃圾收集， 提高垃圾收集的效率。 二、操作系统是一个多任务环境，系统中同时会运行多个任务，每个任务都 有自己的堆空间，堆与堆之间又相对独立；而虚拟机最多只能运行一个任务，也 只有一个堆空间。传统的垃圾收集算法都是面向单个任务的单个堆设计的，因此 并不能很好的适应这种多个任务的环境。 三、操作系统的一些机制会影响到垃圾收集，这是虚拟机中所不会出现的现 象。例如进程间通信可能会导致任务之间会共享对象，这就必须要求垃圾收集能 够适应这种改变，确保对共享对象的回收。 基于以上三点，我们认为在j a v a 操作系统存储管理系统的设计中，不能简单 的使用应用程序级的垃圾收集算法，必须充分考虑和利用系统特点，对传统算法 进行改进和优化，使它们能够适应操作系统环境，从而改善系统性能，提高j a v a 操作系统的实时性和可用性。 1 1 2 相关研究 目前j a v a 操作系统存储管理的研究还处于起步阶段，大部分的j a v a 操作系统 还只是简单的使用应用程序级的垃圾收集算法。j n o d e 系统【3 , 1 9 堤一个开源的j a v a 操作系统，它采用m m t k 框架【2 】来管理系统内存。m m t k 是为j a v a 虚拟机设计 的一个通用的垃圾收集算法框架，该框架集成了各种经典的垃圾收集算法，用户 可以根据需求为j a v a 虚拟机配置合适的垃圾收集算法。m m t k 最初被设计在i b m 的研究型j a v a 虚拟机j i k e s r v m 上，它本身也是用j a v a 语言实现的。目前作为一 种通用的垃圾收集框架，m m t k 可以被集成到任何j a v a 虚拟机中。j n o d e 把m m t k 移植到自己的系统中来管理内存，但垃圾收集的框架和具体的算法都没有变，因 此垃圾收集的效率不高，同时也导致了系统整体性能的下降。 2 0 0 4 年微软雷德蒙德( r e d m o n d ) 研究院启动了s i n g u l a r i t y 1 】操作系统项卧目 的是利用类型安全的语言来实现安全的操作系统。s i n g u l a r i t y 采用了任务独立的垃 圾收集器的策略，即操作系统为每个任务都建立一个垃圾收集器，每个垃圾收集 器只负责收集自己的任务。当一个任务的内存消耗到一定程度时，它的垃圾收集 器被启动并完成一次垃圾收集。这种垃圾收集策略的优点是系统能够为每个任务 配置不同的垃圾收集算法。因为不同类型任务的内存行为不尽相同，所以同一种 垃圾收集算法不可能适应所有任务。为每个任务配置合适的垃圾收集算法就能够 提高单个任务垃圾收集的效率，从而改善系统性能。 但是这种垃圾收集策略也有它的缺点：一是增加了系统开销，二是不能从系 第2 页 国防科学技术大学研究生院硕士学位论文 统全局调配内存资源。每个垃圾收集器的实现至少需要一个垃圾收集线程和其他 的状态数据，这就会消耗系统的内存和线程资源，对于资源比较紧缺的嵌入式系 统来说会产生比较严重的影响。同时每个垃圾收集器各自为政的现象也可能导致 系统整体性能的损失，例如个任务内存的紧缺就可以引起系统频繁的垃圾收集， 但如果能在任务之间协调调配资源就不会出现这种情况。 除了j a v a 操作系统外，多任务的j a v a 虚拟机也是近年来的一个研究热点。这 种j a v a 虚拟机因为能够同时运行多个任务，因此在这一点上它的环境和j a v a 操作 系统更加相似。目前在多任务j a v a 虚拟机上设计的垃圾收集算法更多的是关注算 法的并行性。m - v m l 9 1 是g r z e g o r z 等人在s u n 的h o t s p o t 虚拟机的基础上设计的一 个多任务的j a v a 虚拟机。 s u n i ls o m a i l 【1 6 j 等在m v m 的基础之上为该系统重新设计了垃圾收集器，以便 让垃圾收集算法更好的适应多任务系统。这个垃圾收集器设计了一种叫 p a b ( p r o m o t i o na l l o c a t i o nb u f f e r ) 的内存结构。收集器使用分代式垃圾收集算法， 为每个任务分配一个年轻分代，在年老分代中为每个任务创建一个动态可扩展的 p a b 区。垃圾收集器每次收集个任务，在进行次级收集时，将存活对象提升至 该任务在年老分代中的p a b 中。p a b 使得每一个任务使用的内存不管是在年轻分 代还是在年老分代中都很容易区分，这样在任务结束的时候就可以直接回收任务 内存而不需要进行一次全堆收集。这种任务独立的堆结构同时也提高了垃圾收集 线程和应用程序之间的并行性。 目前分代式垃圾收集算法已经相当成熟，火车算法作为分代式垃圾收集算法 的变种正被应用在s u n 的h o t , p o t 虚拟机中。渐进式和并发的垃圾收集因为能够消 除垃圾收集的停顿时间和利用多核系统实现并发收集而成为了研究的热点。本文 在第三章的3 4 节中介绍了渐进式和并发的垃圾收集的基本问题。 1 2 本文工作 本文首先分析了j a v a 操作系统与虚拟机环境的不同，研究了j a v a 操作系统上 垃圾收集的特点。在此基础上本文重新设计了j a v a o s 的存储管理子系统，并分别 从操作系统特权级、多任务环境和进程间通信等三个方面对存储管理进行了改进 和优化。本文的工作主要包括以下四部分内容。 1 ) 面向操作系统超级特权级的存储管理优化技术研究 本文首次提出了利用操作系统特权级来优化垃圾收集的方法，并具体研究了 如何利用操作系统提供的无任何开销的脏页信息来优化分代式垃圾收集算法。在 此基础上本文在j 乙吼c o r n 系统上设计和实现了f l s p 算法。测试数据表明在操作 系统级别，这种垃圾收集算法能够提高1 3 的系统性能，并且使垃圾收集的停顿 第3 页 国防科学技术大学研究生院硕士学位论文 时间缩短5 0 。另外本文还分别研究了利用写保护机制实现w r i t eb a r r i e r 和利用 页面重映射降低复制开销的方法，为以后的工作提供了指导。 2 ) 面向多任务环境的存储管理设计和优化技术研究 本文针对j a v a 操作系统多任务的环境，从策略上研究了如何让垃圾收集适应 多个任务多个堆的复杂环境。本文设计了任务独立的全局垃圾收集策略，该策略 在系统中设置一个全局垃圾收集器，垃圾收集器负责收集所有的任务，但每次只 选择一个任务进行垃圾收集，这样既能使垃圾收集在全局调配策略，保证系统性 能的最优，又能每次只对一个较小的空间进行收集，降低垃圾收集的停顿时间。 任务独立的全局垃圾收集策略能够利用任务调度来隐藏垃圾收集的延迟，通 过在合适的时机选择合适的任务进行垃圾收集来提高收集的吞吐量。这种策略的 关键是垃圾收集时机的确定和垃圾收集任务的选择，因此本文重点研究了垃圾收 集的时机和垃圾收集任务的选择。垃圾收集的时机主要研究在什么样的情况下进 行垃圾收集最合适，这种时机必须能够在系统垃圾较多且不影响系统正常运行的 时刻进行垃圾收集，以便提高收集的吞吐量。同时垃圾收集时机的研究还包括如 何预测系统空闲时间，以便系统能够利用空闲时间释放一定的内存，减轻系统内 存压力。垃圾收集任务的选择主要研究如何能选择出垃圾最多的任务，以便提高 垃圾收集的吞吐量。同时在选择任务的时候还应该考虑任务调度的情况，要尽量 选择在下一阶段不可能被调度的任务进行收集，这样才能避免垃圾收集和任务的 正常运行相冲突，利用任务调度来隐藏垃圾收集的延迟。 3 ) 面向进程间通信的存储管理设计和优化技术研究 进程间通信是多任务系统的基本功能，是任务间协同工作的基础。但是目前 普遍使用的共享进程间通信方式会对j a v a 操作系统带来安全问题和垃圾收集的问 题，这些问题无法或者很难解决。本文设计了一种安全高效的进程间通信机制 m s p ，m s p 进程间通信方式建立在消息传递的基础上，对小对象采用拷贝的通信 方式，对大对象采用页面重映射的通信方式。因为不需要拷贝大的数据对象，该 通信方式具有很好的通信效率。并且它能够确保在任何时刻一个数据对象只被一 个任务所引用，因此是一种安全的通信方式。 针对m s p 进程间通信对存储管理系统造成的影响，包括对交换堆的收集和虚 地址漏洞的问题，本文改进了垃圾收集算法，使它能够快速有效的收集交换堆和 漏洞虚地址，确保了通信机制的完整性。最后本文还给出了m s p 进程间通信的性 能评测，分别从安全性、通信吞吐量、通信延迟等三个方面与共享的通信方式、 k a f f e o s 的通信方式以及r m i 的通信方式做了详细比较。 4 ) j a v a 操作系统存储管理的实现技术 本文在j u n i c o m 操作系统上实现了存储管理原型系统。本文设计了原型系统 第4 页 国防科学技术大学研究生院硕士学位论文 的整体软件结构，提供了存储管理的接口方法。利用动态编译器实现了存储管理 需要的两个基本功能：u n b o x e d 类型和m a g i c 方法。u n b o x e d 类型可以使j a v a 语言 创建没有对象头的对象，m a g i c 方法使得可以用j a v a 语言实现任何汇编代码。有 了这两个功能，j a v a 语言的功能和灵活性将大大加强。在此基础上，本文为存储 管理原型系统设计了动态可配置的垃圾收集框架，该框架实现了动态配置垃圾收 集算法的功能，能够为不同类型的任务配置合适的垃圾收集。这个框架中还实现 了f l s p 和g e n m s 等分代式垃圾收集算法。此外，存储管理原型系统还实现了内 存管理，内存监控和任务监控等功能，并利用这些功能实现了任务独立的全局垃 圾收集策略。最后，存储管理原型系统还解决了收集交换堆和漏洞虚地址的问题。 1 3 论文结构 本文一共分为八章，文章的结构如图1 1 所示。第一章介绍了文章背景、相关 研究以及本文的工作。第二章概括了存储管理的基本问题，第三章重点介绍了垃 圾收集算法，第二、三章是后续几章的基础。第四、五、六章从分别从三个方面 对存储管理进行了改进和优化，这部分是本文的主要研究内容和重点工作。第七 章是存储管理系统的实现技术，重点介绍了j u n i c o r n 系统上的存储管理原型系统 第八章是总结和未来工作。论文的具体结构如下： 图1 1 文章结构图 第一章为绪论。本章介绍了目前j a v a o s 存储管理的问题，分析了操作系统环 境和虚拟机环境的不同，得出了不能直接将应用程序级垃圾收集算法应用在 第5 页 国防科学技术大学研究生院硕士学位论文 j a v a o s 的存储管理中的结论。然后介绍了目前在j a v a o s 存储管理和垃圾收集方面 的研究现状。最后介绍了本文的工作和论文结构。 第二章为j a v a o s 存储管理概述。本章首先介绍了j a v a o s 存储管理和垃圾收 集的关系，阐明了垃圾收集是存储管理系统最核心和最复杂的部分，明确了本文 将重点对垃圾收集算法进行改进和优化。然后在存储模型一节中介绍了单地址空 间下任务堆的布局和分配。 第三章为垃圾收集算法研究。这一章先后介绍了经典的垃圾收集算法、分代 式垃圾收集算法、渐进式和并发的垃圾收集算法。最后讨论了j a v a o s 中垃圾收集 的特点和要求，为后面对存储管理的优化提供了指导。 第四章为面向超级特权级的存储优化技术。这一章介绍了如何利用操作系统 特权级提供的便利优化垃圾收集。重点描述了f l s p 算法的设计与实现以及它的测 试结果。最后还讨论了其他两种系统特权级便利，它们分别是利用页面重映射降 低复制开销和利用页面写保护机制实现w r i t e b a r r i e r 。 第五章为面向多任务环境的存储管理技术。本章首先介绍了j a v a 操作系统多 任务的设计，包括任务隔离、任务调度以及内核保护等内容。接下来讨论了多任 务系统可以使用的垃圾收集策略，最后重点介绍了任务独立的全局垃圾收集策略。 这种策略需要把握好垃圾收集的时机和选择垃圾较多的任务，因此本章还介绍了 对这两方面内容的研究。 第六章为面向进程间通信的存储管理技术。本章首先介绍了共享的通信方式 以及它的不足。然后详细描述了安全高效的m s p 进程间通信方式。针对m s p 通 信方式对存储管理带来的问题，本章接下来介绍了如何改进垃圾收集以使它能够 收集交换堆并解决虚地址漏洞的问题。最后本章给出了m s p 进程间通信的评测结 果。 第七章为j u n i c o m 的存储管理原型系统。本章首先简单的介绍了j u n i c o r n 系 统。然后分别介绍了存储管理的整体软件结构及对外接口，支持存储管理j a v a 实 现的u n b o x e d 类型和m a g i c 方法。接下来介绍了动态可配置的垃圾收集框架的实现， 这种框架能够使系统为每个任务动态的配置垃圾收集算法，确保不同类型的任务 能够使用适合自己的垃圾收集算法。最后介绍了存储管理的内存管理、内存监控 以及任务监控的实现方法。 第八章为总结和未来工作。 第6 页 国防科学技术大学研究生院硕士学位论文 第二章j a v ao s 存储管理概述 2 1 存储管理与垃圾收集 j a v a 操作系统的存储管理包括存储模型和内存的分配与回收策略两部分内容。 存储模型主要包括堆和栈的空间布局，任务堆和栈的分配和回收等内容。这部分 内容相对而言比较简单，优化空间不大。存储管理的另一个内容是内存的分配与 回收，或者叫对象的分配与回收。由于语言机制的要求以及安全性方面的考虑，j a v a 操作系统必须使用自动内存管理，即内存的回收由系统自动进行，这就是垃圾收 集技术。此外，由于内存分配和回收紧密相关，垃圾收集算法中必须要有相应分 配策略的支持。垃圾收集是一个复杂的技术，在j a v a 虚拟机中，垃圾收集是一个 比较成熟的领域，目前的研究主要集中在并发的垃圾收集算法上。但在操作系统 领域，垃圾收集面对一个更加庞大和复杂的系统，它的优化空间还很大。因此， 我们对j a v a 操作系统的存储优化主要是研究在操作系统新环境下垃圾收集面临的 新问题以及对垃圾收集算法的优化。 2 2 存储模型 j a v a 操作系统是一个多任务系统，存储管理首先要解决的问题是如何为任务 分配堆空间以及栈的设置问题。j a v a 操作系统一般采用单地址空间加软隔离技术 来实现多任务，系统中的所有任务和内核运行在同一个地址空间下。在3 2 位系统 上，任务堆的空间布局如图2 1 所示。显然这种设计会使得任务的地址范围受限， 内存要求太大的任务不能运行。但对于3 2 位的嵌入式系统而言，以每个任务分配 3 2 m b 的地址计算，整个系统至少可以同时运行1 0 0 多个任务，并且3 2 m b 的空间 可以满足大多数普通嵌入式任务的需求。在6 4 位系统上，由于地址空间十分充裕， 将不会出现单个任务空间受限的问题。 普通任务1警通往务2 内棱堆毫阊特殊任务3 ( 6 3 m ) ( 3 2 m )( 3 2 1 v 1 ) 图2 1 单地址空间下任务堆的布局 j a v a 操作系统内核在运行时需要占据定的地址空间。系统启动后，存储管 理系统对整个系统的地址空间和物理内存统管理。在创建任务时，存储管理系 统将为任务分配一定的地址空间和物理内存。对于普通的任务而言，这个地址空 间的大小通常是个定值，该任务所能使用的最大物理内存受限于它所分配的地址 空间的大小。为了提高系统的可扩展性，存储系统会为特殊任务分配较大的地址 第7 页 国防科学技术大学研究生院硕士学位论文 空间，这取决于任务的类型和创建任务时的设置。在我们所实现的存储管理原型 系统中，普通任务可以分配3 2 m b 的地址空间，特殊任务可以分配6 4 m b 、1 2 8 m b ， 最大可以分配2 5 6 m b 的地址空间。 物理内存实行按需分配的策略。任务创建时分配少许物理内存，在任务运行 的过程中，根据任务需求逐渐分配物理内存。任务可以使用的最大的物理内存受 限于它的地址空间的大小，但是一般的任务都很难使用到最大的物理内存。这是 因为当系统中的内存资源消耗到一定程度时就会触发垃圾收集，而垃圾收集会回 收内存垃圾，释放一些内存资源。 存储管理系统要为每个线程分配一个运行时栈。栈的分配有两种方式，一种 是像分配堆那样直接分配内存。这种分配方式简单，但存储管理系统却要管理这 些内存。当需要释放栈时，存储管理系统必须明确需要释放的是哪片内存空间， 然后将这段内存加入到空闲内存池中去。另一种方式是利用分配j a v a 对象的方式 分配栈空间。当需要分配栈空间时，存储管理系统分配一个大的数组对象，并且 将该数组对象对应的首地址返回。这种方法可以免除系统对栈的特殊管理，由于 栈本身就是一个对象，垃圾收集器可以自动回收栈空间。 第8 页 国防科学技术大学研究生院硕士学位论文 第三章垃圾收集算法研究 3 1 应用程序级的垃圾收集 应用程序级的垃圾收集是在上个世纪6 0 年代随着l i s p 语言的产生而发展起 来的。j a v a 语言的广泛应用更是促进了垃圾收集的发展。随着研究的深入，人们 发明了很多经典的垃圾收集算法，这些经典的垃圾收集算法包括引用计数、标记 清扫、半区复制等。但这些垃圾收集算法仍然不能满足需求。这些算法的最大问 题是在进行垃圾收集的时候系统不能正常的工作，需要等到垃圾收集结束后系统 才能恢复运行。为了缩短垃圾收集的时间，人们又发明了分代式垃圾收集算法， 这种算法将垃圾收集分为主收集和次级收集两个过程。次级收集要比主收集快得 多，对于大多数情况系统只需要进行次级收集就能够满足要求，只有次级收集不 能满足要求时才进行主收集。分代式垃圾收集的这种策略大大缩短了系统停顿时 间，但是仍然不能避免系统的暂时停顿。由于这些垃圾收集算法都需要在收集时 暂停整个系统的运行，因此它们也被统称为s t o p t h e w o r l d 垃圾收集算法。与此相 对，人们希望在进行垃圾收集的同时系统仍然能够正常运行，这样就能满足交互 式应用和实时系统的需求。这种想法促使人们研究渐进式和并发的垃圾收集。随 着多核系统的广泛应用，并发的垃圾收集已经成为目前应用程序级垃圾收集的研 究焦点。本章将简单介绍一些经典的垃圾收集算法，以及目前最新的渐进式和并 发的垃圾收集算法。 3 2 1 引用计数 3 2 经典垃圾收集算法 r 图3 1 引用计数 最早的垃圾收集算法是由h g e l e m t e r 7 】等人提出的引用计数算法。如图3 1 所 示，内存管理器为每个对象维护引用计数值，使之等于指向该单元的指针的数量。 每次有一个指针被设为指向这一单元时，该单元的计数值加1 ；而每次删除某个指 第9 页 国防科学技术大学研究生院硕士学位论文 向它的指针时，它的计数值减1 。如果为o ，就表示不存在指向它的指针。它就成 为了不可达对象，它所占据的空间将被回收。 引用计数算法是一个天然的渐进式垃圾收集算法，它将对对象的追踪放在了 每次指针的写操作中，不会引起系统较长时间的停顿。但同时因为这一点使得它 更新指针的开销太大，影响系统整体性能。然而引用计数算法最大的问题在于它 无法解决垃圾成环问题，这就可能使系统的中垃圾越来越多而无法回收。同年j o h n m c c a r t h y 提出了下面的标记清扫算法，成功的解决了垃圾成环问题。 3 2 2 标记一清扫 如图3 2 所示，标记清扫算法 7 1 在程序运行过程中不断分配内存资源，直到所 有内存资源都耗尽，然后出发一次垃圾收集。垃圾收集的第一步是追踪存活对象， 所谓存活对象是指从根集能够直接或间接引用到的对象，它们是程序仍然在用的， 可以访问到的对象。垃圾收集器每追踪到一个存活对象就给它打上标记。追踪结 束后，堆中没有被标记的对象都是垃圾对象。然后垃圾收集器逐一的扫描每个对 象，将垃圾对象回收。标记清扫算法收集到的空闲内存有的可以连成一片较大的 内存区域，有的则是一些内存碎片。这些碎片散布在内存中，导致了下一次分配 必须在堆中搜索合适的“空隙以容纳新的对象，从而导致下一次的分配更加困 难。另外，内存碎片会造成同一数据结构的相关单元之间失去空间上的局部性， 容易导致频繁的换页。一次换页的开销是毫秒级的，这个开销是非常大的。于是， r o b e r tf e n i c h e l 等人提出了半区复制算法，解决了内存碎片问题。 r t 3 2 3 半区复制 图3 2 标记清扫 第1 0 页 国防科学技术大学研究生院硕士学位论文 图3 3 半区复制 如图3 3 所示，半区复制算法【7 】将整个堆划分为两个半区f r o m s p a c e 和 t o s p a c e ，f r o m s p a c e 包含现有的对象，t o s p a c e 包含已经被废弃的对象。每次对 象的分配都在f r o m s p a c e 中进行，分配算法使用最简单的b u m p p o i n t e r 算法。当 f r o m s p a c e 中的内存资源用完以后，就从根集开始追踪f r o m s p a c e 中的所有对象， 访问到f r o m s p a c e 中存活的对象，就将它拷贝到t o s p a c e 中。在f r o m s p a c e 中所 有的存活对象都被访问过以后，收集器在t o s p a c e 中就建立了一个f r o m s p a c e 中 存活对象的副本。这时f r o m s p a c e 中剩下的就都是垃圾对象，而所有的存活对象 都被移动到t o s p a c e 中了，然后算法将f r o m s p a c e 和t o s p a c e 的名称互换，以原 来的t o s p a c e 作为新的f r o m s p a c e ，对象分配将在这个分区进行。半区复制算法的 优点是分配效率高，解决了内存碎片问题。但该算法占用了两个半区，但实际利 用的只有一个半区，内存利用率极低。同时，研究表明，些相对长寿的对象被 反复的从一个半区拷贝到另一个半区，这非常损耗性能，而且毫无必要的。 3 3 分代式垃圾收集 上述三种垃圾收集算法中，引用计数不能解决垃圾成环的问题，标记清扫和 半区复制都将整个堆空间看成一个整体，每次对所有的对象进行收集，造成系统 较大的延迟。分代式垃圾收集算法通过将堆空间分成两个或多个较小的空间，每 次只对其中的一个空间进行收集，从而降低了收集开销。 3 。3 1算法概述 大量研究表明：大多数对象在年轻时候就会死亡，这就是所谓的弱分代假设 ( w e a kg e n e r a t i o n a lh y p o t h e s i s ) 7 1 。这是通过对大量的应用程序的行为做统计分析 得来的，分代式垃圾收集的设计就是基于这一假设。分代式垃圾收集( g e n e r a t i o n a l g a r b a g ec o l l e c t i o n ) 背后的灵感就是将工作集中在回收最有可能是垃圾的对象( 也 就是年轻对象) 上，从而能够让内存回收更高效、对用户的影响更小7 1 。 第1 1 页 国防科学技术大学研究生院硕士学位论文 图3 4 分代式垃圾收集对象引用关系 分代式垃圾收集算法将堆空间分为年轻分代和年老分代两个部分，对象间的 引用关系如图3 4 所示。新对象的分配发生在年轻分代，当年轻分代的空间不足时 算法触发一次次级收集。次级收集只对年轻分代收集，因为年轻分代的空间较小， 并且根据弱分代假设，大部分的死亡对象都会出现在年轻分代，因此次级收集有 较高的吞吐量和较短的停顿时间。次级收集一般采用拷贝式垃圾收集算法，它将 存活对象拷贝到年老分代，这个过程被称为对象年龄的提升。对