042-独占&共享设备

独占型外围设备

• 设备独立性：用户指定逻辑设备而非物理设备，避免当物理设备故障时无法继续执行任务

• 设备管理：一类设备一张设备表 & 设备类表

  • 设备类表：设备类|总台数|空闲台数|设备表起始地址

  • 设备表：物理设备名|逻辑设备名|占有设备的进程|分配标志|好/坏标志

• 优点

  • 应用程序与具体物理设备无关（避免“硬编码”）

  • 易于应对故障，提升可靠性

  • 增加分配灵活性，提升资源利用率

分配方式

• 静态分配：运行前申请

  • 优点：避免死锁

  • 缺点：资源利用率低

• 动态分配：随用随申请

  • 优点：资源利用率高

  • 缺点：可能导致死锁（P 使用 A 后要求 B，Q 使用 B 后要求 A）

共享型外围设备

磁盘

CD-ROM 是螺旋式的，磁盘是同心圆的

• 盘片 -> 盘面 -> 磁道 -> 扇区

• 一张盘片两个盘面

• 柱面：不同盘片位于相同位置的磁道

• 簇：相邻的扇区

• 物理块地址

  • 柱面号 + 磁头号 + 扇区号

  • 盘面号 + 磁道号 + 扇区号

• 读写方式：寻道（移臂） -> 旋转 -> 读写

时间计算

以下内容采用 coa 笔记

• 平均访问时间：$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$

  • $b$：传送的字节数，$r$：旋转速率，转/秒，$N$：每磁道的字节数（扇区数和扇区字节数之积）

  • $T_s$ 平均寻道时间

  • $\frac{1}{2r}$ 平均旋转延迟

  • $\frac{b}{rN}$ 实际传送时间 若有数据传输率的数值直接用数据传输率来算 $\frac{b}{N}$可以是传输/磁道的扇区数的比值，也可以是数据大小的比值

  • 要将转速转换为rps：15000rpm=250rps

• 读取多个相邻磁道，只需考虑1次寻道时间，每个磁道都需考虑旋转延迟

移臂调度算法

• 先进先出：移臂距离大，性能不好

• 优先级：与硬件本身无关，操作系统定义

• 后进先出：提高吞吐量，利用局部性，但可能导致饥饿

• 最短寻道时间优先：性能好，但可能导致饥饿

• 扫描

  • C-SCAN 单向扫描：沿一个方向扫描到底，随后回到另一端继续扫描，折返时不提供服务

  • SCAN 双向扫描：沿一个方向扫描到底，折返后扫描到另一端

  • N-step 扫描：将请求分为多组长度为 N 的队列，每次处理一组队列，处理队列时的其他请求加入另一个队列（N=1时退化为 FIFO）

  • FSCAN：将请求分为两组，处理一组时将请求加入另一组，交替处理

• 电梯：不在末端折返，前方无访问请求即可折返，双向扫描

• 旋转调度：优化 I/O 请求的排序，减少旋转圈数

优化数据分布

• 目标：在尽量少的旋转圈数中响应所有请求

• 循环排序：将请求顺着磁盘转动方向排序，节约时间

• 交替排序：计入磁盘处理数据，无法读入的时间段，将连续内容交替排序，降低无法读入时跳过的时间段带来的影响

• 把相邻扇区集中为簇

• 按柱面集中存储数据

计算题

例：磁道上四个物理块 1-4，旋转一周需 20ms，收到四个 I/O 请求，分别为 1、2、3、4

• 顺序为4、3、2、1：$R=0.5 + \frac{1}{4} + 3\cdot\frac{3}{4} = 3$ 周

• 顺序为1、2、3、4：$R=0.5 + \frac{1}{4} + 3\cdot\frac{1}{4} = 1.5$ 周

• 若磁头在3，按4、1、2、3顺序：$R=4\cdot\frac{1}{4} = 1$ 周

• 顺序为1、2、3、4，每读一块后需5ms的额外处理时间：$R=0.5 + \frac{1}{4} + \frac{1}{4} + 3 \cdot (\frac{3}{4}+\frac{1}{4}+\frac{1}{4}) = 4.75$ 周

• 顺序为1、3、2、4，每读一块后需5ms的额外处理时间：$R = 0.5 + 2 \cdot (\frac{1}{4} + \frac{1}{4}) + \frac{1}{4} + 2 \cdot (\frac{1}{4} + \frac{1}{4}) = 3.75$ 周

RAID 技术

• 详见计组 RAID

级别	描述	磁盘数量	种类	数据可用性	大I/O输出传输能力	小I/O请求数据
0	非冗余	$N$	条带化	最低	很高	很高
1	镜像	$2N$	镜像	比2，3，4，5高，比6低	读：比单盘高 写：类似	读：2倍 写：类似
2	海明码冗余	$N+m$	并行存取	高	最高	单盘2倍
3	位交错奇偶校验	$N+1$	并行存取	高	最高	单盘2倍
4	块交错奇偶校验	$N+1$	独立存取	高	读：RAID0 写：低于单盘	读：RAID0 写：显著低于单盘
5	块交错分布式奇偶校验	$N+1$	独立存取	高	读：RAID0 写：低于单盘	读：RAID0 写：显著低于单盘
6	块交错分布式奇偶校验	$N+2$	独立存取	最高	读：RAID0 写：低于RAID 5	读：RAID0 写：低于RAID 5

磁盘 Cache

• 替换策略：LRU LFU