Files

e2hang ef7621a1ae New Homework

2026-06-25 00:09:09 +08:00

39 KiB

Raw Permalink Blame History

第九章设备与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）

原理：

CPU向设备控制器发出I/O命令，启动设备。
CPU不断循环查询设备状态寄存器，看是否就绪。
就绪后，CPU逐字节/字地从设备读/写数据到内存。
I/O完成后，CPU继续后续工作。

致命缺点：

CPU与设备串行工作：设备工作时CPU只能空转等待。
浪费大量CPU时间：CPU被反复查询占用。

本质问题：CPU参与了数据搬运的全部过程。

9.3.2 中断驱动方式（Interrupt-driven I/O）

原理：

CPU发出启动命令后，立即返回继续做其他事。
设备准备好数据后，向CPU发中断。
CPU响应中断，进入中断处理程序，读/写数据。
处理完毕后返回原任务。

优点：

CPU与设备并行工作，CPU利用率显著提升。

缺点：

每传输一个字节/字都要中断一次，中断开销大。
设备多时，频繁中断严重影响系统性能（"interrupt storm"）。

9.3.3 DMA方式（Direct Memory Access）

原理：引入DMA控制器，让DMA接管"数据搬运"，CPU只在开始和结束时参与。

完整流程（PPT原文）：

DMA编程：CPU设置DMA控制器（源地址、目标地址、传输字节数），启动设备。
磁盘控制器将数据读入内部缓冲区并校验。
DMA请求：DMA向磁盘控制器发读请求，将内存地址放到地址总线。
数据传输：磁盘控制器将数据传至内存指定单元。
回答：磁盘控制器向DMA发回答。
DMA将地址+1、计数-1，重复②─④。
计数为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流程）：

按CAW取一条CCW。
执行该CCW。
(CAW)+1 → CAW。
判断是否为"通道结束"命令：否则返回①；是则向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 独占型设备的分配与去配

用户使用独占设备的流程：申请 → 使用 → 使用 → … → 使用 → 释放

申请步骤：

根据设备类查SDT表。
P(Sm) 对该类设备的信号量做P操作。
查UCB表，找一空闲设备并分配。

使用步骤：

分配通道（修改CCB）。
I/O传输。
去配通道。

释放步骤：

找SDT对应入口。
查UCB表，去配。
V(Sm)。

9.4.3 共享型设备的分配与去配

共享设备的特征：

不需要"申请-释放"！进程直接使用。
来自文件系统调用，每次读/写一块。
通常经过缓冲（参见9.7）。
通过排队优化（磁盘调度）。

对比：独占设备需要事先申请、事后释放；共享设备随用随开，调度算法决定访问顺序。

9.5 设备驱动

设备驱动是操作系统中专门负责某个设备I/O的代码模块，向上提供统一接口，向下控制硬件。

驱动的工作流程（PPT流程图）：

接收I/O请求 → 形成通道程序（CCW序列）。
将通道程序首地址 → CAW。
启动通道。
通道执行CCW，与设备交互传输数据。
通道完成 → 向CPU发中断。
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 = Simultaneous Peripheral Operations On-Line（同时外围设备在线操作）。

由 SPOOLing程序控制通道完成磁盘与外围设备之间的数据传送。

核心组成：

输入井 / 输出井：磁盘上的存储区。
输入SPOOLing进程 / 输出SPOOLing进程：后台进程。
作业控制块（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 保存操作

将信息写到第一个存储块。
第一个成功后，将相同信息写到第二个存储块。
仅当第二次传输也成功时，整个保存操作完成。

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 的改进版。
注意方向：磁头移动方向由题给出，影响服务顺序。

39 KiB Raw Permalink Blame History Unescape Escape

第九章 设备与I/O管理