MARS:通过闪存感知的页面交换,让移动应用重启加速

煤油灯科技2022-02-14 16:01

摘要

在当前Android系统上快速重启应用的方法是在内存中缓存后台应用,此机制受可用内存大小的限制。此外,应用程序状态可能不容易恢复。我们提出了一个原型系统MARS,以支持页面交换和缓存更多的应用程序。MARS可以加速应用程序重启并恢复应用程序状态。作为一种用于优化应用程序重启的新页面交换设计,MARS将Android运行时垃圾回收(GC)从页面交换中分离出来以实现兼容性,并采用了几种闪存感知技术来实现换入加速。MARS的两个主要组件是页槽分配和读/写控制。页槽分配重新组织交换区域中的页槽,以产生顺序读取并提高换入的性能。读/写控制通过减少并发和额外的内部写入来解决读/写干扰问题。与传统的Linux页面交换相比,这两个组件可以将读取带宽放大到约3.8倍。在谷歌Nexus 4手机上进行的应用程序测试表明,MARS将应用程序的启动时间缩短了50%到80%。改进后的页面交换机制的性能比传统的Linux页面交换机制高出4倍。

1.引言

智能手机及其上运行的应用程序在我们的日常生活中扮演着重要的角色。如今人们花在智能手机上的时间比以往任何时候都多。毫无疑问移动应用程序的响应速度是一个影响用户体验的重要因素。

随着越来越多的应用程序在智能手机上可用,并且用户倾向于与多个应用程序交互,应用程序的启动时间不应被忽视。很明显,启动过程可能包括I/O或网络请求、图形渲染、位置传感器以及一些初始化计算,每一项都需要时间来完成。根据对12名Android用户为期两个月的跟踪,大多数移动应用程序的交互只持续大约几十秒到几分钟。如果启动成本超过交互时间,例如超过几十秒,将不可避免的对用户体验产生负面影响。

一些先前的工作试图减少用户感知的启动时间。例如,在[1]中,作者使用预测和预启动来减少应用程序启动期间的响应时间。然而,预启动不能通过初始化来减少固有的时间成本,只能是一定程度减少用户感知时间。并且如果预测失败,则启动保持迟缓并且系统资源也被浪费。预测精度必须很高,否则会降低预启动的收益。

我们还在寻求通过提高应用程序重启的性能来减少应用程序启动的感知时间的方法。我们从观察中了解到,用户通常会多次运行同一个应用程序,并同时使用多个应用程序。 例如,用户可能会痴迷于Facebook,并在日常使用中多次启动它。用户很可能会点击其朋友共享的URL,这通常会启动一个Web浏览器,然后用户又快速返回到Facebook。在这种情况下,一些应用程序会被一次又一次地重启,这就提供了一个新的机会,在重启过程中改善启动时间。

根据观察,在内存中缓存应用程序是一种显著的做法。 这实际上是系统在当前移动平台中的工作方式。例如,Android可以将后台应用程序缓存在内存中,并在内存较低的情况下简单地杀死它们以回收内存。这是因为Android管理每个应用程序的生命周期,并提供API来保存应用程序的特定状态。因此,状态信息可用于在重启之后恢复应用程序,这使得缓存的应用程序可以立即重启和恢复状态,降低被杀死的危害。

然而,应用程序缓存仍然存在两个问题:复杂应用程序的内存大小和可恢复性。至于移动设备上有限的内存大小,只能缓存中等数量的应用程序。仍需要终止应用程序以回收内存。它重启应用程序并将其恢复到以前相同的状态需要很长时 间,这肯定会损害用户体验。此外,当应用变得更加复杂时, 恢复到先前相同状态的假设不容易实现。例如,Android提供的用于存储应用程序状态的API需要将输入作为Bundle对象(从字符串值到Parcelable对象的映射)。很难有效地将游戏应用程序的运行状态信息导出到Bundle对象中。因此,我们认为移动应用程序不应该被简单地扼杀。

页面交换可以缓解上述两个问题。它为缓存应用程序及其完整状态提供了更多的内存空间。应用程序现在不需要从头开始重启。相反,需要加载来重建相应应用程序的内存映像。作为引导程序代码不需要再次执行,重启可能会很快。

可以在Android上启用页面交换,以便快速重启应用程序。不幸的是,出于闪存和电池寿命的考虑,Android在Linux内核中禁用了页面交换。最关键的原因是页面交换和Android运行时垃圾回收(Runtime GC)1 之间的不兼容性。另一个挑战是页面交换的速度。目前大多数智能手机都配备了eMMC2,以提高能效和高密度存储容量。然而,在这种类型的存储中,从交换区域重新加载数据的效率通常很低。因此加速页面交换对于提高应用程序重启的性能具有重要意义。

为了解决这两个问题,本文提出了MARS

在Android上实现面向应用重启的Linux页面交换再设计的原型系统。MARS采用了几种新的设计来构建支持闪存的页面交换机制,以加速应用程序的重启。

1) MARS通过改造Android运行时和Linux页面交换,构建了一个与运行时GC兼容的页面交换机制。

2) MARS重新设计了交换区的数据组织,并仔细控制交换中涉及的读写操作,以避免性能问题。

3) 我们已经测试了我们的原型系统。与传统的Linux页面交换相比,MARS中的页槽分配和读/写控制这两个组件可以将读取带宽扩展到大约3.8倍。在谷歌Nexus 4手机上进行的应用程序测试显示,MARS将应用程序的启动时间缩短了约50% 至80% 。改进后的页面交换机制的性能比传统的Linux页面交换机制高出4倍。

本文其余部分的结构如下。第2节描述了我们建造MARS的动机和遇到的技术挑战。第3节介绍了MARS的设计和实现。我们评估MARS:

1. 我们将其表示为运行时GC,以使其不同于闪存GC(由闪存存储中的闪存转换层执行的闪存块垃圾回收,用于回收脏块)。

2. 嵌入式多媒体卡,一种用于绝大多数移动设备主存储的NAND闪存。

图1.12个Android用户超过2个月的应用程序使用

我们开发了一个名为“ASTAT”的Android应用程序,用于跟踪Android手机上的应用程序交错。在志愿者的许可下,安装在智能手机上的ASTat收集应用程序使用痕迹。跟踪中有25948个应用程序交互。持续时间小于10 秒的个数为10345 。有16946个应用程序交互持续不到1分钟。许多移动应用程序仅持续几秒钟,但使用非常频繁,例如消息、天气预报和实用程序。例如,应用微信在痕迹中有1624次小于10秒的交互。

然后是第5节中的相关工作和第6节中的结论。

2.动机和技术挑战

运行在智能手机上的应用程序与运行在桌面或服务器上的应用程序具有不同的特性。此外,智能手机上的应用程序重启频率远高于其他平台。本文提出MARS通过增强应用启动性能来改善用户体验。在本节中,我们通过回答以下问题来说明我们建造MARS的动机:

•应用程序启动速度慢是一个严重的问题吗?

•最先进的解决方案的局限性是什么?

•为什么要构建MARS而不是使用(启用)原始的Linux 页面交换?

2.1应用程序启动分析

与服务器平台上长时间运行的任务不同,移动应用程序的大量短而频繁的交互是很常见的。事实上,对于移动应用来说,用户体验比性能更重要。用户体验研究[2]显示,10秒是最大等待时间。即使是最新的智能手机,一些流行应用程序的启动时间也长达几十秒。

我们从12个Android用户那里收集了两个月的跟踪数据。从6月到8月,在志愿者的Android手机上安装了一个应用程序使用跟踪器(有他们的权限)

图2.Android上的一些热门应用程序的启动时间

应用程序的启动时间是通过检测Android应用程序框架来测量的。我们选择Activity类的“StartActivity”函数作为开始时间点,ActivityThread类的“HandleResumeActivity”函数作为结束时间点。但是,有些应用程序会先显示闪屏,然后过早地回调Activity类的“onResume”函数。例如,游戏应用程序更新场景的渲染远远落后于恢复的活动。我们进一步检测InputDispatcher类,以跟踪应用程序能够与用户交互的时间点。

图3.使用Android TraceView进行游戏应用程序PVZ 2启动分析Android TraceView是一个图形查看器,用于通过Android DMTraceDump进行应用程序分析。面板顶部有一个时间轴。每个线程的执行都显示在自己的行中,时间向右增加。每个方法都以不同的颜色显示(颜色以循环方式重用,从具有最多包含时间的方法开始)。标记了一些关键方法。

图1显示了应用程序使用持续时间的CDF。超过60%的应用程序交互持续时间从几秒到几十秒。并且大约85%的相互作用持续不到5分钟。[3]中报道了一些类似的结果。研究结果支持这样的观点,即移动交互的持续时间本来就很短,并且应用程序经常重启。此外,我们观察到用户倾向于同时使用多个应用程序。这通常是由于智能手机的使用模式。用户往往会拿出智能手机,使用一段时间后再放回去。

我们选择了Android Market上的各种流行应用来量化应用启动问题。图2显示了这些应用程序的启动时间。启动时间被测量为从用户点击应用的快捷方式图标的时间点到用户能够与应用交互的时间点的时间跨度。这些应用程序中有一半需要5秒以上。在交互可用之前,它们中只有一个需要不到2秒的时间。结果表明,启动确实需要时间,并损害了应用程序体验。

为了更深入地了解应用程序启动过程中所做的工作,我们使用Android DMTraceDump和TraceView工具来帮助分析应用程序的启动过程。以PvZ 2的游戏应用为例,3是其TraceView 的屏幕截图。为了便于说明,标记了一些有代表性的函数调用。每个平行时间轴代表一个线程。对于这个游戏应用程序大部分工作都是由“GL线程”完成的。有许多使用OpenGL库进行图形渲染的初始工作。其他工作(如网络和I/O)与初始进程混合在一起。传统的网络和I/O预取方案[4]、[5]不能解决这个问题,因为它们中的大多数与图形渲染重叠。这表明应用程序启动过程实际上是固有的,并且在从头开始启动期间很难避免。

2.2当前解决方案的局限性

移动系统的当前设计使得难以减少从头开始启动或重启的时间。以Android为例,我们可以看到应用程序生命周期以 及内存管理中的细节。操作系统而不是开发人员管理应用程序的生命周期。这意味着当前台应用程序切换到后台时,根据当前内存利用率,该应用程序将被杀死或缓存。Android使用低内存来立即回收后台应用程序占用的内存。低内存根据进程的Badness值选择要杀死的应用程序。Badness值是由Linux Out of Memory(OOM)Killer计算的数字分数, 它判断是否应该选择进程作为终止的候选进程。要在终止后 还原到重启的应用程序的确切先前状态, Android为开发人员提供了用于保存和恢复系统状态信息的API。这里的假设是:

1)开发人员应该确切地知道如何使用系统API来保存状态信息;

2)将状态信息导出为这些API所要求的数据输入格式是可行且高效的。

但是,对于某些应用程序(如游戏)很难恢复以前的相同状态,因为API(仅支持Bundle对象)有限,并且要保存的状态可能很大。随着移动应用程序复杂性的增加,这种困难变得更加严重。它确实给应用程序开发人员带来了一些负担,他们必须仔细考虑应该保存什么样的状态。此外,重启应用程序所需的时间与从头开始启动应用程 序所需的时间相同,并且由于包含恢复工作,可能需要更长的时间。

在移动操作系统中,将后台应用程序缓存在内存中以实现快速应用程序重启是一种传统的解决方案。这种传统的缓存方法受到智能手机可用内存的限制。某些占用大量内存的应用程序可能会在后台缓存后立即被终止。因此,缓存后台应用程序以促进应用程序启动的效果有限。

对于这个问题,已经出现了一些基于应用程序启动预测的预启动解决方案。一个具有代表性的例子是Falcon[1],它是一种在Windows Phone(WP)上启动应用程序时改善用户体验的新颖解决方案。Falcon的基本思想是预测使用应用程序的时机。因此,它可以在用户手动启动预测的应用程序之前预先启动它。通过这种方式,可以减少感知的发射时间。预测基于上下文信号和访问模式。由于不同用户的预加载预测规则集是不同的,因此Falcon训练单独的上下文触发器以提高准确性。Falcon同时考虑了预期的延迟收益和能量成本,以减少意外副作用的可能性。有了Falcon,即使预测准确,可用内存的限制也无关紧要。然而, 根据评估,自举猎鹰要达到80%的精度需要超过8个月的训练。此外,应用程序启动的可预测性因用户而异。这些因素极大地限制了Falcon的有效性。

我们的解决方案通过使用页面交换扩展了状态缓存机制。 因此,该方法不基于任何不精确的信息,例如预测。使用页 面交换,我们可以扩展虚拟内存以容纳更多的后台应用程序, 也就是说,不需要立即终止应用程序。因此,页面交换的性 能是该解决方案实用性的关键。在下一个小节中,我们将讨论有关此问题的技术挑战。

2.3技术挑战

在Android上启用页面交换以快速重启应用程序在两个方面具有挑战性,即兼容性和性能。

对于兼容性问题,页面交换实际上与Android运行时冲突。Android应用程序在Android运行时上运行(Android 4.4之前的Dalvik或Android 4.4上的Experimental Art)。Android 运行时采用了激进的GC。它不仅可以在堆上分配新对象时触 发,还可以在应用程序处于后台时触发。对于Android运行时, 页面交换尤其是灾难性的。在运行时用完允许的堆之前,不会执行完整的运行时GC周期。然而,在那个时候,垃圾对象 很可能占据了堆的大部分。由于垃圾对象通常在运行时GC启 动之前不会被触及,因此如果启用了页面交换,这些对象应该更有可能被换出。当运行时GC最终运行时,将会有一个荒谬的交换.把所有这些东西都拉进来,却发现它们确实是垃圾, 应该被丢弃。这说明了为什么页面交换与运行时GC冲突。由于应用程序生命周期是由操作系统控制的,因此在回收内存方面,低内存杀手比页面交换更有效。此外,页面交换中额外的闪存写入会减少闪存存储和电池寿命。所以原来的Linux 页面交换在Android上是关闭的。要启用页面交换,我们必须对其进行改造以适应Android运行时。

对于性能问题,Android上传统Linux页面交换的换入性能对于快速重启应用程序是不可接受的。这是由于eMMC(嵌入式多媒体卡)在智能手机上的特点,缓慢的小散读以 及读写的干扰。

• 慢速小型分散读取:由于未公开的内部设计,小型分散读取比eMMC上的顺序读取慢十倍(如表1所示,4 KB大小的顺序读取约为60 MB/s,4 KB大小的分散读取约为6 MB/s)。但是,当应用程序在Android上重启时,Linux页面交换并不能保证要交换的页面是相邻的。在Linux页面交换中,交换区域(交换分区或交换文件)被划分为许多页面大小的插槽。每个插槽称为“页槽”或“交换槽”。尽管Linux页面交换试图在集群中分配页槽(许多连续的页槽),但当交换分区变得混乱时,这就变得很困难。此外,Linux页面交换使用近似最近最少使用(LRU)算法来选择要换出的内存页面。要换出的连续页面并不总是来自同一后台应用程序。

• 读/写干扰:

1)并发读取和写入可能会降低彼此的性能,因为混合的读取和写入会中断闪存的内部流水线操作。然而,在Linux页面交换中,换入和换出经常同时发生。重启通常需要换入操作,在这种情况下无法保证性能。

2)闪存的潜在垃圾回收(Flash GC)会产生额外的读写操作, 也会带来干扰。

为了解决这些兼容性和性能问题,我们设计并实现了MARS来取代Android上的Linux页面交换,以提高应用程序重启的性能

3.设计和实现 

3.1 MARS概览

MARS是一个改装的Linux页面交换兼容Android系统。MARS的设计目标是获得换入加速,以便更快地重启应用程序。MARS的结构如图4所示MARS中有两个主要组件:页槽分配和读/写控制。前者旨在减少分散读取,而后者减少了闪存读写的干扰。由于智能手机上的低端NAND闪存存储是加快换入的目标,主要工作集中在以下几个方面:

图4.MARS的结构

运行时GC和页面交换的隔离分为两个部分。一个是后台应用程序没有GC,另一个是前台应用程序和长期服务没有页面交换。页槽分配尝试在换入时生成顺序读取。读/写控制旨在消除页面交换期间闪存读写的干扰。

Android运行时上的修改:

1)由于我们已经说明了Linux页面交换与运行时GC的冲突,我们首先禁用后台应用程序的“空闲运行时GC”来缓解这个问题。

2)然后收集应用启动事件作为提示信息来指导读/写控制组件。

3)由于在MARS中采用页面交换来回收内存,因此禁用低内存杀手。

Linux页面交换的修改:由于传统的页面交换没有针对智能手机进行优化,我们修改了Linux页面交换的几个方面。第一种是使前台应用程序和长期服务绕过页面交换,以避免与运行时GC的潜在冲突。我们还重组和管理交换分区,以利用智能手机上eMMC的特性。添加了一个自适应的空闲内存水印,以帮助控制页面交换行为。页面缓存的回写机制也略有修改,以减少应用程序重启期间的闪存写入。最后,我们使用后台修剪方法来减少Flash GC的额外读写。

3.2 兼容性改装

为了解决Linux页面交换和Android运行时GC之间的冲突,我们将它们隔离开来, 而不是让它们相互协作。这是由于Android运行时GC的设计要求。Android运行时GC比Java运行时更频繁地运行,以保持较小的内存占用。因此,我们试图让运行时GC保持简单和快速,而不是增加复杂性和延迟。为了隔离Linux页面交换和Android运行时GC,MARS需要改进Linux页面交换和Android运行时框架。

对于后台应用程序,MARS修改了Android运行时GC行为以与Page兼容交换。Android上的完整运行时GC通常需要数百毫秒。这是一 个很长的时间,大大降低了运行时性能。在Android 2.3之后, 当应用程序运行时,仅执行部分运行时GC。Android运行时通过以下方式缩小变大。

当应用程序空闲时,即应用程序在后台运行时,定期显式完整运行时GC。在MARS中,空闲的运行时GC被冻结,直到应用程序返回到前台。因此,运行时GC永远不会混淆页面交换。

在Android运行时框架上,MARS过滤这些进程的内存页面,以将Linux页面交换与Android运行时GC隔离。Linux页面交换采用类似2Q[6]的页面替换算法,这是LRU(最近最少使用)近似的一种实现。该算法维护两个内存页队列—活动列表和非活动列表。对于每个页面,有两个标志位—“PG有效”和“PG引用”。当页面被访问时,设置其“PG引用”标志位。如果其“PG 引用”标志位已设置,则表示该页面被频繁引用。如果此页面位于非活动列表中,则应将其移动到活动列表中。如果页面在一段时间后未被访问,则“PG引用”标志位将被清除。如果活动列表上的页面的“PG引用”标志位已被长时间清除,则这些页面将被移出到非活动列表。只有非活动列表中的页面才是页面交换的候选对象。 MARS修改了“页面引用”功能,始终为前台应用程序和长期服务设置页面的“PG引用”标志位。对于不在Android运行时框架上运行的其他进程,它们不会与页面交换发生冲突。因此,MARS只是将这些流程与后台Android 应用程序的流程相同。

此外,后台应用程序可能会被Android上的低内存杀手杀死,以回收内存。我们禁用了低内存杀手,因为它在MARS中是不必要的和不兼容的。

3.3 页槽分配

eMMC在智能手机上的主要缺点是其分散I/O性能较差。先前的 研究人员[7]报告了智能手机上的另一种低端NAND闪存SD卡的 分散写入性能较差。由于MARS专注于加快换入速度,我们使 用IOzone测量了谷歌Nexus 4手机上eMMC的读取带宽,IOzone 是一款著名的I/O基准测试工具,用于测量存储设备或系统的 性能。表1中所示的结果表明,在谷歌Nexus 4手机的eMMC上, 分散读取操作比顺序读取操作慢十倍。

表1谷歌Nexus 4 eMMC的读取带宽


图5.页槽分配

应用程序扩展区的大小为1 MB,一个应用程序可以有多个应用程序范围。但是只有一个应用程序范围当前正在为哈希映射中的应用程序提供换出服务。当分配了所有页槽时,应从散列映射中删除应用程序范围,并且应在散列映射中添加新的空闲应用程序范围。

如表1所示,随着记录大小的增加,顺序读取和分散读取之间的差异变得可以忽略不计。这为加速交换提供了一种见解,该方法是将应用程序的页面组织在SWAP中的顺序LBA(逻辑块地址)序列并使它们交换在一起。

Linux页面交换已经尝试通过在交换分区中按顺序分配交换页面来对它们进行集群。但是,考虑到最初的Linux页面交换如何分配页槽,这并不能保证在执行换入时读取操作是连续的。下面列出了分配页槽的过程。

1) 如果存在来自连续空闲页槽的当前簇的任何空闲页槽,则将分配该页槽。

2) 如果当前集群没有空闲的页槽,则尝试寻找满足要求的新集群,然后从新集群中分配新的页槽。

3) 否则,只需分配一个空闲页槽。

4) 该方案实际上是一种基于引用局部性信息生成顺序换入读取的直接方法。但由于以下原因,它不适合MARS。

1) 当使用大量页槽时,分配方法不能分配连续页槽。对于传统服务器,情况并非如此,因为交换区域仅在工作集大于主内存时使用。考虑到性能,服务器应用程序很少使用交换区域。然而,在MARS的背景下,我们希望大部分的交换区域都在使用中,因为我们打算尽可能多地保留后台应用程序。

2) 我们已经表明,用户打算同时使用多个应用程序。这将减少内存引用的局部性。

MARS的页面时隙分配方案如图5和6,MARS将交换区域中的页槽重新组织为应用程序范围。应用程序范围是一组对齐的连续页槽。应用程序范围的默认大小为1 MB。为了换出一个页面,MARS会找到该页面所属的进程,并分配一个相应应用程序扩展区的页槽。如果应用程序扩展区中没有空 闲页槽,则MARS会为该进程添加一个新的应用程序扩展区。 通过为不同的应用程序使用不同的盘区,当应用程序被切换 到前台时,相应应用程序的盘区将被加载到存储器中。因此, MARS强制换入读取操作按顺序进行。

应用和应用范围的映射被记录在如图2所示的键值表中。5键是应用程序的散列进程ID,值是指向相应应用程序的当前范围的指针。页槽分配还负责回收没有有效页槽的应用程序范围。这些无效的应用程序扩展区将被修剪(在第3.4节中进一步说明),然后放置在空闲扩展区列表中,用于即将到来的应用程序扩展区分配。

图6.页槽分配算法

交换映射用于记录每个页槽的状态,例如使用、扫描或丢弃。如果该算法找到可用的页槽,则返回页槽的索引“offset”, 它是一个正整数。如果没有空闲页槽,则返回0。函数“获取 进程ID”返回页面所属进程的ID。函数“获取当前页”按顺序返 回第一个未分配的页槽,并维护应用程序范围的空闲页计数。在我们的实现中,哈希映射默认有1024个存储桶,并将哈希 到同一存储桶的所有条目存储在一个数组中。这里使用的算 法具有恒定的复杂度,并且带来了可以忽略的开销。因此, 性能接近于原始页槽分配。

图7.自适应自由记忆水印

保留的内存将补充换入的空闲内存页。当没有应用程序启动时,这部分内存永远不会被使用。保留内存大小由所有后台应用程序的工作集大小的最大值确定。

3.4 读/写控制

先前的研究人员[8],[9],[10]指出,在基于闪存的固态硬盘(SSD)中,并发读写会相互干扰,并导致性能严重下降。这个问题在EMMC中也很严重。主要原因是混合读取和写入将中断闪存存储器中闪存平面的内部流水线操作。

我们在谷歌Nexus 4的eMMC上测量了并发64KB读写的I/O性能,以验证闪存存储的现象。表2所示的结果表明,eMMC上的并发读取和写入的干扰会相互干扰,并大大降低I/O性能。但是,在Linux页面交换中,经常同时触发换入和换出。一种常见的情况是换出页面,以便为一些要换入的页面腾出空间。正如前面所讨论的,这将大大降低性能。

表2.谷歌Nexus 4 eMMC的并发读写带宽(KB/s)

注:“序号”是连续的和“SCAT”。是分散的。

*“+”左侧的数值表示读取带宽,“+”右侧的

数值表示写入带宽。


图8.应用程序重启时的I/O跟踪

对于MARS,当应用程序PVZ 2重启时,两个水印将减少。由于原始页面交换的两个水印是固定的,因此这个小变化会使页面交换的I/O模式产生很大的差异。在MARS中,应用程序重启会导致两个阶段的页面交换。一个是应用程序重启期间的换入阶段,另一个是应用程序重启之后的换出阶段。换入和换出在原始页面交换中同时执行。

MARS通过使用新颖的交换控制机制来解耦交换输出和交换输入。如图6.7所示,MARS控制kswapd,Linux中的内核交换守护进程,具有自适应的可用内存水印—低水印和高水印。在Linux内核中,水印由最小空闲千字节数M决定,它是内核中保留页帧的池大小。(默认情况下,低水位线为5/4 m,高水位线为3/2 m)。当空闲内存低于低水位线时,kswapd线程将被唤醒以回收内存。kswapd的职责是保持可用内存高于高水位线。kswapd还会定期尝试回收内存。在MARS中,当没有应用程序启动时,低水印和高水印会增加一个变量它是所有后台应用程序的总换入大小的最大值。通常小于100MB,对于具有2GB RAM的智能手机,这不会导致性能下降。后台应用程序的总换入大小实际上是其换出大小。通过这种方式,MARS为任何重启的后台应用程序保留了足够的可用内存。在应用程序重启期间,低水位线和高水位线将重置为原始值。因此,kswapd不应在换入时被触发换出。此外,我们还修改了内核中的页面缓存同步守护进程pdflush线程,以关闭应用程序启动时的写回。

以应用PVZ2重启为例,在MARS和传统的Linux页面交换下, 应用重启时换入和换出的交错是不同的。当应用程序PVZ 2重启时,我们使用Android Systrace工具3 来记录手机上eMMC的I/O活动。读和写的交错如图8所示,在应用程序重启期间,MARS将低/高水位线设置为原 始水位线。然后,为应用程序启动保留的内存页将用于换入。 MARS的重新发射时间约为1.6秒。MARS中时间线2到4秒内记录 的I/O活动是由应用程序生成的I/O操作。在传统的Linux页面 交换中,频繁的I/O交叉大大降低了交换的性能。

我们修改了Android应用程序框架,以便在应用程序启动的每个时间点通知Linux 内核。Android 运行时通过Linux proc文件系统指示应用程序的启动状态。除了软件级产生的读写干扰外,Flash GC还可能诱发内部读操作。

Systrace工具将来自Android内核的数据(如CPU调度程序、磁盘活动和应用程序线程)组合在一起,以生成HTML报告,该报告显示给定时间段内Android设备系统进程的整体情况。和将中断正常I/O操作的写入。闪存GC是由闪存存储的特性引起的。闪存存储无法就地更新数据。相反,它们必须首先擦除大的闪存块4,然后写入被擦除的块内的页。不再需要旧的Flash页面(也称为陈旧页面)。在擦除闪存块之前,应将有效的闪存页面(非陈旧)复制到另一个闪存块,并由闪存转换层(FTL)重新映射。这就是为什么Flash GC的过程涉及到在内部读取和重写数据。

在MARS中,我们使用discard5命令来通知FTL哪些Flash页面应该是无效的。由于丢弃命令本身会消耗eMMC的带宽,因此在任何时候都不应发出该命令。当前未执行页面交换时, MARS会在后台发出丢弃命令。合并相邻LBA的丢弃请求,进行批处理操作。

用于丢弃无效闪存页的简单且低开销的方案是丢弃无效应用范围,称为“修剪”。由于此任务应定期执行,因此我们将其分配给kswapd服务。当kswapd没有页面交换任务时,它将在进入睡眠之前执行丢弃无效应用程序范围的功能。

3.5 实现

我们使用ARMLinux3.4的内核版本在Android4.4上构建了我们的原型系统MARS。在Linux内核中有大约200个LOC(代码行) 编码工作,在Android运行时和应用程序框架上有大约40个LOC修改。MARS的实现需要三个主要部分:兼容性改造、页槽分配和读/写控制。它的可移植性和易维护性值得Android社区推荐。

禁用后台运行时GC和低内存Killer的实现位于Android应用程序框架模块和LowMemoryKiller内核模块中。在Android 应用程序框架中跟踪应用程序启动状态。并通过proc文件系统通知内核。除了换出的写入之外,在应用程序启动期间, 还应阻止PDFLUSH线程的页面缓存同步写入。考虑到查找效率和内存开销,我们选择的哈希表的默认大小为1024。

4.评价

我们评估了MARS相对于原始Linux页面交换和Android上的当前解决方案的性能。评估旨在回答以下三个关键问题:

• 与传统的Linux页面交换相比,MARS的每个组件在换入性能方面有什么改进?

• MARS架构设计是否提高了各种移动应用程序的重启性能?

• MARS是加快日常使用的移动应用程序重启的有效解决方案吗?

第4.1节描述了实验装置和方法。然后,我们提出我们的评估,以分别回答第4.2、4.3、4.4节中的三个问题。

4.1方法论

设备和系统设置

所有的评估都是在配备了高通Snapdragon商标S4 Pro CPU、2 GB RAM和16 GB eMMC内部存储的谷歌Nexus 4手机上进行的。Linux内核在编译时启用了“ config Blk dev io trace”选项来跟踪块级I/O。我们使用一个2 GB的交换文件作为交换区。默认情况下,swappiness值设置为60。交换性

[12]是一个参数,它控制为换出运行时内存而给出的相对权 重,而不是从系统页面缓存中删除页面。它可以设置为0到100之间的值(包括0和100)。较低的值会使内核避免交换, 较高的值会使内核使用交换空间。默认情况下,页簇设置为3, 即这8(23)页将被一起分页[12]。设置两个参数设置都会影响页面交换

行为。在我们所有的评估中,运行时在Android 4.4(Dalvik 虚拟机)上设置为默认。

基准

微基准测试测试页面交换中的I/O延迟和带宽,以评估每个MARS组件的有效性。这两个微基准由BLKTRACE[13] 工具测量。跟踪数据被收集在存储器中,以最小化由跟踪本身引起的干扰。然后,使用blkparse[13]和BTT[13]处理收集的轨迹。应用程序基准是用于评估MARS性能的应用程序的重启时间。重启时间是通过检测Android运行时框架来测量的。应用程序重启的时间跨度是从点击应用程序图标的时间点到用户能够与应用程序交互的时间点。为了评估MARS在日常使用中的有效性,我们在基线、传统Linux页面交换和MARS下,在测试智能手机上重放收集的应用程序使用跟踪。然后,我们收集所有应用程序重启时间。 所有评估中涉及的应用程序都是从Android Market上各个类别中最受欢迎的应用程序中挑选的。挑选的应用程序如下所示。

•社交:Facebook、LinkedIn、谷歌+、Twitter、Insta-gram、Pinterest、Fancy、Banjo和Beautylish。

•游戏:水果忍者,PVZ 2,神庙逃亡2,愤怒的小鸟,闪电战和王牌。

•实用工具:今晚酒店,Expedia,天气频道,ES文件资源管理器和谷歌地图。

•工作效率:Evernote、Gmail、Quickoffice和谷歌硬盘。

•通信:Skype、Hangouts、Facebook Messenger和Snapchat。

对于我们所有的实验,我们报告了五次不同运行的平均结果。所有的评估都是在手机上进行的,Wi-Fi连接良好。

4.2 微基准测试

微基准测试用于测试MARS中两个组件的有效性。一个是页槽分配,另一个是读/写控制。前者设计用于在页面交换期间产生更多的顺序读取以增加eMMC的读取带宽。我们可以通过测量SwapIn的占用带宽(吞吐量)来观察页面时隙分配带来的有效性。MARS的读/写控制旨在减少并发读写的干扰,以获得良好的交换性能。读或写操作的延迟可以反映并行I/O序列的干扰。在没有并发写入中断的情况下,读取操作的延迟应保持较低。

我们对Linux内核进行了检测,以跟踪交换输入/交换输出记录。每个记录条目包含:时间戳、操作(换入或换出)、页槽号和相应的进程名称。我们实现了一个SwapIn/Swap-Out 跟踪播放器,它可以在测试智能手机上模拟原始的Linux页面交换和MARS。我们首先在正常使用情况下跟踪智能手机上的换入/换出。然后,我们使用原始的Linux页面交换、没有读/ 写控制的MARS和具有读/写控制的MARS重放相同的跟踪。使用BLKTRACE工具测量了不同页槽分配方案和读写控制策略下的延迟和占用带宽。

Swap-In的占用带宽结果如图9所示。对于Linux页面交换, Swap-In的读取带宽约为6.94MB/s。这是由于缓慢的小分散读 操作和并发写操作的干扰。通过添加页槽分配组件(没有读/ 写控制的MARS),MARS的换入吞吐量为18.76MB/s。这表明MARS的页槽分配方案在提高换入性能方面比Linux页面交换要好得多。通过增强读/ 写控制, MARS 的交换吞吐量增加到

26.48 MB/s。这表明读/写控制可以减少读操作的平均延迟。图10显示了块I/O跟踪的结果。EMMC的读取延迟从不到1毫秒到超过100毫秒不等。对于Linux页面交换,平均读取延迟约为3.1毫秒,范围从0.3毫秒到131毫秒,这是由于我们在第节中说明的读/写干扰。对于没有读/写控制的MARS,干扰的情况类似于Linux页面交换。读取延迟从0.3毫秒到125毫秒不等,平均为2.9毫秒。具有读/写控制的MARS通过减少1毫秒的读取延迟显示了其有效性。平均值约为1.9毫秒。更重要的是,它减少了读取延迟的变化。最大读取延迟降至10.6毫秒。

总之,MARS架构的设计实现了我们最初的目标。MARS的两个组件,页槽分配和读/写控制,已经解决了第2节中演示的技术挑战。它们是专门为应用程序重启而设计的,与传统的Linux页面交换有很大的不同。MARS的页槽分配提高了eMMC上的读取性能。读/ 写控制减少了换入过程中涉及的写操作的干扰。它们都可以大大加快换入速度。

图9.页面交换时的读取带宽

读取占用带宽由“blktrace”收集的I/O操作通过“blkparse”和“BTT”统计处理得到。它反映了换入的吞吐量。为了消除“blktrace”本身的噪声,将跟踪数据保存在内存中,而不写入持久存储。

图10.页面交换时的读取延迟

读取延迟由解析块I/O跟踪的“blkparse”给出

4.3 应用程序基准

在本小节中,我们将评估MARS在Android上的各种应用程序中的性能。这些应用程序列出的最受欢迎的应用程序4.1.我们测量了这些应用程序在MARS和Linux页面交换下的重启时间。从零开始的应用程序的启动时间被测量为基线。对于MARS和Linux页面交换,重启时系统状态几乎保持不变。大约有75%的页槽在使用中。已调出的应用程序的内存页数从20MB到60MB以上不等。图11显示了应用程序WE的重启时间聚类直方图测量的。图12显示最受欢迎应用程序列表上所有应用程序的重启时间CDF。

如图6,11和12,MARS将应用程序重启时间加快了2到4倍。在MARS下重启的时间不到2秒,超过列表中80% 的应用程序。Linux页面交换下的应用程序重启无一例外地比MARS下慢。有些结果甚至比基线还差。对于那些发射时间大于10秒的应用,MARS的优势是显而易见的。总体而言, MARS的性能优于Linux页面交换,并改进了在智能手机上重启的应用程序。

图12.应用程序重启时间的CDF

4.4 MARS的日常使用效果

在本小节中, 我们将评估MARS 在日常使用中的有效性。Yahoo[14]收集的大规模Android应用程序使用数据显示,一个典型的Android设备平均安装了95个应用程序,每天实际使用其中的35个。数据显示,Android用户平均每天与应用程序交互100次,高峰时段(通常在下午晚些时候)每小时最多访问6个应用程序。我们想知道在这种情况下,MARS是否总是能够有效地减少应用程序的启动时间。我们还在12名志愿者的Android手机上部署了为期两个月的应用程序使用跟踪(在第2节中提到)。我们从收集的轨迹中选择一个代表性个体的一天轨迹,并在测试智能手机上手动重放交互,而不进行页面交换、传统的Linux页面交换和MARS。互动发生在两个时间段, 应用程序交互的人来说,MARS的有效性在很长一段时间后才会显现出来。

上午8:00到10:00和晚上8:00到10:00。 其他交互用于将测试智能手机预热到用于测试。启动时间的收集方式与应用程序基准相同。图13显示了每个测试用例的堆积直方图。


图13.日常使用的有效性

在这个堆叠的柱状图中,每一列中的每个块都表示应用程序交互的启动时间。对于我们选择的这个人来说,智能手机在晚上比早上使用得更频繁。在上午8:00至10:00,只有一个应用程序重启,由MARS加速的效率显然是在晚上8:00~10:00。

4.5 开销

MARS的能耗主要包括使用的额外存储容量、闪存损耗和功耗。 随着智能手机上的闪存存储容量变得越来越充足,例如谷歌Nexus 4上的8或16 GB eMMC,MARS的额外存储容量成本以及1或2GB的交换分区是可以接受的。在本小节中,我们将重点介绍MARS的额外闪存存储损耗率和功耗。

显然,额外的闪存写入是由MARS中的页面交换产生的。交换页面的数量由应用程序的交错和工作集确定,即从后台重启应用程序当它的部分内存页面被换出,并且当没有足够的空闲页面时为正在运行的进程分配内存。但是,并非每个应用程序交错都会导致额外的闪存写入。对于第4.4小节中的日常使用评估,21次应用程序重启中有1次(7次)和7次(7次)会分别导致一天中上午8:00至10:00和晚上8:00至10:00的额外闪存写入。智能手机上的应用工作集从大约10 MB(例如,消息传递应用)到超过100 MB(例如,游戏应用)不等。图14显示了我们评估中在测试手机上测量的一些安卓应用的工作集。

多级单元与非门闪存的写入耐久性通常为3000至10000个写入/擦除周期[15]。对于谷歌Nexus 4 [16],[17]上的eMMC,其MLC NAND闪存的写入/擦除周期约为10,000个。根据日常使用的安卓设备的块输入/输出跟踪[18],大约有1837兆字节的数据被写入了24小时。关于MARS的磨损开销,考虑到我们日常使用评估中的最坏情况,大约有10,000 MB(每天100次应用程序交错[14]并为每个应用程序交换100 MB数据)的数据写入页面一天之内交换。即使在这种情况下,配备磨损均衡技术,MLC与非门闪存的写入耐久性将使应用程序能够在智能手机上读写数据超过几十年,如我们的测试手机谷歌Nexus 4。因此,MARS的写入耐久性开销是可以接受的。

图11.Linux页面交换和MARS下的重启时间

重启时间可以用与启动时间相同的方式来测量。基线是没有MARS的安卓上应用的启动时间。

图14. 一些安卓应用的内存使用情况

应用程序使用的内存是安卓“procrank”工具计算的PSS(比例集大小),可以看作是应用程序的工作集大小。

由MARS引起的额外闪存写入同时消耗额外的功率。根据智能手机中读/写操作的功耗测量[19]和我们用PowerTutor进行的验证[20],Android需要70到3300J/KB才能完成I/O操作,包括顺序/分散的读或写。功耗的主要部分是中央处理器和动态随机存取存储器的能量成本,而不是整个输入/输出堆栈中的eMMC设备。顺序操作比分散操作更节能。对于我们日常使用评估中的案例(约20%的应用交错导致了页面交换,即一天为页面交换读写2,000 MB数据),MARS的日常能量开销主要包含两部分:换入的读取能量成本,换出的写入能量成本。

取70 J/KB为读取能量成本,360 J/KB为写入能量成本,MARS的日能量开销为880.64 J,约为我们测试手机电池电量的3.07 %。我们的测试手机嵌入了3.8 V、2100毫安时的电池[21]。这意味着,在谷歌Nexus等智能手机的日常使用中,MARS会导致约3%的能源开销,这对于日常使用的整个能源成本来说并不是一个很大的数字。

如上所述,MARS确实会给智能手机带来潜在的额外成本,包括更大的存储容量、闪存损耗和功耗。我们认为,由于当前的闪存存储空间相对较大,并且变得更大。页面交换所需的额外存储空间很小,应该不成问题。页面交换期间的读写会降低闪存的寿命。然而,随着磨损均衡和NAND闪存升级等闪存控制器技术的提高,闪存的寿命远远超过了智能手机的使用寿命。MARS引入这些额外的写操作是可以容忍的。根据对智能手机功耗的分析[22],能耗是能源成本的主要部分

智能手机上是液晶显示屏。闪存读/写操作仅消耗一小部分电池电量。此外,MARS可以加速应用程序的重启,从而在降低液晶屏显示消耗的同时节省能源。因此,我们认为MARS的能源成本可以忽略不计。

5 相关工作

有各种与MARS设计和实施相关的工作。它们可以分为桌面电脑上的类似工作、移动应用程序启动预测、虚拟内存气相色谱改进以及基于NAND闪存的存储优化性能。

桌面计算机上系统优化的快速应用程序启动的研究区分于不同的环境和要求[5],[23],[24]。一个典型的例子[24],它是Windows Vista的扩展。它不断分析应用程序行为和用户年龄模式,并试图在需要之前将常用的库和应用程序组件加载到内存中。由于智能手机的内存大小通常有限,SuperFetch不适合智能手机。针对固态硬盘上硬盘感知应用启动程序效率低的问题,Joo等人[5]提出了一种固态硬盘感知应用预取方案,该方案试图在应用启动期间将计算时间与固态硬盘访问时间重叠。相比之下,MARS缓存应用程序以跳过初始进程的计算,并专注于加快低端NAND闪存的页面交换。

随着可用移动应用数量的增加,移动用户打算在他们的智能手机上安装越来越多的应用。已经提出了一系列应用程序启动预测方法[1],[25],[26],[27]。预测结果可用于预启动应用程序,以减少感知的启动时间。FAL- CON [1]使用位置和时间访问模式等用户上下文来预测应用程序启动的时间。FALCON还会同时考虑成本和收益来选择最合适的预测。相反,APPM [27]仅在预测中使用历史应用程序用法,没有任何耗电或隐私敏感的上下文。我们认为预测精度和/或长期训练要求限制了这种基于预测的方法的有效性。因此,MARS不依赖任何不精确的信息。

在[28]和[29]中已经研究了垃圾回收应用程序与虚拟内存系统的不良交互。BC [28]与虚拟内存管理器协作,使用从被逐出的页面记录的摘要信息(“书签”)来执行内存中的全堆收集。为了解决当Java虚拟机(JVM)无法调整其应用程序堆大小以适应内存时的交换抖动问题,CRAMM [29]动态调整堆大小以最大化吞吐量,同时最小化页面交换。这种方法不适合智能手机,并且会严重降低应用程序的响应能力。Android运行时的堆大小只有几十MBs。无需为前台运行的应用程序交换页面。在MARS中,我们隔离了运行时GC和页面交换,即没有页面交换

6 结论

本文介绍了MARS的设计、实现和评估,MARS是一种改进的Linux页面交换,用于在智能手机上快速重启应用程序。MARS解决了Linux页面交换和安卓机器运行时垃圾回收之间的冲突。为了加快应用程序重启时的换入速度,MARS针对智能手机上低端闪存存储的性能特点,对Linux页面交换进行了调整。为了解决读取速度慢的问题,MARS重新组织了交换区,并采用了一种新的页槽分配方案来生成顺序读取。为了解决读/写干扰问题,我们开发了读/写控制组件,用于减少交换时的并发写入。与传统的Linux页面交换相比,页面分配组件可以将读取带宽扩展到大约2.7倍。此外,读/写控制可以带来另一项改进,将读取带宽提升至3.8倍。我们已经证明,使用页面交换来扩展用于快速应用重启的传统缓存方案在智能手机中是可行的。微基准已经验证了MARS的两个组件都达到了最初的设计目标。评估结果显示,MARS将安卓应用的启动时间缩短了50%到80%。


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

完整附件下载:MARS- Mobile Application Relaunching Speed-up through Flash-Aware Page Swapping.pdf

你可能也喜欢这些文章