第五章：IO管理

一、IO管理概述

1.IO设备

IO设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

按特性分类	特点
人机交互类外部设备	数据传输速度较慢，如鼠标、键盘、打印机等
数据存储设备	数据传输速度较快，如移动硬盘、光盘等
网络通信设备	数据传输速度一般，如调制解调器等网络通信

按信息交换单位分类	特点
块设备	传输速率较高、可寻址（随机读写某个块），如磁盘等数据传输基本单位为块
字符设备	传输速率较慢、不可寻址（在IO时常采用中断驱动的方式），如鼠标、键盘等数据传输基本单位为字符

2.IO控制器

（1）IO控制器功能：

IO设备的机械部件主要用来执行具体的IO操作，如鼠标、键盘的按钮、显示器的LED屏、移动硬盘的磁臂、
IO设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

CPU无法直接控制IO设备的机械部件，因此需要电子部件作为CPU和机械部分之间的中介，实现CPU对设备的控制。

该电子部件就是IO控制器（设备控制器），CPU可控制IO控制器从而实现对IO设备机械部件的控制。

（2）IO控制器组成：

1个IO控制器可能会对应多个设备。
数据寄存器、控制寄存器、状态寄存器可能会有多个，其这些寄存器都要有相应的地址才能方便CPU操作。
寄存器占用内存地址的一部分，则称为内存映像IO；寄存器占用IO专用地址，则称为寄存器独立编址。

3.IO控制方式

（1）程序直接控制：

CPU干预的频率：非常频繁，IO操作开始前后都需要CPU介入，并且在等待IO完成的过程中CPU需要不断地轮询检查。
数据传送单位：每次读写一个字
数据的流向：内存、CPU寄存器、IO设备
优点：实现简单，在读写指令之后加上实现循环检查的一系列指令即可（程序直接控制）。
缺点：CPU和IO设备只能串行工作，CPU需要一直轮询检查导致长期处于忙等状态，CPU利用率较低。

（2）中断驱动控制：

在程序直接控制的基础上引入中断机制，由于IO设备速度很慢，可将等待IO的进程阻塞先切换到别的进程执行。

当IO完成后控制器会向CPU发出一个中断信号，CPU检测到中断信号后会保存当前进程的运行环境信息，转向执行中断处理程序。

CPU干预的频率：干预频率降低，IO操作开始前后都需要CPU介入，并且在等待IO完成的过程中CPU可以切换到其他进程。
数据传送单位：每次读写一个字
数据的流向：内存、CPU寄存器、IO设备
优点：在中断驱动方式中，IO控制器会通过中断信号主动报告IO已完成，CPU不再需要不停的轮询，CPU和IO设备可并行工作。
缺点：每个字在IO设备与内存之间的传输都需要经过CPU，而频繁的中断处理会消耗掉较多的CPU时间。

（3）DMA控制：

DMA直接存储器存取，Direct Memory Access主要用于块设备的IO控制，主要改进包括：

主要改进
1.数据的传送单位为块，不再以字为单位传输数据。
2.数据的流向从内存直接放入设备，不再需要CPU寄存器作为中间传输
3.仅在传送一个/多个数据块的开始和结束时，才需要CPU干预

CPU干预的频率：CPU介入频率进一步降低，仅在传送一个或多个数据块的开始和结束时，才需要CPU的干预。
数据传送单位：每次读写一个或多个块（每次读写只能是连续的多个块，读入内存后在内存中也必须是连续的）
数据的流向：内存、IO设备
优点：数据传输以块为单位，数据传输不需要经过CPU可直接写入内存，数据传输效率进一步提升。
缺点：CPU每发出一条IO指令，只能读写一个或多个连续的数据块（离散的数据块需要CPU发出多条指令，进行多次中断处理）。

（4）通道控制：

通道是一种硬件设备（低配版的CPU），可以识别并执行一系列的通道指令。

与CPU相比通道可以执行的指令单一，并且通道程序存放在主机内存中（通道与CPU共享内存）。

CPU干预的频率：极低，通道会根据CPU指示执行对应的通道程序，只有完成一组数据块读写后才发出中断信号，请求CPU干预
数据传送单位：每次读写一组数据块
数据的流向（在通道的控制下进行）：内存、IO设备
优点：CPU、通道、IO设备可并行工作，资源利用率特别高
缺点：实现复杂并需要专门的硬件通道的支持

4.IO软件层次

设备独立性软件又称设备无关性软件，与设备的硬件特性无关的功能几乎都在这一层完成。

设备独立性软件功能：

向上层提供统一的调用接口，如read/write系统调用
实现设备的保护功能（原理与文件保护类似）
对设备的错误进行处理（非重点）
设备的分配与回收
数据缓冲区的管理（屏蔽设备之间数据交换单位大小和传输速度的差异）
建立逻辑设备名到物理设备名的映射关系，根据设备的类型选择调用相应的驱动程序

5.IO与设备驱动应用程序接口

（1）IO应用程序接口：

阻塞IO：应用程序发出IO系统调用，进程需要转换为阻塞态进行等待，例如字符设备接口（从键盘读入一个字符get）
非阻塞IO：应用程序发出IO系统调用，系统调用可迅速返回进程无需阻塞等待，例如块设备接口（往磁盘写数据write）

（2）设备应用程序接口：

二、设备独立性软件

IO核心子系统要实现的功能就是IO软件层次中间三层要实现的功能，

主要包括IO调度、设备保护、假脱机技术SPOOLing技术、设备分配与回收、缓冲区管理（缓冲与高速缓存）

1.假脱机技术

（1）脱机技术原理：

脱机技术：脱离主机的控制进行的输入输出操作

脱机技术缓解了CPU与IO设备的速度矛盾，即使CPU忙碌也可提前将数据输入磁带，即使慢速输出设备忙碌也可提前将数据输出磁带。

基于脱机技术发明了SPOOLing假脱机技术，是用软件的方式模拟脱机技术，SPOOLing系统的组成如下：

注：要实现SPOOLing技术必须要有多道程序技术的支持，系统会建立输入进程和输出进程。

（2）脱机技术案例：

SPOOLing技术可将独占式打印机改造称为共享式打印机，实现共享打印机：

当多个用户进程提出输出打印的请求时，系统会答应它们的请求但是并不会真正把打印机分配给他们，

而是由假脱机管理进程为每个进程做两件事：

在磁盘输出井中为进程申请一个空闲缓冲区（缓冲区在磁盘上非内存），并将要打印的数据输入其中
为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（用于说明用户的打印数据存放位置等信息），再将该表挂到假脱机文件队列上。
当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，根据表中的要求打印的数据从输出井传输到输出缓冲区，最后输出到打印机进行打印，用这种方式可依次处理完全部的打印任务。

虽然系统中只有一台打印机，但是当每个进程提出的打印请求时，系统都会在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户都觉得自己在独占一台打印机，从而实现对打印机的共享。即SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，从而改造成共享打印机。

2.设备的分配与回收

（1）设备分配方式：

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏了请求和保持条件，不会发生死锁）
动态分配：进程运行的过程中动态申请设备资源
安全分配方式：为进程分配一个设备后就将进程阻塞，本次IO完成之后才会将进程唤醒（CPU和IO设备只能串行工作、不会死锁）
不安全分配方式：一个进程可以同时使用多个设备（进程的CPU计算任务与IO任务可以并行处理快速推进，有可能发生死锁）

（2）设备分配的步骤：

==设备分配数据结构==：

==设备分配步骤==：

根据进程请求的物理设备名查找SDT（物理设备名是进程请求分配设备时提供的参数）
根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程
根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

（3）设备分配步骤改进：

改进：建立逻辑设备名与物理设备名的映射机制（利用逻辑设备表LUT），用户编程时只需提供逻辑设备名。

==设备分配步骤==：

根据进程请求的逻辑设备名查找SDT（用户编程时提供的逻辑设备名其实就是设备类型）
查找SDT找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备LUT中新增一个表项。
根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

3.缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可以利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高、容量小，如存储器管理中使用的联想寄存器（快表），由于对页表的访问频率极高因此使用。
更多的情况是使用内存作为缓冲区，设备独立性软件的缓冲区管理就是组织管理这些缓冲区。

缓冲区的作用：

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

（1）单缓冲策略：

假设某用户进程请求某种设备读入若干块的数据，

若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若没有特别说明一个缓冲区大小就是一个块）

总结：采用单缓冲策略，处理一块数据平均耗时Max(C, T)+M

（2）双缓冲策略：

假设某用户进程请求某种设备读入若干块的数据，

若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若没有特别说明一个缓冲区大小就是一个块）

总结：采用双缓冲策略，处理一个数据块的平均耗时为Max(T, C+M)

（3）单/双缓冲在通信时的区别：

两台机器之间进行通信时，可以配置缓冲区用于数据的发送和接受：

若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。
若两个相互通信的机器只设置双缓冲区，在任一时刻只能实现数据的双向传输。

（4）循环缓冲区策略：

将多个大小相等的缓冲区连接成一个循环队列，橙色表示已充满数据的缓冲区，绿色表示空缓冲区：

（5）缓冲池策略：

缓冲池有系统中共用的缓冲区组成，

缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。

缓冲区按实际运算中扮演的功能可以分为：用于收容输入数据的工作缓冲区hin、用于提取输入数据的工作缓冲区sin、用于收容输出数据的工作换从区hout、用于提取输出数据的工作缓冲区sout。

三、磁盘与固态硬盘

1.磁盘结构

==盘面与柱面==：

==磁盘、磁道、扇区==：

磁盘表面由磁性物质组成可以用来记录二进制数据，磁盘的盘面被划分成一个个磁道，一个圈就是一个独立的磁道。

磁道又被划分成为一个个扇区，每一个扇区就是一个磁盘块（各个扇区存放的数据量相同）。

注意：最内侧磁道上的扇区面积最小，因此数据密度最大。

==磁盘读写的过程==：

根据磁盘物理地址（柱面号，扇面号，扇区号）读取任意一个磁块：

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

2.磁盘调度算法：

（1）磁盘读写耗费的时间：

一次磁盘读写操作需要花费的时间包括：寻找时间、延迟时间与传输时间：

==寻道时间Ts==：在读/写数据前，将磁头移动到指定磁道所花的时间。

启动磁头臂是需要时间的，假设时间消耗为s
移动磁头也是需要时间的，假设磁头匀速移动每跨越一个磁道耗时为m，共需要跨越n条磁道
则寻道时间Ts = s + m * n

==延迟时间T_R==：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。

设磁盘转速为r（单位：r/s、r/min）
则平均所需的延迟时间Tr = (1/2) * (1/r) = 1/(2r)

注意：1/r为磁盘转一圈所花费的时间，找到目标扇区平均需要转半圈，因此需要乘1/2。

==传输时间Tt==：从磁盘读出 or 向磁盘写入数据所经历的时间，

假设磁盘转速为 r，此次读/写的字节数为b，每个磁道上的字节数为N。
则传输时间Tt = (1/r) * (b/N) = b/(rN)

==所以总的平均存取时间==：Ta = Ts + 1/2r + b/(rN)

注意：可以发现延迟时间和传输时间都与磁盘转速线性相关（转速为硬件固有属性），操作系统磁盘调度算法只能影响寻道时间。

（2）先来先服务（FCFS）

根据进程请求访问磁盘的先后顺序进行调度：

优点：非常公平，如果请求访问的磁道比较集中，算法性能还算过得去。
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间很长。

（3）最短寻找时间（SSTF）

SSTF算法优先处理与当前磁头最接近的磁道，可以保证每次的寻道时间最短（但总的寻道时间不一定最短，贪心思想）

优点：性能较好，平均寻道时间短
缺点：可能产生饥饿现象（特殊情况下，某些磁道得不到服务）

（4）扫描算法（SCAN）

为了防止出现SSTF出现的饥饿问题，提出扫描算法：只有磁头移动到最外侧磁道的时候才能向内移动，移动到最内侧时才能向外移动。

由于磁头移动的方式很像电梯，因此扫描算法也叫电梯算法。

优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
缺点：只有到达最边上的磁道时才能改变磁头移动的方向。SCAN算法对于各位置磁道的响应频率不平均。

（5）LOOK调度算法：

LOOK调度算法解决了只有到达最边上磁道时，才能改变移动的方向的缺点。（如果在磁头移动方向上没有请求，则立即改变磁头方向）

优点：相比与SCAN算法，不需要不需要每次都移动到最外侧or内侧才改变磁头方向，使寻道时间进一步缩短。

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

C-SCAN算法解决了SCAN算法对于各位置磁道的响应频率不平均的问题。

其规定了只有磁头朝某个特定方向移动时，才能处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

优点：相比与SCAN算法，对于各个位置磁道的响应频率很平均。
缺点：只有到达最边上的磁道时才能改变磁头移动的方向，相比SCAN算法平均寻道时间更长。

（7）C-LOOK算法：

C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动的方向，并且磁头返回时不一定需要返回到最边缘的磁道上。

C-LOOK算法解决了这个问题，如果磁头移动方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

优点：比起C-SCAN算法不需要每次都移动到最外侧or最内侧才改变磁头方向，使寻道时间进一步缩短。

3.磁盘管理

（1）引导块：

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的。

（2）磁盘初始化：

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

（3）坏块的管理：

对于简单的磁盘：在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，如在FAT表上标明。该处理方式中坏块对操作系统透明。
对于复杂的磁盘：磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表，在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些备用扇区用于替换坏块。该处理方式中坏块对操作系统透明。