一种基于双窗口的NAND闪存缓冲区管理算法

徐之光，严 华

(四川大学电子信息学院，成都 610065)

NAND闪存是现今最具前途的存储介质之一，有非易失性、抗冲击性强、数据读写速度快、能耗低、噪音低、易移动性等特点[1-2]。NAND闪存广泛应用于移动设备、PC设备及大数据中心[3]，在呈现爆发式增长的5G应用、大数据和云计算、车载、智能终端、VR等领域都有卓越表现。

NAND闪存存储空间由若干个块(Block物理块)构成，而每个块又由若干个页(Page物理页)构成。NAND闪存有读、写、擦除三种基本操作，其中读/写操作执行单位为页，而擦除操作执行单位为块，一般每个块的擦除次数上限在104～105次，超过则会使闪存的存储性能下降[4]。NAND闪存的3种基本操作的耗时不同，擦除耗时最长、写操作其次而读速度最快，同时闪存必须先擦除才能写入新数据，而不支持覆盖写的方式[5-6]。这些特点使得NAND闪存在进行读写操作的过程中，其存储性能逐渐降低，使用寿命逐渐变短。而使用NAND闪存缓冲区管理是提高闪存存储性能、延长其使用寿命的一个有效方法，其基本原理为利用数据访问具有局部性的特点，将访问频度高的数据存入缓冲区，使得数据访问尽量在缓冲区中命中，有效降低闪存的访问开销[7]。

近年来，中外学者提出了很多缓冲区管理策略，如LRU(least recently use)算法、LRU-WSR[8](LRU-write sequence reordering)算法、PR-LRU[9](probability of reference LRU)算法等。LRU算法是经典缓冲区页面置换算法，它认为最有可能下次访问到的页面是最近访问过的页面，所以总是将最近访问的数据存放在缓冲区中，而淘汰最近没有访问过的页面。但是LRU算法是根据传统机械硬盘设计，没有考虑闪存的读/写操作延迟非对称性，因此在闪存中算法性能较差。LRU-WSR算法在LRU的基础上进一步区分了冷热数据，滞后置换出缓冲区的脏数据页，而优先置换出干净数据页和冷脏数据页，减少了NAND闪存的写操作次数，提高了缓冲区命中率。但LRU-WSR算法仍存在一些不足：①若某段时间内只对干净数据页进行频繁访问，会导致热脏数据页很快置换出缓冲区，造成闪存的访问开销明显增加；②算法没有考虑干净数据页面访问频率，可能会造成热干净数据页先于冷干净数据页被置换出，降低缓冲区的命中率。PR-LRU算法在LRU-WSR算法冷、热LRU队列基础上，增加了一个驱逐LRU队列来筛选置换出缓冲区的页面，利用之前页面的访问历史，计算页面的访问概率，从而预测未来页面访问情况。但PR-LRU算法仍存在一些不足：①没有考虑控制冷LRU队列长度，也没有在驱逐LRU队列中滞后置换新的冷页面，导致冷LRU长度不够时，刚进缓冲区的冷干净页面可能被很快置换出，从而增加了闪存的访问开销；②算法没有考虑根据负载不同，调整冷/热LRU队列长度比例，负载局部性较高时，热LRU队列长度不足会导致算法性能下降，而负载局部性较低时，热LRU队列则需要被分配更低空间比例。

已有的NAND闪存缓冲区页面置换算法针对NAND闪存的特性，基本都对数据页面冷热和读写访问开销差异进行了考虑，并制定相应的置换策略。但这些算法置换代价比较固定，缺少对冷干净页面最少数量的控制，导致刚进入缓冲区的冷干净页面很快置换出；缺少对长时间未被访问的热脏页面的考虑，导致这些旧热脏页面滞留在缓冲区;且已有算法每次进行页面页面替换时都需要反向遍历链表，算法效率有待提高。

通过对NAND闪存缓冲区管理算法进行更深入的研究，针对上述3种算法的不足，设计一种基于双窗口的NAND闪存缓冲区页面置换算法——DW-LRU(double windows LRU)算法。与已有算法不同的是：将冷、热2条LRU队列细分为冷干净、冷脏、热干净、热脏4条LRU链表，并且引入新近度OR(operation recency)，进一步细分页面的置换代价。算法采用新的置换策略调整页面，直接从各链表LRU端置换页面，无需反向遍历链表。并且DW-LRU算法在冷干净LRU链表设置了静态窗口w1，限定了冷干净LRU链表的最小长度；在热脏LRU链表上设置了动态窗口w2，让长时间没被访问的旧热脏页面也能被置换出缓冲区。实验基于Linux系统，使用Qemu软件建立嵌入式仿真平台，在数据缓冲区命中率、闪存写操作次数和算法运行时间等方面[8-9]与上述3种算法进行对比。

1 算法的实现

1.1 基本原理

图1为DW-LRU算法缓冲区结构示意图。DW-LRU算法在缓存区维护了4个LRU链表来管理，即都是用最少最近原则将数据页组成链表，以最近使用位置(MRU端)为首，以访问时间间隔最久位置(LRU端)为尾，分别存放冷干净页面(CC)、冷脏页面(CD、热干净页面(HC)和热脏页面(HD)。

图1 DW-LRU算法结构示意图

当上层文件系统执行写请求时，在缓存中对某数据页面进行过写操作，该页面数据被修改为与NAND闪存中数据不一致，需要被置换出缓存区将数据写入NAND闪存设备中，这样的页面称为脏页面。反之，上层文件系统仅对某数据页面进行读操作而未进行过写操作的页面，则称之为干净页面[8]。显然，干净页面不必回写到NAND闪存，对于缓存区页面置换算法来说置换代价更低。而考虑数据访问频度，又可将缓冲区中数据页面分为冷数据页面和热数据页面，将其中仅被上层文件系统访问过一次的页面称为冷数据页面，而将被访问过多次的页面称为热数据页面[8-9]。因此，缓存区页面被分为4类：冷干净页面、冷脏页面、热干净页面及热脏页面。其页面缓冲区置换代价关系如式(1)所示：

CCC

(1)

式(1)中：CCC为冷干净页面置换代价；CCD为冷脏页面置换代价；CHC为热干净页面置换代价；CHD为热脏页面置换代价。

然而，由于冷干净页面置换代价最小，如果不考虑控制冷干净LRU链表长度，保留一部分冷干净页面，可能会很快置换出刚写入缓存区的冷干净页面，降低了缓存区命中率。因此，在冷干净LRU链表头部设置了静态窗口w1来控制其长度，w1大小为占整个缓冲区的大小的百分比。同时，由于热脏页面置换代价最大，可能会造成长时间未被访问的热脏页面长期滞留在缓存区中，称这些页面为旧热脏页面。因此，在热脏LRU尾部设置了动态窗口w2来处理旧热脏页面，w2大小为占整个缓冲区大小的百分比。

DW-LRU算法将数据页面存放在相应链表中，进行页面置换时，检索一遍缓存区后，无需像已有算法如LRU-WSR算法和PR-LRU算法再检索链表查找代价最低的数据页来置换，而是直接对链表LRU端进行操作，从而减少了算法所需的运行时间。

DW-LRU算法主要思想如下。

(1)根据数据页面的冷热特征和访问频率，在缓冲区中维护了4个LRU链表来存放相应页面，并引入新近度，来进一步细分热干净和热脏页面的置换代价，将数据页面继续分成6类：冷干净页面、冷脏页面、旧热干净页面、非旧热干净页面、旧热脏页面及非热脏页面。

(2)在冷干净LRU链表头部设置了一个静态窗口w1，仅当链表长度大于其窗口值时，才优先从中置换出冷干净页面，避免最近写入缓冲区中的冷干净页面被快速置换出，影响缓存区命中率。

(3)在热脏LRU链表尾部设置了一个动态窗口w2，用来处理长时间没被访问的热脏页面，提高缓存区命中率。

1.2 页面置换策略

DW-LRU算法为了更全面地分析页面状态，不仅考虑其冷热脏净属性，还需考虑其新近度OR。一次访问的新近度为在最近一次读/写访问当前页面之后系统执行的不同读/写访问操作的数量[10]。

热脏LRU链表尾部动态窗口w2的定义如式(2)、式(3)所示：

(2)

ΔOlru=Olru_i+1-Olru_i

(3)

式中：Olru_i+1为当前热脏LRU链表尾部LRU端页面的新近度；Olru_i为上次访问热脏LRU链表时，其LRU端页面的新近度；ΔOlru表示当前LRU端页面新近度与上次的差值；Di+1为当前热脏LRU链表动态窗口的大小，其值为占整个缓冲区的百分比；Di为上次热脏LRU链表动态窗口的大小；D初始值为Chdm，Chdm为常量，值为占整个缓存区大小的固定百分比，表示热脏LRU链表的最小窗口值。

DW-LRU算法通过动态窗口w2处理旧热脏页面，动态窗口w2大小作用主要为控制从热脏LRU链表移动合适数量的旧热脏页面至冷脏LRU链表，移动过多或过少旧热脏页面都会影响算法性能。处理热脏LRU链表LRU端页面时，参考其新进度与上一次访问热脏LRU链表时LRU端值的变化情况调整窗口w2大小：当ΔOlru>0时，表示热脏LRU链表尾端页面未被访问时间变长，从侧面表示当前热脏LRU链表中仍存在较多旧热脏页面，因此需增加窗口w2大小；当ΔOlru<0时尾端页面未被访问时间变短，从侧面表示当前热脏LRU链表中旧热脏页面较少，因此需减少窗口w2大小；当ΔOlru=0时，则保持窗口w2不变。

而在热脏LRU链表动态窗口w2中旧热脏页面的判断方法如下：①若Opage≥CoSbuffer，则该页面为旧热脏页面；②若Opage

CCC

(4)

式(4)中：COHC为旧热干净页面置换代价；CNOHC为非旧热干净页面置换代价；COHD为旧热脏页面置换代价；CNOHD为非旧热脏页面置换代价。

因此，DW-LRU缓冲区页面置换策略如下。

步骤1当缓冲区空间满，且数据页面在缓冲区被命中时，若该页面为干净页面，同时该访问为写操作时，放之至热干净LRU链表MRU端；否则，放之至热脏LRU链表MRU端。

步骤2数据页面未被缓冲区命中时，若冷干净LRU链表长度大于静态窗口w1，则置换出链表LRU端页面。

步骤3若步骤2中条件不符合，而热干净LRU链表的LRU端为旧热干净页面，则置换出此页面；若该页面为非旧热干净页面，且冷脏LRU链表长度大于静态窗口w1，则置换出冷脏LRU链表中LRU端页面。

步骤4若步骤(2)、步骤(3)中条件都不符合，此时如果热干净LRU链表长度大于0，则置换出热干净LRU链表的LRU端页面。

步骤5若步骤(2)～步骤(4)的条件都不符合，则置换出热脏LRU链表的LRU端页面，同时更新动态窗口w2的大小，并且将中的旧热脏页面按原顺序依次放至冷脏LRU链表的MRU端。

2 实验环境

实验基于Linux系统，使用Qemu软件模拟ARM处理器，建立了嵌入式仿真平台,并对文件系统YAFFS2进行了移植，而NAND闪存设备则是使用NANDsim来模拟。实验对象模拟的NAND闪存存储容量为64 MB，而每个数据页面存储容量为2 KB，即共有32 000个数据页面。NAND闪存主要参数特性如表1所示。

表1 NAND闪存主要参数特性

实验采用了3种模拟测试数据，其详细信息如表2所示，其中“局部性”中的“80%/20%”表示80%的访问请求集中在20%的页面上，“读/写比例”中“x%/y%”表示总的访问请求中读写操作各占x%和y%。每个测试数据集都包含100万条总访问请求数，分布在10 000个不同的数据页面上。如T1测试数据集中读请求占10%即105条，写请求占90%即9×105条，而T1的“局部性”为“80%/20%”，即8×105条访问请求分布在2 000个不同的数据页面上，而20万条访问请求分布在8 000个不同的数据页面上。仿真实验中具体参数值如表3所示。

表2 模拟测试数据的详细信息

表3 仿真实验参数

3 实验结果与分析

表4为DW-LRU算法在T1测试数据集和缓存区大小为1 MB情况下，静态窗口w1取不同值时，缓冲区命中率、闪存写操作次数和运行时间情况。由表4可知，w1取值为1%时，相比取值为0时(即不使用静态窗口w1)，虽然因为算法保留了部分冷干净页面在缓存区的缘故，闪存写操作次数有小幅度上升，但是缓冲区命中率明显提升，运行时间也明显下降，说明此时算法性能更佳。同时，相比其他取值，w1取值为1%时，缓冲区命中率、闪存写操作次数、运行时间均取到最优值。因此，在验证DW-LRU算法性能时选择参数w1为1%。

表4 DW-LRU算法取不同w1的实验结果

表5为DW-LRU算法在T1测试数据集和缓存区大小为1 MB情况下，取不同Co时，缓冲区命中率、闪存写操作次数和运行时间情况。由表5可知,Co=3时，缓冲区实现命中率最大值且闪存写操作次数、运行时间均为最小值，故选择参数Co=3。

表5 DW-LRU算法取不同Co的实验结果

3.1 缓冲区命中率比较

缓冲区命中率的计算公式为

Rh=Ch/Ct

(5)

式(5)中：Ch为数据访问在缓冲区中命中的次数；Ct为总数据访问请求数。

图2为DW-LRU算法和3种已有算法在不同测试数据集及T1～T3下，缓冲区命中率的比较情况。实验表明4种算法的命中率都随着缓冲区大小增加而提升，而DW-LRU算法缓冲区命中率始终高于其他算法。这是由于DW-LRU算法将缓存区细分成了4个LRU链表并将缓冲区页面置换代价细分为6类，对置换策略做了详尽考虑，因此提高了命中率。对于冷干净LRU链表，考虑控制其长度，为其设置了一个最小窗口w1，使得最近被访问且刚写入缓冲区的冷干净页面不会立即被置换出；同理，对于冷脏LRU链表，也考虑了其长度问题，当冷脏LRU链表长度大于冷干净LRU链表时，才会考虑从冷脏LRU链表进行置换。另外，DW-LRU算法引进了新近度OR，对页面的置换代价进行进一步划分。对于冷脏LRU链表和热干净LRU链表，置换策略为若后者LRU端页面为旧热干净页面，则优先置换出，否则选择置换冷脏LRU链表LRU端页面，最后选择置换热干净LRU端页面；而对于热脏LRU链表，使用动态窗口w2把链表中旧热脏页面调整至热干净链表，避免旧热脏页面一直存储在缓冲区，影响算法命中率。

图2 不同缓存区大小下的缓冲区命中率

实验结果表明，DW-LRU链表缓冲区命中率相较于LRU算法、LRU-WSR算法、PR-LRU算法，平均提升16.8%、12.3%、2.8%。

3.2 闪存写操作次数比较

图3为4种算法在3种测试数据集下的闪存写操作次数比较情况，观察可知DW-LRU算法的闪存写操作次数均小于其他算法。而在T1测试数据集DW-LRU此性能优势最明显，相较于LRU算法、LRU-WSR算法、PR-LRU算法，闪存写操作次数平均降低了35.7%、28.9%、5.8%。因为DW-LRU算法有较高的缓冲区命中率，故闪存在NAND设备上直接物理写操作次数较少，且DW-LRU算法一般优先选择从缓存区中置换出干净页面，而尽可能保留脏页面，并以冷热新旧作为辅助评判标准，有效减少闪存写操作次数。

图3 不同缓存区大小下的闪存写操作次数

3.3 运行时间比较

图4为4种算法在3种测试数据集下运行时间比较情况，观察可知DW-LRU算法的运行时间均小于其他算法。这是由于DW-LRU算法在缓冲区命中率上取得较好效果，直接作用到NAND闪存设备的物理读/写/擦除操作次数较少，故运行时间较短。此外，DW-LRU算法通过特定置换策略调整页面在各链表的位置，执行置换时直接从某链表的LRU端进行置换，避免了反向遍历整条链表，在一定程度上提高了算法运行速率。在T3测试数据集中DW-LRU算法比LRU算法、LRU-WSR算法、PR-LRU算法，运行时间平均降低了46.2%、29.5%、13.1%。

图4 不同缓存区大小下的运行时间

4 结论

提出了一种基于双窗口的NAND闪存的缓存区管理算法，与现有算法做的改进有：①在缓存区中根据访问频度、冷热特征维护了4个LRU链表分别存放相应页面,并且引入了新近度OR，将页面进一步细分为了6类：冷干净页面、冷脏页面、旧热干净页面、非旧热干净页面、旧热脏页面、非旧热脏页面，通过细化置换代价提高缓冲区命中率；②通过置换策略调整页面，直接从各链表LRU端置换页面，避免反向遍历链表带来的问题，提高了算法运算效率；③冷干净LRU链表设置了静态窗口w1，给了冷干净页面一些保留在缓冲区的机会；④在热脏LRU链表上设置了动态窗口w2，让长时间没被访问的旧热脏页面也有机会被置换出缓冲区。

实验证明该算法相比于LRU、LRU-WSR和PR-LRU算法，在缓冲区命中率、闪存写操作次数和算法运行时间等方面具有更好的性能。