第四章 文件管理

第一节 文件系统基础

「文件」文件的结构

自底向上的方式定义

• 数据项：最低级数据组织形式
  • 基本数据项：一个对象某种属性的一个值，数据中最小逻辑单位。
  • 组合数据项：多个基本数据项组成。
• 记录：一组相关数据项的集合，描述对象在某方面的属性。
• 文件
  • 有结构文件：若干相似记录。
  • 无结构文件：字符流。

「文件」文件控制块（FCB）

• 文件控制块是存放控制文件需要的各种信息的数据结构。
• 文件目录：FCB的有序集合
• 文件目录项：一个FCB

FCB 包含的信息

• 基本信息：文件名等。
• 存取控制信息：权限等。
• 使用信息：文件建立时间等。

注意事项

• 一个目录文件也视为一个文件，为目录文件。

「文件」索引节点

什么是索引节点？

• 文件目录放在磁盘上，当文件目录过多，会占用大量盘块，影响读取速度。
• 由于查找文件时只需要比较文件名，故UNIX系统将文件名和文件描述信息分开，使文件描述信息形成 索引节点(inode) 的数据结构，使调入内存的只有文件名和索引节点，节省系统开销。

磁盘索引节点 包含的内容

• 文件主标识符
• 文件类型
• 文件存取权限
• 文件物理地址
• 文件长度
• 文件链接计数
• 文件存取时间

内存索引节点 在磁盘索引节点增加的内容

• 索引节点编号
• 状态
• 访问计数
• 逻辑设备号
• 链接指针

「文件操作」文件的打开与关闭

打开文件表

• 操作系统维护一个包含所有打开文件信息的文件打开表，避免多次重复的检索目录。
• 文件使用时通过系统调用 open 显式打开会被添加到文件打开表中。
• 打开文件表的每个条目关联一个打开计数器（Open Count）
  • 多一个进程使用系统调用open文件，count++
  • 进程使用系统调用close文件，count--
  • 当 count == 0 时，表示文件不再使用，系统将其从打开表中删除

什么是 “打开”？

• 调用 open 根据文件名搜索目录，从外存复制到内存中文件打开表的一个表目中，将表目索引返回给用户。
• 用户再次发出文件操作请求是，可通过索引在文件打开表中查找文件信息，节省开销。
• 文件不再使用时，通过系统调用close关闭文件，系统将该条目从打开文件表中删除。

注意事项

• 文件名不一定是打开文件表的一部分。
• 打开文件表的索引，UNIX称为文件描述符，Windows称为文件句柄。

\

「文件保护」访问类型

• 读、写、执行、添加、删除、列表清单。

「文件保护」访问控制

• 为每个文件和目录增加一个访问控制列表（Access-Control List，ACL），规定每个用户允许访问的类型。

「文件逻辑结构」无结构文件（流式）

特点

• 最简单的文件组织形式，按顺序组织，以字节为单位。
• 管理简单，方便操作。
• 难以搜索。

「文件逻辑结构」有结构文件（记录式）

顺序文件

• 串结构
  • 记录顺序与关键字无关，时间排序，检索费时。
• 顺序结构
  • 按关键字顺序排列，折半查找效率高。

索引文件

• 索引表
  • 对变长记录文件建立一张索引表，给主文件的每个记录在索引表中设置一个表项，记录变长记录的逻辑起始地址和记录长度，按关键字排序。
  • 索引表为定长记录顺序文件，加快检索速度。

索引顺序文件

• 顺序文件和索引文件的结合。
• 同组关键字可无序，组与组之间必须有序。
• 通过索引表找组，组内顺序查找。

「文件逻辑结构」散列文件（Hash）

• 通过键值或散列函数转换的键值直接找到记录的物理地址。
• 有很高的存储存取速度，但是会引起冲突。

「文件物理结构」连续分配

• 每个文件在磁盘上占有一组连续的块。
• 支持循序访问和直接访问。

连续分配的优缺点

• 优点
  • 实现简单，存取速度快。
• 缺点
  • 文件长度不好动态增加，因为末尾可能分配给其他文件。
  • 保持文件有序性，插入删除会对相邻记录做移动，会动态改变文件长度。
  • 反复增删文件可能会产生外部碎片。
  • 难以确定一个文件所需空间大小，适用于长度固定文件。

「文件物理结构」链接分配

• 离散分配方式，消除磁盘外部碎片，可动态为文件分配盘块。

隐式链接

• 目录项含有文件第一块指针和最后一块指针。
• 除了最后一个盘块，每个盘块都含有指向下一个盘块的指针。
• 指针对用户透明。

隐式链接缺点及解决方案

• 缺点
  • 只适合顺序访问，访问效率低，稳定性差（丢失一个指针，后面数据全部丢失）。
• 解决方案
  • 几个盘块组成 簇 (cluster)，按簇分配，减少查找时间，增加了内部碎片。

显式链接

• 在整个磁盘中仅设置一张存放在内存中的文件分配表（File Allocation Table，FAT），每个表项存放指向下一个盘块的链接指针。
• FAT 在系统启动时就会被读入内存，提高检索速度。
• FAT 解决了连续分配的外部碎片和文件大小管理的问题，但 FAT 占用较大的内存空间。

索引分配

• 将每个文件的所有盘块号集中一起构成索引块（表）。

索引分配的优缺点和解决办法

• 优点：支持直接访问，无外部碎片问题。

• 缺点：多了索引块，增加内存开销。

• 每个文件必须有一个索引块，大了占用内存空间，小了无法索引大文件，索引分配难以索引大文件的解决办法

  • 链接方案：多个索引块链接起来。
  • 多层索引：一级索引块指向二级索引块。
  • 混合索引

混合索引分配

• 小文件
  • 每个盘块地址直接放入FCB，直接寻址。
• 中型文件
  • 单级索引，一次间址。
• 大型文件和特大型文件
  • 两级和三级索引分配。

第二节 目录

「目录结构」单级目录结构

• 实现按名存取，查找速度慢，文件不允许重名，多用户操作系统不适用。
• 也就是说，A用户创建了一个名为 daynoti 的文件夹，B用户无法创建名为 daynoti 的文件夹了。

「目录结构」两级目录结构

• 文件分为主文件目录（Master File Directory，MFD）和用户文件目录（User File Directory，UFD）。
  • 主文件目录：记录用户名及相应用户文件目录所在的存储位置。
  • 用户文件目录：记录该用户文件的FCB信息。

如何解决不同用户创建文件夹重名问题

• 用户对文件进行访问时，先搜索该用户对应的UFD，解决了不同用户文件的重名问题。

两级目录结构的优缺点

• 优点
  • 提高检索速度，解决多用户之间文件重名问题，文件系统可在目录上实现访问限制。
• 缺点
  • 缺乏灵活性，不能对文件分类。

「目录结构」树形目录结构

• 树形目录结构是两级目录结构的推广，便于实现文件分类，不便于实现文件共享。

「目录结构」无环图目录结构

• 在树形目录结构的基础上增加了一些指向同一结点的有向边，使目录成为有向无环图。
• 每个共享结点都有一个计数器，多一个用户共享该结点，计数器 + 1，少一个 - 1，直到计数器 == 0时，才真正删除该结点。

「文件共享」硬链接（索引结点共享）

• 文件的物理地址和其他的文件属性等信息，不放在目录项中，放在索引节点中。
• 文件目录中只设置文件名及指向相应索引节点的指针。
• 索引节点有一链接计数器count，用于表示链接到本索引节点上的用户目录项数目。
• 同样，用户删除文件时，是无法删除该文件本身，而是删除自身目录项条目，索引结点count--。

「文件共享」软链接（符号链共享）

软链接的使用及读取过程

• 用户B共享用户A的一个文件F，系统创建一个类型为LINK的新文件H，放入B的目录中。
• 新文件H只包含被链接文件F的路径，操作系统读到类型为LINK的文件时，会根据文件中的路径找到文件F进行读取。

软链接不会出现悬空指针

• 只有文件主采用有指向索引节点的指针，其他共享用户只可以按照路径查找该索引节点。
• 所以当文件主删除该索引节点时，其他用户试图通过符号链访问时，会访问失败，于是自动删除符号链，没有任何影响，不会悬空指针。

硬链接和软链接的区别

区别	特点	速度
硬链接	多个指针指向一个结点，但凡有一个指针指向，结点就不能删除	快
软链接	根据共享文件的路径寻找文件	慢

「文件系统」文件系统结构

层次图

• IO控制：包括设备驱动程序和中断处理程序，在内存和磁盘之间传输信息。
• 基本文件系统：向设备驱动程序发送通用命令，读取写入磁盘的物理块。
• 文件组织模块：组织文件和它的逻辑块、物理块，并能地址转化。
• 逻辑文件系统：管理元数据信息（包括文件系统所有结构，不包括数据），文件保护。

「文件系统」磁盘中的结构

名词简单描述

• 主引导记录（Master Boot Record，MBR）
• 引导块（boot block）
• 超级块（super block）
• 文件系统中空闲块信息

「文件系统」内存中的结构

结构类型

• 内存中的安装表（mount table）：每个已安装文件系统分区的有关信息。
• 内存中的目录结构的缓存（包含最近访问目录的信息）：对安装分区的目录会包括一个指向分区表的指针。
• 整个系统的打开文件表：包含每个打开文件的FCB副本和其他信息。
• 每个进程的打开文件表：包含一个指向整个系统的打开文件表中的适当条目的指针和其他信息。

注意事项

• 一旦文件被打开，系统就不再通过文件名访问文件，而是通过文件描述符（Windows为文件句柄）。

「文件系统」外存空闲空间管理

什么是 卷？

• 包含文件系统的分区通常称为 卷，可以使磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成的RAID集。
• 在一个卷中，文件区（数据空间）和目录区（FCB空间）是分离的。

• 文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配和回收等问题。

「空闲空间管理」空闲表法

• 属于连续分配方式，和内存动态分配类似。
• 系统为外存所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。

「空闲空间管理」空闲链表法

• 空闲盘块链
  • 将磁盘上所有空闲空间以盘块为单位拉成一条链。
  • 链首分配，链尾回收（空闲块插入链尾）。
  • 优点：分配和回收非常简单。
  • 缺点：为一个文件分配盘块会重复多次，效率低；盘块为单位，链很长。
• 空闲盘曲链
  • 将磁盘上所有空闲盘区（每个盘区包含若干盘块）拉成一条链。
  • 每个盘区有指向下一盘区的指针；有指明本盘区大小的信息。
  • 盘区分配和内存动态分配相似，采用首次适应算法。
  • 回收盘区时将会收取和相邻空闲盘区合并。
  • 缺点：分配回收过程复杂。
  • 优点：分配回收效率高，链短。

「空闲空间管理」位示图法

• 利用二进制的一位表示盘块使用情况，0空闲，1占用。

盘块的分配

1. 顺序扫描位示图，找出一个或一组值为 0 的二进制位。
2. 将找到的 0，根据公式转换成对应的盘块号，i 行，j 列，n 每行行数。

$$b=n(i-1)j$$

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

盘块的回收

1. 将回收盘块的盘块号根据公式转换成位示图中的行号和列号。

$$i=(b-1)DIVn+1$$$$j=(b-1)MODn+1$$

2. 修改位示图，令 $map[i,j]=0$。

注意事项

• 空闲表法和空闲链表法都不适用于大型文件系统，会导致空闲表或空闲链表太大。

「空闲空间管理」成组链接法

• UNIX 采用成组链接法，结合了空闲表和空闲链表法两种方法。

• 成组链块：用来存放一组空闲盘块号的盘块。

成组链接法的大致思想

• 把顺序的 n 个空闲盘块号保存在第一个成组链块中，将最后一个空闲盘块（最为成组链块）用于保存另一组空闲盘块号，系统只保存指向第一个成组链块的指针。

盘块的分配

• 根据第一个成组链块的指针，将盘块分配给用户，指针下移一格。
• 若指针指向的是成组链块（最后一个盘块），因为该盘块记录的是下一组空闲盘块号，需要将该盘块读入内存，并将指针指向新的成组链块的第一条记录，执行上述分配操作。

盘块的回收

• 成组链块的指针上移一格，记入回收盘块号。
• 当成组链块的链接数达到 n 时，表示已满，便将现有已记录 n 个空闲盘块号的成组链块号记入新回收的盘块（新的成组链块）。

本章总结

「文件」文件物理分配方式的比较

「文件」文件打开过程描述