4.1_1初识文件管理

4.1_2文件的逻辑结构

分类总览

文件逻辑结构分为两大类：无结构文件、有结构文件。

• 无结构文件：文件内部由二进制流/字符流构成，又称流式文件。例：Windows中的.txt文件。
• 有结构文件：又称记录式文件，由一组相似记录组成，每条记录包含若干数据项；一般选取一个数据项作为关键字。 按记录长度分为：定长记录、可变长记录。 有结构文件的逻辑结构包含三类：顺序文件、索引文件、索引顺序文件。
  

顺序文件

默认物理上为顺序存储。分为串结构、顺序结构。

• 串结构：记录顺序与关键字无关。
• 顺序结构：记录按关键字顺序排列。

定长记录

• 可以实现随机存取。第 $$i$$ 个记录相对位置：$$i \times L$$
• 顺序结构：支持折半查找，可根据关键字快速检索记录。
• 串结构：无法利用关键字快速查找。

可变长记录

• 无法实现随机存取，查找时必须从头依次向后查找。

顺序文件缺点

增加、删除记录操作困难；串结构相对简单。

索引文件

解决可变长记录不能随机存取的问题。

• 建立索引表，每条记录对应一个索引项。索引表本身是定长记录的顺序文件，可以快速找到第 $$i$$ 条记录对应的索引项。
• 文件记录在物理上可以离散存放。
• 索引表按关键字排序时，支持关键字折半查找。
• 增删记录时，需要修改索引表。检索速度快，适合及时性要求高的场景。
• 支持建立多张索引表，用不同数据项建立索引（如数据库，学号、姓名分别建索引）。
• 缺点：每个记录都对应索引项，索引表占用空间大。

索引顺序文件

索引文件与顺序文件思想结合，一组记录对应一个索引项，缩减索引表占用空间。

• 记录分组，每组对应一条索引项。索引项不需要按关键字顺序排列，方便插入新索引项。
• 检索流程：先顺序查找索引表，定位分组；再在分组内部顺序查找目标记录。
• 例题
  1. 共$$10000$$条记录，分为$$100$$组，每组$$100$$条。 索引表共$$100$$项，平均查找$$50$$次；分组内平均查找$$50$$次。 总平均查找次数：$$50 + 50 = 100$$次。
  2. 共$$10^6$$条记录，分为$$1000$$组，每组$$1000$$条。 总平均查找次数：$$500 + 500 = 1000$$次。

多级索引顺序文件

记录数量巨大时，对索引表再次分组，建立多级索引。

• 例：$$10^6$$条记录，低级索引每$$100$$条记录一组，得到$$10000$$条低级索引项；再对低级索引分组，每$$100$$个一组，建立顶级索引表，共$$100$$条顶级索引项。
• 平均查找次数：$$50+50+50=150$$次。

对比总结

类型	核心特点
顺序文件	定长记录支持随机存取；可变长记录不能随机存取；增删记录麻烦
索引文件	一条记录对应一条索引项，支持随机存取；索引表空间开销大
索引顺序文件	一组记录对应一条索引项，索引表更小；检索分两步查找；可扩展多级索引

4.1.3文件目录

文件目录的实现

一个文件对应一个 $FCB$ ，一个 $FCB$ 就是一个目录项，多个 $FCB$ 组成文件目录
对目录的操作：

• 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
• 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
• 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
• 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
• 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

  文件控制块 $FCB$ ： $FCB$ 的有序集合称为文件目录，一个 $FCB$就是一个文件目录项。 $FCB$ 包含文件基本信息、存取控制信息、使用信息。最核心的是文件名、文件存放的物理地址。 $FCB$ 实现文件名与文件的映射，完成按名存取。

目录结构

1. 单级目录结构

整个系统只有一张目录表，不允许文件重名。

• 特点：实现按名存取；创建文件时，需要遍历整张目录表检查重名。

2. 两级目录结构

分为主文件目录 $MFD$ 、用户文件目录 $UFD$ 。

• 主文件目录：记录用户名，以及对应用户文件目录存放位置
• 用户文件目录：由该用户所有文件的 $FCB$ 组成
• 特点：不同用户的文件可以重名；不能对文件进行分类；可做用户访问权限检查。

3. 多级（树形）目录结构

• 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
• 系统根据文件路径找到目标文件
• 绝对路径：从根目录出发的路径
• 相对路径：从当前目录出发的路径
• 优点：层次清晰，方便文件分类，便于管理与保护
• 考点：使用相对路径检索文件，可以减少磁盘I/O次数

4. 无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。

• 可以用不同文件名指向同一个文件，也可以指向目录，方便多用户文件共享
• 为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
• 删除操作：仅删除当前用户的目录项，共享计数器减$$1$$，不会直接删除文件本身
• 区分：共享文件≠复制文件；修改共享文件，所有用户都能看到改动。

索引结点（ $FCB$ 的改进）

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点

• 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小
• 目录项长度减小，单个磁盘块可以存放更多目录项，检索文件时磁盘I/O的次数减少，提升检索速度
• 磁盘索引结点：存放在外存中的索引结点
• 内存索引结点：调入内存后的索引结点，额外记录文件修改标记、访问进程计数等信息

  示例：
  原FCB大小$$64\ \text{B}$$，磁盘块$$1\ \text{KB}$$，每块存$$16$$个FCB；
  索引结点方案：文件名$$14\ \text{B}$$，索引结点指针$$2\ \text{B}$$，每块可存放$$64$$个目录项，磁盘IO次数显著下降。
  

4.1.4 文件物理结构

文件的物理结构，即文件在外存磁盘上的存储组织方式，也叫文件分配方式。
外存存储空间以磁盘块为单位管理，文件的逻辑地址空间也被划分为一个个大小相等的文件块（逻辑块），文件逻辑地址可表示为：(逻辑块号，块内地址)。操作系统以块为单位为文件分配磁盘空间，负责完成逻辑块号到物理块号的地址映射。

连续分配

定义

连续分配要求每个文件在磁盘上占用一组连续的物理块。
目录项（ $FCB$ ）中记录：起始块号、文件长度（总块数）。

地址映射

$$\text{物理块号} = \text{起始块号} + \text{逻辑块号}$$
访问时先校验逻辑块号是否合法：逻辑块号 ≥ 文件长度则判定越界。

优缺点

• 优点：支持顺序访问和随机（直接）访问；顺序存取时速度最快。
• 缺点：不方便文件拓展；会产生外部磁盘碎片，存储空间利用率低。

链接分配

链接分配采用离散分配方式，文件数据可分散存放在不连续的磁盘块中，通过指针将同属一个文件的磁盘块串联起来。分为隐式链接和显式链接两种。

考试中未指明类型的“链接分配”，默认指隐式链接。

1. 隐式链接

• 结构：除文件最后一个磁盘块外，每个磁盘块内部都保存指向下一个块的指针，指针对用户透明。
• 目录项记录：起始块号、结束块号（也可额外记录文件长度）。
• 访问过程：访问第$$i$$个逻辑块，需要从起始块开始依次读取前$$i$$个块，共需要$$i+1$$次磁盘I/O。
• 优缺点
  • 优点：文件拓展方便；无外部碎片，外存利用率高。
  • 缺点：只支持顺序访问，不支持随机访问；查找效率低；块内指针占用少量存储空间。

2. 显式链接

• 结构：把所有磁盘块的链接指针统一抽取出来，集中存放在**文件分配表（ $FAT, File Allocation Table$ ）**中。一个磁盘仅对应一张 $FAT$ ，开机时FAT读入内存并常驻。
• 目录项记录：仅需记录起始块号。
• 优缺点
  • 优点：文件拓展方便，无碎片；支持随机访问；地址转换直接查询内存中的FAT，无需访问磁盘，访问效率高于隐式链接。
  • 缺点： $FAT$ 表需要占用一定的内存和磁盘存储空间。

索引分配

基础概念

索引分配允许文件离散存放，系统为每个文件单独建立一张索引表，记录文件每个逻辑块对应的物理块号。

• 存放索引表的磁盘块称为索引块；存放文件数据的磁盘块称为数据块。
• 索引表功能类似内存管理的页表，建立逻辑块到物理块的映射；逻辑块号可以隐含。
• 对比显式链接：FAT是一个磁盘一张表；索引分配是一个文件一张索引表。
  当文件很大、索引项过多，单个磁盘块无法放下整张索引表时，有三种解决方案：

1. 链接方案

将多个索引块通过指针链式连接存放。

• 缺点：访问靠后的索引块，必须依次读取前面所有索引块，磁盘I/O次数多，查找效率低。
• 示例：磁盘块$$1\mathrm{KB}$$，索引项$$4\mathrm{B}$$，单块可放$$256$$个索引项。若文件共$$256\times256$$个块，则需要$$256$$个索引块链接；访问最后一个逻辑块，需要依次读入前$$255$$个索引块。

2. 多层索引

建立多级索引，原理类似多级页表：第一层索引块指向第二层索引块，可继续扩展更多层级。

• 规则：各级索引表的大小不能超过一个磁盘块。
• 访存次数：采用$$K$$层索引，若顶级索引表未调入内存，访问一个数据块共需要 $$K+1$$ 次读磁盘操作。
• 示例：磁盘块$$1\mathrm{KB}$$，索引项$$4\mathrm{B}$$，单块放$$256$$个索引项。
  • 两层索引最大文件长度：
    $$256 \times 256 \times 1\mathrm{KB} = 65536\mathrm{KB} = 64\mathrm{MB}$$
  • 访问$$1026$$号逻辑块：
    $$1026 / 256 = 4,\quad 1026 % 256 = 2$$
    先读一级索引，再读二级索引，最后读数据块，共$$3$$次磁盘I/O。
• 缺点：即使是小文件，访问数据块也需要$$K+1$$次读磁盘。

3. 混合索引

多种索引方式结合：顶级索引表中同时包含直接地址索引（直接指向数据块）、一级间接索引（指向单层索引表）、二级间接索引（指向两层索引表）等。

• 优势：小文件可通过直接地址快速访问，读磁盘次数少，契合系统中小文件占多数的场景。
• 示例（$$8$$个直接地址项）：
  • 访问$$0\sim7$$号逻辑块：$$2$$次读磁盘（读顶级索引块 + 读数据块）
  • 访问$$8\sim263$$号逻辑块：$$3$$次读磁盘
  • 访问$$264\sim65799$$号逻辑块：$$4$$次读磁盘
• 最大文件长度 = 直接块总容量 + 一级间接块总容量 + 二级间接块总容量。

知识点总结与对比

4.1.5逻辑结构vs物理结构

4.1.6文件存储空间管理

文件存储空间管理的核心是对磁盘空闲块进行组织与管理，完成磁盘块的分配与回收。

存储空间的划分与初始化

1. 存储空间划分：将物理磁盘划分为一个个文件卷（逻辑卷/逻辑盘），例如 $Windows$ 系统的 $C$ 盘、 $D$ 盘。部分系统支持超大型文件，可由多个物理磁盘共同组成一个文件卷。
2. 文件卷结构：每个文件卷分为两个区域
   • 目录区：存放文件目录信息（ $FCB$ ）、磁盘存储空间管理信息（空闲表、位示图、超级块等）。
   • 文件区：用于存放文件数据。
3. 初始化：将各个文件卷划分为目录区、文件区，完成管理数据结构的初始化。

空闲表法

适用于连续分配方式，原理与内存管理的动态分区分配类似。

• 数据结构：建立一张空闲盘块表，每个表项记录一个连续空闲区的「第一个空闲盘块号」和「空闲盘块数」。
• 分配：可采用首次适应、最佳适应、最坏适应等算法，为文件分配连续的空闲磁盘块。
• 回收：回收磁盘块时需处理四种相邻场景：
  ① 回收区前后都无相邻空闲区；② 回收区前后都是空闲区；③ 仅回收区前面是空闲区；④ 仅回收区后面是空闲区。
  回收核心是表项合并，将相邻的空闲区合并为一个表项。

空闲链表法

将所有空闲磁盘块/空闲盘区通过指针链接成链表，操作系统保存链头、链尾指针。分为两种实现：

空闲盘块链

• 结构：以单个盘块为单位组成空闲链，每个空闲盘块内部存储下一个空闲盘块的指针。
• 分配：文件申请$$K$$个盘块时，从链头依次摘下$$K$$个盘块分配，更新链头指针。
• 回收：将回收的盘块依次挂到链尾，更新链尾指针。
• 特点：适用于离散分配的物理结构；为文件分配多个盘块时需要多次操作，效率较低。

空闲盘区链

• 结构：以**盘区（连续的空闲盘块组）**为单位组成空闲链；每个空闲盘区的第一个盘块内，记录该盘区的长度、指向下一个盘区的指针。
• 分配：可采用首次适应、最佳适应等算法，检索大小合适的空闲盘区分配；也可拆分大盘区，剩余部分保留在链中。
• 回收：若回收区与已有空闲盘区相邻则合并；若不相邻，则作为独立空闲盘区挂到链尾。
• 特点：连续分配、离散分配都适用；为文件分配多个连续盘块时效率更高。

位示图法

连续分配、离散分配均适用，是本章核心考点。

• 原理：每个二进制位对应一个磁盘块。通常约定「$$0$$」表示盘块空闲，「$$1$$」表示盘块已分配（具体含义以题目条件为准）。
  位示图由连续的“字”组成，每个字长为$$n$$位，通过**(字号, 位号)**（也称为行号、列号）与盘块号一一对应。
• 核心转换公式（默认盘块号、字号、位号均从$$0$$开始，字长为$$n$$）：
  已知盘块号$$b$$，推导字号$$i$$、位号$$j$$：
  $$i = \lfloor b / n \rfloor,\quad j = b \bmod n$$
  已知字号$$i$$、位号$$j$$，推导盘块号$$b$$：
  $$b = i \times n + j$$
• 分配流程：
  ① 顺序扫描位示图，找到$$K$$个值为$$0$$的二进制位；
  ② 根据字号、位号计算对应盘块号，分配给文件；
  ③ 将对应二进制位置为$$1$$。
• 回收流程：
  ① 根据回收的盘块号，计算对应的字号、位号；
  ② 将对应二进制位设为$$0$$。
• 重要注意点：
  • 必须看清题目条件：二进制$$0$$/$$1$$分别代表空闲还是占用；盘块号、字号、位号是从$$0$$开始还是从$$1$$开始。
  • 核心考点：盘块号与(字号, 位号)的相互转换计算。

成组链接法

• 背景：空闲表法、空闲链表法不适用于大型文件系统（空闲表/链体积过大），UNIX系统采用该方法管理磁盘空闲块。
• 超级块：文件卷的目录区中，专门用一个磁盘块作为「超级块」，记录第一组空闲块的信息；系统启动时将超级块读入内存，运行中需保证内存与外存超级块的数据一致。
• 核心思想：将大量空闲块分组，组与组之间形成链接关系；第一组的空闲块信息存放在超级块中，后续各组的信息存放在前一组的第一个块内。
• 特点：适合大型文件系统；以理解原理为主，较少考查文字描述类题目。
  

4.1.7文件的基本操作

文件的基本操作通过操作系统提供的系统调用来完成，核心包括创建、删除、打开、关闭、读、写六类操作。

创建文件（ $Create$ ）

图形界面点击“新建文件”的背后，实际调用了 $create$ 系统调用。

1. 主要参数
   • 所需外存空间大小
   • 文件存放路径
   • 文件名
2. 操作系统处理流程
   ① 在外存中为文件分配空闲存储空间（结合空闲链表法、位示图、成组链接法等管理策略）；
   ② 根据文件路径找到对应目录文件，在目录中创建该文件对应的目录项（ $FCB$ ），写入文件名、文件外存位置等信息。

删除文件（ $Delete$ ）

1. 主要参数：文件存放路径、文件名
2. 操作系统处理流程
   ① 根据路径找到对应目录文件，定位文件名对应的目录项；
   ② 根据目录项记录的外存位置、文件大小，回收文件占用的全部磁盘块；
   ③ 从目录表中删除该文件对应的目录项。

打开文件（ $Open$ ）

对文件执行读写操作前，必须先通过 $open$ 系统调用打开文件。

1. 主要参数：文件存放路径、文件名、操作类型（如只读 $r$ 、读写 $rw$ 等）
2. 操作系统处理流程
   ① 根据文件路径查找目录，找到目标目录项，检查该用户是否具备指定的操作权限；
   ② 将目录项中的信息复制到内存中的打开文件表，并将表项的索引号返回给用户，该索引号也称文件描述符。
3. 打开文件表的两层结构
   • 进程打开文件表：每个进程私有一张，记录该进程打开的所有文件；特有属性：读写指针、访问权限。
   • 系统打开文件表：整个系统只有一张，记录全局所有打开的文件；特有属性：打开计数器，记录当前有多少个进程打开了该文件。
4. 作用
   打开文件后，后续操作无需每次都查询磁盘目录，直接通过内存中的打开文件表操作，大幅提升访问速度；后续读写仅需传入文件描述符，无需再使用文件名。

   注意：打开文件不会把文件数据直接读入内存，仅将目录项信息复制到内存。

关闭文件（ $Close$ ）

进程使用完文件后，通过 $Close$ 系统调用关闭文件。
操作系统处理流程：

1. 删除该进程打开文件表中的对应表项；
2. 系统打开文件表的打开计数器减$$1$$；若计数器变为$$0$$，则删除系统表中的对应表项，回收相关资源。

读文件（ $Read$ ）

1. 参数：文件描述符、读取数据量、数据存放的内存地址
2. 处理：操作系统根据读指针，从外存对应位置将指定大小的文件数据，读入用户指定的内存区域。

写文件（ $Write$ ）

1. 参数：文件描述符、写入数据量、数据来源的内存地址
2. 处理：操作系统根据写指针，将内存中指定大小的数据，写回外存对应位置。

补充说明

• 文件打开后，所有读写操作都通过文件描述符指明目标文件，不再需要文件名。
• 系统打开文件表的打开计数器，可用于实现文件占用检测：例如文件被打开时无法删除，就是通过该计数器判断的。
  

4.1.8 文件共享

文件共享主要有两种实现方式：硬链接（基于索引结点） 和 软链接（符号链接）。

硬链接（基于索引结点的共享）

1. 基础背景 索引结点是一种目录瘦身机制：除文件名之外的所有文件信息（物理地址、属性等）都存放在索引结点中，目录项仅包含文件名和索引结点指针。
2. 共享原理 多个用户的目录项指向同一个索引结点，不同用户可以通过各自的文件名，访问同一份文件数据。
3. 链接计数 $count$ 索引结点中设置count链接计数变量，记录当前链接到该索引结点的用户目录项总数。

• 例： $count = 2$ ，表示有$$2$$个用户目录项共享该文件。

1. 删除规则

• 用户执行删除操作时，仅删除自身目录下对应的目录项，同时将索引结点的count减$$1$$。
• 若 $count > 0$ ，说明仍有其他用户使用该文件，不删除文件数据与索引结点，否则会造成指针悬空。
• 只有当 $count == 0$ 时，系统才真正删除文件数据和索引结点。

软链接（符号链接 / 基于符号链的共享）

1. 共享原理 创建一个 Link类型的文件（类似 $Windows$ 系统的“快捷方式”），文件内部记录共享文件的完整存放路径。
2. 访问过程 用户访问Link文件时，操作系统判断其为 $Link$ 类型，根据文件内记录的路径逐层查找目录，最终定位到共享文件的索引结点。
3. 特点

• 即使原共享文件被删除，$Link$ 类型文件依然存在；但再次通过路径查找时会失败，找不到目标文件。
• 访问需要遍历多级目录，产生多次磁盘 $I/O$ ，访问速度慢于硬链接。
  

*4.3.1文件系统的层次结构

例子

4.3.2文件系统布局

磁盘的初始化流程

一块全新的磁盘需要经过三步初始化，才能成为可存放文件的文件系统。

1. 物理格式化（低级格式化）

• 核心工作：将磁盘盘面划分为一个个扇区；检测所有坏扇区，并用磁盘预留的备用扇区替换损坏扇区。
• 完成后磁盘仅具备最基础的扇区读写能力，还没有任何文件系统结构。

2. 磁盘分区

• 通过主引导记录（$ MBR$ ）等机制，将一块物理磁盘划分为多个独立的逻辑分区（文件卷/逻辑盘），例如 $Windows$ 系统的 $C$ 盘、$D$ 盘、 $ E$ 盘。
• 每个分区可以独立采用不同的文件系统。

3. 逻辑格式化（高级格式化）

• 核心作用：在分区上建立具体的文件系统，初始化所有文件管理元数据。
• 以$ UNIX$ 文件系统为例，逻辑格式化后，分区从低地址到高地址的结构依次为：
  1. 引导块：负责开机时的操作系统初始化
  2. 超级块：记录文件系统的核心配置参数
  3. 空闲空间管理区：存放位示图、成组链接等空闲块管理结构
  4. i结点区：存放该分区所有的索引结点（ $inode$ ）
  5. 根目录：文件系统的根目录项，是目录树的起点
  6. 文件数据区：存放普通文件、子目录的实际数据
• 说明：逻辑格式化完成后，管理元数据区域就写入了实际数据；用户数据区初始为空。
  

文件系统的层次结构

操作系统内核对上层提供统一的系统调用接口（如 $open$ 、 $ fopen $ ），同时兼容多种不同的文件系统实现（如 $ UFS、NTFS、FAT $ 等），向下对接不同的物理存储设备（内置磁盘、移动硬盘、U盘等）。 用户进程无需感知底层文件系统类型，通过统一接口即可访问不同介质上的文件。

$open$ 系统调用的完整过程

打开文件是用户访问文件的前置步骤，核心是将磁盘上的目录信息加载到内存，建立快速访问通道。

1. 目录检索 用户传入文件路径与打开方式，操作系统沿路径逐级读取外存的目录文件，找到目标文件对应的 $FCB$ （文件控制块）。

   优化：常用目录会被缓存到内存（目录缓存），减少磁盘 $I/O$ 次数。

2. 写入系统打开文件表 将目标 $FCB$ 复制到内存的系统打开文件表，同时维护「打开计数器」，记录当前共有多少个进程打开了该文件。

3. 建立进程级表项 在当前进程的进程打开文件表中新建一条记录，保存文件打开方式、读写指针、指向系统打开文件表的索引等信息。

4. 返回文件描述符 将进程打开文件表的索引号（文件描述符 fd / 文件句柄）返回给用户进程。
   后续的 $ read、write $ 等操作，用户只需传入文件描述符，系统即可直接通过内存中的表项定位文件，无需再次遍历磁盘目录，访问效率大幅提升。

1. 注册到 $VFS$ ：在 $VFS$ 的挂载表（ mount table ）中登记新文件系统，记录其类型、容量等信息。
2. 提供操作函数：新挂载的文件系统向 $VFS$ 提供自身所有操作的函数地址列表。
3. 挂载到目录树：将新文件系统的根目录挂载到指定的挂载点（父目录），使其成为系统目录树的一部分，用户可通过路径直接访问。