摘要

为了保证在低延迟的状态下进行内存分配，移动操作系统会自动杀死应用程序，而不是将内存交换到磁盘。这种设计将过度使用内存的管理负担转移到应用程序员身上，要求他们不断地设置应用程序状态检查点并记录到磁盘中。本文介绍了一个新的移动平台内存管理器Marvin，它支持高效内存交换，同时满足移动应用程序的严格性能要求。Marvin的支持交换的语言运行时是与操作系统级内存管理协同设计的，可以避免传统交换机制的常见缺陷。它的主要特点是:（1）设计了一种新的交换机制，称为提前交换（AOT），它可以从内存预写到磁盘，然后在需要的时候快速获取；（2）一个改进的书签垃圾回收器，以避免交换未使用的内存；（3）一个对象粒度工作集的估计工具。我们的实验表明，Marvin可以同时运行的应用程序比Android多两倍，而且Marvin利用Linux交换文件可以在内存压力下分配内存，回收内存的速度比Android快60倍。

1.引言

在过去的10年里，移动应用变得更庞大、更复杂，远远超过移动设备内存的增长。这一趋势增加了移动操作系统的内存压力，源于应用程序在争夺有限的空间。展望未来，移动操作系统必须在应用程序之间更有效地共享内存，否则用户体验将受到影响。

虽然移动应用程序已经变得更加复杂，但移动内存管理仍处于起步阶段。目前热门的移动操作系统为每个运行的应用设置了固定的内存上限（例如，运行在iPhone X上的ios为1.4GB，运行在谷歌Pixel XL上的Android为512MB）。他们不会额外提供内存，相反它们会杀死正在运行的应用程序，稍后再重启，但是这种方法只在应用程序很小且没有运行状态时有效。然而，这种方法是不可持续的。随着移动操作系统取代桌面操作系统（例如，Android现在是世界上最常用的操作系统），移动应用取代了桌面应用（如谷歌Docs和Word Online取代了微软Word）。今天的应用程序已经不能适应它们的内存分配，所以它们在内存和本地存储之间手动交换对象，或者使用动态库来满足它们的需求。由于内存压力应用程序越来越有可能被杀死，所以它们还必须不断地将执行状态保存到磁盘，并尽量减少启动时间以应对频繁的重启。尽管程序员为此做了很多努力，但仍然需要数秒钟的时间来杀死和重启热门应用程序。

提升移动内存管理是很困难的。移动应用运行在高级语言运行时（例如Swift, ART），这限制了操作系统的洞察力（例如，工作集估计是不可能的），并且对操作系统级别的内存管理器来说是出了名的难以处理。此外，移动应用程序通常会快速分配大量内存（例如:启动时，或用于云端下载），除非操作系统保持一个大的空闲内存池，否则更容易通过终止整个应用程序来实现。最后，基于触摸的接口强加了严格的延迟要求，这是交换到磁盘无法满足的。

在本文中，我们通过一个关键的观察改进了移动内存管理:与其他操作系统不同，移动操作系统在一个公共语言运行时中运行所有的应用程序。例如，所有运行在Android上的应用程序必须运行在Android运行时（ART）。这种差异让我们协同设计语言运行时，以帮助移动操作系统优化内存管理。由于其对内存使用的了解，语言运行时成为能够更好地管理内存的机制的理想场所。

本文展示了利用运行时执行操作系统任务的价值。我们介绍一个新的Android内存管理器Marvin，它能有效地支持内存过度使用。Marvin在语言运行时实现了大部分内存管理，它对应用程序的内存使用有更多的了解。Marvin只依赖操作系统进行跨应用程序的资源分配。

图1:对象大小的CDF和被该大小或更小的对象占据的堆百分比。

通过集成语言运行时，Marvin可以提供增强内存管理的三项新特性:

• 一种新的交换机制，在回收内存时执行提前磁盘交换以避免同步磁盘写入，并将检查点对象留在内存中（与Linux的kswapd不同）。
• 一种新的对象级工作集估计器，它将垃圾回收器和应用程序访问分开，并通过对象级访问跟踪来避免错误共享。
• 一个新的书签垃圾回收器，它跟踪准确的活跃度数据，而不访问换出的对象。

我们通过修改Android运行时（ART）的解释器和编译器来实现Marvin的原型。实验表明，我们的Marvin原型能够运行比Android多两倍的并发应用程序，并且Marvin回收内存的速度比Android在Linux交换文件下分配内存的速度快60倍。

2.现代手机OS内存资源管理的局限性

虽然移动操作系统可能基于传统操作系统（例如，Android和Linux），但它们在两个重要方面有所不同:（1）对于每个应用程序，他们将内存使用量限制在物理内存的一小部分（例如，4GB设备上的512MB），而不是让应用程序分配所需的内存；（2）当物理内存耗尽时，它们会结束应用程序，而不是通过分页或其他机制过度使用内存。为了促进我们的工作，我们用热门的应用程序进行了实验，展示了这些设计决策的原因和成本。实验设备是一部配备4GB RAM和四核高通骁龙821CPU的Pixel XL手机。

2.1固定的内存分配

移动操作系统对应用程序内存使用情况了解很少。运行时垃圾回收器定期接触所有对象并对移动对象进行堆压缩，并且操作系统无法将此活动与应用程序访问区分开。移动应用程序还可以访问语言级别的对象，这些对象的大小各不相同，而操作系统只能以页面粒度跟踪内存访问。为了了解对象级访问对页面大小的访问跟踪的影响，我们测量了热门应用程序中对象的大小。图1显示了大小分布的CDF。大多数对象没有页面大小（例如，多达40%的对象小于4KB），因此操作系统无法准确跟踪它们的使用情况。

图2:固定分配的成本。每个栏显示一个热门应用程序的总Java堆大小，以及其在活动使用期间的最小Java工作集。

移动对象进行堆压缩，并且操作系统无法将此活动与应用程序访问区分开。移动应用程序还可以访问语言级别的对象，这些对象的大小各不相同，而操作系统只能以页面粒度跟踪内存访问。为了了解对象级访问对页面大小的访问跟踪的影响，我们测量了热门应用程序中对象的大小。图1显示了大小分布的CDF。大多数对象没有页面大小（例如，多达40%的对象小于4KB），因此操作系统无法准确跟踪它们的使用情况。

没有对应用程序内存使用情况的深入了解，今天的移动操作系统会为所有应用程序分配固定的内存预算。在Android上，无论应用程序是在前台还是后台，这个内存限制都是一样的。Android试图使用一些技术来最小化应用程序的内存占用，比如将所有应用程序从一个带有即写即拷页面的“合子”进程中派生出来。这些技术减少了框架数据结构和共享库的重复，但不影响Java堆中的应用对象。使用Marvin的对象级工作集估计器，我们测量了热门应用程序的工作集。图2显示，尽管这些应用程序的堆占用空间很大，但它们的工作集实际上只占总堆大小的一小部分。这种很少被访问的内存将被更好地利用来保持其他应用程序的运行，而不是浪费没有被使用的空间。

热门的应用程序通常有很大的内存占用空间，但工作集很小，因为它们尽可能的将数据放于云端。这种缓存可以提高性能，但会导致内存利用率低，选择正确的缓存参数是很困难的。更糟糕的是，现代应用程序经常超出其内存预算。解决这个问题需要应用程序实现手动交换存储，这增加了编程的复杂性。虽然像Glide和Fresco这样的缓存库很有帮助，但它们并不适用于所有内存对象。因此，今天的应用程序使用了复杂的库组合，并在内存和磁盘之间手工切换数据。

图3:有交换文件和内存压力的Android上的内存分配随时间的进展与没有内存压力的情况。

2.2无内存过量使用

如今的移动操作系统在物理内存耗尽时会结束应用程序，而不是交换到磁盘。他们采取这种方法是因为移动应用程序必须在数百毫秒内响应用户输入，所以将同步磁盘写入放在关键路径上的传统交换机制会带来太多延迟。为了测量交换对内存分配的影响，我们在我们的Android测试设备上启用了一个Linux交换文件，我们测量了当Android操作系统有空闲内存时，以及当它有交换文件和内存压力时，分配512MB所需的时间。图3显示了一段时间内内存分配的进度。在内存可用的情况下，操作系统在450毫秒内分配了所有512兆字节；然而，由于交换文件和内存压力，操作系统几乎花了8秒钟就分配了同样的内存。如果应用程序响应用户输入分配内存，那么如此高的分配延迟将是不可接受的。

图4:与从磁盘读取内存映像相比，重新启动应用程序的成本

结束和重启应用程序是有代价的。如图2所示，现代应用程序具有大内存使用足迹，重启的应用程序必须从网络或磁盘获取所有缓存数据。我们测量了重启常用应用程序所需的时间，并将其与从磁盘获取整个检查点内存映像所需的时间进行了比较。如图4所示，重新启动应用程序比从磁盘获取应用程序的所有内存要花费4-27倍的时间。

随时终止和重启应用的能力也给应用开发者带来了编程负担。现代操作系统给应用程序一个有限的时间预算来在被结束之前执行清理。这一限制导致应用程序不断写入状态到存储，事实上，Android鼓励这样做。这种针对应用生命周期事件的持续检查点增加了程序设计的复杂性，这是先前工作中描述的一个挑战。应用程序开发人员不仅必须管理检查点过程，他们还必须正确使用各种机制来实现良好的性能。为应用程序意外死亡做准备所需的编程工作是应用程序开发人员必须支付的额外成本。

3. 实现方法

改进移动操作系统内存资源管理的主要障碍是操作系统缺乏对语言运行时的精确洞察。为了克服这个障碍，我们设计了语言运行时和移动操作系统。移动操作系统特别适合这种协同设计，因为与桌面操作系统（如Linux）不同，它们强制所有应用程序使用相同的语言运行时。

Marvin的设计侧重于Android（和Android运行时（ART）），这是目前世界上最受欢迎的操作系统。使用语言运行时，Marvin完全按照对象粒度来管理内存，跟踪、回收和处理整个对象的故障。本节更详细地描述了在移动操作系统中实现更好的内存资源管理的障碍，以及Marvin如何应对这些挑战。

3.1对象级工作集预估

更好地管理内存资源的第一步是更好地理解每个应用程序的工作集。因此，Marvin在语言运行时实现了语言感知的工作集预估，它以对象粒度跟踪应用程序的读写。Marvin使用这种机制来识别提前交换的候选对象（第3.2节），并将垃圾回收器访问与应用程序访问分开（第3.3节）。由于缺乏硬件访问位来帮助进行这种跟踪，Marvin在ART-in-enterprise和编译器中实现了软件访问跟踪，因为现代移动语言运行时同时运行解释代码和编译代码。

3.2提前交换

综上所述，当操作系统需要内存时，交换到磁盘对于移动操作系统及其基于接触到的应用程序是不可行的。Marvin采取了不同的方法。传统的交换机制在需要内存时写入磁盘，而Marvin使用了一种新的提前交换技术。这种技术需要在之前将内存保存到磁盘，然后回收这些内存压力下的页面。提前交换将交换到磁盘与回收内存分开；因此，我们区分已复制到磁盘但仍驻留在内存中的已保存对象和不再驻留在内存中但仅驻留在磁盘上的已回收对象。

在需要之前，交换对象会留下大量干净的内存资源池，操作系统可以快速回收和重新分配。虽然这种技术允许应用程序继续使用内存，直到操作系统回收它，但每当应用程序弄脏页面时，交换机制必须更新磁盘上的副本，操作系统才能回收它。因为这种权衡，Marvin优先交换不常写入或从未写入的对象。

3.3书签垃圾回收器

像传统的交换一样，提前交换受到与语言级垃圾回收器的摩擦的影响。正如赫兹等人所指出的，当遍历对象堆寻找未使用的对象时，垃圾回收器可能会无意中在内存中分页。通过提前交换，垃圾回收器还可能在更新引用时无意中弄脏页面，从而导致不必要的磁盘写入。Marvin通过将一个修改过的书签垃圾回收器集成到Android Runtime中来解决这个问题。

Marvin的交换机制为每个回收的对象留下存根——类似于书签——详细说明对象对其他对象的引用。使用这些存根，它的垃圾回收器可以在标记和清除运行期间处理回收的对象，而不会在整个交换对象中出错。Marvin的交换机制可以通过丢弃死亡对象而不出错来进一步优化磁盘交换。

4.Marvin概述

Marvin是一个新的移动内存管理器，支持应用程序之间灵活的内存分配，并通过交换实现内存过量使用。Marvin包括语言运行时和操作系统中的组件，它们是协同设计的，以提供更好的内存管理。本节概述了两者。

4.1设计目标

Marvin的设计需要符合以下目标:

1. 快速分配内存。Marvin必须按需快速分配内存，避免在内存分配的关键路径上进行磁盘访问。

2. 高内存利用率。Marvin必须提供无限内存的结论，前提是工作集不超过物理内存的大小。

3. 最低消耗。Marvin必须实现运行时低消耗，并且不需要修改应用程序代码。

虽然后两个目标对所有内存管理系统都是通用的，但是现有的移动平台牺牲了高内存利用率来实现快速内存分配。Marvin的目标是实现所有这些目标。

4.2 Marvin系统模型

Marvin假设一个满足所有条件的系统环境:（1）所有应用程序都是用单一托管语言（例如Java）编写的；（2）所有应用程序都在单一托管语言运行时（例如ART）中运行；（3）运行时执行垃圾收集或某种形式的自动内存管理。可以满足Marvin设计目标的系统环境是Android。Android也运行一些使用本地代码的库；但是Marvin不需要管理它们的内存，因为它们在操作系统级内存管理方面没有托管语言那样的问题。

Marvin的优化也可以应用于其他操作系统（如iOS）。例如，Swift使用自动引用计数作为垃圾收集的替代方法，因此它需要一个书签引用计数器，可以跟踪引用而不会在整个对象中出错。

Marvin在基于ARM64的设备上运行未经修改的Android应用程序。Android以称为DEX的字节码格式分发应用程序。ART在解释器中直接运行DEX字节码，并且还在安装时（提前编译或AOT编译）和运行时（即时编译或JIT编译）将DEX编译为本机ARM64指令。Marvin修改了解释器和编译器。

4.3 Marvin架构

Marvin有两个关键的组成部分:（1）Marvin内核（MK），一个修改的Android/Linux内核；（2）Marvin运行时（MRT），一个修改的ART。大多数内存管理发生在MRT;它执行工作集估计、提前交换和书签垃圾收集。MK的唯一职责是通过决定何时以及从哪个应用程序回收内存来平衡应用程序之间的内存分配。

Marvin在对象粒度上执行工作集估计和交换；但是，没有针对对象级访问位和内存故障的CPU支持。因此，Marvin在MRT解释器和编译器中实现了软件对象访问跟踪和故障检测。解释器在运行DEX字节码时标记访问位并检查换出的对象；编译器将该功能作为附加的ARM64指令插入。Marvin在每个对象头中保留四个字节，并使用它们来存储交换元数据和访问位。在软件中实现这些特性会增加消耗，我们在第8节中对此进行了量化。未来移动设备的硬件改进可以减少这种消耗。

图 5.与传统（如Linux）交换机制相比，Marvin的交换机制执行的动作的时间表。时间线上列出了事件，下面列出了Marvin的应对措施。

4.4 Marvin内存管理时间轴

在应用行为和应用生命周期事件的驱动下，Marvin管理的对象随着时间的推移会经历几种状态。图5说明了这些事件和状态，并将Marvin的交换与传统的交换机制进行了比较。当一个应用程序第一次启动时，MRT开始跟踪它的工作集。它通过检查对象是否冷（最近没有被应用程序读取或写入）来识别适合交换的对象。MRT开始在后台将这些对象的检查点保存到磁盘。我们将具有已保存检查点的对象称为已保存对象。

当应用程序从前台移动到后台时，MRT会暂停应用程序线程，并创建存根（stubs），即在交换候选对象上添加一层间接层的小代理对象。存根确保Marvin可以拦截对对象的访问，并在必要时将它们错回。一旦MRT为一个对象创建了存根，该对象就变得可回收；该对象仍然驻留在内存中，但是MK可以随时回收其内存。MK回收一个对象时，进入回收状态；只有对象的存根保留在内存中，且在可以再次访问对象之前，对象的检查点需要故障返回内存。垃圾回收器只使用存根，不需要将对象错误地放回内存。

5.Marvin核心机制

如第3节所述，Marvin的关键特性是提前交换、语言感知工作集预估和书签垃圾收集。设计这些特性需要解决三个挑战:为对象引用添加一个间接层，在操作系统和运行时之间进行协调，以及插入对象访问。本节描述了Marvin应对这些挑战的机制。

5.1对象引用间接引用存根

根据Java语言规范，对象引用是不透明的。但是实际上对象引用Android运行时是指向保存被引用对象的堆内存的直接指针。这个设计需要Marvin注入一层间接性来实现像软件对象错误和书签垃圾回收器这样的特性。Marvin使用称为存根的特殊对象创建了这一间接层。每个存根包含一个指向其基础对象的指针，以及该对象持有的每个引用的副本。所有对对象的引用都指向它的存根，只有存根持有指向它的基础对象的指针。通过存根访问对象会增加消耗，因此Marvin只为至少为2KB的对象创建存根。

为对象创建存根时，Marvin将对象移动到单独的页面对齐的内存区域，然后重定向对该对象的所有引用以指向其存根。这些任务要求暂停所有应用程序线程。因此，如果Marvin可以一次为多个对象创建存根，使用堆的单次扫描来重定向所有受影响的引用，则可以更高效地执行这些操作。因此，Marvin会定期执行一个堆任务，该堆任务会暂停所有应用程序线程并创建存根，并且只有当应用程序处于后台并且其线程可以安全暂停时，它才会执行该堆任务。每个对象只创建一次存根，因此成本很低，尤其是因为Marvin不会频繁重启应用程序。

5.2用于操作系统运行时协调的回收表

现代移动平台拥有多核处理器，可以让系统服务与应用程序同时运行。在这种环境下，操作系统应该能够从正在运行的应用程序中快速回收内存，而无需调度应用程序的线程来执行。然而操作系统不能简单地从线程未被调度的应用程序中获取内存——一个指向相关内存的指针可能存在于应用程序线程的堆栈或寄存器中，等待线程再次被调度时使用。因此，操作系统和运行时需要一种方法来协调对对象的并发访问，这样操作系统就不会试图回收运行时正在访问的对象。

Marvin使用共享内存回收表来提供这种协调。MRT用可回收的对象填充表，MK用它来标识要回收的内存。每个回收表条目都是一个小的固定大小的数据结构，它保存对象的地址、大小、一组指示对象是否驻留在内存中以及条目是否有效的标志，以及一组用于运行时和操作系统锁定的位。要回收一个对象，MK首先获取该对象回收表条目的排他锁。类似地，每当应用程序线程准备访问对象时，MRT都会获取回收表条目的共享锁。

回收表是必要的，因为它提供了一个约定的位置，MK可以快速扫描以识别可回收的对象。如果回收表中的元数据存储在存根本身中，那么MK将需要扫描MRT的整个Java堆来识别可重新声明的对象，并且存根头将需要包含一个魔鬼数字或者为内核提供一些其他方式来识别它们。

5.3访问对象介入

Marvin的所有功能都要求运行时在应用程序访问对象时介入并执行特定任务。在每次访问对象时，MRT必须为工作集估计器设置读写位；检查存根的存在，并在必要时通过存根重定向对象访问和故障（如果对象已被回收的话）。每当对象被修改时，它还必须设置一个无效位，以便提前交换机制知道哪些对象需要保存，并且每当引用成员变量的相应对象发生变化时，它必须更新存根，以支持书签垃圾回收器。

Android应用程序既可以作为运行在解释器中的DEX字节码执行，也可以作为直接运行在硬件上的编译后的本机代码执行，Marvin必须干预这两种代码中的所有对象访问。因此，Marvin具有一组成对的解释器和编译器修改，增加了所需的对象访问插入。对于解释器在访问对象时执行的每个额外任务，编译器都有相应的变化，将执行相同任务的汇编指令添加到编译后的代码中。

6. Marvin内存管理

本节描述了我们如何使用Marvin的机制（存根、回收表和对象访问介入）来设计组成Marvin内存管理系统的特性。

6.1工作集评估

MRT通过以下方式执行对象粒度工作集估计在每个对象标头中维护两个访问位，一个读取位和一个写入位，并扫描这些访问位。

设置访问位。每当从解释或编译的代码中读取或写入对象时，MRT使用对象访问插入来设置对象的读写位。当垃圾回收器访问一个对象时，通过在对象头中设置一个标志，避免在其工作集估计中包含垃圾回收器读取，如果设置了该标志，则保持读取位不变。

MRT中的访问跟踪是在尽最大努力的基础上执行的，以最小化其消耗:在设置读写位时，MRT使用具有宽松内存排序语义的非原子操作。因此，对同一对象的并发读写可能会导致其中一个访问位的更新丢失。如果应用程序线程读取垃圾回收器正在处理的对象，对读取位的更新也可能丢失。如果估计的工作集和实际的工作集明显不同，这些优化可能会降低交换性能，但不会影响正确性。

扫描访问位。MRT定期遍历堆，并使用Clock算法来跟踪每个对象的长期使用情况。每个对象头包含两个四位移位寄存器，一个用于读取，另一个用于写入。堆遍历之间的时间构成了一个访问跟踪“循环”，每个移位寄存器跟踪对象在最后四轮中是被读取还是被写入。在堆遍历期间，MRT更新对象的移位寄存器，然后清除对象的访问位。MRT利用垃圾收集来扫描访问位，因为垃圾收集无论如何都需要遍历堆。一些ART的GCs只遍历堆的子集，因此MRT将其访问位扫描限制在全堆集合。它还定期调用GC来确保最新的工作集估计在没有应用程序活动的情况下。

生产工作装置。当MRT遍历堆并扫描访问位时，它会将应用程序的工作集制成表格。我们当前的MRT实现将对象视为工作集的一部分，如果它是在最近四轮访问跟踪中编写的。精确的策略是一个易于更改的实现细节。

6.2提前交换

在Marvin的提前交换机制中，MK回收对象并决定回收哪些应用。MRT执行所有其他功能，包括将对象检查点保存到磁盘，恢复回收的对象，以及防止操作系统回收应用程序代码正在使用的对象。

将对象保存到磁盘。MRT使用其工作集估计功能识别适合交换的对象（即冷对象），并主动将它们的检查点保存到磁盘上的交换文件中，以便在内存压力下可以快速回收它们。MRT以周期性堆任务的形式将对象保存到磁盘，该堆任务在后台线程上与应用程序代码同时运行。

在应用程序代码修改一个对象后，MRT必须将该对象的最新副本保存到磁盘上。它不需要立即保存更新的副本，只要它能防止内核在对象“无效”的时候回收它为此，MRT在对象头中保留一个无效位。每当应用程序代码写入对象时，它使用对象访问插入来设置这个无效位，并且它的对象保存堆任务在将对象保存到磁盘时清除这个无效位。MK在寻找要回收的对象时检查无效位，避免回收无效对象。MRT和MK在读写无效位时使用强内存排序语义，以确保对对象的修改不会丢失。

MRT甚至在为交换候选对象创建存根之前就开始将这些对象保存到磁盘。一旦MRT创建了一批存根，这些对象就可以立即回收，而不需要进一步的磁盘输入/输出回收对象。MK选择要重新分类的应用程序，并从与这些应用程序对应的MRT实例中回收对象。它从不针对前台应用程序，以避免前台应用程序用户界面线程的任何交换延迟。选择一个MRT实例作为目标后，MK会扫描MRT实例的回收表，直到找到一个既不脏也不被运行时锁定的对象条目。然后，MK锁定该条目并回收对象的页面。它继续扫描回收表并回收对象，直到从MRT实例中获取了所需的内存量。

每个MRT实例确保MK不会回收当前由其应用程序代码访问的对象。为此，它使用对象访问插入来检测何时读取或写入可回收对象，并在访问前锁定对象的回收表条目，在访问后解锁其条目。

还原对象。MRT要么急切地要么按需地恢复回收的物品。无论哪种方式，每当MRT恢复一个对象时，它都会锁定该对象的回收表条目，将该对象的已保存检查点数据复制到内存中，并将该对象存根中任何已修改的引用复制到该对象本身中。最后一步是必要的，因为当对象不驻留在内存中时，存根中的引用可能已被垃圾回收器修改。

Marvin渴望的对象恢复在应用程序代码需要对象之前，使用应用程序生命周期信息来恢复对象。我们实现了一个简单的快速恢复策略，当MRT实例过渡到前台时，它会恢复所有回收的对象。该策略增加了转换延迟，以保证没有交换延迟会阻塞前台应用的用户界面线程。我们的设计是灵活的，可以支持更先进的政策；例如，运行时可以预测哪些对象可能在提前交换立即被探触到，并用更短的暂停时间恢复这些对象，来换取用户可察觉的卡顿风险。

如果一个对象没有被急切地恢复，MRT会在应用程序代码访问它时按需恢复它，这个过程我们称之为软件对象故障。每当应用程序代码访问可回收对象时，MRT使用对象访问插入，通过检查回收表条目中的一个位来检查该对象是否驻留在内存中。如果没有，MRT执行一个对象错误处理程序，调用它的C++对象恢复函数。

6.3书签垃圾回收器

跟踪垃圾回收器接触堆中的每个对象（或堆的子集），导致活动对象被交换回内存，即使应用程序代码没有使用它们。Marvin的垃圾回收器通过将对象的引用存储在其存根中，并在垃圾收集的标记阶段使用存根来避免接触回收的对象。存根在书签收集器中扮演着类似书签的角色。在标记阶段，垃圾回收器维护一个标记堆栈，并从标记堆栈中反复弹出一个对象，标记其所有引用，并将这些引用推送到标记堆栈上。Marvin的垃圾回收器在从标记堆栈中弹出对象时会检查该对象是否为存根；如果是这样，它将从存根中读取引用，而不是访问基础对象。

为了让垃圾回收器使用存根来代替它们的对象，MRT必须确保驻留在内存中的对象的存根具有对象引用的最新副本。每当Java代码修改一个对象的引用成员变量时，它使用对象访问插入来更新可回收对象的存根。

MRT还必须在垃圾回收器释放任何保存的对象后进行适当的清理。MRT记录垃圾回收器何时释放了保存的对象，以及当交换文件中由释放的对象组成的部分超过设定的阈值（在我们的实现中为25%）时，它将交换文件打包到堆任务中。MRT还通过检查被释放的对象是否是存根来清理可回收和被回收的对象；如果是，它会删除对应于存根的回收表条目。如果一个对象是可回收的，MRT会删除底层对象的内存驻留副本；如果对象被回收，MRT只需在交换文件中标记其副本以供删除，而无需将其错入。

6.4权衡设计和替代方案

通过在运行时跟踪工作集和软件中对象的错误，Marvin实现了一个干净的设计，尽管有一些缺点。首先，Marvin无法回收本机库访问的对象:本机库无法检测存根，也无法在回收的对象中查找错误。第二，软件工作集预估和对象故障增加消耗，尤其是编译代码。我们在第8节中评估了这一消耗。

Marvin将几乎所有的内存管理都转移到了运行时中，因为我们相信运行时对应用程序行为信息的更好访问使得它更适合管理内存。保留在内核中的功能是现有Linux内核设计所要求的最低限度；如果Marvin构建在exokernel之上，它可以将更多的功能转移到运行时中。各种其他设计也是可能的，它们以不同的方式在运行时和内核之间划分功能。

内核级的工作集估计可以减少访问对象的过度消耗，但是如果应用程序的工作集与4KB页面上未使用的对象混合在一起，就会出现错误分割。内核级内存中的错误可以简单地减少对象访问消耗，但是需要更广泛地重新设计运行时垃圾回收器，以避免不必要的交换活动。通过将内存管理的粒度与页面的大小联系起来，内核级的内存管理也将变得不灵活，因为大页面变得越来越常见，对象大小和页面大小之间的差异也越来越大。无论如何，内核级内存管理都需要某种提前交换机制来满足现代移动平台的延迟要求（图3），甚至在Linux内核中添加提前交换也需要很大的努力。

内核级的工作集估计可以减少访问对象的过度消耗，但是如果应用程序的工作集与4KB页面上未使用的对象混合在一起，就会出现错误分割。内核级内存中的错误可以简单地减少对象访问消耗，但是需要更广泛地重新设计运行时垃圾回收器，以避免不必要的交换活动。通过将内存管理的粒度与页面的大小联系起来，内核级的内存管理也将变得不灵活，因为大页面变得越来越常见，对象大小和页面大小之间的差异也越来越大。无论如何，内核级内存管理都需要某种提前交换机制来满足现代移动平台的延迟要求（图3），甚至在Linux内核中添加提前交换也需要很大的努力。

Marvin的垃圾回收器与最初的书签收集器的不同之处在于，它使用存根维护精确的可通达性信息，而不是保守地存储近似的可通达性信息。后一种方法要求垃圾回收器在清除页面和扫描堆时执行更少的工作，但它可能导致堆被无用对象占用。

7.Marvin原型

我们在Android7.1.1（包括Linux 3.18.31）上通过修改ART实现了一个MRT的原型。我们的实现包括ART的ARM64编译器的修改版本，允许我们的原型支持搭载64位ARM处理器的Android设备。我们对ART代码库的更改导致了3475行额外的代码。

除了修改ART之外，我们对Android 7.1.1中包含的OpenJDK版本做了一个小的修改，也就是说，我们在Object类定义中添加了字段，以镜像ART中添加到对象头的字节。我们还更改了Android框架（ProcessList.java）中的一个源文件，以增加并发运行的应用程序数量的硬编码限制，因为Marvin能够运行更多的应用程序。

我们的实验要求我们手动触发回收，因此我们没有在MK中实现自动回收。但是，我们的MRT实现包括回收表，并执行支持内核内存回收所需的所有操作。

7.1对象访问介入

我们通过向ART解释器和编译器添加专门的功能来实现MRT的对象访问插入。这使得MRT可以从运行在解释器中的DEX字节码和本地运行的编译OAT代码中插入对象访问。下一节详细描述了我们如何修改每个组件。

MRT编译。ART解释器在内部将每个Java对象表示为一个C++镜像对象，在执行读或写对象的DEX字节码指令时对其进行操作。镜像对象的类型定义包括在对象内存占用范围内给定偏移量处读取或写入数据的方法，解释器代码在执行DEX指令时调用这些方法。为了在解释器中添加对象访问插入，我们修改了镜像对象方法来实现Marvin的特征。例如，为了通过存根重定向对象访问和按需执行对象故障，我们为每个镜像对象方法添加了一个preamble宏。序言首先检查对象是否确实是存根。如果是，它将this指针转换为存根，调用一个方法来锁定存根的回收表条目（RTE），检查RTE的驻留位，如果驻留位被清除。调用一个方法来在对象ROM磁盘中出错。然后，preamble从RTE获取基础对象的地址，并在基础对象上调用镜像对象方法。最后，如果任何ART包含多个解释器实现，那么preamble将解锁RTE并返回镜像对象方法的结果，并且默认为“mterp解释器”，这是一个用汇编编写的解释器。当mterp解释器执行读或写数组的DEX指令时，它直接访问数组的内存，绕过镜像对象方法。为了允许Marvin介入数组访问，我们使用了“切换解释器”，这是一个用C++编写的解释器，在执行数组访问时调用镜像对象方法。

MRT编译器。Android框架库中的Java代码和部分app Java代码作为本机代码执行，这些代码由ART编译器在安装后静态编译，或者通过即时（JIT）编译动态编译。我们通过修改编译器的汇编器来生成额外的汇编指令，在执行对象访问的代码生成时实现Marvin的功能，从而将对象访问插入到编译后的代码中。我们使用ARM64设备进行测试和评估，因此我们在ARM64汇编程序中添加了对象访问插入支持。上面描述的解释器实现存根重定向和对象错误的每个操作在编译代码中都有一个相应的ARM64指令块。主要区别在于，当检测到存根时，编译后的代码必须用底层“真实对象”的地址显式覆盖保存存根地址的寄存器，然后在处理完对象后将存根的地址加载回该寄存器。在通常情况下，当一个对象不是存根（或者当它是存根，但是它的底层“真实对象”是内存驻留的）时，执行分支通过许多添加的对象错误指令。

7.2局限性和潜在的优化

我们的MRT编译是一个研究原型，因此有一些局限性。一个是从黑盒商用程序中回收对象时的不稳定性。当运行我们在Android Studio创建的应用程序时，MRT可靠且一致地回收和恢复对象，但当运行启用了存根创建和回收的商用程序时，它往往会崩溃。MRT的对象访问插入在商用中工作正常，因此通过禁用存根创建和回收，我们可以测试其消耗并收集工作集数据。我们的MRT原型也不支持使用实时JNI全局引用来回收对象，也不支持通过JNI直接访问可回收数组的内存。

我们在MRT编译器中实现的对象访问插入是未优化的，通过更深层次的编译器集成，可以减少编译代码的每对象访问消耗。我们修改了ARM64汇编程序，它将中间表示（IR）指令转换为ARM64二进制代码。我们的实现为读取或写入对象的每个红外指令生成执行对象访问插入的ARM64指令，即使其中许多指令只需要在对象的寄存器分配开始或结束时执行。编译器的优化版本，在IR级别进行修改，可以减少编译代码的执行和大小消耗。

图6:Marvin从具有不同工作集大小的基准测试应用程序中回收内存时的内存使用情况

MRT编译器还有其他需要优化的地方。例如，我们注意到ARM64参数寄存器（x0–x7和d0–D7）看起来是活动的，但是没有被ART编译器的LocationSummary类这样重新移植；因此，在执行过程调用时，我们保守地将所有参数寄存器保存到堆栈中。仅保存活动参数寄存器将进一步减少代码大小消耗。此外，ARM64汇编程序使最多两个暂存寄存器随时可用，这要求我们保存反向指针，并添加更多指令来在有限的可用寄存器中平衡所需的状态。

8.评估

我们的评估表明，Marvin成功地达到了设计目标。它可以:（1）按需快速回收内存；（2）通过在应用程序之间共享内存而不是结束它们来保持高内存利用率；（3）以及以低消耗和不改变应用程序的方式实现前两个目标。

8.1评估标准

我们在谷歌Pixel XL智能手机上运行了我们的实验，该手机具有4GB内存和四核高通骁龙821中央处理器。智能手机要么运行Android7.1.1的开源版本（AOSP标签Android-7.1.1_r57），要么运行基于该版本的我们的Marvin实现。我们的Marvin实现和我们的基准Android构建都包括对Android框架的更改，以增加并发运行的应用数量的硬编码上限。

我们的实验混合使用合成应用程序进行基准测试和真实应用程序。与Android相比，我们构建了几个模拟各种内存占用和工作集大小的合成工作负载来衡量它们对Marvin的影响。我们还使用了基于真实应用的商业基准应用程序PCMark for Android来衡量Marvin在真实应用上的消耗[3]。我们从测试套件中选择了两个基准测试（编写2.0和数据操作），因为剩下的三个测试将测试本机库的性能。

8.2内存回收

当新的或现有的应用程序需要分配大量内存时，Marvin必须能够从运行中的应用程序中快速回收内存。它的提前交换机制确保每个MRT实例都有一个干净的内存池，可以快速回收，而无需交换到磁盘。在本节中，我们测量了不同工作集大小的应用程序回收内存的延迟。回收延迟取决于应用程序的工作集大小，因为Marvin可以从工作集较小的应用程序中回收更多内存。

对于我们的原型，我们使用madvise将内存从MRT返回到内核。这种设计让我们可以触发回收，而不是等待内存压力。我们的MRT原型在应用程序过渡到后台时回收内存，然后在后台定期回收内存。

图7:随时间变化的活动基准测试应用实例的计数Marvin在需要关闭任何应用程序之前，运行的应用程序数量是普通Android的两倍以上;在有交换文件的Android上，大多数应用程序是活的，但由于不断的交换活动而处于不活跃状态。

Marvin在52ms内返回了250MB的内存，在108毫秒内返回了500MB的内存。相比之下，如图3所示，带有Linux交换文件的Android在内存压力下，释放和分配500MB内存需要将近8秒。使用提前交换让Marvin回收内存的速度比Android快60倍以上使用Linux交换可以分配同样多的内存，让Marvin满足移动应用的严格延迟要求。

8.3内存利用率

为了展示Marvin更高效的内存管理器，我们运行了一个内存占用量大、工作集有限的应用程序的多个实例，并统计了活动应用程序的数量，这些应用程序正在工作负载上取得进展。每个应用程序都有一个220兆字节的数组堆，它每5秒钟删除并重新分配200兆字节的数组。我们使用了两种不同的堆组合:一种是应用程序的堆填充了4KB数组，另一种是应用程序均匀混合了4KB和1MB数组（类似于图1中真实应用程序的双峰分布）。如果一个应用程序在前一轮工作负载后20秒内未能执行一轮工作负载，我们认为它“不活动”；如果它在前一轮的7秒内成功执行了一轮工作负载，我们认为它再次“活跃”。我们每10分钟启动一个新的应用实例，让Marvin有时间执行后台工作。对于未修改的Android系统，只显示带有4KB阵列的应用程序的数据，因为它在4KB/1MB混合模式下的行为几乎相同。

如图7所示，在启用了Linux交换文件的情况下，Marvin运行的活动应用程序是未修改的Android的两倍多，是Android的1.5-2倍多，随着实验的进行，交换导致几乎所有应用程序都不可用。虽然基准Android在物理内存耗尽时开始扼杀应用，但带有swap的Android让更多应用保持活力。然而，在没有书签垃圾回收器的情况下，系统经历了持续的交换活动，这阻止了大多数应用程序在其工作负载上取得进展。我们的实验由于设备崩溃，带有交换文件的Android系统的运行一直提前结束。

图8:Android基准测试结果的PCMark

Marvin更好地利用了设备内存，因为它从应用程序中重新获取了未使用的内存，并使用其书签垃圾回收器来避免在运行垃圾收集时触及未使用的内存。虽然Android只并发运行了10个应用程序，而带有交换文件的Android只短暂地达到了最多13个并发应用程序（4KB阵列）或20个应用程序（4KB/1MB混合），但Marvin同时运行了27个应用程序（4KB阵列）或30个应用程序（4KB/1MB混合）。Marvin的内存回收和书签垃圾回收器让它可以同时执行1.5-2倍的应用程序，同时既不会结束应用程序，也不会降低性能。

8.4运行时开销

虽然Marvin提供了更好的内存管理，但它也有一系列的权衡和折中。本节量化了Marvin的四个消耗来源:（1）由Marvin在编译后的OAT代码中插入对象访问引起的执行时间消耗；（2）由于对象访问插入，增加了编译代码的大小；（3）Marvin的工作集估计的堆遍历导致的CPU利用消耗；以及（4）当应用程序访问回收的对象时的错误消耗。

对象访问插入的执行时间消耗。由MRT编译器生成的本机代码有额外的ARM64指令来支持对象访问插入。一些指令（存根检查、脏位更新和访问跟踪位更新）在每次对象访问时执行。其他指令（通过存根和锁定RTEs间接访问对象）只在访问可回收对象时执行。我们使用Android的PCMark测量了应用于所有对象访问的附加指令的消耗，并使用一个合成基准来说明该消耗对应用程序代码组成的依赖性。

图8比较了在我们的测试集中，在PCMark基准测试中，Marvin和未修改的Android的性能。每个条形显示五次运行的平均值和标准偏差。在运行PCMark时，我们关闭了存根创建和交换，使用基准测试来测量添加到每个对象访问中的存根检查和工作指令的消耗。

图9:在具有不同对象访问插入比例（OAl）的合成工作负载下，Marvin的消耗。点（0,0）表示不运行任何OAl的理论场景，其他点表示实验结果。

集合评估。Marvin在Writing 2.0基准测试中的得分几乎与Android相同，在Data manufacturing基准测试中的得分仅低15%。这些分数表明，对于现实世界的应用程序，Marvin访问常规（即不可回收）对象的消耗很低。

图9探讨了Marvin的消耗对应用程序代码的DEX指令组合的依赖性。该图显示了Marvin执行合成工作负载的消耗，该工作负载执行了比例可调的对象访问（数组读写）和整数运算（加法和乘法）。每一点都代表了在40次工作负载迭代中，Marvin相对于Android的执行时间消耗的平均值和标准差。对于大比例的对象访问，Marvin具有相对较高的消耗（例如，对于40%的对象访问，消耗为350%），而对于低比例的对象访问，Marvin的消耗最小（例如，对于1%的对象访问，消耗为10%）。PCMark 15%的消耗表明，以PCMark为代表的真实应用工作负载的对象访问比例较低。

虽然这些消耗已经很合理了，但是可以通过优化来改善。如第7节所述，更深层次的编译器集成可以让Marvin减少执行对象访问插入的频率，从而减少消耗。

图10:基准测试应用程序在接触堆中回收对象的不同部分时的速度

通过调用并发垃圾回收器进行计时，并利用其堆遍历进行计时。当应用程序在前台时，我们的原型每5秒执行一次堆遍历，当应用程序在后台时每30秒执行一次堆遍历。理论上，这种跨多个MRT实例的垃圾回收器周期性调用可能会增加CPU使用消耗。在实践中，当在后台运行多个应用程序时，我们发现Marvin和未修改的Android的CPU利用率之间的差异可以忽略不计，可能是因为后台应用程序的GC调用很少。

对象中的故障消耗。当一个应用程序第一次访问回收的对象时，Marvin必须将其从磁盘中取出，这增加了初始访问的延迟。Marvin的默认策略是，当应用程序移动到前台时，立即恢复所有对象，以较长的过渡延迟为代价，以保证对象错误延迟不会阻塞应用程序的UI线程。增加的转换延迟与回收的内存数量和恢复速率成正比。有趣的是，我们的原型以大约100 MB/s的速度恢复了内存。但我们相信，通过优化，速率可以提高到260mb /s左右。（ART使用的C++标准库实现的磁盘读取速度较慢，而Android独立工具链链接的标准库实现的速度较快。）对象错误可能会在后台应用程序中发生，但是后台应用程序的Java工作集通常非常小（在我们的测试集中，所有商业应用程序的工作集都小于4MB），所以我们认为对象错误在实践中很少发生。

尽管如此，我们还是研究了对象故障对性能的影响，以了解在不同的策略或工作负载导致更多对象故障的情况下，Marvin将如何表现。图10显示了当堆行走基准应用程序接触到回收对象的不同部分时，对象错误的影响。该应用程序在一组4KB数组上循环，读取每个数组的五个成员变量，并测量遍历对象的速度。每个条形显示五次测量的平均值和标准偏差，并且设备的磁盘缓存在每次运行前都已清除。不出所料，堆步速度与故障率成反比关系；例如，当故障率从10%增加到20%时，速度下降了49%。

9. 相关工作

一些现代系统为移动平台提供了交换，但是侧重于页面粒度而不是对象粒度交换。SmartSwap预测哪些应用程序不太可能被使用，并提前从这些应用程序中交换页面。A2S采取了相反的方法；它避免了从未使用的应用程序中换出页面，因为无论如何，当它们被终止时，它们的页面都会被释放。MARS优化了Linux交换，以提高闪存设备的性能。它禁用后台应用程序中的垃圾收集，并从这些应用程序中回收内存。DR.Swap使用NVRAM而不是闪存来存储换出的页面，并通过直接从NVRAM读取来满足读取需求。Choi等人通过协同设计交换机制来最小化I/O，从而提高内存中文件系统的性能。

Linux内核包括一个守护进程kswapd，它在后台释放未使用的页面，以维护未分配内存的保留池。像Marvin一样，kswapd主动检查未使用的内存，但与Marvin不同，kswapd在检查页面时会重新声明页面。因此，kswapd可以提前检查的内存有限，保持大部分内存被检查和回收会使内存不可用，并缩小设备的有效内存占用空间。

Liang等提出了FAST，这是一个Android内存管理系统，它修改了kswapd以提高其对Android的适用性。FAST将kswapd更改为优先从后台应用程序中回收页面。它还确定了kswapd的大回收大小和典型Android分配的小回收大小之间的不匹配，并包括一个预测器，用于根据工作负载模式确定回收大小。像FAST一样，Marvin避免从前台应用程序回收内存，但Marvin的不同之处在于其运行时级内存管理以及检查点和回收的解耦。

大量的工作研究了为面向对象语言提供持久内存的问题。这些系统检查磁盘或非易失性内存中的对象，但它们这样做是为了在出现故障时确保安全，而不是交换未使用的内存。因此，他们专注于支持在失败情况下提供强有力保证的事务性编程模型，并致力于实现崩溃安全的垃圾收集，而不是最大化可以并发运行的应用程序的数量。SSDAlloc是一个持久性内存系统，与Marvin一样，其动机是帮助内存占用量大的应用程序避免内存压力。与Marvin的运行时级对象错误和工作集估计不同，SS- DAlloc在单独的虚拟页面中分配对象并使用现有的虚拟内存系统估计工作集并触发其对象故障处理程序。

像Marvin一样，书签收集器旨在改善内存受限环境中Java应用程序的性能。它假设操作系统使用传统的页面级交换机制，并专注于让垃圾回收器在没有不必要的交换的情况下运行。它保守地存储垃圾收集期间使用的近似可达性信息（书签），而Marvin存储精确的可达性信息（存根）。BMX垃圾回收器[15]也使用存根来避免昂贵的对象访问，但是在分布式持久对象存储的上下文中。

最近关于垃圾收集的其他工作集中在协同设计GC和运行时以更有效地管理软件缓存，协同设计GC和虚拟内存管理器以提高性能，测量GC对可伸缩性的影响，以及为大数据系统等领域设计GCs或内存管理器。

由于多个运行时在单个操作系统上管理自己的内存，Android的架构类似于虚拟机管理器，多个客户操作系统在一个虚拟机管理程序上运行。Marvin的运行时-操作系统协作类似于VMware ESX服务器中来宾操作系统和虚拟机管理程序之间的协作，后者使用气球驱动程序来引导来宾操作系统回收内存。Wright等人提出了一种系统，其中架构和Java运行时被联合设计以提高内存访问性能。它的特点是硬件修改允许对象寻址的中央处理器缓存和缓存内垃圾收集。

Wright等人提出了一个系统，其中Marvin架构和Java运行时是为了提高内存访问性能而共同设计的。它对硬件进行了修改，允许使用对象寻址的CPU缓存和缓存内GC。

10. 结论

使用移动设备的用户希望系统能够低延迟的完成应用程序之间的切换。然而，随着移动应用程序对内存的需求越来越大，移动设备内存容量却没有跟上步伐，传统的交换机制无法满足用户的延迟预期。Marvin通过一种新颖的运行时级交换机制克服了这一挑战，该机制可以准确估计工作集，将磁盘输入/输出移出分配关键路径，并避免垃圾收集期间不必要的交换。正如我们的实验所证明的，Marvin可以让更多的应用程序同时运行，并且可以通过合理的消耗，达到比未标准化的Android更快地回收内存。

---煤油灯科技victorlamp.com翻译整理---