《基于nand的使用压缩缓存策略的交换系统的设计与实现》由会员分享，可在线阅读，更多相关《基于nand的使用压缩缓存策略的交换系统的设计与实现（59页珍藏版）》请在金锄头文库上搜索。
1、上海交通大学 硕士学位论文 基于NAND的使用压缩缓存策略的交换系统的设计与实现 姓名：顾锋磊 申请学位级别：硕士 专业：软件工程 指导教师：步丰林 20080101 上海交通大学硕士学位论文 第 5 页 摘要 作为磁盘的替代品，NAND 闪存被广泛应用于便携式设备。但 在大部分情况下， NAND 闪存只是被作为大容量数据存储器使用。 随着智能手机、掌上电脑等高端嵌入式设备对内存的占用需求的 快速增大，将会有越来越多的研究关注如何扩大嵌入式设备的可 用内存空间，其中一个研究方向就是在 NAND 闪存上建立交换系 统。 交换系统被应用于几乎所有的现代操作系统中。 传统的交换系 统都是在磁盘分区上
2、建立独立的交换分区，使得系统获得更大的 内存空间却不损失执行效率。相比磁盘设备，NAND 闪存具有高 速、低能耗、抗震、稳定等优良的特性，可以认为在 NAND 上建 立交换系统是现实和有意义的。 虽然 NAND 相比于磁盘有着各种优良的特性，但是 NAND 有 着致命的弱点，即 NAND 具有擦写次数限制。对某块擦写次数超 过限定次数可能损害该块，而面对读写频繁的交换系统，能否使 NAND 避免太早的磨损成为 NAND 交换系统研究的重点。 针对如何减缓NAND的磨损， 本文提出了一个新的基于NAND 的交换系统架构 SNSS（Smart NAND Swap System）。相比于传 统的交换
3、系统，SNSS 的优势在于为交换系统中引入压缩缓存机 制， 并在此基础上创造性的提出两级回收策略和选择性压缩策略， 这些机制和策略的使用， 使得系统对 NAND 的访问次数大为减少。 压缩缓存实际是在内存空间和 NAND 交换分区之间创建了一 个中间层压缩缓存分区。按照 SNSS 的设计，压缩缓存分区 和 NAND 交换分区共享同一个“页槽地址空间”，所有换出页将 先被压缩，然后在这个“页槽地址空间”中分配空间。压缩缓存 分区作为 NAND 交换分区的缓存存在， 以期减少对 NAND 的读写 操作。 针对NAND写操作开销较大的特点， SNSS提出两级回收策略， 即在内存页回收策略上依旧执行传
4、统的 LRU 策略， 而在压缩缓存 分区中执行特殊的回收策略。后者主要根据对 NAND 操作时“重 写”开销较大，“创建新页”开销次之的特点，提出了相应的回 收原则：优先回收“干净”压缩页，其次是“新”压缩页，而尽 量将“脏”压缩页保存在压缩缓存分区中。 上海交通大学硕士学位论文 第 6 页 此外，SNSS 使用选择性压缩策略，即当压缩率并不理想时， 系统将选择不压缩，以节省执行时间。 通过对 SNSS 模型的测试，证明使用压缩缓存策略的 NAND 交换系统，相比传统的做法，在不损耗系统执行效率的条件下， 可以将对 NAND 的写操作次数减少近一半， NAND 的使用寿命可 以增长近一倍。 关
5、键字： 交换系统，NAND，压缩，缓存 上海交通大学硕士学位论文 第 7 页 ABSTRACT Some smart phones and laptop computers now exploit swap system with their second storage media as a cost effective solution to extend limited memory space. The rapid evolving flash memory technology starts to replace the magnetic disks of these compute
6、rs by NAND flash due to its advantageous characteristics such as energy efficiency, access speed and mechanical shock resistance. Although NAND Flash is currently considered as the second mass-storage media, we can imagine that the swap system running over NAND flash will show up in the future. Howe
7、ver, NAND suffers limited lifespan compared with magnetic disks. Blocks of NAND Flash will be destroyed if certain blocks are erased too many times. As a result, our research focuses on how to reduce writing operations on NAND Flash while swapping in and out. This paper presents a new swap system mo
8、del, SNSS (Smart NAND Swap System). And a compressed cache in swap system is introduced, as well as two-level replacement algorithm and adaptive compression, which are intend to reduce access to NAND. A compressed cache is used as middle layer between main memory and NAND swap area. The cache and th
9、e NAND share the same address space of page slots. Each swapped page will be compressed first and then allocated with some page slot, in cache or NAND or maybe both. The two-level replacement algorithm introduced by SNSS is designed to be that pages in RAM are replaced following LRU like tradition,
10、and pages in compressed cache are replaced with a special algorithm which performs “Clean page First, Then New, Dirty Last“ while rewriting on NAND costs too much and creating a new page costs less. Further more, adaptive compression is introduced in SNSS, which is used to avoid compression under lo
11、w compression rate. By simulating the SNSS model, we get the conclusion that SNSS can reduce flash write operations by 50% on average compared with the 上海交通大学硕士学位论文 第 8 页 traditional swap system. As a result, NAND will keep healthy twice longer. Keywords: Swap System, NAND, Compression, Cache 上海交通大学
12、硕士学位论文 第 11 页 插图清单插图清单 图 1 交换分区和交换文件 10 图 2 C.Park1 XIP-NAND 14 图 3 jffs 节点 . 15 图 4 Sangduck 的优先级压缩策略. 20 图 5 基于交换文件的交换系统 22 图 6 传统 FTL(a)与 FASS(b) 22 图 7 使用压缩策略的交换系统 24 图 8 SNSS 系统框架 . 27 图 9 压缩缓存结构 28 图 10 最先匹配原则 29 图 11 碎片回收 29 图 12 FTL 的逻辑页映射表 30 图 13 FTL 连续页空间的空洞 31 图 14 交换文件 32 图 15 CFLRU. 34
13、 图 16 压缩算法的压缩率比较 36 图 17 5.1.1 测试之响应速率 39 图 18 5.1.1 测试之压缩率 39 图 19 5.1.2 测试之运行时间比较 40 图 20 5.1.2 测试之 NAND 占用比较 . 40 图 21 5.1.2 测试之写次数比较 41 图 22 5.2 测试之运行时间比较 41 图 23 5.2 测试之 NAND 占用比较 . 41 图 24 5.2 测试之写次数比较 42 图 25 全缓存模式 42 上海交通大学硕士学位论文 第 12 页 表格清单表格清单 表 1 存储设备的性能比较. 5 表 2 压缩页传递规律 33 表 3 压缩算法资源占用比较
14、 36 第 3 页 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：顾锋磊 日期：2008 年 3 月 18 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构
15、送交论文的复印件和电子版， 允许论文被查阅和借阅。 本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“”） 学位论文作者签名：顾锋磊 指导教师签名：步丰林 日期：2008 年 3 月 18 日 日期：2008 年 3 月 18 日 上海交通大学硕士学位论文 第 1 页 第一章 绪论 1.1 引言 第一章 绪论 1.1 引言 随着消费电子类产品在人们生活中的日益普及，各种产品间的竞争越来 越激烈，多功能、高品质、携带方
16、便且具有较高性价比的电子产品成为产品 开发者的目标。很多具有强大功能的手机、音频播放器、数码相机、车载导 航产品和掌上电脑等产品纷纷涌现，这些产品的竞争促进了生产厂商在各个 层面使用新的技术，其中很重要的一个转变是存储介质的革新。当前越来越 多的功能需求，尤其是多媒体功能，使得原有的存储容量成为了用户体验的 瓶颈； 而且， 3G 时代的到来， 使得移动终端能够获得的数据信息将显著增多， 因此，存储设备在便携式终端设备的开发中占据越来越重要的地位。 相比传统的磁盘、EPROM、NOR Flash 等存储介质，NAND 因其高速、 廉价、 低能耗和大容量等优点而成为目前嵌入式数据存储设备的主流。 NAND Flash 已在多数便携产品中得以使用并作为主要的数据存储器件。 市场调研结 构 IDC 预计，对比 2006 年的销售额为 120 亿美元，2010 年全球闪存销售额 将达到约 200 亿美元。伴随 NAND Flash 市场的迅速增大，围绕 NAND 的研 究与开发进一步深入。 2006 年 32GB
