（计算机应用技术专业论文）parrot及其到jvm的移植.pdf

宁国科学技术大学硕士学位论文摘要 摘要 p e r l 语言广泛应用于系统管理、w e b 开发、网络编程等领域，现在发行的主版本为p e r l 5 。 p e r l 6 作为p e f l 的下一代版本，着眼于解决p e r l 5 解释器难以维护的问题，并增加了许多新 特性。p e r l 5 解释器的前后端相互调用、紧密耦合。而p e r l 6 的编译运行体系被划分为四个模 块：解析器( o a r s e r ) 、编译器( c o m p i l e r ) 、优化器( o p t i m i z c r ) 和解释器( i n t e r p r e t e r ) 。解析器将p e r l 源程序解析成语法树，编译器接受语法树生成p e r l 字节码( p b c ) 文件，经过优化器优化，交 给解释器执行。各个模块间虽然不能完全避免相互调用的关系，但耦合程度己大为降低。 p a r r o t 即是p e r l 6 解释器的一个实现。 目前围绕着j v m 的研究和升发日益增多，使得将现有系统移植到j v m 上运行成为一种 需求。我们在之前的工作中，使用j a v a 语占重写了p e r l 5 解释器的核心，并正在研究支持强 大的p e r l 扩展包。p e r l 5 内置数据类型和操作码的复杂性，前后端的紧密耦合等特性给移植 带来了很多困难。p e r l 6 体系的推出为我们研究更简单有效的移植方法提供，途径。我们采 用的移植方法是用j a v a 重写一个p a r r o t 解释器。我们基本实现了p a r r o t 的主要组成部分 包括本地数据类型、运行时数据结构、内存管理等，并解决了动态编译的移植这一难题。 全文共分八章，第一章介绍了研究背景，p a r r o t 以及p a r r o t 涉及的几种语言和文件；第 二章简单介绍了p a r r o t 解释器的内部结构；第三章给出了p a r r o t 的本地数据类型到j v v l 的 移植：第四章介绍了运行时数据结构的移植；第五章主要介绍了内存管理到j v m 的移植； 第六章介绍了基本指令集的j a v a 实现；第七章给出了动态编译到j v m 的移植；第八章总结 了论文的主要内容，讨论今后可以进一步开展的研究内容。 关键字：p a r r o t ，j a v a 虚拟机，移植，动态编译 叶l 国科学技术大学硕士学位论文 摘要 a b s t r a c t p e r l l a n g u a g e i s a p p l i e dw i d e l y i n s y s t e mm a n a g e m e n t ，w e bd e s i g n i n g ，n e t w o r k p r o g r a m m i n gm a ds o o nn o wi t sm a i nv e r s i o ni sp e r l 5p e r l 6i st h en e x tv e r s i o no ft h ep e r l p r o g r a m m i n gl a n g u a g et h ei n t e r n a l so f t h ev e r s i o n5i n t e r p r e t e ra r es ot a n g l e dt h a tt h e yh i n d e r m a i n t e n a n c e ，t h w a r ts o m en e wf e a t u r ee f f o r t s ，a n ds c a r eo f fp o t e n t i a li n t e r n a l sh a c k e r s p e r l 6 h o p e st os o l v et h e s ep r o b l e m s p e r l 6i s c o m p o s e do fap a r s e r , ac o m p i l e r ，a no p t i m i z e ra n da l l i n t e r p r e t e rt h ep a r s e rt r a n s l a t e sp e r ls c r i p ti n t oas y n t a xt r e et h ec o m p i l e rm o d u l et a k e sas y n t a x t r e ef r o mt h ep a r s e ra n de m i t sap a r r o tb y t e c o d e ( p b c ) f i l et h eo p t i m i z e rm o d u l eo p f i m i z e st h e b y t e c o d et h ei n t e r p r e t e rm o d u l et a k e st h eb y t e c o d es t r e a mf r o me i t h e rt h eo p t i m i z e ro rt h e b y t e c o d ec o m p i l e ra n de x e c u t e si t p a r r o ti st h eo n l yi m p l e m e n to f p e r l 6 si n t e r p r e t e rn o w t o d a ym a n yr e s e a r c h e r sa r es t u d y i n gt h ej a v av h - t u a lm a c h i n e ( j v m ) w i t ht h ed e v e l o p m e n t o fa l lk i n d so fh a r d w a r ea n ds o f t w a r ej v m i tb e c o m e sad e m a n d t op r o v i d e 山es o t t w a r e sw h i c h c a nr a no nj v ma n d p o r te x i s t i n gs y s t e m st oj v v 1 w eh a v er e w r i t t e nt h ec o r eo f p e r l 5i n t e r p r e t e r w i t hj a v a ，a n da r er e s e a r c h i n gt h e w a yt os u p p o r tl a r g e rp e r le x t e n s i o nt h e r ea r el o t so f d i f f i c u l t i e sf o rp o r t i n gp e r lt o j v m ，b e c a u s ep e r l 5h a sc o m p l e xi n t e r n a ld a t as t r u c t u r e sa n d o p c o d e s ，a n di t sf r o n ta n db a c ke n da r ec o u p l e dt i g h t l yw i t ht h eb i r t ho fp e r l 6 ，w ec a nr e s e a r c h f o ras i m p l e ra n dm o r ee f f e c t i v ew a yt op o r t i n gp e r lt oj v v l t h ew a ya d o p t e di sr e w r i t t e np a r r o t u 4 t hj a v aw eh a v ei m p l e m e n t e da l m o s t e v e r yb a s i cc o m p o s i t i o n so f p a r r o t ，i n c l u d i n gn a t i v ed a t a t y p e ，r n n t l m ed a t as t r u c t u r e ，a n dm e m o r ym a n a g e m e n ta n ds oo na n dw eh a v ea l s oi m p l e m e n t e d t h er a n t i m e c o m p i l a t i o nt e c h n i q u ew h i c hi sd i f f i c u l t yi np o r t i n gp a r r o tt oj v m ， t h i sd i s s e r t a t i o nc o n s i s t so f e i g h tc h a p t e r sc h a p t e r1b r i e f l yi n t r o d u c e st h eb a c k g r o u n do f r e s e a r c hp r o j e c t c h a p t e r2i n t r o d u c e st h e p a r r o ti n t e r n a l c h a p t e r3 - 7d e t a i l st h ei m p l e m e n t a t i o no f p a r r o ti nj a v a ，s u c ha sp a r r o t si n t e r n a ld a t a $ t t u c t a r e ，r u n t i m ed a t as l r n o t u r e , m e m o r y m a n a g e r s y t e ma n d s oo nt h el a s tc h a p t e rc o n c l u d e s t h ed i s s e r t a t i o na n d p o i n t so u tt h ef u t u r ew o r k k e y w o r d s ：p a r r o t ，j a v av i r t u a lm a e h i n e ( j v m ) ，p o r t , r u n t i m e c o m p i l a t i o n 中国科学技术大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 当今围绕着j v i v l 的研究和开发日益增多。一些研究者研究用硬件实现m 【l ，2 】：商 业上，s u n 已经将p i c o j a v a 3 1 ( j 讧微处理器的中央部件核心) 的许可授予几家公司，这些 公司将会把这种硬件技术加入到未来的产品中，这样具有本地j v m 实现的硬件设备在不久 的几年将会普及。在考虑硬件j v m 时，嵌入式软件j v m 已经普及【4 ，5 1 。在各种j v m 发 展的同时，也带来另一种需求如何提供运行在j v m 上的各种软件，如何将现有系统移 植到j v m 上运行? 单纯地利用j a v a 编程，一方面会限制开发人员对编程语言的选择，另一 方面会使得大量现有系统不得不用j a v a 重写以适应在j v m 上运行的需求。为此许多研究开 发组织着手进行非j a v a 语言到j v m 移植的工作，并提供了许多可用的工具6 1 ，如j a c l 7 1 是用j a v a 重写的1 d 解释器。 在众多非j a v a 语言中，p e r l 语言是由l a r r y w a l l 设计的一种实用的、解释执行的脚本语 言 8 ，9 】。它结合了许多程序设计语言的优点，拥有无可比拟的优势。因而p e r l 被用于诸多 领域，如c g i 、文件处理、w i n d o w s 脚本编写、g u l ( g r a p h i e a lu s e r a t e r f a c e ) 以及数据库访 问等方面。p e r l 解释器现在发行的主版本为p e r l 5 。p e r l 5 拥有编译器的前端和后端。前者负 责解析p e r l 程序，产生中间表示( i ri n t e r m e d i a t er e p r e s e n t a t i o n ) 1 0 ，1 1 ；后者负责实现p c d 的本地数据类型以及一个虚拟杌( p v m ) 解释执行前端产生的i r 。p e r l 5 的前端和后端耦合 度很高，前端在编译时，一方面，为了优化会调用后端使某些语句在编译时就运行完毕；另 一方面，p e r l 程序中有些语句就是需要编译时运行的( 如“b e g i n e n d ”) ，而p e r l 的某 些操作如r e q u i r e ，需要动态加载包，此时后端就需要调用前端对程序进行实时编译1 2 ，1 3 1 。 p e r l 6 作为p e r l 解释器的下一代版本，着眼于解决p e r l 5 解释器难阻维护的问题，并增加了 许多新特性 p e r l 6 的编译运行体系被划分为四个模块：解析器、编译器、优化器和解释器【1 4 】。如图 11 ，解析器将p e r l 源程序解析成语法树，编译器接受语法树生成字节码( p a r r o tb y t e c o d c ， p b c ) 文件。经过优化器优化，交给解释器执行。各个模块间虽然不能完全避免相互调用的 关系，但耦合程度已大为降低。p a r r o t 2 0 ，2 l 】是p e r l 6 解释器的一个实现，它利用寄存器和 栈等实现字节码文件的装载和运行。 图1 1p e r l 6 体系结构 有关p e r l 到j v m 的移植的研究已经展开。目前讨论的移植大多数是基于p e r l 5 的。其 中移植方法主要分为三种： 第一，用j n i 实现p e r l 到j a v a 环境的接口。j a v a - p e r ll i n g o ( j p l ) 使用了j n i 来提供p c r l 和j a v a 之间的访问。j p l 是p e r l 发布版本的核心部分，它简化了p e r l 和j a v a 的集成。尽管 j p l 还不算是真正意义上的移植，但正如l a r r yw a l l 所指出的，它至少显示出p e r l 与j a v a 中国科学技术大学硕士学位论文 第一章绪论 的语义是兼容的。但要完全地将p e r l 移植到j v m 中时，此方法并不可取。 第二，通过某种方法将p e r l 的i r 最终转化成j a v a 的类文件，从而使p e r l 程序最终可以 在j v md - 运行。k u h n 在他的顷士论文中探讨了两种移植方法：一种是使用j a s m i n 汇编器 将p e r l 的i r 直接转换到j a v a 的类文件 1 5 ，1 6 1 。这种方法过多地依赖于p e r l 的ir 它隐含 地假设p v m 可以很容易地直接映射到j v m 。p e r l 复杂的本地数据类型和i r 使得p v m 到 j v m 的映射极其困难，这种方法已经被证实有很大的局限性。另一种方法是首先将p e r l 的 i r 转换成k a w a 1 7 ，1 8 1 的i r ，然后再将k a w ai r 转换成j a v a 的类文件，该方法仍处于研 究状态1 1 9 。 第三，使用j a v a 语言重新编写p e r l 解释器。我们在之前的工作中，即使用这种方法重 写了p e r l 5 解释器的核心【3 3 】，并正在研究实现对强大的p e r l 扩展包的支持。 p e r l 5 内置数据类型和操作码的复杂性、前后端的紧密耦合等特性给移植带来了很多困 难。p e r l 6 体系的推出为我们研究更简单有效的移植方法提供了途径。基于p e r l 6 的体系结构， 可以考虑两种移植方法： 1 ) 针对p e r l 6 字节码用j a v a 重写其解释器； 2 ) 直接将p e r l 6 字节码文件映射到j a v a 类文件。 前者需要用j a v a 重新实现p e r l 6 的内部数据结构，实现p a r r o t 的寄存器和栈的机制，以 及各种操作函数。后者需要考虑p o r l 6 字节码中的各种操作码到j a v a 字节码中的操作码之间 的映射，p e r l 6 字节码文件各个段的重新组织，以及对实时编译的处理。我们采用了第一种 移植方法，即使用j a v a 重写p r o r o t 。 1 2p a r r o t 简介 2 0 ，2 1 】 p a r r o t 为当前p e r l 6 解释器模块的实现，版本目前为o 1 2 。我们的移植则是基于ol0 版本的。p a r r o t 主要用来执行编译器输出的( 或可选的通过优化器优化过的) p r o - r o t 字节码 文件。它是一个基于寄存器的、字节码驱动的、面向对象的解释器，它的特性还包括多线程、 动态定型等。 和其它所有的解释器系统一样，p a r r o t 解释器是个虚拟机，或者说是软件c p u 。然而 和其他虚拟机不同的是p a r r o t 解释器被设计得更类似于硬件c p u 的镜像。例如，p a r r o t 虚 拟机使用寄存器系统而不是栈系统。它还拥有极其低级的操作码，相对于p e r l 和p y t h o n 等 语言的中级操作码，它更类似于j a v a 。选择这种体系的理由主要在于：虚拟机与底层硬件一 定程度的相似，使得将p a r r o t 字节码编译成更有效的本地机器语言成为可能。选择这种机制 还有另一个好处：我们可以利用所有现存的、关于如何为基于寄存器的硬件c p u 编写编译 器和优化器的文献，来为我们的p a r r o t 这一软件c p u 编写编译器和优化器。 p a r r o t 的主要功能是装入并运行p b c 文件，为此，它实现了四种本地数据类型以支持 p b c 文件中的数据类型，并维护一些运行时结构。p a r r o t 将p b c 文件装载，并解析到内部 结构中，而后根据p b c 文件代码段中的指令流，依次调用相应的操作码函数完成对p b c 文 件的执行。在执行p b c 文件的过程中，由p a r r o t 的内存管理系统负责为运行中使用的变量 等分配空间并回收死对象。而动态编译则是p a r r o t 的个重要的动态特性，也是移植中的难 2 中国科学技术大学硕士学位论文 第一章绪论 点。第1 _ = 章中将对p a r r o t 做进一步的介绍。 p a r r o t 目前的版本因为内置了p i r ( p a r r o ti n t e r m e d i a t er e p r e s e n t a t i o n ) 【2 1 1 编译器和 p a s m 2 1 | l 编器，可接受的输入为p i r 中间码格式、p a s m 汇编码格式以及p b c 字节码格 式的文件。p e r l 语言编写的程序只要被转化为这三者之一即可在p a r r o t 上运行。本文对p a r r o t 中内置的p i r 编译器和p a s m 汇编器不做讨论。但由于p b c 文件中的操作码为整数形式， 不利于阅读，而p a s m 的操作码则是助记符形式，且每个p b c 文件中的操作码都存在在意 义上较为接近的p a s m 操作码，故而本文中需要用到操作码时都使用p a s m 的操作码。以 下将分别介绍p e r l 语言、p a s m 代码和p b c 文件。 1 3p e r l 语言、p a s m 和p b c 文件 t 3 。1p e r l 语言 和多数脚本语言一样，p e d 是弱类型的，不需要显示的类型声明。p e r l 有三种数据类型： 标量、数组和关联数组( 散列) 【2 2 ，2 3 1 。 标量是p e r l 处理的最简单的数据类型。标量可以是数字( 如2 , 3 或2 5 0 6 ) ，也可以是字符 串( 如 h e l l o ”) 。p e r l 中的标量变量以符号$ 和一个字母开始，以后可以是字母、数字和下划线， 大小写有区别，而且所有字母、数字和下划线都有效。 数组是标量数据的有序列表，可以含任意多个元素。数组的值是位于括号内用逗号分开 的一系列值。如： ( 1 , 2 ，3 ，4 ，5 )# 具有l ，2 345 五个数值的数组 ( ”z m d , 1 9 7 4 ，1 7 3 5 )# 具有”z m d , 1 9 7 4 ，1 7 3 5 三个数值的数组 ( )# 空数组 ( s a ，5 )# 两个数值：$ a 的值和5 ( s a + $ b ，6 )# 两个数值 数组变量名要以 打头而不是$ ，如： z m d 。数组的赋值和标量赋值一样，也用等号 表示。p e r l 根据赋值对象是标量还是数组变量，来确定赋值操作是标量赋值还是数组赋值。 关联数组和数组类似，它包含标量数据，可用索引值来单独选择这些数据。和数组不同 的是，关联数组的索引值不是非负的整数而是任意的标量，这些标量称为k e y ，可以在以后 用于检索数组中的数值。 关联数组是p e r l 语言中特有的，关联数组是一个功能强大的数组。关联数组名以号开 头，关联数组的格式如； a r r a y = ( k e y l ，v a l u e l ，k e y 2 ，v a l u e 2 ，k e y 3 ，v a l u e 3 ) ； 每一个k e y 都有一个相对应的值( w u e ) 。 p e r l 语言操作和值的解释由其上下文决定【2 4 】，主要有三种上下文：字符串、数字和数组。 当上下文要求一个数组时，操作返回数组值，其它情况返回标量值。而标量变量及值相应于上 下文被解释为字符串或数字。非空的字符串或非。的数字可以表示布尔类型中的真值；空字 符串和。可以表示假值。是否需要由字符串和数字获得相应的布尔值也根据上下文判断。 3 中国科学技术大学硕士学位论文 第一章绪论 p e r l 语言的每种数据类型有各自的名字空间，因此不用担心不同类型变量( 标量变量、数 组、关联数组、文件和子程序等等) 的同名冲突问题。 p e r l 语言的程序是由说明和命令序列组成【2 5 】。在p e r l 语言中，只有报告格式和子程序需 要说明。c 中所有的控制流语句p e r l 均支持，此外p e r l 提供了比c 更为丰寓的控制语句， 比如“u n l e s s e l s e ”、“f o r e a e h ”、“n e x t ”、“l a s t ”等，从而能更为灵活地组织程序。 1 3 2p a s m 代码 2 0 ，2 1 1 p a r r o t 的字节码可以被认为是为虚拟的c i s c ( c o m p l e xi n s t r u c t i o ns e tc o m p u t e r s ) 机器提 供的某种形式的机器码。为了便于直接获得字节码p e r l 6 的设计者还定义一种汇编代码，即 p a r r o t 汇编码( p a s m ) 。p a s m 拥有许多特性。由于p a s m 是一种汇编语言，它拥有许多低 级的特性，如基于分支( b r a n c h ) 和跳转( j u m p ) 的流控制，对软件寄存器及栈中的数值的 直接操作。另一方面，由于队s m 被设计用于实现动态的高级语言，它也支持许多高级特 性，例如对象、无用单元收集等。 p a s m 的语法很简单。每个语句独立一行，语句都由一个操作码开始，随后跟随0 个或 以上个参数。操作码的参数由逗号隔开，如下： 【l a b e l 】o p c o d cd e s t , s o u r c e ，s o u r c e 如果该操作码返回值，则保存在第一个参数里。参数可以是寄存器或者常数，但是仅源参数 可以是常数。有时作为第一个参数的寄存器可以既是操作码的源参数，也是存储结果的目的 寄存器。p a s m 共含有基本操作码、p m c 操作码、控制流操作码、栈和寄存器操作码等1 1 个类别接近2 5 0 个操作码。 标号命名一行代码以便其它指令引用。标号名由字符、数字和下划线组成。标号的定义 是名称加冒号。可以独立成行，如： l a b e l ： p r i n t “n o r w e g i a n b l u e h n ” 或在语句前和语句同行： l a b e l ：埘m ”n o r w e g i a n t 3 1 u e 、_ n ” 注释由“# ”开头至本行结束。 1 3 3p b c 文件 2 0 】 p b c 文件由文件头和各个段( s e g m e n 0 组成。文件头包含本p b c 文件的字长和版本号等 基本信息。目前定义了以下段： 目录段：紧随文件头之后，其它各段都在其中保存自己在p b c 文件中的位置。 未知段( 默认段) ：处理所有未定义段。 修正段：保存重定位信息。 常量表段：保存字节码文件中的常量。 代码段：保存指令流。 4 中国科学技术大学硕士学位论文第一章绪论 调试段：保存调试信息。 段由段头和各个段的额外数据组成，段头具有相同的结构，用于保存段的长度、类型等 信息。 代码段中的指令由操作码及零个或零个以上操作数构成，类似于p a s m 代码。但操作 码以整数编号表示，且对p a s m 的操作码做了更精细的划分。例如p a s m 的操作码p r i n t ， 被划分为打印整数( 3 7 6 ) 、浮点数( 3 7 8 ) 、p m c ( 3 8 2 ) 等不同的操作码。操作数保存在寄 存器中时，需要给出寄存器的编号。操作数是常数时，对于整数则直接给出该数值；对于其 它类型则将数值保存在常数段中，在操作码后绘出该数值在常数段中的偏移。如下的p a s m 程序： p r i n tn l p r i n t1 2 3 4 5 假设，常数1 2 3 4 5 在常数段中的偏移为0 ，则相应的p b c 指令为： 3 7 8 l3 7 90 由于p a s m 指令更易读，下文在介绍p a r r o t 时主要使用p a s m 指令。 1 4 论文的组织 第二章简单介绍p a r r o t 的结构，包括它的本地数据类型、运行时数据结构、内存管理机 制以及基本指令集等，并比较了p a r r o t 与j v m 的异同，在此基础上提出了移植的基本点和 难点。 第三至六章给出了p a r r o t 各个基本组成部分到j v m 的移植，包括本地数据类型、运行 时数据结构等的相应实现。 第七章主要介绍p a r r o t 到j v m 的移植中的一个难点，即动态编译的移植，详细分析了 p a r r o t 的c 实现中提供的各种动态编译实现方案，以及它们在j a v a 中相应的实现方法，并 给出了应用举例和测试分析。 第八章总结了论文的主要内容，讨论今后可以进一步开展的研究内容。 为简便起见，下文称p a r r o t 的c 语言实现版本为c p a r r o t ，我们用j a v a 语言实现的版本 为j p a r r o t 。 中国科学技术大学硕士学位论文第= 章p a r r o t 概述 第二章p a r r o t 概述 p a r r o t 是一个基于寄存器的虚拟机。它由p e r l 开发组设计开发，目标是作为p e r l 6 的解 释器。本章将对p a r r o t 的基本类型、运行时数据结构、内存管理系统以及动态编译做出介绍。 并根据它们比较p a r r o t 与j v m 的异同，提出移植所依赖的基本点以及移植中的难点。 2 1 p a r r o t 的整体结构1 2 0 。2 1 l 虚拟机是一个想象中的计算机，它有一套逻辑指令( 伪指令) ，这套伪指令定义了这个 想象中的计算机可以进行的操作。程序员编写的源代码被编译成虚拟机的指令之后，就能被 虚拟机理解并执行。简单地来说，虚拟机内部的工作便是将伪指令转变成相应的机器指令， 从而使指令被机器所识别井执行。 p a n o t 是一个基于寄存器的虚拟机系统。j a v a 、n e t 、p e r l 5 、r u b y 以及p y t h o n 则是基 于栈的系统。两者有何区别昵? 在基于栈的系统中，所有的操作都在栈中完成。当两数相加时，需要将操作数都入栈， 而后执行加法指令。加法指令从栈中取出位于栈顶的两个操作数，将它们相加，最后将操作 数放回栈中。这种系统易于实现，且为这种系统编写编译器也较为容易。这种系统的缺点是 需要花费大量的时间来处理栈，因为每个操作中除了完成实际的工作外都还需要移动栈指 针。 而基于寄存器的系统中，除非正在执行处理栈的代码，通常是不需要任何栈操作的。在 这种体系结构中，需要较少的维护，因而可以更快地执行代码。这种系统的缺点是指令流不 够密集( 指令需要指出该指令影响的寄存器) 。代码的产生也更为复杂，因为为这种系统产 生代码和为在基于栈的系统相比，还需要考虑寄存器的分配和管理。 p a r r o t 的整体结构如图2 1 所示，主要分为p b c 文件装载器、运行时数据区、内存管理 器和执行引擎四个部分。 其中，p b c 文件装载器负责根据给定的名称将p b c 文件装入内存，并解析该文件，将 所包含的信息保存到内部结构中。 执行引擎实现了p a r r o t 的本地数据类型和基本指令集，它负责执行那些包含在被装载的 p b c 文件中的指令。p a r r o t 拥有四种基本的本地数据类型：整数、浮点数、字符串和p m c 。 它所实现的基本指令集则包括十几个分类的1 3 0 0 多个操作码。执行引擎每次执行一条指令。 它取得指令中的操作码，如果操作码有操作数则取得操作数。它执行操作码和跟随的操作数 规定的动作，然后再取得下一个操作码。 当p a r r o t 虚拟机运行一个程序时，它需要内存来存储许多东西，例如：字节码、从己装 载的p b c 文件中得到的其它信息、程序创建的对象、传递给方法的参数、返回值、局部变 量以及运算的中间结果等等。p a r r o t 虚拟机把这些东西都组织到几个“运行时效据区”中， 以便于管理。p a r r o t 是基于寄存器的，因而它的运行时数据区中提供了丰富的寄存器。但也 提供了一些栈，以便完成在函数调用时保护现场等工作。p a r r o t 在运行时产生的对象等所需 的空间都从堆上分配。 6 中国科学技术大学硕士学位论文 第二章p a r r o t 概述 运行时数据区的管理，即内存的分配和回收主要由p a r r o t 的内存管理机制负责。p a r r o t 中内存管理被分为两部分：定长对象的管理和变长对象的管理，内存的回收也相应地采用了 两套算法。 困口口 运行时数据区 = ：工王： 困圈 内 存 管 理 器 执行引擎： j 图2ip a r r o t 的整体结构 2 2 本地数据类型 p a r r o t 中的整数和浮点数类型表示相对简单，分别对应于c 中的l o n g 和d o u b l o 。另外 p a r r o t 从内部提供任意精度浮点数( 包括整数) 的支持，但当前版本中只是部分实现，并未 将代码整合。下面只讨论字符串表示和p m c 。 2 2 1 宇符串 文本数据非常复杂，因而p a r r o t 将字符串作为基本的数据类型。所有以p a r r o t 为目标的 语言使用字符串类型相同的实现。随着计算机的发展，产生了字符串许多不同的表示方法， 例如a s c i i 码、u n i c o d c 标准等。 抽象地说，字符串是一系列有意义的整数。有三种和字符串相关的重要特性：编码、字 符集和语言，p a r r o t 知道如何处理它们。 字符串的编码说明如何将数据从一个字节流转化成一个由整数表示的字符流。类似 a s c i i 码的数据很容易处理，因为每个字符就是单独的一个字节，字符范围从。一2 5 5 。u t f - g 是u n i c o d e 的一种，则较为复杂，它的一个字符可能是l 一6 个字节。 字符串的字符集告诉p a r r o t 每个整数代表的意义。p a r r o t 需要了解整数6 5 代表a s c i i 码或者u n i c o d c 字符流中的字母“a ”。 最后，字符串的语言决定字符在上下文中的表现。不同的语言拥有不同的处理字符排列 和大小写字符的规则。 7 中国科学技术大学硕士学位论文 第二章p a r r o t 概述 p a r r o t 具各将字符串由个编码方式向另个转化或者从一个字符集转向另一个，以及 判断何时需要转化的能力。 2 2 2 p m c p m c 是p a r r o t 中基本的变量类型，它是个不透明的数据类型。p m c 可以保存单个的数 值、类似哈希表或者数组的聚合，以及对象。p m c 类型非常简单，并且具有面向对象的特 性。 每个p m c 拥有一组函数，保存在它提供的一个v t a b l e 表中。这些函数中包括高级的、 面向对象的函数，例如用来调用方法的函数；包括中级的函数，例如完成整数和当前p m c 的加法并返回值的函数：也包括低级的函数，例如返回当前p m c 所属的p m c 类型。这些 函数为定义和快速访问每个p m c 都必须表达的属性提供了便利，而不需要说明p m c 实现 这些属性的机制。 基于p m c 中v t a b l e 表具体实现的不同，p a r r o t 定义了5 0 种核，t 3p m c 。除“基类”d e f a u i t 外，这些核，t 5p m c 可以分为以下两类：处理数据类型的p m c 和处理运行控制的p m c 。前 者结合和一些支持结构，可以实现p o r l 中几乎所有的数据类型；后者则用于在处理跳转、 调用例程、抛出异常等程序控制指令时保存所需的信息。下文为了叙述方便，以某种类型的 p m c 指称v t a b l e 为某种类型的p m c ，事实上p a r r o t 文档中也做如此简化。 2 3 运行时数据结构 2 6 】 当前的p e r | 5 解释器是基于栈的它在操作码间通过栈交流数据。即将数据保存在栈 中，操作码从栈中取出数据，处理数据并将结果放回栈。这易于实现但是速度较慢：为了完 成两数相加，需要经历三次入栈和两次出栈。并且，栈在运行时需要增长，这意味着需要不 时地为栈重新分配内存。因而p a r r o t 试图打破虚拟机的传统，使用类似于大多数硬件c p u 的基于寄存器体系。以下将分别介绍p a r r o t 中的寄存器和栈。 2 2 1 寄存器 p a r r o t 提供四个类型的寄存器，每个类型拥有3 2 个寄存器： 1 0 一1 3l整型寄存器 n 0 n 3 1浮点类型寄存器 s 0 $ 3 1字符串类型的寄存器 p 0 - p 31p m c 类型寄存器 p a r r o t 之所以提供数量较大的寄存器，是因为寄存器用完会引起巨大的时间损失。每组 3 2 个寄存器是在时间和空闻之间较好的折中。 8 中国科学技术大学硕士学位论文 第二章p a r r o t 概述 2 2 2 栈 p a r r o l 拥有7 个不同的栈，每个栈都有特定的用途。上节的四个寄存器组各自拥有一个 专属的栈，以便迅速地保存寄存器的内容。整数栈专门用来保存和恢复单独的整数值，它经 常用于正则表达式系统。控制栈保存各种控制信息、异常处理等。而多用途栈则保存一些其 它的普通数值。 四类寄存器栈较为特殊。寄存器栈上的操作不仅影响单个寄存器，系统在一个操作中将 整个寄存器组出栈或者入栈。保存和恢复操作都是复制内存的操作。这使得这些栈的基本操 作在函数调用时保存寄存器非常迅速。 接数栈被设计来保存整数。因此，整数栈的操作非常迅速，这正是正则表达式使用整数 栈的原因。在正则表达式运算时，需要不停地在字符串中移动，这时即利用整数栈来保存回 退信息。 控制栈是解释器私有的，用户不可直接访问。解释器使用控制栈来保存异常处理，返回 函数调用的地址，以及追踪内部数据。 多用途栈用来保存和恢复个别寄存器。这是个定型的栈，因而不允许类似将整数入栈， 却将字符串出栈的操作。该栈常在例程需要多于3 2 个某类型的寄存器时使用。多出的数值 在被称作内存泄漏的操作中，被压入多用途栈或者从该栈中弹出。 所有p a r r o t 的栈都是分段的，它们由一组栈的段构成，而不是完整的一块内存。分段对 性能有一定的影响，但它可以更好地利用内存。传统的栈由一块完整的内存构成，这使得读 写栈较为迅速。但这块内存存满时，程序将出错。为避免发生这种情况，系统通常会为栈分 配较大的内存。当系统中只有一个栈时，这种分配方法是可行的。但在当前的多线程机制下， 每个线程都需要一个字节的栈，因而这种分配方法不适用。 分段的栈除了可以支持栈的动态增长，还使得p a r r o t 更易于实现程序的中断继续 ( c o n t i n u a t i o n s ) 以及协同程序( c o r o u t i n e s l 。 2 4 内存管理 许多现代语言都希望内嵌无用单元收集机制。这样程序员可以不必担心需要识别和清空 死对象。对于解释执行的语言，这需要解释器的支持，因而p a r r o t 提供了对无用单元收集的 支持。它拥有两个相互独立的内存分配系统，每个管理系统拥有自己的无用单元收集算法。 以下首先介绍无用单元收集，而后分别介绍这两种内存分配系统。 2 4 1 无用单元收集技术简介 2 r ，2 a 无用单元收集( g a r b a g ec o l l e c t i o n ，简称g c ) 是2 0 世纪6 0 年代出现的一种技术，用 来将程序最后一次使用堆分配的内存自动回收。 任何无用单元收集算法都必须做两件事情：首先，它必须检测出无用单元收集对象。其 9 中国科学技术大学硕士学位论文 第二章p a r r o t 概述 次，它必须回收无用单元收集对蒙所使用的堆空间并还给程序。 无用单元检测通常通过建立个根对象的集台，并检查从这些根对象开始的可到达性来 实现。不同的语言环境中根对象的集合也不相同，在p a r r o t 中根对象的集合主要包括栈和寄 存器中的对象等。如果正在执行的程序可以访问到的根对象和某个对象之间存在引用路径， 这个对象就是可4 达的。对于程序来说，根对象总是可以访问的。从这些根对象开始，任何 可以到达的对象都被认为是“活动”的对象。无法到达的对象被认为是无用单元，因为它们 不再影晌程序的未来执行。 下面分别简述3 种经典的无用单元收集算法：引用计数( r e f e r e n c ec o u n t i n g ) 、标记- 清 扫( m a r k - s w e e p ) 和节点复制( c o p y i n g ) 。 引用计数一般通过在分配的对象内部放置一个引用计数域来判断对象的生命期。该域在 对象分配时初始化为1 ，以后在指针操作时必须维护引用计数的不变式，b p 保持引用计数域 的数值与实际指向这个对象的引用数一致。任何引用计数为0 的对象可以被当作无用单元来 收集。当一个对象被无用单元收集的时候，它引用的任何对象计数值减1 。在这种方法中， 一个对象被无用单元收集后可能导致后续其它对象的无用单元收集行动。这种算法的主要缺 点是无法释放环形数据结构以及维护引用计数不变式的昂贵开销。 标记- 清扫在内存单元变成无用单元时保持不可到达和未被发现的状态，直到所有内存 耗尽，系统会挂起程序调用收集例程以嗡应新的内存需求。这种算法分为标记过程和清扫过 程。标记过程从根对象的集合出发遍历，标明所有可以到达的单元( 存活单元) 。在清扫过 程中，未被标记的单元被释放了，使用的内存被返回到正在执行的程序。这种算法的主要缺 点是无用单元收集运行时用户程序必须暂停。 节点复制将堆分成两个对等的区域，任何时候都只使用其中的一个区域。其中正在被使 用的包含现有数据的区域被称作f r o m s p a c e 区，未被使用的包含废弃数据的区域被称作 t o s p a c e 区。对象在同一个区域中分配，直到这个区域被耗尽。此时，程序执行被中止，堆 被遍历，遍历时遇到的活动对象被复制到另外个区域。当复制过程结束时，程序恢复执行。 内存将从新的堆区域中分配，直到它也被耗尽。那时程序将再次中止，遍历堆，活动对象又 被复制回原来的区域。这种算法的主要缺点是需要两倍的内存。 2 4 2p a r r o t 的内存管理 p a r r o t 中的定长对象管理系统负责处理p m c 和字符串结构。它们是定长对象，由p a r r o t 从定长对象舞台中分配，定长对象舞台则包含一组定长对象池。使用对象舞台，便于p a r r o t 对对象的查找和跟踪，并加快了检测死对象的速度。 p a r r o t 的死对象检测( d o d ) 系统首先遍历所有的对象舞台，并将所有的字符串和p m c 标记为死对象。然后遍历栈和寄存器，将其中日f 用的所有字符串和p m c 标记为活对象。接 着，它检查所有活着的p m c 和字符串，并标记它们引用的p m c 或字符串为活对象。最后， 清扫舞台，查找所有刚被标记为死对象的p m c 和字符串，将它们放入自由链表。这时，具 有析构函数( 如d e s t r o y ( ) 方法) 的p m c 需要调用该函数。死对象检测在p a r r o t 中没有空对 象时自动调用，或者由运行的代码显式调用。 1 0 中国科学技术大学硕士学位论文第二章p r o r o t 概述 p a r r o t 的变长对象分配系统用来为字符串和p m c 中保存的内容分配空间。它们从p a r r o t 维护的内存池中分配空间，分配的空间没有固定的长度。当p a r r o t 的内存池中没有空的内存 时将运行压缩空间的程序，以便从内存池中获得不再使用的空间。该程序运行后，每个内存 池的一端完全是正在使用的内存，另端则是空的内存。这加