内容


Jikes 研究虚拟机(RVM)

Thomas J. Watson 研究中心的 Jalapeno 研究项目的一个独立开发的部分

Comments

Jalape�o 是用 Java 语言编写的用于 Java 服务器的虚拟机。为了满足服务器的要求(尤其是性能和可伸缩性),Jalape�o 的设计是“从零做起”的,而且尽可能地自给自足。Jalape�o 的独特的对象模型和内存布局允许硬件空指针检查和数组元素、字段和方法的更快速访问。惯例上由本机代码提供的运行时服务也主要用 Java 实现。Java 线程由虚拟处理器(作为操作系统线程实现)进行多路复用。支持一系列并发对象分配器和一系列并行的类型确切(type-accurate)的垃圾回收器。Jalape�o 的可互操作的编译器使我们能够进行准抢先的线程切换和精确的对象引用定位。Jalape�o 的动态优化编译器是为了获得被认为会频繁执行的或计算密集的方法的优质代码而设计的。

最新一期 IBM 系统杂志中的本文和其它文章集中讲述了为最优化 Java 应用程序性能所做的最新努力。

Jalape�o 是用于服务器的 Java 虚拟机(Java virtual machine(JVM))。服务器上的内存限制不象其它平台那么紧。另一方面,用于服务器的 JVM 必须很好地满足如下这些要求(这些要求在客户机、个人电脑或其它嵌入式 JVM 上没这么严格):

  1. 高性能处理器的利用 ― 当前的即时(just-in-time(JIT))编译器并未在利用现代硬件的特性(内存层次结构、指令级并行、多处理器并行等)方面做大量的优化工作,而要获得能与静态编译语言相媲美的性能,就有必要利用这些特性。
  2. SMP 可伸缩性 ― 共享内存多处理器(Shared-memory multiprocessor(SMP))配置在服务器上很流行。有些 JVM 把 Java 线程直接映射到重量级操作系统线程。随着 Java 线程数的增加,这会导致 SMP 上的多线程 Java 程序的可伸缩性很差。
  3. 线程限制 ― 很多服务器应用程序都要为每个进入的请求创建新线程。然而,由于操作系统的约束,有些 JVM 无法创建很多的线程,因而只能处理有限数量的同时请求数。这些约束严重制约了需要同时支持成千上万个用户的应用程序。
  4. 连续可用性 ― 服务器应用程序必须能在长时间(例如,几个月)的连续运行中满足进入的请求。这看来不是当前的 JVM 优先考虑的问题。
  5. 快速响应 ― 多数服务器应用程序都有严格的响应时间要求(例如,至少有 90% 的请求都必须在 1 秒钟内得到服务)。然而,当前的很多 JVM 都使用非增量垃圾回收,导致了严重的响应时间故障。
  6. 库的使用 ― 用 Java 代码编写的服务器应用程序典型地建立在现有的库(bean、框架、组件等)的基础上,而不是“从零开始”写起。然而,由于这些库是为处理一般情形编写的,因此它们在当前的 JVM 上性能都很差。
  7. 适度的性能降低 ― 当向服务器提出的请求数超出了服务器满足请求的能力时,服务器性能的降低是可以接受的。服务器崩溃是 不能接受的。

在 Jalape�o 中,要求 1 由一个动态优化编译器来满足;对未显现为性能瓶颈的代码,我们提供了较轻量级的编译器。要求 2 和 3 通过 Jalape�o 中轻量级线程的实现来满足。用 Java 语言来实现 Jalape�o 满足了要求 4:Java 的类型安全性有助于写出正确的代码,而 Java 的自动存储管理则防止了“悬摆指针”并减少了“存储泄漏”。我们希望目前正在研究的并发及增量内存管理算法能满足要求 5。要求 6 将通过对 Jalape�o 优化编译器的专门化改造来满足,该编译器将用于库(例如)的动态地编译后的代码修改成服务器应用程序的调用上下文。虽然我们知道没有能保证满足要求 7 的编程方式,我们仍尽量不忽视它。

本文按以下方式组织。下一部分考虑实现问题。接着的部分给出 Jalape�o JVM,包括它的对象模型和内存布局以及运行时子系统、线程和同步子系统、内存管理子系统和编译子系统。接着的几部分研究 Jalape�o 优化编译器,描述 Jalape�o 的当前功能状况并给出一些初步的性能结果,还讨论了相关工作。最后一部分给出我们的结论。包含的两个附录用于解释 Jalape�o 的运行时服务如何为 Jalape�o 用户避开一些 Java 约束而仍然保持该语言的完整性,并描述自举 Jalape�op 的详细过程。

设计和实现问题

Jalape�o 项目的目标是“从零开始”生产出世界级的服务器 JVM。我们的方案是创建一个灵活的测试平台,您可以用这个平台探索、量度及评估新的虚拟机想法。我们的开发方法论是避免过早的优化:最初实施的是简单的机制,只有当发现它是性能瓶颈时才进一步加工它。

可移植性 不是一个设计目标:通过利用 Jalape駉的目标体系结构 ― PowerPC 体系结构 1 ― 运行 AIX(Advanced Interactive Executive(高级交互执行体)) 2 的 SMP(symmetrical multiprocessors(对称多处理器))的独特功能可以获明显的性能好处 ― 我们感到有必要采用它。这样,Jalape�o 的对象布局和锁定机制都是完全特定于体系结构的。另一方面,我们也清楚将来可能需要把 Jalape�o 移植到其它一些平台上。因此,在性能不是问题的地方,我们尽量使 Jalape�o 的可移植性更好。在性能和可移植性一样重要的地方,我们尽量降低 Jalape�o 对宿主操作系统的依赖。

用 Java 语言构建 Jalape�o 的原始驱动力是想看看是否可以这样做。 3 使用现代的、面向对象的、类型安全的还带有自动内存管理功能的编程语言所带来的开发回报是相当可观的。(例如,我们没有碰到悬摆指针错误,除了那些由拷贝垃圾回收器的早期版本引入的错误,这些错误必需地避开 Java 内存模型(Java memory model)。我们也希望从 Java 开发中获得性能方面的好处:首先,无须执行桥接用户代码和运行时服务之间的内部语言间隙的代码;其次,由于这种无缝操作,优化编译器可以同时优化用户和运行时代码,甚至可以频繁地编译在用户代码中内联的运行时服务。

Jalape�o 实现有时必须避开 Java 语言的限制。同时,Jalape�o 的用户必须强制遵守这些限制。 附录 A给出了 Jalape�o 实现这些受控规避的机制。

Jalape�o 只有极小一部分 不是用 Java 语言写的。Jalape�o 虚拟机被设计成作为用户级 AIX 进程运行。因此,它必须使用宿主操作系统,以访问底层的文件系统、网络和处理器资源。要访问这些资源,我们面临一个选择:可以用低级系统调用约定来调用 AIX 内核,或者可以通过标准 C 库来访问 AIX 内核。我们选择后一种办法以使我们不依赖特定于发行版的操作系统内核。这就要求 Jalape�o 的一小部分要用 C 而不是 Java 代码编写。

到现在为止,所需 C 代码的总数很少(约 1000 行)。这些代码中的约一半由一些简单的“粘合”函数组成,这些函数在 Java 方法和 C 库之间中继调用。这些代码的唯一目的是在 Java 格式和 C 格式之间转换参数和返回值。C 代码的另外一半由一个“引导”装入程序和两个信号处理程序组成。引导装入程序负责给虚拟机映象分配内存,把映象从磁盘读入内存,并转到映象的启动代码分支(请参阅 附录 B)。第一个信号处理程序捕获硬件陷阱(由空指针解除引用产生)和陷阱指令(因数组边界检查和被零除检查而生成),并将它们连同寄存器状态的快照一起中继到虚拟机。另一个信号处理程序把定时器中断(每隔 100 毫秒生成)传递给运行中的 Jalape�o 系统。

JVM 的组织

下面的几部分描述 Jalape�o 的对象模型(object model)、运行时子系统(run-time subsystem)、线程和同步子系统(thread and synchronization subsystem)、内存管理子系统(memory management subsystem)和编译器子系统(compiler subsystem)。

Java 对象的布局考虑了这几个因素:能实现对字段和数组元素的快速访问,能实现硬件空指针检查,能提供四指令虚方法调度,能进行执行频度较低的操作如同步、类型确切的垃圾回收以及散列。同时也支持对静态对象和方法的快速访问。

在传统的 JVM 中,运行时服务 ― 异常处理,动态类型检查,动态类装入,接口调用,输入和输出,反射(reflection)等等 ― 都是用写成 C、C++ 或汇编程序的 本机方法实现的。在 Jalape�o 中,这些服务主要用 Java 代码实现。

Jalape�o 在 虚拟处理器上对 Java 线程进行多路复用,不是把 Java 线程作为操作系统线程实现,而是在虚拟处理器上把 Java 线程作为 AIX pthread 实现。 4 Jalape�o 的锁定机制的实现无须操作系统支持。

Jalape�o 支持一系列内存管理器,每个内存管理器由一个对象分配程序和一个垃圾回收器组成。所有分配程序是并发的。当前,所有回收器都是阻止一切的、并行的和类型确切的回收器。繁衍的和不繁衍的,拷贝的和非拷贝的管理器都被支持。增量回收器正在研究之中。

Jalapeno 不解释字节码。而是在执行之前把这些字节码编译成机器代码。Jalape�o 支持三个可互操作的编译器,它们处理开发期间、编译期间和运行期间的之间的不同权衡问题。这些编译器是 Jalape�o 设计整体的组成部分:它们支持了线程调度、同步、类型确切的垃圾回收、异常处理以及动态类装入。

对象模型和内存布局
Java 语言中的值或者是 基本类型(例如,int,double 等)或者是对象 引用(即指针)。对象或者是包含元素的 数组或者是包含字段的 标量。Jalape�o 的对象模型依从四条标准:

  • 字段和数组访问应是快速的。
  • 虚方法调度应是快速的。
  • 空指针检查应由硬件执行。
  • 其它(执行频度较低的)Java 操作不应慢得造成抑制。

假设对象引用保存在一个寄存器中,那么就可以只用一条指令以固定的偏移访问对象的字段。为简化对数组的访问,我们让对数组的引用指向数组的第 1 个(下标为 0)元素,余下的元素按升序分布。数组元素的数量,即数组的 长度,就保存在第 1 个元素前面。

Java 语言要求,如果试图通过空对象引用访问对象,那么将产生 NullPointerException。在 Jalape�o 中,引用是机器地址且用“地址 0”表示空(null)。AIX 操作系统允许从低端内存装入东西,但当访问超高端内存(从空指针 偏移一点)时,通常会导致硬中断。 5 这样,对偏离空 Jalape�o 数组引用地址的访问的尝试将被硬件捕获,因为数组访问要求装入数组长度,数组长度偏离数组引用 4 个字节。将字段定位在对象引用的负偏移位,使对字段访问的硬件空指针检查受到影响。

总之,在 Jalape�o 中,数组从对象引用(数组长度位于固定的负偏移位置)处 向上生长,而标量对象则从对象引用处 向下生长,标量对象的所有字段都位于负偏移位置(请参阅图 1)。只用一条指令以基址-偏移(base-displacement)方式寻址即可完成对字段的访问。大多数数组访问需要三条指令。一条陷阱指令即可验证索引是在数组的边界内。除了字节型(和布尔型)数组,其它数组的元素索引然后都必须转成字节型索引。访问本身是用基址-索引(base-index)寻址方式完成的。

对象头(Object header)。每个对象都有一个两个字长的对象头与之相联系。这个头支持了虚方法调度、动态类型检查、内存管理、同步以及散列。它的位置在比对象引用的值低 12 字节的地方。(这为对象是一个数组的情况留了一个存放数组长度字段的空间,请参看 图 1。)

头中的一个字是 状态字。状态字分成三个 位字段。第一个位字段用于锁定(稍后论述)。第二个位字段保存散列对象的缺省散列值。第三个位字段由内存管理子系统使用。(这些位字段的大小取决于编译时常数。)

对象头的另一个字是本对象的类的 类型信息块(Type Information Block(TIB))的引用。TIB 是由 Java 对象引用组成的数组。它的第一个元素描述对象的类(包括类的超类,类实现的接口,任何对象引用字段的偏移量等等)。余下的元素是类的虚方法(Virtual method)的编译后的方法体(可执行代码)。这样,TIB 就作为 Jalape�o 的虚方法表(virtual method table)。

虚方法。方法体是机器指令(int s)的数组。一个虚方法调度牵涉装入 TIB 指针(位于与对象引用有一个固定偏移量的地方),装入方法体(位于从 TIB 指针偏移给定偏移量的地方)的地址,把这个地址移入 PowerPC “链接寄存器(link-register)”,以及执行一条转移和链接(branch-and-link)指令 ― 共四条指令。

静态字段和方法(及其它)。所有静态字段和所有静态方法体的引用都存储在一个名为 Jalape�o 内容表(Jalape�o table of Contents,JTOC)的数组中。这个数组的引用被保存在一个专用机器寄存器(JTOC 寄存器)中。Jalape�o 的所有全局数据结构都可以通过 JTOC 访问到。文本、数值常数和字符串常数的引用也都存储在 JTOC。为了能够快速进行普通情况动态类型检查,JTOC 也为系统中的每一个类保存其 TIB 引用。图 2 描绘了 JTOC。尽管 JTOC 被声明为 int s 数组,但它包含所有类型的值。一个与 JTOC 一起被索引的 JTOC 描述符数组标识了包含引用的条目。

方法调用堆栈(Method invocation stack)。图 3 描绘了 Jalape�o 的堆栈布局。每个方法调用都有一个堆栈帧。(优化编译器将删除叶方法和内联方法的堆栈帧。)堆栈帧包含用于保存非易失性寄存器的空间,一个用途依赖于编译器的本地数据区,还有一个用于保存参数的区域,这些参数将被传递给被调用方法,而且不适合被放在 Jalape�o 的易失性寄存器中。堆栈帧的最后三个字是:一个 编译后的方法的标识(堆栈帧的方法的标识信息),一个 指向下一条指令的指针(任何 被调用方法的返回地址)和一个 指向前一帧的指针

方法调用堆栈和 JTOC 是仅有的两个违反 Java 语言规定的 Jalape�o 结构,Java 语言规定数组不能同时包含基本类型和引用。因为方法调用堆栈和 JTOC 都不能被用户直接访问,所以这并不是一个安全性疏忽。然而,为了使类型确切的垃圾回收更容易,Jalape�o 的编译器必须维护引用映射表(reference map)(稍后论述)以使我们能够找到堆栈中的对象引用的位置。

运行时子系统
通过巧妙使用 MAGIC 类(请参阅 附录 A),Jalape�o 的运行时子系统用 Java 代码(多数)提供服务 ― 异常处理、动态类型检查、动态类装入、接口调用、I/O、反射等等 ― 这些服务惯常是用本机代码实现的。

异常。如果空指针被解除引用、数组索引越界、整数被零除或者线程的方法调用堆栈溢出,那么就将产生硬中断。一个小型的 C 中断处理程序将捕获这些中断并使一个 Java 方法运行。这个方法构造适当的异常并将异常传给 deliverException 方法。软件生成的异常也调用 deliverException 方法。这个方法有两项任务。首先,它必须保存异常对象信息,以便在有需要时能打印堆栈跟踪。它通过向上"遍历"堆栈并记录每个堆栈帧的编译后的方法的标识和指向下一条指令的指针来完成这项任务。其次,它必须把控制转到适当的“catch”块。这也涉及遍历堆栈的步骤。对每一个堆栈帧,它定位方法体(这个方法体生成堆栈帧)的编译后的方法对象。它调用这个对象的一个方法来判断异常是否恰巧在适当的“try”块。如果是这样,控制就被转到相应的 “catch” 块。如果不是这样,那么释放该堆栈帧占用的任何锁,而且也释放该堆栈帧。如果未找到 catch 块,该线程就被杀死。

动态类装入。Java 语言的一个创新特色是在应用程序的执行期间装入类。当 Jalape�o 编译器碰到一个字节码(例如 putstatic 或 invokevirtual)― 该字节码引用了尚未被装入的类 ― 时,编译器不是立即装入该类。相反地,编译器生成那些在第一次 被执行时确保了所引用的类已经被装入(解析并实例化)的代码,然后完成操作。注意,当这些代码被生成时,编译器无法知道该类的字段(例如,指定给一个静态字段的 JTOC 索引)和方法的实际偏移量(因为它们未被指定,直到该类被装入)。基线编译器(baseline compiler)(Jalape�o 的编译器都稍后论述)通过生成一些代码来处理这种不确定情况,这些代码调用运行时例程,运行时例程将执行任何必要的类装入操作,然后用基线编译器已经生成(如果已在最初代码生成期间解析了类的话)的代码来覆盖调用点。在处理器与松散内存聚合模型相连的 SMP 上,这将特别棘手。 6

优化编译器采用另一种方案,这种方案基于额外添加的一级间接;当编译器被执行时,编译器生成的代码从偏移数组中装入一个值。如果偏移值是有效的(非零值),它就被用来完成操作。如果偏移值无效,就装入所要求的类,在此过程中,偏移数组被更新以包含类的所有方法和字段的有效值。对每一个动态链接点,基线编译器的方案使得第一次执行该点时,开销非常大,但随后的执行则不产生开销,而优化编译器的方案在每次执行该点时,会产生很小的开销。然而,优化编译器通常不会被一个方法调用,直到该方法被执行多次;对任何动态链接点,这个编译器看来可以假设极少被执行。哪种办法最适合于快速编译器(quick compiler)仍不清楚。

输入和输出。I/O 需要操作系统支持。要从一个文件读一个块,须构造一个 AIX 堆栈帧并用一个地址调用(通过 C 库)一个操作系统例程,该地址用于拷贝它的结果。这个地址是一个 Java 数组。要小心防止垃圾回收器副本移走对象,直到调用完成(请参阅 附录 A 了解详细信息)。到目前为止,我们尚未观察到因把垃圾回收一直延迟到读操作完成带来的性能降低问题。其它 I/O 服务的处理相似。

反射。Java 的反射机制允许对字段的运行时访问(给定字段的名称和类型)和对方法的运行时调用(给定方法的说明)。Jalape�o 很容易就可支持反射字段访问:名称被转换成偏移量,在裸内存地址执行访问。反射方法调用要困难一点。通过在一个表中查找方法的说明获得方法体的地址。构造了一个人工堆栈帧。(因为这个堆栈帧不包含任何对象引用,所以没必要为它构建一个引用映射表。)方法的参数被小心地分解并装入寄存器。于是就调用了一个方法。当方法返回时,必须清除人工堆栈帧,而把结果包起来并返回给反射调用。

线程和同步子系统。
不是把 Java 线程直接映射到操作系统线程,Jalape�o 在 虚拟处理器上多路复用 Java 线程,虚拟处理器是作为 AIX pthread 实现的。这样做是基于三个考虑。我们要能够实现变形(通过正常线程)和垃圾回收之间的快速切换。我们想不使用 AIX 服务而实现锁定。我们想支持快速线程切换。

目前,Jalape�o 为每一个物理处理器建立一个虚拟处理器。另外的虚拟处理器最终将用于屏蔽 I/O 延迟。这个子系统需要的唯一一项 AIX 服务是 incinterval 系统调用提供的周期定时器中断。Jalape�o 的锁定机制不产生系统调用。

准强占式(Quasi-preemption)。Jalape�o 的线程既不是“运行直至被阻塞(run-until-blocked)”的也不是完全强占式的。依赖自动让出将使得 Jalape�o 不能保证满足服务器环境发展的需要。我们觉得任意抢先会极大地将垃圾回收和线程堆栈上的对象引用标识之间的切换复杂化。在 Jalape�o 中,一个线程可以被抢先,但只能在预定义的 让出点(yield point)被抢先。

编译器在让出点为线程堆栈上的对象引用提供位置信息。堆栈上的每个方法都在一个 安全点(safe point)(稍后论述)。这使得编译器能够在安全点之间优化代码(例如,通过维护一个内部指针),如果允许任意抢先,这些安全点将阻止类型确切的垃圾回收。

。SMP 上的并发执行要求同步。线程调度和负载平衡(尤其是)要求对全局数据结构进行原子访问。用户线程访问它们的全局数据也需要同步。为同时支持系统和用户同步,Jalape�o 提供了三种锁。

处理器(processor)锁是低级原语,用于线程调度(和负载平衡),也用于实现 Jalape�o 的其它锁定机制。处理器锁是 Java 对象,它只有一个字段,用于标识拥有这个锁的虚拟处理器。如果该字段为空,则这个锁就未被拥有。处理器的标识保存在一个专用的 处理器(PR)寄存器。虚拟处理器要为它运行的线程获取一个处理器锁,就将:

  • 装入设置一个 CPU 保留(PowerPC lwarx)的锁所有者字段
  • 验证该字段为空
  • 在一定条件下把 PR 寄存器存储到该字段(PowerPC stwcx)

如果 stwcx 成功,虚拟处理器就拥有了该锁。如果所有者字段不空(另一个虚拟处理器拥有了该锁),或者 stwcx 指令失败,则虚拟处理器将重试(也就是说,自旋(spin))。通过把空值(null)存储到所有者字段来实现一个处理器锁的解锁。处理器锁不能被递归地获取。因为处理器锁“忙等待(busy wait)”,所以对它的占用时间间隔必须极短。当一个线程拥有一个处理器锁时,它不能被切换,有两个原因:因为在继续执行前,它不能释放该锁;因为我们的实现将不适当地把锁的所有权转给在虚拟处理器上执行的其它线程。

Jalape�o 的其它锁定机制的基础是 瘦锁(thin lock) 7 8 不存在争用时,对象头的位用于锁定;存在争用时,这些位则标识一个重量级锁(heavyweight lock)。Jalape�o 的做法有两点与以前不同。在以前的做法中,重量能锁定机制是一个操作系统服务;这里则是一个 Java 对象。这里,如果“线程 A”有一个某对象的瘦锁,则“线程 B”可以把这个锁提升为 厚锁(thick lock)。在以前的做法中,只有拥有瘦锁的线程才能提升它。

对象头(请参阅前面的讨论)的状态字中的一个位字段用于锁定。这个位字段的一个位标明是否有一个厚锁与对象相联系。如果是这样,则这个位字段的其余位就是这个锁在全局数组中的索引。这个数组被分成若干个虚拟处理器区以允许对厚锁的非同步分配。如果该厚锁位未被设置,则位字段的其余部分被分成两部分: 瘦锁所有者(thin-lock owner)子字段标识了占用该对象的瘦锁的线程(如果有的话)。(位字段的大小可以调整,支持的线程数可高达 50 万。) 递归计数(recursion count)子字段保存锁所有者占用锁的次数:不象处理器锁,瘦锁可以被递归地获取。如果一个对象未被锁定,则整个锁定位字段为零。

为获取一个瘦锁,线程把瘦锁所有者位字段设置为自己的标识。只当锁定位字段为零时才允许这样做。当前正在一个虚拟处理器上运行的线程的标识保存在一个专用的 线程标识(thread identifier(TI))寄存器。lwarx 和 stwcx 指令再次被用来确保自动获取瘦锁。

厚锁是一个有六个字段的 Java 对象。mutex 字段是一个处理器锁,用于同步对厚锁的访问。associatedObject 是一个对象引用,该对象是厚锁当前管理下的对象。ownerId 字段包含拥有该厚锁的线程(如果有的话)的标识。recursionCount 字段记录所有者锁定该锁的次数。enteringQueue 字段是正在争用该锁的线程队列。而 waitingQueue 字段则是正在等待 associatedObject 的通知的线程队列。

要把一个瘦锁转换成一个厚锁,必须:

  1. 创建一个厚锁
  2. 获取它的 mutex
  3. 装入该对象的状态字以设置一个保留(lwarx)
  4. 在一定条件下把适当的值 ― 厚锁位设置和这个厚锁的索引 ― 存储(stwcx)进对象头的锁定位字段
  5. 重复步骤 3 和 4 直到有条件的存储成功
  6. 填充该厚锁的字段以反映对象的状态
  7. 释放厚锁的 mutex

关于 PowerPC 上的锁定有两点要详细考虑。第一,(lwarx 的)保留除因争用外还有各种原因可能会被丢失,包括与该保留的字相同的高速缓存行的存储或者虚拟处理器的操作系统上下文切换。第二,在释放一个锁(任何类型)之前,必须执行一个同步以确保其它 CPU 上的高速缓存看到在锁被占用期间所做的任何变化。类似地,在获取一个锁之后,也必须执行一条 isync 指令以使随后的指令不会在一个过时的上下文中执行。

线程调度(thread scheduling)。Jalape�o 实现了一个瘦线程调度(lean thread scheduling)算法,设计该算法是为了有一个短的路径长度,把同步降到最少并为负载平衡提供一些支持。线程切换(和锁)用于实现准抢先,也用于实现 java.lang.Object 的 yield 和 sleep 方法以及 java.lang.Thread 的 wait、notify 和 notifyAll 方法。一个线程切换由以下操作组成:

  • 保存老线程的状态
  • 从等待执行的线程队列中删除一个新线程
  • 把老线程放到某个线程队列(如有必要,锁定该队列)
  • 释放监视对这个队列的访问的进程锁(如果有的话)
  • 恢复新线程的状态并恢复它的执行

在与虚拟处理器相联系的处理器对象中有三个可执行线程的队列。idleQueue 保存一旦没有别的事可做时就将执行的空闲线程。readyQueue 保存其它执行就绪(ready-to-execute)的线程。只有与它们相联系的虚拟处理器才能够访问这两个队列,因此,更新时不需要锁定它们。这个虚拟处理器是唯一能从 transferQueue 中把线程除去的虚拟处理器。然而,其它虚拟处理器可以把线程放入这个队列,所以对它的访问要用一个处理器锁来同步。transferQueue 用于负载平衡的目的。

管程(monitor)。Java 语言支持 管程抽象 9 以允许用户级同步。从概念上说,每一个 Java 对象都有一个管程与它相联系。然而,极少有管程曾被用到过。典型情况下,线程通过执行对象的同步方法来获取对象的管程。一次只能占用少数管程。一个线程可以(递归地)多次获取同一个管程,但没有线程能够获取另一个线程占用的管程。Jalape�o 用它的锁定机制来实现这种功能。

当一个线程试图获取一个对象的管程时,有六种情况,这取决于谁拥有该对象的管程以及该对象是否有一个与之相联系的厚锁:

  1. 对象未被拥有 ― 没有厚锁。就象前面所说的一样,线程获取对象的瘦锁。(这是到目前为止最普遍的情况。)
  2. 对象被这个线程拥有 ― 没有厚锁。线程用 lwarx 和 stwcx 指令把状态字的递归计数位字段加 1。这个同步是必须的,因为另一个虚拟处理器可能正同时把该瘦锁转换为厚锁。如果这个位字段溢出,那么这个瘦锁就被转换成厚锁。
  3. 对象被另一个线程拥有 ― 没有厚锁。这是一种有趣的情况。有三种选择。线程可以:重试(忙等待),让出并重试(给另一个线程一次执行的机会)或者把瘦锁转换成厚锁(情况 6)。我们正在研究这三种选择的各种组合。
  4. 对象未被拥有 ― 有厚锁。我们获取厚锁的互斥锁(mutex),验证该锁仍与对象联系在一起,把线程索引(thread index(TI))寄存器存储到 ownerId 字段,然后释放互斥锁。到互斥锁被获取时,可能厚锁已经被解锁,甚至已经解除和对象的联系。在这种极其少见的情况中,线程开始试图获取对象的管程。
  5. 对象被这个线程拥有 ― 有厚锁。我们杀死 recursionCount。由于只有拥有厚锁的线程才能够访问厚锁的 recursionCount 字段(或者释放该锁),所以同步是不需要的。
  6. 对象被另一个线程拥有 ― 有厚锁。我们获取互斥锁,验证该锁仍然与适当的对象联系在一起,并让给 enteringQueue,同时释放互斥锁。

我们正在研究两个与释放管程有关的问题:当一个厚锁被解锁时,要对 enteringQueue 中的线程做些什么;何时解除一个对象和一个厚锁的联系。

内存管理子系统
在 Java 语言的所有特征中,自动垃圾回收可能是最有用的,要高效实现它,也是最有挑战性的。有很多途径可以实现自动内存管理, 10 11 但没有哪一条途径在服务器环境中具有明显的优越性。Jalape�o 被设计成支持一系列可互换的内存管理器。当前,每个管理器由一个并发对象分配器和一个阻止一切的、并行的、类型确切的垃圾回收器组成。得到支持的四个主要的管理器类型是:拷贝、非拷贝、繁衍拷贝和繁衍非拷贝。

并发对象分配。Jalape�o 的内存管理器把堆分区分为 大型对象空间小型对象空间。每个管理器使用一个非拷贝大型对象空间,这种空间被象管理一系列页面那样管理。用首次拟合法来满足对大型对象的请求。进行一次垃圾回收之后,邻近的空闲页面被合并。

为了通过拷贝管理器支持对小型对象的并发分配,每个虚拟处理器维护一大块本地空间,在这个空间上,对象不用请求同步就可获得分配。(这些本地大块空间不是逻辑上独立于全局堆的:由一个虚拟处理器分配的对象可被任何获取该对象引用的虚拟处理器访问。)分配通过把空间指针按所要求的大小增大并将增大后的结果与本地大块空间的边界比较来完成。如果比较失败(不是正常情况),则分配器自动从共享全局空间获得一个新的本地大块空间。这种技术不要求锁定,除非有人请求一个新的大块空间。维护本地大块空间的代价是内存碎片会轻微增加,因为每个块可能不会完全拟合。

非拷贝管理器把小型对象堆分成固定大小的块(当前是 16 千字节)。每个块再被动态地细分成固定大小的槽(slot)。这些槽的数量(当前是 12)和大小都是编译时常数,编译时常数可被调优以拟合所观察到的小型对象大小的分布。当分配器收到一个空间请求时,它判断能满足请求的最小的槽的大小,并获得该大小的当前块。为免除锁定开销,每个虚拟处理器维护每个槽的一个本地的当前块。如果当前块已满(不是正常情况),则虚拟处理器就查找下一个其空间对当前块可用的块。如果所有这样的块都是满的(更是少见),则虚拟处理器从共享池获得一个块并将新获得的块作为当前块。由于块的大小和槽大小的数量都相当小,所以为每个虚拟处理器拷贝当前块的空间影响是无足轻重的。

从变化到回收。每个虚拟处理器都有一个回收器线程与之相联系。Jalape�o 以两种方式之一运作:或者变化器(正常线程)运行而回收线程空闲,或者变化器空闲而回收线程运行。当变化器显式地提出请求时,当变化器提出分配器不能满足的一个空间请求时,或者当可用内存的数量低于预设的阈值时,垃圾回收就被触发。

可伸缩性要求方式间的切换尽可能地敏捷。在变化期间,所有的回收器线程都处于等待状态。当一个回收被请求时,回收器线程接到通知并被调度(通常是作为下一个要执行的线程)到它的虚拟处理器。当一个回收器线程开始执行时,它将禁用它的虚拟处理器上的线程切换,让其它回收器线程知道它已控制了虚拟处理器,执行一些初始化并与其它回收器同步(在第一个集中点(rendezvous point),稍后论述)。当每个回收器都知道其它的正执行时,切换就完成了。

注意,当所有回收器线程在运行时,所有的变化器都必须位于让出点。没有必要重新调度以使任何先前暂挂的变化器线程到达这一点。当变化器线程的数量很大时,这可能会对性能有重大影响。由于 Jalape�o 中的所有让出点都是安全点,所以回收器线程现在可以继续进行回收工作。

完成回收之后,回收器线程重新启用它的虚拟处理器上的线程切换,然后等待下一个回收。当回收器线程释放它的虚拟处理器时,变化器线程自动启动。

并行垃圾回收。Jalape�o 的垃圾回收器被设计成以并行方式执行。回收器线程于三个阶段的每个结束点在回收器线程之间同步。为此,Jalape�o 提供了一个集中机制,在集中点,没有线程可以继续向前执行,直到所有的线程都到达集中点。

初始化阶段,拷贝回收器线程拷贝它自己的线程对象和虚拟处理器对象。这确保了对这些对象的更新作用在新的副本上,而不是老的副本,后者在回收之后将被废弃。

非拷贝管理器让每一块内存与一个标记(mark)数组和一个分配(allocation)数组联系在一起,每个数组都有一个到每个槽的条目。在初始化期间,所有标记数组的条目都被置零。所有回收器线程都参与这个初始化。

根标识(root identification)和扫描阶段,所有回收器的行为都相似。回收器线程争用 JTOC 和每个变化器线程堆栈,并行地扫描它们以获得根(就是说,从概念上说,对象引用在堆外),这些根被标记并被放到一个工作(work)队列。然后标记可从工作队列访问的对象。标记操作被同步,所以一个回收器正好标记一个活动对象。作为标记一个对象的一部分,拷贝回收器将把它的位拷贝到新空间并用指向该新拷贝的 转发指针覆盖老副本的状态字。(这个指针的低位中的一位被设置以表明该对象已被转发。)

JTOC 中的根通过检查联合检索描述符数组来标识,这个数组标识了每个条目的类型。线程堆栈中的根通过分析与每个堆栈帧相联系的方法来标识。特别地,本地数据区将拥有堆栈帧的任何普通根;参数溢出区将拥有下一个(被调用)方法的堆栈帧的根;非易失性寄存器保存区可能包含来自一些早期堆栈帧的根。根的定位是这样实现的:检查相应于堆栈上的方法的编译器构建的引用映射图并跟踪哪个堆栈帧保存了哪个非易失性寄存器。

全局工作队列在虚拟处理器本地块中实现,以避免过多的同步。从工作队列除去的对象被每个对象引用 扫描。(这些引用的偏移量是从类对象中获得的,该类对象是对象的 TIB 的第一个条目。)对每一个这样的引用,回收器都试图标记该对象。如果成功,回收器就把该对象添加到工作队列。在拷贝回收器中,标记操作(不管是成功还是失败)返回引用对象的新地址。

完成阶段,拷贝回收器只是反向设置堆的占用和可用部分。回收器线程从当前空闲的“托儿所”获得本地大块空间以为下一个变化器循环作准备。非拷贝回收器线程执行以下步骤:

  • 如果这是繁衍回收器的一个小型回收,那么就把所有老对象标记成活动的(从当前分配数组中识别)。
  • 扫描所有标记数组以找出空闲块并将它返回给空闲块表(list)。
  • 对于所有块都不空闲的情况,交换标记和分配数组:老标记数组中的未标记条目标识了可用于分配的槽。

性能问题。我们正积极研究非拷贝和拷贝内存管理器,为的是更充分地理解哪种情况下谁是首选,并为研究混合解决方案提供可能。(非拷贝大型对象空间即是混合解决方案的一个示例。)拷贝内存管理器的主要优点是对象分配的速度快和在回收期间执行了堆的压缩操作(有更好的高速缓存性能)。非拷贝内存管理器的主要优点是回收更快(对象未被拷贝)、更好地使用了可用空间(拷贝管理器浪费了其中一半)以及变化器和回收器之间的交互作用更简单。(如果不必考虑对象可能会在每个安全点移动,那么优化编译器将会执行更强烈的优化。)使用拷贝管理器的系统,其回收之间的运行将整体上更快;使用非拷贝管理器的系统的暂停次数将更少。

非拷贝策略将极大地简化 并发内存管理器(其中的变化器和回收器同时运行):它不需要读障碍(read barrier)并简化了写障碍(write barrier)。

编译器子系统
Jalape�o 通过在运行时把字节码编译为机器指令来执行它们。三个不同但兼容的编译器已经投入使用或正在开发之中。Jalape�o 的开发基于一个早期的显然正确的可用的编译器上进行。这是 Jalape�o 的 基线编译器的角色。然而,顺便说一下,它不生成高性能的目标代码。

为获得被认为是计算密集的方法的优质的机器代码,Jalape�o 的 优化编译器(下一部分讲述)应用了大量新的、特定于动态 Java 上下文的优化措施,同时也应用了传统的静态编译器的优化措施。若将优化编译器用在只是偶而执行的方法上,则运行优化编译器的代价与得益相比是太高了。

Jalape�o 的 快速编译器将在每个方法第一次执行时对方法进行编译。它通过应用一些高效的优化措施来平衡编译时间和运行时间开销。寄存器分配是这些措施中最重要的,因为 PowerPC 有大量(32 个定点,32 个浮点)寄存器资源,而且多数寄存器操作是一个周期的,而存储器引用可能需要几个(有时很多个)周期。

快速编译器通过全面使用尽量少的转换、有效的数据结构以及尽量少传递源和派生数据的办法来尽量限制编译时间。源字节码不被转换成中间表示。相反地,字节码用分析和优化的结果“装饰”后被放入到与每一条字节码指令相关的对象。优化操作包括副本传播以清除由 Java 字节码基于堆栈的天然特性引入的临时文件。快速编译器的主寄存器分配器使用图染色算法。 12 染色对有些方法(例如,需要很多符号寄存器的 long one-basic-block static 初始化器)是不合适的(由于编译时间长)。对于这样的方法,快速编译器有一个更简单、更快的算法。我们将研究检测这些情况的试探法。我们也计划添加最后(final)、静态(static)的短(short)方法或构造器的内联编译并探索本地上下文(孔颈(peephole))优化。

由所有三个编译器生成的代码必须符合 Jalape�o 的调用和抢先约定。它们确保线程执行它所编译的方法时将会实时地对抢先这些线程的尝试作出响应。当前,显式让出点被编译成方法前言(prologue)。最后,循环的“后边缘”将需要让出点,循环不可包含其它让出点。

编译器也负责维护用于支持异常处理和使内存管理器能找到线程堆栈上的引用的表(table)。(Jalape�o 的调试器也使用这个表。)当一个垃圾回收事件发生时,线程堆栈代表的每个方法都将位于垃圾回收的 安全点。安全点是调用点、动态链接点、线程让出点、异常抛出的可能点和分配请求点。对方法体内的任何给定的安全点,创建该方法体的编译器必须能描述活动引用存在于哪里。 引用映射表为每个安全点标识了对象引用的位置。

我们仍未找到为方法选择编译器的一个全面的策略。从快速到优化编译器的切换将在运行时以 Self 方式完成。 13 14

动态优化编译器

我们希望 Java 应用程序的计算部分只涉及 Java 源代码的一小部分。Jalape�o 的优化编译器致力于高效地编译这些字节码。优化编译器是 动态的:它在应用程序运行时编译方法。将来,优化编译器也将是 自适应的:它将在计算密集的方法上被自动调用。优化编译器的目标是在给定的编译时间预算内生成所选定方法的尽可能好的代码。此外,它的优化必须在正确地保护异常、垃圾回收和线程的 Java 语义的同时很大地提高性能。对实现 SMP 服务器的可伸缩性性能来说,降低同步和其它线程原语的花费尤其重要。最后,以最少的工作量把优化编译器的目标重定向到各种硬件平台应是可能的。构建达到这些目标的动态优化编译器是一个很大的挑战。

这个部分提供了 Jalape�o 优化编译器的概述;更详细的信息可在别处找到。 15 优化编译器的结构如图 4 所示。

从字节码到中间表示(intermediate representation)
优化编译器从把 Java 字节码转换成 高级中间表示(high-level intermediate representation(HIR))开始。这是基于寄存器的三个中间表示之一,这些中间表示共享一个公共实现。(基于寄存器的表示比基于堆栈或树的表示在代码移动和代码转换方面有更大的灵活性。它们也允许更接近 Jalape�o 的目标体系结构的指令集。)这些中间表示的指令是 n 元组:一个 操作符和零个或多个 操作数。多数操作数表示的是符号寄存器,但它们也可以表示物理寄存器、内存位置、常数、分支目标或类型。这些中间表示反映了 Java 的类型结构:对不同基本类型上的相似操作有截然不同的操作符,操作数带有类型信息。 17 指令被组合进扩展的基础块,方法调用或可能导致抛出异常的指令都不能终止这些块。(当进行数据流分析或移动这些扩展块上的代码要特别小心。) 1617 这些中间表示也包含高速缓存诸如可达定义(reaching-definition) 18 集合、依赖图和循环嵌套结构的编码这样的可选的附加信息。

转换过程发现方法的扩展基础块,为方法创建异常表并为字节码创建 HIR 指令。它发现并编码类型信息,这些信息可用于随后的优化,而且引用映射表也需要这些信息。一定程度简单的“快速”优化 ― 副本传播、常数传播、本地变量的寄存器重命名、死代码清除等等 ― 也被执行。 19 (尽管在稍后的优化阶段会执行这些优化的更多版本,在这里执行它们还是值得做的,因为这样做减小了生成的 HIR 的大小,从而减少随后的编译时间。)此外,合适地短的 final 或 static 方法被内联了。

副本传播是在转换期间执行快速优化的一个示例。Java 字节码常常包含执行计算并把结果存储到本地变量的指令序列。对中间表示的生成的一个天真想法是为计算结果创建一个临时寄存器,并另外用一条指令把这个寄存器的值移入本地变量。简单的副本传播试探法清除了大量这些不必要的临时寄存器。当从临时寄存器把值存储到本地变量时,将检测到最近生成的指令。如果是这条指令创建了这个临时寄存器来存储结果,那么这条指令就被改成把结果直接写到本地变量。

转换通过字节码的 抽象解释继续进行。按照 Java 虚拟机规范 20 的定义,本地变量的类型(如果在编译时已知,则还包括值)和执行堆栈的条目构成了抽象解释的 符号状态。(因为这些类型不是从 Java 字节码静态可用的,因此所有的 Jalape�o 编译器都必须有效地跟踪这个符号状态。)字节码的抽象解释涉及生成适当的 HIR 指令和更新符号状态。

转换算法的主循环使用一个包含代码块和它们的初始符号状态的工作表(list)。最初,这个工作表包含开始于字节码 0 的代码和每个方法的异常处理程序(符号状态为空)的条目。代码块相继被从工作表中移走并把它们当作扩展基础块对它们进行解释。如果碰到一个分支,则块被分隔并将碎块添加到工作表。(在控制流汇合点,从不同流传入的堆栈操作数的值可能不同,但这些操作数的类型必须匹配。 21 一个元素智能的 meet 操作被用在在堆栈操作数上以更新这些点上的符号状态。 19 )如果一个分支是向前跳转的,则从块的开头到这个分支的一块被暂时看作一个完整的扩展基础块。从该分支到它的目标和从该目标到块的末端的块被添加到工作表。如果分支是向后跳转的,则从分支到块的末端的块被添加到工作表。如果向后跳转分支的目标在一个已经生成了的扩展基础块中,则这个块将在目标点被分隔。如果堆栈在目标点不空,则块必须重新生成,因为它的开始状态可能是不正确的。

为尽量减少为同块字节码生成 HIR 的次数,简单贪婪算法为抽象解释选择有最低开始字节码索引的块。这个简单的试探法依赖于这样的事实,即除了循环,所有控制流构造都是以拓扑有序方式生成的,而且控制流图是可简化的。偶而地,这个试探法看来获得了用当前 Java 源代码编译器编译的方法的扩展基础块的最优顺序。

高级优化
HIR 中的指令很好地模仿了 Java 字节码,有两个重要不同 ― HIR 指令在符号寄存器操作数上进行操作,而不是在隐式堆栈上,而且 HIR 包含独立的操作符,用于实现运行时异常的显式检查(例如,数组边界检查)。相同的运行时检查通常需要多于一条的指令。(例如,incrementing A[ i] 可能涉及两个独立的数组访问,但只需一次边界检查。)对这些检查指令的优化减少了执行时间并使另外的优化更容易。

当前,HIR 使用带有适度编译时开销的简单的优化算法。这些优化有三类:

  1. 本地优化。这些优化对扩展基础块是本地的,例如,公共子表达式清除、冗余异常检查清除以及冗余装入清除。
  2. 流不敏感优化。为在基础块之间进行优化,就要利用 Java 虚拟机规范的“Java 程序中的每个变量在被使用前必须有值” 20 保证。如果一个变量只被定义一次,则该定义将影响到每次使用。对这样的变量,可构建“定义- 使用”链,进行副本传播,并且不需昂贵的控制流或数据流分析即可清除死代码。此外,编译器执行保守的流不敏感的转义分析以把聚集的标量替换和调用的语义扩展变换转义到标准 Java 库方法。 22

    这种技术能捕捉到很多优化机会,但其它的情况只能由流敏感的算法检测到。

  3. 方法调用的内联扩展。为在 HIR 级别上把方法调用扩展成内联,被调用方法的 HIR 被生成并被补入到调用者的 HIR。静态的、基于大小的试探法当前用于控制对静态和最后方法的调用的自动内联扩展。对于非最后虚方法调用,优化编译器预测虚调用的接收方为对象的声明类型。它用运行时测试来监视每个内联虚方法以验证对接收方的预测是正确的,如果不正确,则缺省设置为正常虚方法调用。在有动态类装入的情况下,这种运行时测试是安全的。

由于 Jalape�o 是用 Java 写的,与用于把应用程序方法扩展为内联的框架相同的框架也可用于把对运行时方法的调用扩展为内联(特别是同步和对象分配)。一般说来,从应用程序代码到 Java 库,下至 Jalape�o 运行时系统,都可以把调用扩展为内联,这为优化提供了极好的机会。

低级优化
在执行了高级分析和优化之后,HIR 被转换为 低级中间表示(low-level intermediate representation(LIR))。LIR 把 HIR 指令扩展为特定于 Jalape�o 虚拟机的对象布局和参数传递约定的操作。例如,虚方法调用被表达为类似于 invokevirtual 字节码的单条 HIR 指令。这一条 HIR 指令被转换在三条 LIR 指令,分别负责从一个对象获得 TIB 指针,从 TIB 获得适当方法体的地址,以及将控制转到方法体。

由于字段和头的偏移量现在都是可用的常数,新的优化机会出现了。原则上,任何高级优化也可用在 LIR 上。然而,由于 LIR 的大小可能是相应 HIR 大小的两到三倍,所以在进行 LIR 优化时要更留意编译时间开销。目前,清除本地的公共子表达式是 LIR 上进行的唯一优化。由于 HIR 和 LIR 共享相同的基础设施,所以在 HIR 上执行公共子表达式清除的代码不用修改就可重用在 LIR 上。

同样,作为低级优化的最后一步,我们为每一个扩展基础块构造一个 依赖图 17 依赖图用于指令选择(请参阅下一部分)。依赖图的每个节点是一条 LIR 指令,而每一条边对应于一对指令的依赖约束。边可表示真、假以及寄存器和内存的输出依赖 17 。边还可表示控制、同步和异常依赖。通过在同步操作(monitor_enter 和 monitor_exit)和内存操作之间引入 同步依赖边建立同步约束的模型。这些边阻止内存操作的代码移动越过同步点。Java 异常语义模型 20 通过用 异常依赖边链接扩展块中的不同异常点来建立。异常依赖边也被添加到这些异常点之间和本地变量的寄存器写操作之间,如果方法中有任何异常处理大块空间,则这些本地变量就“生活”在其中。依赖约束的精确模型使我们可以在下一个优化阶段对代码进行激烈的重新排序。

指令选择和特定于机器的优化
在低级优化之后,LIR 被转换成 特定于机器的中间表示(machine-specific intermediate representation(MIR))。当前的 MIR 反映 PowerPC 体系结构。(如果 Jalape�o 被移植到不同的体系结构,可以引入另外的 MIR 指令集。)方法的扩展基础块的依赖图被转换成树。这些用于 自下而上重写系统(bottom-up rewriting system(BURS)) 23 ,这个系统产生 MIR。然后符号寄存器映射到物理寄存器。在每个方法的开始添加 序言,在结尾添加 结语(epilogue)。最后,就生成了可执行代码。

BURS 是代码生成器(code-generator)生成器,类似于扫描器和分析器生成器。想得到的目标体系结构的指令选择由 树语法(tree grammar)指定。树语法中的每一条规则都有一个相关花费(反映生成的指令的大小和指令的预期周期数)和代码生成动作。处理树语法以生成一组表,这些表在编译时驱动指令选择。

在指令选择上使用 BURS 技术有两个重要好处。首先,编译时进行的树型匹配法通过使用动态编程为所有输入树找到了最少花费的分析(与树语法中指定的花费相比)。其次,构建 BURS 基础设施的花费可在几个目标体系结构中分期付清。特定于体系结构的部分相对较少;Jalape�o 的 PowerPC 树语法约有 300 条规则。

BURS 中的树型匹配法最初是开发用来从基于树的中间表示生成代码的,通常是在没有全局优化的场合。为树型匹配法生成有向非循环图的以前的办法只考虑了包含寄存器真依赖(register-true-dependence)边的图。 24 我们的办法更通用,因为它考虑了存在寄存器和非寄存器依赖两种情况下的转换。对这种区分的合法约束不是微不足道的。 25

在构造了 MIR 之后,就执行活动变量分析,以判断符号寄存器和堆栈变量的活动范围,这些堆栈变量保存了位于垃圾回收安全的点的对象引用。标准活动变量分析 18 已被修改成处理 控制流分解图的扩展基础块的,如 Choi 等人所描述的那样。 16

接着,优化编译器使用 线性扫描全局寄存器分配算法 26 来把物理机器寄存器指定给符号 MIR 寄存器。这个算法不是基于图染色的,但却贪婪地在符号寄存器的活动范围的一次线性扫描时间内把物理寄存器分配给符号寄存器。这个算法比图染色算法快几倍,而结果代码的效率几乎一样。更成熟(花费也更大)的寄存器分配算法最终将在更高级别的优化上使用(请参阅下一部分)。(当前在快速编译器中使用的算法比在优化编译器中使用的算法更昂贵,对作者真是一个讽刺。)

方法序言分配一个堆栈框架,保存方法需要的任何非易失性寄存器,并且检查是否有人提出让出请求。结语恢复任何被保存的寄存器并解除堆栈帧分配。如果方法被同步,则序言锁定,而且结语解锁,指定对象也被同步。

优化编译器然后把可执行的二进制代码放到指令数组,即方法体。通过把中间指令偏移量转换为机器代码偏移量,这个装配阶段也最后确定了异常表和指令数组的引用映射图。

优化的级别
优化编译器可在不同的优化级别上执行。每个级别都包含前一级别的所有优化和一些其它东西。 级别 1恰好包含上面描述的优化。(存在 级别 0 主要是出于调试的目的,它与级别 1 相似,但没有任何高级或低级优化。)两个级别的更加激烈的优化也在计划之中。

级别 2 优化将包括代码说明,过程内的流敏感优化和指令调度,流敏感优化基于 静态单指定(static single assignment(SSA))形式(标量 27 和数组 28 )的成熟的寄存器分配。指令调度目前正在实现之中。它使用 MIR 依赖图,这个图用与 BURS 用来构建 LIR 依赖图相同的代码来构建。

级别 3 优化包括过程内的分析和优化。目前,过程内的转义分析 29 和寄存器保存和恢复的过程内优化 15 都正在实现之中。

操作的形态。
优化编译器的前端(转换到 HIR 和高级优化)不依赖于 Jalape�o 的对象布局和调用约定。一个字节码优化项目正在使用这个前端。 30

优化编译器的运作方式是想作为自适应 JVM 的一个组件。图 5 显示了这样一个虚拟机的整体设计。优化编译器是 Jalape�o 的自适应优化系统的关键组成部分,这个自适应系统也包含联机测量(on-line measurement)和正在开发的控制器子系统(controller subsystem)。通过使用软件采样和成型技术和来自硬件性能监视器的信息的概要,联机测量子系统将监视单个方法的性能。当联机测量子系统检测到某个性能阈值被达到时,控制器子系统将被调用。控制器将用概要信息构建一个“优化计划”,这个计划描述了哪个方法应被编译以及应用哪一个优化级别。然后调用优化编译器来编译优化计划中的方法。联机测量子系统继续监视单个方法,包括那些已经优化的方法,以在必要时触发进一步的优化过程。

除上面描述的动态编译方式之外,优化编译器也可用作静态编译器,如图 6 所示。在这种方式下,优化编译器生成的优化代码被存储在引导映像(boot image)中(请参阅 附录 B)。优化编译在执行 Jalape�o 虚拟机之前脱机进行。(我们希望最终能把两种方式合并。应用程序运行一会儿,自适应优化系统就为该应用程序优化 JVM。最后,这个优化后的 JVM 将作为特定于该应用程序的引导映象被写出来。)

优化编译器也可用作 JIT 编译器,在方法第一次执行时编译所有方法。当要设定优化编译器的性能基准时,优化编译器同时用作静态引导映象编译器(针对引导映象的 JVM 代码)和 JIT 编译器(针对基准程序代码和任何余下的 JVM 代码)。

当前状态

实现所有的 Java 语言功能所要求的核心功能就是全部工作,但有待于完成。一些更深奥的线程功能 ― 暂挂、恢复、时间等待等等 ― 还有待于实现。负载平衡算法还处在在初步阶段。还未提供对最终化、弱引用和类验证的支持。快速编译器接近完成。优化编译器的基础框架和它的一些级别 1 的优化已经完成并运行。更高级的优化正在开发之中。联机测量和控制器子系统处在设计阶段。

Jalape�o 对 Java 库代码的支持受到 Jalape�o 写成 Java 代码的限制。Jalape�o 能够处理写成 Java 代码的库方法,但本机方法必须重写。实现 Java 本机接口(Java Native Interface(JNI))将允许 Jalape�o 调用写给这种接口的本机方法,但不能调用某些本机方法。JNI 是一个特别难解决的问题,因为它是虚拟机的 C 语言接口,而在 Jalape�o 中,虚拟机不是用 C 编写的。我们还不知道当我们试图在 Jalape�o 中提供 JNI 服务时会出现什么性能或实现问题。

Jalape�o 项目正处在过渡阶段。初始功能大多已经实现。Jalape�o 的很多机制仍处于初步阶段。现在是测量性能、识别瓶颈并用更高效的实现取代它的时候了。一些“低挂的果实”已被采摘:例如,无争用的锁获取已经被改成内联。然而,基线编译代码的性能量度是如此没有说服力以致于我们只好勉强信任我们的量度,直到优化编译器可用。

在功能和性能上也还有错误有待于隔离、识别和修复。

要想评估 Jalape�o 的当前性能,将它与 AIX 下的 IBM Developer Kit(DK)中的 JVM 作个比较是有帮助的,该 JVM 是东京 IBM 开发的使用 JIT 编译器的 Java 技术版,版本 1.1.8。 31 应该注意到,Jalape�o 的目标奢侈地针对 SMP 服务器,而 IBM JVM 必须适应于所有运行 AIX 的 PowerPC 计算机。读者的脑海中也应记住这里提出的性能图代表的是某个时间点上的快照:Jalape�o 和 IBM JVM 都不时得到改善。

性能图针对 Jalape�o 的基线和优化编译器。对两种情况,引导映象都用优化编译器编译过,而指定编译器主要用于指定的应用程序(和 JVM 的任何动态链接类)。优化编译器图反映当前实现了的级别 1 优化。非繁衍拷贝内存管理器在两种情况中都使用。

图 7 比较了 Jalape�o 的基线和优化编译器(用 Java 语言编写并由 Jalape�o 的优化编译器优化)以及 IBM DK JIT 编译器(用本机代码实现)花费的编译时间。基线编译器是明显的胜出者,其运行比 JIT 编译器快 30 到 45 倍。优化编译器差不多与 JIT 编译器一样快,但没它快。

图 8 把三个编译器生成的代码的性能和 Symantec 的微基准程序(microbenchmark)上的不使用 JIT 编译器的 IBM DK 的解释代码的性能作了一个比较。 32 (该图已被删改以简化 Jalape�o 的优化编译器和 IBM DK JIT 编译器间的性能比较。)基线编译后的代码始终是解释后的代码的两倍快。IBM JIT 编译后的代码快得多:比解释后的代码快 4 到 40 倍。Jalape�o 的优化编译器与 JIT 编译器大致相当。

图 9 在运行在中等大小的(10%)问题上的 SPECjvm98 基准程序 33 上做了相同的比较。 34 基线编译器再一次通常是解释器的两倍好。JIT 编译器再一次快得多。优化编译器再一次通常与 JIT 相当。

图 10 显示了在使用可移植业务对象基准程序(portable business object benchmark,pBOB 版本 2.0a)的 12 路 SMP(带运行 AIX 4.3 的 262 MHz PowerPC S7a 处理器)上的 12 个虚拟处理器上运行的 Jalape�o 优化编译器的性能。这个模型按照 TPC-C 规范建立的基准程序(请参阅 Baylor 等人 35 对这个问题的讨论以了解细节),模拟了事务工作负载中的业务逻辑。一直到 10 个仓库(warehouse),性能几乎是线性地提高,在 13 个仓库时达到峰值,然后缓慢地降低。这表明,到少在这个基准程序上,Jalape�o 伸缩得很好。

相关工作

用 Java 代码实现一个 Java 虚拟机和它的相关子系统(包括优化编译器)提出了几个挑战。Taivalsaari 36 也描述了一个“用 Java 写 Java”的 JVM 实现,设计它是为了检查用 Java 写的高质量的虚拟机的可行性。这个方案的一个缺点是它运行在另一台 JVM 上,这增加了性能开销,因为有两级解释过程。麻省理工学院(Massachusetts Institute of Technology(MIT))的 Rivet JVM 37 也运行在另一台 JVM 上面。通过自举系统,我们的方案不需要另一台 JVM(请参阅 附录 B)。IBM VisualAge for Java 38 的 JVM 是用 Smalltalk 写的。其它的 JVM 39 是用本机代码写的。

最令人兴奋的传统 JVM 可能是 HotSpot。 40 HotSpot 的对象模型和 Jalape�o 的有点相似:对象直接被引用(而不是通过句柄)而且对象有一个两个字的头。在两个模型中,关于对象的类的信息都通过对象头中的引用可用。

HotSpot 最初解释字节码,编译(并内联)被频繁调用的方法。Jalape�o 的快速编译器将扮演与 HotSpot 的解释器相似的角色。其它所有都是同等的,这对 HotSpot 会带来启动方面的好处,对 Jalape�o 会带来性能方面的好处。我们不期望哪个好处会特别大,但这仍然可以看到。如果未优化的 Jalape�o 代码比解释后的 HotSpot 代码表现更好,这将允许 Jalape�o 优化编译器把更多的资源集中在它优化的代码上。用 Java 代码实现 Jalape�o 允许优化编译器内联和优化频繁被调用的运行时服务,HotSpot 通过调用本机代码(极好地优化了的 C 例程)访问这些服务。

HotSpot 把 Java 线程作为宿主操作系统线程实现。这些线程是完全抢先的。Jalape�o 调度它自己的准抢先线程。我们希望这将允许支持更多的线程、更轻量的同步和使从正常操作到垃圾回收的更平滑切换(特别是在有极多线程的情况下)。HotSpot 的每线程方法激活堆栈符合宿主操作系统的调用约定。这应会给 Jalape�o 较小的空间和性能方面的好处(尽管 Jalape�oill 在它 确实调用 C 代码时获得了性能方面的好处)。

HotSpot 和 Jalape�o 都支持类型确切的垃圾回收。Jalape�o 支持一系列内存管理器。Jalape�o 的回收器没有一个象 HotSpot 的那么成熟,但在 SMP 上,Jalape�o 的回收器并行地运行在所有可用的 CPU 上。HotSpot 使用一个带有针对主要回收的“标记并压缩”繁衍方案。为尽可能减少暂停时间,HotSpot 可以使用一个增量的“火车(train)” 回收器。 44 这个回收器执行频繁的短回收。注意,这将加剧任何的过渡到回收(transition-to-collection)延迟。

我们没有关于 HotSpot 的锁定机制的信息。

Squeak 45 是一个用 Smalltalk 写的 Smalltalk 虚拟机。它通过把虚拟机转换为 C 以编译和链接接来生成产品版。转换程序也是用 Smalltalk 写的。

动态编译(称为动态转换或即时编译)已经成为很多面向对象语言的以前的实现中的一个关键因素。Deutsch 和 Schiffman 的 Smalltalk-80 的高性能实现动态地把 Smalltalk 字节码转换成本机代码; 46 他们的编译器与 Jalape�o 的基线编译器非常相似。Self 语言的实现也依赖于动态编译来达到高性能。 47 Self 编译使用与 Jalape�o 的优化编译器所用的中间表示大体相当的的基于寄存器的中间表示 。最近,大量 Java 语言的即时编译器已被开发出来。 31 48 这些编译器中,有一些编译器把字节码转换成三地址代码,进行简单的优化和寄存器分配,然后就生成目标机器代码。

DAISY 49 是一个 VLIW(very long instruction word(超长指令字))仿真器,它“快速”地把不同体系结构指令集,包括 Java 字节码,转换成 VLIW 体系结构。它使用 VLIW 类似于树的表示以进行指令调度和寄存器分配。

很多以前的系统使用了动态编译的更专门的形式,以通过使用“运行时常数”来有选择地优化程序的“热点”。 50 一般来说,这些系统都强调极其快速的动态编译,经常执行大量的脱机预计算,以避免构造正在编译的程序片段的任何显式表示。

有大量的工作用于处理特定于面向对象语言的优化,例如类分析(过程内的 54 和过程间的 55 ),类层次结构分析和优化 56 57 ,接收器类预测 46 58 59 ,方法规范 56 和调用图构造。 55 其它与 Java 编译有关的优化包括边界检查清除 60 和语义扩展。 22

结论

用于 Java 服务器的 Jalape�o 的虚拟机是用 Java 语言编写的。传统上用本机方法支持的运行时服务主要地用 Java 代码实现。

Jalape�o 的对象布局支持单指令字段访问,对数组元素的三指令访问,硬件空指针检查和四指令虚方法调度。通过全局 JTOC 数组快速访问静态字段和方法也实现了。

Jalape�o 的线程通过虚拟处理器进行多路复用。线程切换是准抢先的。三个不同的锁定机制提供了轻量级同步,而不用操作系统支持。

Jalape�o 的内存管理子系统支持一系列内存管理器,每个内存管理器由一个并发对象分配器和一个并行的、类型确切的、停住一切的垃圾回收器组成。繁衍的和不繁衍的,拷贝的和非拷贝的管理器都被支持。增量及并发回收器正在研究之中。

Jalape�o 的三个可互操作的编译器提供了不同级别的动态优化,确保了实时的线程抢先,并且生成了支持异常处理、堆栈中的调用的位置和调试的表。

Jalape�o 的优化编译器为已被识别为频繁执行或计算密集的方法产生优质代码。需被再次编译的方法将根据运行时配置动态地选择。

我们已经证明了用 Java 语言为 Java 服务器构建虚拟机的可行性。我们尚未证明这样一个虚拟机能达到并保持世界级的性能。我们正在为此努力。

附录 A:MAGIC

为分配一个对象,Jalape�o 的内存管理器必须访问原始内存以获得要求大小的一块可用空间。它们“遍历”线程堆栈以识别堆栈帧中的对象引用。拷贝管理器在垃圾回收期间访问对象头以标记对象,访问原始内存以拷贝一个对象。异常处理要求非结构化的传送控制以转到适当的 catch块(“go to”在 Java 语言中是禁止的)。静态数据和方法通过一个专用的机器寄存器访问,不能从 Java 指令访问这个专用寄存器。输入和输出要求访问 Java 语言不知道的操作系统服务。线程切换依赖于接收到来自操作系统的周期性中断。Jalape�o 的锁定机制是用 PowerPC 指令实现的,这些指令无法表达成 Java 字节码。不打破 Java 的编程模型,这些操作都无法进行。

为实现 Jalape�o Java 代码,有必要增加 Java 的功能,以包含本机方法传统上要求的功能:

  • 调用操作系统服务
  • 使用特定于体系结构的机器指令
  • 访问机器寄存器和内存
  • 强制对象引用原始地址, 反之亦然
  • 把执行转到任意地址

Jalape�o 必须要有这些功能,但 Jalape�o 也必须防止用户应用程序能使用这些功能。

在专门的 MAGIC 类的帮助下,Jalape�o 的编译器支持这些违例。这个类的方法符合 Java 外部操作,Jalape�o 必须能够执行这些操作。这些方法的体是空的。Java 的源代码编译器能够编译它们。但是,Jalape�o 的编译器忽略这些结果字节码。而且,这些编译器识别出 MAGICR 类的名字并内联地插入必需的机器代码。为确认用户代码未违背 Java 的约束,当 Jalape�o 的编译器碰到调用一个 MAGIC 方法时,它们将验证正在编译的方法是 JVM 的一个已授权的部分。

需要使用 MAGIC 类的代码在这样做时需特别小心。将要讲述的规则就是一个原因。某些操作要格外小心。涉及原始地址的计算尤其微妙。MAGIC 方法 objectAsAddress 把对象引用转换成原始地址(一个整数)。例如,在进行动态链接时就需要这个功能。然而,它也是有问题的。Jalape�o 的拷贝内存管理器在移动所引用的对象时会更新对象引用,但原始地址却未被更新。在进行涉及原始地址的计算时,为避免垃圾回收的发生,必须很小心,以免拷贝回收器使这些地址无效。这通过调用一个能禁用垃圾回收的方法来避免。

已经禁用了垃圾回收的线程不能试图创建一个对象,因为如果内存不足,系统将会挂起。(注意,其它线程可以自由申请内存。如果无法得到内存,则这些线程被延迟,而且一旦垃圾回收被重新启用,就将开始进行一个回收。)这个约束有一些微妙的牵连。类不能被装入,因为对象是在类装入期间创建的。这意味着必须避免动态链接。类型的强制转型(和存储到对象数组)也不允许,因为这可能也要求类装入。类似地,如果线程试图进入一个共享对象的一个管程,而这个管程当前正被一个正在等待垃圾回收的线程占有,那么系统将陷入死锁。因此,线程在进行涉及原始地址的计算时,必须严格限制在 Java 功能的子集内。

就线程当它的垃圾回收被禁用时进行让出(显式地或隐式地)来说,也会有点问题。这样一个让出可能会任意地延迟所需的垃圾回收。当线程的垃圾回收被禁用时,隐式线程切换被延迟(而显式线程切换被禁止)。

Jalape�o 系统中大约有 650 个 Java 类,其中大约有 110 个访问了 MAGIC 类。其中只有 12 个类要求禁用垃圾回收。

附录 B:开始

一组相当坚实的服务 ― 一个类装入器,一个对象分配器,一个编译器 ― 在 JVM 能够装入正常操作所需的所有剩余服务之前就必须已经存在。用本机代码编写的 JVM 的初始服务,或者运行在另一台 JVM 上的 JVM,都从底层运行时例程可用。Jalape�o 不是用本机代码编写的,它没有底层运行时例程。因此,我们把基本的核心服务装配进一个可执行 引导映象,这个引导映象先于 JVM 运行。这个引导映象是 Jalape�o 虚拟机的一个快照,它被写入到一个文件中。随后,这个文件被装入内存并执行。

引导映象由一个名为 引导映象编写器(boot-image writer)的 Java 程序创建。引导映象编写器构造运行中的 Jalape�o 虚拟机的实体模型(mock-up),然后把它包装进引导映象。引导映象编写器是一个普通的 Java 程序,它可以在任何 JVM 上运行。运行引导映象编写器的 JVM 将被称为 JVM,而产生的结果 Jalape�o 虚拟机则称为 目标JVM。

引导映象编写器类似于一个交叉编译器和链接器:它把字节码编译成机器码并重写机器地址以把程序组件绑定进可运行映象。然而,由于 Jalape�o 的编译器、类装入器和运行时数据结构都是 Java 代码形式,而不似多数编译器,所以引导映象编写器也必须把“活动”对象绑定进引导映象。

引导映象编写器在源 JVM 中实例化 Java 对象,这些对象表示了目标 JVM。然后,它使用 Java 内置的反射功能把这些实体模型对象从源 JVM 的对象模型转换为 Jalape�o 的对象模型。引导映象编写器和这种自引用特征使得它相对简单 ― 它实际上只是一个对象模型转换器。

由于 Jalape�o 是一个 Java 程序,所以它的每个组件都是一个 Java 对象,而且,通过在 Jalape�o 的每个主子系统中执行专门的初始化方法,引导映象编写器能够构造其实体模型。定制的类装入器确保了执行这些代码所需的任何类都既装入到了源 JVM 中,也装入到了实体模型中。当装入一个类时,类的方法被编译(由运行在源 JVM 中的 Jalape�o 的编译器执行)并被包含进实体模型。

要成功实施把类同时装入源 JVM 和它的目标 JVM 的实体模型的策略,就需要一个完整的类列表。如果当 Jalape�o 开始运行时,核心运行时环境的一个方法引用了不在引导映象中的任何类,则将产生无穷递归的结果:运行时环境要求装入它自己的一部分以装入它自己的一部分 ― 等等。

通过仔细的计划和反复试验,我们解决了判断实体模型中最少需要哪些类以阻止这种情形的问题。Jalape�o 的所有核心类都以 VM 为前缀命令。这里是提供使虚拟机能执行编译、内存管理和动态类装入的充足机器所需的类。这个专门的前缀由 Jalape�o 的编译器识别并用于抑制正常的动态链接规则:编译器从不在有这个前缀的类的方法之间生成动态链接代码。小心地编写核心类以避免对 Java 库类的不必要使用。这些基础类 ― java.lang.Object、java.lang.Class、java.lang.String 和一些 I/O 类 ― 是绝不可以排除在外的。VM_ 类和这些基础 Java 类构成了我们认为有必要在引导映象中出现的类的启动集。

然后通过反复试验识别出另外一小部分依赖(例如,Integer、Float、Double 和各种数组和异常类)。我们编译一个引导映象并试图执行它。如果它在试图(递归地)装入类 X时崩溃了,那我们就把 X 添加到写入引导映象的类的列表,并反复进行这个过程。这个过程集中进行了少数重试,也不证明一旦 VM_ 类的实现隐定了,这会成为一个维护问题。

实体模型在完成之后被转换成引导映象。这包括查找实体模型中的所有对象,把它们转换成 Jalape�o 的对象格式并存储进 引导映象数组。运行中的 Jalape�o 虚拟机的所有组件都可以从一个 JTOC 数组中获得(请参阅静态字段和方法部分)。在实体模型中,JTOC 被编码成三个并行的数组:一个整数数组(用于原始值),一个对象实例数组(用于引用)和一个用于区分这两个数组的布尔数组。JTOC 数组的结构被递归地遍历,所碰到的值(引用的和原始的)被转换到引导映象数组。由于每个装入类的类型信息块(请参阅对象头部分)都从 JTOC 引用,所以所有必需的编译后的方法体都将被包含到引用映象中。

这个转换过程使用了映象。引导映象为实体模型中的每个对象获得 java.lang.Class 对象并在由 getFields 方法返回的字段上反复进行一些操作。对每一个字段,它从源对象抽取字段值,从对象的 Jalape�o 类描述中抽取目标字段偏移量。然后,它把位于从对象的索引偏移该偏移量的值写入引导映象。当碰到对象引用时,我们不能使用来自实体模型的任何值。通过用一个作为分配到的引导映象维护的散列表,实体模型中的引用被转换成引导映象地址。(包含引导映象中的所有引用的地址的数组可以被包含进引导映象,以支持引导映象的重定位。)

总的来说,引导映象编写器一个字段一个字段地拷贝 Java 对象,从实体模型到引导映象,同时从源 JVM 的对象模型转换到目标 JVM 的对象模型。有赖于 Java 的映象功能,我们碰上了一个麻烦:Sun 的 Java 开发包(Java Development Kit),版本 1.1.4 不允许对私有字段的反射访问。这在 Java 2 软件开发包(Java 2 Software Development Kit)中不是一个问题,这个开发包允许这样的访问。通过预处理类文件,关掉私有位,我们在更早的版本中就解决了这个问题。

除了能从 JTOC 数组中访问的对象外,引导映象中还需要另外两个对象:一个初始线程对象和一个“引导记录”。初始线程对象包含一个空堆栈,它已为在 Jalape�o 启动时运行 boot( ) 方法的第一条指令准备就绪;“引导记录”是引导映象和引导映象运行器(稍后论述)之间的接口。这个引导记录包含映象中的开始、结束和最后使用的地址,也包含用于启动 Jalape�o 的四个寄存器值,boot( ) 方法的地址和 AIX 系统调用的地址。当这些值被存储到引导映象数组时,这个引导记录被写到磁盘上。

一个称为 引导映象运行器的短小程序启动 Jalape�o 的运行。它把引导映象读进内存,把四个寄存器设置为指定值并转到 boot( ) 方法分支。引导映象是用 C(带有一些汇编程序以设置寄存器和执行最后的分支)写的,不是 Java 代码,所以 不需要在 JVM 上运行。

当 boot( ) 方法开始执行时,虚拟机处在一个脆弱状态:它能够运行机器指令的单个线程,但它还未创建支持它自己的执行所需的外部操作系统资源。引导映象无法创建这些操作系统资源,因为这些资源要引用外部状态,而这些状态将不存在,一直到引导映象执行。因此,Jalape�o 必须执行另外的初始化。

在引导期间,虚拟机初始化特定于硬件的地址(例如,它将最终在自己的堆栈上建立硬件监视页),打开与 Java 库的 System.in、System.out 和 System.error 流对象相对应的文件,分析命令行参数并创建与一个与当前执行环境相对应的 System.Properties 对象。然后,通过创建充当虚拟处理器的操作系统线程初始化多线程子系统,Java 线程在虚拟处理器上多路复用。最后,启用定时器中断以支持线程抢先,生成一个 Java 线程以运行命令行指定的应用程序。

Jalape�o 运行直到最后一个(非守护)Java 线程终止或调用了 System.exit( )。


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=53126
ArticleTitle=Jikes 研究虚拟机(RVM)
publish-date=02022000