第5章 输入输出管理

5.1 I/O管理概述

5.1.1 I/O设备

IO设备的基本概念和分类.pdf

“I/O”就是“输入/输出”（Input/Output），I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

I/O设备的分类

按使用特性分类

• 人机交互类外部设备：鼠标、键盘、打印机等，数据传输速度慢

• 存储设备：移动硬盘、光盘等，数据传输速度快

• 网络通信设备：调制解调器等，数据传输速度介于二者之间

按传输速率分类

• 低速设备：鼠标、键盘等，传输速率为每秒几个到几百字节

• 中速设备：如激光打印机等，传输速率为每秒数千至上万个字节

• 高速设备：如磁盘等，传输速率为每秒数千字节至千兆字节的设备

按信息交换的单位分类

• 块设备：如磁盘等，数据传输的基本单位是“块”，传输速率较高，可寻址，即对它可随机地读/写任一块，常采用DMA控制方式

• 字符设备：鼠标、键盘等，数据传输的基本单位是字符。传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式

按设备的共享属性分类

• 独占设备：同一时刻只能由一个进程占用的设备。属于临界资源，设置不当可能导致死锁，如：打印机

• 共享设备：同一时间段内允许多个进程同时访问的设备，但同一时刻只能有一个进程访问（可并发不可并行），不会导致死锁，且必须是可寻址、可随机访问的设备，如：磁盘

• 虚拟设备：通过SPOOLing技术将原本独占设备改造为逻辑上的共享设备，并可以把一个物理设备变换为多个对应的逻辑设备。

I/O控制器

联系7.2 I/O接口

IO控制器.pdf

I/O设备由机械部件和电子部件组成：

• 机械部件：负责执行具体I/O操作。如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。

• 电子部件：CPU通过电子部件来间接控制和管理机械部件的执行。通常是一块插入主板扩充槽的印刷电路板。电子部件又称I/O接口、I/O控制器、设备控制器。

I/O控制器的主要功能

7.2.1 I/O接口的功能

• 接收和识别CPU发出的命令：如CPU发来的read/write命令，I/O控制器中会有相应的控制寄存器来存放命令和参数

• 向CPU报告设备的状态：I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌

• 数据交换：I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。

• 地址识别：类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器

I/O控制器的组成

7.2.2 I/O接口的基本结构

• CPU与控制器的接口：用于实现CPU与控制器直接的通信。CPU通过控制线发出命令；通过地址线指明要操作的设备；通过数据线来取出（输入）数据，或放入（输出）数据

• I/O逻辑：负责接收和识别CPU的各种命令，并负责对设备发出命令，实现设备控制功能

• 控制器与设备的接口：用于实现控制器与设备之间的通信

tips：

• 一个I/O控制器可能会对应多个设备；

• 数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址。参考7.2.4 I/O端口及其编址

  • 内存映射I/O：控制器中的寄存器与内存地址统一编址（所有设备的寄存器一起，接着内存编址）

  • 寄存器独立编址：控制器中的寄存器使用单独的地址（每个设备的寄存器编址都从0开始）

    缺点：需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号

5.1.2 I/O控制方式

7.1.2 IO控制方式

IO控制方式.mp4

IO控制方式.pdf

每一个阶段的优点都是解决了上一阶段的最大缺点。总体来说，整个发展过程就是要尽量减少CPU对I/O过程的干预，把CPU从繁杂的I/O控制事务中解脱出来，以便更多地去完成数据处理任务。

程序直接控制方式

7.3.1 程序查询方式

完成一次读写操作的流程：（关键词：轮询）

1. CPU向控制器发出读指令。于是设备启动，并且状态寄存器设为1（未就绪）

2. 轮询检查控制器的状态（其实就是在不断地执行程序的循环，若状态位一直是1，说明设备还没准备好要输入的数据，于是CPU会不断地轮询）

3. 输入设备准备好数据后将数据传给控制器，并报告自身状态

4. 控制器将输入的数据放到数据寄存器中，并将状态改为0（已就绪）

5. CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU的寄存器中，再把CPU寄存器中的内容放入内存

6. 若还要继续读入数据，则CPU继续发出读指令

总结

• CPU干预的频率：很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。

• 数据传送的单位：每次读/写一个字

• 数据的流向：

  • 读操作（数据输入）：I/O设备→CPU→内存

  • 写操作（数据输出）：内存→CPU→I/O设备

  • 每个字的读/写都需要CPU的帮助

• 主要缺点和主要优点

  • 优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”）

  • 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低。

中断驱动方式

中断驱动方式的思想是，允许I/O设备主动打断CPU的运行并请求服务，从而解放CPU

7.3.2 程序中断方式

引入中断机制。由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。

注意：

• CPU会在每个指令周期的末尾检查中断；

• 中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能。

完成一次读/写操作的流程（见右图，关键词：中断）

总结：

• CPU干预的频率：

  • 每次I/O操作开始之前、完成之后需要CPU介入。

  • 等待I/O完成的过程中CPU可以切换到别的进程执行。

• 数据传送的单位：每次读/写一个字

• 数据的流向：

  • 读操作（数据输入）：I/O设备→CPU→内存

  • 写操作（数据输出）：内存→CPU→I/O设备

• 主要缺点和主要优点

  • 优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。

  • 缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。

DMA方式

DMA方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路，彻底解放CPU

7.3.3 DMA方式

与“中断驱动方式”相比，DMA方式（Direct Memory Access，直接存储器存取。主要用于块设备的I/O控制）有这样几个改进：

• 数据的传送单位是“块”。不再是一个字、一个字的传送；

• 数据的流向是从设备直接放入内存，或者从内存直接到设备。不再需要CPU作为“快递小哥”。

• 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

完成一次读/写操作的流程（见上图）

总结

• CPU干预的频率：仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

• 数据传送的单位：每次读/写一个或多个块（注意：每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的）

• 数据的流向（不再需要经过CPU）

  • 读操作（数据输入）：I/O设备→内存

  • 写操作（数据输出）：内存→I/O设备

• 主要缺点和主要优点

  • 优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。

  • 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。

通道控制方式

I/O通道控制方式是DMA方式的发展，它可以进一步减少CPU的干预，即把对一个数据块的读或写为单位的干预，减少为对一组数据块的读或写及有关控制和管理为单位的干预。

通道：又称I/O处理机，一种硬件，可以理解为是“弱鸡版的CPU”。通道可以识别并执行一系列通道指令（与CPU相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道与CPU共享内存）

完成一次读/写操作的流程（见上图)

总结

• CPU干预的频率：极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求CPU干预。

• 数据传送的单位：每次读/写一组数据块

• 数据的流向（在通道的控制下进行）

  • 读操作（数据输入）：I/O设备→内存

  • 写操作（数据输出）：内存→I/O设备

• 主要缺点和主要优点

  • 缺点：实现复杂，需要专门的通道硬件支持

  • 优点：CPU、通道、I/O设备可并行工作，资源利用率很高。

补充：通道的分类

• 字节多路通道：一个字节多路通道可控制多个慢速的设备控制器。以字节为数据传送单位，一段时间内可同时为多个慢速设备服务——适用于大量的低速、中速I/O设备

• 数组选择通道：一个数组选择通道可控制多个高速的设备控制器（如DMA控制器）。以数组（块）为数据传送单位。这种通道一段时间内只能为一个高速设备服务——适用于少量的高速I/O设备

• 数组多路通道：一个数组多路通道可控制多个高速的设备控制器（如DMA控制器）。以数组（块）为数据传送单位。这种通道一段时间万能可同时为多个高速设备服务——适用于大量的高速I/O设备

5.1.3 I/O软件层次结构

IO软件层次结构.pdf

• 操作系统就设备管理模块分为若干个层次，低层次用于屏蔽硬件细节的差异，高层次向用户提供简洁、友善的界面。每一层都利用其下层提供的服务，来完成输入输出功能中的某些子功能，并屏蔽这些功能的细节，向上层提供服务。

• I/O层次结构：用户层软件、设备独立性软件/设备无关软件、设备驱动软件、中断处理程序、硬件

• 硬件即机械部分+电子部分，不属于I/O软件组成层次。

• 2/3/4三层属于操作系统的内核部分，即“I/O系统”，或称“I/O核心子系统”

用户层I/O软件

• 用户层软件用于实现与用户交互的接口，包括库函数和SPOOLing软件等。

  • 用户可调用库函数来使用I/O系统调用，进而对设备操作；

  • SPOOLing可以把独占设备变成共享设备。

	系统调用	库函数
本质	OS内核提供的函数，面向硬件	为方便编程而设计，面向开发
运行状态	内核态	用户态
地址空间	内核空间	用户空间
调用对象	OS内核提供的服务	函数库中的一个程序或函数
调用开销	需要进行上下文切换，开销大	未使用系统调用时开销小
可移植性	依赖于内核，不保证移植性	与系统无关，可移植性好
调用性质	操作系统的一个入口点	与用户程序相联系
常见例子	write、open、close	printf、fopen、fclose

设备独立性软件

5.2.1 与设备无关的软件

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

设备独立性软件的主要功能如下：

• 向上层提供统一的系统调用接口（如read/write系统调用）

• 设备保护：原理类似于文件保护。设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。

• 差错处理：设备独立性软件需要对一些设备的错误进行处理

• 缓冲区管理：缓和CPU和I/O设备的速度差异

• 设备分配与回收：引入逻辑设备名，并实现逻辑设备名到物理设备名之间的转换

• 虚拟设备：将独占设备改造为共享设备，提高设备利用率

• 驱动程序接口：方便用户添加设备驱动程序，更换设备时就无需修改I/O软件

• I/O调度：用某种算法确定一个好的顺序来处理各个I/O请求。如：磁盘调度等

设备驱动程序

• 设备驱动程序用于具体实现系统对设备发出的操作命令，驱动I/O设备工作。

• 对于不同类型的设备，其内部的电子部件和硬件特性也不相同，对设备内部寄存器的设置需要通过不同指令序列来完成，因此不同类型的设备需要不同的驱动程序

• 补充：驱动程序一般会以一个独立进程的方式存在。

中断处理程序

中断处理程序的主要任务是分析中断类型并作出相应的处理，处理时需要先保存中断前的状态，然后转入相应的中断服务程序进行处理，处理完毕后恢复中断前的状态

5.1.4 I/O应用程序接口

输入输出应用程序接口和驱动程序接口.pdf

用户层的应用程序无法用一个统一的系统调用接口来完成所有类型设备的I/O。在I/O系统和主机的接口中，根据设备类型的不同，可以分为字符设备接口、块设备接口和网络设备接口。

字符设备接口

字符设备是以字符为信息交换单位的设备，每次可以交换一个或多个字符，传输速度较低，通常采用中断驱动方式，如键盘、打印机等

字符设备接口用于控制字符设备的输入和输出，提供以下操作：

• 打开和关闭操作：使用字符设备时需要先使用打开操作打开设备。

• get和put操作：向字符设备读/写一个字符。字符设备不可寻址，只能用顺序方式存取

块设备接口

块设备是以数据块为信息交换单位的设备，每次可以交换一个或多个数据块的信息，传输速度较高，且支持对存储的信息进行寻址和随机读写。典型的块设备是磁盘

块设备接口用于控制块设备的输入和输出，提供以下操作：

• read/write系统调用：向块设备的读写指针位置读/写多个字符

• seek系统调用：修改读写指针位置

网络设备接口

现代操作系统都提供面向网络的功能，因此还需要提供相应的网络软件和网络通信接口，使计算机能够通过网络与网络上的其他计算机进行通信或上网浏览

网络设备接口，又称“网络套接字(socket)接口”

• socket 系统调用：创建一个网络套接字，需指明网络协议（如TCP还是UDP）

• bind 系统调用：将套接字绑定到某个本地“端口”

• connect 系统调用：将套接字连接到远程地址

• read/write 系统调用：从套接字读/写数据

阻塞I/O与非阻塞I/O

阻塞I/O与非阻塞I/O的区别主要在于应用程序的调用是否立即返回

• 阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。

  eg：字符设备接口——从键盘读一个字符get

• 非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。

  eg：块设备接口——往磁盘写数据

5.1.6 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.2 设备独立性软件

5.2.1 与设备无关的软件

IO核心子系统.pdf

设备的独立性主要是指用户使用设备的透明性，即用户程序和实际使用的物理设备无关

详见设备独立性软件

5.2.2 高速缓存与缓冲区

缓冲区管理.pdf

缓冲区

• 缓冲区是一块存储区域，用于保存在两个设备之间或在设备和应用程序之间传输的数据。

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

  • 硬件缓冲：由寄存器等专用的硬件实现。使用硬件作为缓冲区成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器（快表），由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）

  • 软件缓冲：操作系统在内存中开辟一个空间来实现。

• 缓冲区管理的主要功能是对系统中的缓冲区进行有效组织，并提供获得和释放缓冲区的手段

• 缓冲区的作用

  • 缓和CPU和I/O设备之间速度不匹配的矛盾

  • 减少对CPU的中断频率，放宽对CPU中断响应时间的限制

  • 解决数据单元大小不匹配的问题。如输出进程每次可以生成一块数据，但I/O设备每次只能输出一个字符

  • 提高CPU与I/O设备之间的并行性

• 缓冲区实现思路：当进程与设备执行数据交换时，先向系统申请一个缓冲区，然后由进程或设备将数据送至缓冲区，等待缓冲区填满或者数据输入完成后，将缓冲区中的数据送给设备或进程。

• 注意：缓冲区为空时才能向缓冲区输入数据；缓冲区的数据填满时，才能从缓冲区输出数据

• 常见的缓冲区技术有：单缓冲、双缓冲、循环缓冲、缓冲池

  • 单缓冲：输入和输出共用一个缓冲区，无法同时输入和输出

  • 双缓冲：未解决输入和输出速度不匹配的问题，效果优先

  • 单缓冲、双缓冲、循环缓冲：均为专用缓冲，利用率不高

  • 缓冲池：属于共享资源，可以使并发进程的I/O效率尽可能高

单缓冲

单缓冲仅使用一个缓冲区，每当用户进程发出I/O请求时，操作系统便在内存的系统中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。

常考题型：计算每处理一块数据平均需要多久？

技巧：假定一个初始状态，分析下次到达相同状态需要多少时间，这就是处理一块数据平均所需时间。

在“单缓冲”题型中，可以假设初始状态为工作区满，缓冲区空。

思路：只有输入和处理可以同时进行，则处理一块数据平均耗时 $\max \{C,T\}+M$ ；处理 $n$ 块数据耗时 $(T+M+C)+(n-1)(\max \{C,T\}+M)$

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

双缓冲

双缓冲使用两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）

双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空

思路：输入可以和传送与处理都能同时进行，而传送和处理不能同时进行，则处理一个数据块的平均耗时为 $\max \{T,C+M\}$ ；处理 $n$ 块数据耗时 $(T+M+C)+(n-1)\max \{T,C+M\}$

若两个相互通信的机器设置双缓冲区，则同一时刻可以实现双向的数据传输。

循环缓冲

循环缓冲将多个大小相等的缓冲区链接成一个循环队列。

• in指针，指向下一个可以存入数据的空缓冲区

• out指针，指向下一个可以取出数据的满缓冲区

缓冲池

单缓冲、双缓冲、循环缓冲都是专用缓冲（一对一的特性），而缓冲池是公用缓冲

• 缓冲池包含了一个数据结构及一组操作函数的管理机制，用于管理大小相等的缓冲区。缓冲池即可用于输入又可用于输出，可被多个进程共享

• 缓冲池的组成：

  • 空缓冲队列：由空缓冲区链成的队列，用于取出空缓冲区来进行写入操作

  • 输入队列：装满输入数据的缓冲区链成的队列，用于保存输入设备输入的数据

  • 输出队列：装满输出数据的缓冲区链成的队列，用于保存用户程序输出到设备的数据

• 根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：

  • 用于收容输入数据的工作缓冲区(hin)

  • 用于提取输入数据的工作缓冲区(sin)

  • 用于收容输出数据的工作缓冲区(hout)

  • 用于提取输出数据的工作缓冲区(sout)

• 缓冲池中缓冲区的四种工作方式

  • 收容输入：输入进程从空缓冲队列的队首取得一空缓冲区，作为收容输入工作缓冲区，把数据输入其中，装满后将其挂在输入队列队尾。

  • 提取输入：计算进程从输入队列的队首取得一个缓冲区，作为提取输入工作缓冲区，从中提取数据，用完数据后将其挂在空缓冲队列队尾。

  • ---

  • 收容输出：计算进程从空缓冲队列的队首取得一空缓冲区，作为收容输出工作缓冲区，把数据输入其中，装满后将其挂在输出队列末尾。

  • 提取输出：输出进程从输出队列的队首取得一个缓冲区，作为提取输出工作缓冲区，从中提取数据，用完数据后将其挂在空缓冲队列末尾。

5.2.3 设备分配与回收

设备的分配与回收.pdf

设备分配的策略

• 设备分配的任务是按照一定的策略为提出I/O请求的进程分配合适的设备，确保CPU与I/O设备之间能够正常通信，还应分配相应的控制器和通道。

• 设备分配应根据设备特性、用户要求和系统配置情况。既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开来。（设备的固有属性、安全性、独立性）

设备的固有属性

设备的固有属性：独占设备、共享设备、虚拟设备

设备的分配方式：独享分配、共享分配、虚拟分配

• 独占设备——一个时段只能分配给一个进程（如打印机）

• 共享设备——可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。

• 虚拟设备——采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用SPOOLing技术实现的共享打印机）

设备分配方式

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

• 动态分配：进程运行过程中动态申请设备资源

设备分配算法

• 先来先服务：按照各个进程提出设备使用请求的先后顺序分配设备

• 优先级高者优先：进程的优先级越高越优先被分配设备

• 短任务优先

• ……

设备分配的安全性

从进程运行的安全性上考虑，设备分配有两种方式：

• 安全分配方式：进程发出I/O请求后，便进入阻塞状态，不能再请求任何资源，阻塞时也不保持任何资源。直到其I/O操作完成时才被唤醒（eg：考虑进程请求打印机打印输出的例子）

  • 一个时段内每个进程只能使用一个设备

  • 优点：破坏了“请求和保持”条件，不会死锁

  • 缺点：对于一个进程来说，CPU和I/O设备只能串行工作

• 不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。

  • 一个进程可以同时使用多个设备

  • 优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进

  • 缺点：有可能发生死锁（死锁避免、死锁检测和解除）

设备分配的数据结构

“设备、控制器、通道”之间的关系：一个通道可控制多个设备控制器，每个设备控制器可控制多个设备

用于设备分配的数据结构的主要作用是描述系统的配置、I/O设备的状态特性及当前的使用情况。

• 系统设备表SDT：System Device Table，记录了系统中全部设备的情况，每个设备对应一个表目，整个系统只有一张系统设备表。

  • 设备类型：如 打印机、扫描仪、键盘

  • 设备标识符：即物理设备名

  • 设备控制表DCT

  • 驱动程序入口

• 设备控制表DCT：Device Control Table，用于记录设备的情况，每个设备对应一张DCT

  • 设备类型：如 打印机/扫描仪/键盘

  • 设备标识符：即物理设备名，系统中的每个设备的物理设备名唯一

  • 设备状态：忙碌/空闲/故障…

  • 指向控制器表COCT的指针：每个设备由一个控制器控制，该指针可找到相应控制器的信息

  • 重复执行次数或时间：设备在工作中发生错误时应重复执行的次数，用于判定I/O请求是否失败

  • 设备队列的队首指针：指向正在等待该设备的进程队列（由进程PCB组成队列）

• 控制器控制表COCT：Controller Control Table，用于记录控制器情况，每个设备控制器对应一张COCT。

  • 控制器标识符：各个控制器的唯一ID

  • 控制器状态：忙碌/空闲/故障…

  • 指向通道表CHCT的指针：每个控制器由一个通道控制，该指针可找到相应通道的信息

  • 控制器队列的队首指针、队尾指针：指向正在等待该控制器的进程队列（由进程PCB组成队列）

• 通道控制表：通道控制表CHCT(Channel Control Table)，用于记录通道情况，每个通道对应一张CHCT。

  • 通道标识符：各个通道的唯一ID

  • 通道状态：忙碌/空闲/故障…

  • 与通道连接的控制器表首址：可通过该指针找到该通道管理的所有控制器相关信息（COCT）

  • 通道队列的队首指针、队尾指针：指向正在等待该通道的进程队列（由进程PCB组成队列）

设备分配的步骤

1. 根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）

2. 根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。

3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程

4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

5. 只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送

缺点

• 用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程

• 若换了一个物理设备，则程序无法运行

• 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名

1. 根据进程请求的逻辑设备名查找SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）

2. 查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。

3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。

4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进

   程。

设备分配的独立性

设备独立性：又称设备无关性，是指应用程序与具体使用的物理设备无关。用户可以利用逻辑设备进行I/O操作，而不必指定物理设备。

逻辑设备表LUT：Logical Unit Table，逻辑设备表建立了逻辑设备名与物理设备名之间的映射关系，从而实现了设备独立性。

• 逻辑设备表表项包括：逻辑设备名、物理设备名和设备驱动程序的入口地址。

• 某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。

• 如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。

逻辑设备表的两种设置方式：

• 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统（类似单级目录）

• 每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中。（类似两级目录）

【补充】设备映射表(DMT, Device Mapping Table)，Windows系统，逻辑设备表(LUT)，Unix系统，二者作用类似

5.2.4 SPOOLing技术（假脱机技术）

假脱机技术.pdf

脱机技术

批处理阶段引入了脱机输入/输出技术（用磁带完成）

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

引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

假脱机技术

• 实现思路：SPOOLing技术利用专门的外围控制机，数据从I/O设备输入时，先把低速I/O设备上的数据传送到高速磁盘上，再从磁盘读取相应的数据；数据输出到I/O设备时，先把数据输出到高速磁盘，再从磁盘输出到低速I/O设备。

• SPOOLing系统主要由以下四个部分组成：

  • 输入井：模拟脱机输入时的磁带，用于收容I/O设备输入的数据（磁盘中）

    输出井：模拟脱机输出时的磁带，用于收容用户进程输出的数据（磁盘中）

  • 输入进程：模拟脱机输入时的外围控制机，用于将用户要求的数据输入到输入井。

    输出进程：模拟脱机输出时的外围控制机，用于将用户要求的数据输出到输出井。

  • 输入缓冲区：在输入进程的控制下，“输入缓冲区”用于暂存从输入设备输入的数据，之后再转存到输入井中（内存中）

    输出缓冲区：在输出进程的控制下，“输出缓冲区”用于暂存从输出井送来的数据，之后再传送到输出设备上（内存中）

  • 井管理程序：包含输入井管理程序和输出井管理程序，用于控制设备与输入井、输出井之间信息的交换。

• SPOOLing系统的特点

  • 缓冲区的设置缓和了CPU和磁盘之间速度不匹配的矛盾

  • 将独占设备改造成虚拟的共享设备

  • 将一个物理设备变换成多个对应的逻辑设备

共享打印机的原理分析

打印机是种“独占式设备”，但是可以用SPOOLing技术改造成“共享设备”

当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：

1. 在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中；

2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。

当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。

5.2.5 设备驱动程序接口

输入输出应用程序接口和驱动程序接口.pdf

• 不同的操作系统，对设备驱动程序接口的标准各不相同。

• 设备厂商必须根据操作系统的接口要求，开发相应的设备驱动程序，设备才能被使用

5.2.7 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.3 磁盘和固态硬盘

5.3.1 磁盘

联系计算机组成原理磁盘存储器

磁盘的结构.pdf

磁盘是一种利用磁记录技术存储数据的存储器，具有记录密度大、容量高、速度快等优点，是目前计算机存储系统中使用最普遍的一种外部存储器。

磁盘是以数据块为信息交换单位的设备，每次可与内存交换一个或多个数据块的信息，且支持操作系统直接存取磁盘上的任意物理块

磁盘的结构

【补充】物理块与逻辑块都简称块，物理块=扇区，逻辑块=簇

• 操作系统以簇为单位分配空间，一个簇最小由一个扇区组成

• 文件以扇区为单位存放和读写

磁盘的相关概念如下：

• 盘片：由铝合金或玻璃构成的基片。盘片的表面涂有磁性物质，每个磁盘有一个或多个盘片

• 盘面：盘片上图有磁性物质的面，每个盘片有一个或两个盘面

• 磁头：对磁盘进行读写的部件，每个盘面对应一个磁头，因此盘面号又称磁头号。所有磁头连接在同一磁臂上，因此所有磁头只能共进退

• 磁道：盘面上以盘片中心为圆心，不同半径的同心圆。每个盘面有若干个磁道，各磁道之间有必要的间隙

• 柱面：所有盘面上由相同水平位置的磁道从上到下组成的圆柱体

• 扇区：每个磁道可以被分为若干个弧段，一个弧段就是一个扇区，各扇区之间有必要的间隙。扇区是磁盘的最小组成单元，每个扇区存放的数据量相等，越内侧磁道记录密度越大。

磁盘读写数据

磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读写

（柱面号，盘面号，扇区号）

磁盘的分类

根据磁头是否可移动

• 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道

• 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头

根据盘片是否可更换

• 盘片可以更换的称为可换盘磁盘

• 盘片不可更换的称为固定盘磁盘

5.3.2 磁盘的管理

磁盘的管理.pdf

磁盘初始化

考前记一记

1. 低级格式化，即物理格式化。是指对磁盘划分出柱面、磁道、扇区。每个扇区又划分为头部、数据区域和尾部三个部分组成，其中头部和尾部包含了一些磁盘控制器的信息，用于保存扇区号、进行扇区检验。

   • 低级格式化一般由磁盘生产厂家在出厂前完成

   • 如果某个扇区在出厂前已经损坏，且无法通过纠错算法恢复，则低级格式化过程将对该扇区进行标记，防止操作系统进行读写

2. 磁盘分区，是指把一个物理磁盘的存储空间划分为几个互相独立的部分，逻辑上每个分区就是一个独立的磁盘。每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘）

   • 如果操作系统需要从磁盘引导启动，则必须要有一个分区被标记为活动分区

3. 逻辑格式化，即逻辑格式化。是指对磁盘分区创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表）等，使操作系统能够对磁盘进行读写。

   • 联系1.5 操作系统引导

引导块

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

• ROM中只存放很小的“自举装入程序”，出厂时写入且以后不能再修改

• 完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置。

• 拥有启动分区的磁盘称为启动磁盘或系统磁盘（C盘）

坏块

• 坏块是指无法正常正常使用的扇区，属于硬件故障。

• 磁盘在生产时就可能存在坏块，出厂前的低级格式化会对磁盘上的坏块进行标记，并用磁盘末尾的一些空闲块进行替换，操作系统无法感知

• 出厂后仍会有正常的磁盘块变成坏块，这种情况则可以被操作系统检测到

• 坏块只能进行屏蔽而无法修复。

  • 操作系统可以在逻辑格式化时对整个磁盘进行坏块检查，标记那些脍是坏块。例如在FAT表上标明来避免使用。（坏块对操作系统不透明）

  • 磁盘控制器^[磁盘设备内部的一个硬件部件]会维护一个坏块链表。在磁盘出厂前进行物理格式化时就将坏块链进行初始化。并且会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。（坏块对操作系统透明）

5.3.3 磁盘的调度算法

磁盘调度算法.pdf

读写操作所需时间

• 寻道时间 $T_s$ ：磁头移动到数据所在磁道所需要的时间。寻道时间 $T_s=s+m\cdot n$

  • 启动磁头臂是需要时间的。假设耗时为 $s$ ；

  • 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为 $m$ ，总共需要跨越 $n$ 条磁道。（磁盘调度算法影响的指标，且对读写时间影响最大）

• 延迟时间 $T_r$：磁头移动到指定位置后，扇区旋转至磁头下面所需要的时间。设磁盘转速为 $r$ （单位：转/秒，或转/分），则平均所需的延迟时间 $T_r=\frac{1}{2}\cdot \frac{1}{r}=\frac{1}{2r}$ （平均需要半圈×转一圈所用时间）

• 传输时间 $T_t$：从磁盘读出或向磁盘写入数据所经历的时间。假设磁盘转速为 $r$ ，此次读/写的字节数为 $b$ ，每个磁道上的字节数为 $N$ 。则：传输时间 $T_t=\frac{1}{r}\cdot \frac{b}{N}=\frac{b}{rN}$ （转一圈所用时间×磁道数）

磁盘调度算法

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间

先来先服务(FCFS)

• 实现思路：根据进程请求访问磁盘的先后顺序进行调度

• 优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去

• 缺点：如果有大量进程竞争使用磁盘，且请求访问的磁道很分散，则在性能上很差，寻道时间长。

最短寻找时间优先(SSTF)

• 实现思路：优先处理磁盘访问请求中与当前磁头最近的磁道（贪心算法的思想）

• 优点：性能较好，平均寻道时间短

• 缺点：可能产生“饥饿”现象

扫描算法(SCAN)

若题目中无特别说明，则SCAN就是LOOK

• SSTF算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。

• 实现思路：只有磁头移动到最外侧磁道的时候才能往内移动（即使已经没有需求），移动到最内侧磁道的时候才能往外移动。由于磁头移动的方式很像电梯，因此也叫电梯算法。

• 优点：性能较好，平均寻道时间较短，不会产生饥饿现象

• 缺点：

  • 只有到达最边上的磁道时才能改变磁头移动方向

  • 对各个位置磁道的响应频率不平均，不利于远离磁头一侧的I/O请求

LOOK调度算法

• 实现思路：对SCAN算法的改进，磁头只需要移动到最远端的一个请求即可返回，不需要到达最后一个磁道（边移动边观察，因此叫LOOK）

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

循环扫描算法(C-SCAN)

若题目中无特别说明，则C-SCAN就是C-LOOK

• SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。

• 实现思路：将扫描限定在相同方向，只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

• 优点：比起SCAN来，对于各个位置磁道的响应频率很平均。

• 缺点：只有到达最边上的磁道时才能改变磁头移动方向。另外，比起SCAN算法来，平均寻道时间更长。

• 注意：在计算移动的磁道数时，第一趟遍历过的不要重复地在第二趟再算一遍 易错

C-LOOK调度算法

• 实现思路：对C-SCAN算法的改进，磁头只需要移动到最远端的一个请求即可返回，不需要到达最后一个磁道。

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

减少磁盘延迟时间的方法

减少磁盘延迟时间的方法.pdf

交替编号

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”（读完一个扇区后需要一小段时间处理，即“处理时间”而盘片又在不停的旋转，如果相邻排列，会错过下一个扇区，要等下一轮才行）

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

磁盘地址结构的设计

磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）

在读取地址连续的磁盘块时，若采用第一种编址方式，由于由于柱面号/磁道号相同，只是盘面号不同，因此不需要移动磁头臂。只需要激活相邻盘面的磁头即可

错位命名

读取完上一个盘面的磁盘块，需要短暂的时间处理，而盘面又在不停地转动，因此如果相邻的盘面相对位置处扇区编号相同，就并不能读取数据，只能等一轮，等该扇区再次划过磁头。（类似交替编号）

5.3.4 固态硬盘

固态硬盘SSD.pdf

见计算机组成原理固态硬盘

5.3.6 本节习题精选

选择题：题目、答案

综合题：题目、答案