【操作系统】第五章：设备管理（下）

本篇笔记课程来源：王道计算机考研 操作系统

接上节：【操作系统】第五章：设备管理（上）

七、假脱机技术（SPOOLing技术）

• 假脱机技术，又称 SPOOLing 技术，是用软件的方式模拟脱机技术。因此在用户软件层实现。
• SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

1. 脱机技术

• 脱机输入 / 输出技术：脱离主机的控制进行的输入 / 输出操作。
• 手工操作阶段：主机主要从 IO 设备获得数据，由于设备速度慢，主机速度快，人机速度矛盾明显，主机要浪费很多时间来等待设备。
• 脱机技术优点：
  1. 缓解了 CPU 与慢速 IO 设备的速度矛盾，实现预输入、缓输出。
  2. 即使 CPU 在忙碌，也可以提前将数据输入到磁带；
  3. 即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

2. 输入井和输出井

• 输入井和输出井：是系统在磁盘上开辟出的两个存储区域。
• 输入井：模拟脱机输入时的磁带，用于收容 IO 设备输入的数据
• 输出井：模拟脱机输入时的磁带，用于收容用户进程输出的数据

3. 输入进程和输出进程

• 要实现 SPOOLing 技术，必须要有多道程序技术的支持。系统会建立 “输入进程” 和 “输出进程”
• 输入进程：模拟脱机输入时的外围控制机
• 输出进程：模拟脱机输出时的外围控制机

4. 输入缓冲区和输出缓冲区

• 操作系统会在系统中开辟输入缓冲区和输出缓冲区，作为输入输出时的中转站
• 输入缓冲区：在输入进程的控制下，输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中。
• 输出缓冲区：在输出进程的控制下，输出缓冲区用于暂存从输出井送来的数据，之后再传送给输出设备上。

5. 共享打印机原理分析

• 独占式设备：只允许各个进程串行使用的设备。
• 共享设备：允许多个进程 “同时” 使用的设备（宏观上同时使用，微观上可能是交替使用）。
• 共享打印机：使用 SPOOLing 技术实现，当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
  1. 在磁盘输出井为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中；
  2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。
• 当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。

八、设备的分配与回收

• 在设备独立性软件层实现。

1. 设备分配时应考虑的因素

1. 设备固有属性：独占设备、共享设备、虚拟设备
   • 独占设备：一个时段只能分配给一个进程（如打印机）
   • 共享设备：可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用
   • 虚拟设备：采用 SPOOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用
2. 设备分配算法：先来先服务、高优先级优先、短任务优先
3. 设备分配的安全性：安全分配方式
   • 安全分配方式
     • 为进程分配一个设备后就将进程阻塞，本次 IO 完成后才将进程唤醒。即 一个时段内每个进程只能使用一个设备
     • 优点：破坏了请求和保持条件，不会死锁
     • 缺点：对于一个进程来说，CPU 和 IO 设备只能串行工作
   • 不安全分配方式
     • 进程发出 IO 请求后，系统为其分配 IO 设备，进程可继续执行，之后还可以发出新的 IO 请求。只有某个 IO 请求得不到满足时才将进程阻塞。即 一个进程可以使用多个设备
     • 优点：进程的计算任务和 IO 任务可以并行处理，使进程迅速推进
     • 缺点：有可能发生死锁

2. 静态分配和动态分配

• 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏“请求和保持”条件，不会发生死锁）
• 动态分配：进程运行过程中动态申请设备资源。

3. 设备分配管理中的数据结构

• 设备、控制器、通道 之间的关系： 一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。
  
• 设备控制表（DCT）：系统为每个设备配置一张 DCT，用于记录设备情况：
  • 设备类型：如打印机、扫描仪等
  • 设备标识符：物理设备名，系统中的每个设备的物理设备名唯一
  • 设备状态：忙碌 / 空闲 / 故障 等
  • 指向控制器表的指针：每个设备由一个控制器控制，该指针可找到相应控制器的信息
  • 重复执行次数或时间：当重复执行多次 IO 操作后仍不成功，才认为此次 IO 失败
  • 设备队列的队首指针：指向正在等待该设备的进程队列（由进程 PCB 组成队列）
• 控制器控制表（COCT）：每个设备控制器都会对应一张 COCT，操作系统根据 COCT 的信息对控制器进行操作和管理：
  • 控制器标识符：各个控制器的唯一 ID
  • 控制器状态：忙碌 / 空闲 / 故障 等
  • 指向通道表的指针：每个控制器由一个通道控制，该指针可找到相应通道的信息
  • 控制器队列的队首指针、队尾指针：指向正在等待该控制器的进程队列
• 通道控制表（CHCT）：每个通道都会对应一张 CHCT。操作系统根据 CHCT 的信息对通道进行操作和管理。
  • 通道标识符：各个通道的唯一 ID
  • 通道状态：忙碌 / 空闲 / 故障 等
  • 与通道链接的控制器表首址：可通过该指针找到该通道管理的所有控制器相关信息（COCT）
  • 通道队列的队首指针、队尾指针：指向正在等待该通道的进程队列
• 系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。每个表目记录设备的设备类型、设备标识符、DCT、驱动程序入口。

4. 设备分配的步骤

1. 根据进程请求的物理设备名查找 SDT（系统设备表）
2. 根据 SDT（系统设备表） 找到 DCT（设备控制表），若设备忙碌则将进程 PCB 挂到设备等待队列，不忙碌则将设备分配给进程
3. 根据 DCT（设备控制表）找到 COCT（控制器控制表），若控制器忙碌则将进程 PCB 挂到控制器等待队列，不忙碌则将控制器分配给进程
4. 根据 COCT（控制器控制表）找到 CHCT（通道控制表），若通道忙碌则将进程 PCB 挂到通道等待队列，不忙碌则将通道分配给进程

• 只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动 IO 设备进行数据传送
• 缺点：
  1. 用户编程时必须使用物理设备名，底层细节对用户不透明，不方便编程
  2. 若换了一个物理设备，则程序无法允许
  3. 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

5. 设备分配步骤的改进

• 改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需要提供逻辑设备名
• 步骤：
  1. 根据进程请求的逻辑设备名查找 SDT （系统设备表），用户编程时提供的逻辑设备名就是设备类型
  2. 查找 SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项
  3. 三四步 和前面一样
• 逻辑设备表（LUT）建立了逻辑设备名和物理设备名之间的映射关系。
• 如果用户进程通过相同的逻辑设备名请求使用设备，则操作系统通过 LUT 即可知道用户进程实际要使用的是哪个物理设备，并且也能知道该设备的驱动程序入口地址。

九、缓冲区管理

1. 缓冲区概念

• 缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
  • 使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如快表）
  • 一般情况下，更多的是利用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织管理好这些缓冲区。

2. 缓冲区作用

1. 缓和 CPU 与 IO 设备之间速度不匹配的矛盾
2. 减少对 CPU 的中断频率，放宽对 CPU 中断相应时间的限制
3. 解决数据粒度不匹配的问题
4. 提高 CPU 与 IO 设备之间的并行性

3. 单缓冲

• 单缓冲：假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（一个缓冲区的大小一般就是一个块）
• 注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
• 设 T 为数据从设备到缓冲区的时间，C 为 CPU 处理时间，M 为数据从缓冲区到工作区（内存）的时间，则处理一块数据平均耗时：$$平均耗时：Max(C,T)+M$$
• 若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。

4. 双缓冲

• 双缓冲：假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区
• 采用双缓冲策略，处理一个数据块的平均耗时为$$平均耗时：Max(T,C+M)$$
• 若两个相互连通的机器设置双缓冲区，在同一时刻可以实现双向的数据传输。

5. 循环缓冲区

• 将多个大小相等的缓冲区链接成一个循环队列。
• 系统会定义两个指针：
  1. in 指针：指向下一个可以冲入数据的空缓冲区
  2. out 指针：指向下一个可以取出数据的满缓冲区

6. 缓冲池

• 缓冲池：由系统中共用的缓冲区组成。
• 这些缓冲区按使用状况可以分为
  1. 空缓存队列
  2. 装满输入数据的缓冲队列（输入队列）
  3. 装满输出数据的缓冲队列（输出队列）
• 根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：
  1. 用于收容输入数据的工作缓冲区（hin）
  2. 用于提取输入数据的工作缓冲区（sin）
  3. 用于收容输出数据的工作缓冲区（hout）
  4. 用于提取输出数据的工作缓冲区（sout）
• 输入输出步骤：
  1. 输入进程请求输入数据：从空缓冲队列中取出一块作为收容输入数据的工作缓冲区（hin）。充满数据后将缓冲区挂到输入队列队尾
  2. 计算进程想要取得一块输入数据：从输入队列中取得一块充满输入数据的缓冲区作为提取输入数据的工作缓冲区（sin）。缓冲区读空后挂到空缓冲区队列
  3. 计算进程想要将准备好的数据冲入缓冲区：从空缓冲队列中取出一块作为收容输出数据的工作缓冲区（hout）。数据充满后将缓冲区挂到输出队列队尾
  4. 输出进程请求输出数据：从输出队列中取得一块冲满输出数据的缓冲区作为提取输出数据的工作缓冲区（sout）。缓冲区读空后挂到空缓冲区队列

十、磁盘的结构

1. 磁盘、磁道、扇区

• 磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。
• 磁盘的盘面被划分为一 “圈圈” 磁道。
• 一个磁道被划分为一个个扇区，每个扇区就是一个磁盘块。各个扇区存放的数据量相同（如1KB），因此最内侧磁道上的扇区面积最小，数据量最大。
• 磁盘分类，根据磁头是否可移动分为：
  1. 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道。
  2. 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头。
• 磁盘分类，根据盘片是否可更换分为：
  1. 盘片可以更换的称为可换盘磁盘
  2. 盘片不可更换的称为固定盘磁盘

2.盘面、柱面

• 一个盘片可能会有两个盘面
• 每个磁盘对应一个磁头
• 所有的磁头都是连在同一个磁臂上的，因此所有磁头只能 “共进退”
• 所有盘面中相对位置相同的磁道组成柱面
• 可用磁盘的物理地址：（柱面号，盘面号，扇区号）定位任意一个磁盘块。

3. 根据地址读取 “块”

1. 根据柱面号移动磁臂，让磁头指向指定柱面
2. 激活指定盘面对应的磁头
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对应扇区的读 / 写。

十一、磁盘调度算法

1. 一次磁盘读 / 写操作需要的时间

• 寻找时间（寻道时间）$T_s$：在读 / 写数据前，将磁头移动到指定磁道所花的时间。
  1. 启动磁头臂耗时为 s；
  2. 移动磁头，假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。
  3. 则：寻道时间 $T_s=s+m\times n$
• 延迟时间 $T_R$：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。
  1. 设磁盘转速为 r（单位：转/ 秒，或转 / 分）
  2. 转一圈需要的时间：$T_R=\frac{1}{r}$
  3. 则平均所需的延迟时间 $T_R=\frac{1}{2}\times \frac{1}{r}=\frac{1}{2r}$
• 传输时间$T_t$：从磁盘读出或向磁盘写入数据所经历的时间。
  1. 设磁盘转速为 r，此次读 / 写的字节数为 b，每个磁道上的字节数为 N；
  2. 则传输时间 $T_t=\frac{1}{r}\times \frac{b}{N}=\frac{b}{rN}$
• 总的平均存取时间：$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$
• 延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。

2. 先来先服务算法（FCFS）

• 算法：根据进程请求访问磁盘的先后顺序进行调度。
• 优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过得去。
• 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，性能很差，寻道时间长。

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 45+3+19+21+72+70+10+112+146=498个磁道
• 平均寻道长度：响应一个请求平均需要移动 498/9=55.9 个磁道

3. 最短寻找时间优先（SSTF）

• 算法：优先处理的磁道是与当前磁头最近的磁道。
• 可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
• 优点：性能较好，平均寻道时间短
• 缺点：可能产生饥饿现象，磁头可能在一个小区域内来回移动

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (100-18)+(184-18)=248 个磁道
• 平均寻道长度：响应一个请求平均需要移动 248/9=27.5 个磁道

4. 扫描算法（SCAN）

• 由于磁头移动的方式很想电梯，因此也成为 电梯算法。
• 算法：对 SSTF 算法的改进，只有磁头移动到最外侧磁道的时候才往内移动，移动到最内侧磁道的时候才往外移动。
• 优点：性能较好，平均寻道时间最短，不会产生饥饿现象
• 缺点：
  1. 只有到达最边上的磁道时才能改变磁头移动方向
  2. 对于各个位置磁道的响应频率不平均

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100)+(200-18)=282 个磁道
• 平均寻道长度：响应一个请求平均需要移动 282/9=31.3 个磁道

5. LOOK 调度算法

• 算法：对 SCAN 算法（针对第一个缺点）的改进，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动变观察，因此叫 LOOK）
• 优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (184-100)+(184-18)=250 个磁道
• 平均寻道长度：响应一个请求平均需要移动 250/9=27.5 个磁道

6. 循环扫描算法（C-SCAN）

• 算法：对 SCAN 算法（针对第二个缺点）的改进，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
• 优点：比起 SCAN 来，对于各个位置磁道的响应频率很平均
• 缺点：只有到达最边上的磁道时才能改变磁头移动方向。比起 SCAN 算法平均寻道时间更长。

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100)+(200-0)+(90-0)=390 个磁道
• 平均寻道长度：响应一个请求平均需要移动 390/9=43.3 个磁道

7. C-LOOK 调度算法

• 算法：对 C-SCAN 算法的改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
• 优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (184-100)+(184-18)+(90-18)=322 个磁道
• 平均寻道长度：响应一个请求平均需要移动 322/9=35.8 个磁道

十二、减少磁盘延迟时间的方法

• 延迟时间概念
  • 延迟时间：将目标扇区转到磁头下面所花的时间
  • 磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间。
• 方法一：交替编号 —— 让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
• 方法二：错位命令 —— 让相邻盘面的扇区编号 “错位”。与交替编号的原理相同。
• 读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构：在读取地址连续的磁盘块时，不需要移动磁头，可以减少磁头移动消耗的时间。

十三、磁盘的管理

1. 磁盘初始化

1. 进行 低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。
   • 一个扇区通常分为头、数据区域（如512B大小）、尾三个部分组成。
   • 管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验山区中的数据是否发生错误）
2. 将磁盘分区，每个分区由若干柱面组成（即分为 C、D、E盘）
3. 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表等）

2. 引导块

• 计算机开机时需要进行一系列初始化的工作，这些初始化工作时通过执行初始化程序（自举程序）完成的。
  • 初始化程序（自举程序）将很小一部分存放在 ROM 中，ROM 中的数据在出厂时就写入了，并且以后不能再修改。
  • 完整的自举程序放在磁盘的启动块（即引导块 / 启动分区）上，启动块位于磁盘的固定位置。
• 开机时计算机先运行 “自举装入程序”，通过执行该程序就可找到引导块，并将完整的 “自举程序” 读入内存，完成初始化
• 拥有启动分区的磁盘称为启动磁盘或系统磁盘（如 C盘）

3. 坏块的管理

• 坏块：坏了、无法正常使用的扇区就是坏块。
• 这属于硬件故障，操作系统无法修复。应该把坏块标记出来，一面错误地使用到它。
• 对于简单的磁盘，可以在逻辑格式化时对整个磁盘进行坏块检查，标明哪些扇区是坏扇区（如：在 FAT 表上标明），坏块对操作系统不透明
• 对于复杂的洗盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时九江坏块链进行初始化。会保留一些 “备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

十四、固态硬盘 SSD

• 原理：基于闪存技术（Flash Memory），属于电可擦除 ROM，即 EEPROM
• 组成
  1. 闪存翻译层：负责翻译逻辑块号，找到对应页（Page）
  2. 存储介质：多个闪存芯片（Flash Chip），每个芯片包含多个块（block），每个块包含多个页（page）
• 读写性能特性
  • 以页（page）为单位读 / 写 —— 相当于磁盘的扇区
  • 以块（block）为单位擦除，擦干净的块，其中的每页都可以写一次，读无限次
  • 支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址
  • 读快、写慢。要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的（擦除过的）块中，再写入新的页
• 与机械硬盘相比的特点
  1. SSD 读写速度快，随机访问性能高，用电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
  2. SSD 安静无噪音、耐摔抗震、能耗低、造假更贵
  3. SSD 的一个块被擦除次数过多（重复写同一个块）可能会坏掉，机械硬盘的扇区不会因为写的次数太多而坏掉
• 磨损均衡技术
  • 思想：将擦除平均分布在各个块上，以提升使用寿命
  • 动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块
  • 静态磨损均衡：SSD 监测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务。