5.文件管理

文件(file)：是记录在外存上的，具有符号名的，在逻辑上具有完整意义的一组相关信息项的集合。

信息项：是构成文件内容的基本单位，可以是一个字符，也可以是一个记录。 从用户的角度看，文件是逻辑外存的最小分配单元，即信息(数据)只能以文件的形式写入外存。

一、文件的目录管理

目录管理的目标：按名存取、提高对文件的存取速度（合理安排目录） 、文件共享、允许文件重名

1.文件控制块（FCB）和索引节点

（1）FCB

为了实现“按名存取”，系统必须为每个文件设置用于描述和控制文件的数据结构，它至少要包括文件名和存放文件的盘物理地址，这个数据结构称为文件控制块FCB， 文件控制块是文件存在的标志。

文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合。

目录项：构成文件目录的项目（目录项就是FCB）。

目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。

1. 基本信息 文件名：字符串，通常在不同系统中允许不同的最大长度。 物理位置 文件逻辑结构：有/无结构（记录文件，流式文件） 文件物理结构（如顺序，索引等）

2. 访问控制信息 文件所有者（属主）：通常是创建文件的用户，或者改变已有文件的属主； 访问权限（控制各用户可使用的访问方式）：如读、写、执行、删除等；

3. 使用信息 创建时间 上次修改时间 当前使用信息：打开文件的进程数，在文件上的等待队列等。

（2）索引节点

把文件名与文件的描述信息分开，即把文件的描述信息单独形成一个数据结构，即索引点。在Unix中，称i节点。

2.单级、两级目录结构（被已被淘汰）

（1）构造方法：

把系统中的所有文件都建立在一张目录表中，整个目录组织是个线性表。结构比较简单，能实现目录管理的基本功能--按名存取。 例：D盘这个根目录存储着所有文件。 （2）建立文件：目录表中增加一个新表目； （3）删除文件：目录表中清除该文件对应表目的信息。

（4）优点：结构比较简单、易实现 （5）缺点：查找速度慢：文件目录表很大、不允许重名：不同文件不能同名！同一文件不能以不同名字出现或使用、不便与实现文件共享、只适用于单用户操作系统。

两级目录结构：

（1）构造方法 目录分为两级： 一级称为主文件目录MFD(Master File Directory)（又称根目录），给出用户名，用户子目录的物理位置； 二级称为用户文件目录UFD(User File Directory)（又称用户子目录），给出该用户所有文件的FCB。

（2）新用户建立文件 主目录表中分配一个表目，并为其分配存放二级目录的存储空间，为新建立的文件在二级目录分配一个 表目，分配文件的存储空间。 （3）用户访问文件：先按用户名在主目录中找到该用户的二级目录，然后在二级目录中按文件名找出该文件 的起始地址并进行访问。 （4）优点: 解决了文件的重名问题和文件共享问题,查找时间降低 （5）缺点: 增加了系统开销

3.树型目录（多级目录）

（1）结构及优缺点

每一个结点（目录）出来的分支可以是数据文件，也可以 是目录文件。图中用圆代表文件，用矩形代表目录文件。

树型目录结构.png

优点： 层次结构清晰，便于管理和保护，解决重名问题，查找 速度加快。

缺点： 查找一个文件按路径名逐层检查，由于每个文件都放在 外存，多次访盘影响速度。

（2）路径名

从根目录到数据文件之间，只有一条唯一的通路。 主目录/目录文件名/数据文件名。

例如：D:\赢凌策\计算机\计算机操作系统\7_文件管理

（3）当前目录

每访问一个文件都要使用从根目录开始搜索直到树叶的数据文件为止，包含各中间子目录的全路径名是相当麻烦的，同时由于一个进程运行时访问的文件大多局限在某个范围，基于这一点，可为每个用户（或每个进程）设置一个“当前目录”，又称 “工作目录”。 进程对各文件的访问都相对于“工作目录”而设置路径，这称为相对路径，用相对路径可缩短搜索路径，提高搜索速度。

四、外存分配方法

即文件物理组织方式，目的：有效利用外存空间、提高文件的访问速度。

1.连续分配

为每一个文件分配一组相邻的盘块。

连续分配.png

（1）优缺点

优点： 顺序访问容易（因为连续的空间） 顺序访问速度快（因为一条或相邻的磁道上）

缺点：

要求有连续的存储空间：形成外碎片；运行时进行修改、删除也易形成外碎片。 必须事先知道文件的长度：装入时要求；预估计小于实际文件，需中止COPY，重新估计；若文件动态增长，应该预留空间，但会造成空间使用效率低。

2.链接分配

（1）引入

与内存管理类似： 进程占有连续的内存空间（内、外零头）离散地占有内存空间； 文件占有连续的外存空间（碎片）离散地占有外存空间； 解决方法： 在每个盘块上设一链接指针，将同属于一个文件的多个离散盘块链接成一个链表，由此所形成的物理文件链接文件。消除了外碎片，可以动态增、删、改。

（2）隐式链接

在文件目录的每个目录项FCB中含有指向链接文件第一和最 后一个盘块的指针 只适用于顺序访问，对随机访问效率极低，可靠性差。 改进：将几个盘块组成一个簇（Cluster）,在进行分配时 以簇为单位进行，链接文件的元素也以簇为单位，这样可以成倍减少查找时间，也可减少指针占用的存储空间，但增大了内碎片。

（3）显式链接

把用于链接文件各物理块的指针，显式的存放在内存的一张链接表中，即文件分配表FAT。 不能支持高效的直接存取 FAT占用较大的内存空间

3.索引分配

（1）单级索引分配

为每个文件分配一个索引表，把分配给该文件的盘块号，记录在该索引表中。文件目录中，填上指向该索引表的指针。 优点： 支持直接访问 不产生外碎片 缺点： 索引表在外存空间，需为小文件也匹配索引块。

（2）多级索引分配

二、空闲存储空间的管理

1.空闲表法

空闲表法.png

为外存上的所有空闲区建立一张空闲表，每个空闲区对 应一个表目，包括序号、该区的起始空闲盘块号、空闲盘块数 目等，按起始空闲盘块号排序。 分配：是一种连续分配方式，顺序查找空闲表，找到第一个合适的空闲区，修改空闲表。 回收：将相应块按序填回表中，并与前后合并成大块。 特点：连续存放，易产生碎片。

2.空闲链表法

（1）空闲盘块链

将磁盘上所有空闲存储空间，以盘块为单位链成一个链表。 分配：从链首开始，依次摘下适当数目的空闲盘块进行分配。 回收：依次链入链尾。 特点：分配、回收简单，空闲盘块链可能很长。

（2）空闲盘区链

将磁盘上所有空闲存储空间，以盘区（包括若干盘块）为单位链成一个链表。 分配：查找合适大小的盘区进行分配 回收：与前后盘区合并 特点：分配、回收复杂，空闲盘区链较短。

3.位示图法

（1）位示图

系统为文件存储空间建立一张位示图，如下图。位示图 反映了整个存储空间的分配情况，其中每一位对应一个物理块，“1”表示对应块已被分配，“0”表示对应块为空白。

（2）盘块的分配

顺序扫描位示图，找到一个或一组为“0”的二进制位，将位号、字号转换为盘块号，进行分配： 块号=位数*字号+位号 修改位示图，置“1”。

（3）盘块的回收

将盘块号转换为位号、字号： 字号=块号 整除 位数 位号=块号 取余 位数 修改位示图，置“0”。

4.成组链接法

（1）空闲盘块的组织

① 空闲盘块栈

存放当前可用的空闲盘块的盘块号，最多100个，以及 空闲盘块数N。栈是临界资源，为之设锁。

文件区的所有空闲盘块，被划分为若干个组。设10000 个盘块，100个为一组。201-7999号盘块存放文件。 将每组的盘块数及盘块号，记入前一组的第一个盘块 中。

第一组的盘块数及盘块号记入空闲盘块栈 最后一组的S.free(0)=0，作为结束标记

（2）空闲盘块的分配

空闲盘块的分配.png

（3）空闲盘块的回收

空闲盘块的回收.png

（4）成组链接法的优点

① 空白块号登记不占用额外空间，只临时借用每组的第一个空白块（读块时仍可以分配给用户用）。 ② 当前可分配的物理块号存放在空闲盘块栈，因此绝大部分的分配和回收工作是在主存中进行，可以节省时间。