（计算机系统结构专业论文）基于嵌入式linux的ubifs损耗均衡的研究与实现.pdf

eas tchin a nor maluni v er s i t y t h er e s e a r c h r e a l i z a t i o n o fu b i fsw e a r - l e v e l i n gi nl i n u x - b a s e d e m b e d d e ds y s t e m d e p a r t m e n t ： m a j o r ： r e s e a r c hd i r e c t i o n ： 垦堑b 曼亟鱼星垂s y 墨! 曼堡 d i r e c t o r ： s h a os h i g r a d u a t es t u d e n t ：x i a o r uc a i c o m p l e t e di no c t o b e r , 2 0 10 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于嵌入式l i n u x 的u b i f s 损耗均衡的 研究与实现，是在华东师范大学攻读焉声博士( 请勾选) 学位期间，在导师 的指导下进行的研究工作及取得的研究成果。除文中已经注明引用的内容外， 本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要 贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：日期：7 o l0 年1 1 月2 4 - 日 华东师范大学学位论文著作权使用声明 基于嵌入式l i n u x 的u b i f s 损耗均衡的研究与实现系本人在华东师范 大学攻读学位期间在导师指导下完成的硕出博士( 请勾选) 学位论文，本论文 的研究成果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和 使用此学位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数 据库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位论文共建单 位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者 其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部或“涉密 学位论 文幸，于年月日解密，解密后适用上述授权。 ( 、) 2 不保密，适用上述授权。 导师签名本人签名盔苤垄 2 0i o 年i 月蚪日 ) i t “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定 过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方 为有效) ，未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默 认为公开学位论文，均适用上述授权) 。 蔡笑如硕士学位论文答辩委员会成员名单 姓名职称单位备注 张卫教授华东师范大学主席 沈建华副教授华东师范大学 王荣良副教授华东师范大学 华东师范大学硕士毕业论文论文摘要 论文摘要 由于n a n df l a s h 的物理特性，n a n df l a s h 面临垃圾收集、损耗均衡和坏 块处理三大挑战。因此，n a n df l a s h 需要采用不同的存储策略来解决这些问题， 而使用专门的f l a s h 文件系统是嵌入式系统应用中使用最广泛的一种存储策略， 它支持日志结构，并提供掉电保护，崩溃恢复机制和垃圾收集机制等。 由于嵌入式系统中存储的数据以静态数据为主，对于频繁更新的数据一般 集中在设备的某一区域，这些动态数据将使得f l a s h 设备上的擦除次数分布不均 匀，包含动态数据的擦除块将比包含静态数据的擦除块具有较多被擦除的机会， 从而导致f l a s h 设备因为集中被擦写的区域的损耗殆尽而结束寿命，而包含静态 数据的区域却还没有得到充分使用。这样将给系统和使用者造成损失，对于嵌 入式低成本、低投入的特征也是不允许的。考虑损耗均衡并拥有一个全局范围 的损耗均衡机制是解决n a n df l a s h 使用寿命问题的一个重要方式，而u b i f s 作为一种新型的n a n df l a s h 文件系统拥有这样的一种损耗均衡机制，并且完全 对用户透明。因此，设计并实现一种针对嵌入式系统中的静态数据特征的u b i f s 损耗均衡优化算法，具有现实意义与实用价值。 本文首先分析n a n df l a s h 的物理特性及其面临的挑战，研究不同的损耗均 衡方法和当前几种主流的损耗均衡算法，进而深入剖析u b i f s 架构与其损耗均 衡机制，为u b i f s 损耗均衡优化算法的设计提供参考与借鉴。随后深入研究 u b i f s 文件系统的源代码和其损耗均衡机制的具体实现，详细分析了u b i f s 中 的树型组织方式和管理结构，u b i 操作以及l e b 和p e b 之间的映射机制，为 u b i f s 损耗均衡优化算法的设计和实现打下了基础。接着文中提出了优化算法 的设计要求和总体设计架构，并且给出了在u b i f s 损耗均衡的基础上对损耗均 衡中的保护机制作出优化，对受保护的对象收集写请求操作，空间评估功能模 块以及对数据搬移功能模块的具体实现。最后设计测试方案和编写测试文件， 对u b i f s 的损耗均衡性能和挂载时间等进行测试与分析。 关键词：嵌入式系统、u b i f s 、u b i 、n a n df l a s h 、损耗均衡 a st h ed a t as t o r e di ne m b e d d e ds y s t e mi sm a i n l ys t a t i c ，t h ed y n a m i cd a t aw h i c h i sf r e q u e n t l yu p d a t e dw i l lb ef o c u so no n ea r e ao ft h ef l a s hd e v i c et h a tr e s u l t si nt h e u n e v e nd i s t r i b u t i o no fe r a s ec o u n t e r b e c a u s et h eb l o c k sc o n t a i n i n gd y n a m i cd a t a h a v em o r eo p p o r t u n i t i e st ob ee r a s e dt h a nt h eb l o c k sc o n t a i n i n gs t a t i cd a t a , t h e r ei s o n er e g i o no ff l a s hd e v i c er u n n i n go u to ft h e i re x p e c te r a s et i m e sw h i c hl e a d st ot h e e n do ff l a s hl i f ea n dt h es t a t i cr e g i o ni sn o tf u l l yu s e d t h i sw i l lr e s u l ti ng r e a tl o s st o u s e ra n di sa l s on o ta l l o w e di ne m b e d d e ds y s t e mw h i c hr e q u i r e sl o wc o s ta n dl o w i n v e s t m e n t w eh a v et oc o n s i d e rt h ew e a r - l e v e l i n gm e c h a n i s me s p e c i a l l yi ng l o b a l d o m a i nt os o l v et h ep r o b l e mo ft h el i m i t e dl i f es p a ni nf l a s h a san e wt y p eo f n a n df l a s hf i l es y s t e m ，u b i f si m p l e m e n t st h ew e a r - l e v e l i n gm e c h a n i s mw h i c hi s t r a n s p a r e n t t ou s e r s t h e r e f o r e ，i ti s m e a n i n g f u lt od e s i g na n di m p l e m e n tt h e o p t i m i z a t i o na l g o r i t h mo fu b i f sw e a r - l e v e l i n gf o ra l le m b e d d e ds y s t e m 、而t hs t a t i c d a t a t h i sp a p e ra n a l y z e st h ep h y s i c a lc h a r a c t e r i s t i c sa n dc h a l l e n g e so fn a n df l a s k a n dd i s c u s s e sd i f f e r e n t w e a r - l e v e l i n g m e t h o d sa n ds e r v e r a l w i d e l y u s e d w e a r - l e v e l i n ga l g o r i t h m s t h e nt h eu b i f sa r c h i t e c t u r ea n di t sw e a r - l e v e l i n g m e c h a n i s ma r ed e e p l ya n a l y z e d ，w h i c ha l s op r o v i d et h eb a s i ck n o w l e g m e n ta n d r e f e r e n c ef o rt h eo p t i m i z a t i o nd e s i g n a f t e rs t u d y i n gt h eu b i f ss o u r c ec o d ea n di t s c o n c r e t er e a l i z a t i o no fw e a r - l e v e l i n g ，ad e t a i l e da n a l y s i so fu b i f st r e es t r u c t u r e d m a n a g e m e n ta n du b io p e r a t i o n si n c l u d i n gt h em a p p i n gm e c h a n i s i mb e t w e e nl e b a n dp e b ，p r o v i d et h ef o u n d a t i o no ft h eo p t i m a t i o ni m p l e m e n t i o n i nt h i sp a p e r , t h e o p t i m i z a t i o na l g o r i t h m i s p r o p o s e d w i mo v e r a l l d e s i g n a r c h i t e c t u r ea n dt h e o p t i m i z a t e dp r o t e c t i o n m o d u l ei s g i v e n i nu b i f s w e a r - l e v e l i n gs u b s y s t e m ， i n c l u d i n gt h ew r i t er e q u e s t sc o l l e c t i o nf u n c t i o n ，t h es p a c ea s s e s s m e n tf u n c t i o na n d 华东师范大学硕士毕业论文 a b s t r a c t t h ed a t am o v e m e n tf u n c t i o n t e s tp l a t f o r mi sp e r f o r m e dt ov a l i d a t et h ed e s i g na n d r e a l i z a t i o no ft h eo p t i m i z e du b i f sw e a r - l e v e l i n g k e yw o r d ：e m b e d d e ds y s t e m ，u b i f s ，u b i ，n a n df l a s h ，w e a r - l e v e l i n g i i i 2 2 损耗均衡方法6 2 3 损耗均衡实现7 2 4 损耗均衡重要性技术分析8 2 5 损耗均衡主流算法研究9 第3 章u b i f s 文件系统的分析1 2 3 1l i n u x 文件系统架构中的u b i f s 模块1 2 3 2u b i f s 架构分析。1 5 第4 章u b i f s 损耗均衡的研究1 8 4 1u b i f s 代码分析18 4 2u b i f s 损耗均衡树型管理结构1 8 4 3u b i 操作的映射机制2 2 第5 章u b i f s 损耗均衡的优化设计2 5 5 1 优化目标2 5 5 2 整体设计架构2 5 5 3 优化前提一2 6 5 4 优化算法的设计与分析2 8 5 5 算法的局限性。3 0 第6 章u b i f s 损耗均衡的实现3 2 6 1 写请求收集队列的实现3 2 6 2 主要功能函数3 5 6 3 损耗均衡的实现3 6 6 4l e b 和p e b 的映射3 9 i v 华东师范大学硕士毕业论文目录 6 5 实现中遇到的问题和解决办法4 0 第7 章测试与分析 7 1 测试环境与工具：4 2 7 2 测试方案4 3 7 3 测试结果分析4 6 第8 章总结与展望 4 9 8 1 总结4 9 8 2 进一步的工作4 9 参考文献 致谢 攻读硕士学位期间发表的学术论文 v 5 l 5 3 5 4 华东师范大学硕士毕业论文 第1 章引言 第1 章引言 1 1 研究背景与研究现状 f l a s h 存储器是常用的存储器件，它的不挥发性、抗震性、灵活性、低功耗 以及高速的读写性能等特点为嵌入式系统和移动计算机提供了良好的条件【l 】。 其中，n a n df l a s h 以低成本和大容量支持的优势快速占据嵌入式市场，并成为 未来存储介质的一大趋势。根据i s u p p l i 统计预测，2 0 0 5 年至2 0 0 9 年n a n df l a s h 的c a g r ( c o m p o u n d a n n u a lg r o w t hr a t e ) 值为1 4 ，比d r a m ，n o rf l a s h ， s r a m 等存储器，具有更可观的市场幅度成长【i 】。n a n df l a s h 继承了f l a s h 存 储器独特的物理特性：以页为单位进行内容的写入，以块为单位进行擦除；写 操作只能在空闲或已擦除的单元内进行；写操作比读操作执行时间相差比大； 存在物理坏块，并且每个块的擦除次数有限制等。这些物理特性使得n a n d f l a s h 面临诸多挑战，主要有三类：垃圾收集，即回收包含无效数据的物理块； 坏块管理，即对f l a s h 操作无效导致的坏块和出厂坏块的管理；损耗均衡，即平 衡每个擦除块的损耗机会，避免因为某个擦除块提早耗损而导致整个f l a s h 寿命 缩短。其中擦除次数分布不均严重影响f l a s h 的使用寿命，一般n o rf l a s h 擦除 次数最大在1 0 5 次左右，而n a n df l a s h 擦除次数最大可能在1 0 6 次左右【2 】。所 以，在实际应用中n a n df l a s h 的文件系统都要考虑损耗均衡( w e a r - l e v e l i n g ) 策略，尽量避免未使用完规定的擦除次数而提前损坏的情况，最大化地保证f l a s h 的使用寿命。 文件系统若不考虑损耗均衡，将会导致f l a s h 存储体消耗不均匀，直接缩短 f l a s h 的使用寿命。针对n a n df l a s h 面临的挑战，当前嵌入式系统提出了很多 解决方案，大致有三类： 采用传统文件系统，专门针对磁盘而开发，如e x t 2 ，e x t 3 ，f a t l 6 3 2 ， d o s ，c r a m f s 等，但是对于以f l a s h 为介质的文件系统，管理效率低， 尤其在f l a s h 使用寿命方面。 采用f t l n f t l ( f l a s ht r a n s l a t i o nl a y e r n a n df l a s ht r a n s l a t i o nl a y e r ) 转换层，构建于传统文件系统之上，实现日志管理和损耗均衡等技术， 但存在效率低，内存消耗大，对f l a s h 容量、文件系统访问模式等存在 华东师范大学硕士毕业论文第1 章引言 线性依赖等局限性。 采用f l a s h 专用文件系统，如j f f s l 2 ( j o u r n a l i n gf l a s hf i l es y s t e m ) ， y a f f s1 2 ( y e ta n o t h e rf l a s hf i l es y s t e m ) 等，：一定程度上缓解了f l a s h 使用上的技术瓶颈，并且内存消耗减少，启动快，管理效率高，但有 无法管理大容量f l a s h ，损耗均衡性能差等问题。 u b i f s ( u n s o r t e db l o c ki m a g ef i l es y s t e m ) 是一个正在开发中的n a n df l a s h 文件系统，也是被广泛应用的j f f s 2 的后继者【3 1 。u b i f s 拥有更快的启动速度， 占用内存更少，提供了灵活高效的损耗均衡机制，同时支持大容量f l a s h 。因此， 本文在u b i f s 文件系统的基础上，进行损耗均衡算法的研究。 一般嵌入式系统中应用的数据特点是：数据大多都是静态不变的，而一些 多媒体应用方面，如m p 3 数据、视频信号、图像等，数据不仅容量大而且动态 更新频繁。这样以来，静态数据占据的物理块没有很多机会被擦除，而某些数 据块可能由于频繁更新而提前结束寿命。若静态数据不断增加，那么动态数据 存储的范围则会越来越小，最终导致某些块提前坏掉，影响f l a s h 的整体寿命【l 】。 要解决这个问题，不同的数据属性就需要不一样的存储策略来管理，这样才能 保证f l a s h 使用寿命的最大化。而本文主要针对嵌入式静态数据特点，优化损耗 均衡算法，实现静态数据的搬移，并针对n a n df l a s h 的物理特性和嵌入式应用 环境进行相应的优化。因此，本文基于u b i f s 文件系统设计并实现了一个针对 嵌入式应用的损耗均衡优化算法，并具有一定的实用价值和现实意义。 1 2 论文主要研究工作 本文首先对n a n df l a s h 的物理特性和面临的挑战进行分析，通过分析和比 较当前几种主流损耗均衡算法，体现损耗均衡的重要性，然后深入研究u b i f s 系统架构及其损耗均衡机制，并在u b i f s 文件系统的基础上设计并实现一个针 对嵌入式静态数据应用特点的损耗均衡优化算法，最后设计测试方案，对u b i f s 损耗均衡优化性能和文件系统挂载时间进行测试。 本文的主要工作包括以下几个方面： 1 深入研究u b i f s 文件系统的源代码。 研究u b i f s 文件系统，梳理u b i f s 代码结构和系统架构，研究u b i f s 在 l i n u x 系统中与v f s ( v i r t u a lf i l es y s t e m ) 层和m t d ( m e m o r yt e c h n o l o g yd e v i c e ) 层的接口，为深入研究其损耗均衡机制作准备。 2 华东师范大学硕士毕业论文第1 章引言 2 深入分析u b i f s 损耗均衡模块。 通过借鉴各种损耗均衡算法，以及j f f s 2 和u b i f s 文件系统中损耗均衡机 制的设计思想，分析其实现的方式，优化u b i f s 损耗均衡算法。 3 提出u b i f s 损耗均衡算法的设计方案 提出u b i f s 文件系统的整体架构与性能要求，设计一个较完善的损耗均衡 机制，并针对n a n df l a s h 的物理特性和嵌入式数据特征提出优化方案。 4 实现u b i f s 损耗均衡的优化设计 首先修改并设计算法中所涉及的数据结构，通过空间评估功能模块和数据 搬移功能模块的共同协作，完成写请求的收集工作。针对嵌入式系统的数据特 征，将包含静态数据的数据块作为写请求的收集来源，最终完成损耗均衡的优 化。 5 设计测试方案，对u b i f s 损耗均衡的性能进行测试 使用n a n d s i m ( n a n ds i m u l a t o r ) 模拟n a n df l a s h ，并在其上挂载优化后 的u b i f s ，并通过测试文件对擦除能力和挂载时间等进行全面测试。 1 3 论文组织架构 本文通过对相关背景知识的分析与研究，完成对u b i f s 损耗均衡优化算法 的设计，并详细叙述了u b i f s 损耗均衡优化的实现过程，最后给出一个完整的 测试方案，并对测试结果进行分析。论文总共分八个章节。 第一章：本章主要分析n a n df l a s h 的应用现状和现有的解决方案等相关研 究背景，并对本文所做的主要工作进行概括。 第二章：本章主要详述了n a n df l a s h 的物理特性和面临的挑战，分析了损 耗均衡的方法及其实现，并通过比较，进一步研究损耗均衡的重要性和当前几 个主流算法。 第三章：本章首先研究u b i f s 在l i n u x 文件系统中的位置，即与v f s 和 m t d 层的关联，以及针对n a n df l a s h 存储介质所采用的文件系统。然后对 u b i f s 系统架构作进一步研究，其中分别对u b i ( u n s o r t e db l o c ki m a g e ) 逻辑 卷和系统中的损耗均衡和垃圾收集机制进行了具体分析，为进一步研究损耗均 衡提供参考。 第四章：本章深入剖析u b i f s 损耗均衡模块，包括其复杂的树型管理机制 和映射机制，具体分析了损耗均衡对擦除块的组织和管理，以及u b i 操作和头 3 华东师范大学硕士毕业论文第1 章引言 部信息，并将分析了映射操作的实现。这一章也是u b i f s 损耗均衡优化算法实 现的基石。 第五章：本章详细分析了u b i f s 损耗均衡优化算法的整个设计过程，并根 据算法设计 法的分析， 第六章 损耗均衡对 的应用特征 能。最后梳 第七章弗飞早 和挂载时间 第八章弟早 华东师范大学硕士毕业论文第2 章损耗均衡的研究 第2 章损耗均衡的分析 2 1n a n df l a s h 2 1 1 物理特性 n # _ n df l a s h 的主要物理特性如下【1 ，2 】： n a n df l a s h 采用的是异地更新策略，位操作只能由1 变成0 ，所以在 写之前需要先进行擦除操作； ： n a n df l a s h 的擦除以块为单位，读写以页为单位，页是最小的读写单 元，它包含数据区与备份区，而一个擦除块可以包含若干个页； n a n df l a s h 的使用寿命有一定的限制，因为每个块的擦除次数有限， 比如s l c 为1 0 6 ，m l c 为1 0 5 ，所以需要引入了损耗均衡机制，避免 擦除操作集中在相同的块，尽量使得每个块都得到均匀擦除的机会； n a n df l a s h 会产生坏块的问题，可能由位反转引起，还会产生写干扰 等问题，通过引入e c c ( e r r o rc o r r e c t i o nc o d e ) 校验码对每一页的数 据内容来进行校验进而保证数据的正确性。 2 1 2 面临的挑战 n a n df l a s h 的存储管理面临诸多挑战，如第1 章研究背景与研究现状中所 提到，主要分为三类： 损耗均衡( w e a r - l e v e l i n g ) ：动态损耗均衡主要针对给定的物理擦除块 的有限次擦除问题。f l a s h 设备的使用寿命主要体现在有限次的擦除次 数，物理擦除块在变成为坏块之前可以进行有限次的擦除操作。为了最 大化f l a s h 使用寿命，必须考虑损耗均衡。损耗均衡分为两类：动态损 耗均衡和静态损耗均衡。它将擦除操作均匀地分布到整个设备上。 垃圾收集( g a r b a g ec o l l e c t i o n ) 垃圾收集过程主要处理包含无效数据 的无效擦除块并进行回收。首先选取新擦除块来存储被搬移的有效数 据，然后擦除无效擦除块，使之得到重用。不同的是，在垃圾收集过程 中不能进行读写操作。为了提高系统读写性能，应尽量减少垃圾收集过 华东师范大学硕士毕业论文 第2 章损耗均衡的研究 程的时间。 坏块处理( b a db l o c kh a n d l i n g ) ：f l a s h 设备上的坏块，一部分来自出厂 时就带有的被允许的坏块，一部分来自使用过程中产生的坏块。对f l a s h 的操作失败，就会产生坏块，比如无效的写操作。一旦确认为坏块，f l a s h 设备将在坏块表中登记这些块，并作出标记。对上层文件系统而言，对 坏块处理的实现是透明的，可能通过内部的微控制器在硬件上解决实 现。 2 2 损耗均衡方法 由于f l a s h 存储设备中的区块有使用限制，f l a s h 管理技术通常用于克服其 损耗问题，尽可能延长f l a s h 的可用性。损耗均衡就是f l a s h 管理技术之一。损 耗均衡通过在f l a s h 设备可用块上分散地进行写擦除操作，达到设备损耗的均 匀化。损耗均衡在如下过程中发生：向空闲块中写新数据或者更新数据；擦除 不包含有效数据的脏块，使之成为空闲块。整个过程中，损耗均衡对用户不可 见，只在后台选择目标块。 n a n df l a s h 设备中存储两种数据类型，静态数据很少进行更新，只是频繁 地进行读操作，理论上只存放于同一物理位置，相反地，动态数据则常常进行 更新。按照数据类型分，损耗均衡有2 种方法，分别为动态损耗均衡和静态损 耗均衡。 动态损耗均衡只针对接受动态写操作成功的数据块，它将多个写操作重定 向到不同的物理数据块。本质上，动态损耗均衡解决了因为重复写同一物理块 而造成经常被使用的物理块的过早或过度损耗。如果数据块没有写操作，动态 损耗均衡就不会发生。 区别于动态损耗均衡，静态损耗均衡针对所有数据块，甚至没有写操作的 数据块。但是不同的厂商会根据自己的产品拥有不同的静态损耗均衡算法的触 发机制。通常的触发机制会为每一个数据块保留写擦除操作的计数值，然后根 据不同数据块之间的差额值触发静态损耗算法。静态损耗均衡通过在写擦除池 中缓冲静态数据块，来解决非均匀化损耗问题。付出的代价就是增加额外操作 来搬移静态数据块，以及面临搬移失败带来的开销。 从数据块的覆盖可见，静态损耗均衡更好地保证更多数据块的均衡使用。 对于嵌入式设备而言，数据往往不需要频繁更新和大量更新，尤其对于操作系 6 华东师范大学硕士毕业论文 第2 章损耗均衡的研究 统文件。若只进行动态损耗均衡则使得大部分用于静态损耗均衡的数据块处于 不可用状态，严重缩短f l a s h 设备的使用寿命。这直接影响嵌入式设备的投入成 本，对于以静态数据为主的嵌入式应用，更是毫无意义。 2 3 损耗均衡实现 n a n df l a s h 控制器管理内存访问和f l a s h 块的使用，损耗均衡隶属于该控 制器管理。通常，控制器通过一张查询表，将内存阵列物理块地址( p b a ，p h y s i c a l b l o c k a d d r e s s ) 转换成逻辑块地址( l b a ，l o g i c a lb l o c k a d d r e s s ) ，如图2 - l 所 示。损耗均衡则决定使用哪个物理块进行写操作，它不受数据存放位置的物理 局限，可选择内存阵列中的任何位置存放数据。 h o s t ：使用l b a j 亡 n a n df l a s h c o n t r o i l e r b l o c k 查询表 l b ap b a 0 n 0 01 0 s 3 0 0 0 10 2 1 4 n 0 0 20 5 0 9 j 亡 n a n df l a s h ：使用p b a 图2 - 1 地址映射奇询表 根据不同的损耗均衡方法，控制器选择不同的数据块： 动态损耗均衡：选取擦除次数最少的可用擦除块写入数据； 静态损耗均衡：选取擦除次数最少的可用目标块，必要时进行擦除操作， 并写进新数据。当擦除次数低于一定阈值时，搬移静态数据，进行擦 除操作。 动态损耗均衡通过缓冲可用数据块并为下次写操作选取擦除次数最少的 块。假定拥有4 0 9 6 个物理块的m l c 设备，其中包含7 5 的静态数据和2 5 的 动态数据，并以每1 0 分钟写擦除5 0 个物理块的更新频率进行动态损耗均衡。 垮 华东师范大学硕士毕业论文第2 章损耗均衡的研究 那么该设备将大约可用4 年时间，其中将近7 5 的物理块未受使用。 动态损耗均衡情况下，计算设备使用年限： ( 10 ，0 0 0 c y c l e s 10 2 4 b l o c k s ) ( 5 0 b l o c k s 6 0m i ns 2 4 h o u r s ) = 14 2 2 d a y s 15 y e a r s 褂 旺 掣 赛 剐 霉 损耗均衡方法 图2 2 损耗均衡方法下的物理块使用情况 由图2 2 可知，不同的损耗均衡方法下物理块的使用情况会不同，在该假 定条件中仅采用动态损耗均衡方法只能利用2 5 的物理块，而采用静态损耗均 衡方法后，设备上的所有物理块都得到了充分的利用，延长了n a n df l a s h 的使 用寿命。 2 4 损耗均衡重要性技术分析 同2 3 所假定的情况：拥有4 0 9 6 个物理块的m l c 设备，其中包含7 5 的 静态数据和2 5 的动态数据，并以每1 0 分钟写擦除5 0 个物理块的更新频率进 行动态损耗均衡。特别指出的是，此时n a n df l a s h 设备允许存在2 5 的坏块。 8 加 踟 鲫 加 o 华东师范大学硕士毕业论文第2 章损耗均衡的研究 下面比较考虑损耗均衡前后设备的使用情况，具体见表2 1 。 表2 1 损耗均衡的重要性 情况 未考虑损耗均衡考虑损耗均衡 动作更新3 个文件，即3 5 0 个物理块，更新频率为每个文件1 0 分钟 结果 n a n df l a s h 端口重用2 0 0 个物理块被用重用4 0 9 6 个物理块，将写，擦除操作 于该更新动作，1 年后，n a n df l a s h 中均匀分布到整个f l a s h 设备上，并且 9 5 的内存阵列不可用【2 】使用年限达1 5 年之久 重用块数2 0 0 个物理块4 0 9 6 个物理块 使用寿命 1 0 ，o o o 缈昆s 2 0 0 6 ，d c 缸 ：2 7 8 d a y s 15 妒椰( 考虑损耗均衡) 5 0 b l o c k sx6 f i l e s h o u r 2 4 h o u r s 。 。 由表2 1 可见，是否考虑损耗均衡对f l a s h 设备的使用寿命影响很大。考虑 损耗均衡之后，写擦除操作将会均匀地分布到所有物理块，大大扩展了f l a s h 设备的使用寿命，并且更有效地利用了内存容量。重用2 0 0 个物理块使得接近 2 , 0 0 0 ，0 0 0 有效物理块被写或擦除，而使用4 , 0 9 6 个物理块使得多于4 0 ，0 0 0 ，0 0 0 有效物理块被写或擦除。 2 5 损耗均衡主流算法研究 目前为止，已经提出相当多的损耗均衡算法，主要有以下几个。这些算法 基本围绕：1 ) 如何均衡分配擦除机会；2 ) 如何减少均衡开销。 k l ( k i ma n dl e e ) 算法【8 】 k l 算法使用公式2 1 计算均衡度。在垃圾收集过程中系统选取数值最 大的物理块作为擦除对象，其中，当入趋向于0 时，即均衡度低于可接 受阈值，| ji 成为选取物理块的主要因素。当入趋向于1 时，即均衡度 超过可接受阈值，ui 和8i 成为选取物理块的主要因素。 ( 1 以) x 触去42 赢m f 弘0 肚0 砌洲洳讼龀。1 其中i ii 表示第i 个物理块，ei 表示第i 个物理块的擦除次数，一表 示擦除块的最大擦除次数，入表示正常的均衡度，范围在o 和1 之间。 华东师范大学硕士毕业论文第2 章损耗均衡的研究 物理块的选取主要考虑以下两种情况：一、为回收更多空闲空间而搬移 数据：二、收集静态数据并回写。对于情况一，选取擦除次数最小的物 理块容纳新数据，并且被选取块可能因为数据的动态性而具备更多被选 取的机会，提高物理块使用率。对于情况二，选取擦除次数最大的物理 块收集静态数据，因为大多数静态数据都将聚集在该物理块上，尽可能 分散使用率。 c a t ( c o s t a g et i m e ) 算法【7 ，9 】 c a t 算法由c h i a n g 等人提出，并在垃圾收集过程中被触发。该算法考 虑物理块的擦除开销和数据类型，即静态数据和动态数据。根据公式 2 2 ，c a t 算法选取数值最大的物理块作为擦除对象，即优先选取包含 静态数据的物理块，使得各个物理块之间的擦除机会趋于平衡，但是操 作粒度局限于页级。 尝竺盟( 公式2 - 2 ) ( 1 一“) 乞 其中，pi 表示第i 个物理块占用的f l a s h 内存，a i ( t ) 表示以擦除次数t 作参数的第i 个物理块的年龄，ei 表示第i 个物理块的擦除次数。 s d ( s t a t i c d y n a m i c ) 算法【1 o 】 s d 算法是在m s y s t e m t m e f f s 中提出的，对静态数据，执行h c ( h o t c o l d ) 算法并且周期性被触发。h c 算法就是根据数据属性，当最老数 据块和最新数据块之间的擦除次数超过一定阈值时，交换两个数据块的 数据；对动态数据，从轮询队列中选取物理块进行写操作，这些数据块 根据物理地址的先后次序进行排序。由于s d 算法结合了h c 算法，使 得冷热数据动态分离，物理块的使用也趋于均匀化。 t b ( t u r n - b a s e ds e l e c t i o n ) 算法【5 ，6 ，1 1 】 t b 算法在j f f s 2 和y a f f s 文件系统中提出，根据x + y 次概率计算， 选取合适的擦除块，并且周期性触发。其中x 是不考虑损耗均衡的情况 下垃圾收集器选取擦除块的概率，y 是考虑损耗均衡情况下选取擦除块 的概率。具体地说，在不同的应用系统中，可能一个包含有效数据的擦 除块均被选中，也可能随机地选中擦除块，如采用f i f o 的选取策略。 o p ( o l d b l o c kp r o t e c t i o n ) 算法【3 ，4 1 o p 算法由u b i 提出，并在块被擦除期间触发。当刚完成擦除操作的物 1 0 华东师范大学硕士毕业论文第2 章损耗均衡的研究 理块和最年轻块的擦除次数之差大于一定阈值时，最年轻块中的数据将 被搬移到已擦除块。最年轻块，即包含最新动态数据的物理块。同时， 该算法保证刚被擦除的物理块不会纳入下一次损耗均衡操作的对象范 围，除非要擦除事先定义好的物理块数。 华东师范大学硕士毕业论文第3 章u b i f s 文件系统的研究 第3 章u b i f s 文件系统的分析 3 1 l i n u x 文件系统架构中的u b i f s 模块 s y s 酶m i c a “f f l a s hm e m o r y 图3 - l 系统架构图 l i n u x 文件系统并不允许用户直接访问f l a s h 介质，而是提供给用户一定的 系统调用接口。从系统调用到f l a s h 介质，大概分三层，从高层到底层分别为： v f s ( v i r t u a lf i l es y s t e m ) ，n a n df l a s h 文件系统和m t d ( m e m o r yt e c h n o l o g y d e v i c e ) 层。本文所要研究的重点u b i f s 属于n a n df l a s h 文件系统层。下面 具体讨论各个层次。 3 1 1v f s 虚拟文件系统( v f s ，v i r t u a lf i l es y s t e m ) 是l i n u x 文件系统的根，是底层 f l a s h 文件系统的主要接口。它不是真正的文件系统，只是导出一组接口，然后 将它们抽象到各个底层f l a s h 文件系统【1 9 1 。因为各个文件系统的行为差异可能很 大。v f s 通过文件系统的“注册来完成l i n u x 对不同f l a s h 文件系统的支持。 通过注册之后，v f s 会给系统内核提供一个调用该f l a s h 文件系统函数的接口。 当用户调用一个文件时，不需要因为文件所属不同的文件系统而按照不同 的方式读取。v f s 本身抽象了不同文件系统的共同部分，对用户屏蔽了具体的 操作，这使得用户不用再去关心文件所属的文件系统问题，实现了各个文件系 统的良好兼容。当一个最新推出的文件系统普遍被采用时，l i n u x 借助v f s 的强大功能，可以毫不费力的实现新文件系统在本地的组织运行，同时能不干 1 2 华东师范大学硕士毕业论文 第3 章u b i f s 文件系统的研究 扰其他已经装配在本地的其他文件系统，可以说以v f s 组织文件系统是非常具 有可扩展性，并具有优良的发展前景。 3 1 2n a n df l a s h 文件系统 n a n df l a s h 文件系统越来越多，有j f f s 2 、y a f f s 2 、l o g f s 、u b i f s 等。 j f f s 2 ( j o u m a l l i n gf l a s hf i l es y s t e mv e r s i o n 2 ) 文件系统是一个日志结构 ( 1 0 9 s t r u c t u r e d ) 的文件系统，包含数据和原数据( m e t a d a t a ) 的节点在闪存上 顺序的存储【5 1 。j f f s 2 之所以选择日志结构的存储方式，是因为闪存更新策略 是异地更新( o u t o f - p l a c e ) 的方式。它避免了断电等可能造成数据破坏的现象， 并可以使擦除和编程操作均匀分布到所有的块设备上，避免影响f l a s h 寿命。 y a f f s ( y e ta n o t h e rf l a s hf i l es y s t e m ) 文件系统是为n a n df l a s h 优化的 文件系统，相比于j f f s 2 ，y a f f s 在n a n df l a s h 上提供了更好的性能，包括 更小的内存消耗，更快速的文件系统加载等】。y a f f s 2 文件系统是y a f f s 的 升级版本，消除了原先存在的部分编程问题，对某些芯片支持连续页面编程等。 同时在很多性能上得到改进，如在新8 b i t 的n a n df l a s h 上达到8 7 m b s 的读 取，3 m b s 的写入和5 4 m b s 的垃圾整理等。 u b i f s 文件系统是新型日志文件系统，专门为n a n df l a s h 开发且可视为 j f f s 2 的后继版本，现已整合进内核树( 内核版本2 6 2 7 以后) 。u b i f s 工作在 u b i 之上，并具有诸多优点：它支持大容量n a n df l a s h ，甚至超过i o o g b