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

、创建时间等存入文件状态表，文件内容存储于从空闲块链表申请到的数据块中。文件的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（AverageSearchLength）近似为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中，文件数据内容保存在内存数据块中，内存数据块的大小可以在建立文件系统时动态设定。数据块链表的作用是对内存块进行管理。由于数据块链表中每一项对应一个内存块，所以当添加文件时，系统根据文件大小动态地从

《大容量内存文件系统设计及μC/OS下的实现(第2页)》