一种基于NAND闪存高效的页面替换算法

于万钧　张海军　刘全

摘 要： 针对不同NAND闪存读写操作成本比例的不同，提出一种具有高效页面替换功能的EPRA算法。在内存中，每个受害者候选页被分成固定数量的闪存页面。 EPRA给每个受害者候选页分配权重值，在选择与修改页面时对权重进行调节，从候选页中选择具有最小权重值的页面作为受害者页。EPRA 算法把受害者页中分为热的闪存页和冷的闪存页，并把这些数据写到 NAND 闪存中不同空闲的块中。仿真实验结果表明，EPRA算法使用在不同种类的NAND闪存中时，性能优于现有的页面替换算法。

关键词： 页面替换算法； 权重值分配； NAND闪存存储； 受害者页

中图分类号： TN915?34； TP311 文献标识码： A 文章编号： 1004?373X（2017）16?0053?04

Abstract： In allusion to different cost ratios of read?write operation for different NAND flash memories， an EPRA algorithm with efficient page replacement function is proposed in this paper. Each victim candidate page in the internal storage is divided into a fixed number of flash pages. EPRA assigns a weighted value to each victim candidate page， and adjusts the weighted values in the process of page selection and modification. The page with least weighted value is selected in the candidate page as a victim page. EPRA divides the dirty flash pages into the hot dirty flash memory pages and cold ones， and writes the data in the different blocks in NAND flash memory. The trace?driven simulation resultes show that the EPRA algorithm is superior to the existing page replacement algorithms when it is used in different kinds of NAND flash memories.

Keywords： page replacement algorithm； weighted value allocation； NAND flash memory； victim page

0 引 言

近年来，闪存成为消费电子产品一种最重要的存储设备。闪存有许多诱人的特点，例如体积小、速度快、可抗震、高可靠性、重量轻、低功耗等。单个的NAND闪存芯片存储容量正在增加，且其价格不断下降。因此，越来越多的消费电子产品使用闪存取代磁盘[1]。

由于电子产品中主存储器空间有限，所以操作系统中应该包含页面替换算法，当空闲页的数量不足时，该算法能够获得空闲的页面。在假设磁盘I/O操作成本相等的情况下，人们研究了如何使磁盘页面命中率最大化的页面替换算法[2?4]。NAND闪存存在I/O操作成本不同和先擦后写的硬件约束，因此，传统的页面替换算法不适用于NAND闪存设备，有必要提出一种新的基于NAND闪存设备特点的页面替换算法。许多NAND页面替换算法假设写操作的成本远远高于读操作成本，优先驱除干净页，并非所有类型的NAND闪存都是这样的。表1为4种不同的NAND 闪存类型的写操作和读操作之间成本比例。因此，以优先驱逐干净页的页面替换算法不适用于不同种类的NAND闪存[5?6]。

表1 不同种类的NAND闪存写操作和读操作的成本比例 %

1 背 景

目前主要有两种闪存存储器，NOR闪存和NAND闪存[7]。两者都是用于计算机和消费电子产品的非易失性存储介质。闪存是基于E2PROM的设计原则发明的，可擦除和重复编程。NOR闪存有两个突出的特点，快速存取和片内执行（XIP），因此它经常被用来代替ROM和执行时应用程序代码。

每个NAND闪存是由若干个块组成，每个块分成固定数量的页。每个块和页面的大小通常分别为16 KB和512 B。每一页有一个备用区，备用区的典型大小是16 B，这一般用来存储读操作和写操作过程中发生错误的校验码。NAND闪存有三种类型的操作：读取、写入及擦除操作。读、写操作的基本单元是一个页面，而擦除操作的基本单元是一个块。NAND闪存先擦除后写，且读操作和写操作成本不一样，为了解决NAND闪存中读操作和写操作成本不对称的问题，现有的许多页面替换算法都是在假设读操作成本远高于写操作成本的情况下做研究的，优先驱逐干净页。

2 相关研究工作

LRU是经典的页面替换算法，在现有的系统中，基本上都是采用LRU算法或者类LRU算法[8]。在研究LRU算法的基础上，大量的用于NAND闪存的页面替换算法出现了。Park等人提出了一种高效页面替换算法（CFLRU）[9?10]。 CFLU算法将LRU逻辑链表分为工作区和替换区。在进行页面替换时，优先替换其中的干净页面，该策略将脏页面保留在替换区域中，延迟脏页面写的时间。当替换区域没有干净页面的时候，CFLRU将按照LRU顺序处理其余的页面。endprint

Jung等人提出了LRU?WSR算法[11]。LRU?WSR算法为每个链表添加一个冷标识位，冷标识位为0表明该页是热页，冷标识位为1表明该页是冷页。LRU?WSR算法将热区中的数据页转移到冷区时，判断热区中LRU位置的数据页属性，如果是冷标识位为1的脏页或者是干净页，将该页转移到冷区的MRU位置；如果是冷标识位为0的脏页，将该页冷标识位置为1，移到热区的MRU位置，重复上述判断。LRU?WSR算法考虑了脏页的冷热属性，但是却忽略了干净页的冷热属性。

Li等人提出了CCF?LRU算法[12]。CCF?LRU算法将缓冲区分为两个LRU链表，即L1和L2，L1用于存放热干净页和脏页，L2用于存放冷干净页。CCF?LRU算法优先替换L2中的页面，当L2链表为空时，将在L1中使用LRU?WSR算法选择页面。CCF?LRU算法将缓冲区分为两列，减少一次操作对缓冲区的污染，在访问局部性数据时效率很高，但是该算法无法控制L2链表的长度，在某些情况下，会降低页面命中率。

现有页面替换算法没有考虑到不同NAND闪存的写入和读开销比例是不同的，因而不能很好地用于各类NAND闪存，所以有必要设计一种适用于各种NAND闪存的高效的页面替换算法。

3 EPRA页面替换算法

本节提出一种高效的EPRA（Efficient Page Replacement Algorithm）算法，适用于不同种类的读写成本比例不同的NAND闪存。如图1所示，EPRA维持两个页链表，即干净页链表和脏页链表。

内存中的脏页面通常包含部分干净的数据[13?14]。典型内存页和闪存页的大小分别为4 KB和512 B，因此，将受害者脏页写回到NAND设备中需要8次写操作，包括将干净数据写回到NAND闪存中的冗余操作。为了识别脏页内的干净数据，避免多余的写操作，EPRA算法将脏页链表中每一页分成8份，脏页中的闪存页都设置一个脏标志位。内存中的闪存页在NAND设备中都有一个副本，如果内容不同，将脏标志位设置为1，如果相同，标志位不变，该页视为干净的闪存页。

EPRA算法给干净页链表和脏页链表中每一页加上一个权重值。干净页链表中的权重值为式（1），而脏页链表中的权重值为式（2）：

[mCrPage] （1）

[nCw+mCrPage] （2）

式中：m是页面P拥有总的闪存页数目；Cr是读操作成本；Page是页上次引用的时间；n是页面P拥有的脏的闪存页数目；Cw是写操作成本。干净页链表和脏页链表中的页面从左到右是以权重值升序排列的，EPRA算法比较干净页链表中最左边页的权重值和脏页链表中的最左边页的权重值，选择权重值较小的一页作为受害者页。将热的脏页和冷的脏页写到NAND闪存中同一个空闲块时，由于热的闪存页和冷的闪存页无效的时间不同，垃圾回收的过程中写操作造成很大的开销。为了区分脏页链表中的脏页，记录脏页链表中每个脏页的最近引用时间。当选择了一个脏受害者页时，EPRA使用HD来记录这个热度值，脏页的HD值计算方式为：

[HD=Tc-Tr] （3）

式中，Tc和Tr分别是当前时间和脏闪存页的最近引用时间。因此，HD值等于其引用经过的总时间。

为了避免HD值太大而使精度受到影響，使HD值大小范围为0～1，公式为式（4）：

[NHD=HD-mini∈n（HDi）maxi∈n（HDi）-mini∈n（HDi）] （4）

式中：NHD是标准化后的HD值；n是受害者页中脏闪存页的数目；HDi是第i个脏闪存页的HD值。如果脏闪存页的NHD值小于或者等于受害者页中所有脏闪存页的NHD平均值，那么该脏闪存页是热脏闪存页，相反，这个闪存页将被认为是冷脏闪存页。

当选择一个受害者页面后，EPRA算法检查该受害者是否是干净的。如果受害者页是干净的，擦除受害者页，释放相应的页存储空间。如果受害者页面是从脏页链表中选择的，只读取脏受害者页中的脏闪存页。如图2所示，为了减少垃圾回收操作时的性能开销，EPRA算法利用HD值区分出热的脏闪存页和冷的脏闪存页，并把它们写回到NAND设备中不同的空闲块中。

4 实验及性能评估

在本节中，将EPRA和现有的LRU，CFLRU，LRU?WSR，CCF?LRU算法进行比较。本实验使用K1和K2表示两种不同的应用类型，如表2所示，K1是写密集型应用，而K2是读密集型应用。

表2 测试数据的统计信息

本实验使用两种读写操作成本比例不同的NAND设备进行实验，分别称为T1和T2。T1的写操作成本和读操作成本比例是120∶1，T2的写操作成本和读操作成本的比例是2∶1。DFTL[15]闪存转换层将这两种NAND闪存设备模拟为块设备，使用贪婪垃圾回收算法来回收垃圾。DFTL被设成当NAND设备中空闲块的比例低于5%时自动进行垃圾回收过程，当空闲块的比例高于15%时自动停止垃圾回收过程。

性能指标主要是页面命中率，读操作的次数，拷贝操作的次数，运行时间。图3为使用不同算法测试T1和T2两种NAND设备页面命中率的实验结果，因为EPRA算法在选择一个受害者页时，将每个受害者页的上一次的引用时间考虑在内，所以EPRA算法页面命中率最高。

图4为使用不同算法写操作的实验结果，EPRA算法将每个脏受害者页分成一定数量的页面，使页面大小和NAND闪存页大小相同，仅仅把脏受害者中的脏闪存页写回到NAND闪存中，所以EPRA算法使NAND设备的写操作次数最少。

图5为在T1和T2两种NAND设备上两种不同应用类型的拷贝操作次数的情况分布。EPRA算法考虑到了脏受害者页中每个脏闪存页的HD值，把脏受害者页中的热脏闪存页和冷脏闪存页分别写到NAND设备不同的空闲块中，没有把脏受害者页中的干净页写到NAND设备中，而其他的页面替换算法将脏受害者页中的数据全部写回到NAND设备中。从图5可以看出，EPRA算法在垃圾回收的过程中，拷贝操作次数最少。endprint

图6为T1和T2两种NAND设备上使用不同算法的运行时间的结果分布。如图6所示，因为EPRA算法有着最高的页面命中率和最少的写操作次数，所以运行时间也就最短。CFLRU，LRU?WSR和CCF?LRU算法在假设NAND写操作的成本远高于读操作的成本下优先驱逐干净页，这些算法在T1设备上性能很好，但是在T2这个写操作和读操作成本比例很低的设备上，效果很差。EPRA算法把I/O操作成本和每页上次的引用时间考虑在内，给每页分配一个权重值，因此，EPRA算法在T1和T2两种NAND设备上性能都很好。

5 结 语

本文提出了一种高效的页面替换算法——EPRA算法。该算法在各种类型的NAND闪存上都具有很好的性能。EPRA算法维持两个链表，一个是干净页链表，另一个是脏页链表。EPRA算法假设内存页和闪存页大小为4 KB和512 B，将内存页分成8份。EPRA算法给两个页链表中的每页都分配一个权重值，选择权重值最小的页作为受害者页。如果是从脏页链表中选出了受害者页，从脏受害者中的脏闪存页区分出热脏闪存页和冷脏闪存页，分别将热脏闪存页和冷脏闪存页写回到NAND闪存不同的块中。实验结果表明，EPRA算法适用各种NAND闪存，且在页面命中率方面，读写操作次数和拷贝操作次数与运行时间方面性能比现有的算法性能优越。

参考文献

[1] WEI Yuanting， SHIN Dongkun. NAND flash storage device performance in Linux file system [C]// Proceedings of the 6th International Conference on Computer Sciences and Convergence Information Technology. [S.l.： s.n.]， 2011： 574?577.

[2] O′NEIL E J， O′NEIL P E， WEIKUM G. The LRU?K page replacement algorithm for database disk buffering [C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. [S.l.： s.n.]， 1993： 297?306.

[3] JIANG S， ZHANG X D. LIRS： an efficient low inter?reference recency set replacement policy to improve buffer cache performance [C]// Proceedings of ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems. [S.l.： s.n.]， 2002： 31?42.

[4] Johnson Theodore， SHASHA Dennis. 2Q： a low overhead high performance buffer management replacement algorithm [C]// Proceedings of the 20th international Conference on Very Large Databases. [S.l.： s.n.]， 1994： 439? 450.

[5] 林子雨，赖明星，邹权，等.基于替换概率的闪存数据库缓冲区替换算法[J].计算机学报，2013（8）：1568?1581.

[6] 陈金忠，姚念民，蔡邵滨.基于NAND闪存的高性能和可靠的PRAID?6[J].电子学报，2015（6）：1211?1217.

[7] BEZ Roberto， CAMERLENGHI Emilio， MODELLI Alberto， et al. Introduction to flash memory [J]. Proceedings of the IEEE， 2003（91）：489?501.

[8] 李芳，徐丽，陈亮亮.LRU近似算法的研究[J].现代电子技术，2009，32（10）：36?38.

[9] PARK Chanik， KANG Jeong?Uk， PARK Seon?Yeong， et al. Energy?aware demand paging on NAND flash?based embedded storages [C]// Proceedings of the 2004 International Symposium on Low Power Electronics and Design. [S.l.： s.n.]， 2004： 338?343.

[10] PARK S Y， JUNG D. CFLRU： A replacement algorithm for flash memory [C]// Proceedings of the 2006 International Conference on Compilers， Architecture and Synthesis for embedded systems. [S.l.： s.n.]， 2006： 234? 241.

[11] JUNG H， SHIM H， PARK S， et al. LRU?WSR： integration of LRU and writes sequence reordering for flash memory [J]. IEEE transactions on consumer electronics， 2008（54）： 1215?1223.

[12] LI Z， JIN P， SU X， et al. CCF?LRU： a new buffer replacement algorithm for flash memory [J]. IEEE transactions on consumer electronics， 2009（55）： 1351?1359.

[13] LI Hanlin， YANG Chialin， TSENG H W. Energy?aware flash memory management in virtual memory system [J]. IEEE transactions on very large scale integration systems， 2008， 16（8）： 952?964.

[14] LIN Mingwei， CHEN Shuyu， WANG Guiping. Greedy page replacement algorithm for flash?aware swap system [J]. IEEE transactions on consumer electronics， 2012（58）： 435?440.

[15] GUPTA Aayush， KIM Youngjae， URGAONKAR Bhuvan. DFTL： a flash translation layer employing demand?based selective caching of pagelevel address mappings [J]. ACM SIGPLAN notices， 2009（44）： 229?240.endprint