2.7 文件管理

在计算机应用中，信息的传输、处理和存储是3个最关键的问题，而其中信息的存储方式是其他问题的讨论基础。一个应用必然要生成各种各样的数据信息，不论是暂时的，还是永久性的，都涉及到信息的存储问题。前面已经讲到过的内存管理所讨论的主要是信息的暂时存储和管理问题，而这里将着重讨论永久信息存储问题。

首先，永久信息的存储介质是外围存储设备，例如硬盘、软盘和光盘等，它们的存储方式所涉及到的一个关键性概念就是文件。鉴于此类存储设备在计算机系统中的重要地位，很多操作系统都会将对此类存储介质的存储管理纳入自己的设计范围内以进行仔细考虑，于是文件管理就产生了。

文件管理的核心部分是文件系统，它对操作系统的性能影响颇大。现在人们已经提出了很多不同类型的文件系统，形成了操作系统研究与实践的一道亮丽的风景线。

2.7.1 文件与文件系统

在讨论文件时通常还会遇到其他3个概念，即字段、记录和数据库。

1.字段

字段是数据的基本单位，一个字段通常是一个有着特定长度和类型的值，比如说雇员姓名等。字段可分为两种：长度固定和长度可变。对于后者，每个字段通常包括2～3个子域即字段的值、字段的名称，然后可选择的就是字段的长度。有的时候，字段可以靠一个特殊字符来表示它的结束，从而不需要有字段的长度，例如某些字符串定义以NULL作为结束标志。

2.记录

记录是若干个相关的字段所组成的集合，可以被某些应用程序作为一个整体来看待。例如，一个雇员的记录包括这样一些字段：姓名、年龄、工种、住址和联系方式等。和字段一样，记录的长度也分固定和可变两种。文件是一些相似记录的集合，都有一个唯一标识的文件名，应用程序或用户可以通过它来对文件定位。文件可以被创建或者删除，通常一些访问权限的设定也都出现在文件这一层次，而在一些更高级的系统中，访问权限控制可以细分到记录级、甚至是字段级。

3.数据库

数据库用来对一些相关数据进行管理，它通常是通过文件管理相关程序来对一些可能属于不同类型的文件进行统一管理。一般而言，这些文件或者数据之间的关系是明确界定了的。

文件通常是用户或者程序管理信息和数据经常要用到的。针对文件有一些比较典型的操作，例如取出文件中的一个或若干个记录、向文件中插入一个或者若干个记录、从文件中删除一个或者若干个记录等。

还有一个和文件联系比较紧密的概念就是文件目录，它为一组文件的统一管理提供了一个简单且有效的工具，从而成为所有文件管理系统中不可或缺的一部分。

文件系统向用户或程序提供一个使用文件的统一界面，从而使得对文件的各类操作能够在更加抽象、更加简便的层次上进行。文件系统的引入通常有以下几种目的。

● 满足用户管理数据的需要，这其中包括数据存储和对数据的操作。

● 尽可能保证文件中的数据的有效性。

● 性能优化，以提高系统的吞吐量和响应速度。

● 提供不同类型的存储设备的I/O支持。

● 降低或消除数据丢失或遭破坏的可能性。

● 提供一个标准的I/O界面。

● 在多用户系统中，向多个用户提供I/O支持等。

2.7.2 文件组织与访问

文件组织是指其中记录的逻辑结构，它是按照这些记录访问方式来划分的。在外围存储设备中存在的文件的物理结构有赖于具体的存储设备的分块和分配的策略，这个在后面阐述，这里讲述文件组织的类型。

选取一个文件组织类型需要从几个方面来考虑：信息访问的速度、信息更新的难易程度、存储的经济性及可靠性等。

不同的应用对这几个方面的要求各有不同，需要在具体情况下进行权衡，毕竟有些方面相互之间会产生矛盾。例如，如果想要存储经济，就不好强求访问速度高了，因为一般而言，提高访问速度意味着需要更多的冗余信息来提供文件或记录索引，这就意味着有效存储信息的所占比例将会有所下降。

现在已经有很多文件组织类型，可以总结出5种基本的类型，其他的文件组织类型要么是其中一种，要么就是其中若干种的混合。这5种基本的文件组织类型就是堆文件、顺序文件、索引顺序文件、索引文件、快速文件（图2-12），其性能比较见表2-6。

1.堆文件

文件组织形式中最简单的莫过于堆文件了。在堆文件组织形式中，数据依照它们被存储的顺序依次排放在存储设备中，每一个记录就代表每一次连续数据的存储，在记录间有一个特定的分隔符作为界定。每一个记录都有若干个字段，其中最主要的就是记录名和记录的值。

由于在堆文件中，除了记录信息，没有其他的冗余信息，所以对信息的检索只能用完全搜索的办法。这就是说，如果需要寻找某个特定的记录，那就需要依次查找每个记录直到目标出现，而如果想要查找有着某个特定值的记录，那就麻烦了，需要搜遍所有记录以找出所有符合条件的。

2.顺序文件

最常见的文件结构是顺序文件结构。在这种文件类型中，所有的记录都有着相同的格式：等长、字段数量相同、字段顺序也一致。因此，各个记录只需要保留各自的值即可，而记录名和记录的长度等信息可以提取出来作为文件自身的属性统一存储，这样可以提高文件存储的经济性。

在每一个记录中有一个特殊的字段，就是关键字。关键字唯一标识记录，通常记录是按照关键字的顺序来存储的。顺序文件组织在批处理应用中通常是高效的，而在类似交互式应用中，当涉及到频繁的记录查询或更新的时候，顺序文件结构的表现就很差。通常，顺序文件的物理存储采用链表结构：若干个记录共用一个物理块，而每一个物理块都会有一个指针指向下一个文件所用到的物理块。

3.索引顺序文件

为了克服顺序文件在随机访问时的缺点，人们提出了索引顺序文件类型。索引顺序文件与顺序文件相比，所不同的是加入了两个新的特征：一个是可以支持随机访问的索引，一个是溢出文件。索引能够使得用户或程序很快找到所需要的记录，而溢出文件和日志文件比较类似，这样溢出文件中的记录就可以通过它们前继记录所给出的指针来实现快速访问了。

在简单的索引顺序文件中，索引只有一级，这时的索引就是一个简单的顺序文件。在这个文件中的记录包含两个字段，一个是该记录的关键字，另外一个则是一个指向主文件某个记录的指针。当需要查找某个字段时，首先在索引文件中查找与该字段对应的关键字距离最近的一个索引，在获得该索引之后，就可以根据该索引给出的指针转到主文件中的对应位置继续搜索直到找到所需要的字段为止。如果需要插入一个新的记录，它会被插入到溢出文件中，而与其关键字距离最近的前继记录的指针将会被刷新并指向该记录。另外为了获得更高的访问速度，可以引入多级索引结构。

4.索引文件

索引顺序文件的一个局限性就是它只对记录的某一个特定字段建立索引。因此，如果按照一个并非建立了索引的字段值来搜索的话，索引顺序文件和顺序文件一样都会表现得很不好。但是，很多时候需要按照不同的字段来搜索记录。

索引文件的引入就是为了迎合这种需求。索引文件实际上是一个多索引结构，它针对记录中可能会成为搜索对象的字段建立多个索引文件。在这种索文件组织结构中，记录的访问可以完全通过索引直接完成，并且记录的长度是可以变化的。所有的索引可以分为两种类型，一种是完全索引，它对所有记录都建立索引，另一种是部分索引，它只对某些感兴趣的记录建立索引。由于记录允许变长，所以某些记录拥有别的字段的可能就没有。当有新的记录加入的时候，所有的索引文件都需要更新。

5.快速文件

快速文件组织形式利用哈希表技术，给定一个关键词，可以很快地找到对应的记录所在的物理块的地址。

2.7.3 文件共享

在一个多用户系统中，一个文件通常需要在多个用户中共享，这个时候就有两个问题需要考虑：一个是访问权限，另外一个就是并发访问管理。

1.权限

为了实现多用户系统的文件访问权限控制，不同的用户或用户组的权限已经被分别规定了，可以通过限定可访问文件的用户或用户组来实现对文件访问权限的控制。通常针对一个文件有这么一些访问权限的规定，比如执行、读、写和删除等，并且各个基本权限可以自由组合形成更为精确的规定。

通常每一个文件都有一个所有者，一般而言，这个文件的所有者也是创建该文件的用户，对该文件具有完全的访问权限。另外，每一个多用户系统还有一个拥有至高权限的用户，称为管理员，他对所有文件都拥有完全的访问权限，可以方便地对系统进行有效管理。

2.访问管理

当多个用户拥有对某个文件的写权限的时候，就需要引入相应的互斥控制机制来维持文件本身逻辑的完整性。一个比较简单的做法就是当某个用户需要写这个文件时，拒绝其他用户访问，直到该用户执行完操作为止。更为精细的做法则是在记录级上实现互斥，这样就可以使得一个用户在对文件的某个记录进行操作的同时，另外一个用户可以对文件中的另外一个记录进行操作，从而提高系统效率。

2.7.4 记录分块

上面所提到的文件组织结构是计算机中记录的逻辑结构，它们最终是要存储在外围存储设备中的，这就涉及到了记录的物理结构问题。在物理结构中，记录是以物理块的形式组织的。

现在就有一个问题提出了，物理块究竟应该是等长的还是变长的？毫无疑问，变长可以带来灵活性，可以按照记录逻辑结构的特点随意定义块的长度，但是这样却会在I/O缓冲、内存缓冲的分配和管理上带来麻烦。事实上，在大多数系统中，物理块长度一定。

这样就又有一个问题出来了，物理块的长度如何界定呢？物理块如果越长，而且文件的记录按顺序排放在物理块上的话，那么每次I/O访问就可以往内存读入越多的记录，从而能够提高I/O设备的吞吐量。但是如果文件的记录是随机存储的话，也就说随意散落在各个物理块中，则物理块越长，每次读入内存的记录中无用的就越多。事实上，对于这种情况，可以通过碎片整理程序之类的工具实现文件记录的集中存储，从而提高每次读入记录的有效部分的所占比率。

给定一个记录的长度，就涉及到如何实现分块的问题，主要有3种分法。

（1）固定分块法

记录定长，每个物理块都存放整数个记录，而这个数目都是一样的。这种方法会导致每个物理块最后可能会有固定大小的存储空间被浪费。

（2）变长可跨越分块法

使用变长记录，打包进块，没有浪费存储空间，而某些记录则可能被分开存储在两个块中，由后续块的指针来标明连续性。

（3）变长不可跨越分块法

使用变长记录，但不允许一个记录分开在两个块中存储。因此，如果下一个记录比块的剩余空间大的话，该剩余空间就只能被浪费掉了。

固定分块法适合记录定长的顺序文件存储，而变长可跨越分块法能够有效利用存储空间，并且不限制记录的大小，灵活性很好，但是却很难实现。变长不可跨越分块法会导致存储空间浪费，并且记录的长度受限于物理块的长度。

在现代计算机中，虚拟内存技术得到了广泛应用，这个时候在考虑记录分块的时候就需要注意到一个现实，就是记录分块技术常常要和虚拟内存技术相关的硬件打交道。由于虚拟内存的最小管理单位是分页，因此一个比较理想的I/O传输的基本单位就是分页。但是在通常情况下，分页往往是比较小的，因此在某些计算机系统中就采取将多个分页的长度和作为一个物理块的大小，从而实现一次I/O访问能够读取整数个分页的目的。

2.7.5 外围存储设备管理

在文件系统管理中，对文件的物理存储管理也是一个很重要的内容，这里的文件的物理存储管理主要就是指外围存储设备管理。外围存储设备管理包括两个方面，一个是文件分配，另外一个就是空闲存储空间管理。

1.文件的存储空间分配

文件的存储空间分配涉及到3个方面的内容：一是文件创建之初，分配给它的存储空间大小如何确定的问题；二是文件存储空间总是分成若干个内部连续的存储划分，这样一些划分的大小该如何确定；三是采用什么样的数据结构来对这些分区进行统一管理，也就是涉及到一个文件分配表的选择问题。

对于第一个问题的回答有两个，一个是预分配法，一个是动态分配法。所谓预分配法就是在文件创建之初按其长度的最大值一次性分配给相应大小的存储空间。这种分配方法在某些可以预知文件最大长度的情况下是很有效的，但是对于一些难以预料文件最大长度的情况，为了避免最后所分配区域不够用的状况出现，预分配的存储空间总是比实际所用到的要大，从而造成了存储空间的浪费。动态分配法与预分配法相比就具有更大的灵活性，它只有当预先分配的存储空间不够用时再动态分配一定数量的存储空间。

存储划分的大小的选取需要从多个角度多加权衡，才能得到比较满意的答案。如果划分的连续存储区域比较大的话，不仅可以提高某些数据访问的速度，同时还可以减小文件分配表的大小。综合起来，权衡利弊，可以有以下两种选择。

（1）变长、较长的连续区域划分

这种方式可以提高系统性能，避免存储空间的浪费，而文件分配表也会比较小。问题是，存储空间不好使用，这个道理和前面讲过的物理块变长的情况比较类似。

（2）物理块

物理块长度较小、定长、容易分配，没有考虑连续性，分配起来比较容易，并且有一定的灵活性。至于说连续性方面的缺陷，如果采用某些类似文件碎片整理程序的工具对存储空间进行整理的话，则可以有些补偿，进而能够在某种程度上提高系统的性能。事实上，物理块是在外围存储空间设备管理中广泛使用的。至于说采取什么样的数据结构来对这些存储区域的连续划分进行管理，有3种可以选择的方案，即连续分配法、链状分配法和索引分配法。

所谓连续分配法就是在文件创建之初将一片连续的物理块分配给文件。这是一种预分配法，采用变长存储划分。和连续分配法相对的是链状分配法，它不要求各物理块是连续摆放的，事实上可以是在存储空间中随机摆放的。所有物理块按逻辑顺序通过指针穿成一个单向链表，索引分配法则在主文件之外对它维护一个索引文件，用于索引主文件中的各个物理块，从而实现对各物理块的快速访问。

2.空闲存储空间管理

就像已分配的存储空间需要管理一样，未分配的存储空间也需要进行合理的管理，常用的方法主要有3种，即位示图、空闲块链和索引。位示图维护一个向量，其每一位与存储空间中的一个物理块一一对应。当位值为0时表示与该位对应的物理块处于空闲状态，如果位值是1的话，则说明物理块已经被征用了。空闲块链则是使用链表技术将所有空闲存储区域划分并按照一定的逻辑顺序连接起来，类似地，索引方法也就是利用索引技术将所有空闲存储区域划分进行统一管理的。