21central 文件系统

③文件逻辑结构，指示文件是流式文件还是记录式文件、记录数；文件是定长记录还是变长记录等。④文件的物理结构，指示文件是顺序文件，还是链接式文件或索引文件。（2）存取控制信息类。包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。（3）使用信息类。包括：文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信息（这包括：当前已打开该文件的进程数、是否被其它进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上，）。应该说明，对于不同OS的文件系统，由于功能不同，可能只含有上述信息中的某些部分。图6-14示出了MS-DOS中的文件控制块，其中含有文件名、文件所在的第一个盘块号、文件属性、文件建立日期和时间及文件长度等。FCB的长度为32个字节，对360KB的软盘，总共可包含112个FCB，共占4KB的存储空间。文件名扩展名属性备用时间日期第一块号盘块数图6-14MS-DOS的文件控制块2、索引结点（1）索引结点的引入文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名与目录项中的文件名与目录项中的文件名逐一比较。若未查找到指定文件，便再将下一个盘块中的目录项调入内存。设目录文件所占用的盘块数为N，按此方法查找，则查找一个目录项平均需要调入盘块（N+1）/2次。在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项时，才需从该目录项中读出该文件的物理地址，而其他一些对文件进行描述的信息，在检索目录时，一概不用，因此，这些信息在检索目录时，不需调入内存。为此，可把文件名与文件描述信息分开。UNIX系统即采用了这种方式，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点，在文件目录的每个目录项，仅由文件名和指向该文件所对应的i结点的指针构成。图6-15示出了UNIX的文件目录项。文件名文件名1文件名2……图6-15UNIX的文件目录（2）磁盘索引结点每个文件有惟一的磁盘索引结点，它主要包括以下内容：①文件主标识符：拥有该文件的个人或小组的标识符。②文件类型：包括正规文件、目录文件、或特别文件。索引结点编号③文件存取权限：指各类用户对文件的存取权限。④文件物理地址：每个索引结点中含有13个地址项，它们以直接或间接方式给出数据文件所在盘块的编号。⑤文件长度：指以字节为单位的文件长度。⑥文件连接计数：表明在本文件系统中，所有指向该文件名的指针计数。⑦文件存取时间：指出本文件最近被进程存取的时间，最近被修改的时间及索引结点最近被修改的时间。（3）内存索引结点指存放在内存中的索引结点，当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，便于以后使用。在内存索引结点中，增加了以下内容：①索引结点编号：标识内存索引结点。②状态：指示i结点是否上锁或被修改。③访问计数：每当有一进程要访问此i结点，将该访问计数加1，访问完再减1。④文件所属文件系统的逻辑设备号。⑤连接指针：设置有分别指向空闲链表和散队列的指针。6.4.2目录结构目录结构的组织，关系到文件系统的存取速度、共享性、安全性。1、单级目录结构整个文件系统中只有一张目录表，每个文件占一个目录项，目录项中包含：文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其他文件属性。此外，为表明每个目录项是否空闲，又设置了一个状态位，单级目录如图6-16所示：文件名文件名1文件名2…………图6-16单级目录单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一些缺点：(1)查找速度慢(2)不允许重名(3)不便于实现文件共享2、两级目录物理地址文件说明状态位为每一个用户建立一个单独的用户文件目录UFD，这些目录具有相似的结构，它由用户所有文件的文件控制块组成。在系统中再建立一个主文件目录MFD，每个用户目录文件都在MFD中占有一个目录项，其目录项包括：用户名、指向该用户目录文件的指针。如图6-17所示。图6-17两级目录结构两级目录结构基本上克服了单级目录的缺点，并具有以下优点：（1）提高了检索目录的速度。（2）在不同的用户目录中，可以使用相同的文件名。（3）不同用户还可使用不同的文件名访问系统中的同一共享文件。3、多级目录结构（树型结构）（1）目录结构：树型，主目录被称为根目录，数据文件称为树叶，其它目录均作为树的节点。图6-18示出了多级目录结构。图6-18多级目录结构（2）路径名。在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从树的根(即主目录)开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名(pathname)。系统中的每一个文件都有惟一的路径名。例如，在图6-18中用户B为访问文件J，应使用其路径名/B/F/J来访问。（3）当前目录(CurrentDirectory)。当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据文件)为止的、包括各中间结点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进程运行时所访问的文件，大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件，最后到达要访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形成路径名，如用户B的当前目录是F，则此时文件J的相对路径名仅是J本身。这样，把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relativepathname)；而把从树根开始的路径名称为绝对路径名(absolutepathname)。4、增加和删除目录(1)不删除非空目录。当目录(文件)不空时，不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录，后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除，在MS-DOS中就是采用这种删除方式。(2)可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除。6.4.3目录查询技术1、线性检索法线性检索法又称为顺序检索法。图6-19显示了查找/usr/ast/mbox文件的过程。图6-19查找/usr/ast/mbox的步骤2、Hash方法一种处理此“冲突”的有效规则是：(1)在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。(2)如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。(3)如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。6.5文件存储空间的管理

6.5.1空闲表法和空闲链表法1、空闲表法（1）空闲表空闲表法属于连续分配，系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，包括：序号1234第一空闲盘块号2915--空闲盘块数435--图6-20空闲盘块表(2)存储空间的分配与回收。空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。2、空闲链表法将所有空闲盘区，拉成一条空闲链，根据构成链所用的基本元素的不同，可把链表分成2种形式：（1）空闲盘块链将磁盘上所有空闲区空间，为盘块为单位拉成一条链，当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块链给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。其优点是分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复多次操作。（2）空闲盘区链将磁盘上所有空闲盘区拉成一条链，在每个盘区上包含若干用于指示下一个空闲盘区的指针，指明盘区大小的信息。分配盘块时，通常采用首次适应算法（显式链接法）。在回收时，要将回收区与空闲盘区相合并。6.5.2位示图法1、位示图用二进制位表示磁盘中的一个盘块的使用情况，0：空闲；1：表示已分配。磁盘上的所有盘块都有一个二进制位相对应，由所有的二进制位构成的集合，称为位示图。如图6-21所示。位示图可描述为一个二维数组：varmap：array[1……m,1……..n]ofbit;