- 相关推荐
大容量内存文件系统设计及μC/OS下的实现
摘要：针对某些嵌入式系统中处理数据量大和速度要求高的特点，提出一种应用于嵌入式系统中的大容量内存文件系统的实现方案。该方案通过在内存中建立文件系统，将临时数据有效组织于内存中，既提高访问速度又节省外存空间，因而能满足要求；通过将其移植到μC/OS系统下，便可进行性能测试和分析。结果表明，本内存文件系统具有较高的查找效率和内存利用率。引言
嵌入式系统凭借其特有的功能和资源占用量少的特点，在各个领域得到了越来越多的应用。根据成本和设计的需要，一般的嵌入式系统都配置很少的外部存储空间甚至不带外部磁盘。但随着用户需求和功能复杂度的增加，越来越多的嵌入式系统需要处理大容量的数据，或者在运行过程中会产生大量的临时数据。一方面这些数据处理完后不能立即删除；另一方面这些临时文件不需要长期保存。例如，用来上网冲浪的机顶盒设备在用户浏览过程中不断从互联网上接收数据，因此用户访问后的页面很可能再次浏览，所不能将浏览后的网页立即清除，当然，系统不需要也不可能将所有浏览过的页面保存于硬盘中。所以，处理数据量的增大给嵌入式系统的设计提供了新的要求。
一般来说，嵌入式系统处理大容量临时数据的有效方法是设计一个内存文件系统存储这些数据。内存文件系统MFS（Memory File System）是一个在内存中对文件实行按名存取的底层软件。和普通磁盘文件系统相比，内存文件系统具有存取速度快、可动态改变文件系统大小和数据掉电即丢失的优点，因此它适用于高速的临时数据处理。Linux下的Tmpfs、Proc文件系统以及Freebsd下的MFS都是一种内存文件系统。但是，这些通用操作系统上的内存文件系统不能够直接运用于到嵌入式系统中：其一，它们都是为资源丰富的通用PC平台设计的，不适用于资源有限的嵌入式系统；其二，这些通用内存文件系统的设计方案一般是利用内存来模拟磁盘文件系统，在内存中会建立文件系统缓冲区。这就是说除了文件系统本身占据了内存之外，磁盘缓冲区又会占所一些内存，这些就会导致内存的浪费和利用率的下降。根据上述考虑，本文设计了一适合于嵌放式大容量数据处理的嵌入式内存文件系统EMFS（Fmbedded Momory File System）。文中首先阐述了EMFS嵌入式系统的设计要点，随后讨论了如果将其移植到μC/OS系统，最后对其性能进行了分析和测试。
1 EMFS的设计
从前面分析得知，本文设计的EMFS不采用通用文件系统的磁盘设计方法，如Linux系统的Ext2节点结构和Windows的FAT结构。EMFS对文件的主要管理方式为：
①文件的各个属性单独存储在文件信息表（file status table）中；
②文件数据块用链表来分配和管理，文件数据块大小可以动态改变，这样可以避免在系统运行过程中产生大量的碎片；
③为了提高文件的读写和查找速度，设置一个全局散列表（Hash表）作为文件的读写及查找入口；每个文件根据其文件名、文件长度计算出一个Hash值；然后在Hash表找到文件对应的Hash项，这样就可以读出文件的属性和数据。
图1表示了EMFS在内存中的组织结构。
每一个存储于EMFS的文件在全局Hash表都有个对应的入口项。其文件属性和文件名、文件长度、创建时间等存入文件状态表，文件内容存储于从空闲块链表申请到的数据块中。文件的Hash表、状态表和数据块通过指针链接起来，如图2所示，下面分别介绍文件系统的Hash表、状态表和数据块链表。
1.1 全局Hash表
（1）Hash值的产生
从图2可看出，Hash表是整个文件系统读写和查找的入口，通过计算文件的Hash值来找到其在Hash表中的位置，从而访问文件状态表和数据块。因此文件系统的查找效率主体现在，如何通过文件信息计算其对应的Hash值以及如何有效地组织Hash表。图3表示了EMFS系统中Hash表的构成情况，每个文件对应8字节的Hash值。其中前2个字节是文件名长度和文件名第一个字节的ASCII码值，接下来的2个字节是文件名的16CRC（循环冗余校验编码），最后4个字节文件名的32CRC编码。这里为了减少同文件对应相同Hash值的概率，文件名的Hash值中既包含了文件名的16CRC编码又包含了32CRC编码。
（2）Hash表的组织和查找
在获得Hash值后，如何将8个字节的Hash值有效地组织在全局Hash表中来获得最高的查找速度是一个关键问题。根据数据结构算法理论可知，将Hash表顺序组织为一个有序表，可以通过折半查找法来获得最高的查找效率。其比较次数最多为└log2n┘ 1（n为表中的记录个数），其平均查找长度ASL（Average Search Length）近似为log2(n 1)-1。然而，随着文件的动态增加或删除，每个文件对应的Hash值或大或小，这样系统的Hash表并不能保证是一个顺序表，因此就不能采用折半查找法。如果首先将无序的Hash表排列为有序表再采用折半法查找，那么即使在最好的情况下，排序操作所需要的时间复杂度也为O（nlogn），同时还需要其它的辅助存储，这样在排序操作上就要花费大量的时间和存储空间，使整个系统的查找效率大大降低。针对此不足，本文采用链地址法组织全局Hash表，将全局Hash表分为两部分：其本表和溢出表。其基本思想为：首先分配一个固定大小（这里假设取1024项）的顺序表作为基本表，每个文件计算得出的Ha
【大容量内存文件系统设计及μC/OS下的实现】相关文章：
256×32大容量中文矩阵系统的设计03-18
基于闪存的星载大容量存储器的研究和实现03-18
B2C 电子商务网站的设计与实现03-01
试论将μC/OS-II用于单片机教学03-18