全程优化的固态硬盘垃圾回收方法

Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ＩＳＳＮ　ｌ０ｏ１．９０８１　２０１７—０５一ｌ０　计算机应用，２０１７，３７（５）：１２５７—１２６２，１２８１　文章编号：１００１－９０８１（２０１７）０５－１２５７－０６　ＣＯＤＥＮ　ＪＹＩＩＤＵ　ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ｃｎ　ＤＯＩ：１０．１１７７２／ｊ．ｉｓｓｎ．１００１—９０８１．２０１７．０５．１２５７　全程优化的固态硬盘垃圾回收方法　方才华　一，刘景宁　一，童薇　，　，高　阳　，雷　霞　，蒋瑜　（１．武汉光电国家实验室（华中科技大学），武汉４３００７４；２．信息存储系统教育部重点实验室（华中科技大学），武汉４３００７４）　（｝通信作者电子邮箱Ｔｏｎｇｗｅｉ＠ｈｕｓｔ．ｅｄｕ．ｃｎ）　摘要：由于ＮＡＮＤ闪存的固有限制，写前擦除和擦除粒度较大，基于ＮＡＮＤ　Ｆｌａｓｈ的固态硬盘（ＳＳＤ）需要执行垃　圾回收以重用失效页。然而垃圾回收带来的高开销会显著降低ＳＳＤ的性能，也会直接影响ＳＳＤ的寿命。特别是对于　频繁使用的有数据碎片的ＳＳＤ，垃圾回收带来的性能下降问题将更为严重，现有的垃圾回收（ＧＣ）算法各自侧重垃圾　回收操作的某个步骤，并没有给出全面考虑各步骤对整体影响的综合方案。针对该问题，在详细剖析垃圾回收过程　的基础上，提出了一种全程优化的垃圾回收方法ＷＰＯ－ＧＣ，在数据初始放置、垃圾回收目标块的选择、有效数据的迁　移、触发回收的时间点以及中断处理方式上，尽可能全面地考虑各步骤对ＳＳＤ正常读写请求和寿命的影响。通过开　源模拟器ＳＳＤｓｉｍ上的ＷＰＯ．ＧＣ的有效性验证表明，同典型ＧＣ算法相比，ＷＰＯ—ＧＣ可以减少ＳＳＤ读请求延迟２０％一　４０％和写请求延迟ｌ７％一４０％。均衡磨损近３Ｏ％。　关键词：闪存；固态盘；垃圾回收；磨损均衡；使用寿命　中图分类号：ＴＰ３３３．３５　文献标志码：Ａ　Ｗｈｏｌｅ　ｐｒｏｃｅｓｓ　ｏｐｔｉｍｉｚｅｄ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｆｏｒ　ｓｏｌｉｄ・ｓｔａｔｅ　ｄｒｉｖｅｓ　ＦＡＮＧ　Ｃａｉｈｕａ　一，ＬＩＵ　Ｊｉｎｇｎｉｎｇ　一，ＴＯＮＧ　Ｗｅｉ　，　，ＧＡＯ　Ｙａｎｇ　一，ＬＥＩ　Ｘｉａ　一，ＪＩＡＮＧ　Ｙｕ　，　（１．Ｗｕｈａｎ　Ｎａｔｉｏｎａｌ　Ｌａｂｏｒａｔｏｒｙｆｏｒ　Ｏｐｔｏｅｌｅｃｔｒｏｎｉｃｓ（Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ），Ｗｕｈａｎ　Ｈｕｂｅｉ　４３００７４，Ｃｈｉａ；ｎ　２．研Ｌａｂｏｒａｔｏｒｙ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｓｔｏｒａｇｅ　Ｓｙｓｔｅｍ　ｏｆＭｉｎ￣ｔｒｙ　ｏｆＥｄｕｃａｔｉｏｎ（Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｆＳｃｉｏｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ），Ｗｕｈａｎ　Ｈｕｂｅｉ　４３００７４，Ｃｈｉａ）ｎ　Ａｂｓｔｒａｃｔ：Ｄｕｅ　ｔｏ　ＮＡＮＤ　ｆｌａｓｈ’ｉｎｈｅｒｅｎｔ　ｒｅｓｔｒｉｃｔｉｏｎｓ　ｌｉｋｅ　ｅｒａｓｅ－ｂｅｆｏｒｅ－ｗｒｉｔｅ　ａｎｄ　ａ　ｌａｒｇｅ　ｅｒａｓｅ　ｕｎｉｔ．ｆｌａｓｈ—ｂａｓｅｄ　Ｓｏｌｉｄ－Ｓｔａｔｅ　Ｄｒｉｖｅｓ（ＳＳＤ）ｄｅｍａｎｄ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｏｐｅｒａｔｉｏｎｓ　ｔｏ　ｒｅｃｌａｉｍ　ｉｎｖａｌｉｄ　ｐｈｙｓｉｃａｌ　ｐａｇｅｓ．Ｈｏｗｅｖｅｒ，ｔｈｅ　ｈｉｇｈ　ｏｖｅｒｈｅａｄ　ｃａｕｓｅｄ　ｂｙ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｓｉｇｎｉｉｆｃａｎｔｌｙ　ｄｅｃｒｅａｓｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ｌｉｆｅｔｉｍｅ　ｏｆ　ＳＳＤ．Ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ｗｉｌｌ　ｂｅ　ｍｏｒｅ　ｓｅｒｉｏｕｓ，ｅｓｐｅｃｉａｌｌｙ　ｗｈｅｎ　ｔｈｅ　ｄａｔａ　ｆｒａｇｍｅｎｔｓ　ｏｆ　ＳＳＤ　ａｒｅ　ｆｒｅｑｕｅｎｔｌｙ　ｕｓｅｄ．Ｅｘｉｓｔｉｎｇ　Ｇａｒｂａｇｅ　Ｃｏｌｌｅｃｔｉｏｎ（ＧＣ）ａｌｇｏｒｉｔｈｍｓ　ｏｎｌｙ　ｆｏｃｕｓ　ｏｎ　ｓｏｍｅ　ｓｔｅｐｓ　ｏｆ　ｔｈｅ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｏｐｅｒａｔｉｏｎ，ａｎｄ　ｎｏｎｅ　ｏｆ　ｔｈｅｍ　ｐｒｏｖｉｄｓ　ａ　ｃｏｍｐｒｅｈｅｎｓｉｖｅ　ｓｏｌｕｔｉｏｎ　ｔｈａｔ　ｔａｋｅｓ　ｉｎｔｏ　ｃｏｎｓｉｄｅｒａｔｉｏｎ　ａｌｌ　ｔｈｅ　ｓｔｅｐｓ　ｏｆ　ｔｈｅ　ＧＣ　ｐｒｏｃｅｓｓ．Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｄｅｔａｉｌｅｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＧＣ　ｐｒｏｃｅｓｓ．ａ　ｗｈｏｌｅ　ｐｒｏｃｅｓｓ　ｏｐｔｉｍｉｚｅｄ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ＷＰＯ－ＧＣ（Ｗｈｏｌｅ　Ｐｒｏｃｅｓｓ　Ｏｐｔｉｍｉｚｅｄ　Ｇａｒｂａｇｅ　Ｃｏｌｌｅｃｔｉｏｎ）ｗａｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｉｎｔｅｇｒａｔｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎｓ　ｏｎ　ｅａｃｈ　ｓｔｅｐ　ｏｆ　ｔｈｅ　ＧＣ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｎｅｇａｔｉｖｅ　ｉｍｐａｃｔ　ｏｎ　ｎｏｒｍａｌ　ｒｅａｄ／ｗｒｉｔｅ　ｒｅｑｕｅｓｔｓ　ａｎｄ　ＳＳＤ’ｌｉｆｅｔｉｍｅ　ａｔ　ｔｈｅ　ｇｒｅａｔｅｓｔ　ｅｘｔｅｎｔ．Ｍｏｒｅｏｖｅｒ，ｔｈｅ　ＷＰＯ—ＧＣ　ｗａｓ　ｉｍｐｌｅｍｅｎｔｅｄ　ｏｎ　ＳＳＤｓｉｍ　ｗｈｉｃｈ　ｉｓ　ａｎ　ｏｐｅｎ　ｓｏｕｒｃｅ　ＳＳＤ　ｓｉｍｕｌａｔｏｒ　ｔｏ　ｅｖａｌｕａｔｅ　ｉｔｓ　ｅｆｉｃｉｅｎｃｙ．Ｔｈｅ　ｅｘｐｅｒｆｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｄｅｃｒｅａｓｅｓ　ｒｅａｄ　Ｉ／Ｏ　ｒｅｓｐｏｎｓｅ　ｔｉｍｅ　ｂｙ　２０％一４０％　ａｎｄ　ｗｒｉｔｅ　Ｉ／Ｏ　ｒｅｓｐｏｎｓｅ　ｔｉｍｅ　ｂｙ　１７％一４０％ｒｅｓｐｅｃｔｉｖｅｌｙ，ａｎｄ　ｂａｌａｎｃｅ　ｗｅａｒ　ｎｅａｒｌｙ　３０％ｔｏ　ｅｘｔｅｎｄ　ｔｈｅ　ｌｉｆｅｔｉｍｅ，ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｙｐｉｃａｌ　ＧＣ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｌａｓｈ　ｍｅｍｏｒｙ；Ｓｏｌｉｄ—Ｓｔａｔｅ　Ｄｒｉｖｅ（ＳＳＤ）；Ｇａｒｂａｇｅ　Ｃｏｌｌｅｃｔｉｏｎ（ＧＣ）；ｗｅａｒ—ｌｅｖｅｌｉｎｇ；ｌｉｆｅｔｉｍｅ　０　引言　近年来，基于ＮＡＮＤ　Ｆｌａｓｈ的固态硬盘（Ｓｏｌｉｄ．Ｓｔａｔｅ　Ｄｒｉｖｅ，　ＳＳＤ）因其性能高、功耗低、抗震性好等诸多优点获得广泛的　Ｉ／Ｏ时，若ＳＳＤ是空盘，其每秒进行读写操作的次数（Ｉｎｐｕｔ／　Ｏｕｔｐｕｔ　Ｏｐｅｒａｔｉｏｎｓ　Ｐｅｒ　Ｓｅｃｏｎｄ，ｌＯＰＳ）能达到２０万次，读、写延　迟分别为１８０　Ｉｘｓ和２０００　ｔｘｓ；但对ＳＳＤ进行数据预埋和碎片　化处理后再进行相同的测试，其ＩＯＰＳ下降到６万次／ｓ，读写　延迟上升了３～７倍，造成这种性能差距的直接原因是ＳＳＤ　内部的垃圾回收（Ｇａｒｂａｇｅ　Ｃｏｌｌｅｃｔｉｏｎ，ＧＣ）操作。当ＳＳＤ中用　于容纳异地更新的预留空间越来越少，就会频繁地触发垃圾　回收，导致正常的读写访问被阻塞。由于垃圾回收需通过块　擦除获得可用页，因此垃圾回收操作的执行频率也会对ＳＳＤ　的寿命造成影响。　应用。由于ＮＡＮＤ闪存异地更新的特点，写更新产生的无效　页需经由垃圾回收操作才能重新成为可用页。ＳＳＤ的垃圾回　收操作涉及到目标块的选择、有效数据的迁移和块的擦除操　作　，因而对ＳＳＤ的读写性能和寿命都有很大的影响。　根据采用｛ｊｏ　对Ｉｎｔｅｌ　ＳＳＤ　ＤＣ　Ｐ３７００固态盘的测试结　果，当执行读写请求大小为４　ＫＢ、读写请求比例为７：３的随机　收稿日期：２０１６・０７－１５；修回日期：２０１６一ｌ１—２５。　基金项目：国家８６３计划项目（２０１５ＡＡ０１６７０１，２０１５ＡＡ０１５３０１）；国家自然科学基金资助项目（６１３０３０４６，６１４０２１８９，６１４７２１５３）。　作者简介：方才华（１９９４一），男，浙江三门人，硕士研究生，主要研究方向：大数据存储、固态存储、数据去重；刘景宁（１９５７一），女，湖北武　汉人，教授，博士，主要研究方向：固态存储、数据挖掘、分布式存储；童薇（１９７７一），女，湖北黄陂人，讲师，博士，主要研究方向：非易失性存储　器、输入／输出虚拟化；高阳（１９９２一），男，湖北广水人，硕士研究生，主要研究方向：大数据存储、键值对存储；雷霞（１９９３一），女，湖北仙桃　人，硕士研究生，主要研究方向：大数据存储、安全删除；蒋瑜（１９９３一），男，江苏常州人，硕士研究生，主要研究方向：固态存储、非易失存储器。　１２５８　计算机应用　第３７卷　全程优化的垃圾回收方法（ｗｈ０ｌｅ　Ｐｒｏｃｅｓｓ　Ｏｐｔｉｍｉｚｅｄ　１）何时触发垃圾回收操作？２）如何选择目标块？３）怎样安　置和迁移数据？　文件系统（ＮＴＦＳ和ＥＸＴ４等）　●　Ｇａｒｂａｇｅ　Ｃｏｌｌｅｃｔｉｏｎ，ＷＰＯ—ＧＣ），从数据初始放置、垃圾回收目标　块的选择、有效数据的迁移位置、触发回收的时间点以及中断　处理方式上，全面优化与垃圾回收方面相关的各个步骤，有效　减少了ＳＳＤ正常读写的响应延迟，同时提升了ＳＳＤ的寿命。　闪存设备　●　闪存转换层　百　面　垃圾回收　ｌ　』　１　背景与动机　１．１　ＳＳＤ的架构　【　、　①　存储设备层　ＳＳＤ主要由ＳＳＤ控制器和闪存芯片构成，如图１所示。　ＳＳＤ中的闪存控制器控制多个通道（Ｃｈａｎｎｅ１），每个通道上挂　因瞥咎　占　．　载多颗闪存芯片（Ｃｈｉｐ）　－６］。如图２所示，闪存芯片由多个　晶圆（Ｄｉｅ）组成，每个晶圆又由多个分组（Ｐｌａｎｅ）组成，每个分　组包含多个块（Ｂｌｏｃｋ）。块是芯片擦除的基本单位，每个块包　含多个页（Ｐａｇｅ），页是芯片读写的基本单位。　Ｆｉｇ．１　Ｏｖｅｒａｌｌ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｏｆ　ＳＳＤ　敝据寄存剁　敝据寄存别　敝据寄存　敝据寄存剁　块０　块０　块０　块０　ｌ　页０　Ｉ　ｌ　页ｏ　ｌ　Ｉ页０　Ｊ　ｌ页０　ｌ　ｌ　Ｉ　Ｉ　；　ｌ　Ｉ　；　Ｉ　ｌ　ｌ　Ｉ页６３　ｌ　Ｉ页６３　ｌ　ｌ页６３　ｌ　Ｊ页６３　ｌ　块２０４７　块２０４７　块２０４７　块２０４７　Ｉ　页０　ｌ　ｌ　页ｏ　ｌ　Ｉ页０　Ｉ　Ｉ页０　ｌ　ｌ　ｌ　Ｉ　　ｌｌ　；　Ｉ　Ｉ　；　ｌ　ｌ页６３　ｌ　ｌ页６３　Ｉ　ｌ页６３　Ｉ　Ｉ页６３　１　分组０　分组１　分组０　分组１　晶圆０　晶圆１　闪存芯片　图２闪存芯片的架构　Ｆｉｇ．２　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｏｆ　ｌｆａｓｈ　ｃｈｉｐ　１．２垃圾回收的机制　闪存芯片具有写前擦除的特性，更新数据时要采用异地　更新方式（旧数据成为无效页）　Ｊ。为保证ＳＳＤ的正常使用，　需要对无效页进行垃圾回收操作，即擦除选定的目标块以供　用户再次使用。由于闪存芯片的读写粒度（页单位）和擦除　粒度（块单位）不同，在擦除一个目标块之前，垃圾回收首先　需要迁移其有效数据页到其他块中。如图３所示，一次完整　的垃圾回收操作包括３个步骤：①选择要回收的目标块；②迁　移有效数据到其他块中；③擦除目标块。在数据迁移时，数据　的源物理页和目的物理页所处的芯片和通道均会被占用，在　随后执行块擦除操作时，虽然不会占用通道资源，但被擦除块　所处的芯片也会被占用。因此在ＳＳＤ内部执行垃圾回收操　作过程中，上层向ＳＳＤ发出的读写请求若要访问垃圾回收占　用的芯片或者通道资源　’　，其响应时间和吞吐率都会受到　较大影响。另外由于闪存芯片擦除次数有限的特性，垃圾回　收的执行频率会直接影响ＳＳＤ的寿命。　在设计垃圾回收算法时通常需要考虑如下几个问题：　’、、　．　一一　图３垃圾回收操作的示意图　Ｆｉｇ．３　Ｓｃｈｅｍａｔｉｃ　ｄｉａｇｒａｍ　ｏｆ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｏｐｅｒａｔｉｏｎ　１．３相关工作　针对上述问题，现有垃圾回收算法提出不同的解决方法。　对于何时触发垃圾回收操作，文献［９］设置了一个表示　ＳＳＤ空闲页比例的固定阈值，当空闲页比例小于该阈值时，触　发垃圾回收。这种方法的缺点在于：当垃圾回收被触发时。系　统中的空闲页比例已经很低，此时容易造成垃圾回收的频繁　执行。为避免垃圾回收的频繁触发，文献［１０］在ＳＳＤ空闲时　根据ＳＳＤ当前的多个状态和统计值，如块擦除次数、页的状　态等，确认是否触发垃圾回收操作。该方法能够让垃圾回收　操作避开正常读写请求，最小化垃圾回收对ＳＳＤ性能的影　响；其缺点在于：针对读写访问密集的应用，垃圾回收操作始　终不能有效进行，此外对ＳＳＤ空闲时间的准确预测也很难实　现。文献［１１］提出的ＧＣ算法允许用户Ｉ／Ｏ请求中断正在执　行的ＧＣ操作，待用户Ｉ／Ｏ请求完成后再恢复执行被中断的　ＧＣ进程，但是针对Ｉ／Ｏ密集型应用，垃圾回收操作可能会被　连续的Ｉ／０请求多次中断，难以及时有效回收ＳＳＤ空间。为　避免垃圾回收的频繁触发，文献［１２］设计了一个两级阈值的　方式，既能充分利用ＳＳＤ的空闲时间进行垃圾回收，从而避　免后期垃圾回收的频繁触发，针对密集型应用，又能设计强制　ＧＣ保证ＳＳＤ的空闲空间。　对于如何选择垃圾回收的目标物理块。贪婪算法选取该　垃圾回收请求对应Ｐｌａｎｅ中无效页最多的块作为回收块。该　算法优点是能够最大限度地减少数据迁移量，提高垃圾回收　的效率；缺点是没有考虑回收块的擦除次数，容易导致块被过　早地擦穿，缩短固态盘的使用寿命。另一方面，基于损耗均衡　的Ｇｃ算法选择最少磨损的块作为回收块　，但会增加Ｇｃ　迁移数据的开销。在ＧＣ过程中同时考虑回收块的无效页比　例和擦除次数常常是一对矛盾，为达到二者的平衡，文献　［１４］利用块的有效页比例和擦除次数计算加权分，来选择合　适的回收块。但是其回收块选择机制是基于特定的Ｆｌａｓｈ文　件系统（Ｆｌａｓｈ　Ｆｉｌｅ　Ｓｙｓｔｅｍ，ＦＦＳ），不具有普遍性。ＷＥＣＯ　（ｗＥａｒ　ＣＯｎｓｃｉｏｕｓ）　ｉｓ］在文献［１４］评分机制的基础上，对评分　公式作了优化并将其扩展到块设备，但是对有大量空闲页的　块，其评分机制不准确，会导致有较多空闲页和无效页的块被　选中回收，这样造成了低下的回收效率。　有效数据迁移的关键在于确定数据迁移安放的位置，一　个好的ＧＣ算法应通过分析迁移数据的温度等特点，重新规　划迁移数据的安放，使相近温度的数据聚集到一块中，提高垃　圾回收的效率。ＷＥＣＯ提出一种数据分离策略，在数据迁移　第５期　方才华等：全程优化的固态硬盘垃圾回收方法　１２５９　过程中，能够分离冷热数据。该方法优点是提高垃圾回收的　效率和保护磨损严重的块，以增加使用寿命；其不足之处在于　冷热数据分离的算法复杂，开销较大。　文献［１６］提出缓存感知的垃圾回收算法，当缓存进行替　换往下写时，考虑下层通道是否进行垃圾回收操作，避免对正　在进行的通道进行分发请求，以此减少响应等待时延，但这　不能从根本上减少垃圾回收带来的影响。　１．４动机　现有的Ｇｃ算法　，都不能很好地解决垃圾回收对正　常读写请求的影响，都是针对垃圾回收的某一个步骤中的问　题作优化，例如只针对垃圾回收的触发条件　或者回收目　标块的选择¨　Ｊ，缺乏对ＧＣ的整体优化改进，更没有针对　数据的访问频率（温度）特点，防患于未然，在数据放置和迁　移时就提前考虑如何减少垃圾回收带来的影响问题。　为了更进一步地减少ＧＣ对用户正常读写请求响应延时　的影响，更好地提升ＳＳＤ的性能和寿命，针对现有ＧＣ算法的　缺陷，深入分析ＧＣ的每一步操作，探讨其优化策略，从而达　到全过程的优化，提出一种全面的ＷＰＯ—ＧＣ策略。ＷＰＯ—ＧＣ　主要工作是在其他研究者的工作上进行优化，包括以下４点：　１）分离放置冷热数据。依据数据访问频度，确认数据冷　热温度，在数据放置时就考虑数据的特点，使温度相近的数据　聚集一起，便于达到全盘整体均衡，提高垃圾回收的效率。　２）建立两级阈值引入一种可中断ＧＣ策略，依据ＳＳＤ当　前的工作状态，控制垃圾回收的触发条件，采用不同的中断方　式处理，进一步减少ＧＣ对ＳＳＤ读写性能的影响。其中提出　中断开放策略，即垃圾回收中的每次有效页迁移结束后开放　系统中断，既可以利用不同请求到来的时问间隔进行垃圾回　收，又可以及时响应用户请求，减少用户读写操作的等待延　时，提高系统的平均响应时间。　３）选择适当的垃圾回收目标块。采用综合考虑块中无　效页所占比例和擦除次数的均衡策略，提高垃圾回收的效　率，延长闪存寿命。　４）在数据迁移时，进一步依据数据冷热程度选择数据的　放置位置，减少垃圾回收中不必要的反复迁移。　２设计和实现　ＷＰＯ—ＧＣ主要目标是减少ＧＣ对用户正常读写延时的影　响，其设计思路是全面考虑与ＧＣ相关的各个方面。并对ＧＣ　每一步骤进行全局优化，以兼顾ＳＳＤ性能和寿命的提升。　ＷＰＯ－ＧＣ主要包括以下部分：１）产生不同优先级的垃圾回收　请求；２）控制垃圾回收的触发条件，允许中断开放策略；　３）平衡性能和寿命的目标块选择；４）通过冷热数据分离提高　垃圾回收效率。　２．１产生垃圾回收请求　目前关于垃圾回收请求响应时机，有不同的研究：文献　［９］通过设置较低的空闲空间阈值来作为触发条件，但这会　导致使用后期垃圾回收的频繁触发，严重影响性能；文献　［１Ｏ］采用在ＳＳＤ空闲时间进行垃圾回收，但是无法准确预测　空闲时间；文献［１１］提出可被Ｉ／０请求中断的ＧＣ算法，但　是这会导致垃圾回收操作被连续到来的Ｉ／０请求多次中断，　难以有效回收ＳＳＤ空间。　ＷＰＯ－ＧＣ根据ＳＳＤ空闲空间的多少，设置两级阈值，赋予　垃圾回收操作不同的紧迫程度，采用文献［１２］提出的方法和　公式，分别是不可中断阈值日和可中断阈值　，用于区分垃圾　回收操作的紧迫级别。当Ｐｌａｎｅ的空闲空间比例　低于不　可中断阈值日时，需立刻执行垃圾回收，因而产生不可中断　垃圾回收请求；当ＦＰ的值在不可中断阈值日和可中断阈值　之间时，产生可中断垃圾回收请求，当ＦＰ高于ｒ时不产生　垃圾回收请求。基于固态盘中每个Ｐｌａｎｅ的状态（空闲页数、　无效页数、有效页数），采用式（１）和（２）动态计算得出Ｈ和　的值。　日＝ａＥ＋Ｂ（１一　）　（１）　Ｔ＝ＡＥ＋Ｂ（１一　）＋ｃ，ｐ　（２）　其中：Ｅ表示ＳＳＤ预留空间比例，由ＳＳＤ厂商设定；　是有效　页比例；Ｉｐ是无效页比例；ｏ、ｂ、ｃ、Ａ、Ｂ均为权值系数，满足具　体取值为：０取０．３～０．５，ｂ取０．１—０．３，Ａ取０．５～０．７，Ｂ取　０．１—０．４，ｃ取０．１—０．３，且０＜Ｈ＜Ｔ＜１。通过实验验证　各参数的具体取值为ｏ＝０．３，ｂ＝０．１，Ａ＝０．５，Ｂ＝０．３，　Ｃ＝０．２，Ｅ＝０．１。不可中断垃圾回收请求会立刻执行，对正　常读写请求影响较大，因此应将日的值设定得较小，以尽可能　避免产生这类请求。根据式（１），日的最大值为ａＥ＋ｂ，且随有　效页比例　的上升而下降。可中断垃圾回收请求会在系统空　闲时间执行，　的值以ＡＥ＋Ｂ为参考基准，随着有效页比例的　上升而下降，随无效页比例的上升而上升。这意味着在无效页　较多而有效页较少时，　值较高，可及早触发无效页的回收；　而当有效页比例较高时，　值较低，以避免低效的垃圾回收。　为平衡ＳＳＤ计算资源和及时产生垃圾回收请求，ＷＰＯ－　ＧＣ以每个Ｐｌａｎｅ为单位，每消耗一定数量的页空间，进行一　次垃圾回收请求判断。产生的ＧＣ请求同正常的读写请求一　起挂载到通道请求队列上。为了减少ＳＳＤ正常的读写请求　和两类垃圾回收请求之间的相互干扰，设定这三类请求的服　务优先级由高到低依次为：１）不可中断垃圾回收请求；２）正　常读写请求；３）可中断的垃圾回收请求。　当通道上有不可中断垃圾回收请求时，立即响应不可中　断垃圾回收请求，否则优先处理读写请求；当通道空闲时执　行可中断垃圾回收请求。对于可中断垃圾回收请求，在其执　行过程中可能会被ＳＳＤ的正常读写请求中断，以减小ＧＣ对　正常读写请求响应时延的影响。　２．２　目标回收块的选择　在垃圾回收的目标块选择研究方面，贪婪算法只注重回　收的效率，会造成块磨损的不均衡；文献［１３］采用回收磨损　次数最少的块进行回收，但会增加ＧＣ迁移数据的开销。文　献［１５］综合考虑了块磨损和回收效率的考虑，相对其他策略　有了很大的改进。　ＷＰＯ—ＧＣ为了保证固态盘的使用寿命和回收效率，对文　献［１５］作进一步的优化改进，选用式（３）计算每个块得分，得　分最低的作为回收块。式（３）是在ｒｒｊｉｏｅ等”　提出的公式基　础上提出的，缺乏对特殊情况块的考虑，会选择主要包含空闲　页和无效页的块，这是不合理的。　式（３）由两部分相加而成。第一部分强调ＧＣ操作的性　能，即块中无效页越多，越可能被回收。　ｓｃ。ｒｅ＝ｃ－一。，（笆垒ｇ　三　）＋　ｅｒａ　ａｓｕｒｅｓ（ｉ）－．一　ｍａｘ），’；　　计算机应用　ｌ　ｌ　Ｏ　０　０　Ｏ　０　第３７卷　ｎ：ｆ２／（　＋ｅ　），Ａｅ≠０：Ａｓ：ｍｎ　—ｍｉｎ　ｔＯ，　的方法为ＴｅｍＬＰＮ＝Ｌｕｃ，ＬＰＮ的温度由最近写访问次数决定。　△ｓ＝０　（３）　其中：ｉｎｖａｌｉｄ（ｉ）表示第ｉ块中无效页数量；ｐａｇｅ—ｂｌｏｃｋ表示一　块中的物理页数；ｅｒａｓｕｒｅ（ｉ）表示第ｉ块的擦除次数；ｍ一表示　所有块中，块擦除次数最大的值；ｍｉｎ表示所有块中，块擦除　次数最小的值。　第二部分强调磨损均衡，即块的擦除次数越少，越可能被　回收。两部分的比重由系数ａ决定，ａ是块磨损次数极差Ａ６　的单调递增函数（图４）。ｋ　是表征系统响应能力的常数，　越　小，系统平均响应时间越短，磨损越不均衡，ｋ　取１Ｏ时，ａ约为　０．５，即两部分权重相同。特别地，当ａ为０时，算法不考虑磨损　均衡，即选取有效数据最少的块回收（贪婪策略）；当ａ为１　时，算法为纯磨损均衡，即选取磨损次数最少的块回收。回收　块的选择在更好地考虑ＳＳＤ性能的同时，能够兼顾ＳＳＤ的磨　损均衡，提高ＳＳＤ的寿命。　《　ｆ　ｆ　０　Ａ　图４　Ａ８的单调递增曲线　Ｆｉｇ．４　Ｍｏｎｏｔｏｎｅ　ｉｎｃｒｅａｓｉｎｇ　ｃｕｒｖｅ　ｏｆ　０一Ａｓ　２．３有效数据迁移策略　在垃圾回收过程中有效页的迁移方面，闪存芯片手册指　出可以使用高级命令ｃｏｐｙ—ｂａｃｋ进行有效数据的迁移，但是这　有很多限制条件Ｈ　；部分Ｇｃ算法　“・”　直接将回收块中的　有效数据迁移到空闲块，没有考虑数据的特性；文献［１５］提　出考虑数据的特性，将其进行冷热分离，来减少后续的ＧＣ开　销。　ＷＰＯ—ＧＣ在文献［１５］的基础上，增加了对“页温度”和　“块温度”的逐级考虑，提出冷热数据分离及迁移放置算法，　尽可能使冷热程度（访问频度）相近的数据聚集到同类的块　中，避免后续垃圾回收时冷数据页的无效迁移，提高垃圾回收　的效率，也减少了写放大，延长闪存的寿命。为了实现这一策　略，在ＳＳＤ固件中维护了一张逻辑页码（Ｌｏｇｉｃａｌ　Ｐａｇｅ　Ｎｕｍｂｅｒ，　ＬＰＮ）温度表，用于记录每个ＬＰＮ对应的温度，一个表项及其　各个字段的含义见表１。　表１　ＬＰＮ温度表项　Ｔａｂ．１　Ｉ．ＰＮ　ｔｈｅｒｍｏｍｅｔｅｒ　字段　含义　ＬＰＮ逻辑页号　总写访问（包括首次写和更新）次数　最近写访问次数　最近访问（写访问）时间戳　ＬＰＮ温度值　每当有写子请求到来时，按照图５所示流程更新ＬＰＮ温　度表。其中：ｃｔ是系统的当前时间；“是用于界定是否是最近访　问的时间间隔门限，当本次访问时间（即系统当前时问）距离　最近访问时间大于“时，将最近访问次数置为１。更新ＴｅｍＬＰＮ　图５更新ＬＰＮ温度表流程　Ｆｉｇ．５　Ｆｌｏｗｃｈａｒｔ　ｏｆ　ｕｐｄａｔｉｎｇ　ＬＰＮ　ｔｈｅｒｍｏｍｅｔｅｒ　一个块中有３种页温度，其中：１）有效页的温度就是其对　应的ＬＰＮ的温度值ＴｅｍＬＰＮ；２）无效页的温度值显示为其过　期前对应的ＬＰＮ的温度值；３）空闲页的温度值为０。为了更　好地考虑块中的数据情况，将页更准确地放到温度相近的块　中。提出用块温度（记为ＴｅｍＢｌｏｃｋ）来表示一个块的访问频　度，ＴｅｍＢｌｏｃｋ的计算公式：　１　ｖａ／／ｄ　ｉｎｖａｌｉｄ　ＴｅｍＢｌｏｃｋ＝　ｓｕｍ　（∑Ｔ、　ｅｍＰａｇｅ（　）＋∑ＴｅｍＰａｇｅ（ｊ））　其中各符号的意义见表２。ＴｅｍＢｌｏｃｋ的值由其中的有效页温　度和无效页温度计算得到，温度相近的页聚集一起，失效速率　也会大体相当，以便于减少回收块时的数据迁移。温度越高　的块更加容易失效，提高回收效率。　表２块温度计算所涉及的符号　Ｔａｂ．２　Ｓｙｍｂｏｌｓ　ａｂｏｕｔ　ｂｌｏｃｋ　ｔｅｍｐｅｒａｔｕｒｅ　ｃｏｍｐｕｔｉｎｇ　符号　意义　ｖａｌｉｄ＋ｉｎｖａｌｉｄ　１个块中。有效页总数　１个块中，无效页总数　第ｉ个物理页的温度值　３　实验结果与分析　ＷＰＯ．ＧＣ的测试平台是开源的ＳＳＤｓｉｍｌ１９］，首先分析所用　负载ｔｒａｃｅ的特点，然后描述了测试方案及测试过程，最后分　析实验结果。　３．１测试环境　测试使用ＳＳＤｓｉｍ，一个经过验证的固态盘模拟器，它可以　根据测试具体需要修改其配置文件。本方案测试所用ＳＳＤｓｉｍ　模拟的硬件配置参数见表３，ＳＳＤ物理总容量：４×２×２×２×　１０２４×６４×２　ＫＢ＝４　ＧＢ；用户可用容量：４　ＧＢ×０．８＝３．２　ＧＢ。　表３设备容量设置　Ｔａｂ．３　Ｄｅｖｉｃｅ　ｃａｐａｃｉｔｙ　ｓｅｔｔｉｎｇ　项目　配置　项目　配置　缓存　１２８　ＫＢ　每分组块数　１　０２４　通道数　４　每块页数　６４　每通道芯片数　２　物理页　２　ＫＢ　每芯片晶圆数　２　子页　５１２　Ｂ　每晶圆分组数　２　预留空间　１０％　３．２测试负载分析　测试使用４种ｔｒａｃｅ：Ｅｘｃｈａｎｇｅ、Ｆｉｎａｎｃｉａｌ、ＩｎｔｅｌＳＳＤ一１和　ＩｎｔｅｌＳＳＤ＿２，特性统计如表４。其中，Ｅｘｃｈａｎｇｅ是从一台供　第５期　方才华等：全程优化的固态硬盘垃圾回收方法　１２６１　５　０００企业用户使用的Ｍｉｃｒｏｓｏｆｔ　Ｅｘｃｈａｎｇｅ　２００７　ＳＰ１邮件服务　器上采集的ｔｒａｃｅ　，以小的随机访问的读请求为主。　Ｆｉｎａｎｃｉａｌ是在线事务处理（Ｏｎ—Ｌｉｎｅ　Ｔｒａｎｓａｃｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，　ＯＬＴＰ）应用程序运行在一个大型金融机构产生的Ｉ／Ｏ　ｔｒａｃｅ　；ＩｎｔｅｌＳＳＤ一１和ＩｎｔｅｌＳＳＤ＿２是用　在服务器上生成请　求，并利用ｂｌｏｃｋ—ｔｒａｃｅ工具采集得到的。　表４　ｔｒａｃｅ特性统计　Ｔａｂ．４　Ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｓｔａｔｉｓｔｉｃｓ　ｏｆ　ｔｒａｃｅ　３．３测试方案介绍　和ＤＴ．ＧＣ方案中，产生的是可中断的垃圾回收请求，当写请　求到来时垃圾回收操作还未完成，就中断垃圾回收操作，及时　响应，不造成时延。　ＯＢａｓｉｃ—ＧＣ方案皿ＤＴ—ＧＣ方案￣ＷＰＯ—ＧＣ方案　唇　ａｔ　．本文选用一种典型的垃圾回收算法Ｂａｓｉｃ－ＧＣ，以及文献　［１２］提出的ＤＴ—ＧＣ作为ＷＰＯ．ＧＣ的测试对照组。Ｂａｓｉｃ—ＧＣ　采用的策略如下：１）目标回收块的选取采用贪婪策略，即回　收无效数据最多的块；２）有效数据迁移采用ＷＥＣＯ中的冷热　数据分离方案；３）垃圾回收过程不可被中断。　本文主要测量了以下４个指标来评估ＷＰＯ－ＧＣ方案：　１）平均响应时间。即请求从提交给Ｆｌａｓｈ　ＳＳＤ到被响应　的平均时间，用于评估ＷＰＯ—ＧＣ方案的读写响应性能。　２）擦除次数的标准偏差。记录每个闪存分组在实验过　程中被擦除的次数的标准偏差，用于评估ＷＰＯ－ＧＣ方案的磨　损均衡性能。　Ｅｘｃｈａｎｇｅ　Ｆｉｎａｎｃｉａｌ　ＩｎｔｅｌＳＳＤ１　ＩｎｔｅｌＳＳＤ２　—．—．ｔｒａｃｅ的类型　图６归一化的读请求平均响应时间　Ｆｉｇ．６　Ｎｏｒｍａｌｉｚｅｄ　ａｖｅｒａｇｅ　ｒｅｓｐｏｎｓｅ　ｔｉｍｅ　ｏｆ　ｒｅａｄ　ｒｅｑｕｅｓｔｓ　３）擦除次数。记录同一ｔｒａｃｅ下两种策略分别引发的回　收次数，用于评估ＷＰＯ．ＧＣ方案减少的磨损。　４）总写页数。垃圾回收会造成写放大，记录固态盘全部　的写页次数，进一步评估ＷＰＯ．ＧＣ方案减少的磨损。　３．４测试结果分析　ＤＢａｓｉｃ—ＧＣ方案皿ＤＴ—ＧＣ方案￣ＷＰＯ—ＧＣ方案　本文以Ｂａｓｉｃ．ＧＣ和ＤＴ—ＧＣ方案为对照方案，对ＷＰＯ—ＧＣ　方案的整体性能进行了评估。　通过比较４种负载下三者的平均响应时间，可以看到　ＷＰＯ．ＧＣ方案相对于Ｂａｓｉｃ．ＧＣ在性能上有很大的提升，读／写　饕　Ｅｘｃｈａｎｇｅ　Ｆｉｎａｎｃｉａｌ　ＩｎｔｅｌＳＳＤ１　ＩｎｔｅｌＳＳＤ２　—．—．ｔｒａｃｅ的类型　图７归一化的写请求平均响应时间　Ｆｉｇ．７　Ｎｏｒｍａｌｉｚｅｄ　ａｖｅｒａｇｅ　ｒｅｓｐｏｎｓｅ　ｔｉｍｅ　ｏｆ　ｗｒｉｔｅ　ｒｅｑｕｅｓｔｓ　平均响应时间减少了接近２０％，特别是对于分时间段密集请　求的负载（如Ｆｉｎａｎｃｉ１），读／写平均响应时间减少达加％；ａ相　对于ＤＴ．ＧＣ在性能上的提升不是很明显，最高提升１０％左右。　图６、７分别显示了以Ｂａｓｉｃ．ＧＣ方案为基准对照，归一化　图８显示了以Ｂａｓｉｃ．ＧＣ方案为基准对照，归一化的总擦　除次数，纵坐标为三种方案擦除总次数与基准方案Ｂａｓｉｃ—ＧＣ　擦除总次数的比值。对于不同的ｔｒａｃｅ，块擦除的总次数有很　大不同，且跟Ｂａｓｉｃ－ＧＣ方案配置文件中垃圾回收阈值的设定　有关。　后的读、写平均响应时间，纵坐标对应为三种方案平均读、写　响应时间与Ｂａｓｉｃ．ＧＣ方案平均读、写响应时间的比值。从图　６中可以看出，ＷＰＯ．ＧＣ对４种ｔｒａｃｅ的读平均响应时间相对　于Ｂａｓｉｃ．ＧＣ均有较大提升，提升最少的接近２０％，最多的达　到４０％。从图７中可以看出，ＷＰＯ－ＧＣ方案相对于Ｂａｓｉｃ－ＧＣ　对所有ｔｒａｃｅ测试的结果表现出写平均响应时间均有很大提　升，提升最少的也有１７％，最多的达到４０％；但是相对于　ＤＴ．ＧＣ方案，ＷＰＯ—ＧＣ在性能上的提升并不明显，最高提升　１０％，而且对于ＩｎｔｅｌＳＳＤ一１负载，读写平均响应性能均有所下　降，约２％。　通过对ＳＳＤｓｉｍ的输出信息进行分析，发现三种方案在处　理一些请求所花费的响应时间是一致的，但是有些请求，　Ｂａｓｉｃ．ＧＣ方案的响应时间远大于ＷＰＯ－ＧＣ和ＤＴ—ＧＣ方案，这　应该是导致图６、７结果的原因。造成这种情况是因为Ｂａｓｉｃ－　ＧＣ方案在写请求到来时还在执行垃圾回收操作，无法及时响　应，造成时延，并对后续请求造成累计时延。而在ＷＰＯ－ＧＣ　１２６２　计算机应用　第３７卷　明显。另外３种ｔｒａｃｅ进行更新的次数较多，尽管在目标块选　的优化不是很明显，最高提升１０％，但是在减少写放大和均　取的回收效率上没有贪婪算法好，但由于考虑了冷热数据的　分离，在长时问的使用中弥补了回收效率的欠缺。测试结果　表明，ＷＰＯ－ＧＣ方案与Ｂａｓｉｃ．ＧＣ方案在总写页次数方面相比　差异性不大，ＷＰＯ—ＧＣ方案稍微优异一点。　ＤＢａｓｉｃ—ＧＣ方案ｒｎＤＴ—ＧＣ方案￣ＷＰＯ—ＧＣ方案　１．Ｏ５　　１ｊ四　１．００　０．９５　瓤ｇ　０．９０　０．８５　割　０．８０　Ｉ３Ｊｆ．　０．７５　蹈　０．７０　０．６５　０．６０　Ｅｘｃｈａｎｇｅ　Ｆｉｎａｎｃｉａｌ　ＩｎｔｅｌＳＳＤ．１　ＩｎｔｅｌＳＳＤ２　——．ｔｒａｃｅ的类型　图９归一化的总写页数　Ｆｉｇ．９　Ｎｏｒｍａｌｉｚｅｄ　ｔｏｔａｌ　ｎｕｍｂｅｒ　ｏｆ　ｗｒｉｔｉｎｇ　ｐａｇｅｓ　由于ＷＰＯ－ＧＣ中触发垃圾回收时是参考ＤＴ．ＧＣ的，所以　两者在擦除次数针对每个ｔｒａｃｅ大致相同，其中的细微差异是　由于ＷＰＯ—ＧＣ采用冷热数据分离算法，减少了一些有效页的　多次迁移，从而减少了写放大。从图９可以看到ＷＰＯ．ＧＣ方　案在总写页数上始终保证低于ＤＴ．ＧＣ方案，尤其对负载　Ｅｘｃｈａｇｅ更是减少了２０％的写操作。　图１Ｏ表现了三种方案导致的磨损均衡差异。当Ｆｌａｓｈ　ＳＳＤ所有块擦除次数的标准差较低时，表明磨损均匀分布。　图ｌ０显示了以Ｂａｓｉｃ－ＧＣ方案为基准对照，归一化的块擦除　次数标准差，纵坐标为三种方案块擦除次数标准差与Ｂａｓｉｃ－　ＧＣ方案块擦除次数标准差的比值。从图中可得，在各个　ｔｒａｃｅ下，ＤＴ—ＧＣ方案的分组的擦除次数标准差与Ｂａｓｉｃ—ＧＣ方　案近似相等，而ＷＰＯ－ＧＣ方案的分组的擦除次数标准差均小　于其他两种方案，其中３种ｔｒａｃｅ的测试结果的标准差降低近　３０％，表现出优异的磨损均衡性能。本文提出的新方案兼顾　效率和磨损均衡，在块擦除次数分布不均时，倾向于选择擦除　次数小的块进行回收，使各个块的擦出次数趋向于相同。同　时由于ＳＳＤｓｉｍ的垃圾回收机制是基于分组的，各分组中块的　擦除次数实际上更为平均，有利于提升固态盘的寿命。　ＤＢａｓｉｃ—ＧＣ方案皿ＤＴ—ＧＣ方案●ＷＰＯ—ＧＣ方案　｛磐　Ｅｘｃｈａｎｇｅ　Ｆｉｎａｎｃｉａｌ　ＩｎｔｅｌＳＳＤ１　ＩｎｔｅｌＳＳＤ２　—．—．ｔｒａｃｅ的类型　图１Ｏ归一化的块擦除次数标准差　Ｆｉｇ．１０　Ｎｏｒｍａｌｉｚｅｄ　ｓｔａｎｄａｒｄ　ｄｅｖｉａｔｉｏｎ　ｏｆ　ｂｌｃｏｋ　ｅｒａｓｉｎｇ　ｔｉｍｅｓ　４　结语　本文在详细剖析垃圾回收过程的基础上，提出了一种全　程优化的垃圾回收方法ＷＰＯ－ＧＣ，尽可能全面地考虑各步骤　对ＳＳＤ正常读写请求和寿命的影响。在开源的模拟器　ＳＳＤｓｉｍ上实现并验证了ＷＰＯ．ＧＣ的有效性。实验结果表明，　同典型ＧＣ算法相比，ＷＰＯ．ＧＣ可以减少ＳＳＤ读请求延迟　２０％一４０％，写请求延迟１７％～４０％，并能将均衡磨损近　３０％，从而延长其使用寿命；同ＤＴ．ＧＣ策略比较，在性能方面　衡磨损上有了近３０％的优化。如何在保证读写性能的情况　下，进一步延长ＳＳＤ的寿命，是一个值得深入研究的课题。　本文提出的方案主要是优化并结合前人的工作，接下来的工　作重心将放在如何将垃圾回收与缓存有效结合，在进行有效　数据迁移时，判断该数据所对应的逻辑地址是否在缓存已经　被更新，从而减少迁移耗时。　参考文献（Ｒｅｆｅｒｅｎｃｅｓ）　［１】ＬＥＥ　Ｓ　Ｗ，ＰＡＲＫ　Ｄ　Ｊ，ＣＨＵＮＧ　Ｔ　Ｓ，ｅｔ　ａ１．Ａ　ｌｏｇ　ｂｕｆｆｅｒ．ｂａｓｅｄ　ｆｌａｓｈ　ｔｒａｎｓｌａｔｉｏｎ　ｌａｙｅｒ　ｕｓｉｎｇ　ｆｕｌｌｙ—ａｓｓｏｃｉａｔｉｖｅ　ｓｅｃｔｏｒ　ｔｒａｎｓｌａｔｉｏｎ【Ｊ］．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｅｍｂｅｄｄｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ，２００７，６（３）：１５０—　１５１．　［２】ＴＡＮＧ　Ｘ，ＭＥＮＧ　Ｘ．ＡＣＲ：ａｎ　ａｄａｐｔｉｖｅ　ｃｏｓｔ—ａｗａｒｅ　ｂｕｆｆｅｒ　ｒｅｐｌａｃｅ—　ｍｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｆｌａｓｈ　ｓｔｏｒｇａｅ　ｄｅｖｉｃｅｓ【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１０　１　ｌ　ｔｈ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｄａｔａ　Ｍａｎａｇｅｍｅｎｔ．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２０１０：３３—４２．　【３］　ＳＯＧＡ　Ａ，ＳＵＮ　Ｃ，ＴＡＫＥＵＣＨＩ　Ｋ．ＮＡＮＤ　ｌｆａｓｈ　ａｗａｒｅ　ｄａｔａ　ｍａｎａｇｅ—　ｍｅｎｔ　ｓｙｓｔｅｍ　ｆｏｒ　ｈｉｇｈ—ｓｐｅｅｄ　ＳＳＤｓ　ｂｙ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｏｖｅｒｈｅａｄ　ｓｕｐ—　ｐｒｅｓｓｉｏｎ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１４　ＩＥＥＥ　６ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｍｅｍ—　ｏｒｙ　Ｗｏｒｋｓｈｏｐ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２０１４：１—４．　［４】　ｆｉ０【ＥＢ／ＯＬ］．【２０１６—０５—２２】．ｈｔｔｐ：／／ｆｒｅｅｃｏｄｅ．ｅｏｍ／ｐｒｏｊｅｃｔｓ／ｆｉｏ．　［５】　郭御风，李琼，刘光明，等．基于ＮＡＮＤ闪存的固态盘技术研　究［Ｊ］．计算机研究与发展，２００９，４６（２）：３２８—３２８．（ＧＵＯ　Ｙ　Ｆ，ＬＩ　Ｑ，ＬＩＵ　Ｇ　Ｍ，ｅｔ　ａ１．Ｒｅｓｅａｒｃｈ　ａｎｄ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｓｏｌｉｄ　ｓｔａｔｅ　ｄｉｓｋ　ｔｅｃｈｎｏｌｏｇｙ　ｂａｓｅｄ　ｏｎ　ＮＡＮＤ　ｆｌａｓｈ　ｍｅｍｏｒｙ［Ｊ］．Ｊｏｕｍａｌ　ｏｆ　Ｃｏｍ－　ｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００９，４６（２）：３２８—３２８．）　【６］　马宇川．拒绝掉速闪迪Ｅｘｔｒｅｍｅ　Ｐｒｏ４８０ＧＢ固态硬盘深度体验　【Ｊ１，微型计算机，２０１４（２１）：７１—７４．（ＭＡ　Ｙ　Ｃ．Ｒｅｊｅｃｔｅｄ　ＳａｎＤｉｓｋ　Ｐｒｏ４８０ＧＢ　ｅｘｔｒｅｍｅ　ｓｏｌｉｄ　ｓｔａｔｅ　ｈａｒｄ　ｄｉｓｋ　ｄｅｐｔｈ　ｅｘｐｅｒｉｅｎｃｅ　［Ｊ］．Ｍｉｃｒｏ　Ｃｏｍｐｕｔｅｒ，２０１４（２１）：７１—７４．）　［７］　ＢＥＡＫ　Ｓ，ＡＨＮ　Ｓ，ＣＨＯＩ　Ｊ．Ｕｎｉｆｏｒｍｉｔｙ　ｉｍｐｒｏｖｉｎｇ　ｐａｇｅ　ａｌｌｏｃａｔｉｏｎ　ｆｏｒ　ｌｆａｓｈ　ｍｅｍｏｒｙ　ｆｉｌｅ　ｓｙｓｔｅｍｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　ＡＣＭ＆　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｍｂｅｄｄｅｄ　Ｓｏｆｔｗａｒｅ．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ，２００７：１５４—１６３．　［８】　ＫＩＭ　Ｙ，ＯＲＡＬ　Ｓ，ＳＨＩＰＭＡＮ　Ｇ　Ｍ，ｅｔ　ａ１．Ｈａｒｍｏｎｉａ：ａ　ｇｌｏｂａｌｌｙ　ｃｏ—　ｏｒｄｉｎａｔｅｄ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｏｒ　ｏｆｒ　ａｒｒａｙｓ　ｏｆ　ｓｏｌｉｄ—ｓｔａｔｅ　ｄｒｉｖｅｓ【Ｃ】／／Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１　１　ＩＥＥＥ　２７ｔｈ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｍａｓｓ　Ｓｔｏｒａｇｅ　Ｓｙｓｔｅｍｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｉｅｓ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，　２０１１：ｌ一１２．　【９］ＨＡ　Ｋ，ＫＩＭ　Ｊ．Ａ　ｐｒｏｇｒａｍ　ｃｏｎｔｅｘｔ—ａｗａｒｅ　ｄａｔａ　ｓｅｐａｒａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　ｒｅｄｕｃｉｎｇ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｏｖｅｒｈｅａｄ　ｉｎ　ＮＡＮＤ　ｆｌａｓｈ　ｍｅｍｏｒｙ　［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｔｏｒ－　ａｇｅ　Ｎｅｔｗｏｒｋ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｐａｒａｌｌｅｌ　Ｉ／Ｏｓ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：　ＩＥＥＥ，２０１１：１—１０．　【１０】　ＧＡＬＡＮＤ　Ｅ，ＴＯＬＥＤＯ　Ｓ．Ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅｓ　ｆｏｒ　ｆｌａｓｈ　ｍｅｍｏｒｉｅｓ［Ｊ］．ＡＣＭ　Ｃｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ，２００５，３７（２）：１３８—１６３．　［１　１】ＬＥＥ　Ｊ，ＫＩＭ　Ｙ，ＳＨＩＰＭＡＮ　Ｇ，ｅｔ　ａ１．Ａ　ｓｅｍｉ・ｐｒｅｅｍｐｔｉｖｅ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｏｒ　ｏｆｒ　ｓｏｌｉｄ　ｓｔａｔｅ　ｄｒｉｖｅｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｔｅｒ－　ｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｅｒｆｏｒｍａｎｃｅ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｓｙｓｔｅｍｓ　ａｎｄ　Ｓｏｆｔ—　ｗａｒｅ．Ｐｉｓｃａｔａｗａｙ．ＮＪ：ＩＥＥＥ．２０１１：１２—２１．　［１２】　ＱＩＮ　Ｙ，ＦＥＮＧ　Ｄ，ＬＩＵ　Ｊ，ｅｔ　ａ１．ＤＴ－ＧＣ：ａｄａｐｔｉｖｅ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃ—　ｔｉｏｎ　ｗｉｔｈ　ｄｙｎａｍｉｃ　ｔｈｒｅｓｈｏｌｄｓ　ｆｏｒ　ＳＳＤｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１４　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｌｏｕｄ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｂｉｇ　Ｄａｔａ．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２０１４：１８２—１８８．　（下转第１２８１页）　第５期　ｖｅｒｓｉｔｙ，２００８．）　张玮等：针对并行软件待测行为测试的模型化简方法　１２８１　ｔｒｉ　ｎｅｔｓ【Ｃ】／／ＲＥＸ１９９３：Ｒｅｆｌｅｃｔｉｏｎｓ　ａｎｄ　Ｐｅｒｓｐｅｃｔｉｖｅｓ．Ｌｏｎｄｏｎ：　Ｓｐｒｉｎｇｅｒ・Ｖｅｒｌａｇ，１９９４：２３０—２７２．　【５】　孙涛．基于ＣＰ—ｎｅｔｓ模型的并行软件测试方法研究【Ｄ】．呼和浩　特：内蒙古大学，２０１２．（ＳＵＮ　Ｔ．Ｒｅｓｅａｒｃｈ　ｏｎ　ｔｅｓｔｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｐａｒｌｌａｅｌ　ｓｏｆｔｗａｒｅ　ｂａｓｅｄ　ｏｎ　ｃｏｌｏｒｅｄ　Ｐｅｔｒｉ　ｎｅｔｓ［Ｄ］．Ｈｏｈｈｏｔ：Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ，２０１２．）　【６】　ＲＡＩ　Ｖ，ＳＩＶＡＳＵＢＲＡＭＡＮＩＡＮ　Ｓ，ＢＨＵＬＡＩ　Ｓ，ｅｔ　１．Ａ　ｍｕｈｉｐｈａｓｅｄ　ａａｐｐｒｏａｃｈ　ｆｏｒ　ｍｏｄｅｌｉｎｇ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＢｉｔＴｏｒｒｅｎｔ　ｐｒｏｔｏｃｏｌ【Ｃ］／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏ１１　Ｄｉｓｔｉｂｕｔｒｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，　２００７：１０．　ｏｍａｔｅｄ　Ｔｅｓｔ　Ｇｅｎｅｒａｔｉｏｎ　Ａｎｄ　Ｖｅｒｉｉｅｄ　Ｓｏｆｆｔｗａｒｅ　［１２】　ＲＵＳＨＢＹ　Ｊ．Ａｕｔ［Ｍ】．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００５：１６１—１７２．　Ｓ　Ｊ，ＰＡＲＫＥＲ　Ｋ，ｅｔ　ａ１．Ｕｓｉｎｇ　ｓｙｍｂｏｌｉｃ　ｅｘｅｃｕｔｉｏｎ　【ｌ３］　ＬＥＥ　Ｇ，ＭＯＲＲＩｔｏ　ｇｕｉｄｅ　ｔｅｓｔ　ｇｅｎｅｒａｔｉｏｎ：ｒｅｓｅａｒｃｈ　ａｒｔｉｃｌｅｓ［Ｊ］．Ｓｏｆｔｗａｒｅ　Ｔｅｓｔｉｎｇ　Ｖｅｒｉｉｆｃａｔｉｏｎ＆Ｒｅｌｉａｂｉｌｉｔｙ，２００５，１５（１）：４１—６１．　［１４】　李华，叶新铭．基于Ｐｅｔｉ网的控制流与数据流相结合的协议　ｒ测试［Ｊ】．内蒙古大学学报（自然科学版），１９９９，２９（５）：７０２—　７０５．（Ｕ　Ｈ，ＹＥ　Ｘ　Ｍ．Ｐｒｏｔｏｃｏｌ　ｔｅｓｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　【７】　胡乃文．基于改进蚁群算法的测试序列优化算法【Ｄ］．北京交通　大学，２０１５．（ＨＵ　Ｎ　Ｗ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｔｅｓｔ　ｓｅｑｕｅｎｃｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ【Ｄ］．Ｂｅｉｊｉｎｇ：Ｂｅｉｊｉｎｇ　ｃｏｎｔｒｏｌ　ｆｌｏｗ　ａｎｄ　ｄａｔａｆｌｏｗ　ｂａｓｅｄ　ｏｎ　Ｐｅｔｉｒ　ｎｅｔ［Ｊ】．Ｊｏｕｍａｌ　ｏｆ　Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ），１９９９，２９（５）：７０２　—７０５．）　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，２０１５．）　ｉｆｃａｔｉｏｎ　ａｎｄ　ｖａｌｉｄａｔｉｏｎ　ｏｆ　ｓｉｍｕｌａｔｉｏｎ　ｍｏｄｅｌｓ　【１５］　ＳＡＲＧＥＮＴ　Ｒ　Ｇ．Ｖｅｒｉ【８】　陆公正．基于ＥＦＳＭ模型的测试用例优化生成及实例化【Ｄ】．上　海：上海大学，２０１４．（ＬＵ　Ｇ　Ｚ．ＥＦＳＭ　ｍｏｄｅｌ　ｂａｓｅｄ　ｏｐｔｉｍａｌ　ｇｅｎｅｒａ—　【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４０ｔｈ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｉｎｔｅｒ　Ｓｉｍｕｌａｔｉｏｎ．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２０１３：３７—４８．　ｔｉｏｎ　ａｎｄ　ｉｎｓｔａｍｉａｔｉｏｎ　ｏｆ　ｔｅｓｔ　ｃａｓｅｓ【Ｄ］．Ｓｈａｎｇｈａｉ：Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒ－　ｓｉｔｙ，２０１４．）　【９】ＳＵＮ　Ｔ，ＹＥ　Ｘ，ＬＩＵ　Ｊ．Ａ　ｔｅｓｔ　ｇｅｎｅｒａｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｍｏｄｅｌ　ｒｅ。　Ｔｈｉｓ　ｗｏｒｋ　ｉｓ　ｐａｒｔｉｌｌａｙ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎ—　ｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（６１５６２０６４，６１４６２０６６）．　ｄｕｃｔｉｏｎ　ｏｒ　ｐａｆｒａｌｌｅｌ　ｓｏｆｔｗａｒｅ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　１３ｔｈ　Ｉｎ－　ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｉｂｕｔｒｅｄ　Ｃｏｍｐｕｔｉｎｇ，Ａｐ－　ＺＨＡＮＧ　Ｗｅｉ．ｂｏｒｎ　ｉｎ　１９９１．Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒ－　ｅｓｔｓ　ｉｎｃｌｕｄｅ　ｓｏｆｔｗａｒｅ　ｔｅｓｔｉｎｇ．　ＳＵＮ　Ｔａｏ，ｂｏｒｎ　ｉｎ　１９８０，Ｐｈ．Ｄ．，ａｓｓｏｃｉａｔｅ　ｐｒｏｆｅｓｓｏｒ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｓｏｆｔｗａｒｅ　ｔｅｓｔｉｎｇ．　ＷＡＮ　Ｘｉａｏｙｕｎ，ｂｏｒｎ　ｉｎ　１９９０，Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｅｒ　ｅｓｅａｒｒｃｈ　ｉｎｔｅｒ－　ｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｉｅｓ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏ—　ｃｉｅｔｙ，２０１２：７７７—７８２．　【１０】　ＺＨＵ　Ｈ，ＨＥ　Ｘ．Ａ　ｍｅｔｈｏｄｏｌｏｇｙ　ｏｆ　ｔｅｓｔｉｎｇ　ｈｉｇｈ—ｌｅｖｅｌ　Ｐｅｔｒｉ　ｎｅｔｓ【Ｊ】．　Ｉｆｏｒｍａｔｎｉｏｎ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｔｅｃｈｎｏｌｏｇｙ，２００２，４４（８）：４７３—４８９．　【ｌｌ】ＪＥＮＳＥＮ　Ｋ．Ａｎ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｔｈｅ　ｔｈｅｏｒｅｔｉｃａｌ　ａｓｐｅｃｔ　ｏｆ　ｃｏｌｏｒｅｄ　Ｐｅ－　ｅｓｔｓ　ｉｎｃｌｕｄｅ　ｓｏｆｔｗａｘｅ　ｔｅｓｔｉｎｇ．　（上接第１２６２页）　［１３］ＫＷＯＮ　Ｏ，ＬＥＥ　Ｊ，ＫＯＨ　Ｋ．ＥＦ・Ｇｒｅｅｄｙ：ａ　ｎｏｖｅｌ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｐｏｌｉｃｙ　ｆｏｒ　ｆｌｓｈ　ｍｅｍｏｒｙ　ｂａｓｅｄ　ｅｍｂｅｄｄｅｄ　ｓｙｓｔｅｍｓ［Ｃ］／／　ａＰｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｃｉｅｎｃｅ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ．２００７：９１３—９２０．　２０１　１　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ，２０１１：９６—１０７．　ＮＧＴＯＮ　Ｂ，ＺＨＡＮＧ　Ｑ，ｅｔ　ａ１．　［２０］　ＫＡＶＡＬＡＮＣＫＥＲ　Ｓ，ＷＯＲＴＨＩＣｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ｏｆ　ｓｔｏｒａｇｅ　ｗｏｒｋｌｏａｄ　ｔｒａｃｅｓ　ｆｒｏｍ　ｐｒｏｄｕｃｔｉｏｎ　［１４］　ＫＩＭ　Ｈ，ＬＥＥ　Ｓ．Ａｎ　ｅｆｆｅｃｔｉｖｅ　ｆｌａｓｈ　ｍｅｍｏｒｙ　ｍａｎａｇｅｒ　ｆｏｒ　ｒｅｌｉａｂｌｅ　ｌｆａｓｈ　ｍｅｍｏｒｙ　ｓｐａｃｅ　ｍａｎａｇｅｍｅｎｔ［Ｊ］．ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ＆Ｓｙｓｔｅｍｓ，２００２，Ｅ８５Ｄ（６）：９５０—９６４．　Ｗｉｎｄｏｗｓ　ｓｅｒｖｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００８　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｉｌ　Ｗｏｒｋｌｏａｄ　Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２００８：１１９—１２８．　［１５］ＴＪＩＯＥ　Ｊ，ＢＬＡＮＣＥ　Ａ，ＸＩＥ　Ｔ，ｅｔ　ａ１．Ｍａｋｉｎｇ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｗｅａｒ　ｃｏｎｓｃｉｏｕｓ　ｆｏｒ　ｌｆａｓｈ　ＳＳＤ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　ＩＥＥＥ　７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｔｗｏｒｋｉｎｇ，Ａｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ａ　ＩＯＴＹＡ　Ｒｅｐｏｓｉｔｏｒｙ［ＥＢ／ＯＬ］．［２０１６・０５・２２］．ｈｔｔｐ：／／ｉｏｔｔａ．　［２１］　ＳＮＩｓｎｉａ．ｏｒｇ／ｔｒａｃｅｓ／１３０．　Ｓｔｏｒａｇｅ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２０１２：１１４—　１２３．　Ｔｈｉｓ　ｗｏｒｋ　ｉｓ　ｐａｒｔｉｌａｌｙ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｈｉ【ｈ　Ｔｅｃｈｎｏｌｇｏｇｙ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｐｒｏｇｒａｍ（８６３　Ｐｒｏｇｒｍ）ａ　ｏｆ　Ｃｈｉｎａ　［１６］ｗｕ　Ｓ，ＬＩＮ　Ｙ，ＭＡＯ　Ｂ，ｅｔ　ａ１．ＧＣａＲ：ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ａｗａｒｅ　ｃａｃｈｅ　ｍａｎａｇｅｍｅｎｔ　ｗｉｔｈ　ｉｍｐｒｏｖｅｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｒ　ｆｌｆａｓｈ—ｂａｓｅｄ　ＳＳＤｓ　（２０１５ＡＡ０１６７０１，２０１５ＡＡ０１５３０１），ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（６１３０３０４６，６１４０２１８９，６１４７２１５３）．　ＦＡＮＧ　Ｃａｉｈｕａ，ｂｏｒｎ　ｉｎ　１９９４．Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｂｉｇ　ｄａｔａ　ｓｔｏｒａｇｅ，ｓｏｌｉｄ　ｓｔａｔｅ　ｓｔｏｒａｇｅ，ｄａｔａ　ｄｅｄｕｐｌｉｃａｔｉｏｎ．　［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１６　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｕｐｅｒｅｏｍｐｕｔｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２０１６：Ａｒｔｉｃｌｅ　Ｎ０．２８．　［１７］ＭＯＭＯＤＯＭＩ　Ｍ，ＩＴＯＨ　Ｙ，ＳＨＩＲＯＴＮ　Ｒ，ｅｔ　ａ１．Ａｎ　ｅｘｐｅｒｉｍｅｎｔａｌ　４．Ｍｂｉｔ　ＣＭＯＳ　ＥＥＰＲＯＭ　ｗｉｔｈ　ａ　ＮＡＮＤ—ｓｔｒｕｃｔｕｒｅｄ　ｃｅｌｌ『Ｊ］．ＩＥＥＥ　ＬＩＵ　Ｊｉｎｇｎｉｎｇ，ｂｏｒｎ　ｉｎ　１９５７，Ｐｈ．Ｄ．，ｐｒｏｆｅｓｓｏｒ．Ｈｅｒ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｓｏｌｉｄ　ｓｔａｔｅ　ｓｔｏｒａｇｅ，ｄａｔａ　ｍｉｎｉｎｇ，ｄｉｓｔｉｂｕｔｒｅｄ　ｓｔｏｒａｇｅ．　ＴＯＮＧ　Ｗｅｉ，ｂｏｒｎ　ｉｎ　１９７７，Ｐｈ．Ｄ．，ｌｅｃｔｕｒｅｒ．Ｈｅｒ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｎｏｎ—ｖｏｌａｔｉｌｅ　ｍｅｍｏｒｙ　ｄｅｖｉｃｅ，ｉｎｐｕｔ／ｏｕｔｐｕｔ　ｖｉｔｒｕａｌｉｚａｔｉｏｎ．　ＧＡＯ　Ｙａｎｇ，ｂｏｒｎ　ｉｎ　１９９２，Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｌｉｄ－Ｓｔａｔｅ　Ｃｉｒｃｕｉｔｓ，１９８９，２４（５）：１２３８—１２４３．　［１８］ＸＩＥ　Ｗ，ＣＨＥＮ　Ｙ．Ａｎ　ａｄａｐｔｉｖｅ　ｓｅｐａｒａｔｉｏｎ—ａｗａｒｅ　ＦＴｒＬ　ｆ０ｒ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｅｆｉｃｉｆｅｎｃｙ　ｏｆ　ｇａｒｂａｇｅ　ｃｏｌｌｅｃｔｉｏｎ　ｉｎ　ＳＳＤｓ［ｃ］／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１４　１４ｔｈ　ＩＥＥＥ／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｌｕｓｔｅｒ，Ｃｌｏｕｄ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，　２０１４：５５２—５５３．　ｉｎｃｌｕｄｅ　ｂｉｇ　ｄａｔａ　ｓｔｏｒｇｅ，ｋｅｙ－ｖａａｌｕｅ　ｓｔｏｒａｇｅ．　ＬＥＩ　Ｘｉａ，ｂｏｒｎ　ｉｎ　１９９３，Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｅｒ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｂｉｇ　ｄａｔａ　ｓｔｏｒａｇｅ，ｓｅｃｕｒｅ　ｄａｔａ　ｄｅｌｅｔｉｏｎ．　［１９］ＨＵ　Ｙ，ＪＩＡＮＧ　Ｈ，ＦＥＮＧ　Ｄ，ｅｔ　ａ１．Ｐｅｒｆｏｒｍａｎｃｅ　ｉｍｐａｃｔ　ａｎｄ　ｉｎｔｅｒｐｌａｙ　ｏｆ　ＳＳＤ　ｐａｒａｌｌｅｌｉｓｍ　ｔｈｒｏｕｇｈ　ａｄｖａｎｃｅｄ　ｃｏｍｍａｎｄｓ，　ＪＩＡＮＧ　Ｙｕ，ｂｏｒｎ　ｉｎ　１９９３，Ｍ．Ｓ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｓｏｌｉｄ　ｓｔａｔｅ　ｓｔｏｒａｇｅ，ｎｏｖｅｌ　ｎｏｎ—ｖｏｌａｔｉｌｅ　ｍｅｍｏｒｙ　ｄｅｖｉｃｅ．　ｌａｌｃａｏｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｎｄ　ｄａａｔａ　ｇｒａｎｕｌａｒｉｔｙ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ