894 lines
39 KiB
Markdown
894 lines
39 KiB
Markdown
# 第九章 设备与I/O管理
|
||
|
||
## 一、知识讲解
|
||
|
||
本章是操作系统课程中连接硬件与软件的关键章节，主要解决**计算机如何与外部设备进行高效、可靠的数据交换**问题。涉及设备分类、物理特性、I/O传输方式、设备分配、缓冲、磁盘调度、RAID、虚拟设备（SPOOLing）等核心内容，几乎每年必考。
|
||
|
||
---
|
||
|
||
### 9.1 设备及其分类
|
||
|
||
#### 9.1.1 按用途分类
|
||
|
||
设备按功能可分为三大类：
|
||
|
||
| 分类 | 含义 | 典型设备 |
|
||
|---|---|---|
|
||
| **存储型设备** | 用于永久/半永久保存数据 | 磁盘、磁带、光盘 |
|
||
| **I/O型设备** | 与外界进行数据交换的设备 | 扫描仪、打印机、键盘、鼠标、显示器 |
|
||
| **网络设备** | 用于网络通信 | 网卡、交换机、路由器 |
|
||
|
||
> **易考点**：键盘、显示器属于"输入/输出型设备"而非存储型；磁盘属于"存储型设备"但也参与I/O。
|
||
|
||
#### 9.1.2 按管理方式（共享属性）分类
|
||
|
||
这是**考试重点**，PPT明确给出了三种分类：
|
||
|
||
| 类型 | 特征 | 典型设备 |
|
||
|---|---|---|
|
||
| **共享型设备（块型）** | 多个进程的I/O操作以块为单位可以交叉（交替） | 磁盘 |
|
||
| **独占型设备（块型）** | 多个进程的I/O操作以块为单位不宜交叉 | 磁带 |
|
||
| **独占型设备（字符型）** | 多个进程的I/O操作以字符为单位不能交叉 | 打印机、键盘 |
|
||
|
||
**为什么磁盘是"共享"而磁带是"独占"？**
|
||
- 磁盘的寻道时间远大于旋转/传输时间，多进程交叉访问能"分摊"寻道延迟，提高吞吐。
|
||
- 磁带的读写头物理位置固定，多个进程交替使用需要频繁倒带，效率极低。
|
||
- 字符型设备（如打印机）只能顺序接收字符流，切换会破坏输出内容。
|
||
|
||
> **易错点**：不要把"块型共享"理解为任意交叉。**只能在块边界交叉**，且通过调度算法优化（参见9.6磁盘调度）。
|
||
|
||
---
|
||
|
||
### 9.2 设备的物理特性
|
||
|
||
#### 9.2.1 磁盘组的物理结构
|
||
|
||
一个磁盘组由**多个盘面**组成，每个盘面对应一个磁头，所有磁头固定在**引臂**上同步移动。
|
||
|
||
- **盘面（Platter）**：磁盘组的圆盘。
|
||
- **磁道（Track）**：盘面上的同心圆。
|
||
- **扇区（Sector）**：磁道被划分为若干扇区（最小读写单位）。
|
||
- **柱面（Cylinder）**：所有盘面上半径相同的磁道集合（同一引臂位置可同时访问）。
|
||
- **引臂（Arm）**：带动所有磁头径向移动的机械装置。
|
||
|
||
#### 9.2.2 磁盘的三维地址与一维地址转换
|
||
|
||
PPT给出了**核心公式**，这是考试常考题：
|
||
|
||
设磁盘有 `l` 个柱面，`m` 个盘面，`n` 个扇区/磁道，三维地址为 `(i, j, k)`，一维块号为 `b`：
|
||
|
||
$$
|
||
b = i \times m \times n + j \times n + k
|
||
$$
|
||
|
||
反之（已知 `b` 求 `(i, j, k)`）：
|
||
|
||
$$
|
||
i = b \div (m \times n)
|
||
$$
|
||
$$
|
||
j = (b \mod (m \times n)) \div n
|
||
$$
|
||
$$
|
||
k = b \mod (m \times n) \mod n
|
||
$$
|
||
|
||
**例题（PPT原题）**：设 `l=2, m=3, n=3`，柱面号 i=0→0→1，盘面号 j=0→1→2，扇区号 k=0→1→2，则块号 b=0,1,2,…,17 顺序排列。这就是"使相邻块物理上最近"的编址方法。
|
||
|
||
**为什么这样编址？**
|
||
- 同一柱面内的块读写只需切换磁头，无需移动引臂，**速度最快**；
|
||
- 同一盘面内的相邻扇区只需等待旋转，**次快**；
|
||
- 跨柱面读写需要移动引臂，**最慢**。
|
||
- 因此连续编号优先沿"扇区→盘面→柱面"扩展，使"逻辑相邻"的块在物理上也相邻，从而减少寻道时间。
|
||
|
||
#### 9.2.3 扇区交错（Interleaving）
|
||
|
||
磁盘旋转一周需要一定时间。当连续读多个扇区时，CPU/DMA处理完一个扇区的数据后，下一个扇区可能已经转过磁头，需要等到该扇区再次旋转回来。解决方法：**扇区交错编号**。
|
||
|
||
- **不交错**：扇区按 0,1,2,… 顺序编号 → 处理不及，会错过下一个扇区。
|
||
- **单交错（factor=2）**：编号为 0,2,4,1,3,5,… → 处理一个扇区后正好赶上下一扇区。
|
||
- **双交错（factor=3）**：处理更慢时使用。
|
||
|
||
> 交错因子需要根据CPU/DMA速度与磁盘转速匹配。现代磁盘采用**缓存**和**高速DMA**，交错因子通常为1。
|
||
|
||
#### 9.2.4 光盘的物理特性（补充）
|
||
|
||
- 读取原理：**凹坑（pit）/凸起（land）**，用激光反射强弱区分0/1。
|
||
- 螺旋线结构，约22188圈（展开长5.6km）。
|
||
- **恒定线密度（CLV）**：内侧转速高（530转/分），外侧转速低（200转/分），保证数据密度均匀、读取速度均匀。
|
||
- 帧结构：14 bit → symbol；42 symbol → frame（588 bit）；98 frame → sector（2352 byte）。
|
||
- 每个扇区含 2048 字节用户数据 + 288 字节 ECC/控制信息。
|
||
|
||
---
|
||
|
||
### 9.3 I/O 传输方式（四种核心方式）
|
||
|
||
这是**每年必考**的内容，必须掌握各方式的原理、流程图、优缺点对比。
|
||
|
||
#### 9.3.1 程序查询方式（Programmed I/O / Polling）
|
||
|
||
**原理**：
|
||
1. CPU向设备控制器发出I/O命令，启动设备。
|
||
2. CPU不断**循环查询**设备状态寄存器，看是否就绪。
|
||
3. 就绪后，CPU逐字节/字地从设备读/写数据到内存。
|
||
4. I/O完成后，CPU继续后续工作。
|
||
|
||
**致命缺点**：
|
||
- **CPU与设备串行工作**：设备工作时CPU只能空转等待。
|
||
- **浪费大量CPU时间**：CPU被反复查询占用。
|
||
|
||
> **本质问题**：CPU参与了数据搬运的全部过程。
|
||
|
||
#### 9.3.2 中断驱动方式（Interrupt-driven I/O）
|
||
|
||
**原理**：
|
||
1. CPU发出启动命令后，**立即返回继续做其他事**。
|
||
2. 设备准备好数据后，向CPU发**中断**。
|
||
3. CPU响应中断，进入中断处理程序，读/写数据。
|
||
4. 处理完毕后返回原任务。
|
||
|
||
**优点**：
|
||
- CPU与设备**并行工作**，CPU利用率显著提升。
|
||
|
||
**缺点**：
|
||
- 每传输一个字节/字都要中断一次，**中断开销大**。
|
||
- 设备多时，频繁中断严重影响系统性能（"interrupt storm"）。
|
||
|
||
#### 9.3.3 DMA方式（Direct Memory Access）
|
||
|
||
**原理**：引入**DMA控制器**，让DMA接管"数据搬运"，CPU只在开始和结束时参与。
|
||
|
||
**完整流程**（PPT原文）：
|
||
1. **DMA编程**：CPU设置DMA控制器（源地址、目标地址、传输字节数），启动设备。
|
||
2. 磁盘控制器将数据读入内部缓冲区并校验。
|
||
3. **DMA请求**：DMA向磁盘控制器发读请求，将内存地址放到地址总线。
|
||
4. **数据传输**：磁盘控制器将数据传至内存指定单元。
|
||
5. **回答**：磁盘控制器向DMA发回答。
|
||
6. DMA将地址+1、计数-1，重复②─④。
|
||
7. 计数为0时，DMA向CPU发**中断**。
|
||
|
||
**优点**：
|
||
- 数据传输由DMA控制，**不占用CPU**。
|
||
- 中断次数少（**仅在传输开始和结束时中断一次**）。
|
||
- 适合**块设备**（磁盘、磁带）。
|
||
|
||
**与中断方式的关键区别**：中断方式每个字节都中断，DMA方式只在块传输结束时中断。
|
||
|
||
#### 9.3.4 通道方式（Channel）
|
||
|
||
**原理**：通道是**专门负责I/O操作的处理器**（I/O处理机），有自己的指令系统，可以执行**通道程序**。
|
||
|
||
**通道的组成**：
|
||
- **指令系统**：基本操作包括 控制、读、写、转移、结束。
|
||
- **指令格式**：(操作码, 传输量, 特征位, 地址)。
|
||
- **运控部件**。
|
||
- **存储区**：与CPU共享内存（通道内有缓冲区）。
|
||
|
||
**关键数据结构**（PPT重点）：
|
||
| 缩写 | 全称 | 作用 |
|
||
|---|---|---|
|
||
| **CAW** | Channel Address Word | 存放下一条通道命令的地址 |
|
||
| **CCW** | Channel Command Word | 通道命令字（一条I/O指令） |
|
||
| **CSW** | Channel Status Word | 通道状态字（保存执行结果） |
|
||
| **CDW** | Channel Data Word | 通道数据字（存放数据） |
|
||
|
||
**执行过程**（PPT流程）：
|
||
1. 按CAW取一条CCW。
|
||
2. 执行该CCW。
|
||
3. (CAW)+1 → CAW。
|
||
4. 判断是否为"通道结束"命令：否则返回①；是则向CPU发中断。
|
||
|
||
**关键特点**：
|
||
- 一个通道程序可控制**多个设备进行多次I/O传输**（DMA只能控制一个设备）。
|
||
- 通道独立于CPU工作，进一步解放CPU。
|
||
|
||
#### 9.3.5 三种通道类型（PPT强调）
|
||
|
||
| 类型 | 子通道性质 | 连接设备 | 特点 |
|
||
|---|---|---|---|
|
||
| **字节多路通道** | 多个**非分配型**子通道 | 低速字符设备 | 多个设备分时共享通道，按字节交叉 |
|
||
| **数组选择通道** | 一个**分配型**子通道 | 高速块设备 | 一次独占通道，传输完才让出 |
|
||
| **数组多路通道** | 多个**非分配型**子通道 | 高速块设备 | 既高速又可分时共享，最强 |
|
||
|
||
> **分配型 vs 非分配型**：分配型 = 整个通道被一个设备独占；非分配型 = 多个设备分时使用通道。
|
||
|
||
#### 9.3.6 四种I/O方式对比（必考表格）
|
||
|
||
| 方式 | CPU与设备并行 | 数据传输单位 | 中断次数 | 适用 |
|
||
|---|---|---|---|---|
|
||
| 程序查询 | 否 | 字节 | 0（轮询） | 极少用 |
|
||
| 中断驱动 | 是 | 字节 | 每字节一次 | 慢速字符设备 |
|
||
| DMA | 是 | 块 | 每块一次（首尾各一） | 块设备 |
|
||
| 通道 | 是 | 块/组 | 更少（多个块） | 复杂I/O |
|
||
|
||
---
|
||
|
||
### 9.4 设备的分配与去配
|
||
|
||
#### 9.4.1 数据结构（4张表）
|
||
|
||
设备分配依赖四个核心数据结构，**PPT考试必考**：
|
||
|
||
| 缩写 | 全称 | 内容 |
|
||
|---|---|---|
|
||
| **UCB** | Unit Control Block（设备控制块） | 设备标识、状态、相连通道、占有设备进程 |
|
||
| **CCB** | Channel Control Block（通道控制块） | 通道标识、状态、类型、占有通道进程 |
|
||
| **COCT** | Channel-Operation Control Table（通道-操作控制表，PPT的"通道控制块"） | — |
|
||
| **SDT** | System Device Table（系统设备表） | 设备类、总数、设备等待队列、UCB表指针 |
|
||
|
||
**SDT是入口**，每个设备类对应SDT中一项，每项的指针指向该类的UCB表。
|
||
|
||
#### 9.4.2 独占型设备的分配与去配
|
||
|
||
用户使用独占设备的流程：**申请 → 使用 → 使用 → … → 使用 → 释放**
|
||
|
||
**申请步骤**：
|
||
1. 根据设备类查SDT表。
|
||
2. `P(Sm)` 对该类设备的信号量做P操作。
|
||
3. 查UCB表，找一空闲设备并分配。
|
||
|
||
**使用步骤**：
|
||
1. 分配通道（修改CCB）。
|
||
2. I/O传输。
|
||
3. 去配通道。
|
||
|
||
**释放步骤**：
|
||
1. 找SDT对应入口。
|
||
2. 查UCB表，去配。
|
||
3. `V(Sm)`。
|
||
|
||
#### 9.4.3 共享型设备的分配与去配
|
||
|
||
共享设备的特征：
|
||
- **不需要"申请-释放"**！进程直接使用。
|
||
- 来自文件系统调用，每次读/写一块。
|
||
- 通常**经过缓冲**（参见9.7）。
|
||
- 通过**排队优化**（磁盘调度）。
|
||
|
||
> **对比**：独占设备需要事先申请、事后释放；共享设备随用随开，调度算法决定访问顺序。
|
||
|
||
---
|
||
|
||
### 9.5 设备驱动
|
||
|
||
设备驱动是**操作系统中专门负责某个设备I/O的代码模块**，向上提供统一接口，向下控制硬件。
|
||
|
||
**驱动的工作流程**（PPT流程图）：
|
||
1. 接收I/O请求 → 形成**通道程序**（CCW序列）。
|
||
2. 将通道程序首地址 → **CAW**。
|
||
3. **启动通道**。
|
||
4. 通道执行CCW，与设备交互传输数据。
|
||
5. 通道完成 → **向CPU发中断**。
|
||
6. CPU响应中断，执行中断处理程序。
|
||
|
||
通道程序可**静态编制**（编译时确定）或**动态生成**（运行时根据请求构造）。
|
||
|
||
---
|
||
|
||
### 9.6 设备调度（磁盘调度，**考试重中之重**）
|
||
|
||
#### 9.6.1 调度目标
|
||
|
||
- **公平性**：所有请求都应被服务。
|
||
- **防止饿死**：避免某些请求长期得不到服务。
|
||
- **高效性**：减少磁盘引臂移动量（寻道时间），提高吞吐。
|
||
|
||
#### 9.6.2 磁盘I/O时间组成（计算基础）
|
||
|
||
访问一个磁盘块的总时间 Ta 由三部分组成：
|
||
|
||
$$
|
||
T_a = T_s + T_r + T_t
|
||
$$
|
||
|
||
| 符号 | 名称 | 公式 | 含义 |
|
||
|---|---|---|---|
|
||
| **Ts** | 寻道时间 | Ts = m × n + s | n=跨越磁道数，m=每磁道移动时间，s=启动时间 |
|
||
| **Tr** | 旋转延迟 | Tr = 1/(2r) | r=转速（转/秒），即旋转半周的平均时间 |
|
||
| **Tt** | 传输时间 | Tt = b/(rN) | b=读写字节数，N=每磁道字节数 |
|
||
|
||
**例题计算**（PPT例8-1）：
|
||
- 磁道0~199，跨越1道需1ms，每道100扇区，转速6000 r/m = 100 r/s。
|
||
- 4次访盘：
|
||
- 寻道：20+90+40+15 = 165 道 → 165 ms。
|
||
- 旋转延迟：1/(2×100) = 5 ms/次 → 20 ms。
|
||
- 传输：1/(100×100) = 0.1 ms/次 → 0.4 ms。
|
||
- **总时间 = 165 + 20 + 0.4 = 185.4 ms**。
|
||
|
||
#### 9.6.3 磁盘调度算法（**必考计算**）
|
||
|
||
设磁道请求序列：**130, 42, 180, 15, 108, 68, 97**，磁头当前位置 **53**。
|
||
|
||
##### (1) FCFS（先到先服务）
|
||
|
||
按请求到达顺序服务。
|
||
|
||
- 路径：53 → 130 → 42 → 180 → 15 → 108 → 68 → 97
|
||
- 移动量：(130-53) + (130-42) + (180-42) + (180-15) + (108-15) + (108-68) + (97-68)
|
||
- = 77 + 88 + 138 + 165 + 93 + 40 + 29 = **630**
|
||
|
||
**特点**：公平，但效率差，无寻道优化。
|
||
|
||
##### (2) SSTF（最短寻找时间优先）
|
||
|
||
每次选**距离磁头当前位置最近**的请求。
|
||
|
||
- 53 → 42（差11）→ 68（差26）→ 97（差29）→ 108（差11）→ 130（差22）→ 15（差115）→ 180（差165）
|
||
- **另一种常见正确路径**（从53出发优先选最近的）：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 42 → 15
|
||
- 移动量：(68-53)+(97-68)+(108-97)+(130-108)+(180-130)+(180-42)+(42-15)
|
||
- = 15 + 29 + 11 + 22 + 50 + 138 + 27 = **292**
|
||
- **PPT给出的移动量**：314（按 53→42→180→15 简化版本，实际有不同走法）
|
||
- 实际上"正确"的SSTF从53出发选最近的应该是 42，所以 PPT 写 53→42 开始。
|
||
- 按 PPT 写法：53→42→180→15 移动量 = (53-42)+(180-42)+(180-15) = 11+138+165 = 314（PPT 仅给出关键几步的简化）
|
||
|
||
**注意**：SSTF是**贪心算法**，可能**导致饿死**（远端请求长期等不到服务）。
|
||
|
||
##### (3) SCAN（电梯算法）
|
||
|
||
磁头在一个方向上**一直移动到最端**，途中服务所有请求，到端点后反向。
|
||
|
||
- 设方向由外向内（向内移动），磁道范围 0~199。
|
||
- 当前 53 向内（向高编号移动）：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 199 → （反向）→ 42 → 15 → 0
|
||
- **SCAN移动量**：(199-53) + (199-0) = 146 + 199 = **345**
|
||
- **PPT简化写法**：(53-0) + (180-0) = 233（按简化假设）
|
||
- 实际严格计算应包含端点。
|
||
|
||
**LOOK算法**（PPT提及）：是SCAN的改进，**不到端点**就反向，只服务到最远请求。
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → （反向）→ 42 → 15
|
||
- 移动量：(180-53) + (180-15) = 127 + 165 = **292**
|
||
- **PPT给出的LOOK移动量**：203（按简化版 (53-15) + (180-15) = 38+165=203）
|
||
|
||
> PPT 上的 SCAN/LOOK 数字可能采用"路径上经过的请求"的简化算法，考试时建议按标准定义计算并写出完整路径。
|
||
|
||
##### (4) C-SCAN（循环扫描）
|
||
|
||
单向扫描（只向一个方向），到达端点后**快速返回起点**，从起点重新开始同方向扫描。
|
||
|
||
- 53 向内：53 → 68 → 97 → 108 → 130 → 180 → 199 → 快速回到 0 → 15 → 42
|
||
- **移动量**：(199-53) + (199-0) + (42-0) = 146 + 199 + 42 = **387**
|
||
- 或更简单的算法：到达端点 + 跳回起点 + 起点到最远请求。
|
||
|
||
**C-LOOK**：C-SCAN的改进，回到最远请求而非端点。
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 跳回 15 → 42
|
||
- 移动量：(180-53) + (180-15) + (42-15) = 127 + 165 + 27 = **319**
|
||
|
||
**C-SCAN优点**：所有磁道被服务的**最长等待时间相同**，公平性好。
|
||
|
||
**缺点**：disk head stickiness（磁头粘性）—— 大量请求集中在磁头移动方向上时，刚服务过的磁道要等一整圈才能再次服务。
|
||
|
||
##### (5) N-step SCAN（N步扫描）
|
||
|
||
将请求队列**分成若干长度为N的子队列**，每个子队列内部用SCAN算法；服务完一个子队列后再服务下一个。
|
||
|
||
- **N很大时** → 接近SCAN算法。
|
||
- **N=1时** → 退化为FCFS。
|
||
- 例：N=4，磁头在20向内，请求分组成 [12,5,7,30]、[60,77,13,26]、[61,80,53,66]。
|
||
- 服务顺序：20→30→12→7→5 → 60→77→13→26 → 80→66→61→53
|
||
|
||
##### (6) FSCAN（冻结扫描）
|
||
|
||
用**两个队列**：服务队列 + 请求队列。
|
||
- 用SCAN扫描服务队列，期间**新到达的请求入请求队列**。
|
||
- 服务队列扫完后交换两队列身份。
|
||
|
||
> FSCAN 是 N-step SCAN 的特例（N=服务队列长度）。
|
||
|
||
#### 9.6.4 调度算法对比
|
||
|
||
| 算法 | 公平性 | 寻道效率 | 饿死可能 | 复杂度 |
|
||
|---|---|---|---|---|
|
||
| FCFS | 高 | 差 | 无 | 最低 |
|
||
| SSTF | 低 | 好 | 有 | 中 |
|
||
| SCAN/LOOK | 中 | 好 | 无 | 中 |
|
||
| C-SCAN/C-LOOK | 高 | 好 | 无（最长等待时间相同） | 中 |
|
||
| N-step SCAN | 高 | 好 | 无 | 高 |
|
||
| FSCAN | 高 | 好 | 无 | 中 |
|
||
|
||
---
|
||
|
||
### 9.7 缓冲技术（Buffering）
|
||
|
||
#### 9.7.1 缓冲的目的
|
||
|
||
**解决设备数据到达与离开速度不一致**的问题。在内存中设置缓冲区作为"中转站"。
|
||
|
||
#### 9.7.2 Buffering vs Caching
|
||
|
||
- **Buffering（缓冲）**：数据**只有一份**，用于速度匹配。
|
||
- **Caching（缓存）**：数据**可能有多个副本**（fast中存slow的副本），利用局部性原理提高访问速度。
|
||
|
||
#### 9.7.3 硬缓冲 vs 软缓冲
|
||
|
||
- **硬缓冲**：设在设备内部（如打印机自带缓冲区）。
|
||
- **软缓冲**：设在内存系统空间中（操作系统管理）。
|
||
|
||
#### 9.7.4 私用缓冲 vs 公共缓冲
|
||
|
||
- **私用缓冲**：一个缓冲区与一个固定设备绑定。简单但**利用率低**。
|
||
- **公共缓冲（缓冲池）**：系统统一管理，按需动态分配。**利用率高**，是现代OS采用方式。
|
||
|
||
#### 9.7.5 缓冲池管理（PPT伪代码）
|
||
|
||
```
|
||
Var buf_num: semaphore; // 初始 n，表示空闲缓冲数
|
||
mutex: semaphore; // 初始 1，互斥访问缓冲链
|
||
|
||
申请缓冲： 释放缓冲：
|
||
P(buf_num) P(mutex)
|
||
P(mutex) 空缓冲入链尾
|
||
取链头空缓冲 V(mutex)
|
||
V(mutex) V(buf_num)
|
||
```
|
||
|
||
#### 9.7.6 单缓冲、双缓冲、循环缓冲（扩展）
|
||
|
||
- **单缓冲**：1个缓冲区，设备和处理器串行工作（设备写满缓冲区→处理器读走→再启动设备）。性能 = max(T, C)。
|
||
- **双缓冲**：2个缓冲区交替使用，实现设备和处理器的并行（生产者-消费者经典模式）。性能 = max(T, C)，但可达流水线效果。
|
||
- **循环缓冲**：N个缓冲区组成环形队列，支持双缓冲无法处理的突发流量。
|
||
- **缓冲池**：多个缓冲区统一管理，可服务多个I/O设备。
|
||
|
||
#### 9.7.7 输入设备的缓冲实现（PPT流程）
|
||
|
||
- **进程方面**：申请空缓冲→启动设备→等待→从io链取缓冲→信息送到进程空间→释放空缓冲。
|
||
- **中断方面**：传输完毕→申请空缓冲→启动设备→缓冲入io链尾→若有等待进程唤醒。
|
||
|
||
> 注意"申请空缓冲"在进程侧和中断侧**都会发生**：进程要缓冲处理数据，中断要缓冲准备下次接收。
|
||
|
||
#### 9.7.8 块型设备缓冲（UNIX风格）
|
||
|
||
- 50个缓冲区，每个514字节（512数据+2控制）。
|
||
- 缓冲区属于某设备或在自由链 `bfreelist` 上。
|
||
- 关键操作：
|
||
- `getblk(dev, blkno)`：获取/分配一个缓冲块。
|
||
- `bread(dev, blkno)`：读一个块，若已在缓存直接返回。
|
||
- `breada(dev, blkno, rablkno)`：读主块同时预读下一块。
|
||
- `bwrite(bp)`：同步写。
|
||
- `bawrite(bp)`：异步写，立即释放。
|
||
- `bdwrite(bp)`：延迟写（标记B_DELWRI，腾出缓冲前才实际写盘）。
|
||
- `brelse(bp)`：释放缓冲入空闲链。
|
||
|
||
> **预读（readahead）和延迟写（delayed write）** 是缓冲的核心优化思想。
|
||
|
||
---
|
||
|
||
### 9.8 输入输出进程
|
||
|
||
#### 9.8.1 概念
|
||
|
||
**专门负责I/O传输的进程**。将I/O封装为独立的"服务进程"，形成 **C/S（Client/Server）模式**。
|
||
|
||
#### 9.8.2 特点
|
||
|
||
- **界面清晰**，上层进程通过消息/系统调用请求I/O服务。
|
||
- **两次进程切换**（请求进程→I/O进程→I/O完成→请求进程），有**速度开销**。
|
||
|
||
---
|
||
|
||
### 9.9 RAID 技术
|
||
|
||
#### 9.9.1 RAID 概念
|
||
|
||
- **RAID**：Redundant Array of Inexpensive Disks（廉价磁盘冗余阵列），后又叫 Redundant Array of Independent Disks（**独立磁盘冗余阵列**）。
|
||
- 由 UC Berkeley 的 **David A. Patterson** 等提出。
|
||
- 背景：磁盘访问速度增长远慢于CPU和内存，多盘并行是解决方案。
|
||
- 目标：**高性能 + 高可靠性**。
|
||
|
||
#### 9.9.2 RAID 核心概念
|
||
|
||
- **物理上**：多个独立磁盘。
|
||
- **逻辑上**：操作系统看作**一个单一的逻辑盘**。
|
||
- 数据分布存储在多个物理盘上。
|
||
- 利用部分冗余容量存放**校验信息**，保证故障后可恢复。
|
||
|
||
#### 9.9.3 硬件RAID vs 软件RAID
|
||
|
||
| 维度 | 硬件RAID | 软件RAID |
|
||
|---|---|---|
|
||
| 实现 | 专用RAID控制器 | 操作系统软件 |
|
||
| 成本 | 高 | 低 |
|
||
| 性能 | 高（独立硬件） | 较低（占用CPU） |
|
||
| 支持级别 | 全部 | 通常仅0,1,5 |
|
||
| 引导卷支持 | 全部 | **不能作为引导卷** |
|
||
| 兼容性 | 好 | 与其他软件可能冲突 |
|
||
| 可靠性 | 高 | 软件bug风险 |
|
||
|
||
#### 9.9.4 RAID级别（**必考表格**）
|
||
|
||
| Level | 分条粒度 | 读并发 | 写并发 | 冗余方式 |
|
||
|---|---|---|---|---|
|
||
| **0** | 块 | 支持 | 支持 | **无**（无容错） |
|
||
| **1** | 块 | 支持 | **不支持** | 镜像（100%冗余） |
|
||
| **2** | 位 | 不支持 | 不支持 | 汉明纠错码 |
|
||
| **3** | 位 | 不支持 | 不支持 | 单个奇偶校验 |
|
||
| **4** | 块 | 支持 | **不支持** | 块级异或校验（校验盘独立） |
|
||
| **5** | 块 | 支持 | **支持** | 块级分布式异或校验 |
|
||
|
||
##### RAID 0（数据分条）
|
||
|
||
- 数据按**块**循环分条到多个磁盘。
|
||
- 优点：访问速度快，空间利用率100%。
|
||
- 缺点：**无容错**，任一盘坏全部数据丢失。
|
||
|
||
##### RAID 1（镜像）
|
||
|
||
- 数据按**块**分条，**完全相同的数据存两份**（分布镜像）。
|
||
- 读：可读任一副本 → 速度快。
|
||
- 写：必须写两个盘 → 写速度无提升。
|
||
- 空间利用率仅 **50%**，但**可靠性最高**。
|
||
|
||
##### RAID 2（位级汉明码）
|
||
|
||
- 数据按**位**分条到多个数据盘。
|
||
- 校验盘存放**汉明纠错码**，可发现2位错误、纠正1位错误。
|
||
- 缺点：需要较多校验盘，成本高；写必须访问所有盘，速度慢。
|
||
|
||
##### RAID 3（位级单奇偶校验）
|
||
|
||
- 数据按**位**分条到数据盘，**一个独立盘**存放**奇偶校验位**。
|
||
- 校验计算：P = bit0 XOR bit1 XOR bit2 XOR bit3（设4个数据盘）。
|
||
- 故障恢复：bit_i = P XOR (其余所有bit的异或)。
|
||
- 缺点：读写都要访问所有盘，多请求**无法并行**。
|
||
|
||
##### RAID 4（块级异或校验）
|
||
|
||
- 数据按**块**分条，校验盘**独立**。
|
||
- 读操作**可并行**（只需访问相关数据盘）。
|
||
- 写操作要更新校验盘，**校验盘成为瓶颈**，**写不可并行**。
|
||
- 校验更新公式：`P'_4~7 = (block4 XOR block4') XOR P_4~7`。
|
||
- 故障恢复：`block7 = P_4~7 XOR block4 XOR block5 XOR block6`。
|
||
|
||
##### RAID 5（块级分布式校验）
|
||
|
||
- 数据按**块**分条，校验信息**循环分布在各盘**上（无独立校验盘）。
|
||
- 读写都**可并行**（只要不涉及同一数据盘和校验盘）。
|
||
- 空间利用率 `(N-1)/N`。
|
||
- 任意盘故障都可通过其余 `N-1` 个盘恢复。
|
||
- 至少需要 **3 个盘**。
|
||
|
||
#### 9.9.5 RAID 优缺点总结
|
||
|
||
- 优点：读/写速度提升、数据可靠性高、容量扩大。
|
||
- 缺点：成本上升、软件RAID性能受限、引导卷限制、故障恢复复杂。
|
||
|
||
---
|
||
|
||
### 9.10 虚拟设备（SPOOLing）
|
||
|
||
#### 9.10.1 概念
|
||
|
||
利用**共享型设备（磁盘）**实现数量较多、速度较快的**独占型设备**。
|
||
|
||
**引入原因**：用户直接使用独占设备（如打印机）效率低：
|
||
- CPU快、打印机慢 → 速度不匹配。
|
||
- 占有期间未必一直在用 → 设备利用率低。
|
||
- 进程独占设备 → 其他进程等待。
|
||
|
||
#### 9.10.2 实现方法
|
||
|
||
在进程和独占设备之间增加**共享设备（磁盘）作为缓冲**：
|
||
- 进程→虚拟设备：间断传输（向磁盘写）。
|
||
- 虚拟设备→独占设备：连续传输（由SPOOLing控制）。
|
||
|
||
#### 9.10.3 输入型虚拟设备（SPOOLing 输入）
|
||
|
||
- 用户→**输入井**（磁盘上的虚拟输入区）。
|
||
- **预输入进程**：把输入机数据预先读入输入井。
|
||
- 进程从输入井读数据（高速）。
|
||
|
||
**申请 → 使用 → 释放**：
|
||
- 申请：分配虚设备→分配实设备→数据由实设备→虚设备→去配实设备。
|
||
- 使用：数据由虚设备→进程空间。
|
||
- 释放：去配虚设备。
|
||
|
||
#### 9.10.4 输出型虚拟设备（SPOOLing 输出）
|
||
|
||
- 进程→**输出井**（磁盘上的虚拟输出区）。
|
||
- **缓输出进程**：把输出井数据送往输出机。
|
||
- 进程向输出井写数据（高速）。
|
||
|
||
#### 9.10.5 SPOOLing 系统结构
|
||
|
||
**SPOOLing** = **S**imultaneous **P**eripheral **O**perations **O**n-**L**ine（同时外围设备在线操作）。
|
||
|
||
由 **SPOOLing程序控制通道**完成磁盘与外围设备之间的数据传送。
|
||
|
||
**核心组成**：
|
||
1. **输入井 / 输出井**：磁盘上的存储区。
|
||
2. **输入SPOOLing进程 / 输出SPOOLing进程**：后台进程。
|
||
3. **作业控制块（JCB）**：管理作业信息。
|
||
|
||
**JCB内容**：
|
||
- 作业标识、用户标识、作业状态、调度参数
|
||
- 作业位置、资源需求、进入时间、处理时间、记账信息
|
||
|
||
#### 9.10.6 作业状态变迁（SPOOLing）
|
||
|
||
```
|
||
提交 → 后备 → 执行 → 完成 → 退出
|
||
```
|
||
|
||
- **预输入程序**：扫描"提交"作业，将其读入输入井（"后备"）。
|
||
- **作业调度程序**：从"后备"作业中按调度算法选作业进入内存（"执行"）。
|
||
- **作业调度程序2**：处理终止作业，将其状态改为"完成"，唤醒"完成"作业等待者。
|
||
- **SPOOLing输出程序**：将"完成"作业从输出井送往输出机，状态改"退出"。
|
||
|
||
#### 9.10.7 SPOOLing 优点
|
||
|
||
- **设备独立性**：用户面向虚设备，不直接面对物理设备。
|
||
- **提高设备利用率**：独占设备变为可共享。
|
||
- **提高CPU效率**：CPU与设备并行工作。
|
||
|
||
---
|
||
|
||
### 9.11 稳定存储器（Stable Storage）
|
||
|
||
#### 9.11.1 定义
|
||
|
||
**不丢失信息的存储器**称为稳定存储器。
|
||
|
||
#### 9.11.2 实现策略
|
||
|
||
- 不存在绝对可靠的存储介质 → 采用**冗余**策略。
|
||
- 在**两种失效独立**的介质上构建（如同型号磁盘的两份拷贝）。
|
||
|
||
#### 9.11.3 保存操作
|
||
|
||
1. 将信息写到**第一个存储块**。
|
||
2. 第一个成功后，将**相同信息写到第二个存储块**。
|
||
3. 仅当第二次传输也成功时，整个保存操作完成。
|
||
|
||
#### 9.11.4 恢复操作
|
||
|
||
读取一对数据块，鉴别内容：
|
||
- **一对完全相同且无误** → 正常。
|
||
- **一块检测到错误** → 用另一块取代。
|
||
- **两块都无误但内容不同** → 用**第二块**内容覆盖第一块（第二块是最新写入的）。
|
||
|
||
> 第二块优先于第一块：因为第一块可能由于第一次写时故障导致内容陈旧。
|
||
|
||
---
|
||
|
||
### 9.12 系统举例：Windows 10 I/O 子系统
|
||
|
||
PPT提到的主要特点：
|
||
|
||
- **设备驱动**：支持多种可装卸文件系统（FAT32、OS/2、HPFS、CDFS等）；设备驱动以DLL形式动态加载，可用高级语言编写，移植性好。
|
||
- **I/O请求包（IRP）**：I/O管理器以IRP方式驱动，每个I/O请求均表示为IRP，I/O管理器协调各组件。
|
||
- **异步I/O**：通过**系统线程**实现，调用进程不必等待I/O完成。底层使用**APC（异步过程调用）**机制。
|
||
- **映像文件I/O**：支持。
|
||
|
||
---
|
||
|
||
## 二、考点总结
|
||
|
||
### 考点1：设备分类（用途+管理方式）
|
||
|
||
- **内容**：按用途分为存储型、I/O型、网络设备；按管理方式分为块型共享、块型独占、字符型独占。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. 下列属于"块型共享设备"的是？答：磁盘。
|
||
2. 打印机属于哪一类设备？答：独占型（字符型）。
|
||
|
||
### 考点2：磁盘三维/一维地址转换
|
||
|
||
- **内容**：`b = i × m × n + j × n + k`；反推公式：`i = b÷(m×n), j = (b mod (m×n))÷n, k = b mod (m×n) mod n`。
|
||
- **考查方式**：计算题、填空。
|
||
- **可能的题目**：
|
||
1. 磁盘 l=4, m=5, n=8，求块号 100 对应的 (i,j,k)。
|
||
答：i = 100÷40 = 2；j = (100 mod 40)÷8 = 20÷8 = 2；k = 100 mod 40 mod 8 = 20 mod 8 = 4。所以 (2,2,4)。
|
||
|
||
### 考点3：扇区交错编号
|
||
|
||
- **内容**：磁盘高速旋转，处理一个扇区的时间内扇区可能转过磁头，需要交错编号（单交错、双交错）。
|
||
- **考查方式**：简答、填空。
|
||
- **可能的题目**：
|
||
1. 为什么磁盘需要扇区交错编号？答：因为磁盘旋转时，处理完一个扇区数据后下一扇区可能已转过磁头；交错编号使下一扇区恰好转到磁头下，保证连续读。
|
||
|
||
### 考点4：四种I/O传输方式对比
|
||
|
||
- **内容**：程序查询、中断、DMA、通道的原理、并行性、中断次数、适用场景。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. 哪种I/O方式适合块设备且CPU开销最小？答：通道方式。
|
||
2. DMA方式中断发生在什么时候？答：只在传输开始设置和传输结束时各一次（整块传输开始和结束）。
|
||
3. 程序查询方式的主要缺点？答：CPU与设备串行工作，CPU空转浪费大量时间。
|
||
|
||
### 考点5：通道的三种类型
|
||
|
||
- **内容**：字节多路通道（低速字符设备分时共享）、数组选择通道（高速独占）、数组多路通道（高速分时共享）。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. 连接高速块设备且支持分时共享的通道是？答：数组多路通道。
|
||
2. 字节多路通道适合连接哪类设备？答：低速字符设备。
|
||
|
||
### 考点6：通道程序相关数据结构
|
||
|
||
- **内容**：CAW、CCW、CSW、CDW的含义。
|
||
- **考查方式**：填空、选择。
|
||
- **可能的题目**：
|
||
1. 存放下一条通道命令地址的寄存器是？答：CAW。
|
||
2. 保存通道执行结果的是？答：CSW。
|
||
|
||
### 考点7：设备分配的数据结构
|
||
|
||
- **内容**：UCB、CCB、SDT的作用与关系。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. 系统设备表的英文缩写？答：SDT。
|
||
2. 设备分配的入口表是？答：SDT。
|
||
|
||
### 考点8：独占设备 vs 共享设备的分配差异
|
||
|
||
- **内容**：独占设备需要"申请-使用-释放"流程；共享设备直接使用，由调度算法决定顺序。
|
||
- **考查方式**：简答。
|
||
- **可能的题目**：
|
||
1. 共享型设备的分配与独占型有何不同？答：共享设备无需事先申请和事后释放，进程直接使用，每次I/O一块，通常经过缓冲，由调度算法决定访问顺序。
|
||
|
||
### 考点9：磁盘调度算法（**计算必考**）
|
||
|
||
- **内容**：FCFS、SSTF、SCAN/LOOK、C-SCAN/C-LOOK、N-step SCAN、FSCAN。
|
||
- **考查方式**：计算题（最重要的题型）、简答。
|
||
- **可能的题目（计算）**：
|
||
|
||
**例题1：FCFS计算**
|
||
- 题目：磁头当前位置53，请求序列130、42、180、15、108、68、97，磁道范围0~199。求FCFS的访问顺序和总移动量。
|
||
- 解答：53→130→42→180→15→108→68→97
|
||
- 移动量 = (130-53) + (130-42) + (180-42) + (180-15) + (108-15) + (108-68) + (97-68)
|
||
- = 77 + 88 + 138 + 165 + 93 + 40 + 29 = **630**
|
||
|
||
**例题2：SSTF计算**
|
||
- 题目：同例1，使用SSTF算法。
|
||
- 解答（贪心，每次选距离最近的）：
|
||
- 53 → 42（差11）→ 68（差26）→ 97（差29）→ 108（差11）→ 130（差22）→ 15（差115）→ 180（差165）
|
||
- 移动量 = 11 + 26 + 29 + 11 + 22 + 115 + 165 = **379**
|
||
|
||
**例题3：SCAN计算**
|
||
- 题目：磁头在53，方向向内（向大编号），磁道0~199，请求序列：130,42,180,15,108,68,97。使用SCAN算法。
|
||
- 解答：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 199 → 反向 → 42 → 15 → 0
|
||
- 移动量 = (199-53) + (199-0) = 146 + 199 = **345**
|
||
|
||
**例题4：LOOK计算**
|
||
- 题目：同上，使用LOOK算法（不到端点）。
|
||
- 解答：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 反向 → 42 → 15
|
||
- 移动量 = (180-53) + (180-15) = 127 + 165 = **292**
|
||
|
||
**例题5：C-SCAN计算**
|
||
- 题目：磁头在53，方向向内，请求序列同上，使用C-SCAN算法。
|
||
- 解答：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 199 → 快速跳回 0 → 15 → 42
|
||
- 移动量 = (199-53) + (199-0) + (42-0) = 146 + 199 + 42 = **387**
|
||
|
||
**例题6：C-LOOK计算**
|
||
- 题目：同上，使用C-LOOK。
|
||
- 解答：
|
||
- 53 → 68 → 97 → 108 → 130 → 180 → 跳回最远请求 15 → 42
|
||
- 移动量 = (180-53) + (180-15) + (42-15) = 127 + 165 + 27 = **319**
|
||
|
||
### 考点10：磁盘I/O时间计算
|
||
|
||
- **内容**：Ts = m×n + s；Tr = 1/(2r)；Tt = b/(rN)；Ta = Ts + Tr + Tt。
|
||
- **考查方式**：计算题。
|
||
- **可能的题目**：
|
||
|
||
**例题1**：磁盘转速7200 r/m，每道100扇区，每道8192字节，跨越一道需0.5ms，启动时间忽略。读取一个扇区的时间？
|
||
- 解答：
|
||
- r = 7200/60 = 120 r/s
|
||
- Tr = 1/(2×120) = 1/240 s ≈ 4.17 ms
|
||
- Tt = 8192/(120×8192) = 1/120 s ≈ 8.33 ms
|
||
- 平均寻道（需跨越约50道）：Ts = 50×0.5 = 25 ms
|
||
- 总时间 ≈ 25 + 4.17 + 8.33 ≈ 37.5 ms
|
||
|
||
**例题2（PPT原题）**：见9.6.2节，185.4 ms。
|
||
|
||
### 考点11：缓冲技术
|
||
|
||
- **内容**：缓冲目的、Buffering vs Caching、缓冲池管理、单/双/循环缓冲。
|
||
- **考查方式**：填空、简答、PV操作。
|
||
- **可能的题目**：
|
||
1. 缓冲（Buffering）和缓存（Caching）的本质区别？答：缓冲只有一份数据用于速度匹配；缓存可有多个副本，利用局部性提高访问速度。
|
||
2. 公共缓冲 vs 私用缓冲？答：公共缓冲利用率高，私用缓冲简单但利用率低。
|
||
|
||
### 考点12：UNIX缓冲管理操作
|
||
|
||
- **内容**：getblk、bread、breada、bwrite、bawrite、bdwrite、brelse。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. breada函数的作用？答：读主块时同时启动预读下一块（异步预读）。
|
||
2. bdwrite的作用？答：延迟写，标记B_DELWRI，腾出缓冲时才实际写盘。
|
||
|
||
### 考点13：虚拟设备与SPOOLing
|
||
|
||
- **内容**：虚拟设备实现方法、SPOOLing系统组成、JCB内容、作业状态变迁。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. SPOOLing的含义？答：Simultaneous Peripheral Operation On-Line（同时外围设备在线操作）。
|
||
2. 虚拟设备是什么？答：用共享型设备实现的、速度较快数量较多的"独占设备"。
|
||
3. SPOOLing系统主要由哪几部分组成？答：输入井/输出井、输入/输出SPOOLing进程、JCB、通道、SPOOLing程序。
|
||
|
||
### 考点14：RAID级别对比（**必考表格**）
|
||
|
||
- **内容**：RAID 0~5的对比（分条粒度、读写并发、冗余方式）。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. RAID 0 的特点？答：块级分条，无容错，速度最快，空间利用率100%。
|
||
2. RAID 5 相比 RAID 4 的优势？答：RAID 5将校验信息循环分布到所有盘上，消除校验盘瓶颈，读写都可并行（不涉及同盘时）。
|
||
3. RAID 5 至少需要几个盘？答：3个。
|
||
4. RAID 1 空间利用率？答：50%。
|
||
5. RAID 2 和 RAID 3 的区别？答：都按位分条，但 RAID 2 用汉明纠错码（可发现2位错误纠正1位），RAID 3 用单个奇偶校验位（只能纠正1位错）。
|
||
6. RAID 5 故障恢复公式？答：某块 = 其所在组的校验块 XOR 其余所有数据块。
|
||
|
||
### 考点15：硬件RAID vs 软件RAID
|
||
|
||
- **内容**：硬件RAID性能高、价格高；软件RAID便宜但性能差、不能做引导卷、仅支持0/1/5级。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 软件RAID有哪些缺点？答：性能差、不能做引导卷、仅支持0/1/5级、软件兼容性问题、可靠性受软件bug影响。
|
||
2. 软件RAID支持哪些级别？答：通常仅0、1、5。
|
||
|
||
### 考点16：稳定存储器
|
||
|
||
- **内容**：定义、保存策略（写两次）、恢复策略（第二块优先）。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. 恢复时两块内容不同但都无误，应如何处理？答：用第二块覆盖第一块（因为第二块是后写的，应为最新）。
|
||
2. 为什么需要稳定存储器？答：现实中不存在绝对可靠的存储介质，需要冗余策略保证不丢信息。
|
||
|
||
### 考点17：设备驱动的执行流程
|
||
|
||
- **内容**：形成通道程序→设置CAW→启动通道→执行CCW→中断处理。
|
||
- **考查方式**：简答、填空。
|
||
- **可能的题目**：
|
||
1. 设备驱动完成I/O的关键步骤？答：①接收I/O请求形成通道程序；②将首地址送CAW；③启动通道；④通道执行CCW与设备交互；⑤完成后向CPU发中断；⑥CPU处理中断。
|
||
|
||
### 考点18：扇区交错编号原因
|
||
|
||
- **内容**：磁盘旋转时，处理完一个扇区数据的时间，下一扇区可能已转过磁头。
|
||
- **考查方式**：简答。
|
||
- **可能的题目**：
|
||
1. 简述扇区交错编号的必要性。答：磁盘高速旋转，从一个扇区读取到下一个扇区就位时存在时间差，若按物理顺序编号，处理完前一个扇区时下一扇区已转过磁头，需等一整圈才能再读，因此采用交错编号使下一扇区恰好转到磁头下。
|
||
|
||
### 考点19：三种磁盘I/O时间及计算公式
|
||
|
||
- **内容**：Ts = m×n + s（寻道时间）；Tr = 1/(2r)（旋转延迟）；Tt = b/(rN)（传输时间）。
|
||
- **考查方式**：计算题、填空。
|
||
- **可能的题目**：
|
||
1. 平均旋转延迟公式？答：Tr = 1/(2r)，即旋转半周的时间。
|
||
2. 传输时间公式？答：Tt = b/(rN)，b=读写字节数，r=转速（转/秒），N=每磁道字节数。
|
||
|
||
### 考点20：N-step SCAN 与 FSCAN
|
||
|
||
- **内容**：N-step SCAN将请求分成长度为N的子队列，FSCAN用两个队列（服务+请求）。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. N=1的N-step SCAN等价于？答：FCFS。
|
||
2. N很大的N-step SCAN等价于？答：SCAN。
|
||
3. FSCAN的两个队列？答：服务队列和请求队列。
|
||
|
||
---
|
||
|
||
### 三、磁盘调度计算典型例题（综合）
|
||
|
||
**题目**：设磁盘磁道编号0~199，磁头当前位置在53，方向向大编号移动，请求序列为：130, 42, 180, 15, 108, 68, 97。分别使用 FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK 计算**访问顺序、总移动量、平均寻道长度**。
|
||
|
||
**解答总结表**：
|
||
|
||
| 算法 | 访问顺序 | 总移动量 | 平均寻道 |
|
||
|---|---|---|---|
|
||
| FCFS | 53→130→42→180→15→108→68→97 | 630 | 90 |
|
||
| SSTF | 53→42→68→97→108→130→15→180 | 379 | 54.1 |
|
||
| SCAN | 53→68→97→108→130→180→199→0→15→42 | 345 | 34.5 |
|
||
| LOOK | 53→68→97→108→130→180→42→15 | 292 | 36.5 |
|
||
| C-SCAN | 53→68→97→108→130→180→199→0→15→42 | 387 | 38.7 |
|
||
| C-LOOK | 53→68→97→108→130→180→15→42 | 319 | 39.9 |
|
||
|
||
> 注：SCAN包含端点199→0的跳跃；LOOK不到端点；C-SCAN到端点后快速跳回起点；C-LOOK跳回最远请求。
|
||
|
||
**关键考点**：
|
||
- SCAN vs LOOK：SCAN到端点，LOOK到最远请求。
|
||
- C-SCAN vs SCAN：C-SCAN单向扫描，跳回起点后同方向继续。
|
||
- C-LOOK 是 C-SCAN 的改进版。
|
||
- 注意方向：磁头移动方向由题给出，影响服务顺序。 |