考频地图
本章与组成原理第 7 章(输入输出系统)高度重叠:中断方式和 DMA 方式两科都考,可以对照复习。磁盘调度是送分题,一定要拿满。
| 考点 | 考频 | 题型 | 必须会的动作 |
|---|---|---|---|
| 四种 I/O 控制方式 | ★★★★☆ | 选择 / 计算 | 对比 CPU 干预频率,算 CPU 占用百分比 |
| I/O 软件层次 | ★★★★☆ | 选择 | 判断某个动作由哪一层完成 |
| 缓冲 | ★★★☆☆ | 选择 / 计算 | 单缓冲、双缓冲处理一块数据的时间 |
| 设备分配与 SPOOLing | ★★★☆☆ | 选择 | SPOOLing 的组成和作用 |
| 磁盘访问时间 | ★★★★☆ | 计算 | 寻道 + 旋转延迟 + 传输 |
| 磁盘调度算法 | ★★★★★ | 计算 | 写出服务顺序,算总移动磁道数 |
I/O 设备与控制方式
一、设备分类
| 分类依据 | 类别 | 例子 |
|---|---|---|
| 信息交换单位 | 块设备:以数据块为单位,可寻址,传输快 字符设备:以字符为单位,不可寻址,常用中断方式 | 磁盘、U 盘 键盘、鼠标、打印机 |
| 传输速率 | 低速 / 中速 / 高速 | 键盘 / 打印机 / 磁盘 |
| 使用特性 | 人机交互类、存储设备、网络通信设备 | 显示器 / 磁盘 / 网卡 |
| 共享属性 | 独占设备、共享设备、虚拟设备 | 打印机 / 磁盘 / SPOOLing 下的打印机 |
二、设备控制器:CPU 和设备之间的“翻译”
CPU 不直接控制机械部件,而是通过读写设备控制器(I/O 接口)中的寄存器来指挥设备:
三、四种 I/O 控制方式
你(CPU)让快递员(设备)送 100 个包裹进屋(内存):
程序查询:你站在门口,每个包裹都盯着等它到,再亲手搬进屋。
中断:你去干别的,每到一个包裹快递员按一次门铃,你过来搬一个。
DMA:你给快递员一把钥匙和“放在客厅哪里”的说明,他自己把 100 个包裹搬进屋,全部搬完按一次门铃。
通道:你雇了个管家(通道),把“这一批 10 车货分别放哪”写成清单交给他,全部办完再告诉你。
| 方式 | CPU 干预频率 | 传送单位 | 数据流向 | CPU 与 I/O 并行? |
|---|---|---|---|---|
| 程序直接控制(轮询) | 极高,全程 | 字 | 设备 → CPU 寄存器 → 内存 | 否 |
| 中断驱动 | 高,每个字一次 | 字 | 设备 → CPU 寄存器 → 内存 | 是 |
| DMA | 中,每块开始、结束 | 块 | 设备 → 内存(不经过 CPU) | 是 |
| 通道 | 低,一组块一次 | 一组块 | 设备 → 内存 | 是 |
DMA 控制器的四个寄存器
| 寄存器 | 作用 |
|---|---|
| 命令 / 状态寄存器 CR | 存 CPU 发来的命令(读 / 写)和设备状态 |
| 内存地址寄存器 MAR | 这次数据要放到内存的哪里(或从哪里取),每传一个字自动 +1 |
| 数据寄存器 DR | 暂存正在传送的数据 |
| 数据计数器 DC | 还剩多少字节没传,减到 0 就发中断 |
通道是一种专门处理 I/O 的处理机,执行由通道指令组成的通道程序(放在内存里)。它与 CPU 共享内存,但没有自己的内存;指令类型单一,只能执行 I/O 相关的操作。
例:中断方式和 DMA 方式各占多少 CPU 时间
注意单位:题目说的 MB 是 2²⁰ 还是 10⁶,按题意。若题目没说明,计算机存储容量一般按 2 的幂,传输率可能按 10 的幂。
- DMA 方式下数据直接在设备和内存之间传送,不经过 CPU;但开始和结束仍要 CPU 处理。
- 中断方式中,数据传送仍要经过 CPU 寄存器。
- DMA 每传一块中断一次,中断方式每传一个字中断一次,不要混。
- 通道程序存放在内存中,由通道执行,不是 CPU 执行。
I/O 软件层次
I/O 软件分层的目的:越往上越通用、越与具体设备无关;越往下越贴近硬件。选择题的固定问法是“某个工作是在哪一层完成的”——把下面这张图和表记熟就行。
| 动作 | 属于哪一层 |
|---|---|
| 把逻辑设备名映射为物理设备名(查逻辑设备表 LUT) | 设备独立性软件 |
| 检查用户是否有权使用该设备 | 设备独立性软件 |
| 缓冲区管理、设备分配与回收 | 设备独立性软件 |
| 计算磁盘数据所在的柱面号、磁头号、扇区号 | 设备驱动程序 |
| 向设备控制器的寄存器写命令、检查设备状态 | 设备驱动程序 |
| I/O 完成后唤醒等待该 I/O 的进程 | 中断处理程序 |
| printf 把数字格式化为字符串 | 用户层 I/O 软件 |
设备独立性(设备无关性):用户程序使用逻辑设备名(如“打印机”)请求设备,而不是具体的物理设备。好处:换了设备不用改程序;系统可以灵活分配同类设备中的任意一台;便于实现 I/O 重定向。逻辑设备名到物理设备名的映射记在逻辑设备表 LUT 中(可以全系统一张,也可以每用户一张)。
- 设备驱动程序与设备相关,不同类型设备有不同的驱动;设备独立性软件与设备无关。
- 驱动程序通常运行在内核态(它要直接操作控制器寄存器)。
- “计算磁盘地址”是驱动做的,“分配缓冲区”是设备独立性软件做的,这两个是最常考的混淆项。
缓冲、设备分配与 SPOOLing
一、为什么要缓冲
缓冲区是内存中的一块区域(也可以是设备里的硬件缓冲),用来暂存数据,缓和 CPU 与 I/O 设备速度不匹配的矛盾;同时减少 CPU 被中断的次数(攒满一块再通知),提高 CPU 与设备的并行性。
计算题模型:从磁盘读一块数据进缓冲区耗时 T;把缓冲区数据传到用户区耗时 M;CPU 处理这块数据耗时 C。T 由设备完成,可以与 CPU 并行;M 和 C 都要占 CPU。另外有两条规则:缓冲区满了才能往外传、空了才能往里写。
| 方案 | 每块用时(稳定后) | 道理 |
|---|---|---|
| 无缓冲 | T + C | 设备直接写用户区;用户区被 CPU 处理时设备不能写,二者串行 |
| 单缓冲 | max(C, T) + M | CPU 处理第 i 块时,设备可同时往缓冲区读第 i+1 块(C 与 T 重叠);但 M 时缓冲区和用户区都被占,不能重叠 |
| 双缓冲 | max(T, C + M) | 设备往缓冲区 A 写时,CPU 可从缓冲区 B 取并处理;设备几乎不停 |
多个缓冲区连成环,输入指针 in 指向下一个空缓冲区,输出指针 out 指向下一个满缓冲区。适合生产与消费速度基本匹配的场景,本质就是第 2 章的“生产者-消费者”。
系统公用的一组缓冲区,组织成三个队列(空缓冲队列、输入队列、输出队列),以及四种工作缓冲区:收容输入 hin、提取输入 sin、收容输出 hout、提取输出 sout。
缓冲 vs 高速缓存(Cache):Cache 存放的是低速设备上某些数据的副本(Cache 里有的,下层一定有);缓冲区存放的是低速设备上数据的拷贝或尚未写入的数据(缓冲区里有的,下层不一定有),是为了解决速度不匹配而不是为了重复访问。
二、设备分配
系统用四张表记录设备、控制器、通道之间的关系。分配一台设备的过程,就是顺着这四张表一路往下“占资源”:
| 考虑因素 | 选项 |
|---|---|
| 设备固有属性 | 独占设备 → 独占式分配;共享设备 → 分时共享;虚拟设备 → 同一时间段可分给多个进程 |
| 分配算法 | 先请求先分配;优先级高者优先 |
| 安全性 | 安全分配:进程发出 I/O 请求后就阻塞,直到 I/O 完成——破坏了“请求并保持”,不会死锁,但 CPU 与 I/O 串行 不安全分配:发出请求后仍可继续运行、继续请求——效率高,但可能死锁 |
三、SPOOLing(假脱机)技术
办公室只有一台打印机。如果谁要打印就把打印机“锁”给谁,别人只能排队干等。SPOOLing 的做法:每个人的打印内容先存到磁盘上的一个文件夹(输出井),交完就走;后台有一个专门的打印进程,从文件夹里按顺序一份份打印。每个人都觉得“我已经打印完了”,打印机被“虚拟”成了人人都有一台。
- 作用:把独占设备改造成逻辑上的共享设备(虚拟设备);提高 I/O 速度(进程与磁盘交互而不是与慢速设备交互);实现虚拟设备功能。
- 前提:需要多道程序技术(输入进程、输出进程要与用户进程并发)和大容量磁盘(做井)。
- 代价:占用磁盘空间;数据真正输出有延迟。
- 输入井、输出井在磁盘上;输入缓冲区、输出缓冲区在内存中。
- SPOOLing 并没有让打印机物理上被多个进程同时使用,而是让每个进程感觉自己有一台。
- SPOOLing 属于用户层 I/O 软件(其实现不需要特殊硬件)。
- 单缓冲公式里 M 不能与 C 重叠:传送 M 时用户区正被写入,CPU 无法同时处理。
磁盘与磁盘调度
一、磁盘的结构
二、读一次磁盘要多久
可以看出:寻道和旋转延迟占了绝大部分,真正传数据的时间很短。旋转延迟由转速决定,OS 无能为力;但寻道时间可以通过合理安排请求顺序来减少——这就是磁盘调度。
三、磁盘调度算法
统一用经典例子:磁头当前在 53 号磁道,正向磁道号增大方向移动,磁道范围 0–199,请求队列 98, 183, 37, 122, 14, 124, 65, 67:
| 算法 | 规则 | 服务顺序 | 总移动 | 特点 |
|---|---|---|---|---|
| FCFS | 按请求到达顺序 | 98, 183, 37, 122, 14, 124, 65, 67 | 640 | 公平;请求分散时性能差 |
| SSTF 最短寻找时间优先 | 每次选离当前磁头最近的 | 65, 67, 37, 14, 98, 122, 124, 183 | 236 | 平均寻道短;会饥饿(远处的请求一直被插队) |
| SCAN(电梯) | 沿当前方向一直走到磁盘端点,再掉头 | 65, 67, 98, 122, 124, 183, (199), 37, 14 | 331 | 不会饥饿;两端磁道被访问的频率不均 |
| LOOK | 同 SCAN,但只走到最远的请求就掉头 | 65, 67, 98, 122, 124, 183, 37, 14 | 299 | SCAN 的改进 |
| C-SCAN 循环扫描 | 只在一个方向上服务;到端点后直接返回另一端(返回途中不服务) | 65, 67, 98, 122, 124, 183, (199 → 0), 14, 37 | 382(含返回 199) | 各磁道等待时间更均匀 |
| C-LOOK | 同 C-SCAN,但只到最远请求,再跳到另一侧最远请求 | 65, 67, 98, 122, 124, 183, (→ 14), 37 | 322(含返回 169) | C-SCAN 的改进 |
口径提示:C-SCAN / C-LOOK 的“返回距离”是否计入总移动,不同教材不一致,以题目说明为准;没说明时一般计入。另外,若题目没说“到端点”,很多题目里的“SCAN”其实按 LOOK 来算(王道口径:“只需移动到最远请求处即可改变方向”也被允许)。读题时看清楚。
四、减少旋转延迟:交替编号与错位命名
五、磁盘的管理
- 磁盘初始化:低级格式化(划分扇区,每个扇区含头、数据区、尾/校验码)→ 分区 → 逻辑格式化(建立文件系统)。
- 引导块:计算机启动时先执行 ROM 中的“自举装入程序”,它从磁盘的引导块(启动分区)读入完整的自举程序。
- 坏块处理:简单磁盘由 FAT 等文件系统标记坏块;复杂磁盘由控制器维护坏块链表,用备用扇区替代(扇区备用 / 扇区转移)。
六、固态硬盘 SSD
基于 NAND 闪存,由闪存翻译层(FTL,负责把逻辑块号映射到物理页)和存储介质组成。一个闪存由若干块组成,每块含若干页。以页为单位读写,以块为单位擦除;页只有在所在块被擦除后才能重新写入。没有机械部件,随机访问快,读快写慢。
闪存的每个块只能擦写有限次数。动态磨损均衡:写入时优先选擦除次数少的新块。静态磨损均衡:后台定期把长期不改的“冷数据”搬到擦写次数多的块上,让擦写次数少的块去承担新写入,更均衡、寿命更长。
- SSTF 会饥饿;SCAN、C-SCAN 不会。SSTF 不一定是最优的(它只看眼前最近)。
- 平均旋转延迟是半圈的时间,不是一圈。
- 磁盘调度只能减少寻道时间,不能减少旋转延迟和传输时间。
- SSD 写之前要先擦除整块,所以写入(特别是小量随机写)比读慢。
真题与自测
一、真题问法
问法 1(分层):“用户程序发出磁盘 I/O 请求后,系统的处理流程是:用户程序 → 系统调用处理程序 → ? → ? → 中断处理程序。”→ 设备独立性软件(系统调用处理程序属于这一层)→ 设备驱动程序。
问法 2(缓冲):“某文件占 10 个磁盘块,读一块到缓冲区 100 μs,缓冲区到用户区 50 μs,CPU 处理一块 50 μs。单缓冲区下读入并处理完该文件需多少时间?”→ 每块 max(50, 100) + 50 = 150,最后一块再加 C:10 × 150 + 50 = 1550 μs。双缓冲:每块 max(100, 100) = 100,总时间 100 × 10 + 50 + 50 = 1100 μs。
问法 3(调度):给出磁头位置、方向、请求队列,求某算法的服务顺序和平均寻道长度。→ 画数轴,一步步写。
问法 4(SPOOLing):“SPOOLing 技术的输入井、输出井位于?”→ 磁盘。“SPOOLing 的主要作用?”→ 把独占设备变为共享设备。
二、折叠自测
1. DMA 方式与中断方式的根本区别是什么?
中断方式每传一个字就中断一次,数据经过 CPU;DMA 方式每传一块才中断一次,数据直接在设备和内存之间传送,不经过 CPU。DMA 的数据传送由 DMA 控制器完成。
2. 计算磁盘的柱面号、磁头号、扇区号是哪一层的工作?
设备驱动程序。它与具体设备相关,负责把上层的逻辑块号转成设备能理解的物理地址并写入控制器寄存器。
3. T = 100,M = 20,C = 60,单缓冲和双缓冲下每块平均用时分别是多少?
单缓冲:max(60, 100) + 20 = 120。双缓冲:max(100, 60 + 20) = 100。
4. SPOOLing 系统由哪几部分组成?需要哪两个前提?
输入井和输出井(磁盘)、输入缓冲区和输出缓冲区(内存)、输入进程和输出进程、井管理程序。前提是多道程序技术和大容量磁盘。
5. 转速 7200 转/分的磁盘,平均旋转延迟是多少?
一圈 60 / 7200 s ≈ 8.33 ms,平均旋转延迟为半圈 ≈ 4.17 ms。
6. 哪种磁盘调度算法可能导致饥饿?为什么?
SSTF。如果磁头附近不断有新请求到来,远处的请求会一直被推后,长时间得不到服务。
7. 磁盘地址为什么用(柱面号, 盘面号, 扇区号)而不是(盘面号, 柱面号, 扇区号)?
让连续的地址尽量落在同一柱面内。读完一个盘面上的一条磁道后,换盘面只需电子切换磁头,不需要移动磁臂,减少了寻道。
8. 设备分配中的“安全分配方式”为什么不会死锁?
进程发出 I/O 请求后立刻阻塞,直到 I/O 完成才能继续运行,因此不可能在占有一个设备的同时再请求另一个设备,破坏了“请求并保持”条件。
三、考前速览
查询每字盯、中断每字报、DMA 每块报、通道一组报。
驱动算地址写寄存器,独立性软件管名字、权限、缓冲、分配。
单缓冲 max(C,T)+M,双缓冲 max(T,C+M)。
SPOOLing:独占变共享,井在磁盘上。
Ta = Ts + 1/(2r) + b/(rN)。
① DMA 开始和结束仍需 CPU。
② 通道程序在内存中,由通道执行。
③ 平均旋转延迟是半圈。
④ SSTF 会饥饿。
⑤ C-SCAN 返回距离是否计入看题目。