论文部分内容阅读
摘要:Flash存储设备与传统针对磁盘构成的存储系统设计不同,具有许多新的特征,如读、写以及删除操作的I/O开销并不对称,因此要对Flash存储的页面置换算法进行重新设计。面向Flash存储的普适页面置换算法以及专门性的页面置换算法是当前算法的两大类型。普适性的页面置换算法可以减少二级存储设备中的写回操作,具有较高的性能。以Flash系统为基础所提出的专门性页面置换算法,考虑了Flash存储的特性,同时也针对特定的应用信息进行设计,最大限度提高了存储设备的性能,为类似Flash存储的页面置换算法的研究提供了参考的经验。
关键词:Flash存储;页面置换;算法
中图分类号:TP333 文献标识码:A 文章编号:1007-9599 (2012) 13-0000-02
随着Flash存储容量的逐渐加大,当前单片可达到32G-64G的内存容量,并且随着Flash技术的发展成本也逐渐下降,基于Flash存储的设备也得到了广泛的应用,性能较为稳定的Flash设备具有无寻道延迟、读写访问迅速以及低功耗、抗震性能较好且安全稳定性较高等特征,因此Flash具有良好的发展趋势。当前,基于Flash存储设备在移动设备上得到了有效的应用。在实际的应用过程中,还应充分考虑其在传统的操作系统上的优化是否合理。相对于磁盘的读写而言,Flash的存储涉及到读写以及擦除操作,读写以页数为单位,而擦除则是以块为单位,页面是Flash存储所使用的最小单位,每一个块中包含了多个页面。由于Flash方式没有寻道的时间,在覆盖存储之前必须进行擦除操作,致使Flash存储的读写操作的性能开销具有较大的不对称。由此要重新考虑操作策略,满足Flash存储系统的性能需求。
一、Flash存储概述
就理论上而言,Flash存储具有NOR以及NAND两种存储类型。NOR类型的Flash存储机制是支持每位上的随机访问,主要实现计算机代码的存储,而NAND的Flash的存储机制则用于存储高密度的数据形式,由于其读写的访问形式是通过扇区的单元级别进行访问的。当前电子市场上的多数SSD都是以NAND为存储基础的。就NAND的Flash存储机制而言,具有两种形式:SLC(Single level cell)和MLC(Multi level cell)。MLC的存储容量相对而言较大,由此其操作的时延也将更大,其运行的成本也相对较高。当前已有将MLC以及SLC结合起来,构成新型的Flash的存储方式研究。
如上所述,Flash的存储方式包括读写以及擦除三种操作形式,而Flash的存储单元所能进行的擦除次数是有限的,一般在十万到百万次之间,为了提高Flash存储单元的使用时间,必须是实际的使用过程中,使擦除的操作尽量分布在每一个存储块上,由此Flash存储的负载损耗以及垃圾回收也将是一个重要的问题。作为很重要的存储介质,Flash存储虽然与磁盘的存储介质有了一定的结合,但其依旧具有较高的成本。
二、普适性页面置换算法
(一)CFLRU系列算法
CFLRU是新提出的页面置换算法,CFLRU算法是通过在LRU链表中保存页面数据,但在保存过程中,将数据链表分为了工作区域以及CF区域。CF区域实际上也可定义为干净优先区,这个区域也是进行页面置换的区域。这个区域的大小是以包括的页面数目以及窗口的大小为标准进行衡量的。工作区域包括当前所使用的页面,干净页都存在于CF区,由此CF区域具有大量的缓冲数据。在该区域进行页面置换时,要在窗口的范围内,从LRU位置遍历直到选中一个干净页面,而后将选中的页面进行置换,若是没有干净页面,那么就选择一个LRU位置进行脏页置换。
CFLRU算法在一定的范围内选择干净页面进行页面置换操作,而工作区的干净页面并不会受到影响和替换,由此保证了一定的缓冲效率,由此提高了系统的运行效率。但CF的窗口大小是预先设定的。在无法确定应用的状况下,无法动态确定窗口的大小,致使CFLRU算法无法在不同的应用下都提升I/O的性能。并且CFLRU算法仅仅考虑数据的新近性,并未考虑数据页面的访问频率,替换掉访问频率较高的页面将对后续的持续访问造成影响。
(二)LRU-WSR算法
文献中所提出的另外一种缓冲置换算法就是LRU-WSR算法。这种算法考虑了数据页面的访问频率,通过引入CFLRU与二次选择算法结合的冷检测算法思想,新近的脏页并不会及时被替换,而是通过暂时不替换来减少Flash存储读取和写入的次数,从而也有效防止了对后续的访问造成一定的影响。为了确认冷脏页,在缓冲的链表中的页面都加上了冷标志。LRU-WSR算法先从LRU位置中选择一个页面作为替换的候选页面,若是这个选择的页面是干净页,那么并不查看其是否具有冷标志就将其替换,若是选中的候选页面是脏页,则应对其是否具有冷标志,若是具有冷标志,则使用这个脏页进行替换,若是未被设置冷标志,那么则将页面移动到LRU中的MRU位置,同时将页面设置冷标志。同时从LRU中选择一个候选页面进行反复循环判断。冷标志在页面再次引用后将被删除,同时页面也将移动到MRU位置上。
由LRU-WSR算法未定义窗口概念,由此并不会一味使用干净页面置换掉脏页,与CFLRU算法相比较而言具有更高的缓冲命中率,同时也考虑了访问的频率。干净页面与冷脏页面若是刚好位于LRU位置则会被直接替换掉,同时给予了置换开销最大的热脏页两次替换容许,实现了页面替换的延迟,从而有效提高了Flash存储的整体的存储性能,但LRU-WSR算法置换粒度范围不大,仅仅对脏页访问频率进行了计算而不对干净页进行划分,由于置换的冷脏页基本上没有置换开销,由此也必会对缓冲的命中率具有较大的影响,由此若是没有进行快速的替换将对LRU-WSR算法的效果产生影响。
面向Flash存储的普适性页面置换算法仅仅关注Flash存储的读写以及擦除操作过程中的开销不对称性特征,这与专门性页面置换算法相比具有很大程度的区别。 三、专门性页面置换算法
(一)FAB算法
FAB算法是针对PMP的,FAB算法属于专门性的页面置换算法,与普适性算法具有较大的不同,FAB算法并不选择单个页面作为置换的对象,而是以擦写块作为替换候选的对象,通过将处于同样擦写块的缓冲页分类为一组,再将这些分类的组按照LRU链表的形式进行组织起来,在Flash存储的读写访问过程中,所命中的页面将从LRU链表移动到MRU位置,若是空间不足,那么就选择最大页面数的组,若是具有多个组包含同样的页面数则使用LRU策略选择一个组,而后将脏页写到存储中,并将请求的数据填充到新的页面组或者新的页面当中,实现了页面的置换。
大部分的PMP数据格式大多为连续的多媒体资源,由此Flash存储块中的页有两种情况:空闲的页或者连续的有效资源,FAB算法正是针对此种应用环境,Flash存储中以块为擦除单位,只有当整体块中的数据都无效才将被擦除,若是部分数据有效部分数据无效,则将有效数据移动到同一块中,擦除掉无效数据。
(二)CRAW-C算法
CRAW-C算法是在基于Flash移动嵌入系统中实现应用。这些移动嵌入系统具有使用一般的文件系统实现数据的存储,同时还使用了压缩文件系统实现系统文件的存储。系统文件是首先固化在存储当中的。为了节约移动设备的空间由此进行了压缩存放,且将系统文件存放在可读区域防止损坏,若是在实际运行中,要将这些系统文件首先解压后才能使用,由此占据了一定的存储空间,对存储性能造成了一定损失。由此通过CRAW-C算法,实现了此种应用算法环境下的页面置换,不仅考虑到了解压压缩文件到的页面开销,同时也考虑到了Flash存储操作中的非对称性。
CRAW-C算法将内存分为读、写以及压缩读三个区域,根据实际的页面访问需要实现了对三种操作开销适时的调整和改变。初始区域的大小按照访问量进行按照比例划分,划分好区域后应建立一个ghost队列,保存替换下来的页面元数据,运用这些队列实现了估计访问模式。而当缓冲区域没有空闲页面,那么则通过判断当前区域大小与理想区域的区别,选择区别较大的区域进行替换,通过判断这个页面在最近的时间内是否被访问,同时也是使用标记进行区分,访问过的标记为1,在缓冲页面所形成的环状链表中进行判断,寻找头部标志为0的页面进行替换,同时在搜寻过程中清零页面标志为1的页面,在寻找到了标志为0的页面后将头部移到当年置换页面的后面位置,尾部移到当前置换页面的位置,而后再进行搜寻选择和替换的过程。
与普适性算法不同,面向应用的专门性页面置换算法考虑到了Flash存储中的不对称读写操作访问时间,同时也针对了应用进行了专门的设计,对Flash存储中的特定的信息进行了开发,从而最大限度提升了系统中的存储性能。
参考文献:
[1]刘锐,李盘林,李秉智.一种适用于大容量Flash存储系统的管理方案[J].计算机应用研究.2006(02)
[2]朱知博.基于NAND FLASH的高速大容量存储系统设计[J].现代电子技术,2011,(08)
[3]刘瑞,黄鲁,陈楠. 基于Flash的高速大容量固态存储系统设计[J].测控技术,2009,(04)
[4]杨修国.关于嵌入式系统中的Flash存储管理的综述[J].科学咨询(决策管理),2008(04)
[5]李树全,吴跃,陈志飞.SAN存储虚拟化研究[J].微电子学与计算机,2009(01)
[6]何晓凤.网络视频监控(NVR)存储技术的分析及其应用[J].中国科技信息,2011,(02)
[7]刘福岩,尤晋元.存储系统的层次性与进程数据存储模型[J].计算机研究与发展,2000(11)
[8]何剑锋,李大晖,李祥.基于ARM嵌入式μClinux下Nand-Flash的应用设计[J].自动化与仪表,2009,(03)
关键词:Flash存储;页面置换;算法
中图分类号:TP333 文献标识码:A 文章编号:1007-9599 (2012) 13-0000-02
随着Flash存储容量的逐渐加大,当前单片可达到32G-64G的内存容量,并且随着Flash技术的发展成本也逐渐下降,基于Flash存储的设备也得到了广泛的应用,性能较为稳定的Flash设备具有无寻道延迟、读写访问迅速以及低功耗、抗震性能较好且安全稳定性较高等特征,因此Flash具有良好的发展趋势。当前,基于Flash存储设备在移动设备上得到了有效的应用。在实际的应用过程中,还应充分考虑其在传统的操作系统上的优化是否合理。相对于磁盘的读写而言,Flash的存储涉及到读写以及擦除操作,读写以页数为单位,而擦除则是以块为单位,页面是Flash存储所使用的最小单位,每一个块中包含了多个页面。由于Flash方式没有寻道的时间,在覆盖存储之前必须进行擦除操作,致使Flash存储的读写操作的性能开销具有较大的不对称。由此要重新考虑操作策略,满足Flash存储系统的性能需求。
一、Flash存储概述
就理论上而言,Flash存储具有NOR以及NAND两种存储类型。NOR类型的Flash存储机制是支持每位上的随机访问,主要实现计算机代码的存储,而NAND的Flash的存储机制则用于存储高密度的数据形式,由于其读写的访问形式是通过扇区的单元级别进行访问的。当前电子市场上的多数SSD都是以NAND为存储基础的。就NAND的Flash存储机制而言,具有两种形式:SLC(Single level cell)和MLC(Multi level cell)。MLC的存储容量相对而言较大,由此其操作的时延也将更大,其运行的成本也相对较高。当前已有将MLC以及SLC结合起来,构成新型的Flash的存储方式研究。
如上所述,Flash的存储方式包括读写以及擦除三种操作形式,而Flash的存储单元所能进行的擦除次数是有限的,一般在十万到百万次之间,为了提高Flash存储单元的使用时间,必须是实际的使用过程中,使擦除的操作尽量分布在每一个存储块上,由此Flash存储的负载损耗以及垃圾回收也将是一个重要的问题。作为很重要的存储介质,Flash存储虽然与磁盘的存储介质有了一定的结合,但其依旧具有较高的成本。
二、普适性页面置换算法
(一)CFLRU系列算法
CFLRU是新提出的页面置换算法,CFLRU算法是通过在LRU链表中保存页面数据,但在保存过程中,将数据链表分为了工作区域以及CF区域。CF区域实际上也可定义为干净优先区,这个区域也是进行页面置换的区域。这个区域的大小是以包括的页面数目以及窗口的大小为标准进行衡量的。工作区域包括当前所使用的页面,干净页都存在于CF区,由此CF区域具有大量的缓冲数据。在该区域进行页面置换时,要在窗口的范围内,从LRU位置遍历直到选中一个干净页面,而后将选中的页面进行置换,若是没有干净页面,那么就选择一个LRU位置进行脏页置换。
CFLRU算法在一定的范围内选择干净页面进行页面置换操作,而工作区的干净页面并不会受到影响和替换,由此保证了一定的缓冲效率,由此提高了系统的运行效率。但CF的窗口大小是预先设定的。在无法确定应用的状况下,无法动态确定窗口的大小,致使CFLRU算法无法在不同的应用下都提升I/O的性能。并且CFLRU算法仅仅考虑数据的新近性,并未考虑数据页面的访问频率,替换掉访问频率较高的页面将对后续的持续访问造成影响。
(二)LRU-WSR算法
文献中所提出的另外一种缓冲置换算法就是LRU-WSR算法。这种算法考虑了数据页面的访问频率,通过引入CFLRU与二次选择算法结合的冷检测算法思想,新近的脏页并不会及时被替换,而是通过暂时不替换来减少Flash存储读取和写入的次数,从而也有效防止了对后续的访问造成一定的影响。为了确认冷脏页,在缓冲的链表中的页面都加上了冷标志。LRU-WSR算法先从LRU位置中选择一个页面作为替换的候选页面,若是这个选择的页面是干净页,那么并不查看其是否具有冷标志就将其替换,若是选中的候选页面是脏页,则应对其是否具有冷标志,若是具有冷标志,则使用这个脏页进行替换,若是未被设置冷标志,那么则将页面移动到LRU中的MRU位置,同时将页面设置冷标志。同时从LRU中选择一个候选页面进行反复循环判断。冷标志在页面再次引用后将被删除,同时页面也将移动到MRU位置上。
由LRU-WSR算法未定义窗口概念,由此并不会一味使用干净页面置换掉脏页,与CFLRU算法相比较而言具有更高的缓冲命中率,同时也考虑了访问的频率。干净页面与冷脏页面若是刚好位于LRU位置则会被直接替换掉,同时给予了置换开销最大的热脏页两次替换容许,实现了页面替换的延迟,从而有效提高了Flash存储的整体的存储性能,但LRU-WSR算法置换粒度范围不大,仅仅对脏页访问频率进行了计算而不对干净页进行划分,由于置换的冷脏页基本上没有置换开销,由此也必会对缓冲的命中率具有较大的影响,由此若是没有进行快速的替换将对LRU-WSR算法的效果产生影响。
面向Flash存储的普适性页面置换算法仅仅关注Flash存储的读写以及擦除操作过程中的开销不对称性特征,这与专门性页面置换算法相比具有很大程度的区别。 三、专门性页面置换算法
(一)FAB算法
FAB算法是针对PMP的,FAB算法属于专门性的页面置换算法,与普适性算法具有较大的不同,FAB算法并不选择单个页面作为置换的对象,而是以擦写块作为替换候选的对象,通过将处于同样擦写块的缓冲页分类为一组,再将这些分类的组按照LRU链表的形式进行组织起来,在Flash存储的读写访问过程中,所命中的页面将从LRU链表移动到MRU位置,若是空间不足,那么就选择最大页面数的组,若是具有多个组包含同样的页面数则使用LRU策略选择一个组,而后将脏页写到存储中,并将请求的数据填充到新的页面组或者新的页面当中,实现了页面的置换。
大部分的PMP数据格式大多为连续的多媒体资源,由此Flash存储块中的页有两种情况:空闲的页或者连续的有效资源,FAB算法正是针对此种应用环境,Flash存储中以块为擦除单位,只有当整体块中的数据都无效才将被擦除,若是部分数据有效部分数据无效,则将有效数据移动到同一块中,擦除掉无效数据。
(二)CRAW-C算法
CRAW-C算法是在基于Flash移动嵌入系统中实现应用。这些移动嵌入系统具有使用一般的文件系统实现数据的存储,同时还使用了压缩文件系统实现系统文件的存储。系统文件是首先固化在存储当中的。为了节约移动设备的空间由此进行了压缩存放,且将系统文件存放在可读区域防止损坏,若是在实际运行中,要将这些系统文件首先解压后才能使用,由此占据了一定的存储空间,对存储性能造成了一定损失。由此通过CRAW-C算法,实现了此种应用算法环境下的页面置换,不仅考虑到了解压压缩文件到的页面开销,同时也考虑到了Flash存储操作中的非对称性。
CRAW-C算法将内存分为读、写以及压缩读三个区域,根据实际的页面访问需要实现了对三种操作开销适时的调整和改变。初始区域的大小按照访问量进行按照比例划分,划分好区域后应建立一个ghost队列,保存替换下来的页面元数据,运用这些队列实现了估计访问模式。而当缓冲区域没有空闲页面,那么则通过判断当前区域大小与理想区域的区别,选择区别较大的区域进行替换,通过判断这个页面在最近的时间内是否被访问,同时也是使用标记进行区分,访问过的标记为1,在缓冲页面所形成的环状链表中进行判断,寻找头部标志为0的页面进行替换,同时在搜寻过程中清零页面标志为1的页面,在寻找到了标志为0的页面后将头部移到当年置换页面的后面位置,尾部移到当前置换页面的位置,而后再进行搜寻选择和替换的过程。
与普适性算法不同,面向应用的专门性页面置换算法考虑到了Flash存储中的不对称读写操作访问时间,同时也针对了应用进行了专门的设计,对Flash存储中的特定的信息进行了开发,从而最大限度提升了系统中的存储性能。
参考文献:
[1]刘锐,李盘林,李秉智.一种适用于大容量Flash存储系统的管理方案[J].计算机应用研究.2006(02)
[2]朱知博.基于NAND FLASH的高速大容量存储系统设计[J].现代电子技术,2011,(08)
[3]刘瑞,黄鲁,陈楠. 基于Flash的高速大容量固态存储系统设计[J].测控技术,2009,(04)
[4]杨修国.关于嵌入式系统中的Flash存储管理的综述[J].科学咨询(决策管理),2008(04)
[5]李树全,吴跃,陈志飞.SAN存储虚拟化研究[J].微电子学与计算机,2009(01)
[6]何晓凤.网络视频监控(NVR)存储技术的分析及其应用[J].中国科技信息,2011,(02)
[7]刘福岩,尤晋元.存储系统的层次性与进程数据存储模型[J].计算机研究与发展,2000(11)
[8]何剑锋,李大晖,李祥.基于ARM嵌入式μClinux下Nand-Flash的应用设计[J].自动化与仪表,2009,(03)