研究置换面向Flash存储页面置换算法综述要求

论文导读：
摘要：随着时代的进步，现代计算机技术也得到了飞速的发展。Flash存储容量相比之前有了很大的增加，而且还具有很多磁盘没有的优点。因此Flash存储的应用前景非常广。但是Flash存储的页面置换算法也要进行相应的更新，才能适应Flash的发展趋势。本文主要分析Flash存储页面置换算法的两类算法，即普通性页面置换算法和专门性页面置换算法，探讨其各自的应用原理。
关键词：Flash存储 页面置换 算法
1007-9416（2012）12-0103-01
页面置换算法，是指计算机通讯网络在地址映射时，通常会遇到需要访问的页面不在内存中，出现缺页中断的情况。一旦出现这种情况，计算机的操作系统就要在内存中再另外选择一个页面，将其移出内存，从而留出空间给将要调进来的页面。页面置换算法就是选择将哪一个页面移出内存的过程。

1、Flash存储

在Flash存储诞生之前，计算机的存储主要采用的是磁盘存储的方法。磁盘存储功能较小，弊端多，不能满足快速的经济发展要求。而Flash存储相比于磁盘存储，其功耗较小，可靠性高，而且无寻到延迟，可以快速随机读写访问，有良好的抗震性能，因此，逐渐取代磁盘存储，成为未来计算机存储革命的核心技术。
目前，Flash存储主要有两种存储类型，即NANA类型和NOR类型。其中，NOR类型的作用是存储计算机代码，可以支持Flash存储上的每一位数据的随机访问。而NANA类型是目前大部分固态磁盘所采用的Flash存储类型，其目的是对较高密度的数据进行存储，扇区单元级别访问使其主要的读、写访问形式。NANA Flash存储也可以分为两种。一种是MLC Flash存储，其特点是存储容量大，操作时延长，运作成本高。另一种是SLC Flash存储，操作时延较短，成本也比较低，但是存错容量也小。
由于之前一直是使用磁盘存储，因此传统的页面置换算法也是根据磁盘的存储系统来设计的，不能适应Flash 存储系统的应用。为此，需要针对Flash存储系统，设计和优化专门的页面置换算法。

2、Flash存储普适性页面置换算法

所谓普适性的页面置换算法，就是只考虑Flash存储三种基本操作方式（读、写、擦除）开销不对称的问题。

2.1 CFLRU系列算法

CFLRU，即clean first LRU，是Park S.Y等人针对Flash存储而专门研究出来的一种新页面置换算法。它和传统的LRU算法有相同点，页面数据在LUR链表中存储。但不同的是，在这个存储过程中，CFLRU把LRU链表分成了两个工作区域——干净优先区（CF区域）和工作区域。工作区域主要存储的是最近使用的页面。而CF区域是完成页面置换的区域，页面的数目、窗口的大小决定了该区域的大小，主要存储的是干净页面，具有的缓冲数据大。
简单而言，CFLRU算法就是在CF区域选定一个干净的页面进行页面置换，而工作区的干净页面有不会受到干扰，从而保证缓冲效率，提高计算机系统的运行速度。但是，CFLRU算法也有弊端，就是干净优先区的窗口是预先设定大小的，如果不确定应用，就不能动态确定窗口大小，因此，应用不同的话，CFLRU算法不能保证把所有的I/O性能都提高。另外，CFLRU算法只涉及了数据的新近性，但数据页面的访问频率却被忽略了，因此，一些访问频率比较高的页面有可能被替换，从而影响后续的访问。

2.2 LRU-WSR算法

LRU-WSR算法，是一种二次选择算法和CFLRU算法综合而成的冷检测算法。通过二次算法，置换时并不会移除新近访问的脏页，因此有效解决的CFLRU算法没有考虑访问频率的问题，对后续访问不会产生任何影响。为了防止常用范围页面被替换，LRU-WSR算法会在缓冲链表中对这些页面进行冷标志。在选择页面进行置换时，如果该页面是干净的页面，则不用查看是否有冷标志，可以直接置换。如果选择页面时脏页面，则系统会先主动查看该页面是否有冷标志。若有，那该页面就会被直接替换掉，若没有，该页面会被移到MRU位置上，标上冷标志，然后再从LRU链表上选择一个候选页面就，继续循环的判断。
LRU-WSR算法对窗口的大小没有明确的规定，也不会只用干净页面来置换脏页。因此，它比CFLRU 算法的缓冲命中率更高，而且对页面的访问频率也顾论文导读：3.1CRAW-C算法CRAW-C算法把Flash存储内存分为三个区域：读区域、写区域和压缩读区域。然后再按照具体的页面访问需要，调整或改变三种操作开销。按照访问量来确定初始区域的大小，然后建立ghost队列，替换下来的页面数据就会在这里被保存。从而完成估计访问模式。如果缓冲区域内已经没有闲置的页面，那可以对比当前区域
及到了，Flash 存储的整个存储作用得到了很大的提高。但是，LRU-WSR算法的置换粒度范围比较小，对冷脏页没有进行置换开销，不能快速置换，从而影响了LRU-WSR 算法的置换效果。

3、专门性页面置换算法

专门性页面置换算法除了有普适性页面置换算法一般的功用之外，它还考虑到了当前计算机的应用环境，是专门针对Flash存储特定信息的页面置换算法，对Flash存储性能的提高有巨大的作用。

3.1 CRAW-C算法

CRAW-C算法把Flash存储内存分为三个区域：读区域、写区域和压缩读区域。然后再按照具体的页面访问需要，调整或改变三种操作开销。按照访问量来确定初始区域的大小，然后建立ghost 队列，替换下来的页面数据就会在这里被保存。从而完成估计访问模式。如果缓冲区域内已经没有闲置的页面，那可以对比当前区域与理想区域的大小，选择区别最大的来替换。

3.2 FAB算法

普适性页面置换算法的置换对象是单个页面，而FAB算法的置换对象是整个擦写板块，把同一擦写块中的缓冲页分为一组，然后再采用LRU链表形式组织这些分组。在Flash存储在进行读、写访问时，被选中的页面就会从LRU链表原创论文www.7ctime.com
转移到MRU，然后把脏页内容写在存储中，请求的数据就会填写到新的页面中，达到页面置换的目的。
4、结语
总而言之，随着计算机技术和网络通讯技术的进步，Flash存储将会替代传统的磁盘存储，成为未来计算机存储的核心。而页面置换算法也需要进行相应的改革，跟上Flash存储技术的发展脚步，这样才能全面地促进计算机存储技术的发展。
参考文献
郑文静，李明强，舒继武.Flash存储技术[J].计算机研究与发展，2010，47（4）.
杨修国.关于嵌入式系统中的Flash存储管理的综述[J].科学视野，2008（7）.
[3]朱浩，戴华东，颜跃进.面向Flash存储的页面置换算法综述[J].计算机研究与发展，2011，48（增刊）.