摘 要

传统的磁盘存储器主要是机械硬盘，机械硬盘的寿命主要由工作时间决定，其磁盘的擦除次数对寿命的影响不大，故传统的磁盘管理算法不用考虑磁盘的擦除次数，但是固态硬盘的寿命受磁盘擦除次数的影响，故传统的磁盘管理算法不能直接搬移到固态盘管理算法上，需要重新设计。目前常用的方法是给固态硬盘加一层缓存，这样可以增大数据吞吐量，降低响应时延，减少因写请求导致的擦除操作，既提高了存储器的性能又延长了寿命。其中缓存算法主要采用了最近最少使用算法。通过建模仿真，定量分析缓存算法对固态盘性能和寿命的影响发现，随着缓存的增大，固态盘的擦除次数减少、单位时间数据吞吐量增大、响应时间减少，故缓存有效提高固态盘的性能和延长固态盘的寿命。

关键词：固态硬盘；缓存算法；寿命；性能

Abstract

The traditional disk storage is mainly a mechanical hard disk. The life of the mechanical hard disk is determined by the working time. The disk erasure count has little effect on its life. Therefore, the traditional disk management algorithm doesn’t attach importance to the disk erasure count. However, the erasure affects the life of solid state disk greatly. Therefore, the traditional disk management algorithms cannot be directly applied to the SSD management algorithm and need to be redesigned. Currently, a commonly used method is to add a layer of cache to the solid state disk, which can increase the data throughput, reduce the response delay, and reduce the erase operation caused by the write request, which not only improves the performance of the flash but also prolongs the its life. The cache algorithm mainly uses the least recently used algorithm. By modeling and simulating, quantitative analysis of the impact of the cache algorithm on the performance and life span of the solid state disk found that with the increase of the cache, the erasing frequency of the solid state disk is reduced, the throughput per unit time of data is increased, and the response time is reduced. Therefore, the cache has effectively increased solid state disk performance and extended SSD’s life.

Keywords: solid state disk; cache algorithm; lifetime; performance

目 录

摘 要 1

Abstract 2

第1章 绪论 1

1.1背景介绍 1

1.2固态盘的特性 2

1.3主流的缓存技术 3

1.3.1最佳置换算法（Optimal） 3

1.3.2先进先出页面置换算法（FIFO） 4

1.3.3最近最久未使用置换算法（LRU） 5

1.4国内外研究现状 6

1.5研究意义和内容 6

第2章 缓存算法的设计 8

2.1实际场景的需求分析 8

2.2内存的页面置换算法的设计 9

2.3缓存的读写模块设计 10

2.4本章小结 11

第3章 缓存算法的实现 13

3.1请求数据的结构 13

3.2内存的页面置换算法的实现 13

3.3闪存读写模块的实现 14

3.3.1 4K对齐的实现 14

3.3.2 缓存页的拼接 14

3.3.3 缓存页与闪存的数据一致性 15

3.4本章小结 15

第4章 缓存算法的性能测试与分析 16

4.1测试平台 16

4.2测试数据集来源 16

4.3性能测试 16

4.4测试结果分析 18

4.5本章小结 18

第5章 总结和展望 19

5.1全文总结 19

5.2未来的展望 19

参考文献 20

致谢 21

第1章 绪论

1.1背景介绍

目前，人们为了平衡存储设备的成本和性能，将存储器的层次结构划分为寄存器、高速缓存、主存、磁盘缓存、磁盘、可移动介质，如图1.1所示，从下到上速度越来越快，价格越来越高^[1]。其中，寄存器速度最快、成本最高，是存储器中非常宝贵的资源，一般直接与中央处理器（CPU）交换数据。高速缓存容量远远大于寄存器，却比主存小两到三个数量级。主存访问速度低于寄存器和高速缓存，程序首先从磁盘中读出在写到主存中，CPU才能执行。由于程序执行具有局部性原理（局部性原理分为空间局部性和时间局部性，由于程序主要由顺序语句、条件语句和循环语句组成，程序执行的过程中，相邻两步之间寻址间隔相差很小，因此程序在较短的时间内，只会在主存某一小部分执行，因此，空间局部性是指程序访问某一存储单元后有很大概率再次访问这个存储单元，时间局部性是指程序的某个指令在某一个时间内被执行，在后面的时间内有很大概率被再次执行），会将一些访问次数较高的程序段提前放到高速缓存中，有效提高存储器的整体性能^[1]。磁盘的容量大、成本低，广泛应用于数据量较大、访问次数较少的应用场景。但是，随着物联网、大数据、人工智能的发展，人类社会产生的数据会越来越多，数据的急剧增加对存储器的容量和性能提出了更高的要求，现有的存储设备应付这些数据的冲击越来越捉襟见肘，计算机处理器的发展速度远远快于存储器，导致存储器的性能成为计算机系统整体性能的瓶颈。为此，人们不得不研究新的介质制作存储器。

近几年，固态硬盘作为一种新的存储设备进入人们的视野，同时，由于固态硬盘具有优越的读写性能和低功耗的节能特性越来越受到人们的欢迎。但是，相对机械硬盘来说，固态硬盘的成本高，并且由于固态硬盘不能本地更新，因此，在进行写操作时，需要将原有的物理块进行擦除，而固态硬盘的擦除次数有限，若对某一物理块进行频繁擦除操作，很有可能导致物理块达到极限而过早失效，此后这个物理块读写操作将会受到影响。凡此种种的问题导致固态硬盘很难像机械硬盘那样普及，因此将缓存技术引入固态盘控制器算法中将有效控制固态盘物理块擦除的次数，同时缓存的预取技术（由于程序执行具有局部性原理，主存会将经常访问的信息复制到高速缓存中存放）能够加快固态硬盘的读写速度。

1.2固态盘的特性

目前固态盘的存储介质主要是闪存，闪存根据数字电路的特征分为NOR Flash和NAND Flash两种，NOR Flash由Intel于1988年提出，NAND Flash由Toshiba公司于1989年提出，在读性能上，NOR Flash读速度稍快于NAND Flash，而在写性能上，NAND Flash写速度远快于NOR FLASH，并且擦除操作所需时间，NAND Flash需要4ms，而NOR Flash需要5s，NAND Flash擦除操作速度比NOR Flash快一个数量级，因此，NAND Flash整体性能比NOR Flash好^[2]。目前市场上NAND Flash在闪存中占比最大。闪存芯片是一种电可擦写和可编程的只读的非易失性半导体介质，存储信息的单元是浮栅场效应管，通过设定阈值判定高低电平来存储信息。根据存储单元存放信息的位数，闪存可以分为SLC，MLC，TLC。其中，SLC(Single-Level Cell)一个存储器单元可以存放1bit数据，即存放1和0电平,速度快，寿命长，可以擦出10万次，但是价格是MLC的三倍。MLC (Multi-Level Cell)一个存储器单元可以存放2bit数据，即存放11，10，01，00 四种类型的电平，寿命、速度和价格均一般，擦除次数约为1000到3000次。TLC (Trinary-Level Cell)一个存储单元存放3bit数据，即存放111，110，101，100，011，010，001，000 八种类型的电平，速度慢寿命短但是价格低廉，擦除次数约为1000次。目前企业级存储系统优先选择SLC，而中低端市场选择MLC和TLC^[2-3]。

从组织结构上看，闪存有五个层次组成，分别为芯片（chip）、晶圆（die）、分组（plane）、块（block）、页（page）^[4-5]。芯片（chip）存在闪存结构的最外层，外围电路通过地址总线和数据总线与闪存进行命令和数据的交流。晶圆(plane)处于闪存的第二层，主要与高级命令有关。分组（plane）处于闪存的中间层，像三星、美光等闪存芯片会在这一层增加一个数据寄存器，以提高存储器的读写性能。块（block）是擦除的基本单位，一个物理块有多个页（page）组成。页（page）是读写的基本单位。闪存具有写前擦除的特性并且擦除的次数有限。

1.3主流的缓存技术

缓存算法根据页的命中率进行页的换入换出以减少请求的响应时间。缓存的功能有两种，第一种缓存预取，由于程序执行的局部性原理，当一个指令执行后，在未来的一个很短的时间内，这个指令附近的其它指令有较大的概率会被执行（时间局部性），当访问某一存储单元后，在未来的一个很短的时间内，这个存储单元附近的其它存储单元也会有较大概率被访问（空间局部性），因此，将执行过指令的附近一簇或几簇指令和访问过存储单元的附近一簇或几簇存储单元提前读取到主存中，减少请求的响应时间。第二种缓存的写入，当系统接收到磁盘驱动器发送的写请求信息时，并不会立马将缓存中的数据写入磁盘，而是给系统一个数据写入完毕的应答，同时将数据暂时存储在缓存中，等在数据总线空闲的时候，将缓存中的数据一次写入磁盘，这样既提高了系统数据总线的使用率又避免了短时间大量数据给数据总线带来冲击和压力。传输缓存算法分为单级缓存和多级缓存。单级缓存通过统计页的使用频率或使用时间决定将一些使用频率高的页提前调入缓存，而将使用频率低的页调出缓存。单级缓存算法依据的标准单一，因此传统的单级缓存算法一般在一个应用场景表现出的性能非常优异，但是在其它场景表现的性能比较糟糕。而多级缓存算法应用场景比较多，并且能够存储大量缓存数据。人们经常在主存和磁盘之间增加一个固态盘作为二级缓存，当主存连续读取较大的文件时，主存中缓存的数据会被污染，当下次访问缓存中预取的命令和数据时，将大概率不能命中，需要重新到磁盘中读取指令和数据，这样将会失去缓存预取的作用，增加请求的响应时间，降低存储系统的读写性能，而当存储系统中存在二级缓存时，可以将主存中的数据换出到二级缓存中，当访问未命中时，可以在二级缓存命中。一般来说，一级缓存的命中率为80%，只有20%的概率需要在二级缓存中读取数据，因此，多级缓存有利于提高系统的读写性能和降低请求的响应时间^[6-12]。

缓存的效率和性能取决于系统采用的页面置换算法，一个好的页面置换算法应该在程序执行过程中页面的换入和换出次数最少。目前，传统的单级缓存中页面置换算法主要有最佳置换算法（Optimal）、最近最久未使用置换算法（LRU）、Clock置换算法、最少使用置换算法（LFU）和页面缓冲算法（PBA）^[1][13]。

1.3.1最佳置换算法（Optimal）

最佳置换算法采取的思想是根据物理页未来请求的时间和频率决定当前物理页的调入和调出。理论上，最佳置换算法效率最高，物理页换入换出的次数最低，但是这个算法物理上是不可实现的，因为无法准确预测未来的请求调用的物理页号。但是最佳置换算法可以确定页面置换算法的极限值，具有一定的理论指导价值。

接下来举一个例子说明最佳置换算法的工作原理，页面调入调出次序如表1.1所示。假设系统为某一进程分配三个缓存页，请求的页面号引用串为a，b，c，d，b，e，c，b，a。进程在开始运行的时候将a，b，c三个物理页调入缓存页1、缓存页2、缓存页3中，接下来下发请求页面号为d，未命中，因此需要从磁盘中调取页面号为d的物理页，当前缓存页中，a在第9次访问，b在第5次访问，c在第7次访问，a因为很久才会再次访问，因此将a所在的缓存页调出写入磁盘，然后将d调入写入主存。以此类推，在第6次请求到来时，因为物理页d在后续的请求中不会再被访问，因此选择将物理页d调出缓存。在第9次请求到来时，由于请求序列即将结束，因此选择三个缓存页中任何一个缓存页调出即可，此处例子中选择调出缓存页1中的物理页e。系统在响应这一串请求序列时，调页次数为6次，缓存命中次数为3次，未命中次数为6次。

表1.1 最佳置换算法缓存调入调出实例

1.3.2先进先出页面置换算法（FIFO）

先进先出页面置换算法的思想是，选择一个容量与缓存页数相同的队列，将请求的页面号存入队列中，当队列满的时，将队首页调出，调入的也存在队尾。先进先出算法的本质是将常驻缓存的物理页调出，这个算法原理简单，但是置换的效果不是很好，并且不能保证后面即将访问的物理页不会在本次被调出。但是先进先出页面置换算法为研究其它的新的页面置换算法提供了思路。

为了更好的理解先进先出页面置换算法的工作原理，接下来举一个例子加以说明，页面调入调出次序如表1.2所示。假设系统为某一进程分配三个缓存页，请求的页面号引用串为a，b，c，d，b，e，c，b，a。进程在开始运行的时候将a，b，c三个物理页调入缓存页1、缓存页2、缓存页3中，接下来下发请求页面号为d，未命中，因此需要从磁盘中调取页面号为d的物理页，当前缓存队列中处在队尾的是物理页a，因此，选择调出物理页a，调入的物理页d存储在缓存队列的队首。以此类推，在第6次请求的时候，调出物理页b，调入物理页e，第8次请求的时候，调出物理页c，调入物理页b，第9次请求的时候，调出物理页d，调出物理页a。系统在响应这一串请求物理页面号时，调页次数7次，缓存命中次数2次，缓存未命中次数7次。

表1.2 先进先出页面置换算法缓存调入调出实例

1.3.3最近最久未使用置换算法（LRU）

先进先出页面置换算法是根据页面调入缓存的时间来决定调出的物理页，但是物理页调入的时间并不能反映物理页使用频率，因此，先进先出页面置换算法在页面置换算法中表现的性能比较糟糕。最佳置换算法是根据当前缓存中物理页在未来使用的时间和频率进行决策当前缓存中调出，但是这个算法是物理不可实现的，因为请求未下发，无法对未来的请求进行预测。而最近最久未使用置换算法很好地克服了上述缺点。最近最久未使用置换算法的思想是，根据缓存中物理页在过去时间内使用的频率和次数，来预测未来物理页使用的频率和次数，进而选择使用频率最低的物理页进行调出，因为程序具有局部性原理，过去物理页使用的频率对未来物理页使用频率的预测具有一定的科学性。

下面将结合一个具体的请求序列对最近最久未使用置换算法进行详细阐述，页面调入调出次序如表3.3所示。请求的物理页面号是a，b，c，d，b，e，c，b，a。进程在开始运行的时候将物理页a，b，c调入缓存页1、缓存页2、缓存页3中。当第4个请求到来是，由于物理页a最久未使用，因此，将物理页a调出，物理页d调入，以此类推，第6个请求到来时候，物理页c最久未使用，所以调出物理页c，调入物理页e，第7次请求和第9次请求可以按照相同的方法进行确定调入调出的物理页。系统在响应这一串请求序列时，调页次数是7次，缓存命中次数是2次，未命中次数是7次。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：