一种自适应的s-fc八景管理算法.docxVIP

一种自适应的s-fc八景管理算法 1 存储的缓冲置换策略 基于这种存储容量的存储容量在移动设备上广泛传播，具有低延迟、低能耗、轻巧清洁、高抗震性等特点。随着存款容量的增加和价格的降低，其应用逐渐扩展到个人计算机和企业服务器市场。在过去几年中，sd存储容量的数量至少在2012年。目前，所有应用程序都把存盘驱动器视为一个设备，并使用与磁盘相同的访问接口，但这两个硬盘驱动器的u型功能有很大不同。存盘驱动器的随机读速度远快于其随机读写速度。在一些应用中，数据库服务器不能基于存储功能来设计合适的数据结构和算法，因此很难计算性能。 缓冲区是现代计算机最基本的组成部分之一.它在存储系统、数据库、网络服务器、文件系统以及操作系统中都有广泛的应用.缓冲区置换算法的任何进展都会影响现代计算机的整体性能.假设用磁盘做辅存且读写操作的时间延迟相同,那么对于给定大小的缓冲区,现存的缓冲区置换算法的目标就是最小化缓冲区的缺页率.当缓冲区已满并且请求的数据页不在缓冲区中时,缓冲区置换算法首先从当前缓冲区选择一个用于置换的数据页,如果所选的数据页是脏页(其内容被修改过),就必须将该页的内容写回硬盘,然后才能将请求的数据页读入缓冲区,以保证数据的一致性.这种操作可能会成为系统性能的瓶颈,这是因为请求页的线程或进程必须等待写操作的完成.早在20年前,Effelsberg等已经认识到缓冲区中数据页的读写状态是影响置换策略的重要因素,由于闪存硬盘有望替代磁盘成为新一代的数据存储设备,并且闪存硬盘的读写代价存在不对称性问题,在设计置换策略时更应考虑读写状态的差异性. 针对闪存读写操作的不对称性问题,近几年研究者已经提出了几种适用于闪存的缓冲区置换策略.然而,这些置换策略在实际中存在以下问题: (1) 适用的闪存硬盘类型有限 已有的基于闪存的缓冲区置换算法的基本假设是闪存的随机读代价相对于随机写代价来说可忽略不计,因此这些缓冲区置换策略都是通过无条件先置换只读页来减少随机写操作的次数,从而提高系统的性能.然而,如图1所示,该假设和实际情况并不相符,即随机读代价和随机写代价相比,并非在所有情况下都可以被无条件忽略.尽管所有的闪存设备都表现出较快的随机读速度和较慢的随机写速度,但对于不同的闪存设备而言,读写代价的比例差别很大,显然在不考虑只读页的操作代价和访问频率的情况下就无条件首先置换只读页是不合理的. (2) 多线程处理能力不足1 已有的基于闪存的缓冲区置换策略都是基于LRU置换策略进行改进,LRU的优势在于它实现简单,操作代价低,但LRU也有自身的局限性:① 每次命中的数据页必须移动到最近使用(MRU)的位置.实际中多个线程可能都试图移动各自的数据页到MRU位置,而MRU位置通过锁保护来保证一致性和正确性.由于所有命中操作都在等待该操作的完成,就会引起大量锁争用的问题.在高性能和高吞吐量环境中,例如虚存、数据库、文件系统和存储控制器中,这种情况是不可接受的. ② LRU没考虑数据页的“访问频率”.和LRU对应,CLOCK算法克服了LRU算法的上述缺点.通过将数据页组织成时钟形式的环形缓冲区,CLOCK算法无需在每次命中数据页后移动数据页的位置,因此不会出现锁争用的问题.因此,CLOCK算法在实际系统中,如DB2、SQL Server、Postgresql等,得到了广泛应用. 针对现有基于闪存的缓冲区置换算法存在的问题,本文提出一种基于闪存的clock算法FClock来解决以上问题.FClock为每个数据页维护一个“访问位”并将缓冲区中的数据页组织成两个时钟形式的环形结构CC(Clean Clock)和DC(Dirty Clock),分别用于管理未修改的数据页和修改过的数据页.当数据页被初次读入缓冲区时,它的访问位被置为0.当命中某个数据页时,将其访问位加1.当需要选择一个置换页时,FClock并非直接置换出未修改页,而是首先根据启发式规则判断被置换的数据页是已修改页还是未修改页,然后再从DC或者CC中找访问位是0的数据页进行置换,以此来进行自适应的调整.最后,受文献的“局部性过滤”原则的启发,FClock使用基于平均命中距离的技术来消除短期频繁访问而长期不访问的数据页长时间驻留内存的问题. 2 背景和相关工作 2.1 dd型存储芯片的操作 一般来说,有两种不同类型的闪存芯片,分别是NOR型闪存和NAND型闪存.NOR型闪存芯片和EPROM以及SRAM一样,有专用的地址和数据总线;而NAND闪存芯片无专用的地址和数据总线,用一个IO接口来控制输入输出.NOR型闪存芯片可用来替换可编程的只读存储器(PROM)和可擦除的PROM(EPROM)来进行有效的随机存取;NAND型闪存芯片由于其存储容量较高,主要用来存储数据.闪存硬盘(SSD)中使用的通常是NAND型芯片. NA