978 lines
44 KiB
Markdown
978 lines
44 KiB
Markdown
# 第八章 文件系统
|
||
|
||
## 一、知识讲解
|
||
|
||
### 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
|
||
|
||
**典型用法**：
|
||
```c
|
||
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的计算）。其中**磁盘调度算法的计算题**是每年必考，必须掌握执行过程和总移动距离的计算方法。
|