操作系统（五）——输入/输出（I/O）管理
操作系统（五）——输入/输出（I/O）管理
1. I/O设备的概念和分类
通过之前的学习可以知道，操作系统作为系统资源的管理者，既需要对上层的软件进行管理，也需要对下层的硬件进行管理。在之前的学习里，已经学习了操作系统对处理机还有存储器这些硬件进行管理。但是这些硬件其实是在计算机的主机内部的。本章要探讨的所谓的设备管理，指的是操作系统对计算机主机外部硬件设备的管理。
接下来了解一下I/O设备的基本概念和分类。
I/O设备又可以称为外部设备，属于计算机中的硬件部件。所谓的I/O指的就是输入和输出。l/O设备可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备。
因此输入的过程就是把设备准备好的数据读入计算机当中，而输出的过程就是把计算机准备好的数据写出到输出设备上。所以UNIX系统会把这些外部设备抽象为一种特殊的文件，这样的话用户就可以用读文件或者写文件的方式，来对外部设备进行操作。
像下图的write操作就是向外部设备写出数据，也就是数据输出的过程。read操作就是从外部设备读入数据，也就是数据输入的过程。
接下来看一下IO设备有哪些分类：
按使用特性分类：
按传输速率分类：
按信息交换的单位分类：
最后对这部分进行一个小结：
2. I/O控制器
I/O设备由机械部件和电子部件(I/O控制器、设备控制器)组成。
我们平时使用的鼠标、键盘还有显示器，这些我们看得见摸得着的机械部分就是机械部件，这些机械部件主要用来执行具体的IO操作。比如说显示屏就是用来显示输出数据。
而电子部件一般来说就是印刷电路板。当我们的设备连上电脑以后，CPU是没办法直接控制这些IO设备的机械部件，必须通过电子部件来间接的控制这些机械部件。
因此电子部件(I/O控制器)就是一个CPU和IO设备的机械部件之间的一个中介。I/O控制器其实就是用于实现CPU对I/O设备的控制的。
I/O控制器的功能如下图：
I/O控制器首先要能接收和识别CPU发出的命令，除了命令本身外，CPU还会告诉I/O控制器执行这个命令的一些相关参数。因此I/O控制器中会有相应的控制寄存器来存放命令和参数。
其次，I/O控制器还要能向CPU报告设备的状态，比如一个设备此时是忙碌还是空闲。CPU作为系统资源的管理者，当然也需要知道各个设备的相应状态。因此I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌。CPU可以读取这个寄存器当中的内容，来判断设备此时的状态。
接着，I/O控制器还需要实现数据交换的功能。I/O控制器是CPU和I/O设备机械部件的中介，所以需要作为数据交换的中间媒介。因此，l/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。
最后，I/O控制器需要实现地址识别的功能。I/O控制器当中会设置各种各样的寄存器，并且每一组寄存器可能会有多个，为了识别这些寄存器，所以需要像给内存编址一样给个寄存器编上一个相应的地址。CPU在往这些寄存器当中读或者写数据的时候，就是通过这些寄存器对应的地址来进行操作的。I/O控制器需要通过CPU提供的地址来判断，此时CPU想要操作的到底是哪一个寄存器。
下面看一下I/O控制器由哪些部分组成：
一般来说，I/O控制器可以分为三个部分，第一个部分是CPU与控制器的接口，第二个部分叫做I/O逻辑，第三个部分是控制器与设备的接口。
I/O控制器作为CPU和机械部件之间的中介，如上图，CPU与控制器的接口负责I/O控制器与CPU连接。控制器与设备的接口负责I/O控制器与设备的机械部件连接。而I/O控制器在连接CPU和设备的时候，需要做一些中间处理，这些处理就在I/O逻辑部分完成。
因此，I/O逻辑会负责接收和识别CPU的各种命令（如地址译码），在接收和识别了CPU的命令之后，I/O逻辑需要把它翻译成具体的设备能够明白的命令，然后通过控制器与设备之间的接口，发送给具体的设备，让设备执行相应的操作。
在上图可以发现，一个I/O控制器可能会有多个控制器与设备之间的接口，也就是说一个I/O控制器有可能会负责控制多个具体的I/O设备。此时CPU为了区别要操作的是哪一个设备，同样需要给这些设备进行编号，CPU在发出I/O命令的时候，也需要指明自己需要操作的是哪个设备。
来看一下具体过程，如上图，CPU首先会通过一个叫做控制线的线路，向I/O控制器发出一个具体的指令。同时，CPU还会在地址线上说明自己要操作的是哪一个设备。如果说，此时是要输出一个数据，CPU会通过数据总线把自己要输出的数据放到I/O控制器的数据寄存器当中，之后I/O逻辑就可以从数据寄存器当中取得CPU想要输出的数据。类似的，CPU此时发出的这个I/O指令可能会有一些相应的参数，这些参数会放到控制寄存器当中，I/O逻辑就可以从控制寄存器当中取得相应的参数。另外为了实现对各个设备的管理，CPU还会从状态寄存器当中读出各个设备的状态，因此I/O逻辑会往状态寄存器当中写入相应的数据，来告诉CPU各个设备的状态到底是什么样的。这就是CPU与控制器的接口所需要完成的一些事情。
现在看一下控制器与设备的接口需要做哪些事情，如果输出一个数据，首先就是由CPU通过数据总线把数据写入到数据寄存器当中，之后I/O逻辑就可以从数据寄存器当中取得CPU想要输出的数据，然后通过控制器与设备的接口把数据输出到外部设备上。类似的，如果要输入一个数据，这些数据可以通过控制器与设备的接口输入，然后I/O逻辑就可以把这些数据放到数据寄存器当中，之后CPU从数据寄存器当中取走数据。这就完成了数据输入的过程。那除了传送数据，设备还需要及时向I/O控制器反馈自己的状态，同样的，设备通过控制器与设备的接口像I/O控制器报告此时自己的状态，然后I/O控制器的I/O逻辑又会把这个设备的状态写入到对应的状态寄存器里。另外，制器与设备的接口中还会有一个用于实现设备控制的电路，I/O逻辑会根据CPU发出的命令和相应的参数，然后对对应的设备发出一些控制命令。
这地方有两个小细节需要注意一下，如下图：
对于上图所说的两个注意点，这里要补充一下知识，一般来说给寄存器编址有两种方式，第一种方式就是让他们占用内存地址的一部分，这种方式称为内存映像I/O。另一种方式就是会采用I/O专用的地址，也就是寄存器独立编制。
下面看一下这两种方式的区别：
如果采用内存映像I/O，如上图左，假设内存共有N个地址，编号分别是0到N-1。如果系统中有一个设备控制器0，它有三个对应的寄存器，这些寄存器就会顺着内存地址继续往下编制，寄存器0的地址是N，寄存器1的地址是N+1，寄存器2的地址是N+2，然后依次类推。如果还有别的设备控制器，那依次往下编制。也就是说内存映像I/O，控制器中的寄存器与内存地址统一编址。
如果采用寄存器独立编址的话，内存编号仍是分别是0到N-1，如果有一个设备控制器有三个寄存器，这些寄存器又会从0开始进行编号，如上图右，相应的，如果还有别的寄存器也会从0开始编号。不过在有的系统当中，也有可能是各个设备控制器当中的寄存器用连续编号的方式。这些细节部分可以忽略，只需要知道寄存器独立编制，控制器中的寄存器与内存地址不统一编址。
采用寄存器独立编址有一个很明显的缺点：需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号。而采用内存映像I/O，就不需要设置专门的指令来支持对这些寄存器的操作，即可以采用对内存进行操作的指令来对控制器进行操作。
下面对这小结进行一个总结：
3. I/O控制方式
随着计算机的发展，I/O控制器也是在不停的发展的，相应的，I/O控制器对设备的控制方式也出现了不同的变化，本节要掌握下图的四种I/O控制方式。
注意，在学习这几个I/O控制方式时，要注意研究上图提出的几个问题。
3.1 程序直接控制方式
下面来分析一下，采用程序直接控制方式，完成一次读写操作的流程是什么样的，这里以读操作为例：
如上图，在2.I/O控制器里我们知道，一个I/O控制器有如上图右的结构组成。
如果要进行读操作，CPU会首先通过控制线向I/O控制器发出一条读指令，然后I/O控制器会根据CPU的要求来启动相应的设备，并且会把这个设备对应的状态设置为未就绪，或者忙碌的状态，假设状态寄存器为1表示这个设备忙碌。
接下来这个设备就会开始准备计算机想要读入的数据。但是由于设备的速度要比CPU慢很多，所以在设备还没有完成I/O之前，CPU会一直不断的轮询检查这个设备的状态，也就是检查状态寄存器中的数据，如果数字为1就表明这个设备在忙碌，还没有准备好想要读入的数据。
再接下来，如果设备准备好了输入的数据，那么这个设备就会给I/O控制器传送这一次要输入的数据，并且报告自己的状态已经变成了已就绪的状态。
然后，I/O逻辑会把这个设备传送来的数据放入数据寄存器当中，并且会把状态寄存器改为0，即已就绪的状态。在这个过程中，CPU也是在不停的轮询检查的，当它发现状态寄存器变为了0，CPU就可以从数据寄存器当中，取出此次要输入的数据。
在取出此次要输入数据的过程中，CPU首先会把这个数据读到CPU自己的寄存器当中。然后再把CPU寄存器当中的内容再放到内存当中。所以数据输入的过程，本来是要从设备输入到内存，但这个过程中必须先经过CPU的寄存器，然后再由寄存器转存到内存当中，这样就完成了一次读操作。
如果之后还要继续读数据，CPU就会发送下一条读指令，然后继续循环上面的过程。
采用程序直接控制方式的流程图如下图右：
这里说一下不易理解的点，在每个步骤后面都会有一个指向性信息，比如第一个步骤，给I/O模块发出读命令的后面就有一个CPU->I/O，其意思是读命令是CPU向I/O控制器发出的，其余的几个步骤后面的指向性信息同理。
另外，这里还有一个不易理解的点，为什么数据读入CPU寄存器以后，还需要往存储器当中写入数据。这里可以结合上图的C语言代码来理解，如C语言代码里的scanf，就是从键盘这种I/O设备里读入一个输入字符，并且赋值给其中某一个变量。而程序里定义的变量a,b,c,d等是存放在存储器也就是内存中的，所以这些数据从键盘读入以后，最终是要被放到存储器也就是内存中的，因此当CPU获得从键盘输入的数据以后，还需要把这些数据写入到相应的存储器的单元里。同理，printf输出数据时，也是把内存当中存储的变量的数据经过CPU输出到输出设备上。
接下来分析一下开篇提到的另外的几个问题：
首先看一下CPU的干预频率，在使用程序直接控制方式的时候，CPU需要不断轮询检查I/O操作是否已经完成，所以CPU干预的频率是很频繁的，不仅在I/O操作开始之前和完成之后需要CPU的介入，在等待I/O完成的过程中，CPU也需要不断的轮询检查。这也是程序直接控制方式的最大一个缺点。
下一个要关注的问题是程序的控制单位，从上面的分析中可以发现，每次读入或写出的数据量是一个字。
下一个要注意的是数据的流向，所谓数据流向就是上面分析的，在读入数据时，数据流向是从I/O设备->CPU->内存。在输出数据时，数据流向是从内存->CPU->I/O设备。所以每个字的读和写都需要CPU的介入和帮助。也就是说CPU需要花费大量时间来辅助I/O完成。
最后要看一下程序直接控制方式的主要缺点和优点：
优点：实现简单，可以用软件的方式就可以实现。由于轮询的过程就是在执行一系列循环检查的指令，所以这种方式才称为“程序直接控制方式”。
缺点：CPU和I/O设备只能串行工作，在CPU发出一条命令以后，并不能去做别的事情，需要一直不断的循环检查I/O是否已完成，所以CPU长期处于“忙等”状态，CPU利用率低。相应的，当CPU在进行一些别的计算工作时，I/O设备也是空闲的，所以I/O设备的利用率也是低的。为了应对这种问题，人们提出了中断驱动方式。
3.2 中断驱动方式
与程序直接控制方式相比，中断驱动方式主要是引入了中断机构，可以让CPU在发出I/O指令之后，继续做别的事情，即切换到别的进程。中断驱动的流程图如下。
由于I/O设备速度很慢，而CPU又是一种速度很快的硬件机构，所以当CPU发出I/O指令之后，可以把此时需要等待I/O的进程先阻塞，然后CPU去做其它的事情，当I/O完成之后，控制器会向CPU发出一个中断信号，CPU检测到中断信号以后，就会根据中断信号类型来执行相应的中断处理程序。在CPU处理中断的过程当中，会从I/O控制器中读出一个字的数据传送到CPU寄存器，并且再写入主存。接下来CPU就可以恢复之前被阻塞的进程继续往下执行，当然也可以选择不恢复，让其在就绪队列里继续等待，然后先执行别的进程。
这里要注意两点：①CPU会在每个指令周期的末尾检查中断；②中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能，而且中断每次只能读入一个字的数据，所以如果要读入大量的数据，显然会发生大量的中断，这样也会导致系统的性能降低。
接下来分析一下开篇提到的另外的几个问题在中断方式里的情况：
相比于之前的程序控制方式来说，采用中断方式的CPU干预的频率就降低了许多，CPU只需要在每次的I/O操作开始之前发出一条指令，然后就可以做其它的事情；当I/O完成之后，CPU也需要介入来处理相应的中断，而由于等待I/O的过程中，CPU可以切换到别的进程，所以在引入了中断以后，才实现了CPU和I/O设备并行工作的特点。
另外需要知道的是，每发出一个读/写指令，就会读入或写出1个字大小的数据。
中断驱动方式的数据流向与前面的程序直接控制方式是相同的，在读入数据时，数据流向是从I/O设备->CPU->内存。在输出数据时，数据流向是从内存->CPU->I/O设备。
中断驱动方式的优点就是解决了程序直接控制方式的最大缺点，引入了中断技术之后，可以让CPU和I/O设备并行的工作，然后CPU不需要再不停地轮询来检查I/O是否完成。这样CPU和I/O设备的利用率都得到了明显的提升。
而这种方式也存在很明显的缺点，就是每次只能传送一个字，所以当要传送大量数据时，就会发送很多次中断，而每次中断处理都会付出一定时间代价。所以中断如果发生太频繁，就会消耗较多的CPU时间。
另外，采用这种方式的时候，在读入数据或者写出数据的时候，都必须先经过CPU，但是通过之前的分析也可以知道，读入数据就是把I/O设备准备好的数据放到内存里，而写出数据则是把内存准备好的数据写出到I/O设备，所以为了把中间必须经过CPU中转的步骤省略掉，人们又提出了一种新的I/O控制方式叫做DMA方式。
3.3 DMA方式
DMA方式又叫直接存储器存取，这种方式主要用于对于块设备的I/O控制，相比于中断驱动方式，DMA的数据传送单位由”字”变成了”块”，每次会读入或写出一个块。
另外DMA的数据流向不再需要经过CPU，而是可以在DMA控制器的控制下，直接从设备放入内存或者从内存写出到设备。
而且，使用DMA方式，CPU对I/O操作的干预频率也进一步降低，仅仅在传送一个或多个数据块的开始和结束时，才会需要CPU进行干预。
DMA方式的大致流程如上图左下，首先CPU会给I/O模块发出一个读或者写一个块的命令，之后CPU就可以转头做其它的事情。接下来DMA控制器会根据CPU发出的命令参数，完成CPU指定的一系列读写工作，当CPU指定的这些块读完或者写完之后，又会由DMA控制器向CPU发出一个中断信号，让CPU介入处理这个中断。
在上面一直提到的DMA控制器也是一种I/O控制器，只不过存在一些小区别，DMA控制器的组成如下图：
DMA控制器同样由三部分组成，第一部分是主机与控制器的接口，第二部分是I/O控制逻辑，第三部分是块设备和控制器接口。
为了实现DMA控制器和CPU之间的通信，还会再DMA控制器里设置一系列寄存器，如上图，然后CPU可以通过系统总线来读或者写DMA控制器当中某些寄存器的内容，用这种方式达到控制I/O设备的一个目的。
这里说明一下，上图中的寄存器以及其作用都已经给出，这里就不再详细叙述。但是要知道，和之前说的I/O控制器一样，这些寄存器也有可能有多个，上图只列出几个主要的，并没有列全。
在控制器和块设备之间也有一个相应的接口，通过这个接口可以实现控制器对于这些块设备的通信控制的过程。
系统总线还会把DMA控制器和内存连接在一起，所以DMA控制器和内存之间可以直接进行数据的读写，不再需要经过CPU。比如说CPU在刚开始可以指明这次要读的数据是存放在磁盘的什么位置，读入的数据要存放在内存的什么位置，这个信息是存放在DMA控制器的MAR里的，并且还会说明此次要读入数据的数据量，数据量存放在DC里。接下来DMA控制器就会跟据CPU提供的这一系列的参数，从磁盘的相应位置，读入数据，然后写到内存里，这个过程就不再需要CPU的干预，只有DMA控制器完成了整个CPU指定的这一系列动作以后，才会向CPU发出一个中断信号，然后CPU再进行后续的处理。
这里要注意，DMA控制器并不是每次直接读入一整块的数据，然后把一整块放到内存当中，其实DMA控制器在读入数据的过程当中，也是一个字一个字的读入，然后每次读入的一个字都是先存放在DR，也就是数据寄存器当中，再从DR写入到内存当中。通过这种一个字一个字的方式，最终就可以完成一地址块数据读入的工作。
采用DMA方式完成一次读写操作的流程就是上面所说，接下来继续研究DMA方式：
首先还是再看DMA的CPU的干预频率，在采用DMA方式以后，CPU的干预频率就进一步降低，仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。在开始之前，CPU需要发出相应的I/O指令，并且指明相应的参数；在结束之后，CPU需要处理中断，然后进行后续的一系列处理。
另外，DMA方式的数据传送单位也从一个字变成了一个块，CPU每发出一个读指令或者写指令之后，DMA控制器就会完成对一个块或者多个块的读和写的操作，但需要注意的是，这个地方指的多个块，只能是读写连续的多个块，并且这些块在读入内存以后也必须是连续存放的。也就是说，如果想要读入多个离散的块或者想把读入的块离散的存放在内存的不同位置，那么采用DMA方式同样是需要CPU发出多条I/O指令。
采用DMA方式以后，数据的流向就不再需要经过CPU，它可以直接从I/O设备读入，然后再DMA控制器的控制下，直接把数据放入到内存，在输出时刚好相反。
DMA方式的优点就是进一步提升了数据传输的效率，数据传输以块为单位，CPU介入频率进一步降低，这样的话，CPU就可以有更多的时间去进行别的处理，另外数据传输的过程也不再需要经过CPU，所以数据传送的效率也进一步增加。总而言之，CPU和I/O设备的并行性得到提升，资源利用率也得到了进一步的提升。
DMA方式的缺点就是上面刚刚说到的，CPU每发出一条l/O指令，只能读/写一个或多个连续的数据块。如果想要读入多个离散的块或者想把读入的块离散的存放在内存的不同位置，那么采用DMA方式同样是需要CPU发出多条I/O指令。为了解决这个问题，人们又提出了通道控制方式。
3.4 通道控制方式
通道是一种硬件，可以理解为是”弱鸡版的CPU”，通道可以识别并执行一系列的通道指令。
首先，看一下通道的工作原理，如上图，CPU、内存、通道通过系统总线连接到一起。CPU会先向通道这个硬件发出I/O指令，并且指明此次要执行的通道程序(即通道指令的序列)是存放在内存的什么位置的，同时CPU还要指明此次要执行操作的设备是哪一个，在把这些信息告诉通道以后，CPU就可以切换到其它进程执行。
接下来通道会根据CPU的指示，去找到此次要执行的通道程序存放在内存当中的哪个位置，这个通道程序可以理解为任务清单(就是一些利通道指令的集合)。在通道程序的通道指令当中，会向通道指明此次要读入和写出的数据是多少，读写的数据要放到或存在于内存当中的什么位置等一系列信息，这些都是通道在执行这个程序的过程当中就可以知道的事情。所以采用这种方式，就相等于CPU只是告诉通道现在去执行一个任务，任务清单已经放到内存里，但具体任务的内容要做什么并不是由CPU直接告诉通道，而是由通道去读取内存当中的通道程序，然后一步一步执行的。
当通道执行完一系列任务之后，就会向CPU发出一个中断信号，CPU接收到中断信号以后，对中断进行处理，然后再继续执行接下来的一系列程序。
上面就是通道控制方式当中，完成一次I/O所需要经历的一系列步骤。现在要思考一个问题，为什么说通道是“弱鸡版的CPU”？
说通道是“弱鸡版的CPU”是因为与CPU相比，通道可以执行的指令很单一，并且通道也没有自己的内存，通道程序是放在主机内存中的，也就是说通道与CPU共享内存，因此可以把通道理解为是弱鸡版的CPU。
引入了通道以后，CPU的干预频率就进一步降低，CPU可以一次扔给通道一堆事情，这些事情会写在通道程序里，所以通道可以根据通道程序的指示一步一步完成I/O操作，然后当它完成了一系列的数据块读写以后，才需要对CPU发出中断信号，因此CPU的干预频率是极低的。
在通道控制方式中，每次读写可以完成对一组数据块的读写操作。
与DMA类似，采用通道控制方式之后，可以在通道的控制下，让数据直接从I/O设备读入内存，或者直接把内存中的数据直接输出到I/O设备当中。
通道方式的主要缺点就是实现复杂，需要专门的通道硬件支持。
但通道方式的优点也很明显，就是CPU、通道、l/O设备可并行工作，资源利用率很高。
3.5 I/O控制方式小结
4. I/O软件层次结构
I/O软件层次从上至下，依次可以分为用户层软件、设备独立性软件、设备驱动程序、中断处理程序这样的四层，如下图：
从上图还可以看到，在I/O软件的下层是I/O的硬件设备，而I/O设备的硬件又是由机械部分和电子部分组成，而I/O硬件的组成和原理在I/O控制器部分已经说过，这部分重点关注软件层面要实现的功能。
另外，I/O软件层次里的下面三层，即设备独立性软件、设备驱动程序、中断处理程序属于操作系统内核部分，所以这三层也可以被称为I/O核心子系统或简称I/O系统。上面的用户层软件是在操作系统内核之外的，也就是可以在用户态下实现一系列的功能。
从上面的示意图中还可以看到，在这些层次结构当中，越靠近上层的越接近用户，越靠近下层的越接近硬件。而各个层次都会使用它们下面一层软件所提供的功能，并且向它上层的软件提供一些服务。像这种，每一层会利用其下层提供的服务，实现某些功能，并屏蔽实现的具体细节，向高层提供更简单易用的接口，这种思想就是封装思想。
当用户发出一个I/O请求的时候，这个I/O请求会从上至下，经过各个层次进行处理，最后被扔给I/O硬件，来执行实际的I/O操作。当I/O硬件做完这次I/O操作，发出I/O应答的时候，又会由这些层次从下往上依次进行处理，最后返回给用户。
接下来按照从上至下的顺序，依次分析一下各个层次所需要实现的功能。
4.1 用户层软件
用户层作为最接近用户的一个层次，需要向用户提供一些简单易用的交互的接口。一般来说，用户层软件会向用户提供一些与I/O操作相关的库函数，让用户调用这些库函数来对设备进行操作。比如C语言里的printf，就是在显示屏这个I/O设备上打印输出。
既然需要使用I/O设备进行输出操作，所以用户层软件需要请求操作系统提供服务，因为只有操作系统才有对硬件操作的权利，因此用户层软件会使用设备独立性软件这一层向上提供的系统调用接口，来请求操作系统内核的服务。比如printf(“hello world”)这样一句代码，在用户层软件处理完了以后，会把它翻译成等价的write系统调用，当然在进行write调用时，也会填入相应的参数，比如打印输出的内容。
这里注意一下，设备独立性软件向上层提供了系统调用的接口，而设备独立性软件是用来处理系统调用的一个层次。所以有的题目中也会把设备独立性软件这一层称为系统调用处理层。像我们熟悉的Windows操作系统就会向外提供一系列系统调用，但是由于系统调用的格式严格，使用麻烦，因此windows系统在用户层上封装了一系列更方便的库函数接口供用户使用( Windows API)。
4.2 设备独立性软件
设备独立性软件，又被称为设备无关性软件，而与设备的硬件特性无关的功能几乎都在这一层实现。下面看一下这层要实现哪些功能、
像在4.1用户层软件里所说，这一层要实现的第一个功能就是要向上层提供一个统一的调用接口。
第二个要实现的功能是设备的保护。对设备的保护原理类似于对文件的保护，在很多操作系统当中，设备会被看做是一种特殊的文件，而不同的用户对各个文件的访问权限是不一样的。既然设备被看作是一种特殊的文件，相应的不同的用户对设备这种特殊的文件的访问权限肯定也是不一样的，因此操作系统需要提供设备保护的功能。
第三个要实现的功能是差错处理，就是对设备产生的一些错误进行处理。注意，因为差错的类型是有很多的，所以这个地方有印象即可，不需要了解差错处理的细节。
第四个要实现的功能是设备的分配与回收，因为很多设备是一种临界资源，不可以同时分配给多个进程使用，所以操作系统需要对设备这种资源进行分配与回收的管理。
第五个要实现的功能是数据缓冲区管理，数据缓冲区是用来屏蔽各个设备之间数据交换单位大小，还有传输速度的差异。至于具体实现的细节会在后面进行介绍。
第六个要实现的功能是建立逻辑设备名到物理设备名的映射关系，并且根据设备的类型来选择调用相应的驱动程序。
这里说一下逻辑设备名和物理设备名，所谓逻辑设备名就是用户在请求使用一个设备的时候，所提供的名字，也就是用户所看到的设备名。比如说平时在打印店打印的时候，因为打印店里的电脑都会连上很多台打印机，所以在进行打印时，会被让选择哪一台进行打印，在选择时会看到打印机1、打印机2等，这些用户看到的设备名就是逻辑上的设备名。操作系统对这些设备进行管理在背后还会有一个叫做物理设备名的东西。
所以当我们选择某一个逻辑设备的时候，操作系统需要知道这个逻辑设备具体对应的到底是哪一个物理设备。一般来说，这个映射关系是通过一个叫做逻辑设备表的东西来实现的，并且在这个逻辑设备表中，还会记录每一个逻辑设备对应的设备驱动程序的入口地址，如下图。
在上图中可以看到，逻辑设备名还带有类似于文件路径的东西，这就是刚刚所说的，很多操作系统会把设备当做是一种特殊的文件，所以这个文件当然也会有一个存储的路径，每一个表项记录了逻辑设备名到物理设备名的映射关系，并且还记录了这个设备它所对应的驱动程序的入口地址在什么地方。
一般来说会用两种方式来管理逻辑设备表。第一种方式是整个系统只设置一张逻辑设备表，但是由于各个用户在使用设备时，使用的都是逻辑设备名，而操作系统又是根据逻辑设备名来查找逻辑设备表的表项的，所以如果不同的用户使用相同的逻辑设备名，就有可能导致这个逻辑设备到物理设备映射紊乱的问题，所以其实整个系统只设置一张逻辑设备表这种方式，只适用于单用户的操作系统。
第二种方式是为每一个用户设置一张逻辑设备表，采用这种方式不同用户所使用的逻辑设备名可以是重复的，并且相同的逻辑设备名，可以被映射到不同的物理设备上去。
上面还说到另一个问题，就是不同类型的I/O设备需要有不同的驱动程序，这是为什么呢？下面看一下设备驱动程序的概念。
4.3 设备驱动程序
我们在网上搜索打印机会发现有各种品牌的各式各样的打印机，不同品牌的打印机外形不同，并且内部的电子部件（I/O控制器）也有可能是不同的结构，比如假设下图是佳能打印机内部结构。
可以看到佳能打印机内部总共有两个数据寄存器，它的状态寄存器当中0代表空闲，1代表忙碌。
但是换成惠普打印机，其内部结构可能又是另一种样子，如下图：
可以看到惠普打印机内部只有一个数据寄存器，它的状态寄存器当中1代表空闲，0代表忙碌，与佳能打印机刚好相反。
我们将这两个例子总结到下图：
通过例子可以发现，不同型号的设备内部的电子部件有可能是完全不一样的，各个设备内部的硬件特性只有设计者才知道。所以操作系统要通过这些设备的控制器来控制这些设备的具体运行的话，那操作系统肯定需要了解这些设备内部的硬件细节。不过这些IO设备多种多样，所以操作系统不可能了解所有的设备的内部细节，因此这些设备在出厂的时候，一般来说厂家会提供一个与设备对应的驱动程序，然后当要控制某个设备的时候，CPU只需要执行这个设备相对应的驱动程序就可以完成对这个设备控制器的控制。
所以在生活中可以发现，当给计算机插上一个新的机械键盘或鼠标时，在这些设备第一次被插上电脑时，电脑的右下角会有一个正在安装驱动程序的小弹窗，这个自动安装的驱动程序就是由厂家提供的，为了让操作系统实现对新的设备硬件进行具体控制的一个程序。所以设备独立性软件不可以直接操作硬件，必须调用厂家提供的设备驱动程序，由这个设备驱动程序来完成对硬件的具体控制。
各个类型的驱动程序一般来说在系统中会以一个独立进程的方式运行存在。所以再看一下刚刚的逻辑设备表，如下图，为什么不同的设备要对应不同的驱动程序呢，就是因为各种设备内部的硬件特性是不一样的，因此必须执行与它对应的特定的驱动程序，才可以正常的完成对这个设备硬件的控制。比如要使用打印机1，那么操作系统就会查询下图的设备记录表，找到设备对应的驱动程序的入口，然后找到对应的驱动程序。
4.4 中断处理程序
当硬件设备完成I/O操作以后，它会发出一个中断信号，作为I/O应答，系统会根据这个中断信号的类型来找到与这个中断信号对应的中断处理程序，然后执行这个程序，进行中断处理。
中断程序对中断的处理流程如上图。首先，中断处理程序会从I/O控制器（设备控制器）当中读出设备的状态，来判断这一次的I/O是否是正常的结束。如果此次是正常的结束，接下来中断处理程序会从设备控制器的数据寄存器当中读出一个字的数据，并且经由CPU放到内存缓冲区当中，这就完成了一个字的读入。如果此次I/O是非正常结束，系统会根据异常的原因做出相应的处理。这就是中断处理程序所需要做的事情。
当中断处理程序把这一次要输入的数据放到内存之后，接下来会交由设备驱动程序对这些数据进行进一步的处理。等设备驱动程序处理完了以后，又会再交由上一层的设备独立性软件进行再进一步的处理，最后一层一层往上，然后一直返回给用户。所以如果要输入一个数据的话，对这个数据的处理应该是从下往上依次层层处理的。
经过分析可以发现，除了设备驱动程序会直接和硬件打交道以为，中断处理程序也需要直接和硬件打交道。但是再往上的设备独立性软件和用户层软件就不会直接和硬件打交道了。
4.5 I/O软件层次小结
5. 输入输出应用程序接口和驱动程序接口
本节要掌握输入/输出应用程序接口和设备驱动程序接口。其中输入/输出应用程序接口又分为字符设备接口、块设备接口和网络设备接口。另外还需要认识什么是阻塞I/O，什么是非阻塞I/O。
下面首先看一下什么是输入/输出应用程序接口，结合下图理解。
I/O软件分为多个层次，上层的用户应用程序需要通过系统调用的方式来请求使用底层的某一种I/O设备，而I/O设备的种类特性非常的多样化，所以上层的应用程序很难通过一个统一的系统调用接口来操作所以类型的I/O设备。比如像块设备（如磁盘）就是有寻址的概念，同时块设备支持多个字节的读写，因此当我们自己写程序时，要用系统调用的方式从块设备中读入数据，那么read调用就要先指明要操作的是哪个块设备，另外还可以指明此次要读入几个字节，同时还可以指明要从哪个地方开始读。
上面是块设备的读入方法，但这种读入方法显然不适用于字符设备，因此字符设备不可寻址。比如键盘就是最典型的输入型字符设备，键盘是没有地址的概念。所以在用系统调用从键盘中读入一个字符的时候，不可能指明从哪个地址读入。
因此可以看到，由于底层的设备多种多样，对于各种设备的I/O读写，所需要提供的参数也各不相同，因此很显然用户层的应用程序无法用一个统一的系统调用接口来完成所以类型设备的I/O。
所以设备独立软件这一层，需要对上一层的应用程序提供若干种类型的程序接口，上层应用程序如果访问的是字符设备或者块设备和网络设备，那么它所调用的系统调用接口是各不相同的。
下面来分别看一下这三种设备的接口有什么特性：
用户层的软件如果要使用一个字符型设备，要对字符型设备进行读或者写，那么可以采用get和put这两个系统调用，get是从指定的字符设备当中读出一个字符，put是往指定的字符设备当中写入一个字符，数据的读写是以字符为单位的。
块设备的系统调用接口是read和write系统调用，块设备有地址的概念，可以用seek系统调用来指定读写指针要放到磁盘的哪个地址。放到这个地址以后就可以使用read或write往读写指针所指的位置后面读写若干位的字符。
接下来详细说一下可能不是很熟悉的网络设备接口。电脑里会有网卡，这个网卡就是所谓的网络控制器，用于收发网络数据包。显然，电脑上的网络控制器可能会收到很多很多的数据包，而不同的数据包应该丢给不同的应用程序，这时候就要区分这个数据包是给哪个应用程序的。
为了区分网卡接收到的数据包是给哪个应用程序的，网络设备接口(网络套接字接口)，会向上层的应用程序提供socket系统调用，这个系统调用的作用是可以创建一个网络套接字，另外在创建时还需要指明连接的网络协议是什么协议，比如TCP或UDP。
有了网络套接字以后就可以使用bind系统调用，把套接字绑定到本地的某一个端口上，再结合本机的IP地址，这个端口号就可以映射到计算机当中的某一个应用程序上。
在网络设备接口里，设备独立性软件还提供了connect的系统调用，这个系统调用可以把套接字连接到远程的某一个主机上，当网络套接字初始化完毕以后，就可以使用read或write对网络套接字进行数据的读写。
接下来根据图示来理解一下进程是如何使用网络设备接口来实现网络通信的：
如上图，有两台主机，它们之间使用网络进行连接，每一台主机上可能会同时运行多个进程，比如主机1就同时运行了P1和P2两个进程。另外每一台主机都会有一个网络控制器，也就是网卡，用于实现网络数据包的收发。同时每一台主机都会有各自的IP地址，每个进程都会有自己的进程用户空间，同时操作系统内核也会有操作系统内核的空间。
现在P3这个进程要使用网络通信，它可以先使用socket系统调用来创建一个网络套接字(套接字简单理解就是申请一片内核空间用于接收和发送数据)。socket系统调用会给用户进程返回一个描述符(可以理解为就是指向套接字的指针)。有了套接字对象之后，还需要把套接字绑定到本地的某一个端口，比如上图是绑定到6666这个端口，这样主机2的套接字就可以等待着被连接。
同理，主机1也可以进行相同的操作，P1进程也通过socket系统调用，来申请创建一个套接字对象，并通过bind系统调用绑定到本地端口211。
现在两个主机都有了各自的套接字，同时也确定了各自的一个数据收发端口号，接下来一步要做的事情就是使用connect系统调用，把本机的套接字连接到另一台机器的套接字上。比如说可以让主机1的P1进程使用connect系统调用，指明要把fd指向的套接字(P1刚刚申请的套接字)，连接到主机2的6666端口处，这个系统调用就会使得这两个套接字之间建立起一个连接，接下来两个主机就可以通过套接字进行通信。
比如P1现在想给P3发送一个数据包，如下图：
P1首先在自己的用户区准备好这个数据，然后使用write系统调用指明要想fd指向的套接字当中写入数据。
设备独立性软件接收到write系统调用以后，就会把用户进程准备好的数据给复制到内核区，也就是套接字对应的缓冲区当中。这一步设备独立性软件这一层来完成的事情。
现在数据已经放到内核缓冲区里，接下来设备独立性软件这一层会调用网络控制器的驱动程序来处理这片数据，这个驱动程序会负责把准备好的数据给输出到网络设备上。
接下来网络控制器就可以把数据包给发送到网络上。数据包会顺着网线发送到主机2的网络控制器处。
主机2的网络控制器接收到一个数据包以后会向主机发出一个中断信号。主机2的中断处理程序发现中断信号是来自于网络控制器，因此中断处理程序接下来会调用网络控制器的驱动程序，让驱动程序来把网络控制器里收到的数据给它搬到内核的缓冲区里。因为早就知道这个数据应该发送到6666这个端口处，所以数据会被复制到6666这个端口所对应的内核缓冲区里。
现在数据已经一路发到主机2里，接下来P3这个进程要接收一个网络数据包，只需要使用read系统调用指明要从fd所指的这个套接字对象当中读出一个数据包。这个系统调用的结果就是，设备独立性软件会从缓冲区里把数据给复制到用户进程的用户去当中，这样用户进程P3就可以使用它收到的这一块数据。
接下来看一下阻塞I/O和非阻塞I/O的概念：
阻塞I/O就是应用程序发出I/O系统调用，进程需转为阻塞态等待。比如从键盘使用get读入一个字符，那么只要键盘的输入动作没有完成，这个进程就得一直等下去。
非阻塞l/O就是应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。比如write系统调用往磁盘写数据，这个系统调用可以很快的被处理完，然后迅速的返回到用户进程让其继续往下执行。
接下来看一下设备驱动程序接口：
同样从层次结构出发，设备独立性软件需要根据实际操作的设备不同去调用不一样的设备驱动程序。因此，若各公司开发的设备驱动程序接口不统一，则操作系统很难调用设备驱动程序。
所以操作系统会统一一个标准，要求设备的厂商在制作这个驱动程序的时候，按照规定好的统一标准来开发驱动程序，如下图。
而由于不同的操作系统，对设备驱动程序接口的标准各不相同，所以设备厂商还必须根据各操作系统的接口要求，开发相应的设备驱动程序，设备才能被使用。
6. I/O核心子系统
通过前面的学习可以知道，I/O软件层次里的下面三层，即设备独立性软件、设备驱动程序、中断处理程序属于操作系统内核部分，所以这三层也可以被称为I/O核心子系统或简称I/O系统。因此，I/O核心子系统要实现的功能其实就是中间三层要实现的功能，而这三层要实现的功能可以参考上面一节。
在考研中，我们需要重点理解和掌握的功能是：I/O调度、设备保护、假脱机技术( SPOOLing技术）、设备分配与回收、缓冲区管理（即缓冲与高速缓存)。
下面看一下这些功能分别要在哪些层次实现：
在上一节已经强调过，所以和硬件直接相关的肯定是设备驱动程序和中断处理程序需要负责的，但在刚刚提到的功能中，都没有与硬件直接相关的。
其中假脱机技术一般在用户层实现。而I/O调到、设备保护、设备分配与回收和缓冲区管理这几个功能是在设备独立性软件这一层实现。一般来说，假脱机技术都需要使用到磁盘这种设备的设备独立性软件这一层的服务，所以假脱机技术一般来说都是在用户层软件这一层实现。
本部分先主要介绍两个很熟悉的功能的实现，一个是I/O调度，一个是设备保护。
下面首先看一下I/O调度：
I/O调度就是用某种算法确定一个好的顺序来处理各个I/O请求。比如在第四章里学的磁盘调度，就是用某一种算法，来确定应该先满足哪些磁盘的访问请求。由于磁盘也是一种I/O设备，所以磁盘调度也是一种I/O调度的问题。
而I/O调度的算法如上图提到，这些算法我们在前面已经学过，这里不再介绍。
接下来再看一下设备的保护：
设备的保护在上一节已经提及过，因为在UNIX系统中，设备会被看做是一种特殊的文件，因此其实系统也会为各个设备建立一个相应的FCB(文件控制块)，不同的用户对不同的文件是有不同的访问权限的，所以把设备看做是一种特殊的文件，当一个用户想要访问某个设备的时候，系统也会根据设备对应的FCB来判断一下这个用户是否有相应的访问权限。这样就实现了所谓的设备保护的功能，但它其实上也是文件保护那一块所需要做的事情(这个知识点可以参考第四章文件保护的知识)。
7. 假脱机技术
本节假脱机技术知识总览：
首先看一下什么是假脱机技术：
在手工操作阶段，主机直接从I/O设备获得数据，由于设备速度慢，主机速度很快。人机速度矛盾明显，主机要浪费很多时间来等待设备。
所以在批处理阶段，人们引入了脱机技术，刚开始的脱机技术是使用磁带实现的，如下图。
引入了脱机技术以后，程序员可以先用纸带机把自己的程序数据输入到磁带当中，磁带速度要比纸带机要快，而这个输入的过程是一台专门的外围控制机来实现的。
由于程序的数据首先被输入到更快速的磁带当中，而之后CPU可以直接从磁带中读取想要的输入数据，因此这就很大的缓解了这种速度矛盾。 也就是说引入了脱机输入技术以后，在数据输入的时候速度就快了很多。
在数据输出时同理，主机会先把数据输出到一个很快速的磁带上，之后又会由一个外围控制机控制着把磁带当中的数据依次的给输出到慢速的纸带机上。同样的由于磁带的速度的比纸带的速度快很多，因此CPU在输出时就可以节省很多等待输出完成的时间，这样就大大的提升了CPU的利用率。
脱机技术中的脱机，就是指脱离主机的控制进行输入/输出操作，而在上面的介绍中也明白了在脱机技术中，输入输出是由外围控制机来实现的。显然CPU输入输出的过程并不需要主机或CPU的干预和控制，这样CPU就可以有更多的时间去处理别的计算内容。
引入脱机技术后，除了缓解了CPU与慢速I/O设备的速度矛盾。还有另一好处就是，在输入时，即使CPU在忙碌，也可以在外围控制机的控制下提前将数据输入到磁带；而在输出时，即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。
基于脱机技术的思想，人们又发明了假脱机技术，又叫SPOOLing技术，假脱机技术当中的脱机是用软件的方式来模拟实现的。SPOOLing系统的组成如下图：
SPOOLing系统一般来说由上图的部分组成，系统会在磁盘上开辟出两个存储区域，一个是叫输入井，一个是叫输出井。
“输入井”用于模拟脱机输入时的磁带，用于收容I/O设备输入的数据。
“输出井”用于模拟脱机输出时的磁带，用于收容用户进程输出的数据。
除了磁带之外，外围控制机也是实现脱机技术当中一个很重要的部件。外围控制机在假脱机技术里就睡由一个输入进程和一个输出进程来实现的。
“输入进程”模拟脱机输入时的外围控制机，“输出进程”模拟脱机输出时的外围控制机。
显然输入进程和输出进程肯定需要和用户进程并发的执行，才可以完成模拟脱机输入和脱机输出的过程。因此SPOOLing技术肯定是需要有多道程序技术的支持的。
另外还需要注意，在内存当中还会开辟输入缓冲区和输出缓冲区：
输入缓冲区和输出缓冲区的作用就是在模拟脱机输入和脱机输出的时候，作为一个数据的中转站。
输入进程在实现模拟脱机输入的时候，其实是先接收了输入设备的数据，然后把这些数据先放到输入缓冲区里，之后再把输入缓冲区当中的数据放到磁盘的输入井当中
而进行数据输出时，在输出进程的控制下，输出缓冲区用于暂存从输出井送来的数据，之后再传送到输出设备上。
接下来看一个具体的假脱机技术的应用——共享打印机的实现：
在前面的学习中提到过两个概念，一个是独占式设备，一个是共享设备，这两个概念的解释在上图已经给出。
打印机是一种独占式设备，在一段时间内只能为一个用户进程提供服务，如果打印机设备同时处理多个进程的请求的话，就有可能导致各个进程的打印输出结果相互串行。所以对于打印机这个独占式设备来说，如果一个进程正在使用这个打印机，那另一个进程在请求使用打印机的时候必然是需要阻塞等待的。
但是打印机虽然是独占式设备，但可以使用SPOOLing技术改造成共享设备。如下图。
当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
第一件事：在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的而非内存里)，并将要打印的数据送入其中。
第二件事：为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的)，再将该表挂到假脱机文件队列上。
当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。
在采用了假脱机技术以后，虽然系统中只有一台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备)，使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。
因此，SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。
下面对这部分进行小结：
8. 设备的分配与回收
本节设备的分配与回收知识点总览：
首先看一下设备分配时应该考虑的因素：
设备分配时要考虑设备的固有属性、设备的分配算法还有设备分配中的安全性。
从设备的固有属性角度看，设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。
独占设备就是一个时段只能分配给一个进程的设备，如打印机。
共享设备就是可以同时分配个多个进程使用的设备，比如磁盘，但是所谓的这种共享，是宏观上山的共享，微观上各个进程可能是交替的使用设备。
虚拟设备就是采用SPOOLing技术把独占设备改造成的虚拟的共享设备，可同时分配给多个进程使用。
从设备分配算法角度看，可以有很多我们很熟悉的算法进行设备分配，比如先来先服务、优先级高者优先，短任务优先等，这里不再具体赘述。
从设备分配的安全性角度看，可以有如下图的两种分配方式：
注意，如果使用不安全分配方式，一个进程可以同时使用多个设备，但是有可能会发生死锁，所以可以结合第二章死锁的知识，使用银行家算法来避免系统进入不安全状态，即死锁避免。
接下来看一下两种设备分配方式——静态分配和动态分配：
这两种分配方式在第二章死锁的部分也已经讲过，这里也不过多赘述。
下面看一下设备分配管理中需要用到哪些数据结构。在了解这些数据结构之前，先看一下设备、控制器、通道之间的关系，如下图：
一个通道可控制多个设备控制器，每个设备控制器又可以控制多个设备，所以可以把它们之间的关系理解为一个树的形状。
从另一个角度来说，每个设备肯定会有一个它所从属的控制器，而每个控制器也肯定会有一个它所从属的通道。这里要注意，一个系统中可能会有多个通道。
由于控制一个设备肯定需要找到这个设备的控制器，而要控制一个控制器肯定也需要找到控制器所从属的通道。所以设备分配管理中的数据结构需要表示出这种从属的关系。
下面看一下系统中需要配置的第一种数据结构——设备控制表：
系统会为每一个设备配置一张设备控制表，用于记录设备的使用情况。
一个设备控制表当中可能会有如上图所示的一些常用的字段。其中指向控制器表的指针就是上面所说的用于找到一个设备所从属的控制器到底是那一个。
接下来看一下第二种数据结构——控制器控制表：
每一个设备控制器都会对应一张控制器控制表，操作系统会根据控制器控制表的信息对控制器进行操作和管理。
控制器控制表当中也可能会有如上图所示的一些常用的字段。其中指向通道表的指针用于找到一个控制器所从属的通道到底是那一个。
接下来看一下第三种数据结构—通道控制表：
每个通道都会对应一张通道控制表，操作系统根据通道控制表对通道进行操作和管理。
与之前的两个数据结构类似，通道控制表当中也可能会有如上图所示的一些常用的字段。其中操作系统可以通过与通道连接的控制器表首址找到该通道控制的所有控制器的相关信息。
第四个需要设置的系统数据结构叫做系统设备表：
系统设备表当中记录了系统中全部设备的情况，每一个设备会对应一个表目，每个表目中又会记录这个表目所对应的设备的设备类型，比如说是打印机还是扫描仪等。还会记录这个设备的标识符。除此以外，这个表目中还会包含这个设备的控制表。最后还记录了设备的驱动程序的入口。
由于系统设备表当中记录了系统中全部设备的情况，所以用户用设备名请求某一个设备的时候，操作系统是可以从系统控制表当中来找到用户指定的设备到底是哪一个。
接下来分析一下设备分配的具体步骤：
第一步操作系统会根据进程请求的物理设备名查找系统设备表。操作系统用某种方式来查找系统设备表的时候，就会把各个表目当中记录的设备标识符和用户提供的物理设备名进行比对，然后找到这两个参数相匹配的一个表项，之后就可以这个设备对应的设备控制表。
第二步，在找到设备控制表以后，会根据设备控制表中记录的信息来判断此时这个设备是否空闲，如果设备空闲的话，就可以把这个设备分配给进程，如果设备忙碌的话，就需要把进程挂到这个设备对应的等待队列中，一直到这个设备空闲，并且把设备分配给该进程以后，才会把这个进程重新唤醒。除了分配设备之外，还需要把这个设备对应的控制器也分配给这个进程，所以系统还会根据指向控制器表的指针找到这个设备对应的控制器控制表。
第三步，在找到控制器控制表以后，与前面类似，会根据控制器控制表中记录的信息来判断此时这个控制器是否空闲，如果控制器空闲的话，就可以把这个控制器分配给进程，如果控制器忙碌的话，就需要把进程挂到这个控制器对应的等待队列中，一直到这个控制器空闲，并且把控制器分配给该进程以后，才会把这个进程重新唤醒。除了分配控制器之外，还需要把这个控制器对应的通道也分配给这个进程，所以系统还会根据指向通道表的指针找到这个控制器对应的通道控制表。
第四步，在找到通道控制表以后，同理，会根通道控制表中记录的信息来判断此时这个通道是否空闲，如果通道空闲的话，就可以把这个通道分配给进程，如果通道忙碌的话，就需要把进程挂到这个通道对应的等待队列中，一直到这个通道空闲，并且把通道分配给该进程以后，才会把这个进程重新唤醒。
只有设备、控制器、通道三者都分配成功时，这次的设备分配才算成功，之后便可启动I/O设备进行数据传送。
现在思考一下，这个设备分配过程有什么缺点呢？
如上图，首先第一个缺点就是用户编程时需要使用物理设备名，这种方式对用户编程来说是很不方便的。第二个缺点就是用户编程使用的是物理设备名，如果更换设备，则设备名也会更换，此时用户程序就无法运行。第三个缺点是若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待。比如一台电脑连了三台打印机，如果进程请求使用的是第一台打印机，那么虽然第二台和第三台打印机此时有可能是空闲的，只要第一台打印机此时是忙碌的，那这个进程依然需要阻塞等待，但显然其实可以把这个进程的打印任务把它分配给第二台或第三台打印机进行。因此采用这种方式也会导致设备的利用率不高的问题。
解决上述缺点的办法就是建立逻辑设备名与物流设备名的映射机制，这样用户编程时只需要提供逻辑设备名，然后由操作系统完成逻辑设备名到物理设备名的转换。
引入逻辑设备名与物流设备名的映射机制之后，进程在请求使用某种设备的时候只需要提供逻辑设备名，所谓的逻辑设备名就是指明它所要使用的设备类型。
比如说进程想要使用打印机这种设备，那由于系统设备表当中有一个字段记录了设备的类型，因此操作系统可以根据用户提供的逻辑设备名来依次查找系统设备表，然后找到一个指定类型的，并且空闲的设备，把它分配给进程。只有这个类型的设备全部处于忙碌状态的时候，才需要把这个进程给阻塞。
把这个设备分配给进程以后，操作系统还需要在逻辑设备表LUT当中，新增一个表项。
之后的操作就会之前一样，可以根据设备控制表找到相应的控制器控制表，然后把控制器分配给设备。然后根据控制器控制表找到相应的通道控制表，然后把通道分配给设备。
只有进程第一次通过逻辑设备名申请使用一个设备的时候，操作系统才会来查询这个系统控制表，如果之后进程再次以相同的设备名来请求使用设备的话，那操作系统首先做的事，是会在逻辑设备表当中查找这个逻辑设备对应的物理设备，然后找到相应的表项以后，就可以找到设备对应的驱动程序。
有这样的两种方式设置逻辑设备表：
第一种就是整个系统中只有一张逻辑设备表，这样的话各个用户所用的逻辑设备名不允许重复，所以这种方式只适合用于单用户操作系统。
第二种就是每个用户设置一张逻辑设备表，这样的话不同用户的逻辑设备名可以重复，可以适用于多用户操作系统。
下面对本节进行一个小结：
9. 缓冲区管理
缓冲区管理知识点总览：
首先看一下，什么是缓冲区，缓冲区有什么作用：
缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合，如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本。
一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区。
所以本节介绍的缓冲区主要还是围绕内存作为缓冲区这种类型。
下面看一下缓冲区有什么作用：
在内存中可以开辟一小片区域作为缓冲区，如果要输出数据的话，CPU产生的这些数据首先会被放到内存的缓冲区当中，不过CPU速度很快，所以它很快就可以把这个缓冲区给充满。等缓冲区放满了以后，CPU就可以去做别的事情。之后I/O设备就可以慢慢的从缓冲区当中取走数据。在数据输入时也是类似的，I/O设备可以慢慢的把数据放到缓冲区当中，当缓冲区满了以后，CPU再很快速的从缓冲区当中取走数据，所以采用这种方式的话很明显可以缓和CPU和I/O设备之间的速度不匹配的矛盾。
如果说没有采用缓冲区这种策略的话，I/O设备每输入或者每输出一定单位的数据之后，就需要对CPU发出一个中断信号，请求CPU介入处理。假设I/O设备是一种字符型设备，那每输入完一个字符或者每输出一个字符，I/O设备都会打断CPU，向CPU发出中断信号。而对中断的处理是需要付出一定时间代价的，因此CPU频繁的处理这些中断，显然会降低系统的性能。而如果采用缓冲区这种策略，只有缓冲区的数据被全部取走或者输入的数据充满了缓冲区以后，CPU才需要来介入处理中断，因此采用这种方式可以减少CPU的中断频率，放宽CPU对中断响应时间的限制。
缓冲区还有一个作用就是解决数据粒度不匹配的问题。比如说此时在CPU上运行的输出进程，每次可以申请一整块的数据，但I/O设备每次只能输出一个字符。如果没有采用缓冲区策略的话，输出进程只能一个字符一个字符的给I/O设备来传送数据。如果采用缓冲区策略的话，输出进程可以直接把一整块的数据放到缓冲区里，让I/O设备从缓冲区里一个字符一个字符的往外取。输入时同理。
另外，采用缓冲区以后，很显然是可以提供CPU和I/O设备之间的并行性的。
接下来介绍几种缓冲区管理的策略。
首先看一下单缓冲：
假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。
注意，缓冲区有一个特点，当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出;当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
那么看一下对一个数据块的处理需要经历哪些步骤：
首先系统在主存中，为用户进程分配了一块大小的缓冲区，那么这个块设备会产生一块大小的数据把它输入到缓冲区当中，这个过程假设所耗费的时间为T。
之后这块数据需要传送到用户进程的工作区当中，才可以被用户进程所处理（在考研当中，默认用户进程的工作区也是刚好可以放得下一块数据）。这个过程假设所耗费的时间为M。
再之后，用户进程就可以开始对这一块数据进行处理，假设对一块数据进行计算处理所需要的时间为C这么多。当它处理完以后，这个用户进程的工作区就可以被腾空了。
在考研中经常考察的题型是，会让计算每处理一块数据平均需要多长的时间。这里说一个技巧，可以假定一个初始状态，分析下次到达相同状态需要多少时间，这就是处理一块数据平均所需时间。
而在“单缓冲”题型中，可以假设初始状态为工作区满，缓冲区空。所以对于单缓冲，要分析下一次达到工作区满，缓冲区空这样的一个状态需要花多少时间。这个时间长度就是处理一个数据块平均所需要消耗的时间。
下面看单缓冲区的第一种情况，假设输入时间T大于处理时间C：
根据假设条件，刚开始工作区是满的，缓冲区是空的。所以刚开始CPU就可以处理工作区中的这一块数据，这个处理过程需要花费C这么长的时间。另外由于刚开始缓冲区为空，所以块设备可以往其中冲入一块数据，这个时间总共耗费了T这么久。
由于T>C，因此CPU处理完数据后，并不能紧接着将下一块数据传送到工作区，必须等待缓冲区中冲满数据并且把数据传送到工作区以后，才可以进行下一块数据的处理。
显然在T这个时间点缓冲区充满，可以紧接着将这一块数据传送到工作区当中，这个过程又要花费M这么长的时间。
此时经历了T+M这么的时间以后，就再次回到了刚刚假设的初始状态，也就是缓冲区满，工作区空。接下来的数据处理无非就是重复刚刚分析的过程，因此通过刚刚的分析可以发现，平均每处理一块数据的用时是T+M这么多。
下面看第二种情况，假设输入时间T小于处理时间C：
刚开始同第一种情况一样，刚开始工作区是满的，缓冲区是空的。所以刚开始CPU就可以处理工作区中的这一块数据，这个处理过程需要花费C这么长的时间。另外由于刚开始缓冲区为空，所以块设备可以往其中冲入一块数据，这个时间总共耗费了T这么久。
由于这次T<C，因此缓冲区中冲满数据后，暂时不能继续冲入下一块数据，必须等待CPU处理结束后，才能将数据从缓冲区传送到工作区。
显然也是在C这个时间点CPU处理结束，可以紧接着将这一块数据传送到工作区当中，这个过程又要花费M这么长的时间。
此时经历了C+M这么的时间以后，就再次回到了刚刚假设的初始状态，也就是缓冲区满，工作区空。接下来的数据处理同样是重复刚刚分析的过程，因此通过刚刚的分析可以发现，平均每处理一块数据的用时是C+M这么多。
通过分析上面两种情况，可以总结如下图的结论：
结论：采用单缓冲策略，处理一块数据平均耗时Max(C，T)+M。
接下来看一下双缓冲策略：
假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块)。
类似的，双缓冲问题也经常会让计算每处理一块数据平均需要多长的时间。
在双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空。
先看第一种情况，如上图，假设T>C+M：
根据假设的初始状态，缓冲区1中此时是有一块数据的，缓冲区2和工作区是空的。所以在0这个时刻，可以把缓冲区1中的数据传送到工作区当中，这个过程耗时是M这么多。而接下来CPU就可以处理工作区当中的数据，耗时为C。
另一方面，在刚开始缓冲区2是空的，所以刚开始块设备可以往缓冲区2中输入数据，充满缓冲区2总共耗时T。
由于T>C+M，所以虽然在C+M这个时刻，CPU已经把工作区中的数据给处理完了，工作区已经空了。但是由于缓冲区2此时这个时刻还没有充满，所以暂时不能把缓冲区2的数据传送到工作区当中，必须等到T这个时刻，缓冲区2才可以被充满，所以到T这个时刻就回到了假设的初始状态。
因此，当T>C+M的时候，处理一块数据平均用时为T。
下面看第二种情况，假设T<C+M：
刚开始缓冲区2是空的，所以刚开始设备可以往缓冲区2中冲入数据，耗时为T。另一方面，由于刚开始，缓冲区1当中是充满数据的，所以一开始就可以把缓冲区1的数据传送到工作区当中。到M这个时刻工作区会充满，然后CPU就可以开始处理数据，耗时C这么长。
处理完工作区中的数据以后，缓冲区2中也已经充满了下一块的数据，因此接下来可以紧接着把缓冲区2当中的数据传送到工作区当中，接着继续处理工作区中的这一块数据。
接着回头看数据输入的这个过程，在T这个时刻，缓冲区2已经被充满，设备开始空闲。并且，由于缓冲区1当中的数据在M这个时刻就已经被取空了，因此当缓冲区2的数据被充满以后，设备就可以紧接着往缓冲区1中冲入数据，这个耗时也是T这么多。
假设2T<2M+C，则I/O设备将缓冲区1冲满时，缓冲区2的数据尚未取空，因此I/O设备暂时不能冲入数据，只有缓冲区2当中的数据被取空以后，这个设备才可以继续往缓冲区2当中写入下一块的数据。
经过分析可以发现，如果采用双缓冲结构，并且T<C+M，那么很难找到一个和刚开始的初始状态一模一样的一个状态。所以对于这种情况，上面假设的先假定一个初始状态，然后分析下次到达相同状态需要多少时间这种方法就不太好使用了。
但是通过甘特图的方式往下分析可以发现，每经过M+C这么长的时间，就会有一块数据被处理完毕，因此，当T<C+M就意味着设备输入数据块的速度要比处理机处理数据块的速度更快。每处理一个数据块平均耗时C+M。
经过上面的两种情况的分析，可以知道采用双缓冲策略，处理一个数据块的平均耗时为Max(T,C+M)。
下面看一下单缓冲和双缓冲在通信时的区别：
单缓冲和双缓冲策略不仅可以在主机和设备之间的数据传送当中使用，在两台主机通信时，也可以采用这种缓冲策略，用于数据的发送和接收。
如上图，如果说为两台通信的主机配置单缓冲区的话，A主机想要发送的数据，要先放入A主机缓冲区中，等缓冲区满时就可以将数据发送到B缓冲区中。之后，B主机将缓冲区中的数据全部取走后，才能向A主机发送数据。
显然，若两个相互通信的机器只设置单缓冲区，则在任一时刻只能实现数据的单向传输。
为了实现同一时刻双向传输，可以给两台机器配置双缓冲区，其中一个缓冲区用来暂存即将发送的数据，而另一个缓冲区用来接收输入的数据。所以如果采用双缓冲结构，那么这两台主机可以同时往自己的发送缓冲区当中冲入自己想要发送出去的数据，接下来可以同时往对方的接收缓冲区当中冲入数据。这样就实现了同一时刻双向传输的功能。
接下来看另一种缓冲区——循环缓冲区：
很多时候只有两个缓冲区依然不能满足进程的实际需要，所以操作系统可以给一个进程分配多个大小相等的缓冲区，让这些缓冲区连成一个循环的队列。
在上图中，橙色表示已经被充满数据的缓冲区，而绿色表示的是此时为空的缓冲区。系统会保持两个指针用于缓冲区的管理。其中，in指针，指向下一个可以冲入数据的空缓冲区；out指针，指向下一个可以取出数据的满缓冲区。当out指针指向的缓冲区数据被取空以后，out指针就会指向下一个满缓冲区。类似地，如果in指针所指向的缓冲区被充满以后，in指针也需要指向下一个为空的缓冲区。
在考研中，一般来说只有单缓冲和双缓冲需要分析处理一个数据平均所需要的消耗时间，循环缓冲只需要了解大致的原理就可以了。
接下来看一下缓冲池的概念：
缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为:空缓冲队列、装满输入数据的缓冲队列（输入队列)、装满输出数据的缓冲队列(输出队列）。
另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：用于收容输数据的工作缓冲区(hin)、用于提取输入数据的工作缓冲区(sin)、用于收容输出数据的工作缓冲区(hout)、用于提取输出数据的工作缓冲区(sout)。
如果一个输入进程要请求输入一块数据，那么系统会从空缓冲队列的队头当中，取下一块空的缓冲区，把它作为**用于收容输入数据的缓冲区(hin)**，当这块缓冲区被充满以后，就会被挂到输入队列的队尾上。
如果计算进程想要取得一块之前已经输入的数据，那么操作系统会从输入队列的队头取下一个缓冲区，把它作为**提取输入的工作缓冲区(sin)**，接下来这块缓冲区当中的数据会被传送到计算进程的工作区当中，所以这块缓冲区中的数据就被取空了，当它取空之后，这个缓冲区又会被挂回到空缓冲队列的队尾。
如果此时计算进程已经准备好了数据，想要把这些数据冲入到缓冲区，那么系统会从空缓冲队列的队头取下一个空闲的缓冲区，把这个缓冲区作为**收容这个进程想要输出数据的工作缓冲区(hout)**，因此接下来这个缓冲区慢慢的会被充满，由于这块缓冲区的数据接下来是要输出到I/O设备上的，所以这块数据会被挂到输出队列的队尾。
如果某个输出进程请求输出一块数据，那么操作系统会从输出队列中取得一块冲满输出数据的缓冲区作为**提取输出数据的工作缓冲区(sout)**。缓冲区读空后挂到空缓冲区队列。
下面对本节进行一个小结：
10. 磁盘的结构
磁盘的结构知识总览：
首先看一下磁盘、磁道、扇区的概念：
磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。磁盘的结果如上图右。
磁盘的盘面被划分成一个个磁道。如上图左的一个“圈”就是一个磁道。注意，在实际的磁盘中磁道数量会有很多，这里图中因为画不下，所以只画了几道。
而一个磁道又可以被划分成一个个扇区，每个扇区就是一个“磁盘块”。而且各个扇区存放的数据量相同，如1KB，即每个扇区的大小是1KB这么多。注意，不同磁道的扇区大小也是相同的，所以，由于最内侧磁道上的扇区面积最小，因此数据密度最大。
在上图的磁盘结构中还会发现，在磁盘的中间会有一个马达，这个马达转动时就可以带动磁盘的转动。
另外，为了方便查找，可以给扇区进行编号。
接下来看一下怎么从磁盘当中读写数据：
首先，需要把“磁头”移动到想要读/写的扇区所在的磁道。磁头会由磁头臂带动，磁盘会由中间马达带动转起来，让目标扇区从磁头下面划过，这样才能完成对扇区的读/写工作。
如上图左，就是将磁头移动到橙色磁道，并让电机旋转带动磁盘旋转进行橙色磁道数据读取的示意图。
注意，上图左只给了一个盘片，但事实上磁盘当中会有很多个这样的盘片，如下图：
相应的，每个盘面上都会有一个磁头，然后这些磁头都会由磁头臂统一的带动着往里或往外移动。
我们可以对这些盘面进行编号，每个盘面都会对应一个用于读取磁盘数据的磁头。
另外，在有的磁盘当中，一个盘片有可能会对应两个盘面，也就是盘片的正面和背面。
还有一点需要注意的是所有的磁头都是连在同磁臂上的，因此所有磁头只能共进退。
还要知道，磁盘盘面中相对位置相同的磁道组成柱面。
所以对于磁盘的物理地址，我们结合上面的定义，就可以用下图的三元组来表示：
可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。其中柱面号用来定位盘面中某一个磁道，盘面号用来选择到底是哪一个盘面中的磁道，而扇区号用来选择在这个磁道中到底是哪一个扇区。在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号)的地址形式。
所以如果要读取某一个文件在某一个盘块中的数据的话，那么磁盘会根据这个地址来找到磁盘块对应的位置，具体步骤如下：
①根据“柱面号”移动磁臂，让磁头指向指定柱面；
②激活指定盘面对应的磁头；
③磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写。
接下来看一下，磁盘有哪些分类：
按照磁头是否可以移动划分，有下图两种：
按照盘片是否可以更换也有下图两种分类：
最后对本部分进行小结：
11. 磁盘调度算法
本节知识点总览：
本节首先要掌握一次磁盘读/写操作需要多久的时间，应该怎么计算，计算时会从寻道时间、延迟时间和传输时间三个部分入手。而磁盘调度算法的不同会影响寻道时间的长短，所以选择一个合适的调度算法对磁盘整体的性能是有很大影响的。这里要重点掌握上图列出的四种算法。
首先看一下一次磁盘的读或写操作需要多久的时间。
磁盘的读写操作需要时间包含三部分，分别是寻道时间、延迟时间、传输时间。上图给出了这三个部分的详细计算已经介绍，这里就不再对其计算过程进行重复。
从上图的公式中可以看到，延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。所以操作系统唯一可以影响的时间就是寻道时间，根据不同的磁盘调度算法，寻道时间会有很大差异。
接下来就看一下各种磁盘调度算法：
首先看一下先来先服务算法：
所谓先来先服务算法就是根据进程请求访问磁盘的先后顺序进行调度。
这里根据上图给出的例子，可以看到，按照先来先服务的规则，按照请求到达的顺序，磁头需要依次移动到55、58、39、18、90、160、150、38、184号磁道，磁头总共移动了498个磁道。响应一个请求平均需要移动55.3个磁道。
所以先来先服务算法的优点就是公平；如果请求访问的磁道比较集中的话，算法性能还可以。缺点是如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，会有很多时间浪费在寻道上。
接下来看第二种磁盘调度算法——最短寻找时间优先：
最短寻找时间优先算法会优先处理的磁道是与当前磁头最近的磁道。这样可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优。)
根据上图还是之前的例子，可以看到，按照最短寻找时间优先的规则，磁头需要依次移动到90、58、55、39、38、18、150、160、184号磁道，磁头总共移动了248个磁道。响应一个请求平均需要移动27.5个磁道。
最短寻找时间优先算法的优点是性能较好，平均寻道时间短。缺点是可能产生“饥饿”现象。比如本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话，150、160、184号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象。
产生饥饿的原因在于：磁头在一个小区域内来回来去地移动。为了解决饥饿的问题，人们又提出了扫描算法。
接下来看第三种磁盘调度算法——扫描算法：
SSTF算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
如上图例子，假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道，此时磁头就会从100的位置一直增大，直到移动到200号磁道，才会开始回来往磁道号变小的方向移动。
在磁头访问磁道的过程中，磁头总共移动了282个磁道，平均响应一个请求需要移动31.3个磁道。
这种扫描算法的优点是性能较好，平均寻道时间较短，不会产生饥饿现象。但缺点也很明显有两点：①只有到达最边上的磁道时才能改变磁头移动方向，如上例，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了，但是该算法依然会向右移动到最大磁道处才返回。②SCAN算法对于各个位置磁道的响应频率不平均。比如假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离；而响应了184号磁道的请求之后，磁头往返之后很快又可以再次响应184号磁道的请求。
下面就来看一下对于扫描算法的这两个缺点的改进：
首先看扫描算法的第一个缺点，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。为了解决这个问题，人们提出了LOOK调度算法。
LOOK调度算法规定，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。(边移动边观察，因此叫LOOK。)
如上图还是同一个例子，只不过此次磁头往磁道号增大的方向移动不需要移动到200了，当移动到184号磁道时，此时在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。
在这个过程中，磁头总共移动了(184-100)+(184-18)= 250个磁道，响应一个请求平均需要移动250/9= 27.5个磁道（平均寻找长度)。
经过改进可以看到，比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。
下面看对扫描算法的第二个缺点的改进：
SCAN算法对于各个位置磁道的响应频率不平均，为了解决这个问题，于是循环扫描(C-SCAN)算法就出现了。
循环扫描(C-SCAN)算法规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
如上图，还是同一个例子，假设C-SCAN算法只有在向右移动时才会处理磁道访问请求，而且根据C-SCAN算法的规定，磁头只有到了最边上的磁道才能改变磁头移动方向。磁头返回途中不处理任何请求。
在这个过程中，磁头总共移动了(200-100)+(200-0)+(9o-0)= 390个磁道，响应一个请求平均需要移动390/9 =43.3个磁道（平均寻找长度)。
所以C-SCAN比起SCAN来，对于各个位置磁道的响应频率很平均。但是缺点也一样，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。另外，比起SCAN算法来，C-SCAN平均寻道时间更长。
为了应对这个问题，人们效仿LOOK调度算法，提出了C-LOOK调度算法。
C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。
C-LOOK算法规定，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
如上图，同样的例子，假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。使用C-LOOK算法在磁头移动到184处时，在磁头移动方向上已经没有别的请求，这是就可以让磁头返回。而磁头只需要返回到最靠近边缘的、并且需要访问的磁道上即可，并不需要回到最左边边缘处。
在这个过程中，磁头总共移动了(184-100)+(184-18)+(90-18)= 322个磁道，响应一个请求平均需要移动322/9= 35.8个磁道(平均寻找长度)。
很明显C-LOOK比起C-SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。
下面看一下本部分小结：
这里注意一点，若题目中无特别说明，则默认题目中的SCAN算法就是LOOK算法，C-SCAN算法就是C-LOOK算法。
12. 减少磁盘延迟时间的方法
我们意识到了一次读磁盘或者写磁盘的操作，需要寻道时间、延迟时间和传输时间这样三个部分组成。其中延迟时间指的是把目标扇区转到磁头下面所花的时间。如上图，比如说我们此时要读取橙色的这些区域的话，那么我们首先需要有一段延迟时间是用来转动磁盘的，让橙色区域放到这个磁头的下面。
假设现在要连续读取橙色区域的2、3、4扇区，磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停地旋转。因此，如果2、3号扇区相邻着排列，则读完2号扇区后无法连续不断地读入3号扇区，必须等盘片继续旋转，3号扇区再次划过磁头，才能完成扇区读入。
所以，由于磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。
面对上面的这个问题，我们可以采用交替编号的方式来处理：
所谓交替编号，就是让逻辑上相邻的扇区在物理上有一定的间隔。如上图，我们编好了0号扇区后，并不是在它后面紧接着就规定1号扇区，而是在间隔了一个扇区后，才把下一个扇区编为1号扇区。然后依次类推。
假设现在这个磁头指向0号扇区位置，如果接下来要读入的是2号、3号和4号扇区，那由于首先要读入的是2号扇区，所以需要先转动磁盘让2号扇区放到磁头下面，接下来在这个磁盘继续转动的过程中就可以把2号扇区的数据给堵住了。在读完了2号扇区之后，磁头需要有一小段时间做中间的准备，在这段时间内，磁头是不能读入任何数据的，但是由于采用了交替编号的策略，所以在3号扇区划过磁头前，这个磁头就做好了下一次读取数据的准备。因此，这个磁盘继续旋转，3号扇区从磁头下面划过，磁头也可以顺利的把3号扇区里的数据给读进来。
从上面这个过程中可以看到，采用交替编号这样的策略，可以使读取连续的逻辑扇区所需要的延迟时间更小。
接下来探讨一个磁盘地址结构的问题：
通过之前的学习可以知道，磁盘的物理地址是按(柱面号，盘面号、扇区号)这种顺序的一个三元组，现在思考一下，为什么不是(盘面号，柱面号，扇区号)这种顺序的一个三元组呢？也就是说，为什么柱面号一定要在前，盘面号一定要在后？这里来分析一下这个问题。
用上图的磁盘为例，假设这个磁盘有8个柱面/磁道（假设最内侧柱面/磁道号为0 )，4个盘面，8个扇区。则可用3个二进制位表示柱面，2个二进制位表示盘面，3个二进制位表示扇区。
若物理地址结构是（盘面号，柱面号，扇区号)，且假设现在需要连续读取物理地址(00, 000,000) ~ (00,001,111）的扇区。
首先(00,000,000) ~ ( 00, 000,111 )这些扇区就是0号盘面0号柱面的8个扇区，根据之前的分析可以知道，在转了一圈之后，这个磁头可以依次读入0123这几个扇区的数据。再转第二圈后，这个磁头可以依次读入4567这几个扇区的数据，也就是说(00,000,000) ~ ( 00, 000,111 )这个物理地址范围内的数据只需要转两圈就可以读完。之后再读取物理地址相邻的区域(00,001,000) ~ ( 00,001,111)，即0号盘面1号柱面的8个扇区，这时由于柱面号变了，所以需要启动磁头臂，将磁头移动到下一个磁道。
通过之前的学习可以知道，启动磁头臂还有移动磁头是一种物理上的移动，它所需要花费的时间是比较高的，这是盘面号在柱面号之前的情况，下面看一下盘面号在柱面号之后的情况。
若物理地址结构是(柱面号，盘面号，扇区号)，假设此时需要读取的取物理地址依然是(000,00,000) ~ (000,01,111)的扇区。
同样的，首先要读取(00,000,000) ~ ( 00, 000,111 )即0号盘面0号柱面的8个扇区，根据上面的分析可以知道，这部分需要转两圈才可以读完。
接下来还要读取(00,001,000) ~ ( 00,001,111)范围内的数据，但是这里采用的是(柱面号，盘面号，扇区号)即柱面号在前，盘面号在后的物理地址结构，所以(00,001,000) ~ ( 00,001,111)对应的是0号柱面1号盘面的8个扇区。而由于柱面号/磁道号相同，只是盘面号不同，因此不需要移动磁头臂，只需要激活相邻盘面的磁头即可。并不需要像之前一样要启动磁头臂，然后来回移动磁头。
因此磁盘的物理地址是(柱面号，盘面号，扇区号)而不是(盘面号，柱面号，扇区号)的原因，就是读取地址连续的磁盘块时，采用(柱面号，盘面号，扇区号)的地址结构可以减少磁头移动消耗的时间。
理解了上面的问题之后，接下来再看第二种减少延迟时间的方法——错位命名：
先来看一下，不采用错位命名方式在读取编号连续的扇区会发生什么情况。
假设0号盘面和1号盘面在它们相对位置相同的这些扇区的编号都是相同的，也就是0号盘面的0号扇区下面，对应的刚好是1号盘面的0号扇区，然后0号盘面的4号扇区下面对应的也是1号盘面的4号扇区，这些扇区号是一一对应的，两个盘面对应的磁头也是指向一个相对位置相同的地方。
现在假设这个0号盘面的橙色区域对应的扇区编号的物理地址为(000,00,111)，由于磁盘的地址结构是(柱面号，盘面号，扇区号)，所以与这个扇区序号相邻的下一个扇区的编号应该是(000,01,000)，也就是1号盘面的0号扇区，即上图右的橙色区域。
由于所有盘面都是一起连轴转的，因此读取完磁盘块(000,00,111)之后，需要短暂的时间处理，而盘面又在不停地转动，因此当（000,01,000)第一次划过1号盘面的磁头下方时，并不能读取数据，只能再等该扇区再次划过磁头。
为了解决上述问题，可以使用错位命名的方式来命名，如下图：
错位命名就是就将相邻盘面中的偏下方的盘面的扇区编号向后移动一位，以达到与上方盘面错开编号的目的，如上图的0号盘面和1号盘面就是错位命名，可以看到，0号盘面在1号盘面正上方，0号盘面的0号扇区它的正下方对应的是1号盘面的7号扇区，然后0号盘面的4号扇区下面对应的也是1号盘面的0号扇区，也就是说这些盘面的扇区编号是错开的，这就是为什么叫错位命名。
还是使用上面的例子作分析，由于采用错位命名法，因此读取完磁盘块( 000,00,111)之后，还有一段时间可以用于处理，当(000,01,000)第一次划过1号盘面的磁头下方时，就可以直接读取数据，从而减少了延迟时间。
下面对本节进行一个小结：
13. 磁盘的管理
本节知识点总览：
首先看一下什么是磁盘初始化：
磁盘刚被制造出来时，只被划分成了一个一个的磁道，在磁盘正式出厂之前，还需要进行一个低级格式化的过程，这个过程就是一个划分扇区的过程。一个扇区通常可分为头、数据区域、尾三个部分组成。每个扇区的数据区域所能存放的数据数量都是相同的，比如512B，所以前面说的一个扇区可以存放的数据大小，其实指的是数据区域可以存放的大小。
另外，在文件的物理结构的部分说过一种链式结构，也就是把文件的那些数据块用链接的方式把它们连起来，那前一个数据块指向下一个数据块的指针就可以保存在尾部这个部分。也就是说链接部分并不需要占用数据区域，这样的话可以方便操作系统的管理。
除此以外，管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)。
在正式使用磁盘之前，还需要对磁盘进行逻辑上的分区，每个分区由若干个相邻的柱面组成，这里所谓的分区就是我们平时熟悉的C盘、D盘等。
在划分了分区以后，需要进行逻辑格式化。逻辑格式化所做的事情就是创建文件系统，包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表)。
上面是磁盘初始化时要做的事情，接下来看一下什么是磁盘的引导块：
在磁盘完成了物理格式化、磁盘分区和逻辑格式化以后，就可以把操作系统相关的数据写到磁盘中，也就是安装操作系统的一个过程。
计算机开机时需要进行一系列初始化的工作（包括初始化CPU、内存等），这些初始化工作是通过执行初始化程序（自举程序）完成的。一般来说，初始化程序是存放在ROM（只读存储器）中的，而ROM中的数据在出厂时就写入了(一般来说，ROM在出厂时就直接集成在了电脑主板上)，并且以后不能再修改。
也就是说，计算机开机时，首先会读取ROM当中的程序，并且执行这些程序完成初始化的工作。但是思考一下，把初始化程序程序（自举程序）放在ROM中存在什么问题？
假设自举程序需要更新的话就会很不方便，因为ROM当中的数据是无法更改的，但是由于自举程序本身又比较复杂，所以不太可能保证自举程序相关的数据永远不改变。对于这个问题，应该如何解决呢？
那现在的操作系统一般是只在ROM当中存放很小的一个自举装入程序，而完整的自举程序放在磁盘的启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置。比如上图指向C盘的几个盘块，这几个盘块就可以称为启动分区或者叫引导块。
当计算机开机的时候，首先会先执行ROM当中的自举装入程序，在执行自举装入程序的过程中，CPU就可以知道接下来需要执行的自举程序是存放在硬盘当中的哪个位置。通过自举装入程序的引导，CPU就可以从磁盘中读取完整的自举程序，这样的话就可以完成初始化。
自举装入程序的复杂度不高，所以其实是可以保证自举装入程序是不会出错的，不需要更改的。而自举程序需要更改的话，就把自举程序放在磁盘的固定位置，这样的话当自举程序需要更新的时候，就只需要重新把这些引导块当中的数据，把它重新更新一下就可以。所以这种方案带来的好处就是自举程序更新会变得很方便。
一般来说，拥有启动分区(启动块、引导块)的磁盘称为启动磁盘或系统磁盘。
接下来再看一下对磁盘的坏块应该进行什么样的管理：
所谓的坏块就是指那些坏了、无法正常使用的扇区。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。
对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表(文件分配表)上标明。被标记为坏块的块，之后不再分配给任何一个文件。由于操作系统在对存储空间进行管理时肯定需要读取文件分配表的内容，而哪些块是坏块是记录在文件分配表当中的，因此采用这种方式的话，坏块对这个操作系统是不透明的。
对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表，并在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。另外，磁盘控制器会保留一些“备用扇区”，用于替换坏块。比如操作系统想使用一个本来已经坏掉的块，那么在硬件层次，磁盘控制器这个硬件部件就会用其中的某一个好的备用块来替换这个坏块，但是这个过程对操作系统是透明的，操作系统是不可知的。这种方案也称为扇区备用。
上面就是对磁盘坏块管理的两种方法。下面对本节进行一个小结：
