大容量内存文件系统设计及μc-os下的实现

《大容量内存文件系统设计及μc-os下的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大容量内存文件系统设计及μC/OS下的实现

2、第1关键词：嵌入式系统内存文件系统大容量存储μC/OS引言嵌入式系统凭借其特有的功能和资源占用量少的特点，在各个领域得到了越来越多的应用。根据成本和设计的需要，一般的嵌入式系统都配置很少的外部存储空间甚至不带外部磁盘。但随着用户需求和功能复杂度的增加，越来越多的嵌入式系统需要处理大容量的数据，或者在运行过程中会产生大量的临时数据。一方面这些数据处理完后不能立即删除；另一方面这些临时文件不需要长期保存。例如，用来上网冲浪的机顶盒设备在用户浏览过程中不断从互联网上接收数据，因此用户访问后的页面很可能再次浏览，所不能将浏览后的网页立即

3、清除，当然，系统不需要也不可能将所有浏览过的页面保存于硬盘中。所以，处理数据量的增大给嵌入式系统的设计提供了新的要求。一般来说，嵌入式系统处理大容量临时数据的有效方法是设计一个内存文件系统存储这些数据。内存文件系统MFS（MemoryFileSystem）是一个在内存中对文件实行按名存取的底层软件。和普通磁盘文件系统相比，内存文件系统具有存取速度快、可动态改变文件系统大小和数据掉电即丢失的优点，因此它适用于高速的临时数据处理。Linux下的Tmpfs、Proc文件系统以及Freebsd下的MFS都是一种内存文件系统。但是，这些通用操作系统上的内存文件系统不能够直接运用于到

4、嵌入式系统中：其一，它们都是为资源丰富的通用PC平台设计的，不适用于资源有限的嵌入式系统；其二，这些通用内存文件系统的设计方案一般是利用内存来模拟磁盘文件系统，在内存中会建立文件系统缓冲区。这就是说除了文件系统本身占据了内存之外，磁盘缓冲区又会占所一些内存，这些就会导致内存的浪费和利用率的下降。根据上述考虑，本文设计了一适合于嵌放式大容量数据处理的嵌入式内存文件系统EMFS（FmbeddedMomoryFileSystem）。文中首先阐述了EMFS嵌入式系统的设计要点，随后讨论了如果将其移植到μC/OS系统，最后对其性能进行了分析和测试。1EMFS的设计从前面分析得知，本

5、文设计的EMFS不采用通用文件系统的磁盘设计方法，如Linux系统的Ext2节点结构和FS在内存中的组织结构。每一个存储于EMFS的文件在全局Hash表都有个对应的入口项。其文件属性和文件名、文件长度、创建时间等存入文件状态表，文件内容存储于从空闲块链表申请到的数据块中。文件的Hash表、状态表和数据块通过指针链接起来，如图2所示，下面分别介绍文件系统的Hash表、状态表和数据块链表。1.1全局Hash表（1）Hash值的产生从图2可看出，Hash表是整个文件系统读写和查找的入口，通过计算文件的Hash值来找到其在Hash表中的位置，从而访问文件状态表和数据块。因此文件系

6、统的查找效率主体现在，如何通过文件信息计算其对应的Hash值以及如何有效地组织Hash表。图3表示了EMFS系统中Hash表的构成情况，每个文件对应8字节的Hash值。其中前2个字节是文件名长度和文件名第一个字节的ASCII码值，接下来的2个字节是文件名的16CRC（循环冗余校验编码），最后4个字节文件名的32CRC编码。这里为了减少同文件对应相同Hash值的概率，文件名的Hash值中既包含了文件名的16CRC编码又包含了32CRC编码。（2）Hash表的组织和查找在获得Hash值后，如何将8个字节的Hash值有效地组织在全局Hash表中来获得最高的查找速度是一个关键问题

7、。根据数据结构算法理论可知，将Hash表顺序组织为一个有序表，可以通过折半查找法来获得最高的查找效率。其比较次数最多为└log2n┘+1（n为表中的记录个数），其平均查找长度ASL（AverageSearchLength）近似为log2(n+1)-1。然而，随着文件的动态增加或删除，每个文件对应的Hash值或大或小，这样系统的Hash表并不能保证是一个顺序表，因此就不能采用折半查找法。如果首先将无序的Hash表排列为有序表再采用折半法查找，那么即使在最好的情况下，排序操作所需要的时间复杂度也为O（nlogn），同时还需要其它的辅助存储，这样在排序操作上就要花费大量的时间和

8、存储空间，使整个系统的查找效率大大降低。针对此不足，本文采用链地址法组织全局Hash表，将全局Hash表分为两部分：其本表和溢出表。其基本思想为：首先分配一个固定大小（这里假设取1024项）的顺序表作为基本表，每个文件计算得出的Hash值通过对1024取模得到个介于0～1023之间的模值。如果此模值在基本表中的对应项没有被占用，那么该项就作为此文件的Hash项；如果此模值在基本表中的对应项已被其它文件占用，那么就溢出表中申请一个此文件的Hash项，并将此Hash项链接到具有相同模值的链表中。通过这种顺序表和链表相结合的结构，既