第 5章 文件管理
文件系统概述
文件的结构和存取方式
文件目录
文件存储空间的管理
文件的使用、共享与保护
文件系统的性能问题
5.1.1 文件的概念
1,文件外存中具有符号名的一组有逻辑意义的信息项的集合 。
2,文件系统指 OS中管理文件的那一部分软件。它负责管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并 为用户提供一整套方便有效的文件使用和操作方法 。 它在 OS接口中占比例最大，是 I/O系统的上层软件。文件系统面向用户的主要任务是实现文件的“按名存取”。
5.1.2 文件分类
分类角度多。比如，可按文件的用途、文件中数据的形式、存取控制属性、文件信息的保存期限、文件的逻辑结构、文件的物理结构等进行分类。
UNIX系统将文件分为三类,
普通文件 (包括用户的 ASCII或二进制文件 )；
目录文件 ；
特殊文件 （ 设备文件,管道，套接字，符号链等）
5.2 文件结构与存取方法文件的结构指文件中信息的配置和构造方式，有逻辑结构和物理结构之分。
1,文件的逻辑结构
用户眼中文件信息的组织形式叫文件的逻辑结构。它包括记录式文件和流式文件两种，每种文件信息的逻辑单位分别是记录和字符。
UNIX系统视所有文件的逻辑结构为无结构的流式文件
早期有结构的记录式文件又分定长和不定长两种，流式文件可看作特殊的定长记录式文件
文件的逻辑结构与文件的存储介质无关
2,文件的物理结构
系统眼中文件 信息的组织形式叫文件的物理结构。它包括顺序文件、链接文件、索引文件三种 （实为连续文件与不连续文件两大类）
文件的物理结构也叫文件的存储结构，指文件在外存上的存储组织形式，它与存储介质的性能和外存的分配方式有关
顺序文件,文件的信息存放在若干连续的物理块中。特点,实现简单，顺序存取速度快，
但分配慢，外存碎片多 （似内存的可重定位可变分区分配）
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
文件名 始址 块数
count 0 2
tr 14 3
mail 19 6
list 28 4
f 6 2
文件目录count
f
tr
mail
list
磁盘空间连续分配产生顺序文件：
磁盘空间
链接文件：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接。
特点：提高了磁盘空间利用率,不存在外部碎片问题，有利于文件长度动态变化，
但存取速度慢（不适合随机存取，寻道时间长），可靠性差，指针占空间。
链接文件按链接指针的不同实现又分为隐式链接文件和显式链接文件,MS DOS、
Windows中采用的是后者，其 FAT和簇的概念是传统链接结构的变形文件名 始址 末址
jeep 9 25
文件目录
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
1
10
16
-1
25
磁盘空间链接式分配产生链接文件：
磁盘空间
索引文件：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个索引表，
并将这些物理块号存放在其中
一个索引表就是磁盘块地址数组,其中第 i个条目指向文件的第 i块
索引表组织,单级索引、多级索引,Hash索引。
UNIX文件系统采用多级索引结构
特点：既能顺序存取，又能随机存取，支持文件长度动态变化，外存利用率高，但索引表需占额外空间。
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
文件名 索引表地址文件目录
Jeep 19
9
17
1
10
25
-1
-1
-1
19
磁盘空间索引式分配产生索引文件：
文件 jeep的单级索引表
UNIX System V
采用多级混合索引方式索引结点中的
13个地址项十个直接地址项三次间接地址块一次间接地址块二次间接块一次间接块一次间接块二次间接块物理块物理块物理块设每个盘块 4kB，每个盘块号 4B，则采用
3次间址可表示的文件最大长度为：
4T+4G+4M+40K(B)
3,文件的存取方式当今 OS支持的文件存取方式主要有顺序存取和随机存取两种。
顺序存取对文件中的信息按逻辑顺序进行读 /写的存取方式称顺序存取
随机存取对文件中的信息按任意顺序进行读 /写的存取方式称随机存取
早期系统中记录式文件所对应的第三种存取方式 —— 按键存取 现在多见于 DBMS中
4,文件的 存储介质磁带，磁盘，光盘，优盘,……
以块为单位进行信息的存储、传输、分配
磁带：顺序存取设备，前面的物理块被存取访问之后，才能存取后续的物理块的内容。
存取速度较慢，现在主要用于后备存储。
磁盘：可编址的随机存取设备，存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。
光盘、优盘：可移动磁盘的改进、变形物。
文件的存取方式不仅与文件的结构有关，还与文件所在存储介质的性能有关，如下表所示：
5,文件结构、文件存取方式与文件存储介质的关系存储介质物理结构存取方式磁带顺序结构顺序存取磁盘顺序 链接 索引顺序 顺序 顺序随机 随机问题 1：上表内容完全正确吗？
问题 2：磁盘上的不定长记录式顺序文件适合随机存取吗？
1,分配方式当今 OS几乎都采用 离散分配方式 （似内存分页），以节省外存空间。采用 链接分配 法导致链接文件，如 MS DOS；采用 索引分配 法将形成索引文件，如 UNIX。 UNIX仅对其对换区采用 连续分配方式,以加快对换过程。
2,分配算法似首次适应法的扩充（即顺序查找分配法）
3,分配算法用的主要数据结构 （即描述外存空间使用情况的几类不同的数据结构）
6 文件存储空间的管理
(1)空闲区表 /链
将所有空闲区记录在一个表 /链中。 适合连续分配。如今少用
(2)空闲块链
把所有空闲块链成一个链。 适合离散分配，今 DOS、
Windows等用之
扩展,①不断地适度地增加块尺寸 。 从最早的
512B?1KB? 2KB? 4KB? 8KB? 16KB? 32KB?
64KB。 FAT16支持的最大簇为 32KB,FAT32支持的最大簇为 16KB,NTFS支持的最大簇为 64KB（ 请思考 FAT12、
FAT16与 FAT32之间的区别 ） ②成组链接法,链上每个节点记录 1组空闲块。适合大型文件系统，分配、释放快，链本身短，占空间少（除首组外均隐藏在空闲块中）。 UNIX
用之成组链接法分组原理图
—— 逆序分组，顺序分配成组链接法初始化链的例子：
超级块 中空闲块号栈 50号空块 150号空块 250号空块
39
50
49
…
12
100
150
149
…
51
100
250
249
…
151
100
0
349
…
251
S.free
0
1
38
← 空闲块数
← 空闲块号
251号空闲块磁盘专用块 ← → 内存专用块
(superblock)
分配算法 （ 分配 1个空块 ） 回收算法 （ 回收 1个空块 ）
IF 栈已上锁 THEN 阻塞 ELSE 对栈上锁 IF 栈已上锁 THEN 阻塞 ELSE 对栈上锁
IF 空闲块数 ＞ 1 THEN { IF 空闲块数 ＜ 100 THEN {
空闲块数减 1；开锁； 将释放块压入 S.free(空闲块数 )单元 ;
返回 S.free(空闲块数 )单元的空块； } 空闲块数加 1；开锁；返回； }
IF 空闲块数 =1 且 S.free(0)=0 THEN{ ELSE{把空闲块栈内容写到释放块中；
开锁；失败返回； } ELSE { 置空闲块数为 1；
将 S.free(空闲块数 -1)单元的空块存入 T； 将释放块号压入 S.free(0)单元；
将 T号块内容读入专用块； 开锁；返回； }
开锁；返回 T号空块； }
采用成组链接法的外存分配、回收算法：
(3) 位示图
用一串二进制位反映磁盘空间中分配使用情况,
每个物理块对应一位,分配物理块为 1，否则为
0
申请物理块时，可以在位示图中查找为 0的位，
返回对应物理块号；
归还时；将对应位转置 0
描述能力强，适合各种物理结构 （ 对连续文件稍差），本身占空间少，可常驻内存，而字位号到块号的转换也不难。今 Linux等用之 （甚至对内存分页方式也用它）
5.3 文件目录
1.基本概念
文件控制块 （ FCB）,是 OS为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（ 文件属性 ）,也叫文件目录项
文件控制块是文件存在的标志
文件控制块的内容,
基本信息,文件的名字,地址,大小、结构、类型
存取控制信息,文件属主、存取权限或属性或口令
使用信息,共享计数，文件的建立、修改日期等
文件目录,把所有的 FCB组织在一起，就构成了文件目录，即文件控制块的有序集合
目录项：构成文件目录的项目，即 FCB
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件
目录主要是为了系统快速实现“按名存取”
而引入的，查目录是文件系统最频繁的操作，
因此目录的合理组织很重要
2,目录结构
(1) 单级目录结构系统为所有文件建立一个目录文件 （线性表）
优点,简单，易实现缺点：
限制了用户对文件的命名 （存在“命名冲突”问题）
顺序检索文件时平均检索时间长
限制了对文件的共享
不适于多用户系统
(2) 二级目录结构
为克服单级目录结构存在的命名冲突问题，
并提高对目录文件的检索速度而引入
目录分为两级,一级称 为主文件目录,给出用户名，用户子目录所在的物理位置；二级称为 用户文件目录 （又称用户子目录），给出该用户所有文件的 FCB
优点,解决了文件的重名问题和文件共享问题 ;
可用于多用户系统 ;
顺序查找时间降低。
缺点,增加了系统开销二级目录结构示意图
FCB1
FCB2
FCB1
FCB2
(3) 多级目录结构（树型目录）
对二级目录简单扩充可得三级或三级以上的多级目录结构，即允许每一级目录中的 FCB要么指向文件，要么指向下一级子目录即可。这是当今主流 OS普遍采用的目录结构
优点,①解决了命名冲突问题
② 提高了文件检索速度
③ 易于实现文件的共享和保护
④ 层次结构清晰,便于对文件分类管理
缺点：查找一个 文件 按 路径名 逐层检查，由于每个文件都放在外存，多次访盘影响速度
UNIX多级树形目录结构 示意图
tty00
／
dev bin lib etc usr
tty01
sh date cc who
passwd
UNI
X
fei1
myfile.c
getty include
fei2 testfile.c
(4) 文件目录改进为加快目录检索可采用目录项分解法，把 FCB
分成两部分：
符号目录项（次部）
文件名，文件号 （即基本目录项编号，以实现主次部的链接）
基本目录项（主部）
FCB中除文件名外的所有项目
UNIX采用此法,它把符号目录项称为 目录项,而把基本目录项称为 I节点 （ Index node,索引节点 ），
这样，目录项中的文件号就是索引节点号
(FCB)
采用基本文件目录和符号文件目录的多级目录结构示意图 (1)
基本文件目录变小了的 符号文件目录根目录采用基本文件目录和符号文件目录的多级目录结构示意图 (2)
基本文件目录
(ID1)
ID 其它属性 地址
1
2
3
4
5
6
7
8
9
10
11
文件名 ID
Zhang_San 3
Li_Si 8
根 目录 (ID2) Software 4
Tools 6
Products 7
Rooms 5
Zhang_San的目录 (ID3)
文件名 ID
ZhangSan Tools子目录 (ID6)
SA2 10
Mygame 11
Li_Si的目录 (ID8)
Tools 5
Mygame 10
Classmate 9
文件名 ID
ID4
ID5
ID7
ID9
ID1
0ID11
例 5.1 设物理块大小 512字节，一个 FCB有 48个字节，符号目录项占 8字节，文件名 6字节，文件号 2字节，基本目录项占
48-6=42字节。若把含有 128个目录项的某单级目录文件改造成符号文件目录和基本文件目录的结构，试说明改造后查找一个文件的平均访盘次数，谈一下自己的认识 。
解：分解前,1块含 512/48=10个 FCB
分解后,1块含 512/8=64个符号目录项，或者，
1块含 512/42=12个基本目录项该目录文件含有 128个目录项,分解前占 13块,
分解后其符号文件占 2块,基本文件占 11块 。
故分解前查找一个文件的平均访盘次数：
(1+13)/2=7次,分解后,(1+2)/2 +1 =2.5次由此可见：改造后减少了访问硬盘的次数，提高了检索速度。
(5) 目录的其他实现方法：
Hash表算法：
目录文件按目录项键的 Hash值的顺序组织。
创建或搜索时根据文件名计算 Hash值，得到一个指向目录表中相应表目的指针
其他算法：
如 B+树,这是一种将大的单级索引目录文件组织成有序的树型多级索引目录文件的方法，
是索引顺序文件中实际采用的基本索引结构，
支持随机访问和顺序访问，多见于 DBMS中。
NTFS文件系统就采用了 B+树文件的“按名存取”是通过查目录实现的，
系统按照文件的 路径名 检索。目录查询技术主要有两种：
线性检索法
Hash方法为加快目录检索，许多系统引入当前目录 （工作目录，值班目录）,相对路径名,cd命令等。
3,目录查询技术
5.4 文件使用
为 方便 用户 使用文件，文件系统提供对文件的各种操作，形式分别为：系统调用或命令
①提供设置 和 修改用户文件 的 存取权限 的 服务
② 提供建立、修改、改变、删除目录的服务
③ 提供文件共享，设置访问路径的服务
④ 提供创建,打开、读、写、关闭,撤消 文件 等服务
⑤ 文件系统维护
⑥ 文件系统的转储和恢复
⑦ ……
其中，最基本的操作是：打开、关闭、读、写文件等
(1) 打开文件 操作 简介
任何一个文件使用前都要先打开，即 把
FCB送到内存,以建立用户和文件的联系，使今后频繁的查目录操作在内存中完成 。如 fd=open(文件路径名,打开方式 )
打开文件操作的主要执行步骤如下：
① 根据文件路径名查目录，找到 FCB主部；
② 根据打开方式、共享说明和用户身份检查访问合法性；
③ 根据文件号查 系统打开文件表,看文件是否已被打开； 若 是 → 共享计数加 1,否则 → 将外存中的 FCB主部等信息填入系统打开文件表空表项,共享计数 置为 1；
④ 在 用户打开文件表 中取一空表项，填写打开方式等，并指向系统打开文件表对应表项返回信息,fd,文件描述符，是一个非负整数，用于以后读写文 件
5.5 文件的共享与保护
1,文件共享的定义一个文件被多个用户或程序使用共享形式,
被多个用户 不同时 使用，由 存取权限 控制
被多个程序 同时 使用，但各用自己的 读 写 指针
被多个程序 同时 使用，但共享 读 写 指针
2,文件共享的目的
节省时间和存储空间，减少了用户工作量；
进程间通过文件交换信息。
3,文件共享的实现方法 （ 3种）
按“路径名”访问共享文件,即基于系统目录的共享法 。 实现简单，但路径名可能长，检索较慢。
用连接命令实现基于 i-node的共享 (硬链接方式 )
通过“连接（ Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，
新建目录项中的索引节点号即被共享文件的。
解除连接需执行 Unlink命令。 UNIX提供此法。
它是方法 1的发展 。 使用文件别名，检索较快，也叫静态共享。
问题,删除文件时应怎样考虑？
用符号链 （ Symbolic linking） 访问共享文件系统建立一个新文件，类型为 LINK，放在要连接的目录下。该文件只包含被链接文件的路径名问题,系统时空开销大优势,适于异地系统间（特别是计算机网络环境下）的文件共享，也没有直接删除文件的副作用。
符号链在 Windows中叫快捷方式
UNIX实例 —— 用户 B用连接方式共享用户 A的文件 F
Link(A/F,B/C) （ Linux命令为 ln A/F B/C）
在 B目录中建立一个新表目，并在文件 F所对应的目录表目中的“连接数”项加 1
文件名 内部标识号
C A/F的内部标识号为支持用户的 3种共享形式,UNIX在 用户打开文件表 和 内存索引节点 间还引入了 系统打开文件表,以解决 文件读写指针 的存放位置问题，如下图所示。
UNIX系统文件共享示例
4,文件的保护与保密这是实现 文件系统安全性 的两个重要方面。 安全性 应确保未经授权的用户不能存取某些文件，防止数据的丢失、被偷窃、被篡改。 这涉及到技术、管理、法律、道德、教育和政治等问题
(1) 系统安全的分级管理
系统级管理（注册、登录、口令机制）
用户级管理（分类授权）
目录、文件级管理（设权限、属性等）
(2) 文件保护 —— 防破坏 （被动做法）
人为破坏因素
有意、无意的非法操作
病毒破坏
黑客入侵
自然破坏因素
火灾、水灾、震灾,战争
存储介质等硬、软件损坏
系统对策
授权机制
防毒机制 +法制教育
防黑机制
备份,转储,恢复机制
硬、软件冗余机制
授权机制的实现方法一,文件的二级存取控制 (UNIX采用 )
第一级：对访问者的识别对用户分类：
文件主（ owner）
文件主的同组用户
（ group）
其它用户（ other）
第二级：对操作权限的识别对操作分类：
读操作（ r）
写操作（ w）
执行操作（ x）
不能执行任何操作（ -）
这样 UNIX索引节点中可用 9个二进制位 rwx rwx rwx对各类用户设访问权限。文件主人可改之，如 chmod 755 file2
方法二,存取控制矩阵 （早期 OS用）
文件用户 A B C
User1 rw r w
User2 e
具体的备份、转储与恢复机制通过转储操作，可形成文件或文件系统的多个副本
备份有 本地,异地,热,冷 备份之分
转储有全 量转储、增量转储两种
恢复有全 量 恢复,增量 恢复 两种
(3) 文件保密 —— 防窃 （主动做法）
口令机制（常结合 DES等加密法使用）
隐藏法
加密解密机制
RSA体制（ 1978,MIT,Rivest,Shamir和
Adleman创建,2002 Turing Award），已被
ISO推荐为公开密钥数据加密标准。它是建立在数论中的大整数分解质因子的基础上的
数字签名（ RSA的应用）
5.6 文件系统的一致性
事务、检查点、并发控制，见 DBMS
磁盘块号的一致性检查
UNIX一致性检查工作过程：
设 两张表，每块对应一个表中的计数器，初值为 0
表一：记录了每块在文件中出现的次数表二：记录了每块在空闲块表中出现的次数对任一块的检查结果 01,10为一致,00为块丢失,02
为空块重复,……,检查程序要给予解决
文件系统概述
文件的结构和存取方式
文件目录
文件存储空间的管理
文件的使用、共享与保护
文件系统的性能问题
5.1.1 文件的概念
1,文件外存中具有符号名的一组有逻辑意义的信息项的集合 。
2,文件系统指 OS中管理文件的那一部分软件。它负责管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并 为用户提供一整套方便有效的文件使用和操作方法 。 它在 OS接口中占比例最大，是 I/O系统的上层软件。文件系统面向用户的主要任务是实现文件的“按名存取”。
5.1.2 文件分类
分类角度多。比如，可按文件的用途、文件中数据的形式、存取控制属性、文件信息的保存期限、文件的逻辑结构、文件的物理结构等进行分类。
UNIX系统将文件分为三类,
普通文件 (包括用户的 ASCII或二进制文件 )；
目录文件 ；
特殊文件 （ 设备文件,管道，套接字，符号链等）
5.2 文件结构与存取方法文件的结构指文件中信息的配置和构造方式，有逻辑结构和物理结构之分。
1,文件的逻辑结构
用户眼中文件信息的组织形式叫文件的逻辑结构。它包括记录式文件和流式文件两种，每种文件信息的逻辑单位分别是记录和字符。
UNIX系统视所有文件的逻辑结构为无结构的流式文件
早期有结构的记录式文件又分定长和不定长两种，流式文件可看作特殊的定长记录式文件
文件的逻辑结构与文件的存储介质无关
2,文件的物理结构
系统眼中文件 信息的组织形式叫文件的物理结构。它包括顺序文件、链接文件、索引文件三种 （实为连续文件与不连续文件两大类）
文件的物理结构也叫文件的存储结构，指文件在外存上的存储组织形式，它与存储介质的性能和外存的分配方式有关
顺序文件,文件的信息存放在若干连续的物理块中。特点,实现简单，顺序存取速度快，
但分配慢，外存碎片多 （似内存的可重定位可变分区分配）
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
文件名 始址 块数
count 0 2
tr 14 3
mail 19 6
list 28 4
f 6 2
文件目录count
f
tr
list
磁盘空间连续分配产生顺序文件：
磁盘空间
链接文件：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接。
特点：提高了磁盘空间利用率,不存在外部碎片问题，有利于文件长度动态变化，
但存取速度慢（不适合随机存取，寻道时间长），可靠性差，指针占空间。
链接文件按链接指针的不同实现又分为隐式链接文件和显式链接文件,MS DOS、
Windows中采用的是后者，其 FAT和簇的概念是传统链接结构的变形文件名 始址 末址
jeep 9 25
文件目录
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
1
10
16
-1
25
磁盘空间链接式分配产生链接文件：
磁盘空间
索引文件：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个索引表，
并将这些物理块号存放在其中
一个索引表就是磁盘块地址数组,其中第 i个条目指向文件的第 i块
索引表组织,单级索引、多级索引,Hash索引。
UNIX文件系统采用多级索引结构
特点：既能顺序存取，又能随机存取，支持文件长度动态变化，外存利用率高，但索引表需占额外空间。
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
文件名 索引表地址文件目录
Jeep 19
9
17
1
10
25
-1
-1
-1
19
磁盘空间索引式分配产生索引文件：
文件 jeep的单级索引表
UNIX System V
采用多级混合索引方式索引结点中的
13个地址项十个直接地址项三次间接地址块一次间接地址块二次间接块一次间接块一次间接块二次间接块物理块物理块物理块设每个盘块 4kB，每个盘块号 4B，则采用
3次间址可表示的文件最大长度为：
4T+4G+4M+40K(B)
3,文件的存取方式当今 OS支持的文件存取方式主要有顺序存取和随机存取两种。
顺序存取对文件中的信息按逻辑顺序进行读 /写的存取方式称顺序存取
随机存取对文件中的信息按任意顺序进行读 /写的存取方式称随机存取
早期系统中记录式文件所对应的第三种存取方式 —— 按键存取 现在多见于 DBMS中
4,文件的 存储介质磁带，磁盘，光盘，优盘,……
以块为单位进行信息的存储、传输、分配
磁带：顺序存取设备，前面的物理块被存取访问之后，才能存取后续的物理块的内容。
存取速度较慢，现在主要用于后备存储。
磁盘：可编址的随机存取设备，存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。
光盘、优盘：可移动磁盘的改进、变形物。
文件的存取方式不仅与文件的结构有关，还与文件所在存储介质的性能有关，如下表所示：
5,文件结构、文件存取方式与文件存储介质的关系存储介质物理结构存取方式磁带顺序结构顺序存取磁盘顺序 链接 索引顺序 顺序 顺序随机 随机问题 1：上表内容完全正确吗？
问题 2：磁盘上的不定长记录式顺序文件适合随机存取吗？
1,分配方式当今 OS几乎都采用 离散分配方式 （似内存分页），以节省外存空间。采用 链接分配 法导致链接文件，如 MS DOS；采用 索引分配 法将形成索引文件，如 UNIX。 UNIX仅对其对换区采用 连续分配方式,以加快对换过程。
2,分配算法似首次适应法的扩充（即顺序查找分配法）
3,分配算法用的主要数据结构 （即描述外存空间使用情况的几类不同的数据结构）
6 文件存储空间的管理
(1)空闲区表 /链
将所有空闲区记录在一个表 /链中。 适合连续分配。如今少用
(2)空闲块链
把所有空闲块链成一个链。 适合离散分配，今 DOS、
Windows等用之
扩展,①不断地适度地增加块尺寸 。 从最早的
512B?1KB? 2KB? 4KB? 8KB? 16KB? 32KB?
64KB。 FAT16支持的最大簇为 32KB,FAT32支持的最大簇为 16KB,NTFS支持的最大簇为 64KB（ 请思考 FAT12、
FAT16与 FAT32之间的区别 ） ②成组链接法,链上每个节点记录 1组空闲块。适合大型文件系统，分配、释放快，链本身短，占空间少（除首组外均隐藏在空闲块中）。 UNIX
用之成组链接法分组原理图
—— 逆序分组，顺序分配成组链接法初始化链的例子：
超级块 中空闲块号栈 50号空块 150号空块 250号空块
39
50
49
…
12
100
150
149
…
51
100
250
249
…
151
100
0
349
…
251
S.free
0
1
38
← 空闲块数
← 空闲块号
251号空闲块磁盘专用块 ← → 内存专用块
(superblock)
分配算法 （ 分配 1个空块 ） 回收算法 （ 回收 1个空块 ）
IF 栈已上锁 THEN 阻塞 ELSE 对栈上锁 IF 栈已上锁 THEN 阻塞 ELSE 对栈上锁
IF 空闲块数 ＞ 1 THEN { IF 空闲块数 ＜ 100 THEN {
空闲块数减 1；开锁； 将释放块压入 S.free(空闲块数 )单元 ;
返回 S.free(空闲块数 )单元的空块； } 空闲块数加 1；开锁；返回； }
IF 空闲块数 =1 且 S.free(0)=0 THEN{ ELSE{把空闲块栈内容写到释放块中；
开锁；失败返回； } ELSE { 置空闲块数为 1；
将 S.free(空闲块数 -1)单元的空块存入 T； 将释放块号压入 S.free(0)单元；
将 T号块内容读入专用块； 开锁；返回； }
开锁；返回 T号空块； }
采用成组链接法的外存分配、回收算法：
(3) 位示图
用一串二进制位反映磁盘空间中分配使用情况,
每个物理块对应一位,分配物理块为 1，否则为
0
申请物理块时，可以在位示图中查找为 0的位，
返回对应物理块号；
归还时；将对应位转置 0
描述能力强，适合各种物理结构 （ 对连续文件稍差），本身占空间少，可常驻内存，而字位号到块号的转换也不难。今 Linux等用之 （甚至对内存分页方式也用它）
5.3 文件目录
1.基本概念
文件控制块 （ FCB）,是 OS为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（ 文件属性 ）,也叫文件目录项
文件控制块是文件存在的标志
文件控制块的内容,
基本信息,文件的名字,地址,大小、结构、类型
存取控制信息,文件属主、存取权限或属性或口令
使用信息,共享计数，文件的建立、修改日期等
文件目录,把所有的 FCB组织在一起，就构成了文件目录，即文件控制块的有序集合
目录项：构成文件目录的项目，即 FCB
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件
目录主要是为了系统快速实现“按名存取”
而引入的，查目录是文件系统最频繁的操作，
因此目录的合理组织很重要
2,目录结构
(1) 单级目录结构系统为所有文件建立一个目录文件 （线性表）
优点,简单，易实现缺点：
限制了用户对文件的命名 （存在“命名冲突”问题）
顺序检索文件时平均检索时间长
限制了对文件的共享
不适于多用户系统
(2) 二级目录结构
为克服单级目录结构存在的命名冲突问题，
并提高对目录文件的检索速度而引入
目录分为两级,一级称 为主文件目录,给出用户名，用户子目录所在的物理位置；二级称为 用户文件目录 （又称用户子目录），给出该用户所有文件的 FCB
优点,解决了文件的重名问题和文件共享问题 ;
可用于多用户系统 ;
顺序查找时间降低。
缺点,增加了系统开销二级目录结构示意图
FCB1
FCB2
FCB1
FCB2
(3) 多级目录结构（树型目录）
对二级目录简单扩充可得三级或三级以上的多级目录结构，即允许每一级目录中的 FCB要么指向文件，要么指向下一级子目录即可。这是当今主流 OS普遍采用的目录结构
优点,①解决了命名冲突问题
② 提高了文件检索速度
③ 易于实现文件的共享和保护
④ 层次结构清晰,便于对文件分类管理
缺点：查找一个 文件 按 路径名 逐层检查，由于每个文件都放在外存，多次访盘影响速度
UNIX多级树形目录结构 示意图
tty00
／
dev bin lib etc usr
tty01
sh date cc who
passwd
UNI
X
fei1
myfile.c
getty include
fei2 testfile.c
(4) 文件目录改进为加快目录检索可采用目录项分解法，把 FCB
分成两部分：
符号目录项（次部）
文件名，文件号 （即基本目录项编号，以实现主次部的链接）
基本目录项（主部）
FCB中除文件名外的所有项目
UNIX采用此法,它把符号目录项称为 目录项,而把基本目录项称为 I节点 （ Index node,索引节点 ），
这样，目录项中的文件号就是索引节点号
(FCB)
采用基本文件目录和符号文件目录的多级目录结构示意图 (1)
基本文件目录变小了的 符号文件目录根目录采用基本文件目录和符号文件目录的多级目录结构示意图 (2)
基本文件目录
(ID1)
ID 其它属性 地址
1
2
3
4
5
6
7
8
9
10
11
文件名 ID
Zhang_San 3
Li_Si 8
根 目录 (ID2) Software 4
Tools 6
Products 7
Rooms 5
Zhang_San的目录 (ID3)
文件名 ID
ZhangSan Tools子目录 (ID6)
SA2 10
Mygame 11
Li_Si的目录 (ID8)
Tools 5
Mygame 10
Classmate 9
文件名 ID
ID4
ID5
ID7
ID9
ID1
0ID11
例 5.1 设物理块大小 512字节，一个 FCB有 48个字节，符号目录项占 8字节，文件名 6字节，文件号 2字节，基本目录项占
48-6=42字节。若把含有 128个目录项的某单级目录文件改造成符号文件目录和基本文件目录的结构，试说明改造后查找一个文件的平均访盘次数，谈一下自己的认识 。
解：分解前,1块含 512/48=10个 FCB
分解后,1块含 512/8=64个符号目录项，或者，
1块含 512/42=12个基本目录项该目录文件含有 128个目录项,分解前占 13块,
分解后其符号文件占 2块,基本文件占 11块 。
故分解前查找一个文件的平均访盘次数：
(1+13)/2=7次,分解后,(1+2)/2 +1 =2.5次由此可见：改造后减少了访问硬盘的次数，提高了检索速度。
(5) 目录的其他实现方法：
Hash表算法：
目录文件按目录项键的 Hash值的顺序组织。
创建或搜索时根据文件名计算 Hash值，得到一个指向目录表中相应表目的指针
其他算法：
如 B+树,这是一种将大的单级索引目录文件组织成有序的树型多级索引目录文件的方法，
是索引顺序文件中实际采用的基本索引结构，
支持随机访问和顺序访问，多见于 DBMS中。
NTFS文件系统就采用了 B+树文件的“按名存取”是通过查目录实现的，
系统按照文件的 路径名 检索。目录查询技术主要有两种：
线性检索法
Hash方法为加快目录检索，许多系统引入当前目录 （工作目录，值班目录）,相对路径名,cd命令等。
3,目录查询技术
5.4 文件使用
为 方便 用户 使用文件，文件系统提供对文件的各种操作，形式分别为：系统调用或命令
①提供设置 和 修改用户文件 的 存取权限 的 服务
② 提供建立、修改、改变、删除目录的服务
③ 提供文件共享，设置访问路径的服务
④ 提供创建,打开、读、写、关闭,撤消 文件 等服务
⑤ 文件系统维护
⑥ 文件系统的转储和恢复
⑦ ……
其中，最基本的操作是：打开、关闭、读、写文件等
(1) 打开文件 操作 简介
任何一个文件使用前都要先打开，即 把
FCB送到内存,以建立用户和文件的联系，使今后频繁的查目录操作在内存中完成 。如 fd=open(文件路径名,打开方式 )
打开文件操作的主要执行步骤如下：
① 根据文件路径名查目录，找到 FCB主部；
② 根据打开方式、共享说明和用户身份检查访问合法性；
③ 根据文件号查 系统打开文件表,看文件是否已被打开； 若 是 → 共享计数加 1,否则 → 将外存中的 FCB主部等信息填入系统打开文件表空表项,共享计数 置为 1；
④ 在 用户打开文件表 中取一空表项，填写打开方式等，并指向系统打开文件表对应表项返回信息,fd,文件描述符，是一个非负整数，用于以后读写文 件
5.5 文件的共享与保护
1,文件共享的定义一个文件被多个用户或程序使用共享形式,
被多个用户 不同时 使用，由 存取权限 控制
被多个程序 同时 使用，但各用自己的 读 写 指针
被多个程序 同时 使用，但共享 读 写 指针
2,文件共享的目的
节省时间和存储空间，减少了用户工作量；
进程间通过文件交换信息。
3,文件共享的实现方法 （ 3种）
按“路径名”访问共享文件,即基于系统目录的共享法 。 实现简单，但路径名可能长，检索较慢。
用连接命令实现基于 i-node的共享 (硬链接方式 )
通过“连接（ Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，
新建目录项中的索引节点号即被共享文件的。
解除连接需执行 Unlink命令。 UNIX提供此法。
它是方法 1的发展 。 使用文件别名，检索较快，也叫静态共享。
问题,删除文件时应怎样考虑？
用符号链 （ Symbolic linking） 访问共享文件系统建立一个新文件，类型为 LINK，放在要连接的目录下。该文件只包含被链接文件的路径名问题,系统时空开销大优势,适于异地系统间（特别是计算机网络环境下）的文件共享，也没有直接删除文件的副作用。
符号链在 Windows中叫快捷方式
UNIX实例 —— 用户 B用连接方式共享用户 A的文件 F
Link(A/F,B/C) （ Linux命令为 ln A/F B/C）
在 B目录中建立一个新表目，并在文件 F所对应的目录表目中的“连接数”项加 1
文件名 内部标识号
C A/F的内部标识号为支持用户的 3种共享形式,UNIX在 用户打开文件表 和 内存索引节点 间还引入了 系统打开文件表,以解决 文件读写指针 的存放位置问题，如下图所示。
UNIX系统文件共享示例
4,文件的保护与保密这是实现 文件系统安全性 的两个重要方面。 安全性 应确保未经授权的用户不能存取某些文件，防止数据的丢失、被偷窃、被篡改。 这涉及到技术、管理、法律、道德、教育和政治等问题
(1) 系统安全的分级管理
系统级管理（注册、登录、口令机制）
用户级管理（分类授权）
目录、文件级管理（设权限、属性等）
(2) 文件保护 —— 防破坏 （被动做法）
人为破坏因素
有意、无意的非法操作
病毒破坏
黑客入侵
自然破坏因素
火灾、水灾、震灾,战争
存储介质等硬、软件损坏
系统对策
授权机制
防毒机制 +法制教育
防黑机制
备份,转储,恢复机制
硬、软件冗余机制
授权机制的实现方法一,文件的二级存取控制 (UNIX采用 )
第一级：对访问者的识别对用户分类：
文件主（ owner）
文件主的同组用户
（ group）
其它用户（ other）
第二级：对操作权限的识别对操作分类：
读操作（ r）
写操作（ w）
执行操作（ x）
不能执行任何操作（ -）
这样 UNIX索引节点中可用 9个二进制位 rwx rwx rwx对各类用户设访问权限。文件主人可改之，如 chmod 755 file2
方法二,存取控制矩阵 （早期 OS用）
文件用户 A B C
User1 rw r w
User2 e
具体的备份、转储与恢复机制通过转储操作，可形成文件或文件系统的多个副本
备份有 本地,异地,热,冷 备份之分
转储有全 量转储、增量转储两种
恢复有全 量 恢复,增量 恢复 两种
(3) 文件保密 —— 防窃 （主动做法）
口令机制（常结合 DES等加密法使用）
隐藏法
加密解密机制
RSA体制（ 1978,MIT,Rivest,Shamir和
Adleman创建,2002 Turing Award），已被
ISO推荐为公开密钥数据加密标准。它是建立在数论中的大整数分解质因子的基础上的
数字签名（ RSA的应用）
5.6 文件系统的一致性
事务、检查点、并发控制，见 DBMS
磁盘块号的一致性检查
UNIX一致性检查工作过程：
设 两张表，每块对应一个表中的计数器，初值为 0
表一：记录了每块在文件中出现的次数表二：记录了每块在空闲块表中出现的次数对任一块的检查结果 01,10为一致,00为块丢失,02
为空块重复,……,检查程序要给予解决
