英语原文共 7 页

新型安卓软件恢复模型

摘要：安卓用户有时会遇到用户界面响应缓慢甚至应用程序、操作系统崩溃的问题。这些问题通常是由软件老化，一种以长期运行的软件系统中观察到的性能和功能逐渐衰退为特征的现象引起的。对抗软件老化的一种实用且广泛使用的方法是软件恢复，即被动或主动地重新启动应用程序或设备。要减少服务中断，力求平衡应用程序宕机时间和性能水平的主动恢复是首选。然而，传统的恢复模式不能直接应用于安卓应用程序或系统，因为它们不能解决用户体验问题，例如避免在活跃阶段恢复。手机的使用时间在日常生活中通常是零碎的、在活跃模式和睡眠模式之间周期性切换，在这项工作中，由这样一个事实，我们提出了考虑使用行为和时长因素的主动恢复策略。特别地，我们将使用行为和老化过程分别建模为独立的随机Petri网，然后将它们组合成连续时间马尔可夫链。我们通过数值实验评估该模式，并证明了所提出的恢复方法的有效性和优越性。

关键词：软件老化；软件恢复；用户体验；安卓

Ⅰ.引言

软件老化是指在系统持续运行的过程中，由于不可预知的错误（通常指与老化有关的错误），导致应用程序或系统的崩溃累积而导致性能下降的现象[1]。它在Linux、Apache服务器和中间件[2-4]等各种系统和应用中被广泛研究，安卓作为手机最流行的操作系统之一，截至2017年已占据89.5%的市场份额[5]。在安卓系统中，软件老化也会发生，在较长时间的运行（通常是几天）后，用户界面响应慢似乎是许多安卓用户的常见体验。因此，最近的一些研究工作都集中在这个问题上[6-8]。

软件恢复是一种用于抵消老化影响并避免与老化相关的故障的被动或主动的方法，例如在特定时间手动重启（被动）或自动重启（主动）。软件恢复的研究一般可分为基于模型的方法[10-12]和机器学习方法[13-17]。最近，有人提出了一些针对安卓的恢复策略。例如，Weng等人利用机器学习算法预测最佳恢复时间[18]，Guo等人提出了两级恢复策略[19]。为了确定最佳的恢复策略，现有的研究大多集中在老化过程的建模上。研究人员们没有考虑到使用行为对恢复策略的潜在影响。

与其他操作系统和应用程序（如Linux或Apache服务器）相比，手机的使用时间通常是零碎的。用户在日常生活中经常和手机进行间断的交互[20]，这意味着用户的使用行为在活跃模式和睡眠模式之间频繁切换。如果不考虑使用行为，那么可以在系统处于活跃模式时实施恢复。不幸的是，这将导致极差的用户体验，并可能损害设备和应用程序厂商。为了避免这个问题，在安卓恢复中需要对使用行为和老化过程进行建模。

在本文所描述的工作中，我们首先将手机使用行为建模为一个双态马尔可夫链，这样就可以预测一天中所有时段的用户行为。我们将实施恢复的老化过程与不实施恢复的老化过程分别建模为单独的马尔可夫链[22]。利用随机Petri网（SPN）和ORIS工具[23][24]，我们可以在独立的使用行为模型和老化过程模型的基础上生成集成的连续时间马尔可夫链（CTMC）。有了集成CTMC模型，我们就可以同时考虑安卓手机的使用模式和年龄（即老化状态），实施谨慎的主动恢复策略。最佳的恢复间隔可以通过最大化收益和最小化成本来确定。数值实验验证了该模型的有效性和优越性。请注意本文中使用马尔可夫模型主要是为了简化分析，但这一思想也可以推广到其他具有一般分布的非马尔可夫模型，这些模型可以更恰当地捕捉用户行为和老化过程。

本文的其余部分组织如下：第二节介绍相关工作，第三节介绍安卓手机的恢复模型，第四节用数值实例说明了所提出的恢复模型的有效性，第五节总结。

Ⅱ.背景及相关工作

传统上认为软件错误是确定性的，软件容错通常由设计多样性实现（例如，N版本编程[9]）。随着软件规模和复杂性的增加，软件错误的随机性和不可重复性逐渐受到关注。软件老化的概念最早提出于1995年[22]，此后在软件可靠性工程领域得到了专家学者的广泛研究。

研究发现，软件老化比硬件老化更普遍。软件老化是长时间运行的计算机系统中经常发生的一种现象，它是由于内存泄漏和数据损坏等错误积累造成的，并会导致系统性能和可靠性逐步下降。

在Linux[2]、Apache服务器[3]、中间件和云计算软件[26][27]等各种系统中都观察到了软件老化。有关软件老化的全面调查，请参阅[9]。至于安卓系统中的软件老化，这一现象既存在于操作系统层面，也存在于应用层面。Araujo等人研究了安卓应用中内存泄漏与软件老化的关系[8]。Qiao等人根据内存泄漏位置（Dalvik堆或本机堆）和进程属性（非常驻或常驻）分析老化表现模式，对安卓操作系统中与老化相关的故障的表现进行了实证研究[28]。Cotroneo等人系统地研究了安卓系统变量与软件老化的关系[7]。

软件恢复作为软件老化的对策，可以在不同的层次上实施，如应用程序（组件/线程/任务）重启、虚拟机（VM）重启、操作系统重启和集群故障转移。其他特定于应用程序的恢复技术包括垃圾收集和内核页表的刷新。Alonso等人对六种粒度不同的恢复技术进行了实验研究，证明了恢复的性能成本比与其粒度有关[29]。与传统的基于重启的恢复技术相比，Machida等人提出了一种通过向关键应用程序分配额外可用资源来延迟老化过程的新方法，称为软件寿命延长[10]。另一个工作线程使用虚拟化来掩盖由应用程序或操作系统重启引起的宕机时间[33][34]。

在[22]中，Huang等人提出了一个经典的使用齐次CTMC预测软件恢复时间的四态软件恢复模型。Dohi等人进一步扩展出了基于非齐次CTMC的四态恢复模型，以预测高保证系统的软件恢复时间表[30]。Trivedi等人同样使用非齐次马尔可夫模型，评价操作软件系统中软件恢复的有效性，并确定实施软件恢复的最佳时间[11]。Xie等人利用半马尔可夫过程模型，通过最大化稳态可用性，确定软件系统两级恢复策略的有效性[12]。Meng等人研究了一种基于几何序列的定期检测软件恢复策略，以确定最佳的定期检测时间[31]。然而，这些基于模型的方法主要聚焦于老化过程本身的建模。他们都没有直接考虑到整个恢复模型中使用行为的建模。

除了上述基于模型的方法外，还可以根据机器学习（ML）计划恢复[13][16][17]。Alonso等人提出了一系列用于预测软件老化和实施软件恢复的著名机器学习分类器的详细评估方法[29]。

近年来，已有多篇文献对手机恢复进行了研究。例如，Guo等人提出了一种两级恢复策略（应用程序重启和系统重启）以抵消软件老化[19]。本文分别研究了基于离散时间马尔可夫链（DTMC）的预期老化时间、基于结合了我们以往的文献[6]和[18]中研究的四态马尔可夫链与随机森林ML算法的混合方法的安卓手机最佳恢复时间。这些方法在其模型中同样不考虑用户行为和用户体验因素。

Ⅲ. 分析模型和指标

A. 随机Petri网

随机Petri网（SPN）通过五元组（P，T，A，M₀，Lambda;）表示，每个组件定义如下：

P={p₁，p₂，hellip;，p_m}：库所的有限集（用圆圈表示）。

T={t₁，t₂，hellip;，t_n}：变迁的有限集。

Asube;（Ptimes;T）cap;（Ttimes;P）库所和变迁之间的偏序关系的集合，称为弧集。

M₀：初始标志。

Lambda;：与变迁相关的实施速率lambda;数组。

本文用SPN来表示内部子系统或进程的状态变化，并用由单个SPN集成的CTMC来描述整个系统的状态变化。我们可以使用SPN更清楚地表示正在运行的系统的各种进程。有一些工具可以将SPN自动转换为CTMC。本文利用ORIS工具[23]构建并分析所提出的恢复模型。

B.模型描述

在本节中将介绍已建立的恢复模型。根据安卓手机的使用行为[20]，我们构建了一个双态马尔可夫模型来描述它，如图1所示。这两种状态分别是“睡眠”和“活跃”，然后我们可以预测一天中各时段的手机使用行为。这两种状态的定义是：

睡眠：用户不在使用手机，因此手机处于休眠状态。

活跃：用户正在使用手机。

两种状态间的变迁实施速率是lambda;_as和lambda;_sa，如图1所示，表示手机从“睡眠”状态到“活跃”状态的变迁实施速率是lambda;_sa，从“活跃”状态到“睡眠”状态的变迁实施速率是lambda;_as。我们假设每个状态的保持时间在一定时间内呈指数型分布。

图1. 用户使用行为的双态CTMC

图2. 没有实施主动恢复的老化过程CTMC

图3. 实施主动恢复的老化过程CTMC

假设没有主动恢复的老化过程被建模为如图2所示的CTMC。根据安卓手机的软件老化过程，首先，系统处于“年轻”状态，即手机操作流畅，没有明显延迟，用户拥有高质量的体验。然后，手机以变迁实施速率lambda;_yo进入“衰老”状态。“衰老”状态意味着手机操作不流畅，用户界面响应有延迟。Kang等人[21]发现，当用户界面响应延迟超过500ms时，用户体验会恶化。在我们的模型中，当用户界面平均响应时间超过500ms时，手机进入“衰老”状态。

我们假设系统在“衰老”状态逗留1/lambda;_ore时间之后，手机的用户界面响应时间达到无法忍受的阶段并立即实施一些恢复操作（例如手动重启）。我们将恢复操作中系统不可用的这段时间定义为“恢复”状态。实施恢复操作后，手机将以lambda;_rey速率从“恢复”状态转变为“年轻”状态。这意味着系统平均需要1/lambda;_rey时间从“恢复”状态回到“年轻”状态。

为了提升用户体验，最好在用户界面响应变慢、用户注意到性能下降之前主动实施恢复。这样，用户就可以尽可能长地操作处于“年轻”状态的手机。主动恢复（[11]中称为预防性维护）的过程由“重生”状态表示，如图3所示。只有“年轻”状态才允许主动恢复。一旦恢复完成，系统被重置为“年轻”状态，并且和新的一样好。

在图3中，如果给出了变迁实施速率lambda;_yo、lambda;_ore、lambda;_rey、lambda;_ry（或从实践中观察到），则可以仅根据老化状态确定实施恢复平均时间，即1/lambda;_yr。然而，这种策略是主动的，可能会极大降低用户体验。因此，要设计用户体验最好、对用户干扰最小的最佳恢复策略，我们必须将使用行为模型和老化过程模型结合起来。

图4. 没有实施恢复的用户行为和老化过程SPN

图5. 实施恢复的用户行为和老化过程SPN

将图1、图2的状态替换为库所后，我们可以通过如图4所示的SPN对没有实施恢复的用户行为和老化过程模型编码，其中：

P={睡眠，活跃，年轻，衰老，恢复}，

M₀=（1，0，1，0，0），

Lambda;={lambda;_sa，lambda;_as，lambda;_yo，lambda;_ore，lambda;_rey}。

相似的，实施恢复的SPN如图5所示，其中：

P={睡眠，活跃，年轻，衰老，恢复，重生}，

M₀=（1，0，1，0，0，0），

Lambda;={lambda;_sa，lambda;_as，lambda;_yo，lambda;_ore，lambda;_rey，lambda;_yr，lambda;_ry}。

请注意，在图5中，实施恢复有一个限制，即手机不能处于“活跃”库所，由“活跃”库所和与lambda;_yr相关的变迁间的抑止弧表示，这意味着只有使用行为处于“睡眠”库所、老化过程处于“年轻”库所时才能实施恢复。

图6. 没有实施恢复的集成CTMC

图7. 实施恢复的集成CTMC

我们使用Oris工具来分析上述的SPN，并将SPN分别转换为CMTC，如图6、图7所示。

CTMC中的各状态定义如下：

活跃年轻（AY）：用户正在操作手机，设备运行流畅。

睡眠年轻（SY）：用户不在操作手机，设备运行流畅。

活跃衰老（AM）：用户正在操作手机，用户界面响应慢。

睡眠衰老（SM）：用户不在操作手机，用户界面响应慢。

活跃恢复（ARe）：用户操作手机时手动重启。

睡眠恢复（SRe）：用户不操作手机时重启。

重生睡眠（RS）：用户不操作手机时，系统主动恢复。

重生活跃（RA）：用户操作手机时，系统主动恢复。

请注意，在图7中比图6多出 “RS”和“RA”两个状态。这是因为图4中不存在“重生”库所。

一般来说，当手机处于“睡眠”使用模式时，如果手机可以被恢复或自动恢复，并且不让用户注意到，突然崩溃或停机不会对用户体验产生很大影响。但是这样的事情在手机处于“活跃”使用模式时是不可容忍的，因为它可能导致极差的用户体验。为了提升用户体验，“活跃”模式中潜在的系统故障(如崩溃或停机) 和恢复、重生一样，应被尽可能避免。

已知初始状态的转移速率和概率向量时，我们可以得出实施恢复的模型中每个稳定状态的概率：

相似的，我们可以用来表示没有实施恢复的模型中每个稳定状态的概率向量：

在计算出每个稳定状态的概率后，我们可以分析可用性和用户体验，以确定最佳恢复时间间隔。

C.方法评估

在一天

资料编号：[5549]