摘 要

软件在长期连续运行过程后，当安卓手机内存不足时，内存回收机制运作，造成软件性能下降等现象，即软件老化。由于安卓内存管理机制的复杂性，很难通过分析相应的内存管理机制来判断是否存在老化，所以可以通过一些性能指标，如本文采用的可用内存，间接地关注一些与老化相关的现象。为了减少软件老化带来的影响，需要进行软件恢复。由于进行软件恢复有一定的成本，需要寻找最佳恢复策略。本文主要研究内容就是对比分析不同型号的安卓手机的老化现象并建立马尔科夫老化预测模型，有助于今后更好地开展老化恢复研究、制定老化恢复策略。

本文中介绍了安卓内存回收机制，主要是内核层的LMK（低内存管理）、运行库层的GC（垃圾收集）内存回收机制的相关理论知识及其与软件老化的关系。选择两款不同手机进行为期三天的相同的压力测试实验，使用应用程序模拟用户对软件进行的点击、划动操作，以可用内存为指标监测老化现象，每隔一段时间收集一次数据。之后对数据集进行简化、归一化和分割处理，使用黄金分割原理将实验过程中的数据分割成四种状态。根据四种状态计算概率转移矩阵，构建马尔科夫链，预测两款手机各自进入老化状态的时间。实验结果表明，不同型号的手机进入老化状态的时间有明显差异，且与实际观察结果相近。最后针对可能影响老化现象的因素进行了分析，指出实验中可以改进的地方。

关键词：软件老化；内存回收；压力测试；马尔科夫链

Abstract

After long and continuous running, software performance degradation and other phenomena, that is, software aging will occur because of operating of memory recycling mechanism when Android has insufficient memory. It is difficult to judge whether there is software aging by analyzing the memory management mechanism because of its complexity. So we can monitor aging-related phenomena indirectly to some performance indexes, such as available memory used in this paper. In order to reduce the impact of software aging, software rejuvenation is needed. There is a certain cost in software rejuvenation, so it is important to make an optimal rejuvenation strategy to minimize the cost. The main purpose of this paper is to analyze and compare aging phenomena of Android mobile phones of different models by establishing a Markov Model. This will help us to carry out research on software rejuvenation and make more optimal rejuvenation strategies in the future.

In this paper, I introduce Android memory collection mechanism, mainly the related theories of the LMK(Low Memory Killer) mechanism of Kernel Level and the GC(Garbage Collection) mechanism of Runtime Level and the relationship between the mechanisms and software aging. Then, mobile phones of two different models were selected for the stress testing for three days. An application is used to simulate the tapping and swiping operations of users, and available memory data is used as an indicator to monitor aging phenomena and is collected every three minutes. Then the data set is simplified, normalized and segmented, and I use the golden section principle to divide the experimental data into four different states. With these four states, we can get the state transition probability matrix, establish Markov Chain, and calculate the expected time to go to aging state of the two mobile phones. The experimental result shows that the expected time for software aging of different models is obviously different, and it is similar to the actual observations. Finally, factors that may affect the aging phenomena are analyzed, and some improvements can be made in the future are pointed out.

Key Words：software aging；memory collection；stress test；Markov Chain

目 录

第1章 绪论 1

1.1 研究背景 1

1.1.1 软件老化及恢复 1

1.1.2 安卓系统中的软件老化 1

1.2 国内外研究现状 2

1.2.1 软件老化 2

1.2.2 安卓系统中的软件老化 3

1.3 研究目的及意义 3

1.4 研究内容 4

1.5 论文组织结构 4

第2章 安卓内存回收机制 5

2.1 LMK机制^[21] 5

2.2 GC机制 5

2.3 安卓内存回收机制与软件老化 5

第3章 实验测试 7

3.1 实验工具及环境 7

3.2 实验方案 7

3.2.1 压力测试 7

3.2.2 监控策略 8

3.3 实验结果 8

3.4 实验总结 10

第4章 马尔科夫模型分析 11

4.1 模型介绍 11

4.1.1 马尔科夫过程 11

4.1.2 马尔科夫链 11

4.1.3 吸收马尔科夫链 12

4.2 数据处理 12

4.2.1 归一化数据集 12

4.2.2 分割数据集 13

4.3 实验1建模分析 14

4.4 实验2建模分析 15

4.5 结果分析 16

第5章 总结 17

参考文献 19

致谢 21

绪论

研究背景

软件老化及恢复

在长期运行的复杂软件系统中，人们往往能观察到性能下降或故障率增加的现象^[1]，这就是软件老化。它是指软件在长期连续运行过程中，由于不可预知的（通常指与老化相关的）错误，如系统内存泄漏、未释放的文件描述符、存储空间碎片以及舍入误差的积累，导致软件性能逐渐下降甚至崩溃的现象^[2][3]，是计算机系统中的一种常见现象。软件老化是随机的，且频率和导致故障的概率比传统硬件老化高。软件老化可以在各种软件中发现，不仅局限于一般商业或民用系统，也会发生在军事、航空航天和其他安全关键系统中，例如Linux操作系统^[4]、eucalyptus 云计算基础设施^[5]、Cisco Catalyst交换机、Apache网络服务器、爱国者导弹防御系统^[6]。软件老化具有以下特征^[6]：

1.在没有外部干预的情况下，老化的影响是不可逆的；

2.只有当时钟时间（系统启动或进程创建的时间）是影响误差积累和传播的系统内部环境的一部分时，老化效应取决于时钟时间；

3.只有当进程在运行时触发与老化相关的故障或引起自然老化效应，或者CPU时间是影响误差累积和/或传播的系统内部环境一部分时，CPU时间影响老化效应。

当软件发生意外错误时，会影响设备的使用效率，对用户体验产生很大负面影响，甚至造成事故。例如在爱国者导弹系统^[6]中，它的24位寄存器可以用于整数计数约19.4天而不产生溢出，而每当将整数值转换成实际值时会导致误差，其大小与系统连续运行的时间成正比，在系统运行时间约八小时后误差会变得很大。1991年，位于沙特阿拉伯的爱国者系统在自上次重启后运行超过20小时后拦截飞毛腿导弹失败。

软件恢复是一种用于抵消老化影响并避免与老化相关的故障的被动（手动）或主动（自动）的方法，例如重新启动系统或重新启动出现老化的应用程序^[2]，许多基于主动恢复的策略被用来对抗老化。

安卓系统中的软件老化

安卓是一种基于Linux平台的开放源代码的操作系统。它主要用于移动设备，如平板电脑和智能手机。安卓系统的开放性和开发的方便性使其拥有众多的开发者，越来越多功能各异且相互兼容的产品不断被推出，吸引着厂商和消费者。随着互联网的发展，移动设备成为现在人们生活中不可或缺的一部分，尤其是出门在外时，便携且功能强大的智能手机、平板电脑被越来越多的人选择用来代替台式电脑工作或娱乐。安卓手机拥有庞大的用户群，据网站通讯流量监测机构StatCounter公布的数据，2018年8月跨平台操作系统市场中，安卓以41.66%的比例位列第一。

随着硬件系统及软件功能的不断发展，人们对移动应用带来的用户体验的要求越来越高，即安卓系统中的软件老化受到越来越多的关注。在安卓操作系统的错误报告中已经观察到了各种老化现象，其中典型的例子有应用程序的不平滑、意外阻塞以及突然崩溃。

虽然安卓是基于Linux操作系统开发的，但它们之间有许多不同之处。DVM（Dalvik虚拟机）和JNI（Java本机接口）的使用使得安卓中存在Dalvik堆和本地堆两个堆区域，Dalvik堆受到自身最大容量的限制，它的内存泄漏频繁触发GC，导致其他线程挂起；而本地堆的大小受到整个系统内存的限制，GC不负责它。这将导致不同的堆内存泄漏有不同表现。此外，基于安卓的LMK机制，不同优先级的进程在用户和系统角度引起的内存耗竭的老化现象都不同。这都是软件老化的新表现^[20]。因此，安卓系统中的特定软件老化现象需要被研究。

国内外研究现状

软件老化

目前，国内外已经有了很多关于软件老化及恢复的研究，主要集中在老化现象建模与分析、老化恢复策略制定上。常用的分析方法有基于模型（如马尔科夫模型、Petri网和随机回归网络）、基于测量（如局部线性回归、局部加权回归、决策树、神经网络、支持向量机等）和混合（两种方法的结合）方法^[1]。

在软件老化检测及预测方面，Sachin Garg等人设计和实现了基于简单网络管理协议的分布式监控和数据采集工具，以系统资源估计耗竭时间为指标检测评估Unix系统中的老化^[7]。Rivalino Matias Jr.等人提出一种基于差异分析、评估使用多个统计技术和应用程序级内存相关度量（RSS和堆使用）计算出的散度图的方法，在内存泄漏检测方面较为突出^[8]。Karen J. Cassidy等人针对大型联机事务处理服务器中的共享内存池闩锁争用提出经验建模方法，将预警故障检测系统应用于这种软件老化中特别复杂的类型^[9]。Antonio Bovenzi等人在Apache 网络服务器、James邮件服务器和空中交通管制系统开发的中间件上进行老化实验，以内存消耗和吞吐量损失作为老化指标，采用Mann-Kendall方法进行趋势检测，提出工作负载（单位时间的请求数）极大地影响软件老化^[11]。杜小智等人针对视频点播系统，采用Mann-Kendall方法来检测老化趋势，采用Sen的斜率估计方法来估计老化衰退速率，提出了基于径向基网络的软件老化预测模型^[12]。范新媛等人以Apache网络服务器为研究目标，通过实验证明ARIMA模型可以有效地拟合剩余内存的损耗情况，较好地描述和预测内存的使用情况^[13]。

在恢复策略方面，Andrea Bobbio等人通过监测退化指数识别系统的当前退化水平并调整恢复策略^[15]。Javier Alonso等人分析六种机器学习算法来预测资源枯竭引起的系统崩溃，其中随机森林是最佳选择，并进行基于Lasso正则化的特征选择，以减少建立随机森林模型所需的参数的数量^[16]。Hiroyuki Eto等人用连续时间马尔科夫链描述了多级退化软件系统，以强化学习算法中的Q-学习算法为例，提出了一种基于仿真的算法，即使在系统失效时间分布未知的情况下，也能自适应触发恢复^[19]。