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

摘要：针对某些嵌入式系统中处理数据量大和速度要求高的特点，提出一种应用于嵌入式系统中的大容量内存文件系统的实现方案。该方案通过在内存中建立文件系统，将临时数据有效组织于内存中，既提高访问速度又节省外存空间，因而能满足要求；通过将其移植到μ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项）的顺序表作为基本表，每个文件计算得出的Hash值通过对1024取模得到个介于0～1023之间的模值。如果此模值在基本表中的对应项没有被占用，那么该项就作为此文件的Hash项；如果此模值在基本表中的对应项已被其它文件占用，那么就溢出表中申请一个此文件的Hash项，并将此Hash项链接到具有相同模值的链表中。通过这种顺序表和链表相结合的结构，既会影响查找速度又不会增加额外存储空间，从而提高EMFS的查找效率而且不增加系统的时间和空间复杂度。

1.2 文件状态表

文件状态表用来存放文件系统中文件的各个属性，包括文件名称、文件大小、读写标志、创建和修改时间。同时，为了提高内存空间的利用率，可以对文件进行选择性压缩存储，因此文件状态表也包括文件压缩标志，压缩前的原始大小和压缩后的文件大小。从图2可以看到，文件状态表是和Hash表以及数据块链表连在一起的，那么一旦定位到文件对应的Hash项，就可以对文件状态表进行读写。

1.3 数据块链表

在EMFS中，文件数据内容保存在内存数据块中，内存数据块的大小可以在建立文件系统时动态设定。数据块链表的作用是对内存块进行管理。由于数据块链表中每一项对应一个内存块，所以当添加文件时，系统根据文件大小动态地从数据块链表中申请一定数量的数据块；当删除文件时，系统将数据块插入到此链表中。

2 EMFS在μC/OS系统下的实现和性能分析

2.1 EMFS是μC/OS下的实现流程

μC/OS是一个多任务的实时性嵌入式操作系统，得到了广泛的使用。μC/OS公开了它的实时性内核源码，同时提供了内存管理的接口和函数。通过在其实时内核的基础上进行少量的修改，便可将EMFS移植到μC/OS系统中。图4是EMFS在μC/OS下的初始化流程。

初始化完毕后，在μC/OS系统中建立EMFS的三主要数据结构，随后就可以向EMFS中读写文件并进行测试。图5和图6分别是读写文件的流程。

2.2 EMFS的性能测试与分析

通过将EMFS移植到μC/OS系统，便可以对EMFS的性能进行分析。前面提到，EMFS的主要特点是有效高的查找速度和内存利用率。现在，从这两方面分别对EMFS进行性能测试和分析比较。

（1）平均查找次数

通过加入8000个平均长度为20KB的文件到EMFS中，这可以在对全局Hash表的基本表设定不同大小的情况下，随机地读出一定数量的文件来统计EMFS的平均查找次数。这里设定基本表的大小分别为1024和2048，读出文件数量分别为500、1000、2000、4000和8000个，平均查找次数的统计结果具体如表1所列。

读出文件数      查找次数 基本表项数	500	1000	2000	4000	8000
1024	1.204	1.489	1.942	2.974	4.904
2048	1.098	1.231	1.465	1.966	2.95

从表1可以分析出以下几点：

①8000个文件全部读出所需的平均查找次数最多不到5次；而当Hash表采用顺序表时，使用拆半查找法得到的平均查找次数为└log28000┘+1=13次，可见EMFS的查找效率非常高，而且它不增加时间和空间的复杂度。

②读出的文件数量越少，平均查找次数越少。因为文件是随机选择的，故读出的文件越少，它们对应的Hash值在基本表中越分散，因而比较次数相应较少。

    ③基本表包含的Hash项越多，EMFS的平均查找次数越少。这是因为基本表越大，Hash值取模后落在基本表的概率就越大，因此比较的次数就越少。但要注意一点，在实际应用中基本表并不是设置得越大越好，基本表设置得越大，相应地溢出表就越小。当把溢出表项用完之后，基本表可以还没有用完，但这时已经不能够再添加文件了，这样系统效率反而会降低。

（2）内存利用率

EMFS的内存利用率可以从两个方面来表现：一对文件进行选择性压缩的机制；二是内存数据块大小的选择。

对文件进行压缩存储可以提高内存利用率，然而文件的压缩和解压需要耗费一定系统时间和资源，这在一定程序上会降低系统的性能，因此需对文件进行选择性压缩。具体方法是对文本等压缩比例高的文件进行压缩存储，对数据等压缩比例低的文件，则选择直接存储。

另外，对文件数据块大小的选择也会影响内存利用率。在EMFS中，文件数据存储的基本单位是一个内存数据真。这样，每个文件的最后一个数据块很可能会用不完，平均来看，每个文件会浪费1/2个数据块。在文件数据块为1KB和2KB的情况下，我们测试得到内存利用率分别为97.4%和94.8%。显然，前者的利用率更高，这是因为文件数据块越小，文件浪费的空间越少。但是，文件数据块不能设置得太小，否则系统在运行过程中会产生很多碎片，导致系统性能的降低。

3 结论

本文提出了嵌入式系统下的一种大容量内存文件系统的实现方案，并从文件的平均查找次数和系统内存利用率等方面对文件系统进行了测试和性能分析。测试结果表明，此系统具有较快的查找定位速度和较高的内存利用率，所以本系统能够有效地应用于嵌入式系统，尤其是那些产生较多临时文件或处理大容量数据的嵌入式系统。