Mass-Storage Structure
Disk scheduling
磁盘调度算法（Disk Scheduling Algorithms）是操作系统用于优化磁盘访问顺序的机制，旨在减少磁头移动（寻道时间），提高磁盘I/O效率。以下是常见算法及其详解：
1. 先来先服务（FIFO/First-Come, First-Served）
- 原理：按请求到达的顺序处理。
- 优点：简单、公平。
- 缺点：效率低（可能产生大量不必要的磁头移动）。
- 示例：
请求序列：[35, 10, 40, 5, 20, 45, 15, 65]，磁头初始位置：50
处理顺序：50 → 35 → 10 → 40 → 5 → 20 → 45 → 15 → 65
总寻道距离：15 + 25 + 30 + 35 + 15 + 25 + 30 + 50 = 225（单位：磁道）
2. 最短寻道时间优先（SSTF/Shortest Seek Time First）
- 原理：优先处理离当前磁头位置最近的请求。
- 优点：平均寻道时间较短。
- 缺点：可能导致“饥饿”（远距离请求长期不被处理）。
- 示例：
请求序列同上，初始位置：50
处理顺序：50 → 45 → 40 → 35 → 20 → 15 → 10 → 5 → 65
总寻道距离：5 + 5 + 5 + 15 + 5 + 5 + 5 + 60 = 105
3. 扫描算法（SCAN/Elevator Algorithm）
- 原理：磁头从一端移动到另一端（如从左到右），处理路径上的请求；到达端点后反向移动。
- 优点：公平，无饥饿。
- 缺点：端点附近的请求等待时间较长。
- 示例：
初始位置：50，移动方向：向右（假设磁盘范围 0-100）
处理顺序：50 → 65（端点）→ 45 → 40 → 35 → 20 → 15 → 10 → 5
总寻道距离：15 + 20 + 5 + 5 + 15 + 5 + 5 + 5 = 75
4. 循环扫描算法（C-SCAN/Circular SCAN）
- 原理：单向扫描（如仅向右），到达端点后立即返回起点重新开始。
- 优点：更均匀的等待时间。
- 缺点：返回起点时不做处理，可能浪费时间。
- 示例：
初始位置：50，方向：向右
处理顺序：50 → 65 → 5 → 10 → 15 → 20 → 35 → 40 → 45
总寻道距离：15 + 60（从65到5）+ 5 + 5 + 5 + 15 + 5 + 5 = 115
5. 观察算法（LOOK）
- 原理：改进版SCAN，仅移动到最远请求点后立即返回，无需到达磁盘端点。
- 优点：减少不必要的移动。
- 示例：
初始位置：50，方向：向右
处理顺序：50 → 65（最远请求）→ 45 → 40 → 35 → 20 → 15 → 10 → 5
总寻道距离：15 + 20 + 5 + 5 + 15 + 5 + 5 + 5 = 75
6. 循环观察算法（C-LOOK）
- 原理：改进版C-SCAN，仅移动到最远请求点后返回最近的另一方向请求点。
- 示例：
初始位置：50，方向：向右
处理顺序：50 → 65 → 5 → 10 → 15 → 20 → 35 → 40 → 45
总寻道距离：15 + 60（从65到5）+ 5 + 5 + 5 + 15 + 5 + 5 = 115
对比总结
| 算法 | 平均寻道时间 | 公平性 | 饥饿问题 | 适用场景 |
|---|---|---|---|---|
| FIFO | 高 | 公平 | 无 | 简单场景 |
| SSTF | 低 | 不公平 | 有 | 中等负载 |
| SCAN | 中等 | 公平 | 无 | 高负载 |
| C-SCAN | 中等 | 公平 | 无 | 均匀服务时间要求 |
| LOOK | 低 | 公平 | 无 | 现代系统常用 |
| C-LOOK | 低 | 公平 | 无 | 高吞吐量需求 |
例题：
冗余阵列(RAID)
RAID（Redundant Array of Independent Disks） 是一种通过组合多个物理磁盘来提升存储性能、可靠性和容错能力的技术。 以下是常见 RAID 级别及其核心原理、优缺点和应用场景的详解：
RAID 核心概念
- 条带化（Striping）
将数据分割成块，分散存储在多个磁盘上，提升读写速度（如 RAID 0）。 - 镜像（Mirroring）
数据同时写入多个磁盘，提供冗余（如 RAID 1）。 - 奇偶校验（Parity）
通过校验数据恢复丢失信息，实现容错（如 RAID 5、6）。
常见 RAID 级别对比
| RAID 级别 | 最小磁盘数 | 原理 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|
| RAID 0 | 2 | 数据条带化 | 读写速度最快 | 无冗余，可靠性低 | 高性能需求，临时数据处理 |
| RAID 1 | 2 | 数据镜像 | 高可靠性，快速恢复 | 存储利用率仅50% | 关键数据备份（如系统盘） |
| RAID 5 | 3 | 条带化 + 分布式奇偶校验 | 平衡性能与冗余，存储利用率高 | 单磁盘故障恢复慢 | 中小型数据库、文件服务器 |
| RAID 6 | 4 | 条带化 + 双重奇偶校验 | 允许两磁盘同时故障 | 写入速度较慢，成本高 | 大容量高可靠性存储（如医疗数据） |
| RAID 10 | 4 | RAID 1 + RAID 0（先镜像再条带） | 高性能 + 高可靠性 | 存储利用率仅50% | 高并发事务（如金融数据库） |
详细解析
1. RAID 0（条带化）
- 原理：数据分割为块，交替写入多个磁盘。
- 示例：
写入文件时，文件分块存储到 Disk1 和 Disk2。 - 缺点：任一磁盘故障将导致全部数据丢失。
- 场景：视频编辑、临时缓存。
2. RAID 1（镜像）
- 原理：数据同时写入两个磁盘，互为备份。
- 示例：
Disk1 和 Disk2 存储完全相同的数据。 - 场景：关键系统盘、小型服务器。
3. RAID 5（分布式奇偶校验）
- 原理：数据与奇偶校验信息分散存储在所有磁盘。
- 奇偶校验块（Parity）用于恢复数据。
- 示例：
3 磁盘 RAID 5：数据块 D1、D2 和奇偶校验 P 分布在 Disk1、Disk2、Disk3。
若 Disk1 故障，可通过 D2 和 P 恢复 D1。 - 场景：企业文件共享、中型数据库。
4. RAID 6（双重奇偶校验）
- 原理：使用两组独立的奇偶校验，允许两磁盘故障。
- 示例：
4 磁盘 RAID 6：数据块 D1、D2 和奇偶校验 P、Q 分布在 Disk1-Disk4。 - 场景：高可靠性需求的长期存储。
5. RAID 10（镜像+条带化）
- 原理：先镜像（RAID 1），再条带化（RAID 0）。
- 每组镜像对构成一个逻辑条带。
- 示例：
4 磁盘 RAID 10：Disk1 和 Disk2 镜像，Disk3 和 Disk4 镜像，数据条带化写入两组镜像。 - 场景：高并发、高可靠性的核心数据库。