孟斌
文件管理
文件管理是对外部存储设备上的以文件方式存放的信息的管理。文件的结构是指文件的组织形式，从用户角度所看到的文件组织形式，称为文件的逻辑结构；文件的物理结构是指文件在存储设备上的存放方法，侧重与提供存储器的利用效率和降低存取时间。文件的存储设备通常划分为大小相同的物理块，物理块是分配和传输信息的基本单位。用户通过对文件 的访问来完成对文件的查找、修改、删除和添加等操作。常用的访问方式有两种：顺序访问和随机访问。
1. 文件的逻辑组织
文件的逻辑组织是为了方便用户的使用，逻辑结构是用户可见的结构。文件的逻辑结构可以分为无结构的字符流文件和有结构的记录文件（又称有格式文件）。
记录文件由记录组成，即文件的内容划分为多个记录，以记录为单位组织和使用信息。常用的记录式结构有：
- 连接结构：是一种吧记录按照生成的先后顺序排列的逻辑结构，其特点是适应性强，可用于所有文件，且记录的排列顺序与记录的内容无关；缺点是搜索性能差
- 多重结构：把记录按键与名排列成列式结构，一个包含n个记录名、m个键的文件构成一个$m \times n$维行列式
- 转置结构：把包含相同键的记录指针全都指向该键，即把所有与同一键对应的记录的指针连续置于目录中该键的位置下。最适合于给定键后的记录搜索
- 顺序结构：把文件中的键按规定的顺序排列起来
用户通过对文件的存取来完成对文件的修改、追加和搜索等操作，常用的存取方法有顺序存取法、随机存取法（直接存取法）和按键存取法。
2. 文件的物理结构
在文件系统中，文件的存储设备通常划分为若干个大小相同的物理块。文件的物理结构是指文件在存储设备上的存放方法，常用的文件物理结构有：
- 连续文件：又称顺序文件，是一种最简单的物理文件结构，它把一个在逻辑上连续的文件信息依次存放到物理块中。
- 优点是一旦知道文件在文件存储设备上的起始位置和文件长度，就能进行存取。适合顺序存放，在连续存取相邻信息时，存取速度快
- 缺点是在文件建立时必须指定文件的信息长度，以后不能动态增长，需要进程修改的文件不宜采用此方式存储
- 串联文件：又称链接文件，用非连续的物理块来存放文件信息，这些物理块之间没有顺序关系，其中每个物理块设有一个指针，指向下一个物理块的地址，这样所有的物理块都被链接起来，形成链接队列。
- 优点是可以解决存储器的碎片问题，提高存储空间的利用率
- 缺点是因为只能按照队列中的链接指针顺序查找，所有搜索效率低，只适用于顺序访问
- 索引文件：是另一中对文件存储不连续分配的方法。为每个文件建立一张索引表，索引表中的每一表项支出文件信息所占的逻辑块号和与之对应的物理块号。
- 优点是既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取，这样既适用于顺序存取，又适用于随机存取
对于一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，即在由索引表指出的物理块中存放的是存放文件信息的物理块地址。
- 缺点是索引表增加了存储空间的开销；在存取文件时至少需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息
为了提高效率，一种改进方法是，在对某个文件进行操作之前，预先把索引表调入内存，这样文件的存取就能直接从在内存中的索引表中确定相应的物理块号，从而只需访问一次磁盘
- 优点是既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取，这样既适用于顺序存取，又适用于随机存取
3. 树形目录结构
文件控制块的集合称为文件目录，文件目录也被组织成文件，被称作目录文件。文件管理的一个重要方面是对文件目录进行组织和管理。文件系统一般采用一级目录结构、二级目录结构和多级目录结构。
DOS、UNIX、Windows系统都是采用多级树形目录结构
在多级树形目录结构中，整个文件系统有一个根，然后在根上分枝，任何一个分枝上都可以再分枝，枝上也可以长出树叶。根和枝称为目录或文件夹，树叶则是一个个文件。
实践证明，这种结构的文件系统效率比较高
对文件进行访问时，需要用到路径的概念。路径是指从树形目录中的某个目录层次到某个文件的一条路径。在树形目录结构中，从根目录到任何数据文件之间，只有一条唯一的通路，这样每个数据文件的路径名都是唯一的。
4. 存储空间管理
由于文件存储设备时分成许多大小相同的物理块，并以块为单位交换信息，因此文件存储设备的管理，实质上是对空闲块的组织和管理问题，它包括空闲块的组织、空闲块的分配与空闲块的回收等问题。
4.1 空闲表法
空闲表法属于连续分配，系统为外存上的所有空闲区建立一张空闲表，每个空闲区对一个空闲表项，包括序号、第一空闲盘块号和空闲盘块数。
4.2 空闲链表法
将所有空闲盘区，拉成一条空闲链，根据构成链所用的基本元素的不同，可把链表分成两种形式：
- 空闲盘块链，将磁盘上所有空闲区空间，以盘块为单位拉成一条链
- 空闲盘区链，将磁盘上所有空闲盘区拉成一条链，在每个盘区上包含若干用于只是下一个空闲盘区的指针，指明盘区大小的信息
4.3 位图法
位图（bitmap）用二进制位表示磁盘中的一个盘块的使用情况，0表示空闲，1表示已分配。磁盘上的所有盘块都与一个二进制位相对应，有所有二进制位构成的集合即为位图。
其优点是很容易找到一个或一组相邻的空闲盘块；位图小，可以把它保存在内存中，节省测盘的启动操作。
4.4 成组链接法
将空闲链表结合形成的一种空闲盘块管理方法，适用于大型文件系统。
声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意