（模式识别与智能系统专业论文）nand+flash与usb闪存盘之间的数据交互.pdf

摘要摘要如今嵌入式系统对存储系统的要求越来越高，不但要求能够安全快速地存储大量的数据，而且要求能够跟外部进行数据的交互。所谓数据交互就是能够将外部的数据导入或者将嵌入式存储器内部的数据导出。n a n df l a s h 被广泛用作嵌入式系统的存储设备，而同外界进行数据交互的一个方便快捷的方法就是能够与u s b闪存盘进行文件的相互拷贝。本文针对如何实现n a n df l a s h 和u s b 闪存盘之间的文件交互，提出了一整套解决方案。重点讨论的问题是：如何根据n a n df a s h 自身的特点在其中建立文件系统，用来管理嵌入式系统内部的文件。对于n a n df l a s h 固有的坏块以及磨损平衡问题提出了有效的解决方案。对于嵌入式系统在恶劣工作环境下出现突然掉电，从而可能导致的文件系统崩溃的问题也给出了简洁高效的解决方案。为了实现对u s b 闪存盘的文件访问，本文讨论了如何利用u s b 接口芯片和f p g a 协同工作来实现对u s b 闪存盘扇区的数据访问。在此基础上根据f a t l 6 和f a t 3 2 标准编写了相应的文件系统程序，从而实现了对格式化为f a t l 6 或f a t 3 2 格式的u s b闪存盘的文件访问与操作。最终成功实现了嵌入式系统与连接其上的u s b 闪存盘之间文件的相互拷贝，解决了嵌入式系统与外界进行数据交互的问题。从而使该系统能够利用此能力满足实际应用中的各种数据交互要求。关键词：n a n df l a s h数据交互文件系统坏块处理掉电保护a b s t r a c tt o d a y , ah i g hp e r f o r m a n c es t o r a g es y s t e ma r er e q u i r e di ne m b e d d e ds y s t e m ，t h ea b i l i t yo fs t o r i n gm a s so fd a t as a f e l ya n dq u i c k l yi se s s e n t i a la n dt h ed a t ae x c h a n g eb e t w e e ne m b e d d e ds y s t e ma n de x t e r n a le n v i r o n m e n ti sa l s ov e r yi m p o r t a n t n a n df l a s hb e c o m ew i d e l yu s e di ne m b e d d e ds y s t e mb e c a u s eo fh i g hm e m o r yd e n s i t ya n dl l i g hm e m o r ys p e e d ac o n v e n i e n tw a yo fe x c h a n g i n gd a t ab e t w e e ne m b e d d e ds y s t e ma n de x t e r n a le n v i r o n m e n ti sf i l ec a nb ec o p y e df r o me a c ho t h e rt h r o u g h tu s bi n t e r f a c e am e t h o do fe x c h a n g i n gf i l e sb e t w e e nn a n df a s ha n du s bf l a s hd r i v e ri sp r e s e n t e di nt h i sp a p e r t h ei m p o r t a n ti s s u ei n c l u d e ：h o wt oc r e a t eaf i l es y s t e mo nn a n df l a s hc o n s i d e r i n gt h es p e c i a lc h a r a c t e ro fn a n df l a s h s o m ee f f i c i e n tm e t h o d sa r eb r i n g e du pt or e s o l v et h ep r o b l e ms u c ha s ：b a db l o c km a n a g e m e n t ，w e a rl e v e l i n g ,p o w e rl o s sr e c o v e r ya n ds oo n i no r d e rt ov i s i tt h ef i l ei nu s bf l a s hd r i v e r , t h i sp a p e ra c c o m p l i s ht h el o w l e v e ld r i v e ro f u s bi n t e r f a c e ，f a t l 6a n df a t 3 2f i l es y s t e m f i n a l l y , t h ef i l ei nn a n df l a s ha n du s bf l a s hd r i v e rc a nb ec o p y e db e t w e e ne a c ho t h e r , h o wt oe x c h a n g ed a t ab e t w e e ne m b e d d e ds y s t e ma n de x t e r n a le n v i r o n m e n ti sn ol o n g e rap r o b l e m ，t h ee m b e d d e ds y s t e mc a ne a s i l yr e s o l v et h ed a t ae x c h a g ep r o b l e mm a k eu s eo ft h i st e c h n o l o g y k e yw o r d ：n a n df l a s hd a t ae x c h a n g ef i l es y s t e mb a db l o c km a n a g e m e n tp o w e rl o s sr e c o v e r y西安电子科技大学学位论文创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：走垒拦盐只期2 竺! 宝：f ：丝西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规定)本学位论文属于保育i 在一年解密后适用本授权书。本人签名：起挺盟同期丝! 望：l !第一章绪论第一章绪论1 1 引言随着嵌入式系统在消费电子，数据采集和工业控制等领域得到越来越广泛的应用，各个领域都对嵌入式系统提出了更高的要求。作为嵌入式系统中最重要的组成部分，存储系统呈现出了较快的发展速度，存储量和存取速度都有很大的提高。n a n df l a s h 作为一种安全、快速的存储体，具有体积小、容量大、成本低、以及更多的擦除次数等一系列优点，已成为嵌入式系统中数据和程序最主要的载体。而越来越多的应用要求嵌入式系统本身的存储系统能够与外界进行数据交互。与外界进行数据交互的一种方便快捷的方法就是能够与通用的u s b 闪存盘进行文件的交互。为了能够与u s b 闪存盘进行文件的交互，嵌入式系统必须具备u s b 接口的驱动能力从而能够读取u s b 闪存盘各个扇区的数据，在有了底层驱动能力后嵌入式系统还必须能够识别u s b 闪存盘的文件系统，这样才能读取或者向其中写入文件。为了管理自身的数据，嵌入式系统需要在n a n df l a s h 中建立自己的文件系统。由于n a n df l a s h 在结构和操作方式上与硬盘等其他存储介质有较大区别，同时n a n df l a s h 存储器还有坏块，磨损平衡等等问题，这些都要求建立于其上的文件系统必须根据n a n df l a s h 自身特性进行特殊设计，以保证实现存储系统的高性能和高可靠性。1 2 嵌入式文件系统特点嵌入式系统通常采用闪存作为存储介质，而闪存相对于磁盘有很多特别之处，这就使嵌入式文件系统的实现方式与磁盘文件系统有很多不同之处。下面在不涉及具体物理特性的基础上，从文件系统的角度介绍闪存的特性及限制，从而引出嵌入式文件系统针对这些特性及限制相对与磁盘文件系统需要进行哪些方面的修改。闪存的最小寻址单位是字节( b y t o ，而不是磁盘上的扇区( s e c t o r ) 。这意味着可以从一块闪存的任意偏移( o f f s e t ) 读数据，但并不表明对闪存写操作也是以字节为单位进行的。当一块闪存处在干净的状态时( 被擦写过，但是还没有写操作发生) ，在这块f l a s h 上的每一位( b i t ) 都是逻辑1 。闪存上的每一位( b i t ) 可以被写操作置成逻辑0 。可是把逻辑0 置成逻辑l 却不能按位( b i t ) 来操作，而只能按擦写块( e r a s eb l o c k ) 为单位进行擦写操作。擦写块的大小从4 k 到1 2 8 k 不等。从上层来看，2n a n df l a s h 与u s b 闪存盘之间的数据交互擦写所完成的功能就是把擦写块内的每一位都重设置( r e s e t ) 成逻辑l 。闪存的使用寿命是有限的。具体来说，闪存的使用寿命是由擦写块的最大可擦写次数来决定的。超过了最大可擦写次数，这个擦写块就成为坏块m a db l o c k ) t 。因此为了避免某个擦写块被过度擦写，以至于它先于其他的擦写块达到最大可擦写次数，应该在尽量小的影响性能的前提下，使擦写操作均匀的分布在每个擦写块上。这个过程叫做磨损平衡( w e a rl e v e l i n g ) 。将磁盘文件系统( e x t 2 ，f a t ) 运行在闪存上的很自然的方法就是在文件系统和闪存之间提供一个闪存转换层( f l a s ht r a n s l a t i o nl a y e r ) ，它的功能就是将底层的闪存模拟成一个具有5 1 2 字节扇区大小的标准块设备( b l o c kd e v i c e ) 。对于文件系统来说，就像工作在一个普通的块设备上一样，没有任何的差别。同时为了解决闪存存在的坏块和磨损平衡问题嵌入式文件系统需要有针对性地做出修改。1 3 研究工作概要及内容安排1 3 1 主要工作本文在深入分析f a t 文件系统的基础上，实现了对格式化为f a t 3 2 或f a t l 6的u s b 闪存盘的文件操作。同时在嵌入式系统的n a n df l a s h 上创建了f a t l 6文件系统，并有针对性地解决了f a t 文件系统应用于嵌入式环境所遇到的问题，其中包括：1 ) 利用缓存机制将n a n df l a s h 抽象为一个带c a c h e 的通用存储设备，使上层文件系统可以不考虑n a n df l a s h 必须按块先擦后写的特性。2 ) 运用虚拟内存的思想解决了n a n df l a s h 的坏块问题，实现逻辑清晰并且效率高。3 ) 对于嵌入式文件系统在意外掉电情况下的自我保护问题提出了一种有效的解决方法，同时实现了f a t 表所在f l a s h 块的磨损平衡。4 ) 利用f a t 文件系统分配空闲簇的算法，对数据区的磨损平衡也提出了一种高效的实现方法。最终在解决了u s b 闪存盘和n a n df l a s h 文件系统的基础上，实现了这两者之间的文件交互，使嵌入式系统具备了一种有效地同外部环境进行数据交互的手段。1 3 2 论文章节安排第一章首先引出了嵌入式系统与外界进行数据交互的需求，简单描述了嵌入式存储介质以及嵌入式文件系统的特点。第二章详细剖析了文件系统的实质，为嵌入式系统与外界进行文件交互打下第一章绪论基础。第三章论述了如何实现对u s b 闪存盘中文件的操作。第四章详细分析了n a n df l a s h 的特性，并根据这些特性实现了适用于n a n df l a s h 的f a t l 6 文件系统。第五章简单描述了嵌入式系统同u s b 闪存盘进行文件拷贝的过程。最后一章“结束语”对本文研究工作做了总结，并说明所做工作在实际应用中的意义。第二章文件系统剖析第二章文件系统剖析要实现u s b 设备和嵌入式设备本身的n a n df l a s h 之间的文件交互，首先必须对文件系统有深刻的了解。本章从用户使用角度和文件系统设计者角度详细阐述了文件系统的外在表现形式和实现机制，从而对文件系统形成一个清晰的认识，这样才能针对嵌入式设备存储介质的不同和应用场合的不同设计出高效、安全的文件系统。2 1 文件本节从用户角度来考察文件，也就是怎么使用文件，它具有什么样的特性。2 1 1 文件命名文件是一种抽象的机制，它提供了一种在存储介质上保留信息而且方便以后读取的方法。这种方法可以使用户不用了解存储信息的方法、位置和实际存贮介质的控制方式等有关细节。对被管理的对象的命名方法可以称为抽象机制的最重要的特性。所以，本文将从对文件的命名来考察文件系统。当用户程序创建文件时，它给出文件名。当用户程序中止后，文件会仍旧存在，其他程序可以通过文件名对这个文件进行存取。文件的具体命名规则在各个系统中是不同的，不过通常各种文件系统都允许1 至8 个字母组成的字符串作为合法文件名，有的文件系统区分大小写字母但有的不区分，w i n d o w s 下的f a t 文件系统不区分字母的大小写。很多文件系统支持旬点隔开为两部分的文件名，如p r o g c o 句点后的部分称为文件的扩展名( f i l ee x t e n s i o n ) ，通常文件扩展名表示文件的一些信息，通常的一些文件扩展名及其含义在表2 1 中列出。表2 1 常用文件扩展名及其含义扩展名意义f i l e b a k备份文件f i l e b i n可执行二进制文件f i l e cc 源程序文件f i l e d a t数据文件f i l e d o c文档文件f i l e f i nf o r t r a n 源程序f i l e h l p帮助文件f i l e 1 i b链接程序采用的o b j 文件库6n a n df l a s h 与u s b 闪存盘之间的数据交互f i l e m a n联机手册f i l e o b j目标文件( 编译器输出但未链接)f i l e p a sp a s c a l 文件f i l e r e x用于t e x 格式化程序的输入f i l e t x t一般文本文件文件扩展名在某一些情况下只是一种约定，不强迫采用。名字为f i l e t x t 的文件也许是文本文件，这个文件名主要是用于提醒用户，大多情况下并不传送特别的信息给计算机。对于可以处理若干种不同的文件的某个程序，这类约定是特别有用的。如c编译器，它可以编译，链接多种文件，其中有c 文件，或者汇编语言文件。扩展名这是就很有必要，编译器利用它能够区分哪些是c 文件，哪些是汇编文件，哪些是其他文件。2 1 2 文件存取早期的文件系统只有一种文件存取方式：顺序存取( s e q u e n t i a la c c e s s ) 。程序在这些系统中可以从开始处顺序读取文件全部字节或记录，但不能跳过某一些内容也不能非顺序读取。在存储介质是磁带而不是磁盘时，顺序存取文件是相当方便的。当磁盘被用来存储文件后，磁盘存储文件中的字节或记录可以被非顺序地读取，或按照关键字而不是位置来存取记录。这种能够以任何次序读取其中字节或记录的文件成为随机存取文件( r a n d o ma c c e s sf i l e ) 。随机存取文件对很多应用程序而言是必不可少的，如数据库系统。如果乘客打电话预定某航班机票，订票程序必须能够直接存取该航班记录，而不必读出其他航班的成千上万个记录。有两种方法指示从何处开始读取文件。一种是r e a d 每次操作都给出开始读取文件的位置。另一种是用一个特殊的s e e k 操作设置当前位置，从这个当前新位置顺序地开始读文件。一些早期大型机操作系统创建文件时，要指定是顺序还是随机存取文件。操作系统对这两种文件采用不同的存储技术。但现在操作系统则不加区别，文件创立后，全部文件自动地成为随机存取文件。2 1 3 文件属性文件都有文件名和数据，而且所有的文件系统在文件中保存其他的信息，如，文件创建日期，长度等等。这些其他项目称为文件属性( a t t r i b u t e ) 。文件的属性在不同的系统中差别很大。一些有可能的属性在表2 2 中给出，但也有存在其他第二章文件系统剖析7的属性。不存在具有全部这些属性的系统，但每种属性都在某种系统中采用。表2 2 文件属性字段含义保护谁能访问该文件，以何种方式访问口令访问该文件所需口令创建者文件创建者的标识所有者当前所有者只读标志0 表示读写，1 表示只读隐藏标志0 表示正常，1 表示不在列表中显示系统标志0 表示正常文件，1 表示系统文件存档标志0 表示已备份过，l 表示需要备份a s c i f 二进制0 表示a s c i i 文件，1 表示二进制文件标志随机存取标志0 表示顺序存取，l 表示随机存取临时标志0 表示正常，1 表示在进程结束时删除文件锁标志0 表示未锁，1 表示己上锁记录长度一个记录的字节数关键字位置每个记录中关键字偏移关键字长度关键字段的字节数创建时间文件创建日期和时间最后存取时间文件最后存取的日期和时间最后修改时间文件最后修改的日期和时间当前长度文件字节数最大长度文件最大允许字节数前4 个属性和文件保护相关，它指出谁可以存取这个文件，谁不可以存取这个文件。有不同的各种文件保护方案，在一些系统中用户必须给出口令才能存取文件，这时口令也是文件属性之一。标志是一些位或短的字段，用于对某些特殊属性禁止或允许，如，隐藏属性表明文件不在文件列表中出现。记录文件是否备份过用存档标志位。执行备份后该标志位清除，若文件被修改，系统设置存档标志位。用这种方法，备份程序可知道哪些文件要备份。临时标志位表明当创建该文件的进程中止时，文件会自动删除。有关记录长度，关键字位置和关键字长度字段，出现在只能用关键字查找记录的文件里，它们提供了所需的查找关键字信息。n a n dn a s h 与u s b 闪存盘之间的数据交互有关时间字段记录了文件的创建时间，最近访问时间以及最近修改时间等。每个时间字段的作用不同，如目标文件生成后，若修改了源文件，则需要重新编译目标文件，时间字段提供了必要的信息。当前长度字段给出了当前的文件的大小，在一些大型机文件系统中文件被创建时，要给定出文件的最大长度，以便系统事先按最大长度留出存储空间。微型机和个人计算机则不需要这一点。2 1 4 文件操作使用文件的目的是存储信息并方便以后检索。对于存储和检索，不同系统提供了不同的操作。以下是与文件有关的最常用的一些有代表性的操作：1 c r e a t e 。创建无任何数据的文件。该调用的目的是表示文件存在，并且设置一些属性。2 d e l e t e 。在不再需要文件时，必须删除以释放磁盘空间。任何文件系统都有一个自己的函数来删除文件。3 o p e n 。在使用文件之前，必须先打开文件。o p e n 调用的目的是：把文件属性和存储介质地址表存入内存，便于后续系统调用的快速存取。4 c l o s e 。存取结束后，不再需要文件属性和磁盘地址，这时应该关闭文件以释放内部表空间，有些文件系统限制用户打开的文件的个数，以鼓励用户关闭不再使用的文件。5 r e a d 。在文件中读数据。一般，读出的数据来自文件的当前位置。调用者必须指明需要读取多少数据，并且提供存放这些数据的缓冲区。6 w r i t e 。对文件写数据，写操作一般也是从文件当前位置开始。如果当前位置是文件末尾，文件长度增加。如果当前位置在文件的中间，则现在数据被覆盖，并且永远丢失了。7 a p p e n d 。此调用是w r i t e 的调用形式，它只能在文件末尾添加数据。若系统只提供最小系统调用集合，则通常没有a p p e n d 。很多系统对同一操作提供了多种实现方法，这些系统中往往有a p p e n d 调用。8 s e e k 。对于随机存取文件，要指定从何处开始读写数据，通常的方法是通过s e e k 系统调用把当前位置指针指向文件中特定位置。s e e k 调用结束后，就可以从该位置读写数据了。9 g e ta t f r i b u t e s 。程序的运行常需要读取文件属性。此调用就是用来获得文件的属性。1 0 s e ta i t r i b u t e s 。文件创建之后，用户可以通过此系统调用设置文件的一些属性。1 1 r e n a m e 。用户常常要改变文件的名字。可以调用r e n a m e 系统调用第二章文件系统剖析9达到这一目的。2 2 目录文件系统通常提供目录用于记录文件。目录本身在很多系统中也是文件。本节讨论目录，它的组成，特性和可以进行的操作。2 2 1 层次目录系统通常一个目录包含很多项，成为目录项，每个目录项代表一个文件。图2 1 a中是一种可能的情形，其中每个目录项包含文件名、文件属性和文件数据在存储介质上的地址等等。另一种情况如图2 1 b ，这里，目录项中含有文件名和指向另一个数据结构的指针，文件属性和在存储介质中的地址就存放在这个数据结构之中。以上两种系统都得到了广泛的应用。g a m e s属性m a i l属性n e w s属性w o r k属性包含属性的数据结构图2 1 目录项存储方式在打开文件时，文件系统先查找目录，直到找到要打开文件的文件名。然后从目录项或目录项所指向的数据结构里取得文件属性和在存储介质中的地址，放到内存的相应记录中，以后对该文件的操作都采用内存中的信息。目录数目在每个系统中各不相同。最简单的设计是系统仅维护一个单独的目录，包含用户的全部文件，如果有很多用户采用相同的文件名，会出现冲突和混乱，这一模型只适用于简单的系统中。对系统采用单目录管理文件的改进思想是，每个用户拥有一个目录。这类设计消除了用户之间的文件名冲突，但仍然难以使很多文件的用户感到满意。用户常常需要把文件按某种逻辑方式组织起来。这时需要某种方法，使用户可以按自己选择的方式把文件分别组织起来。最终需要的是一般的层次( 即目录树) 。采用层次结构，每个用户可以拥有多个所需的目录，自然地组织他们的文件，如图2 2 所示1 0n a n df l a s h 与u s b 闪存盘之间的数据交互目录图2 2 目录层次结构图中，根目录含有目录a ，b ，c ，分属不同用户，其中有两个用户为他们的项目创建了子目录。2 2 2 路径名用目录树组织文件系统时，需要某种方法指明文件名。常用的方法有两种。第一种是，每个文件都赋予一绝对路径名，它由从根目录到文件的路径组成。绝对路径名一定从根目录开始，且是唯一的。另一指定文件名的方法是相对路径名。它常和工作目录( 也成当前目录) 一起采用。用户可以指定一目录作为当前工作目录。这时不从根目录开始的所有的路径名都是相对于工作目录的。一些程序需要存取某个特定文件，而不论当前目录是什么。这时，应该采用绝对路径名。不论当前工作目录是什么，绝对路径名总能正常工作。支持层次目录结构的大多数文件系统，在每个目录中都有两个特殊的目录项搿 和“。，通常读做“d o t 和“d o t d o t ”。d o t 指当前目录，d o t d o t 指其父目录【4 1 。2 2 3 目录操作不同文件系统中管理目录的系统调用差别比较大，比管理文件的系统调用差别要大。尽管如此，为了了解这些系统调用及他们怎样工作，下面给出一些一般性的抽象函数。1 c r e a t e 。创建目录。除了目录项“ 和“。 外，目录内容为空。目录项“”和“。 是系统自己放到目录中的。2 d e l e t e 。删除目录。在有些系统中只有空目录可删除。只有“ 和“的目录被认为是空目录，这两个目录项不能被删除。第二章文件系统剖析3 o p e n d i r 。目录内容可被读取。如，为列出目录中全部文件，程序须先打开该目录，然后读其中全部文件的文件名。同打开和读文件相同，在读目录前，须打开目录。4 c l o s e d i r 。读目录结束后，应关闭目录以释放内存空间。5 r e a d d 瓜。系统调用砌弘d d 瓜返回打开目录的下一个目录项。6 r e n a m e 。在很多方面目录和文件都相似。文件可换名，目录也可。2 3 文件系统的实现现在从用户角度转到实现者角度来考察文件系统。用户关心的是文件是怎样命名的，可以进行哪些操作，目录树是怎样的以及类似的界面问题。而实现者感兴趣的是文件和目录是怎样存储的，磁盘空间是怎样管理的以及怎样使系统有效而可靠的工作等等。2 3 1 实现文件实现文件存储的关键问题是记录各个文件分别用到哪些存储介质块。不同的系统采用不同的方法。下面列举其中几种方法。1 连续分配最简单的分配方法是把每个文件作为连续数据块存储到存储介质上。例如，在块大小为1 k 的存储介质上，5 0 k 的文件要分配5 0 个连续的块。这一分配方案有两大优势。首先，简单，容易实现，记录每个文件用到的存储介质块简化为只需记住一个数字即可，也就是第一块的地址。其次，性能好，在一次操作中，就可以从磁盘上读出整个文件。但是，连续分配方案中也有同样明显的两大不足。首先，除非在文件创建时就知道文件的确切长度，否则这一方案行不通。不知道文件的最大长度，文件系统就不知道要保留多大的存储介质空间。但是，在那些文件长度已知的情况下，连续分配的优势可以得到充分利用。第二个不足之处是：该分配方案会造成空间碎片。浪费了原来可以采用的空间。2 链表分配存储文件的第二种方法是为每个文件构造存储介质块的链表，如图2 3 所示。每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。与连续分配方案不同，这类方法可以利用每个存储介质块，不会因为碎片而浪费存储空间，同样，在目录项中，只需要存放文件第一块的地址，文件的其他块可以从这个首地址查找。另方面，在链表分配方案中，尽管顺序读取文件非常方便，但是随机存取1 2n a n df l a s h 与u s b 闪存盘之间的数据交互却相当缓慢。而且，因为指针占用了一些字节，每个存储介质块存储数据的字节数不再是通常的2 的幂次方，虽然这个问题并不是非常严重，但它确实降低了系统的运行效率，因为许多程序都是以长度为2 的幂次方来读写存储介质块的。文件块2文件块3物理块4721 01 2图2 3 按存储介质块链表来存储文件3 采用索引的链表分配如果取出每个存储介质块的指针字，把它放到内存的表或索引中，就可以解决上述链表的两个不足。如果按这类方式组织，整个块都可以存放数据。再者，随机存取也容易的多。要查找文件，只要给出偏移位置，虽然仍要顺着链表进行查找，但是整个链表都存放在内存中，不需要访问存储介质( 访问文件存储介质的速度要比内存慢得多) 。与以前的方法相同，不管文件有多大，在目录项中只需记录一个整数( 起始块号) ，按照它就可以找到文件的全部块。这类方法的主要缺点是必须把整个链表都存放到内存中。对于大的存储介质，例如具有5 0 00 0 0 个1 k 大小块( 5 0 0 m ) 的f l a s h ，其中链表中含有5 0 00 0 0 项，每个项至少3 个字节，为了提高查找速度，有时需要4 个字节。这样，取决于空间或时间的优化方案，这张表要占1 5 m 或2 m 内存。4 i 节点第四种记录各个文件分别包含哪些存储介质块的方法是给每个文件赋予一张成为i 节点的小表，其中列出了文件属性和文件中各个块在存储介质上的地址。开始几个存储地址存放在i 节点内，所以对于小文件，所需信息均在i 节点中，在打开文件时，这些信息从文件存储介质中读入内存。稍大一些的文件，在i 节点中存在有一个成为一次间接块的文件存储介质块地址，这个块中含有附加的存储介质地址，如果文件再变大，可以采用i 节点中的另一个地址，即二次间接块的地址，二次间接块包含有很多一次间接块的地址，而每个一次间接块又指向数百个数据块。如果这还不够的话，还有三次间接块。2 3 2 实现目录在读文件以前，必须先打开文件。打开文件时，文件系统利用用户给出的路径名找到相应目录项，目录项中提供了查找文件存储介质块所需要的信息。因实现方式而异，这些信息有可能是整个文件的存储地址( 连续分配方案) ，第一个第二章文件系统剖析块的块号( 对于两种链表分配方案) 或者是i 节点的节点号。无论怎样，目录系统的主要功能是把a s c i i 文件名映射成查找文件数据所需的信息。与此密切相关的问题是在何处存放文件属性。一种较明显的方法是把文件属性直接存放在目录项中，很多系统确实是这样做的。对于采用i 节点的系统，还存在另一种方法，即把文件属性存放在i 节点而不是目录项中。下面是层次目录结构的一种实现方法。图2 4 是f a t 系统的目录项。它总共3 2 个字节，其中包含了文件名，文件属性和第一个存储介质块的块号，根据该块号可以在f a t 表中找到文件其他所有的块。83l1 02224i文件名令珍黝太i 弋ll上长度图2 4f a t 目录工贞在f a t 系统中，目录可以包含其他目录，从而形成层次文件系统。2 3 3 存储空间管理存储空间的管理是文件系统设计者要考虑的主要问题。存储n 个字节的文件可以有两种策略：分配n 个字节的连续的存储空间，或者把文件分成很多个( 并不一定要) 连续的块。在存储管理中，单纯段式和分页也要进行同样的权衡。按连续字节序列来存储文件的一个明显问题是当文件扩大时，有可能需要在存储介质上移动文件。内存中分段也存在同样的问题。不同的是，相对于把文件从存储介质的一个位置移动到另一个位置，内存中的段移动操作要快得多。由于这个原因，几乎所有的文件系统都把文件分割成固定大小的块来存储，各个块之间不一定相邻。一旦决定把文件按固定大小的块来存储，就会有块的大小应该是多少的问题，如果分配大小很大，因为分配给文件的最小单位就是块，所以这时每一个文件，甚至是1 个字节的文件，都要占用一个块的大小。另一方面，块分的很小意味着每个文件由很多个块组成，每读一块都要查找该块的位置，所以读取由很多小块组成的文件的速度很慢。所以在设计文件系统时，如何划分块的大小，要根据实际应用的需要，在速度和空间之间找到一个平衡点。一旦选定了块的大小，下一个问题就是怎样跟踪空闲块。有两种方法被广泛的采用。第一种方法采用存储介质块的链表。每个块中包含尽可能多的空闲磁盘块号。对于1 k 大小的块和1 6 位的磁盘块号，空闲块链表中每个块包含有5 1 1 个1 4n a n df l a s h 与u s b 闪存盘之间的数据交互空闲块块号。2 0 m 的存储介质最多需要4 0 个块的空闲链表来存放全部2 0 k 个块号。通常情况下，采用空闲块存放空闲块链表。另一种空闲块管理的方法是采用位图。在位图中空闲块用l 表示，分配块用0 表示( 或者反之) 。2 0 m 的存储介质空间需要2 0 k 位来表示，即只需3 个块。很明显，位图方法所需空间要少于链表方法所需空间，因为每块只用一个二进制位表示，而在链表方法中，记录每个块要用到1 6 位，只有在磁盘空间快满时链表方案需要的块比位图少。如果有足够的内存来存放位图，则这类方法无疑是非常好的。但是，如果只有一个块的内存可以用来记录空闲存储块，并且空闲存储块很少，这时选择链表方案更好。假设内存中只存放一个块的位图，则有可能在这个位图表中根本找不到空闲块。这时，就要从存储介质中调入其他位图块。相比之下，当把一个空闲块链表装入内存后，在调入下一个链表块之前，可以进行多达5 1 1 次的分配。2 3 4 文件系统的可靠性文件系统应该保证其所管理的文件的安全，应当具有一定的健壮性，如果文件系统太脆弱，经常崩溃的话，恢复全部信息是一项困难而又费时的工作，很多情况下这根本是不可能的。尽管文件系统不能抵御设备和媒体的物理性损坏，它至少在软件方面能够保护信息。下面讨论一些文件系统应该注意的一些问题。1 坏块管理存储容量大且没有坏块的存储介质是很昂贵的，不利于广泛的应用。所以一些存储介质常常有坏块，象n a n df l a s h 往往出厂时就有一些坏块，在使用过程中一些块也会变坏。对坏块问题有软件和硬件两种解决方法。硬件方法是由硬件内部逻辑来管理坏块，自动用空闲块来代替坏块，这种情况下文件系统不需要考虑坏块问题，但这种方法硬件成本高，且有些硬件没有实现。软件解决方法是要求文件系统精心地构造一个包含全部坏块的表或文件。这类技术可以将坏块从记录空闲块的表中删除，使其不会分配给文件使用。只要不在坏块上读写文件，文件操作就不会出现任何问题。2 备份即使有再好的处理坏块的策略，经常地备份文件也是很重要的。在嵌入式系一般不将整个文件系统进行备份，而是将存储有关键信息的存储块进行备份，这样可以保证关键块损坏后，文件系统不至于崩溃。3 文件系统的一致性影响文件系统可靠性的另一个问题是文件系统的一致性。很多文件系统读取存储介质块，进行修改后，再写回。如果在修改过的磁盘块全部写回之前，系统断电或出现其他意外情况，则文件系统有可能处于不一致状态 4 】。如果一些未被第二章文件系统剖析写回的块是i 节点块，目录块或包含空闲表的块时，这个问题尤为严重。为了解决文件系统不一致问题，很多系统都带有一个实用程序以检验文件系统的一致性。当系统启动时，特别是意外断电后重启，可以运行该程序进行一致性检查。下面介绍在采用i 节点系统中这个程序是如何工作的，其他大多数系统的工作原理和它类似。一致性检查分为两种：块的一致性检查和文件的一致性检查。在检查块的一致性时，程序构造一张表，表中为每个块设立一个计数器，两个都初始化为0 。第一个计数器跟踪该块在文件中出现的次数，第二个计数器跟踪该块在空闲表中出现的次数。接着检验程序读取全部的i 节点，由i 节点可以建立相应文件中使用的全部块的块号。每读到一个块号时，该块在表中的第一计数器加1 。然后该程序检查空闲块链表或位图，查找全部未采用的块，每当在空闲表中找到一个块时，它在表中的第二计数器加l 。如果文件系统一致，则每个块或者在表中的第一计数器为1 ，或者在表中第二计数器为1 ，如图2 5 a 所示( 第一，第二计数器各一张表) 。但当系统崩溃后，这两张表可能如同图2 5 b 所示。图中存储块3 没有在任何一张表中，这称为丢失。尽管块丢失不会造成损害，但它的确浪费了存储空间，丢失块问题解决很容易：文件系统检验程序把它们加到空闲表中即可。有可能出现的另一种情况如图2 5 c 所示。其中，在空闲表中存储介质块5 出现了两次( 只有在空闲表是真正意义上的一张链表时，才会有重复，在位图中，不会发生这类情况。) 解决方法也很简单：只要重新建立空闲表即可。块号块号口正巨口正圈使肿的块日巫e 匝亚皿空闲块a )块号l234567891 0口互五日丑珊使肿的块口互亚圈丑卿空闲块c 、使用中的块空闲块使用中的块空闲块图2 5 文件系统状态a ) 一致b ) 块丢失c ) 空闲表中有重复块d ) 重复数据块最糟糕的情况是，在两个或多个文件中出现同一个数据块，如图2 5 d 中的块6 。如果其中一个文件被删除，会添加块6 到空闲链表中，导致同一个存储块同时1 6n a n df l a s h 与u s b 闪存盘之间的数据交互处于使用中和空闲两种状态。若删除其中两文件，在空闲表中这个磁盘块会出现两次。文件系统检验程序可以这样来处理：先分配一个空闲块，把存储块6 中的内容复制到空闲块中，然后把它插到其中一个文件中。这样文件的内容未改变( 虽然这些内容几乎可以肯定是不对的) ，但至少保持了文件系统的一致性。这一错误应该报告，由用户检查。最后，另一种可能是一个块在文件中和空闲表中同时存在，解决方法很简单：将它从空闲表中移除。除检查每个存储器块外，文件系统检验程序还检查目录系统。此时也要用到一个计数器表，但这时是一个文件对应一个计数器而不是一个块对应一个计数器。程序从根目录开始检验，沿着目录树下降递归，检查文件系统中的每个目录。对每个目录中的文件，其对应的i 节点计数器加1 。检查全部完成后，得到对应每个i 节点号的一张表。表中给出指向某i 节点的目录数目，然后，检验程序将这些数字与存储在文件i 节点中的连接数目相比较。如果文件系统一致，这两个数目应相等。但是，两种错误有可能出现，在i节点中的链接数太大或太小。如果i 节点的连接数大于指向i 节点的目录现个数，这时即使相关目录中的文件都被删除，文件连接数仍i h ! t b - 0 ，不会删除文件i 节点。该错误并不严重，却浪费了存储空间因为存在不再任何目录中的文件。为改正这一错误，可以把i节点的文件连接数设成正确值。如果正确的值是o ，文件应该被删除。另一个错误则是潜在的灾难。如果同一文件链接两个目录项，但其i 节点连接数只为1 ，如果文件从任何一个目录项删除，i 节点连接数变为0 。文件系统标志该i 节点为“未采用 ，该文件的全部存储器块被释放。这会导致另一目录指向一未采用的i 节点，而很有可能其存储器块马上分配给其他文件，改正方法同样是把i 节点中的连接数设为目录项的实际数目。2 3 5 文件系统的性能访问文件存储块要比访问内存慢的多。由于存取时间的差异很大，所以在设计时，文件系统应尽量减少存储块访问次数。最通常减少磁盘访问次数技术是块高速缓存。高速缓存在这里是一些块，逻辑上它们属于文件存储器，但基于性能的考虑被保存在内存中。管理高速缓存用到了不同的算法。通常算法是：检查全部的读请求，检查在高速缓存中是否有所需要的块。如果在，可进行读操作无须访问存储器块。如果高速缓存中该块不存在，要把它首先读到高速缓存中，然后对该块的请求都通过高速缓存来完成。第二章文件系统剖析1 7如果高速缓存已满，此时需要调入新的块，要把某一原来的块调出高速缓存。如果自上次调入以后要调出的块做过修改，则要把它写回存储器块。这种情况跟虚拟内存的分页机制矧非常相似。所以全部的分页算法，例如f i f o 算法，第二此机会算法，l r u 算法等等都适用于高速缓存。不同之处在于，高速缓存引用相对较少，所以可以把全部块用链表按精确的l r u 顺序链接起来。虽然在这类情况下可以用精确的l r u 算法，但又带来了问题，这于前一节讨论的系统崩溃和文件一致性有关。如果一关键块比如i 节点块，读到高速缓存并做出修改，但是没有写回存储器块，这时，系统崩溃会导致文件系统的不一致。如果把i 节点块放在l r u 链表的尾部，在它到达链首并写回存储器块之前，有可能要相当一段时间。再有，某一些磁盘块，如两次间接块，很少在一个短的时间内被引用两次。基于这些考虑，需要修改l r u 方案，并注意如下两点：1 ) 这一块是否不久要重新采用?2 ) 这一块是否关系到文件系统的一致性?考虑以上两个问题时，可将块分为i 节点块，间接块，目录块，全数据块，部分数据块等等几类。把有可能最近不再需要的块放在链表的前部，于是很快缓冲区又可采用。对有可能不久将采用的块，可放在链表的尾部，正在写的如部分数据块，这样它们能在高速缓存中保存一段较长时间。与前一个相对独立的是第二个问题。如果关系到文件系统的一致性( 除数据块之外，其他块基本上都是这样的) 的模块被修改，都应该立即将该块写回存储器块，不管它是否在链表尾部。将关键块迅速写回存储器块会大大减少在意外情况发生时文件系统被破坏的可能性。仔细安排关键块写入的顺序的写入顺序是很重要的。尽管用这类方法可以保证文件系统一致性不受破坏，但实际应用中一般不希望数据块在高速缓存中放很久之后才写回文件存储器，因为这样当意外断电时，虽然文件系统不会被破坏，在高速缓存中的还没来得及写回文件存储器的内容会全部丢失。解决此问题也有两种方法，一是间隔一定的时间，如3 0 秒，将修改过的高速缓存写回文件存储器，另一种方法是当高速缓存被修改时候立即将其写回，这种方法虽然不会造成数据丢失，但其要求频繁地访问文件存储器这种慢速设备，所以效率不高。2 3 6 小结以上从分别从使用者角度和设计者角度对文件系统进行了分析，从使用者角度看，文件系统是一组文件和目录以及对文件和目录的操作。文件可以被读写，1 8n a n dr a s h 与u s b 闪存盘之间的数据交互目录可以被创建、删除，并可以将一个文件从一个目录移到另一个目录中。文件命名、结构、分类、存取和属性都是重要的设计问题。从内部看，文件系统又是另一番景象。文件系统的设计者必须考虑存储器块分给哪个文件，存储空间是怎样被管理的。目录可以按不同的方式组织，可以把名字、属性和存储地址放在一起，也可以只放一个名字和i 节点号。坏块管理、一致性问题和高速缓存也是很重要的问题。只有在充分了解了文件系统的内部机制之后，才可以考虑如何才能解析出u s b 闪存盘中的文件，如何能够向其写入文件，使文件格式与w i n d o w s 兼容，这样才能在p c 与嵌入式系统之间进行文件的交互。实现这些的同时也要考虑u s b 闪存盘中文件系统的安全性、一致性及效率问题。在下面的章节中主要讨论u s b 闪存盘中的文件系统及其数据传输。第三章u s b 闪存盘的数据传输及其文件系统1 9第三章u s b 闪存盘的数据传输及其文件系统要在嵌入式系统中实现对u s b 闪存盘中文件的操作，首先必须清楚嵌入式文件系统的层次结构，这样才能清楚要实现对u s b 闪存盘中文件的读取，写入等操作所需要解决的问题。3 1 嵌入式文件系统的层次结构与a n s ic 标准相对应，一般将嵌入式文件系统分为3 个层次。第一层次，a p i 层。a p i 层是文件系统与用户应用程序之间的接口，包含一个与文件函数相关的函数库，如f o p e n 、f w r i t e 等，也相当于h i g hl e v e l 层。这是与用户直接相关的层，用户不关心u s b 闪存盘中是什么样的文件系统，也不关心嵌入式系统是如何通过u s b 接口控制u s b 闪存盘的，其关心的只是几个特定的操作文件的函数，