操作系统之文件管理
概述
文件是指具有文件名的若干相关元素的的集合
1 文件和文件系统
1.1 基本概念
1.1.1 数据项
最低级的数据组织形式
- 基本数据项 数据组织中可命名的最小逻辑数据单位。
- 组合数据项
1.1.2 记录
描述对象某属性的相关数据项的集合 关键字是惟一能标识一个记录的数据项
1.1.3 文件
由创建者定义且有文件名的相关元素集合
1.2 文件类型和文件系统模型
- 按用途
- 系统文件 由系统软件构成的文件
- 库文件 文件允许用户对其进行读取和执行 主要由各种标准子程序库组成，例如：C语言子程序库存放在子目录下 *.LIB,/lib/,/usr/lib/
- 用户文件 是用户通过操作系统保存的用户文件，由文件的所有者或所有者授权的用户才能使用
- 按存取控制属性
- 只读文件
- 读写文件
- 可执行文件
- 各个操作系统的保护方法和级别有所不同
- 按组织形式和处理方式
- 普通文件 由ASCII码或二进制码组成的字符文件
- 目录文件 是由文件的目录信息构成的系统文件 操作系统将目录也做成文件，便于统一管理
- 特殊文件 特指系统中的各类I/O设备 所有的输入输出外部设备都被看作特殊文件便于统一管理 按文件方式提供给用户使用
1.3 文件操作
1.3.1 文件“打开”(重点)
- 为了避免多次重复地检索目录
- 在大多数OS中都引入了“打开”(open)这一文件系统调用
- 当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开
将文件属性从外存拷到内存中打开文件表的一表目中 将其编号返回给用户。 系统可利用该编号到打开文件表中去查找。
1.4 文件的逻辑结构 (重点)
- 文件的逻辑结构（文件组织） 从用户观点出发，所观察到的文件组织形式 是用户可以直接处理的数据及其结构 它独立于物理特性。
按文件结构
- 有结构文件 在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。
- 无结构文件 以字节为单位的流式文件。 Unix中，所有的文件被看成流式文件 流式文件多采用读/写指针来指下一要访问的字符。
按文件组织方式
顺序文件
由一系列记录按某种顺序排列所形成的文件。
可以按照各种不同的顺序进行排列：
- 串结构 各记录之间的顺序与关键字无关。通常由时间决定
- 顺序结构 记录按关键字(词)排列
顺序文件的优缺点
- 对诸记录进行批量存取时，存取效率高
- 交互应用场合的查找/修改记录性能差
- 增加/删除记录比较困难
- 运行记录文件，或称为事务文件
只有顺序文件才能存储在磁带上，并能有效地工作
索引文件
当记录为可变长度时，通常为之建立一张索引表，为每个记录设置一个表项 索引表是按记录键排序的,本身是一个定长记录的顺序文件,可以方便地实现直接存取。
使用索引表，每个表目包含一个记录的键及其记录的逻辑地址，这类文件称索引文件。
- 优点 检索速度快 主要用于对信息处理的及时性要求较高的场合
- 缺点 存储费用高，因为除了主文件外，还需配置一张索引表 每个记录都有一个索引项 当增加新记录/删除记录时，需对索引表进行修改
索引顺序文件
有效地克服了变长记录文件不便于直接存取的缺点 所付出的代价也不算太大。
可为变长记录文件建立一张索引表 主文件中的每个记录在索引表中设有一相应的表项
将顺序文件中的所有记录分为若干个组。 为顺序文件建立一张索引表，为每组中的第一个记录建立一个索引项。 实现了组间索引，组内顺序。
索引顺序文件
3 目录管理
对目录管理的要求如下
- 实现“按名存取” 。 目录管理中最基本的功能
- 提高对目录的检索速度
- 文件共享 须在外存中只保留一份文件的副本。
- 允许文件重名。 允许不同用户对不同文件取相同的名字
3.1 文件控制块（FCB）
- 用于描述和控制文件的数据结构
- 文件管理程序可借助FCB中的信息对文件施以各种操作
文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录 通常，一个文件目录本身也被看作是一个文件， 称为目录文件
- 基本信息类 文件名、物理位置 、逻辑结构 、物理结构
- 文件控制信息类 文件拥有者权限、核准用户权限、一般用户权限
- 使用信息类 文件建立日期、文件修改日期
3.2 索引结点(重点)
使文件描述信息单独形成一个称为索引结点的数据结构 文件目录通常是存放在磁盘上的 在查找目录的过程中
- 先将存放目录文件的第一个盘块中的目录调入内存
- 把用户所给定的文件名与目录项中的文件名逐一比较
- 若未找到指定文件，再将下一个盘块中的目录项调入内存
假如一个FCB为64 B，盘块大小为1 KB，若一个文件目录中共有640个FCB，需占用 40 个盘块 每个盘块中只能存放： 16 个FCB 平均查找一个文件需启动磁盘 20 次
- 平均查找一文件需启动磁盘次数太多。
- 在检索目录文件的过程中，只用到了文件名
- 仅当一目录项中的文件名与指定要查找的文件名相匹配时，才需从该目录项中读出文件的物理地址。
UNIX系统采用了把文件名与文件描述信息分开的办法
UNIX系统——索引结点的引入
若每个目录项占16B，盘块大小为1 KB 每盘块可存 64 个目录项 640个目录项只占10个盘块 为检索到一个文件，平均启动磁盘次数=5 查找目录时间大大缩短
3.2.1 磁盘索引结点
- 每个文件有惟一的一个磁盘索引结点
- 存放在磁盘上的索引结点。
文件主标识符。 文件类型。 文件存取权限 文件物理地址： iaddr(0)～iaddr(12)以直接或间接方式给出数据文件所在盘块的编号 文件长度 文件链接计数 文件存取时间
3.2.2 内存索引结点
当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中。
增加了以下内容： 索引结点编号--用于标识内存索引结点。 状态:指示i结点是否上锁或被修改。 访问计数:每当有一进程要访问此i结点时，将该访问计数加1，访问完再减1。 文件所属文件系统的逻辑设备号。 链接指针--设置有分别指向空闲链表和散列队列的指针
3.3 简单的文件目录
3.3.1 单级文件目录
在整个文件系统中只建立一张目录表 每个文件占一个目录项 目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性。 为表明每个目录项是否空闲，又设置了一个状态位。
简单且能实现目录管理的基本功能:按名存取
- 缺点 查找速度慢 不允许重名 不便于实现文件共享 应当允许不同用户使用不同的文件名来访问同一个文件
3.3.2 两级文件目录
可为每一个用户建立一个单独的用户文件目录。 所有用户的文件目录具有相似的结构 它由用户文件控制块组成。
两级文件目录
提高了检索目录的速度。 在不同的用户目录中，可使用相同的文件名。 不同用户可用不同的文件名访问同一共享文件。
隔离的缺点
- 相互合作去完成一个大任务
- 用户又需去访问其他用户的文件
3.3.3 树形结构目录(重点)
主目录被称为根目录，把数据文件称为树叶，其它目录作为树的结点。
树形目录
路径名
- 每个文件有又惟一的路径名
- 从根目录开始，把全部目录文件名与数据文件名依次地用“/”连接起来，构成该数据文件的路径名。
image.png
当前目录(工作目录)
进程对各文件的访问都相对于“当前目录”而进行 在UNIX/Linux 系统中，“ . ”是指当前目录，“..”是指父目录。
当前目录
Linux层次目录结构
3.4 目录查询技术——线性检索法
在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名。 /usr/ast/mbox
线性检索法
4 文 件 共 享
- 定义 系统应允许多个用户共享同一份文件，在系统中只保留一份共享文件的备份
- 目的 节省时间和存储空间，减少了用户工作量
4.1 基于有向无循环图实现文件共享
当多个用户要共享一子目录或文件时，须将共享文件或子目录链接到多个用户的目录中，才能方便地找到该文件，此时文件系统的目录结构是个有向非循环图。
有向无循环图DAG
4.2 利用索引结点的共享方式(硬链接）(重点)
由任何用户对文件进行Append操作或修改，所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见的，从而也就能提供给其他用户来共享。
ln Wang/Test Lee/ABC
image.png
进程B链接前后的情况
当文件主删除文件时，并没有真正删除该文件和索引结点。只有等到链接计数count=0时，才真正删除该文件。
image.png
4.3 利用符号链实现文件共享（软链接）(重点)
利用符号链实现文件共享
- 在利用符号链实现文件共享时，只是文件主才拥有指向其索引结点的指针；
- 共享该文件的其他用户则只有该文件的路径名,并不拥有指向其索引结点的指针
- 优点
- 能够用于链接(通过计算机网络)世界上任何地方的计算机中的文件
- 缺点
- 在每次访问共享文件时，都可能要多次地读盘
- 符号链实际上是一个文件，尽管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间
image.png
4.4 硬链接和软链接
- 硬链接 将文件名和自身的inode链接起来,只能用单个文件系统
- 符号链接（软链接） 符号链接是一种只有文件名,通过文件名来引用文件
5 文件保护
- 存取控制机制 防止由人为因素所造成的文件不安全性。
- 采取系统容错技术 防止系统部分的故障所造成的文件的不安全性。
- 建立后备系统 防止由自然因素所造成的不安全性
5.1 访问矩阵(重点)
基本的访问矩阵
- 行代表域，列代表对象
- 矩阵中的每一项是由一组访问权组成的。
- 每一项访问权access(i, j)定义了在域Di中执行的进程能对对象Qj所施加的操作集。
image.png
5.1.1 访问矩阵的实现
访问控制表(Access Control List) 对访问矩阵按列(对象)划分 为每一列建立一张访问控制表ACL。 当对象是文件时，访问控制表作为文件存取控制信息，存放在该文件的文件控制表中 减少所占用的存储空间，并能提高查找速度。
image.png
5.1.2 访问权限(Capabilities)表
每一行构成一张访问权限表。 表中的每一项即为该域对某对象的访问权限。 当域为用户(进程)、对象为文件时 访问权限表便可用来描述一个用户(进程)对每一个文件所能执行的一组操作。
6 文件物理结构(重点)
6.1 连续分配（顺序式的文件结构）
为每一文件分配一组相邻盘块,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中所形成的文件结构 该分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。
磁盘空间的连续组织方式
- 优点
- 顺序访问容易，支持顺序存取和对定长记录文件随机存取
- 顺序访问速度快 磁头的移动距离最少，对文件访问的速度是几种存储空间分配方式中最高的一种。
- 缺点
- 要求有连续的存储空间
- 会产生许多外部碎片，降低利用率。
- 如定期紧凑消除碎片又需花机器时间。
- 须事先知道文件的长度
- 对动态增长文件较难
- 必须事先估计文件的长度
- 要求有连续的存储空间
6.2链接组织方式（链接式的文件结构）
1.2.1 隐式链接
在文件目录的每目录项中，须含有指向链接文件第一个盘块和最后一个盘块的指针。 每一个物理块中设有一个指针，指向下一个物理块的位置
主要问题在于
- 随机访问极其低效 若要访问第i个盘块，必须读出前i-1个
- 只通过链接指针来将一大批离散的盘块链接起来
- 可靠性较差
- 只要其中的任何一个指针出现问题，都会导致整个链的断开
1.2.2 显式链接(重点)
把链接文件各物理块的指针，显式地存放在内存中一链接表中。 在整个磁盘仅设置一张该表。 查找记录的过程是在内存中进行的,因而可显著提高检索速度，且大大减少了访问磁盘的次数
image.png
显式链接
1.2.3 FAT和NTFS技术
- 把具有16位表宽的FAT表称为FAT16 将FAT表的宽度增至16位，最大表项数将增至 65536 个 将一个磁盘分区分为 65536 个簇。 在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64 由此得出FAT16可以管理的最大分区空间为： 216×64×512=2048MB （每个盘块为512字节）
- FAT12 以盘块为基本分配单位 在FAT的每个表项中存放下一个盘块号，它是用于盘块之间的链接指针 每个表项占12位 最大表项数： =212 =4096个 每个分区最大: =4096*512B=2M
image.png
- 簇的基本概念
- 能适应磁盘容量不断增大的情况 不以盘块而是以簇(cluster)为基本单位
- 簇是一组连续的扇区（扇区称为盘块）,在FAT中它是作为一个虚拟扇区， 簇的大小一般是2n(n为整数)个盘块。
- 可减少FAT表中的项数。 使FAT表占用更少的存储空间，减少存取开销，提高文件系统效率；
- 这也会造成更大的簇内零头
- FAT16
- 把具有16位表宽的FAT表称为FAT16 将FAT表的宽度增至16位，最大表项数将增至65536个 将一个磁盘分区分为65536个簇。
- 在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64
- 由此得出FAT16可以管理的最大分区空间为： 216×64×512=2048MB （每个盘块为512字节）
- FAT32 FAT32是FAT系列文件系统的最后一个产品。 每一簇在FAT表中的表项占据4字节 允许在FAT32中采用较小的簇 FAT32的每个簇都固定为4KB=8×512B 每簇用8个盘块，每个盘块仍为512字节 FAT32分区格式可以管理的单个最大磁盘空间大到2TB
1.3 索引组织（索引式文件结构）
1.3.1 单级索引组织
链接方式的问题
- 不能支持高效的直接存取
- FAT需占用较大的内存空间
应将每个文件所对应的盘块号集中地放在一起, 为每个文件分配一个索引块(表), 把分配给该文件的所有 盘块号 都记录在该索引块中 支持直接访问 对于大文件而言，该方式优于链式组织方式
主要问题
- 需要较多外存空间来建立索引块
- 对于小文件，空间浪费严重
- 当文件太大，效率低
1.3.2 多级索引组织
多级索引分配
1.3.3 混合索引分配方式
image.png
2文件存储空间管理(重点)
image.png
image.png
image.png
image.png