六、文件管理

1、文件

       文件系统的管理功能是将其管理的程序和数据通过组织为一系列文件的方式实现的。而文件是指具有文件名的，在逻辑上具有完整意义的一组相关元素的集合。

■  数据项、记录和文件

      在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型：基本数据项、组合数据项。记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。由于对象所处的环境不同可把他作为不同的对象。 文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。

                                             

■  文件命名：由文件名和扩展名构成

文件名MS-DOS由1-8个字符组成；WINDOWS由1-255个字符组成（支持长文件名），扩展名一般由1-3个字符组成。

■  文件类型

1) 按用途分类：系统文件、用户文件、库文件

2) 按文件中数据的形式分类：源文件、目标文件、可执行文件

3) 按存取控制属性分类：只执行文件、只读文件、读写文件

4) 按组织形式和处理方式分类：普通文件、目录文件、特殊文件

■  文件属性

除了文件内容外还包含文件属性信息：名称、类型、位置、大小、保护、时间日期等

2、文件操作：

■   存取方法：顺序存取方法、直接存取方法（又称随机存取方法）、索引存取方法

■   基本操作：创建文件、删除文件、读文件、写文件。

■   打开和关闭操作

■   其它文件操作

3、文件结构

■  文件的逻辑结构：无结构的流式文件、有结构的记录式文件

■    选取文件逻辑结构遵循的基本要求：

（1）有助于提高对文件的检索速度

（2）方便对文件进行修改

（3）尽量减少文件占用的存储空间，不要求大片的连续存储空间

■   根据文件的组织方式，可把有结构文件分为三类：顺序文件、索引文件、索引顺序文件。

■  顺序文件

      顺序文件的最佳应用场合是在对文件中的记录进行批量存取时(即每次要读或写一大批记录)。所有逻辑文件中顺序文件的存取效率是最高的。此外，对于顺序存储设备(如磁带)，也只有顺序文件才能被存储并能有效地工作。

■    索引文件

（1）按关键字建立索引

（2）具有多个索引表的索引文件：为每种可能成为检索条件的域(属性或关键字)都配置一张索引表。

■   索引顺序文件

      索引顺序文件是对顺序文件的一种改进，它基本上克服了变长记录的顺序文件不能随机访问，以及不便于记录的删除和插入的缺点。但它仍保留了顺序文件的关键特征，即记录是按关键字的顺序组织起来的。它又增加了两个新特征：一个是引入了文件索引表，通过该表可以实现对索引顺序文件的随机访问；另一个是增加了溢出(overflow)文件，用它来记录新增加的、删除的和修改的记录。

（1）一级索引顺序文件
　　最简单的索引顺序文件只使用了一级索引。

检索时间：

      对于一个含有N个记录的顺序文件，查找某个关键字值的记录时平均需要查找N/2次。对于具有一级索引顺序文件，为能查找某个关键字值的记录时平均需要查找次。

（2）两级索引顺序文件：对于一个非常大的文件，为找到一个记录而须查找的记录数目仍然很多，为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文件再建立一张索引表，从而形成两级索引表。

■  直接文件：关键字决定了记录的物理地址。哈希(Hash)文件是目前应用最为广泛的一种直接文件。

4、文件目录

■   功能：实现按名存取、提高检索速度、文件共享、允许文件重名。

■   操作：创建目录、删除目录、改变目录、移动目录、链接(Link)操作、查找

■  文件目录内容：

（1）文件控制块FCB(File Control Block)

      文件目录在文件名与文件自身之间一种映射。为了能对文件进行正确的存取，必须提供用于描述和控制文件信息的数据结构。

MS-DOS的文件控制块

　（2）索引结点：查找目录的过程中，须将存放目录文件的第一个盘块中的目录调入内存，然后将用户所给定的文件名，与目录项中的文件名逐一比较。因此，有的系统（UNIX，Linux）采用将文件名和文件描述信息分开，将文件描述信息单独形成一个称为索引节点的数据结构。

UNIX的文件目录

■  文件目录结构

（1）单级文件目录
　　这是最简单的文件目录。在整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性。此外，为表明每个目录项是否空闲，又设置了一个状态位。

单级文件目录

单级目录结构的特点：

优点：结构简单，使用方便，易于实现。

缺点：查找速度慢、不允许重名、不便共享、不适合多用户操作系统

（2）两级文件目录

       克服单级文件目录所存在的缺点，可以为每一个用户再建立一个单独的用户文件目录UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块组成。此外，在系统中再建立一个主文件目录MFD(Master File Directory)；在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针。

（3）树形多级结构目录(Tree-Structured Directory)

       在现代OS中，最通用且实用的文件目录无疑是树形结构目录。它可以明显地提高对目录的检索速度和文件系统的性能。主目录在这里被称为根目录，在每个文件目录中，只能有一个根目录，每个文件和每个目录都只能有一个父目录。把数据文件称为树叶，其它的目录均作为树的结点，或称为子目录。

（4）无环图目录结构

       严格的树形结构目录中，每个文件只允许有一个父目录，父目录可以有效地拥有该文件，其它用户要想访问它，必须经过其属主目录来访问该文件。这就是说，对文件的共享是不对称的，或者说，树形结构目录是不适合文件共享的。

■  文件路径

（1）绝对路径

       在树形结构目录中，从根目录到任何数据文件都只有一条唯一的通路。在该路径上，从树的根(即主目录)开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构成该数据文件唯一的路径名。

（2）相对路径

       当进程访问局限于某个子目录时，可以设置一个“当前目录”，又称为“工作目录”。从当前目录开始，到达要访问的最终文件所进过的路径称为相对路径。

5、文件共享与保护

■  利用符号链接(Symbolic Linking)实现共享

优点：在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，如果其他用户又试图通过符号链去访问一个已被删除的共享文件，则会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。

缺点：每次访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而由于链本身实际上是一个文件，尽管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。

■  利用索引结点的共享方式

■  文件保护：口令保护、加密保护、访问控制

（1）访问类型：读、写、执行、添加、删除、列表、重命名、复制

（2）访问控制：用户身份认证，如WINDOWS，数据库等身份认证。

（3）口令：用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应的口令，同时告诉共享该文件的其他用户。

（4）密码：用户对文件内容进行加密，文件被访问时需要使用密钥

6、文件存储空间管理

■   空闲表法

      空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表。

存储空间的分配与回收：

      空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法、最佳适应算法和最坏适应算法等，它们对存储空间的利用率大体相当。

■  空闲链表法

1) 空闲盘块链：磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。缺点：空闲盘块链可能很长，影响效率。

2) 空闲盘区链：将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。缺点：分配与回收的过程较复杂。

■   位示图法

      利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。

      盘块分配时可分三步进行：

(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。

(2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：

b = n(i - 1) + j

式中，n代表每行的位数。

(3) 修改位示图，令map[i, j] = 1。

　盘块的回收分两步：

(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：

i = (b - 1)DIV  n + 1

j = (b - 1)MOD  n + 1

(2) 修改位示图。令map[i, j] = 0。

■  链接索引表法

又称成组链接法。使用若干个空闲盘块作为索引表块，来指出存储空间中所有的空闲块。

7、文件分配

文件分配是指如何分配空白块来存放文件中的内容，也称为文件的物理结构。文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有： (1) 连续组织方式。 (2) 链接组织方式。 (3) 索引组织方式。

■  连续分配：又称连续组织方式，要求为每一个文件分配一组相邻接的盘块。采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。

优点：顺序访问容易、顺序访问速度快

缺点：要为文件分配连续存储空间、必须事先知道文件长度

不能灵活删除和插入记录、容易形成磁盘碎片

■  链接分配：采用链接分配方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。

(1) 消除了磁盘的外部碎片，提高了外存的利用率。

(2) 对插入、删除和修改记录都非常容易。

(3) 能适应文件的动态增长，无需事先知道文件的大小。

1. 隐式链接：在采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块的指针和文件的长度。

2. 显式链接

       把链接文件各物理块的指针显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张（FAT表）。

隐式链接和显式链接的比较：

隐式链接指针在磁盘上，每次都要读取磁盘。

显式链接将磁盘上文件的链式结构用内存的一张FAT表去描述，查找时可以在内存中进行，定位后再读磁盘。速度比隐式快很多。

■  索引链接分配

（1）一级索引链接分配
　　链接组织方式虽然解决了连续组织方式所存在的问题(即不便于随机访问)，但又出现了另外两个问题，即：① 不能支持高效的直接存取，要对一个较大的文件进行存取，须在FAT中顺序地查找许多盘块号；② FAT需占用较大的内存空间，由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。

（2）多级索引链接分配

      在为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS须再为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。

8、Windows文件管理

■  FAT12

1) 早期的FAT12文件系统

      FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。

MS-DOS的文件物理结构

2) 以簇为单位的FAT12文件系统

       如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。

■  FAT16  

      FAT12对磁盘容量限制的原因在于， FAT12表中的表项有限制，亦即最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。

■   FAT32

      由于FAT16表长只有65 535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零，也就应当增加FAT表的长度，为此需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。

FAT中簇的大小与最大分区的对应关系

■  NTFS

      NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP及后续的Windows OS。

（1）磁盘组织：

      NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即使NTFS具有了与磁盘物理块大小无关的独立性。

（2）文件的组织：

      在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。