（一）文件
1. 基本概念
文件是具有文件名的若干相关元素的集合；
“元素” 通常是指记录；
“记录” 是一组有意义的数据项集合；
层次结构（由下至上）：数据项
记录 文件；
数据项：文件系统中最低级的数据组织方式，分为两种
1）基本数据项：描述一个对象某种属性的字符集；
是数据组织中最小的可命名单位，又称原子数据、数据元素、字段；
例：“学生” 的基本数据项：姓名，学号等；
2）组合数据项： 若干个基本数据项组成的，简称组项；
- 例：“工资” 由基本工资，绩效工资，工龄工资等组成；
记录：一组相关数据项的集合，描述对象某个方面的信息；
文件：具有文件名的若干相关元素的集合，分为有结构文件和无结构文件两种；
- 文件的一些属性：类型、长度（大小）、物理位置、创建时间、修改时间等；
2. 文件名和类型
- 文件名和扩展名；
3. 文件元数据和索引节点
3.1. 文件控制块 FCB（File Control Block）
通常含有 3 类信息：基本信息、存取控制信息、使用信息；
基本信息：(1) 文件名；(2) 物理位置；(3) 逻辑结构；(4) 物理结构；
逻辑结构：用户决定的文件内容的组织形式；
物理结构：描述了文件的内容在磁盘上的存放情况；
存取控制信息：文件所有者的存取权限，核准用户和普通用户的存取权限；
使用信息：创建和修改时间，当前打开该文件的进程，在内存中是否被修改等；
- 不同 OS 的实现不同；
3.2. 索引节点
引入：因为磁盘的分块存储，当一个目录下文件较多时，目录文件就要占用大量磁盘块。
- 例：若 FCB 为 64B，一个块大小 1KB，一个目录有 640 个文件，对应 640 个 FCB，则一个目录文件就要占据 40 个盘块。在此目录中，顺序查找一个文件平均需要进行 20 次磁盘 IO；
索引节点：又称 i 节点，将文件名和 FCB 分开存储，减少目录文件的大小，以减少查找文件的 IO 次数；
在 UNIX 系统中，一个目录项仅占 16B，其中 14B 为文件名，2B 为指向 i 节点的指针；在
- 1KB 盘块可存放 64 个目录项，与上述情况相比，平均 IO 次数可降至
；
- 1KB 盘块可存放 64 个目录项，与上述情况相比，平均 IO 次数可降至
磁盘索引节点：
存放在磁盘上的索引节点，每个文件唯一，包含
包含：(1) 文件所有者标识符；(2) 类型；(3) 存取权限；(4) 物理地址；(5) 长度；(6) （硬）连接计数（UNIX 系统）；(7) 存取时间信息；
内存索引节点：
打开文件时，将磁盘索引节点复制到内存，并添加一些内容；
添加：(1) 内存索引节点编号；(2) 读写状态，用于多进程同步和读写保护；(3) 访问计数；(4) 所属文件系统的逻辑设备号；(5) 指向一些队列的指针；
4. 访问权和保护域
访问权：指进程对某个对象执行操作的权力；
对象：可以是硬件资源如打印机，也可以是软件资源，如文件；
操作：对特定对象的操作，如文件的操作有 Read, Write；
保护域：简称为 “域”，是指进程对一组对象的访问权限的集合，进程只能在特定域内进行操作；
5. 访问矩阵
5.1. 基本访问矩阵
利用一个矩阵描述系统的访问控制信息，行代表域，列代表对象，每一个元素是一组访问权；
矩阵元素
定义了域 中的进程能对对象 执行的操作集合； 图示
实际 OS 通常不直接使用基本访问矩阵，而是如下所示的的简化的实现方式；
5.2. 访问控制表（Access Control List，ACL）
为矩阵中的每一列（对象）单独建立一张表，每个表项为 （域，操作权集合），无操作权的域不包含在内；
因为大多数情况下，矩阵中的空项远多于非空的，因此 ACL 可以减小存储空间，提高查找速度；
5.3. 访问权限表
- 和 ACL 类似，为每一行单独建立一张表，表项为（对象，操作权集合）；
6. 文件的逻辑结构
6.1. 引入
文件的逻辑结构：用户角度，描述逻辑记录的组成，是用户可以直接处理的数据，独立于物理特性；
- 又称为 “文件组织”；
文件的物理结构：OS 角度，描述文件在外存的存储和组织，与 OS 采用的外存分配方式有关；
逻辑结构的目标
提高文件检索的速度；
方便修改；
降低文件的存储成本（减少文件占用的存储空间）
1）按文件是否有结构分类
有结构文件：由定长记录或变长记录组成。广泛用于数据库系统；
无结构文件：又称流式文件，长度以字节为单位。系统中大量的源程序，可执行文件等都是无结构文件；
2）按文件组织方式划分（对于有结构文件）
顺序文件：一系列记录按照某种顺序排列而成的文件。通常是定长记录；
索引文件：文件有变长记录时，建立一张索引表索引每个记录，加快检索速度；
索引顺序文件：由若干记录组组成的文件，每个记录组是定长记录顺序排列，通常为每组记录中的第一个建立索引；
6.2. 顺序文件
2 种排列方式：(1) 串排列；(2) 顺序排列；
串排列：顺序和关键字无关，通常按照创建时间顺序排列；
顺序排列：根据某个关键字，按照一定顺序排列；
优缺点
优点：适合大量文件需要批量读写，所有逻辑结构中，顺序文件存取效率最高；
缺点：对于单个记录的增删改查效率较低；
记录的寻址：隐式和显式寻址（了解）
隐式寻址：通过当前记录的地址确定下一个记录的地址，适用于所有顺序文件；
显式寻址：通过一个整数来唯一标识所有记录，通过地址运算实现随机访问，只适用于定长记录的顺序文件；
6.3. 索引文件
本质是一个定长记录的顺序文件，每个表项定位主文件中的一个记录；
- 因为是定长记录的顺序文件，所以可以采用快速查找算法；
1）按关键字建立索引；
2）多个索引表的索引文件：为实现按不同关键字检索主文件记录的要求；
6.4. 索引顺序文件
改进了顺序文件的实现，克服了变长记录不能随机访问，和不便于增删改查的缺点；
新特征：(1) 建立索引表；(2) 增加溢出文件，记录增加的，修改的和删除的相关记录；
1）一级索引顺序文件：将所有记录分成
个组，为每组的第一个记录建立索引，表项包含该记录的关键字和指针； 2）二级索引顺序文件：为多个索引表建立二级索引表，目的是为了减少表项数量，加速查找；
6.5. 直接文件和哈希文件
直接文件：指可以通过关键字直接得到记录物理地址的文件，无需先找到索引；
哈希文件：是目前最广泛的直接文件的一种实现方式，通过哈希函数，将关键字映射到某个地址表的表项，该表项存放记录的物理地址，直接指向该记录；
7. 文件的物理结构
7.1. 连续组织方式
又称连续分配方式，为每个文件分配一组相邻的盘块；
读写时，相邻磁盘块位于同一磁道上，所以不需要移动磁头，效率很高；
将文件中的记录连续存放在相邻磁盘块中，则此文件物理上为顺序文件，逻辑结构为顺序结构；
优点：顺序访问容易，且访问速度快；
缺点：(1) 需要连续的磁盘块；(2) 必须事先知道文件长度，无法存放运行时动态增长的文件；(3) 对于记录增删改查效率低；
7.2. 链接组织方式
将文件分装到多个离散的盘块中，通过盘块上的链接指针或者文件分配表来寻址同一个文件的盘块，此种方式组织的文件称为链接文件；
隐式链接：使用盘块上的链接指针；
显式链接：使用文件分配表；
优点
无需连续盘块，提高了外存利用率；
增，删，改文件为链表操作，复杂度低；
无需事先知道文件大小，可以适应动态增长的文件；
隐式链接
通过盘块上的链接指针来访问下一个盘块；
每个文件的目录项包含：文件名、起始盘块号和最后盘块号；
- 实际上最后盘块号不是必须的，可以将其链接指针置为特殊值来标识（如 EOF）
缺点：对于某个盘块的随机访问复杂度高，查找速度慢（链表需要遍历之前的）；
显式链接
利用**文件分配表（File Allocation Table，FAT）**查找下一个盘块；
FAT 表整个磁盘仅设置一张，使用时加载进内存；
表示 号盘块的下一个盘块号为 ； 或 表示 号盘块是某个文件的最后盘块；
FCB 中仅存储文件开始盘块的序号；
显式链接：FAT12 文件系统
早期的 FAT12 文件系统：以盘块为基本单位（如 MS-DOS）；
- 为安全起见，每个分区都有两张相同的 FAT 互相备份，为 FAT1 和 FAT2；
MS-DOS 文件系统物理结构
簇为单位的 FAT12 文件系统
簇（cluster）是一组相邻的扇区（盘块），分配盘块时，以簇为单位；
一般连续 2n 个扇区为一个簇，簇也叫做逻辑块；
总结：链接组织方式的缺点
对于大文件的存取，需要查找大量盘块号，效率低；
显式链接 FAT 占据较大存储空间（外存 + 内存）；
7.3. 索引组织方式
单级索引方式
利用一个盘块（图中 19 号）来专门记录文件的物理块号，称为索引块；
目录项中存放文件名和索引块号；
索引块中的表是顺序表，因此支持高效随机访问。同时一定程度上支持动态增长；
多级索引方式（两级索引为例）
- 大文件需要多个索引块来寻址，则 OS 再分配一个主索引去索引这些索引块；
7.4. 增量式索引组织方式
根据文件的大小动态选择对应的组织方式，如：
小文件：盘块地址直接放入 FCB；
中型文件：单级索引；
大文件：多级索引；
7.5. Unix System V 的组织方式
Unix System V 的索引节点 i 中有 13 个地址项（
） 混合索引方式
：10 项，直接指向物理块； ：1 项，单级索引； ：1 项，二级索引； ：1 项，三级索引；