摘要
嵌入式系统已经广泛地渗透到科学研究、工程设计、军事技术、各类产业和商业文化艺术、娱乐业以及人们的日常生活等各方面。随着嵌入式系统越来越广泛的应用,嵌入式系统中的数据存储和数据管理已经成为一个重要的课题摆在设计人员面前。
闪存(Flash Memory)是嵌入式系统中一种常用的存储介质,具有体积小、容量大、成本低、掉电数据不丢失等一系列优点。目前已经逐步取代其他半导体存储元件,成为嵌入式系统中的主要数据和程序载体。通常,一个闪存是由若干个闪存块组成,每个闪存块又分为若干个物理页。闪存块是擦除操作的最小单位,而读和写都是以页为单位进行,对一个物理页进行重写之前,必须先对该页所在的块执行擦除操作。而每一个闪存块的擦除次数是有限的,一般是在10万次到100万次之间,只要有一个闪存块的擦除次数达到了上限,数据存储就变得不可靠,会影响到整个闪存的读写效率和性能。因此,需要设计高效的磨损均衡处理(wear-leveling)策略,尽可能让各闪存块保持相近的擦除次数以延长闪存的使用寿命。
本文首先介绍国内外现有的磨损均衡算法,通过仿真试验对比各算法的优缺点。然后从理论上给出了在任何一个闪存块达到擦除次数上限前,闪存可执行的擦除操作次数的上下界,并对此进行了证明。接着,对现有的算法进行改进,提出了两种基于不同目标的磨损均衡算法:
1、闪存在每次初始化的时候,都需要将块的擦除情况读入到内存中,然后根据这些信息实现块的均匀擦除,但嵌入式设备的内存非常有限,减少磨损均衡处理时的内存消耗是磨损均衡策略设计中应当考虑的问题。本文创造性地在确定性算法中加入了随机处理的成分,减少了算法执行过程中的内存开销。
2、节能是嵌入式系统设计的关键目标之一。嵌入式系统使用过程中不断进行着数据的存取,大量的能量消耗在作为外部存储介质的闪存的操作上。因此,减少嵌入式设备外部存储介质上的能耗是实现节能的重要途径。本文提出了一种基于低能耗的磨损均衡算法,既能够使各物理块有相近的擦除次数,从而延长闪存的使用寿命,又能够减少闪存操作上的能耗,从而延长了嵌入式设备一次充电后的使用时间。
Embedded devices has been developed rapidly in the research lab and used widely in many fields such as industry, military department, personal consumption. With a great widely use of embedded devices, various optimization techniques are proposed to resolve the problems of data storage and data management in these devices.
With the recent technology breakthroughs in both capacity and reliability, more and more embedded systems now deploy flash memory as their storage systems, due to its small bulk, big capacity, low cost and nonvolatile features. Flash memory has gradually replaced the use of other semiconductor storages and has become the primary data and program storages. Due to the hardware architecture, data on the flash memory is written in a page and erasing is done in a block. A block must be erased before any new data is written in it. But a block could tolerate a limited number of erasing before the block becomes unreliable. The number is typically 100K to 1000K cycles. Therefore the wear leveling algorithm is to have an even erasure count distribution of flash memory blocks so that the endurance of flash memory could be improved.
This paper presents the current wear leveling algorithms published in papers or patents and compares with each other in computer simulations. Then the paper lays out and prove a low bound and a upper bound of erasing count before any block reaches the maximum count. Next, two wear leveling algorithms are proposed in order to solve two different problems:
During the initialization process of flash memory, block erasure information is to load into the main memory which is used to realize the even erasure. But the capacity of main memory in embedded device is not enough, reducing the consumption of main memory should be taken into account. By combining the deterministic and randomized algorithms, we invent an effective algorithm to evenly leverage the placements of cold-hot data while consumes less memory.
Energy-conservation is one of the critical issues in the design of embedded systems. One promising approach is to reduce the energy consumption of secondary storage, here the flash-memory in particular. We presents a set of energy-aware flash memory management strategies. the proposed strategies can optimize the energy distribution, and the saved energy from shutting down the idle banks can effectively serve the read and write requests of applications while blocks have close erasures.
引文
[1]于宗光,何耀宇.闪速存储器的研究与进展[J].半导体技术,1999,24(5):1-7.
[2]李力.闪速存储器技术现状及发展趋势[J].单片机与嵌入式系统应用,2001,12(8):32-35.
[3]骆丽.嵌入式系统设计[M].北京:北京航空航天大学出版社,2004.
[4]Gary Wang.深入浅出聊闪存[J].电子与电脑,2006,8(1 3):53.55.
[5]Flash Memory[M].Intel Corporation,1994.
[6]Suman Nath,Aman Kansal.FlashDB:Dynamic Self-tuning Database for NAND Flash[M].Microsoft technical report,2006.
[7]易柏林.新型嵌入式移动存储卡标准的研究与实现[D].北京:北京邮电大学,2007.
[8]朱岩,沈卫华,孙辉先.基于闪存的固态存储器的数据管理[J].计算机工程,2007,12(2):54-56.
[9]冯翔.嵌入式系统中闪存设备管理技术研究与实现[D].湖南:湖南大学,2004.
[10]Chang M.L,Lee P.C,Chang R.C.Managing FlashMemory in Personal Communication Device[J].ISCE '97,1997.177182.
[11]J.W.Hsieh,L.E Chang,T.W.Kuo.Efficient On-Line Identification of Hot Data for Flash-Memory Management[C].In:Proceedings of the 2005 ACM symposium on Applied computing,Mar 2005,838-842.
[12]YUN Z.Flash Memory Technology Development[C].In:International Parallel and Distributed Processing Symposium,San Francisco,CA,April 2001.
[13]Understanding the Flash Translation Layer[EB/OL].http://developer.intel.com/.Technical report,Intel Corporation,Dec 1998.
[14]钟忻慕,慕春棣.基于闪存的文件系统的实现[J].计算机工程与应用,2003,39(24):133-135.
[15]Yuan-Hao Chang,Jen-Wei Hsieh,Tei-Wei Kuo.Endurance enhancement of flash-memory storage systems:an efficient static wear leveling design[C].In:Proceedings of the 44th Annual Conference on Design Automation,ACM Press, 2007.212-217.
[16]张骏,樊晓桠,刘松鹤.一种flash存储器静态负载平衡策略[J].计算机应用,2006,26(5):1205-1207.
[17]Woodhouse D.JFFS:The journaling flash file system[EB/OL]http://sources.redhat.com/jffs2/jffs2.pdf,2008-05-07.
[18]阳富民,邓雪梅,涂刚.JFFS2文件系统闪存管理策略研究与改进[J].计算机工程与科学,2005.27(2):54-57.
[19]Amir Ban.Wear leveling of static areas in flash memory[P].US patent:0184432.2002-12-5.
[20]Chang L P,Kuo T W.Adaptive striping architecture for flash memory storage systems of embedded systems[C].In:Proceedings of the IEEE Real-time and Embedded Technology and Applications Symposium,IEEE Computer Society,2002,187-196.
[21]Gal E,Toledo S.Algorithms and data structures for flash memories[J]ACM Computing Surveys,2005,37(2):138-163.
[22]Mahmud Assar.Flash memory mass storage architecture[P].US patent:5388083.1995-2-7.
[23]Charles C Lee.System and method for managing blocks in flash memory[P].US patent:0204187.2005-9-15.
[24]Karl Lofgren.Wear leveling techniques for flash EEPROM systems[P].US patent:6230233.2001-5-8.
[25]Robert Chang.Wear-leveling in non-volatile storage systems[P].US patent:6985992.2006-1-10.
[26]潘沁,周新志,魏刚.磨损均衡算法在NAND flash管理中的改进[J].微计算机信息,2007,23(3):301-303.
[27]Li-Pin Chang.On efficient wear leveling for large-scale flash-memory storage systems[C]In:Proceedings of the 2007 ACM Symposium on Applied Computing,ACM Press,2007,1126-1130.
[28]Rosenblum M,Ousterhout K.The design and implementation of a log-structured file system[J]Computer Systems,1992,10(1):26-52.
[29]盛骤,谢式干,潘承毅.概率论与数理统计[M].北京:高等教育出版社,2001.
[30]C.McDiarmid.Probabilistic Methods for Algorithmic Discrete Mathematics[M].Springer Verlag,1998,195-248.
[31]Sarbazi-Azad,H.,Khonsari,A.A class of ball-and-bin problems and its application to mesh networks[C].In:Proceedings of the 2003 10th IEEE International Conference On Electronics,Circuits and Systems,2003,1038-1041.
[32]Michael Mitzenmacher.The Power of Two Choices in Randomized Load Balancing[D].Ph.D Thesis,University of California,Berkeley,1996.
[33]Martin Raab,Angelika Steger."balls into bins"-a simple and tight analysis.In:Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science,London,UK,1998,159-170.
[34]刘锐,李盘林,李秉智.一种适用于大容量Flash存储系统的管理方案[J].计算机应用研究,2006,23(2):87-89.
[35]李强,杜威,慕春棣.基于大容量闪存的嵌入式文件系统[J].计算机工程,2005,31(10):78-80.
[36]杜晔华.嵌入式系统中闪速存储器系统的若干节能技术研究[D].浙江:浙江大学,2007.
[37]Delaluz V,Kandemir M,Kolcu I.Automatic data migration for reducing energy consumption in mulit-bank memory systems[C].In:Proceedings of Design Automation.New Orleans,Louisiana,USA,2002:213-218.
[38]Lee H G,Chang N.Energy-aware memory allocation in heterogeneous non-volatile memory systems[C].In:Proceedings of the International Symposium on Low Power Electronics and Design.Seoul,Korea,2003:420-423.
[39]Lebeck A R,Fan X,Zeng H,Ellis C S.Power aware page allocation[C].In:Proceedings of the International Conference on Architectural Support for Programming Language and Operating Systems.Cambridge,MA,2000:105-116.
[40]Park C,Kang J U,Park S Y,Kim J.S.Energy-aware demand paging on NAND flash-based embedded storages[C].In:Proceedings of the International Symposium on Low Power Electronics and Design,Newport Beanch,California,USA,2004:338-343.
[41]Chiang M.L.,Lee P.H.,Chang R.C.Cleaning policies in mobile computers using flash memory[J].Systems and Software,1999,48(3):213-231
[42]Kim H J,Lee S G.A new flash memory management for flash storage systemiC].In:Proceedings of the International Computer Soft-ware and Applications Conference,Phoenix,AZ,USA,1999:284-290.
[43]Kimi J,Lee G.an effective flash memory manager for reliable flash memory space management[J].Information and System,2002,85(6):950-964.
[44]Marshall M,Manning H.flash file management system[P].US patent:5832493.1998-12-3.
[45]Jou E,Jeppesen H.flash memory wear leveling system providing immediate direct access to microprocessor[P].US patent:5568423.1995-2-12.
[46]Kawaguchi A,Nishioka S,Motoda H.a flash-memory based file system[C].In:the USENIX Technical Conference.New Orleans:USENIX,1995:155-164.
[47]朱文忠.闪速存储器系统的节能方法研究[J].科技创新导报,2008,10(6):43-45.
[48]Wells S,Hasbun N,Robinson K.sector-based storage device emulator having variable-sized sector[P].US patent:5822781.1998-10-13.
[49]Du Y H,Cai M,Dong J X.Adaptive energy-aware design of a multi-bank flash-memory storage system[C].In:Proceedings of the 1 lth IEEE International Conference on Real-Time and Embedded Computing Systems and Applications.Hong Kong:IEEE Computer Society,2005:311-316.
[50]Sarnsung Electronics.NAND flash memory & Smart Media data book[M].Korea:Samsung Company,2002.
[51]Lee M,Seo E,Lee J,Kim J.PABC:Power-Aware Buffer Cache Management for Low Power Consumption.IEEE Transactions on Computers,2007,56(4):488-501
[52]Hsieh J W,Kuo T W,Wu P L,Huang Y H.Energy-Efficient and Performance-Enhanced Disks Using Flash-Memory Cache//Proceedings of ACM International Symposium on Low Power Electronics and Design. Portland,Oregon,USA,2007:334-339
[53] Khatib M G, Zwaag B J, Hartel P.H, Smit G J. Interposing Flash between Disk and DRAM to Save Energy for Streaming Workloads//Proceedings of Embedded Systems for Real-Time Multimedia.Salzburg,2007:7-12
[54] Tseng H W, Li H L, Yang C L.An Energy-Efficient Virtual Memory System with Flash Memory as the Secondary Storage//Proceedings of International Symposium on Low Power Electronics and Design. Tegernsee,2006:418-423
[55] Huang W T, Chen C T, Chen C H, Cheng C C. Energy-Efficient Buffer Architecture for Flash Memory//Proceedings of Multimedia and Ubiquitous Engineering. Busan,2008:543-546
[56] Du Y H, Cai M, Dong J X. Dynamic Voltage Scaling of Flash Memory Storage Systems for Low-Power Real-Time Embedded Systems[J]. Embedded Software and Systems.2005,16(18):152-157
[57] Joo Y S, Cho Y J, Shin D H, Chang N Y. Energy-Aware Data Compression for Multi-Level Cell (MLC) Flash Memory//Proceedings of Design Automation Conference. San Diego,California,USA,2007:716-719
[58] Joo Y S, Cho Y J, Shin D H, Park J Y. An Energy Characterization Platform for Memory Devices and Energy-Aware Data Compression for Multilevel-Cell Flash Memory[J]. ACM Transactions on Design Automation of Electronic Systems.2008,13(3):43-72
[59] Moshnyaha V G, Vo H, Reinman G, Potkonjak M. Reducing Energy of DRAM/Flash Memory System by OS-controlled Data Refresh//Proceedings of Circuits and Systems. New Oreans,LA,2007:2108-2111
[60] Chang L P, Kuo T W. An Adaptive Striping Architecture for Flash Memory Storage Systems of Embedded Systems//Proceedings of the 8th IEEE Real-time and Embedded Technology and Applications Symposium.California,2002:187-196
[61] Wu C H, Kuo T W, Yang C L. Energy-Efficient Flash-Memory Storage Systems with an Interrupt-Emulation Mechanism // Proceedings of the international conference on Hardware/Software Codesign and System Synthesis. Washington.DC,U SA,2004:134-139
[62]杜晔华,蔡铭,董金祥.基于数据相关性的多片闪存系统垃圾回收器[J].华中科技大学学报.2007,35(11):66-68
[63]杜晔华,蔡铭,董金祥.闪存存储系统中低功耗自适应垃圾回收机制的设计与实现[M].中国计算机大会论文集,清华大学出版社,2005
[64]Intel.NAND flash Datasheet.Intel Corporation,2007
[65]Delaluz V,Kandemir M,Vijaykrishnan N,Sivasubramaniam A.DRAM Energy Management Using Software and Hardware Directed Power Mode Control//Proceedings of High-Performance Computer Architecture.Saudi Arabia,2001:159-169
[66]S.Irani,S.Shukla,R.Gupta.Online strategies for dynamic power management in systems with multiple power-saving states[J].ACM Transaction on Embedded Computing Systems.2003,2(3):325-346
[67]Amber Huffman.NAND Flash Interface Specification.Intel Corporation,2006