Operating-System/Homework/08第八章 文件系统1.md

第八章 文件系统

一、知识讲解

8.1 文件与文件系统

文件（File）：具有符号名而且在逻辑上具有完整意义的信息项的序列。

• 文件是操作系统对外部存储设备上数据的抽象，用户通过文件名（符号名）来访问数据，而不需要关心数据存放的具体物理位置。
• 文件是逻辑上的概念，强调"完整意义"——例如一个源程序、一张照片、一段视频都可以是一个文件。
• 文件存在的两个必要条件：①有名字；②是信息项的序列（不是单个数据，而是有序集合）。

文件系统（File System）：文件与管理文件的程序集合。

• 文件系统 = 文件 + 管理程序
• 管理程序负责：文件的创建、删除、打开、关闭、读写、保护、共享、组织、存储空间管理
• 文件系统的目标：实现对文件的按名存取；提供统一的用户界面；保证文件的安全性和一致性

UNIX文件分类

文件类型	含义	内容/特点
普通文件	保存用户数据	内容可以是程序、数据、图像等，保存在磁盘块中
目录文件	用来组织其他文件	内容是（文件名，文件号）序列，保存在磁盘块中
特殊文件	设备以文件形式呈现	包括块设备文件和字符设备文件

将设备作为文件管理的好处（必考简答）：

1. 界面统一：使用文件与使用设备的命令相同——open（打开/申请设备）、close（关闭/释放设备）、read（读取）、write（写入）。
2. 利用文件保护功能保护设备：设备的访问权限和普通文件一样通过权限位管理，可防止越权访问。
3. 编程方便：应用程序对设备和文件使用同一套系统调用接口。

8.2 文件的访问方式

1. 顺序访问（Sequential Access）

• 从文件起始位置开始，依次访问每个记录。
• 也可从文件中间某处开始顺序访问（如"倒带"或"快进"）。
• 类似于磁带访问方式。
• 适合：文本文件顺序处理、流水作业。

2. 随机访问（Random Access / Direct Access）

• 按记录编号直接访问（直接给出第n个记录）。
• 按关键字（key）访问（通过散列或索引查找）。
• 适合：数据库系统、需要频繁跳跃访问的应用。

易考点：顺序访问依赖文件的逻辑组织（流式或记录式），随机访问要求文件有定位机制（指针或索引）。

8.3 文件的组织

8.3.1 逻辑组织

逻辑组织是指用户所看到的文件组织形式，由用户决定，与物理存储无关。

1. 记录式文件：记录的序列

类型	优点	缺点
等长记录	处理方便，速度快	空间浪费（长记录被截短，短记录被填充）
不等长记录	节省空间	处理不便，速度慢（要先读长度信息）

2. 流式文件：字节的序列（如 UNIX、Windows 系统中的文件）

• 文件被看作无结构的字节流。
• 由应用程序解释字节含义（文本、二进制、对象文件等）。
• 优点：操作系统实现简单，使用灵活。
• 缺点：应用程序需要自行组织。

8.3.2 文件的物理组织

物理组织是指逻辑组织到磁盘块的映射。

• 文件：记录（字节）序列
• 磁盘：块（block）序列
• 映射关系：文件系统负责将逻辑位置转换为物理块号

考虑因素：

• 记录格式：等长/不等长/流式
• 空间开销：除文件内容外的存储开销（FCB、指针、索引）
• 访问速度：随机访问速度
• 长度变化：是否支持动态增长

三种基本物理结构（必考对比表）

结构	磁盘块分配方式	优点	缺点	适用场景
顺序结构	文件占有若干连续的磁盘块	速度快（顺序读写接近磁盘极限）、节省空间（无指针开销）	长度变化困难（动态增长需要搬迁）、外部碎片	一次写完后不再修改的文件；磁带
链接结构	文件可存于不连续块，块间以指针相连	节省空间（充分利用碎片）、长度变化容易	随机访问速度慢（必须沿着指针链查找）、指针占空间、可靠性差（指针损坏全链断）	早期FAT系统；顺序读写为主
索引结构	文件可存于不连续块，块号记在索引块中	速度快（可随机访问）、长度变化容易	索引块占空间、小文件也需一个索引块浪费空间	UNIX、NTFS等现代文件系统

Hash结构（散列文件）

计算地址：hash(key) = addr（在磁盘或文件中的存放位置）

问题：冲突（collision）—— key1 ≠ key2 但 hash(key1) = hash(key2)

冲突解决方法：顺序探查法

• 如发生冲突，则在冲突位置开始顺序探查第一个空闲的存储位置。

保存记录的流程：

1. 计算 addr = hash(key)
2. 检查 addr 对应位置是否空闲
3. 若空闲则填入记录内容并标记为占用
4. 若被占用则顺序探查下一个空闲位置

查找记录的流程：

1. 计算 addr = hash(key)
2. 取 addr 对应记录的冲突计数 count
3. 若 count = 0，则无此记录
4. 否则比较 hash(key) 和 key，相等则找到
5. 若不相等则 count := count - 1，若 count = 0 则无此记录，否则顺取下一记录

删除记录：

1. 调用查找过程
2. 找到则置空闲标志
3. 对应 hash(key) 的冲突计数减1

特点：

• 按关键字检索速度非常快（理论 O(1)）。
• 常用于目录检索。
• 文件可循环使用，满时保存失败。

UNIX文件物理结构（索引+链接的混合结构）

UNIX的inode采用多级索引结构：

• i_addr[0] ~ i_addr[9]：10个直接地址（指向10个数据块）
• i_addr[10]：一级间接地址（指向一个索引块，该索引块有256个数据块指针）
• i_addr[11]：二级间接地址（指向一个二级索引块，每项指向一个一级索引块）
• i_addr[12]：三级间接地址

最大文件大小 = 10 + 256 + 256² + 256³ 个块（按每块 512B 算，最大约 16GB；按每块 1KB 算，最大约 32GB）。

这种结构对小文件很友好（直接寻址快速），对大文件也能支持（多级间接寻址），是顺序、链接、索引三种结构的折中。

8.4 文件目录

文件控制块与目录项

文件控制块（FCB, File Control Block）：

• 文件存在的标志，其中保存系统管理文件需要的全部信息。
• 每一个文件都有一个FCB，文件被删除时FCB被撤销。

目录项：

• 目录文件中的一项，内容为FCB（或者说目录项就是FCB在目录中的条目）。

文件目录 vs 目录文件：

• 文件目录：用于检索文件的目录（一种逻辑结构）。
• 目录文件：内容为目录项的文件（一种物理存储形式）。

FCB的内容（必考）

FCB通常包含以下信息（部分）：

• 文件名
• 文件号
• 文件主（owner）
• 文件类型
• 文件属性
• 共享说明
• 文件长度
• 文件地址
• 建立日期
• 最后修改日期
• 最后访问日期
• 口令
• 其它（如权限位、链接计数等）

FCB创建：建立文件时 FCB撤销：删除文件时

目录结构（必考对比）

目录结构	描述	优点	缺点
单级目录	整个系统只有一个目录	简单	① 重名问题（不同用户不能有同名文件）；② 无分组能力；③ 无保护
两级目录	每个用户一个目录（主文件目录 + 用户文件目录）	① 支持路径名；② 不同用户可重名；③ 查找效率高	无分组能力
多级目录（树形）	目录可嵌套（UNIX风格）	① 支持层次结构；② 良好组织；③ 支持分组	路径名较长，访问需逐级查找
无环图目录	允许共享，目录图无环	支持文件共享	需管理引用计数避免悬挂指针

多级目录示例（UNIX）：

root
├── bin
├── usr
│   ├── lib
│   └── users
│       ├── Li
│       │   ├── d1
│       │   │   ├── f1
│       │   │   └── f2
│       │   └── d2
│       └── Wang
│           └── d1
├── dev
└── etc

文件目录的查找

查找路径：

1. 绝对路径：由根目录开始查找（如 /usr/users/li/d1/f1）
2. 相对路径：由当前目录开始查找（如 d1/f1）

查找算法：

• 顺序查找（UNIX）：逐个比较文件名
• hash查找：通过散列函数定位，速度快
• 对分查找：要求文件名排序，时间复杂度 O(log n)

FCB的改进（UNIX）

将FCB分成主部和次部：

部分	内容	大小（UNIX）	保存位置
次部	文件名、文件号	16字节	目录文件中（便于查找）
主部	其他信息（权限、大小、地址等）	32字节	外存inode区域，打开时读入内存

改进的好处：

1. 提高查找速度：目录文件中只含文件名+文件号（16字节），比较次数减少，目录占用磁盘块减少，可一次读入更多目录项。
2. 实现文件链接（link）：多个目录项可以指向同一个inode（链接计数）。

8.5 文件的共享

共享目的：

1. 节省存储空间（如多个用户共享编译器 cc、编辑器 vi、编译工具 yacc）。
2. 进程相互通讯（UNIX的 pipe()）。

文件共享模式：

• 不同时使用：根据共享说明（如只读）
• 同时使用：根据共享说明和（relaxed）R/W规则

文件共享的实现方式：

1. 公共目录：在公共目录下创建文件，所有用户通过该目录访问。
2. 共享说明：在FCB中记录共享属性。
3. 连接（link）：
   • 硬链接（hard link）：link("/usr/users/wang/d1/f1", "/usr/users/li/f2")，多个目录项指向同一个inode，inode的i_nlink计数加1。
   • 撤销：unlink("/usr/users/wang/d1/f1")，引用计数减1，减到0才真正删除。
4. 符号链接（symbolic link）：一个文件包含另一个文件的路径名（PPT未深入，扩展知识）。

8.6 文件的保护、保密与安全

概念	含义	举例
保护（Protection）	防止用户对文件进行非授权的访问	控制谁能读/写/执行某个文件
保密（Privacy/Confidentiality）	防止文件内容泄露	加密文件内容
安全（Security）	防止文件被破坏	备份、防病毒、防自然灾害

8.6.1 文件的保护

文件主/创建者应该能控制：

• What can be done：可以做什么操作
• By whom：允许谁做

允许的访问类型（必记）：

1. Read（读）
2. Write（写）
3. Execute（执行）
4. Append（追加）
5. Delete（删除）
6. List（列目录）

1. 存取控制矩阵（Access Control Matrix）

• 二维矩阵 A[i][j]：用户 i 对文件 j 的访问权限。
• 特点：权限规定细，过于繁琐，占较多存储空间（用户和文件都多时矩阵爆炸）。

2. 访问权限说明（UNIX i_mode）

UNIX的权限位采用9位模式（三组×三种权限）：

• 文件主（owner）：i_uid
• 同组用户（group）：i_gid
• 其他用户（others）

每种身份可拥有：r（读）、w（写）、x（执行）

身份	r	w	x
文件主	1/0	1/0	1/0
同组用户	1/0	1/0	1/0
其他用户	1/0	1/0	1/0

判别过程：

• 文件主判别：访问进程 u_uid == i_uid
• 同组用户判别：访问进程 u_gid == i_gid
• 其余为其他用户

i_mode的设置：

• 在创建文件时给出：creat(filename, mode)
• 文件主可修改：chmod(filename, new_mode)

8.6.2 文件保密

1. 口令（Password）

• 使用：创建文件时用户规定一个口令，系统将其记在FCB中；访问文件要求给出口令，并与FCB中口令比较。
• 特点：
  • 简单（实现容易）
  • 保密性不强（对系统操作员不保密——系统管理员能看到口令）

2. 密码（Encryption）

• 使用：保存时用key加密；读取时用key解密。
• 特点：
  • 对文件内容加密
  • 速度慢
  • 效果好（即使文件被偷取也无法解读）

加密/解密原理（线性同余伪随机数）：

保存时：用一个key启动一个随机数发生器，产生一个随机数序列，
        将其依次加到文件的各个字中。
读取时：用同一个key启动同一个随机数发生器，产生相同随机数序列，
        将其依次由文件的各个字中减去。
线性同余法产生伪随机数：
Procedure random(Var key:integer);
Begin
    key := (key * C1 + C2) MOD C3
End;

由于加法和减法使用相同的伪随机数序列（key相同则序列相同），所以可以还原。

8.6.3 文件系统的安全

1. 备份（Backup）

• 定期将磁盘上文件复制到磁带上
• 发生故障时由磁带恢复（有限度的恢复）

实现方法：

• 海量转储（Full Backup）：定期将磁盘上文件全部复制到磁带上
• 增量转储（Incremental Backup）：每次只复制修改部分
• 优点：恢复时只需最近一次全量 + 之后的增量

2. 磁盘整理

• 利用转储和恢复可以对磁盘进行整理
• 使文件物理块连续，空闲盘块连续（消除碎片）
• 注意：整理时先做转储（备份），恢复时文件按连续块写入

8.7 文件系统的实现

8.7.1 内存所需表目

文件操作需要在内存中维护若干表：

1. 系统打开文件表（整个系统一个）

• 也叫文件表或全局文件表
• 每条记录包含：
  • FCB主部（内存中的inode）
  • 文件号
  • 共享计数（多少个进程打开）
  • 修改标志

2. 用户打开文件表（每个进程一个）

• 也叫文件描述符表或进程文件表
• 每条记录包含：
  • 打开方式（读/写/读写）
  • 读写指针（文件内的当前读写位置）
  • 系统打开文件表入口（指针）

典型关系（UNIX）：

u_ofile[i] → file[j] → inode[k]
   (n)        (1)       (1)

• 多个用户打开文件表项可指向同一个系统打开文件表项（实现共享）
• 系统打开文件表项指向内存inode
• 内存inode指向外存inode

文件描述符（fd）：

• 用户打开文件表中的入口
• 是一非负整数
• 进程通过fd访问文件，而非直接使用文件名

8.8 文件系统的界面（系统调用）

PPT列出了文件系统提供给用户/程序员的系统调用（操作系统界面）：

系统调用	命令形式	功能
创建文件	creat(path_name, fcb_args)	创建新文件并初始化
打开文件	fd = open(path_name, mode)	打开已存在文件，返回fd
关闭文件	close(fd)	关闭文件
指针定位	seek(fd, offset)	调整读写指针位置
读文件	read(fd, nrd, buf)	读取nrd个记录到buf
写文件	write(fd, nwt, buf)	将buf的nwt个记录写入
建立连接	link(old_name, new_name)	创建硬链接
断开连接	unlink(path_name)	删除链接/文件
创建管道	pipe(fd[2])	创建无名管道
创建节点	mknode(pathname, type, dev)	创建特殊文件
安装卷	smount(special, directory, roflag)	挂载文件系统
卸下卷	sumount(special_file_name)	卸载文件系统
改变权限	chmod(pathname, newmode)	修改权限
改变所有者	chown(pathname, owner, group)	修改所有者
读文件状态	state(pathname, statbuffer)	通过路径获取状态
读打开文件状态	fstate(fd, statbuffer)	通过fd获取状态
改变当前目录	chdir(pathname)	切换当前工作目录

重要系统调用的执行步骤（必考）

1. 创建文件 creat(path_name, fcb_args)

• (1) 为此文件分配一个FCB主部，初始化
• (2) 将文件名和文件号作为FCB次部填到末级目录中
• (3) 以写方式打开

2. 打开文件 fd = open(path_name, mode)

• (1) 根据文件路径名查目录找到FCB主部
• (2) 合法性检查（根据打开方式、共享说明、用户身份）
• (3) 根据文件号查系统打开文件表看该文件是否已被打开：
  • 如是：共享计数加1
  • 否则：取一个空闲的系统打开文件表项并将外存中FCB主部等信息填入此表项，共享计数置为1
• (4) 在用户打开文件表中取一空表项，填写打开方式和读写指针，并指向系统打开文件表的对应表项
• 返回：fd（文件描述符，用户打开文件表中的入口），非负整数

3. 关闭文件 close(fd)

• (1) 由fd查用户打开文件表，找到系统打开文件表入口
• (2) 系统打开文件表中共享计数减1：
  • 如减1后值为0且修改标志为1，则将此FCB由内存写回外存FCB主部
• (3) 将fd所对应的用户打开文件表项置为空闲

4. 读文件 read(fd, nrd, buf)

• (1) 由fd查用户打开文件表，找到对应入口
• (2) 合法性检查（打开方式、存取方式）
• (3) 查系统打开文件表，找到文件的地址
• (4) 计算欲访问起始记录的位置（offset + 物理结构）
• (5) 将文件中由当前读指针所确定的nrd个记录读入内存中由buf起始的区域

5. 写文件 write(fd, nwt, buf)

• (1) 由fd查用户打开文件表，找到对应入口
• (2) 合法性检查
• (3) 查系统打开文件表，找到文件的地址
• (4) 计算欲访问起始记录的位置
• (5) 如果需要，申请存储块
• (6) 将内存中由buf起始的nwt个记录写到文件中由当前写指针所确定的区域（可能切换进程）

6. 建立连接 link(old_name, new_name)

• (1) 查目录找到文件old_name的FCB主部，得到文件号
• (2) 查目录找到new_name的末级目录
• (3) 将文件号与new_name中末级名字合起来构成一个新的目录项，填入new_name的末级目录文件中
• (4) 将FCB主部中的连接计数加1

7. 断开连接 unlink(path_name)

• (1) 查目录找到文件path_name的FCB主部
• (2) 将连接计数i_nlink减1
• (3) 如减1后值为0，则归还该文件所占用的全部存储块，该文件被撤销
• (4) 将FCB次部由上级目录中清除

UNIX文件系统的实现细节

内存表目（UNIX）：

1. u_ofile（每进程一个）

   • struct user { int u_ofile[NOFILE]; }，NOFILE = 15
   • 是用户打开文件表，每项指向file表的入口

2. file（整个系统一个）

   • struct file { char f_flag; char f_count; int f_inode; char *f_offset[2]; } file[NFILE]，NFILE = 100
   • f_flag：R/W/PIPE标志
   • f_count：共享计数
   • f_inode：指向内存inode
   • f_offset[2]：读/写指针

3. inode（整个系统一个内存inode表）

   • 包含文件主部信息
   • i_count：内存引用计数
   • i_flag：ILOCK/IUPD/IACC/IMOUNT/IWANT/ITEXT

UNIX外存空间管理：

超级块（super block）struct filesys：

• 记载文件卷上空闲块信息
• s_isize：inode区大小（块数）
• s_fsize：整个文件卷大小（块数）
• s_nfree：内存中空闲块数
• s_free[100]：内存中空闲块号数组
• s_ninode：内存中空闲inode数
• s_inode[100]：空闲inode编号数组
• s_flock、s_ilock：锁
• s_fmod、s_ronly：修改/只读标志
• 文件卷安装（mount）后超级块读入内存。

空闲inode管理：

• s_inode最多可记载100个空闲inode（编号）
• 申请：
  • (1) s_ninode > 0，取 s_inode[--s_ninode]
  • (2) s_ninode = 0，由磁盘inode区顺取100个空闲i节点（i_nlink = 0），将其编号填入s_inode表，修改s_ninode，然后分配
• 释放：
  • (1) s_ninode < 100，s_inode[s_ninode++] = i_number（释放的）
  • (2) s_ninode = 100，丢弃

管道（pipe）

pipe(fd) 创建无名管道：

1. 分配一个inode（i_count = 2）
2. 分配2个file表目（f_flag分别为PipeR和PipeW，读/写指针offset为0）
3. 分配2个u_ofile表目，分别指向2个file表目
4. 返回2个文件描述符 fd[0]、fd[1]，分别为u_ofile中的2个入口

pipe文件的使用：

• 读（read）：读指针追上写指针，读者等待
• 写（write）：写指针追上读指针，写者等待
• 关闭：无读者，信号通知写者；无写者，唤醒等待读者

安装（mount）与卸下（umount）

smount(special_pathname, directory_pathname, roflag)：

1. 检查是否超级用户
2. 找到special_pathname文件的inode（用mknode建立）
3. 合法性检查（特殊块型文件）
4. 找到directory_pathname节点的inode
5. 如非目录或引用数大于1，错返
6. 读入super block到buf，按filesys格式解释
7. 安装节点inode的i_addr[0] = 设备文件i_addr[0]（dev）
8. 分配一个mount表项，填写（m_dev, m_bufp, m_inodep）
9. 安装节点inode的i_flag |= IMOUNT

sumount(special_file_name)：反向过程，将卷写回并释放资源。

i_mode的详细格式

i_mode（16位）：
位 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
   |  |  |  |  |  |  | | | | | | | | | |
   |  |  |  |  |  |  | └──┴──┴──┴──┴──┴──┴── 其他用户权限(rwx)
   |  |  |  |  |  |  └────────────────────── 同组用户权限(rwx)
   |  |  |  |  |  └────────────────────────── 文件主权限(rwx)
   |  |  |  |  └──────────────────────────── 文件类型(2位) 00普通 01字符 10目录 11块型
   |  |  |  └─────────────────────────────── 大文件
   |  |  └────────────────────────────────── Set gid (执行时获得组权限)
   |  └───────────────────────────────────── Set uid (执行该文件进程的身份暂时改为文件主身份)
   └──────────────────────────────────────── 黏着位

i_flag（标志位）：ILOCK、IUPD、IACC、IMOUNT、IWANT、ITEXT

Set uid 的作用：执行该文件时，进程的身份暂时改为文件主的身份（即 u_uid = i_uid），这用于让普通用户能执行需要特权的程序（如passwd修改口令）。

8.9 日志结构文件系统（LFS, Log-Structured File System）

背景：

• CPU速度越来越快
• 内存容量以接近指数级速度增长
• 磁盘容量更大更便宜
• 磁盘速度的提高却相对较慢 → 成为系统效率的瓶颈

UNIX中创建文件的步骤（4次磁盘写）：

1. 文件名写入目录中
2. 新文件inode更新
3. 目录文件inode更新
4. 写入文件内容

小量写（small write）问题：

• 一次写修改磁盘块上的一小部分数据
• 假定一次写需要10ms寻道时间、4ms旋转延迟、50µs读写
• 磁盘访问效率仅 1%（54µs / 10.054ms ≈ 0.5%）

延迟写（delayed write）：

• 写操作先放缓冲区，延迟写回
• 问题：发生故障时给一致性带来威胁

LFS思想（UC Berkeley提出）：

• LSFS将整个磁盘看做一个日志（log），周期性地追加新日志
• 写操作并非直接反映到磁盘上，而是被暂时存到内存缓冲区中
• 缓冲区内容包括：新写的数据 + 更新数据
• 当积累到一定规模时，作为一个segment追加到日志的末尾

Segment结构：

• segment = summary + (Inodes, directories, data blocks)
• 大块顺序写，利用磁盘的全部带宽

Inode map：

• inode存储位置不能由其编号确定
• 系统维持一个Inode map，实现 i-number 到磁盘 inode 的映射
• Inode map也保存在segment中

清洁线程（cleaner）：

• 循环扫描磁盘并对segment进行压缩
• 步骤：
  1. 读入第一个segment
  2. 舍弃过时内容
  3. 仍有用的inode和数据块与内存当前segment合并
  4. 作为新segment写回磁盘
  5. 旧segment被标记为空闲
  6. 顺序处理下个segment

8.10 内存映射文件（Memory Mapped File）

背景：

• 文件保存于外存，存取速度慢
• 访问之前需要打开
• 每次访问需要经过"打开文件表"
• 读写需要经过I/O传输
• 缓冲可以提高速度，但首次访问需要I/O
• 内存容量增加，利用率不充分（进程虚拟空间大，只使用较小部分）

提示：将文件映射到内存

• 以访问内存的方式访问文件
• 操作序列：open → map → 使用 → unmap → close

工作原理：

• 进程通过map(fd, offset)将文件的某段映射到进程的虚拟地址空间
• 进程对该地址范围的访问通过页表转换为对磁盘文件的访问
• 操作系统以页为单位管理，按需调页（demand paging）
• 修改内存中的页，操作系统在合适时机写回磁盘

优点：

1. 访问速度接近内存
2. 避免多次read/write系统调用的开销
3. 多个进程可映射同一文件，实现共享内存
4. 利用虚拟存储管理，无需显式I/O

典型用法：

fd = open("f1", 'rw');
map(fd, 1K);      // 将文件f1的1K处开始映射到进程虚拟空间
// 像访问内存一样使用指针
unmap(fd);
close(fd);

8.11 系统举例

8.11.1 Linux文件系统

VFS（Virtual File System，虚拟文件系统）：

• 并不是一个实际文件系统，而是多种实际文件系统的一个统一界面
• 为多种文件系统（Ext2fs, FAT等）提供统一接口
• 也为各种外部设备（块设备、网络设备）提供统一接口
• Linux的核心是扩展的快速文件管理系统

VFS架构：

• 上层：用户进程通过系统调用访问
• 中间层：VFS提供统一接口
• 底层：具体文件系统（Ext2fs等）+ 设备驱动

Ext2fs文件系统：

磁盘布局：

| 引导块 | 块组 | 块组 | ... | 块组 | ... | 块组 |
                            ↑
                  一组相邻的柱面

每个块组包含：

• 超级块（备份）
• 组描述符
• 位示图（block bitmap）
• inode表
• 文件块（数据块）

Ext2fs与VFS的差别：

特性	VFS	Ext2fs
块大小	大块（up to 8KB）+ 碎块（fragment）	统一长度块（1KB, 2KB, 4KB）
空闲块管理	—	位示图（bit map）
块分配	—	使文件物理块尽量连续或临近；预先分配，未用完盘块在文件关闭时释放

8.12 文件系统的效率（性能优化）

1. 缓存（caching）

• keep file blocks in core memory, whenever possible（尽可能将文件块保存在内存）
• keep read-in block buffers associated with file blocks
• keep write-out block buffers associated with file blocks

2. 预读（read ahead）

• 用于顺序访问
• 当前文件块 #15，下一个可能是 #16 → 预读 #16
• 实现：
  • 每个打开文件有一个访问位（access bit）
  • 打开时置为 0（顺序）
  • 发生seek时翻转标志（非顺序）

3. 延迟写（delayed write）

• 写操作延迟到绝对必要时才执行
• 触发时机：
  • 没有空闲缓冲区时
  • 文件关闭时（所有用户关闭，i_count = 0）
  • 系统刷新（system flush）

4. 减少磁盘臂移动（reducing disk arm motion）

• 为文件分配连续的磁盘块
• 磁盘访问请求按扫描顺序（scan order）服务

磁盘调度算法（考试必考重点）

磁盘调度算法用于决定多个磁盘I/O请求的服务顺序，目标是最小化磁头移动总距离（寻道时间）。

1. FCFS（First-Come, First-Served，先来先服务）

• 按请求到达顺序服务
• 优点：公平、实现简单
• 缺点：磁头移动距离大

2. SSFT / SSTF（Shortest Seek Time First，最短寻道时间优先）

• 每次选择距当前磁头位置最近的请求服务
• 优点：磁头移动距离小
• 缺点：① 可能"饥饿"（远处请求长期得不到服务）；② 不保证最优

3. SCAN（扫描算法 / 电梯算法）

• 磁头从一端向另一端移动，沿途服务所有请求
• 到达另一端后反向，继续服务
• 又称"电梯算法"（类似电梯运行）
• 优点：避免饥饿
• 缺点：磁头刚扫过的区域又要等到反向才能服务

4. C-SCAN（循环扫描）

• 磁头从一端向另一端移动，只在一个方向服务请求
• 到达另一端后，立即返回起始端（不服务途中请求）
• 返回过程中不服务任何请求
• 优点：每个请求等待时间更均匀
• 缺点：返回时不服务请求，造成浪费

5. LOOK / C-LOOK

• 实际系统常用：磁头不必到达磁盘两端
• LOOK：SCAN的改进，磁头只移动到最远请求处就反向
• C-LOOK：C-SCAN的改进，返回时也不必到达磁盘起点，只回到最远请求处

易混淆点：C-SCAN与C-LOOK区别在于磁头是否真的"返回起点"，SCAN与LOOK区别相同。

---

二、考点总结

考点1：文件和文件系统的概念

• 内容：文件是具有符号名而且在逻辑上具有完整意义的信息项的序列。文件系统是文件与管理文件的程序集合。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （填空）文件存在的两个条件是：①______；②______。 答案：①有符号名；②是信息项的序列
  2. （简答）什么是文件系统？ 答案：文件系统是操作系统中负责管理和存取文件的程序集合，它负责文件的创建、删除、读写、保护、共享等，并向用户提供统一的文件操作接口。

考点2：UNIX文件分类

• 内容：UNIX文件分为普通文件、目录文件、特殊文件。设备作为文件管理的好处是界面统一、保护容易。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （选择）UNIX中，下列属于特殊文件的是（ D ） A. 普通文件 B. 目录文件 C. 文本文件 D. 设备文件
  2. （简答）将设备作为文件管理有哪些好处？ 答案：①界面统一，使用open/close/read/write与文件操作相同；②可利用文件保护功能保护设备；③编程方便。

考点3：文件的逻辑组织与物理组织

• 内容：逻辑组织有记录式（等长/不等长）和流式。物理组织有顺序、链接、索引、Hash结构。
• 考查方式：选择、填空、简答、画图
• 可能的题目：
  1. （选择）等长记录的优点是（ C ） A. 节省空间 B. 长度可变 C. 处理方便速度快 D. 适合流式文件
  2. （简答）简述顺序、链接、索引三种物理组织的优缺点。 答案：见正文8.3.2节表格。

考点4：FCB（文件控制块）

• 内容：FCB是文件存在的标志，包含文件名、文件号、文件主、文件类型、文件属性、共享说明、文件长度、文件地址、建立/修改/访问日期、口令等。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （填空）文件控制块FCB是______的标志，其中保存______。 答案：文件存在；系统管理文件需要的全部信息
  2. （简答）FCB主要包括哪些内容？ 答案：见8.4节列表。

考点5：目录结构

• 内容：单级目录、两级目录、多级目录（树形）、无环图目录的特点和优缺点。
• 考查方式：选择、简答
• 可能的题目：
  1. （选择）UNIX系统采用（ C ） A. 单级目录 B. 两级目录 C. 多级目录 D. 无环图目录
  2. （简答）比较单级目录和两级目录的优缺点。 答案：单级目录简单但有重名问题、无法分组；两级目录支持路径名、不同用户可重名，但分组能力仍有限。

考点6：FCB的改进（主部+次部）

• 内容：次部保存文件名和文件号，主部保存其他信息。主部在外存inode区，目录项含次部。
• 考查方式：简答
• 可能的题目：
  1. （简答）为什么将FCB分成主部和次部？次部放在哪里？ 答案：次部只含文件名和文件号（16字节），放在目录文件中可提高目录查找速度（一次可读入更多目录项），且便于实现文件链接（多个目录项指向同一inode）。主部放inode区，打开文件时读入内存。

考点7：文件共享与硬链接

• 内容：通过link系统调用创建硬链接（多目录项指向同一inode，引用计数加1）；unlink减少引用计数，为0才真正删除。
• 考查方式：选择、简答、综合应用
• 可能的题目：
  1. （填空）UNIX中建立硬链接的命令是______，每建立一个硬链接，inode的______字段加1。 答案：link()；i_nlink（链接计数）
  2. （简答）简述link系统调用的执行步骤。 答案：见8.8节。

考点8：文件保护和保密

• 内容：保护防止未授权访问；保密防泄露；安全防破坏。存取控制矩阵、访问权限位（UNIX rwx）、口令、加密。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （填空）UNIX中判断文件主的条件是______。 答案：u_uid == i_uid
  2. （简答）存取控制矩阵的优缺点是什么？ 答案：优点是权限规定细，缺点是过于繁琐、占较多存储空间（用户和文件多时矩阵爆炸）。
  3. （简答）口令保密与密码保密的优缺点对比。 答案：口令简单但对系统操作员不保密；密码保密效果好但速度慢。

考点9：文件系统实现——内存表目

• 内容：用户打开文件表（每进程）、系统打开文件表（全局）、inode表。文件描述符fd是用户打开文件表入口。
• 考查方式：选择、填空、画图、简答
• 可能的题目：
  1. （填空）UNIX中，文件描述符是______表的入口，是______整数。 答案：用户打开文件表（u_ofile）；非负
  2. （画图）画出u_ofile、file、inode三表之间的联系。 答案：u_ofile[i] → file[j] → inode[k]，多对一映射。

考点10：主要系统调用的执行步骤

• 内容：creat、open、close、read、write、seek、link、unlink、pipe的步骤。
• 考查方式：简答、综合应用
• 可能的题目：
  1. （简答）简述open系统调用的执行步骤。 答案：见8.8节。共4步：查目录找FCB→合法性检查→查/建系统打开文件表项→建立用户打开文件表项。
  2. （简答）close时，什么情况下需要将内存FCB写回外存？ 答案：共享计数减1后为0且修改标志为1时，需要写回。

考点11：空闲块管理——成组连接法

• 内容：UNIX采用成组连接法管理空闲块，每100个块为一组，组间链接，第一组缓冲到内存。
• 考查方式：选择、简答、计算
• 可能的题目：
  1. （填空）UNIX采用______方法管理空闲块，每______块为一组。 答案：成组连接；100
  2. （简答）简述成组连接法申请和释放空闲块的过程。 答案：申请时，若s_nfree > 1，取s_free[--s_nfree]；若s_nfree = 1，将s_free[0]所指连接块读入内存，分配s_free[0]。释放时，若s_nfree < 100，s_free[s_nfree++] = 释放块号；若s_nfree = 100，将s_nfree和s_free拷贝到释放块中，将该块号记录到s_free[0]，写回外存，s_nfree = 1。

考点12：UNIX inode的多级索引

• 内容：i_addr[0]~[9]为10个直接地址；[10]为一级间接；[11]为二级间接；[12]为三级间接。最大文件块数 = 10+256+256²+256³。
• 考查方式：选择、计算
• 可能的题目：
  1. （选择）UNIX的inode采用（ D ）结构。 A. 顺序 B. 链接 C. 单一索引 D. 多级索引
  2. （计算）UNIX中，每块大小为1KB，每块号占4字节，问最大文件大小？ 答案：每块可存256个块号（1024/4）。最大块数 = 10+256+256²+256³ = 10+256+65536+16777216 ≈ 16843018块。最大文件大小 ≈ 16843018 × 1KB ≈ 16GB。

考点13：日志结构文件系统（LFS）

• 内容：LFS把磁盘视为日志，写入先入缓冲，达到segment规模后批量追加到日志末尾。Cleaner线程负责压缩segment。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （填空）LFS将整个磁盘看作一个______，周期性追加新日志。 答案：日志（log）
  2. （简答）LFS为什么要引入Inode map？Cleaner线程的作用是什么？ 答案：inode存储位置不再由编号确定，所以需要Inode map维护i-number到磁盘inode的映射。Cleaner线程循环扫描磁盘segment，舍弃过时内容，合并有用数据为新segment写回，回收旧segment。

考点14：内存映射文件

• 内容：将文件映射到进程虚拟空间，以访问内存方式访问文件，避免系统调用开销。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （填空）内存映射文件的基本操作序列是：open → ______ → 使用 → ______ → close。 答案：map；unmap
  2. （简答）内存映射文件相比传统read/write方式有什么优点？ 答案：①以访问内存方式访问文件，速度快；②避免多次系统调用开销；③可方便地实现多进程共享；④由操作系统按需调页，对程序员透明。

考点15：文件系统效率优化

• 内容：缓存（caching）、预读（read ahead）、延迟写（delayed write）、减少磁盘臂移动（连续分配+按scan顺序服务）。
• 考查方式：选择、填空、简答
• 可能的题目：
  1. （简答）列举提高文件系统效率的四种方法。 答案：①缓存（将文件块保存在内存）；②预读（顺序访问时预读下一块）；③延迟写（写延迟到必要时）；④减少磁盘臂移动（连续块分配 + 按扫描顺序服务请求）。

考点16：磁盘调度算法（计算题重点）

16.1 FCFS（先来先服务）

题目：磁头初始位置在磁道50，请求队列依次为：98, 183, 37, 122, 14, 124, 65, 67。求FCFS的磁头移动总距离。

解答（按请求到达顺序服务）：

50 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
|48|  |85| |146| |85| |108| |110| |59|  |2|

• 50→98: 48
• 98→183: 85
• 183→37: 146
• 37→122: 85
• 122→14: 108
• 14→124: 110
• 124→65: 59
• 65→67: 2
• 总移动距离 = 48+85+146+85+108+110+59+2 = 643

16.2 SSTF（最短寻道时间优先）

题目：同16.1，磁头初始位置50。求SSTF的总移动距离。

解答（每次选距当前最近的请求）：

• 当前50，最近=65（距离15）
• 当前65，最近=67（距离2）
• 当前67，最近=37（距离30）
• 当前37，最近=14（距离23）
• 当前14，最近=...（剩余98, 183, 122, 124）
  • 距14最近=98（距离84），但实际剩14→98最近是98
  • 14→98（84），但其实更近的是回到67？已经走过了。
  • 实际算法：从14开始剩98(84), 183(169), 122(108), 124(110)
  • 最近=98（84）
• 98→122（24）
• 122→124（2）
• 124→183（59）
• 总移动距离 = 15+2+30+23+84+24+2+59 = 239

16.3 SCAN（扫描算法/电梯算法）

题目：同16.1，假设磁头初始位置50，向磁道号增大方向移动。求SCAN的总移动距离。

解答：

• 假设磁道范围 0~199（或更大），磁头从50向增大方向移动。
• 经过：50→65→67→98→122→124→183（已无更大请求）→ 假设到达199（端点）→反向→37→14
• 50→65: 15
• 65→67: 2
• 67→98: 31
• 98→122: 24
• 122→124: 2
• 124→183: 59
• 183→199（端点）: 16
• 199→37: 162
• 37→14: 23
• 总移动距离 = 15+2+31+24+2+59+16+162+23 = 334

16.4 C-SCAN（循环扫描）

题目：同16.1，磁头初始位置50，向磁道号增大方向。求C-SCAN的总移动距离。

解答：

• C-SCAN只在一个方向服务，到达端点后立即返回起点（返回途中不服务）。
• 50→65→67→98→122→124→183（已无更大）→ 199（端点）→ 0（返回起点）→ 14→37
• 50→65: 15
• 65→67: 2
• 67→98: 31
• 98→122: 24
• 122→124: 2
• 124→183: 59
• 183→199: 16
• 199→0: 199（不服务任何请求）
• 0→14: 14
• 14→37: 23
• 总移动距离 = 15+2+31+24+2+59+16+199+14+23 = 385

16.5 FCFS、SSTF、SCAN、C-SCAN对比

题目：磁盘请求队列：98, 183, 37, 122, 14, 124, 65, 67，磁头初始位置50，磁道范围0~199。

算法	服务顺序	总移动距离
FCFS	50→98→183→37→122→14→124→65→67	643
SSTF	50→65→67→37→14→98→122→124→183	239
SCAN（向大）	50→65→67→98→122→124→183→199→37→14	334
C-SCAN（向大）	50→65→67→98→122→124→183→199→0→14→37	385

考试技巧：

• SSTF通常移动距离最小，但可能"饥饿"远处请求。
• SCAN避免饥饿，但刚扫过的请求要等反向才服务。
• C-SCAN使等待时间均匀，但返回时不服务浪费。
• 答题时务必画出走磁道的全过程并标出每步距离。

考点17：i_mode权限位（UNIX）

• 内容：i_mode包含文件类型、Set uid、Set gid、黏着位，9位rwx分三组。
• 考查方式：选择、填空
• 可能的题目：
  1. （填空）UNIX的i_mode中，______位让执行该文件的进程身份暂时改为文件主身份。 答案：Set uid
  2. （判断）Set gid的作用是让进程暂时获得文件主权限。（错，Set gid是获得组权限）

考点18：管道（pipe）

• 内容：pipe创建无名管道，本质是内核缓冲区，fd[0]读、fd[1]写。读空则等待，写满则等待，关闭时唤醒对方。
• 考查方式：选择、简答
• 可能的题目：
  1. （填空）pipe系统调用返回两个文件描述符，______用于读，______用于写。 答案：fd[0]；fd[1]
  2. （简答）pipe读/写时分别会出现什么情况？ 答案：读时若读指针追上写指针，读者等待；写时若写指针追上读指针，写者等待；关闭时无读者则信号通知写者，无写者则唤醒等待读者。

考点19：mount与umount

• 内容：smount将特殊文件挂载到目录节点，使该目录成为新文件卷的根；sumount反向操作。
• 考查方式：选择、简答
• 可能的题目：
  1. （简答）简述mount的主要步骤。 答案：检查超级用户→找到特殊文件inode→合法性检查→找到挂载点inode→读super block到buf→建立mount表项→设置挂载点标志。

考点20：备份与磁盘整理

• 内容：海量转储（全部）和增量转储（仅修改部分）；通过转储-恢复可整理磁盘。
• 考查方式：选择、简答
• 可能的题目：
  1. （填空）磁盘备份有______和______两种方式。 答案：海量转储；增量转储
  2. （简答）为什么要采用增量转储？ 答案：全量备份耗时长、占空间大；增量转储只备份修改部分，时间短、空间省，恢复时用最近一次全量 + 后续增量。

---

总结：第八章是操作系统课程的核心章节之一，文件系统是用户与外存的接口，考点集中在文件组织（顺序/链接/索引）、FCB与目录结构、文件保护（存取控制矩阵/权限位）、UNIX文件系统实现（成组连接、inode多级索引）、系统调用流程、以及磁盘调度算法（FCFS/SSTF/SCAN/C-SCAN的计算）。其中磁盘调度算法的计算题是每年必考，必须掌握执行过程和总移动距离的计算方法。