一种移动智能终端的内存回收管理算法∗

余志诚

（海南核电有限公司 昌江 572733）

1 引言

移动智能终端的内存具有功耗低、体积小、读取速度快等诸多优势，但是其存储特性与其他存储介质存在较大差异。移动智能终端内存的基本存储单元是区块，每个区块由一定数量的页构成［1］。内存的基本操作包括数据读出、数据写入和数据擦除［3］。擦除以区块为最小操作对象，而读和写是以页作为最小操作对象，所以擦除开销远大于读写［5］。每个区块的擦除次数是有限的，如果部分区块的擦除次数到达了极限，内存的数据写入性能就会随之恶化，因此需要采取均衡区块擦除次数的机制以延长内存寿命［6］。

移动智能终端在数据写入时不能直接覆盖已存在的数据，需要先擦除内存区块中已有数据。因此当进行数据写入操作时，新数据常常被写到空闲的空间，随后更新内存的地址映射表，地址映射表之外的数据所占用的空间成为无效数据区，无效数据页所在的区块称为脏块［10］。脏块需要进行内存回收操作后才能使用。

移动智能设备内存回收采用贪心算法［2］。这种算法的优势是实现单次内存回收效率最优，但是在面临内存空间中脏块较多时，内存回收的效率变差，且难以很好地兼顾不同区块的磨损均衡等问题［4］。本文针对这种算法的缺陷，提出了一种基于目标块重复搜索的回收算法策略，该算法针对内存脏块较多的情况，采取重复搜索策略，以提高脏块回收效率，而且根据数据写入所触发的内存回收的次数调度的相应内存回收策略，均衡内存中不同区块的擦除次数，提高内存有效使用寿命［7～8］。

2 模型建立

移动智能终端的内存回收采用异地更新机制，其原理如图1所示。首先在内存空间中依据一定的规则选择待回收脏块作为候选块，然后在候选块中依据相应的规则选择1个或多个脏块作为目标块，把目标块中的有用页面复制到空闲块，最后擦除已复制完成的目标块，使其变成空闲块［11～13］。

图1 内存回收过程

2.1 候选块选择的多约束最优化模型

候选块是内存中需要进行回收的脏块。设第n次回收操作时内存脏块分别是Dn.1，…，Dn.xn，每个脏块中的无效页面数分别是Pn.1，…，，每个区块的擦除次数分别是rn.1，…，，Tn是内存回收的限制时间，X为可以回收的数据块的最大值，Tc为页面复制的单位时间，λ为磨损均衡参数，即不同区块的擦除次数最大差值。布尔变量Sn·m表示该脏块是否被选作候选块，Sn·m为1表示在第n次内存回收时Dn·m被选中为候选块，反之表示没有选中。内存回收算法中候选块选择的多约束最优化模型为

由式（1）可知候选块选择的前提是满足响应时间的限制和兼顾磨损均衡，目标是最大程度减少区块擦除次数。

2.2 目标块选择的多约束最优化模型

目标块是被选中进行内存回收操作的候选块。设第n次内存回收时中的候选块为，…，，擦除次数为，…，，因数据写入而导致相应区块的有用页面无效的概率分别为an·1，…，an·η，回收的页面数为，…，，候选区块的数量为η。布尔变量表示是否选中该候选块为目标块。内存回收算法中目标块选择的多约束最优化模型为

由式（2）可知目标块选择的约束条件是候选块内有用页面的数量和候选块的磨损均衡度。

3 基于目标块重复搜索的内存回收算法

移动智能终端在创建或修改文件时触发内存回收。目前移动智能终端的内存回收普遍基于贪心算法。为提升回收效率，内存回收包含Passive和Aggressive两种模式。当空闲块比较多的时候使用Passive模式，而在空闲块的数量较少并且低于设置阈值时采用Aggressive模式。两种模式的目标块搜索算法都是基于贪心机制，即首先选取无效页面低于设置阈值的区块作为候选块，然后选择无效页面数最多的候选块作为目标块进行擦除操作。其中Passive模式的候选块阈值要大大低于Aggres⁃sive模式的阈值，这样的设置在提升了Passive模式下内存回收效率的同时，导致含有较少无效页面的候选块难以及时得到回收，只有等到内存空间耗尽时触发Aggressive模式才能得到回收，由于这些候选块的有效页面较多，擦除开销很大，从而导致Aggressive模式的内存回收开销和触发频率明显提高［14～15］。

针对以上问题，本文提出基于目标块的重复搜索算法。算法对内存中脏块集中区域采用重复搜索的策略，提高存在较多有效页面较多候选块回收效率，延迟Aggressive回收的触发。算法以目标块的擦除次数作为回收目标块的主要依据，引入磨损均衡机制，提高内存均衡度。算法根据单次数据更新的内存回收次数，在贪心算法和磨损均衡算法中合理调度，若在数据更新的内存回收开销较大，则使用贪心算法以提升单次数据更新的效率；若内存回收开销不大，则使用磨损均衡策略以提高内存使用寿命。

3.1 目标块重复搜索策略

移动智能终端的回收算法中目标块分段搜索原理如图1所示。内存被分成包含相同的区块数的内存段，每次回收操作时按顺序依次对内存段进行搜索。为了保证单次回收效率，设定了有效页阈值，如果内存区块有效页数小于阈值就选中为目标快，如果存在多个满足条件的目标块，根据贪心策略，选择有效页最少的目标块进行回收。

图2 逐段搜索原理

由于移动智能终端文件系统空间分配具有随机性，脏块不是均匀分布在整个内存空间中。如果一个搜索段中存在多个满足条件的脏块，而根据贪心策略只能选择其中有效页面最少一块，其他满足条件区块只能等到下一次内存回收被触发时才可能被回收。长此以往，内存空间中可能大量存在有效页低于阈值的脏块难以被及时回收，这回导致触发Aggressive模式的触发频率增大和Aggressive模式下内存回收效率的降低。

分段重复搜索的算法原理如图2所示。重复搜索算法中内存分段的大小保持不变。首先通过搜索模型，确定内存中脏块较多区域，在此区域中，第i次内存回收的起始位置是第i-1次内存回收选择块加x，其中x值随着内存脏块的增多而减小。重复搜索算法能够对内存中脏块比较集中的区域能够实现多次搜索，对满足回收条件的脏块的回收更加彻底，从而避免脏块在内存中的累计耗费宝贵内存空间，进而降低Aggressive模式的触发频率。

图3 重复段搜索原理

3.2 目标块回收调度策略

在回收目标块的选择策略上，贪心算法未考虑内存的磨损情况，这将导致不同区块之间擦除次数差值增大，一些区块较早达到擦除次数上限，会在很大程度上影响存储性能并缩短内存使用寿命。

针对这个问题，本文引入磨损均衡的内存回收思路。首先确定数据更新所触发的内存回收次数，根据内存回收次数的不同采取不同的目标块回收策略。当内存回收次数较多时，内存回收操作将占用较多的系统资源，对数据读写性能产生较大影响，因此依据单次回收效率优先原则使用贪心算法；当回收次数较少时，依据区块擦除均衡优先原则，优先使用磨损均衡算法。

磨损均衡回收算法给满足条件的目标块赋予回收优先级PR(x)，并按优先级依次回收。优先级按式（3）计算。

上式中 page(x)和erase(x)分别表示第x区块的有效页数和擦除次数，Tp为单个区块内的总页数，maxj[e r ase(j)]和minj[e r ase(j)]分别表示内存区块最大和最小擦除次数。β为表示磨损均衡因素在回收选择策略中的控制参数。当采取磨损均衡回收策略时，需要设定磨损程度较轻的区块回收优先级高于磨损程度较高的区块。

设第i次内存回收操作的数据写入量是Dr。内存回收所触发的垃圾回收次数为Cgc。有效页阈值为Pval，即当块中有效页数低于Pval时，该块可被选为目标块。一个内存区块中的总页数为Tp。磨损均衡回收算法描述如下：

1）获取触发内存回收的数据写入量，记为Dr；

2）根据阈值Pval对内存空间进行搜索，计算出此次数据写入操作所触发的垃圾回收次数，记为Cgc；

3）根据回收写入比μ=CgcDr确定目标块选择策略。如果μ＜β，使用式（3）计算优先级，选择优先级最小的区块作为回收目标块。若μ＞β，则使用贪心算法选择目标块。其中β为平衡内存回收算法效率和区块磨损均衡的控制参数。

4）根据选定的回收块选择策略，对符合条件的目标块进行回收。

上述算法中数据写入所触发的内存回收次数Cgc的计算过程描述如下：

1）内存回收次数的变量赋值Cgc=0，触发内存回收的数据写入的变量赋值Dtmp=Dr。

2）如 PearsedPfree＞1/4，则不进行内存回收，转步骤4）执行。

3）使用前述的重复搜索算法对候选区块进行搜索。如第i区块的有效页数 Page(i)＜Pval，则检查此区块是否已标记为目标块。若是，则继续检查下一区块；若否，则将该区块标记为目标块。Cgc=Cgc+1，Pearsed=Pearsed+Tp，Pfree=Pfree+Tp，转步骤5）执行。

4）如果没有搜索到可以回收的目标块，则Pearsed=Pearsed-1，Pfree=Pfree-1。

5）Dtmp=Dtmp-1。如果Dtmp=0，回收所有已标记的目标块，返回Cgc值，结束。否则，转步骤2）执行。

4 实验与分析

4.1 实验环境

实验平台采用三星G9500，Android7.0，内核版本7.0.23.01，CPU频率2.4GHz，4GRAM，64GROM。实验针对三种移动智能终端常用的负载进行测试，负载的存储特性如表1所示。

表1 三种实验负载的特性

基于目标块重复搜索的回收算法可配置的参数组合是一个三元组 ＜Pval，μ，β＞ ，其中 Pval是有效页数阈值，μ为回收比阈值，β为磨损均衡控制参数。Pval设置为6，以便能够使回收符合条件的目标块，降低Aggressive模式的触发次数。回收比设置为0.4，把写操作触发的内存回收块数保持在带写入页数的0.4倍左右，以保证数据写入的性能。β为1，表示完全以磨损均衡策略进行内存回收。为保证磨损均衡因素在内存回收中占有较大权重同时兼顾回收效率，本实验将 β设置为0.7。由此，本实验的参数设置为＜6，0.4，0.7＞。

4.2 结果分析

第一组实验是对贪心算法和基于目标块重复搜索算法的内存回收效率测试。实验结果如图4、图5和图6所示。

图4表示内存回收过程中的有效页从脏块复制到空闲块所需的数量开销。从图中可以看出三种不同程度的负载下，基于目标块重复搜索算法的有效页复制从数量上都少于贪心算法。

图5表示在不同负载下贪心算法和基于目标块重复搜索算法的目标块的擦除次数。从图中可以看出在不同负载下，基于目标块重复搜索算法的目标块擦除数都少于贪心算法。

图6表示在不同负载下贪心算法和基于目标块重复搜索算法的内存回收次数。图中数据表明在不同负载下，基于目标块重复搜索算法的内存回收次数以及Passive内存回收次数都不同程度地小于贪心算法。

图4 有效页复制开销

图5 目标块擦除开销

图6 内存回收次数

由实验结果可知在不同强度的读写负载下，基于目标块重复搜索算法都能表现出对内存回收效率有一定提升作用。其中原因在于，在读写的过程中，内存中目标块的分布具有随机性，而逐段搜索对不同区域的回收效率相等，导致目标块集中的区域难以回收彻底。而基于目标块重复搜索算法对目标块集中区域采取重复搜索的策略，能够比较彻底地回收目标块，有效减少有效页复制和目标块擦除的次数，提升内存回收效率。

第二组实验针对两种算法的不同区块擦除次数进行记录。实验对反复运行100次视频存储负载。两种算法的不同区块擦除次数如图7所示。

图7 横轴表示区块号，纵轴表示时内存区块的擦除次数，图中数据表示实验结束时0～1000号内存区块的擦除次数。根据计算贪心算法的不同区块擦除次数的标准方差为10.13，基于目标块重复搜索算法的标准方差是6.04。由此可见基于目标块重复搜索算法的磨损均衡度更好。这是由于基于目标块重复搜索算法在目标块的选择时，优先对擦除次数较少的目标块进行回收，缩小了不同目标块擦除次数的差值，使得内存的磨损更加均衡。

5 结语

本文在对移动智能终端的内存回收候选块和目标块的选择进行模型分析的基础上，提出了分段重复搜索的思路，阐述了基于目标块重复搜索内存回收算法。通过实验表明，本文提出的针对移动智能终端的内存回收算法相对于贪心算法，可以减少回收过程中有效页复制开销，降低目标块擦除次数，减少内存回收的触发次数，能够获得更好的数据读写效率，提升移动智能终端的内存使用寿命。