目录
(1)先来先服务(First Come First Served,FCFS)算法
(2)最短寻道时间优先(Shortest Seek Time First,SSTF)算法
(4)循环扫描(Circular SCAN,C-SCAN)算法
5.1 I/O管理概述
5.1.1 I/O设备
1.设备的分类
I/O设备是指可以将数据输入计算机的外部设备，或者可以接收计算机输出数据的外部设备。I/O设备的类型繁多，从不同的角度可将它们分为不同的类型。
按信息交换的单位分类，I/O设备可分为：
1)块设备。信息交换以数据块为单位，如磁盘、磁带等。磁盘设备的基本特征是传输速率较高、可寻址，即对它可随机地读/写任意一块。
2)字符设备。信息交换以字符为单位，如交互式终端机、打印机等。它们的基本特征是传输速率低、不可寻址，并且通常采用中断I/O方式。
按设备的传输速率分类，I/O设备可分为：
1)低速设备。传输速率仅为每秒几字节到数百字节，如键盘、鼠标等。
2)中速设备。传输速率为每秒数千字节至数万字节，如激光打印机等。
3)高速设备。传输速率在数百千字节至千兆字节，如磁盘、光盘等。
按设备的使用特性分类，I/O设备可分为：
1)人机交互设备。用于用户和计算机之间交互信息的设备，如键盘、显示器、打印机等。
2)存储设备。用于存储信息的设备，如磁盘、磁带、光盘等。
3)网络通信设备。用于计算机和计算机之间的通信，如网卡、调制解调器等。
按设备的共享属性分类，I/O设备可分为：
1)独占设备。同一时刻只能由一个进程占用的设备。一旦将这类设备分配给某进程，便由该进程独占，直至用完释放。低速设备一般是独占设备，如打印机。
2)共享设备。同一时间段内允许多个进程同时访问的设备。对于共享设备，可同时分配给多个进程，通过分时的方式共享使用。典型的共享设备是磁盘。
3)虚拟设备。通过SPOOLing技术将独占设备改造为共享设备，将一个物理设备变为多个逻辑设备，从而可将设备同时分配给多个进程。
2.I/O接口
I/O接口(也称设备控制器)是CPU与设备之间的“桥梁”,以实现设备和计算机之间的数据交换。它接收发自CPU的命令，控制设备工作，使CPU能从繁杂的设备控制事务中解脱出来。设备控制器主要由三部分组成，如下图所示。
1)设备控制器与CPU的接口。用于实现CPU与设备控制器之间的通信。该接口有三类信号线：数据线、地址线和控制线。数据线传送的是读/写数据、控制信息和状态信息；地址线传送的是要访问I/O接口中的寄存器编号；控制线传送的是读/写等控制信号。
2)设备控制器与设备的接口。一个设备控制器可以连接一个或多个设备，因此控制器中有一个或多个设备接口。每个接口都可传输数据、控制和状态三种类型的信号。
3)I/O逻辑。用于实现对设备的控制。它通过一组控制线与CPU交互，对从CPU收到的I/O命令进行译码。CPU启动设备时，将启动命令发送给控制器，同时通过地址线将地址发送给控制器，由控制器的I/O逻辑对地址进行译码，并对所选设备进行控制。
设备控制器的主要功能有：①接收和识别命令，如磁盘控制器能接收CPU发来的读、写、查找等命令；②数据交换，包括CPU和控制器之间的数据传输，以及控制器和设备之间的数据传输；③标识和报告设备的状态，以供CPU处理；④地址识别；⑤数据缓冲；⑥差错控制。
3.I/O接口的类型
1)按数据传送方式(外设和接口一侧),可分为并行接口(一个字节或者一个字的所有位同时传送)和串行接口(一位一位地有序传送),接口要完成数据格式的转换。
2)按主机访问I/O设备的控制方式，可分为程序查询接口、中断接口和DMA接口等。
3)按功能选择的灵活性，可分为可编程接口(通过编程改变接口功能)和不可编程接口。
4.I/O端口
I/O端口是指设备控制器中可被CPU直接访问的寄存器，主要有以下三类寄存器。
●数据寄存器：用于缓存从设备送来的输入数据，或从CPU送来的输出数据。
●状态寄存器：保存设备的执行结果或状态信息，以供CPU读取。
●控制寄存器：由CPU写入，以便启动命令或更改设备模式。
I/O端口要想能够被CPU访问，就要对各个端口进行编址，每个端口对应一个端口地址。而对I/O端口的编址方式有与存储器独立编址和统一编址两种，如图5.2所示。
(1)独立编址
独立编址是指为每个端口分配一个I/O端口号。I/O端口的地址空间与主存地址空间是两个独立的地址空间，它们的范围可以重叠，相同地址可能属于不同的地址空间。普通用户程序不能对端口进行访问，只有操作系统使用特殊的I/O指令才能访问端口。
优点：I/O端口数比主存单元少得多，只需少量地址线，使得I/O端口译码简单，寻址速度更快。使用专用I/O指令，可使程序更加清晰，便于理解和检查。
缺点：I/O指令少，只提供简单的传输操作，所以程序设计的灵活性较差。此外，CPU需要提供两组独立的存储器和设备的读/写控制信号，增加了控制的复杂性。
(2)统一编址
统一编址也称内存映射I/O,是指将主存地址空间分出一部分给I/O端口进行编址，I/O端口和主存单元在同一地址空间的不同分段中，根据地址范围就能区分访问的是I/O端口还是主存单元，因此无须设置专门的I/O指令，用统一的访存指令就可访问I/O端口。
优点：不需要专门的I/O指令，使得CPU访问I/O的操作更加灵活和方便，还使得端口有较大的编址空间。I/O访问的保护机制可由虚拟存储管理系统来实现，无须专门设置。
缺点：端口地址占用了部分主存地址空间，使主存的可用容量变小。此外，由于在识别I/O端口时全部地址线都需参加译码，使得译码电路更加复杂，降低了寻址速度。
5.1.2 I/O控制方式
I/O控制是指控制设备和主机之间的数据传送。在I/O控制方式的发展过程中，始终贯穿着这样一个宗旨：尽量减少CPU对I/O控制的干预，将CPU从繁杂的I/O控制事务中解脱出来，以便其能更多地去执行运算任务。I/O控制方式共有4种：
1.程序直接控制方式
CPU对I/O设备的控制采取轮询的I/O方式，也称程序轮询方式。如图5.3(a)所示，CPU向设备控制器发出一条I/O指令，启动从I/O设备读取一个字(节),然后不断地循环测试设备状态(称为轮询),直到确定该字(节)已在设备控制器的数据寄存器中。于是CPU将数据寄存器中的数据取出，送入内存的指定单元，这样便完成了一个字(节)的I/O操作。
这种方式简单且易于实现，但缺点也很明显。CPU的绝大部分时间都处于等待I/O设备状态的循环测试中，CPU和I/O设备只能串行工作，由于CPU和I/O设备的速度差异很大，导致CPU的利用率相当低。而CPU之所以要不断地测试I/O设备的状态，就是因为在CPU中未采用中断机制，使I/O设备无法向CPU报告它已完成了一个字(节)的输入操作。
2.中断驱动方式
中断驱动方式的思想是允许I/O设备主动打断CPU的运行并请求服务，从而“解放”CPU,使得CPU向设备控制器发出一条I/O指令后可以继续做其他有用的工作。如图5.3(b)所示，我们从设备控制器和CPU两个角度分别来看中断驱动方式的工作过程。
从设备控制器的角度来看：设备控制器从CPU接收一个读命令，然后从设备读数据。一旦数据读入设备控制器的数据寄存器，便通过控制线给CPU发出中断信号，表示数据已准备好，然后等待CPU请求该数据。设备控制器收到CPU发出的取数据请求后，将数据放到数据总线上，传到CPU的寄存器中。至此，本次I/O操作完成，设备控制器又可开始下一次I/O操作。
从CPU的角度来看：当前运行进程发出读命令，该进程将被阻塞，然后保存该进程的上下文，转去执行其他程序。在每个指令周期的末尾，CPU检查中断信号。当有来自设备控制器的中断时，CPU保存当前运行进程的上下文，转去执行中断处理程序以处理该中断请求。这时，CPU从设备控制器读一个字的数据传送到寄存器，并存入主存。中断处理完后解除发出I/O命令的进程的阻塞状态，然后恢复该进程(或其他进程)的上下文，然后继续运行。
相比于程序轮询I/O方式，在中断驱动I/O方式中，设备控制器通过中断主动向CPU报告I/O操作已完成，不再需要轮询，在设备准备数据期间，CPU和设备并行工作，CPU的利用率得到明显提升。但是，中断驱动方式仍有两个明显的问题：①设备与内存之间的数据交换都必须经过CPU中的寄存器；②CPU是以字(节)为单位进行干预的，若将这种方式用于块设备的I/O操作，则显然是极其低效的。因此，中断驱动I/O方式的速度仍然受限。
3.DMA方式
DMA(直接存储器存取)方式的基本思想是，在I/O设备和内存之间开辟直接的数据交换通路，彻底“解放”CPU。DMA方式的特点如下：
1)基本传送单位是数据块，而不再是字(节)。
2)所传送的数据，是从设备直接送入内存的，或者相反，而不再经过CPU。
3)仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。
为了实现主机和控制器之间直接交换成块的数据，须在DMA控制器中设置如下4类寄存器：
1)命令/状态寄存器(CR)。暂存从CPU发来的I/O命令，或设备的状态信息。
2)内存地址寄存器(MAR)。在输入时，它存放将数据从设备传送到内存的起始目标地址；在输出时，它存放由内存到设备的内存源地址。
3)数据寄存器(DR)。暂存从设备到内存，或从内存到设备的数据。
4)数据计数器(DC)。存放本次要传送的字(节)数。
如图5.3(c)所示，DMA方式的工作过程是：CPU接收到设备的DMA请求时，它向DMA控制器发出一条命令，同时设置MAR和DC初值，启动DMA控制器，然后继续其他工作。之后CPU就将I/O控制权交给DMA控制器，由DMA控制器负责数据传送。DMA控制器直接与内存交互，每次传送一个字，这个过程不需要CPU参与。整个数据传送结束后，DMA控制器向CPU发送一个中断信号。因此只有在传送开始和结束时才需要CPU的参与。
DMA方式的优点：数据传输以“块”为单位，CPU介入的频率进一步降低；数据传送不再经过CPU的寄存器，CPU和设备的并行操作程度得到了进一步提升。
4.通道控制方式
5.1.3 I/O软件层次结构
I/O软件涉及的面很宽，往下与硬件有着密切关系，往上又与虚拟存储器系统、文件系统和用户直接交互，它们都需要I/O软件来实现I/O操作。
为使复杂的I/O软件能具有清晰的结构、良好的可移植性和易适应性，目前普遍采用层次结构的I/O软件。将系统中的设备管理模块分为若干层次，每层都是利用其下层提供的服务，完成输入/输出功能中的某些子功能，并屏蔽这些功能实现的细节，向高层提供服务。在层次结构的I/O软件中，只要层次间的接口不变，对某一层次中的软件的修改都不会引起其下层或高层代码的变更，仅最低层才涉及硬件的具体特性。一个比较合理的层次划分如图5.5所示。整个I/O软件可以视为具有4个层次的系统结构，各层次及其功能如下：
(1)用户层软件
(2)设备独立性软件
用于实现用户程序与设备驱动器的统一接口、设备命名、设备保护，以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
设备独立性也称设备无关性，其含义是指应用程序所用的设备不局限于某个具体的物理设备。为实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名来请求使用某类设备；而在系统实际执行时，必须将逻辑设备名映射成物理设备名。
使用逻辑设备名的好处是：①增加设备分配的灵活性；②易于实现I/O重定向，所谓I/O重定向，是指用于I/O操作的设备可以更换(重定向),而不必改变应用程序。
为了实现设备独立性，必须再在驱动程序之上设置一层设备独立性软件。总体而言，设备独立性软件的主要功能可分为以下两个方面。①执行所有设备的公有操作，包括：对设备的分配与回收；将逻辑设备名映射为物理设备名；对设备进行保护，禁止用户直接访问设备；缓冲管理；差错控制；提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异。②向用户层(或文件层)提供统一接口。无论何种设备，它们向用户所提供的接口应是相同的。例如，对各种设备的读/写操作，在应用程序中都统一使用read/write命令等。
(3)设备驱动程序
与硬件直接相关，每类设备需要配置一个设备驱动程序。
