大容量内存文件系统设计及μC/OS下的实现 02 如何, 信息

samwalton

从图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值在基本表中越分散，因而比较次数相应较少。