计算机操作系统第8章设备管理

8.1 设备管理概述 8.2 I/O控制方式 8.3 缓冲技术 8.4 设备分配 8.5 磁盘的驱动调度 8.6 Spoling技术的实现举例 习题,一个计算机系统一般是由主板、磁盘、处理机和主存储器等组成的，对于一个计算机系统，如果配备上不同的外设，可以使得系统功能变得更强大。例如，配上光盘驱动器、声卡和音箱，可以欣赏音乐、播放电影；装上调制解调器(MODEM)，可以上网浏览各种信息和查阅资料。可见，配备上各种各样的外设，可以使系统功能越来越强大。而设备管理的功能就是如何对这些外设进行有效管理，使其最大可能地为用户服务。,8.1 设备管理概述,操作系统中设备管理的关键是如何提高设备的利用率，即如何使得设备并行工作，主要体现在两方面：设备和CPU的并行，设备和设备之间的并行，从而使系统中的各种设备尽可能地处于忙碌状态。操作系统的设备管理不仅仅是提高设备的利用率，还要方便用户使用。操作系统设备管理中通过屏蔽设备的物理特性，实现了设备独立性，使得用户对设备的使用与物理设备无关。,计算机系统中的设备大多数属于独占设备，即要互斥地使用。而为了提高设备的利用率，对设备的分配一般要采用动态分配方式，这时操作系统使用虚拟设备技术对外部设备进行管理，使得既可以动态分配，又不会产生死锁。以上叙述的是设备管理中主要解决的几个问题，本章中将重点解决。,8.1.1 设备分类目前，世界各国都在加速建设信息化，信息化的建设推动了计算机科学技术的发展，随着计算机技术的迅猛发展和计算机应用领域的不断扩展，相应的，外部设备的品种、类型和数量也不断增加，外部设备在计算机硬件系统的成本中所占的比重也不断上升。在计算机系统中的外设种类繁多、型号各异，性能、功能、价格相差甚多，下面从不同的角度对设备进行分类。,1按设备的使用特性分类(1) 存储型设备，指的是以存储大量信息和快速检索为目标，它在系统中作为主存储器的扩充，所以又称为辅助存储器，如磁盘机、磁带机。(2) 输入、输出型设备，输入指的是从外界向计算机传送信息，输出指的是计算机向外界传送信息。输入和输出设备使得计算机和外部世界可以进行信息交换，如显示器、卡片机、打印机等。,2. 按信息组织分类(1) 块设备：块指的是连续信息所组成的一个区域，块设备则是指每次与内存交换进行信息交换的单位是一个或几个块的信息，这类设备用于存储信息。存储型设备一般为块设备，典型的块设备是磁盘。(2) 字符型设备：指的是以字符为单位与内存进行信息的交换，即一次交换一个字节或多个字节。一般的输入型和输出型设备为字符型设备。,3. 按传输速率分类(1) 低速设备：是指其传输速率仅为每秒钟几个字节至数百个字节的一类设备。典型设备有键盘、鼠标、语音的输入和输出等设备。(2) 中速设备：是指其传输速率在每秒钟数千个字节至数万个字节的一类设备。典型设备有行式打印机、激光打印机等。(3) 高速设备：是指其传输速率在数百千个字节至数十兆字节的一类设备。典型设备有磁带机、磁盘机、光盘机等。,4. 从资源分配角度分类(1) 独占设备：是指这类设备被分配给一个作业后，被这个作业所独占使用，其他的任何作业不能使用，直到该作业释放该设备为止。例如，某个进程正在使用打印机，其他进程则不能使用该打印机，否则会产生输出结果混乱的情况。,(2) 共享设备：是指允许多个用户共同使用的设备。如磁盘、磁鼓等设备，可由多个进程同时进行访问。共享设备的“同时使用”的含义是指多个作业可以交替启动共享设备，当一个作业正在使用设备时其他作业暂时不能使用，即每一时刻仍然只有一个作业占用，但是当一个作业暂时不使用，其他作业就可以启动设备使用。(3) 虚拟设备：指的是通过某种技术把独占设备虚拟成共享设备(虚拟设备)，如Spooling系统，使用硬盘模拟输入设备(输入井)和打印机(输出井)。,8.1.2 设备控制器设备控制器是CPU与I/O设备间的接口，它接收从CPU发来的命令，并去控制I/O设备工作，使处理机从繁杂的设备控制事务中解脱出来。设备控制器是一个可编址设备，当它仅控制一个设备时，它只有一个唯一的设备地址；若控制器可连接多个设备，则应具有多个设备地址，使每一个地址对应一个设备。,1. 设备控制器的功能1) 接收和识别命令CPU可以向控制器发送多种不同的命令，例如可以向软盘控制器发送读、写和格式化等命令，设备控制器应能接收并识别这些命令。因此，设备控制器应该具有相应的控制寄存器来存放所接收的命令和参数，并对命令进行译码。,2) 数据交换数据交换，指实现CPU与控制器之间、控制器与设备之间的数据交换。对于前者是通过数据总线，由CPU将数据写入控制器，或是从控制器中读出数据；而对于后者是设备将数据写入控制器或是从控制器传送到设备。所以设备控制器需要设置数据寄存器来存放有关数据。3) 设备状态的了解和报告控制器记录所连接设备的状态以供CPU了解。例如，用户进程想要使用某设备，只有当该设备处于就绪状态时，CPU才能启动设备控制器从设备中读出数据。为此，要在控制器中设置一个状态寄存器，用其中的每一位反映设备的某一状态。,4) 地址识别我们知道内存中的每个单元都有一个地址，系统中的设备和内存一样，每一个设备都有一个物理地址，设备控制器必须能够识别它所控制的所有设备的地址，因此，在设备控制器中还要设置地址译码器。,2. 设备与控制器之间的接口一般地，设备并不是直接与CPU进行通信，而是与设备控制器通信。因此，在设备与设备控制器之间应有一个接口。该接口中通常有三种类型的信号：数据信号、控制信号和状态信号，如图8-1所示。,图8-1 设备与控制器之间的接口,1) 数据信号设备控制器和设备之间要进行信息的交换，对于输入是指由设备发送给设备控制器；对于输出是由设备控制器发送到设备的比特流。 2) 控制信号指由设备控制器发送给设备的，用于规定设备执行读或写操作的信号或是其他操作的信号。 3) 状态信号 用于指示当前设备的状态。例如，设备正在读或写等。,3. 设备控制器的组成由于设备控制器处于CPU与设备之间，它既要与CPU通信，又要与设备通信，还应具有按照CPU所发来的命令去控制设备工作的功能。每个控制器主要是一些与CPU通信的寄存器，操作系统向控制器发送命令启动设备工作，如启动磁盘进行读操作，设备控制器收到命令后，CPU可以转去做其他的工作，而设备在控制器的控制下完成I/O操作。当命令执行结束后，控制器发出中断信号，CPU接收到中断信号后，转去中断处理，CPU可以在设备控制器的数据寄存器中取得执行结果。因此，一般的设备控制器由以下三部分组成，如图8-2所示。,图8-2 设备控制器,1) 设备控制器与处理机的接口设备控制器与处理机的接口主要完成CPU和设备控制器之间的通信，既可以是CPU向控制器传送命令或数据，也可以是控制器向CPU提供输入数据及相关的设备状态信息等。2) 设备控制器与设备的接口对于一个设备控制器可以连接一个或是多个设备，所以设备控制器中包含有多个接口，每个接口用于连接一个设备，而每个接口中包含数据、控制和状态三种类型的信号。,3) I/O逻辑 设备控制器主要是通过I/O逻辑来实现对设备的控制。I/O逻辑通过一组控制线与处理机进行通信，处理机通过该逻辑向设备控制器发送命令，该逻辑对命令进行译码，并选择一个设备进行控制。例如，系统要启动某个设备进行工作时，CPU将命令发送到设备控制器的控制寄存器中，同时通过数据总线将地址发送给设备控制器，设备控制器的I/O逻辑对地址进行译码，选择一个对应的设备，启动运行。,8.1.3 I/O通道在CPU和I/O之间增加了设备控制器后，CPU只需要向设备控制器传送相应的命令，设备控制器可以接收并识别此命令来启动设备完成输入和输出工作，这时CPU可以进行其他工作，实现了CPU和I/O设备的并行工作，提高了资源的利用率。但是CPU的负担仍然很重，因为在控制器的控制之下设备一般只完成若干字节的数据的传输后会向CPU发送中断信号，CPU会被频繁地中断，进行中断处理使得CPU的利用率低下。为此，在CPU和设备控制器之间又增设了I/O通道。其目的是要把CPU从繁杂的I/O任务中解脱出来，由通道来承担一些原来由CPU处理的I/O任务。,实际上，I/O通道是一种特殊的处理机。它是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外设实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入、输出操作可以和CPU并行操作。但I/O通道又与一般的处理机不同，主要表现在以下两个方面：一是其指令类型单一，这是由于通道硬件比较简单，其所能执行的命令主要局限于与I/O操作有关的指令，即通道程序；二是通道没有自己的内存，通道所执行的通道程序是放在主机的内存中的，也就是说通道与CPU共享内存。,当系统要启动某个设备进行工作时，CPU可以向通道发送命令，余下的时间CPU可以转去处理其他的事件，当通道接收到命令后将会独立于CPU去执行自己的通道程序，控制设备完成输入和输出功能，当输入、输出完成后，通道向CPU发送中断信号。综上所述，引入通道后，大大提高了CPU和设备的并行度。根据信息交换方式的不同，可把通道分成以下三种类型：字节多路通道、数组选择通道和数组多路通道。,1字节多路通道字节多路通道，如图8-3所示，包含一个主通道和许多分别连接在低、中速I/O设备上的非分配型子通道，子通道按时间片轮转方式共享主通道，按字节方式进行数据传送。具体而言，当第一个子通道控制其I/O设备完成一个字节的交换后，便立即腾出字节多路通道(主通道)，让给第二个子通道使用；当第二个子通道也交换完一个字节后，又把主通道让给第三个子通道使用，依此类推。循环一周后，重新返回到第一个子通道去使用主通道。,图8-3 字节多路通道,2数组选择通道字节多路通道一般适于连接中、低速设备，当连接高速设备时，可能会造成数据的丢失，因此它不适于连接高速设备，基于这一点，则推动了按数组方式进行数据传送的数组选择通道的形成。数组选择通道可以连接多台高速设备，但是它只含有一个分配型子通道，在一段时间内只能执行一道通道程序，控制一台设备进行数据传送。因此，当某台设备占用了该通道后，便一直由它独占，即使是它并没有数据要进行传送，此时通道虽然是空闲的，但是也不允许其他设备使用该通道，直到该设备传送完毕释放该通道为止。由此可见，数组选择通道的利用率很低。,3数组多路通道数组选择通道虽有很高的传输速率，但它却每次只允许一个设备传输数据。数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道分时并行操作的优点相结合而形成的一种新通道。其含有一个主通道和多个分别连接在高、中速I/O设备上的非分配型子通道，子通道按时间片轮转方式共享主通道，按数组方式进行数据传送，因而既具有很高的数据传输速率，又能获得令人满意的通道利用率。,现代计算机系统采用自成独立系统的通道结构，主存储器与外围设备之间传送信息的输入输出操作由通道完成，只要中央处理器(CPU)启动了通道，通道就能按指定的要求独立地完成输入输出操作。然后中央处理器就可做与输入输出操作无关的其他工作，从而使计算机系统获得了中央处理器与外围设备之间并行工作的能力。一旦CPU发出指令，启动通道，则通道独立于CPU工作，一个通道可以连接多个控制器，可以是树形配置，也可交叉配置，如图8-4所示。,图8-4 通道结构,一般的，通道的价格昂贵，使得计算机系统中所配置的通道数量较少，这又往往使它成为I/O的瓶颈，进而造成整个系统吞吐量的下降。如图8-5所示，为了启动设备4，必须用到通道1和控制器2；若二者已被其他设备占用，则无法启动设备4。类似的，若要启动设备1和2，由于它们都要用到通道1，因而也不可能启动。这就是由于通道不足所产生的“瓶颈”问题。,图8-5 单通路I/O系统,解决因通道不足而产生的瓶颈问题的最有效方法是，增加设备到主机间的通路而不是增加通道，如图8-6所示。换言之，就是把一个设备连接到多个控制器上，而一个控制器又连接到多个通道上。这种多通路方式不仅可以解决瓶颈问题，而且能够提高系统的可靠性，也不会因为个别通道或控制器的故障而使设备与存储器之间无法建立通路，进行数据传输。,图8-6 多通路I/O系统,8.2.1 程序I/O方式在早期的计算机系统中，由于无中断机构，处理机对I/O设备的控制，采取程序I/O方式。程序I/O方式是最简单的I/O控制方式。这种方式由用户进程直接控制CPU与外设之间的数据传输。 由于数据传送过程中输入和输出的情况比较类似，下面只给出输入数据时的工作过程(程序I/O方式的流程图如图8-7所示)。,8.2 I/O控制方式,(1) I/O指令启动输入设备数据时，要同时把状态寄存器中忙/闲标志置为1。(2) 测试忙/闲标志。若为“1”，表示输入机尚未输完一个字，处理机应继续对该标志测试；若为“0”，表明数据已输入到控制器的数据寄存器中，转(3)。(3) 处理机将数据取出送入内存单元，完成一个字的I/O。程序I/O方式简单、易于实现，但是存在一些缺点：(1) CPU和外设之间只能串行工作。由于CPU的速度要远远高于外设的速度，所以，CPU大部分的时间都是在不断地测试设备的状态，使得CPU的利用率很低。,(2) 在某一段时间内，CPU只能和一台外设进行数据交换，这样使得外设之间也只能够串行工作，外设的利用率较低。(3) 程序I/O方式是通过不断地检测设备的状态来控制数据的传输，所以，不能发现设备和其他硬件所产生的错误。,图8-7 程序I/O方式流程图,8.2.2 中断控制方式在现代计算机系统中，对I/O设备的控制，广泛采用中断控制方式。在I/O设备输入每个数据的过程中，由于无须CPU干预，因而可使CPU与I/O设备并行工作。当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器便按照该命令的要求去控制I/O设备。此时，CPU与I/O设备并行操作。,在中断控制方式下，数据传输的过程如下(中断控制方式的流程图如图8-8所示)：(1) 进程需要数据时，通过CPU向指定的设备发出指令，启动该设备进行输入操作并将设备控制器的状态寄存器中的中断位打开，允许中断程序被调用执行。(2) 该进程放弃处理机，等待输入的完成。操作系统进程调度程序调度其他就绪进程占用处理机。(3) 当输入完成时，输入设备向CPU发出中断请求信号。CPU在接收到中断信号之后，转向中断处理程序。,(4) 中断处理程序首先保护现场，然后把输入缓冲寄存器中的数据传送到某一个特定单元中去，同时将等待输入完成的那个进程唤醒，进入就绪状态，最后恢复现场，并返回到被中断的进程继续执行。在此后的某段时间内，进程调度程序会选中这个由阻塞变为就绪状态的进程。,与程序I/O方式相比，中断控制方式提高了CPU的利用率，例如，从终端输入一个字符的时间约为100 ms，而将字符送入终端缓冲区的时间小于0.1 ms。若采用程序I/O方式，CPU约有99.9 ms的时间处于忙等待中。 采用中断驱动方式后，CPU可利用这99.9 ms的时间去做其他事情，而仅用0.1 ms的时间来处理由控制器发来的中断请求。可见，中断驱动方式可以成百倍地提高CPU的利用率。但是也存在一些问题：,(1) 设备控制器的数据寄存器通常只能放一个字节的数据，从而使得数据传输过程中会频繁地发生中断，每次中断都需要CPU花费时间去处理。(2) 在计算机系统中配置有很多的外设，如果这些外设都采用中断控制方式，中断的次数会急剧增加，造成CPU的负担过重，难于应付，可能会导致数据丢失。,图8-8 中断控制方式流程图,8.2.3 DMA方式使用中断控制方式进行数据传输时是以字节为单位进行的，如果使用这种方式进行块设备的数据传输，如按一块512字节计算，一块数据的输入输出就需要中断512次，显然效率是比较低的。因此，对于块设备，不能采用中断控制方式，而要采用DMA方式。DMA(Direct Memory Access)方式又称直接存储器访问方式。其基本思想是在外设和主存之间开辟直接的数据交换通路。DMA方式在进行数据传送时以数据块为基本单位，在设备和内存之间进行数据的交换。对于DMA方式，仅在传送一个或多个数据块的开始和结束时，才需中断CPU，请求干预；整块数据的传送过程是在DMA控制器控制下完成的，不需要CPU的干预。,DMA方式下，数据的输入过程是：当某个进程请求输入一批数据时，先将要传送的数量和内存缓冲区地址分别送到计数器和内存地址寄存器，启动设备并允许中断；此后，请求者进程进入阻塞状态，等待数据输入完成；DMA硬件把数据读入数据缓冲寄存器，DMA得到总线控制权，将数据存入指定的内存单元，然后释放总线的控制权，调整内存的地址和计数器值，直到计数器值为0则表示这一批数据输入结束，停止I/O操作并发出中断信号。CPU接收到信号后转去中断处理，中断处理程序将唤醒因等待输入而被阻塞的进程，当进程调度程序再次选择该进程时，将会按照指定的内存地址使用输入的数据。,中断方式是在数据缓冲寄存器满之后发出中断，要求CPU进行中断处理，而DMA方式则是在所要求传送的数据块全部传送结束时要求CPU 进行中断处理，这就大大减少了CPU进行中断处理的次数。中断方式的数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下，不经过CPU控制完成的。这就排除了CPU因并行设备过多而来不及处理以及因速度不匹配而造成数据丢失等现象。,在DMA方式中，由于I/O设备直接同内存发生成块的数据交换，因此I/O效率比较高。由于DMA技术可以提高I/O效率，因此在现代计算机系统中，得到了广泛的应用。许多输入输出设备的控制器，特别是块设备的控制器，都支持DMA方式。,DMA方式较前面的控制方式，大大减少了中断的次数，但是仍存在局限性：(1) DMA方式对外设的管理和操作仍然是由CPU控制的，若系统中外设的种类繁多，I/O的数据量就会增加，对外设的管理和控制会很复杂。(2) 设备多时会增加冲突。当外部设备越来越多时，多个DMA控制器同时使用，可能会引起内存地址的访问冲突。,8.2.4 通道控制方式I/O通道方式是DMA方式的发展，它可以进一步减少CPU的干预，实现CPU、通道和I/O设备三者的并行工作，从而更有效地提高了整个系统的资源利用率。通道控制方式的数据传输过程如下：(1) 当进程要求设备输入时，CPU发出指令指明I/O操作、设备号和对应通道。(2) 对应通道收到CPU发来的启动指令后，读出内存中的通道指令程序、设置对应设备的控制状态寄存器的初值。,(3) 设备按通道指令的要求，把数据送往内存指定区域。(4) 若传送结束，I/O控制器发中断信号，请求CPU做中断处理。(5) 中断处理结束后，CPU返回到被中断的进程处继续执行。(6) 当进程调度程序选中这个已得到数据的进程后，才能进行加工处理。在通道控制方式下，通道控制设备的运行，同时又独立于CPU运行，所以在此方式下实现了CPU、通道和外设的并行工作。,在现代操作系统中，几乎所有的I/O设备在与处理机(内存)交换数据时，都使用了缓冲区。因为提高I/O速度和设备的利用率，在很大程度上都需要借助于缓冲技术来实现。缓冲技术是两种不同速度的设备之间传输信息时平滑传输过程的一种常用手段。它可以提高外部设备的利用率，尽可能使外设处于忙状态。在操作系统中引入缓冲的主要目的有以下几点：(1) 缓和处理机和I/O设备之间速度不匹配的矛盾。(2) 减少对CPU的中断次数。(3) 提高CPU和I/O设备之间的并行性。,8.3 缓 冲 技 术,缓冲管理的主要功能就是管理好缓冲区，并提供获取和释放缓冲区的方法，操作系统主要提供了以下几种缓冲形式。1) 单缓冲单缓冲是操作系统提供的最简单的一种缓冲形式。单缓冲是在设备和处理机之间设置一个缓冲区。每当一个进程发出一个I/O请求时，系统便在主存中为之分配一个缓冲区，该缓冲区用来临时存放输入/输出数据。例如，假设有一批数据，现在要读入该数据并打印出来，系统采用单缓冲方式，CPU和打印机的工作过程是这样的：当CPU将数据读入缓冲区时，打印机是空闲的，当打印机工作时，从缓冲区中取出数据打印，这时CPU是空闲的。所以在单缓冲下，CPU和外设是串行工作的。,2) 双缓冲 解决外设之间并行工作的最简单的办法是设置双缓冲。在双缓冲方案中，具体的做法是为输入或输出操作设置两个缓冲区buffer1和buffer2。CPU可以先读入一部分数据放入buffer1，装满后，当打印机在打印buffer1中的数据时，可以再向buffer2中读入另一部分数据。当buffer1中的数据打印完毕，buffer2中的数据也输入完成后，这时可以在打印buffer2的同时，向buffer1中继续输入数据，这时CPU和打印机都处于忙碌的状态，即并行工作。,双缓冲方式和单缓冲方式相比，虽然双缓冲方式能进一步提高CPU和外设的并行程度，并能使输入设备和输出设备并行工作，但在实际系统中却很少采用这种方式，因为计算机系统中的外设很多，又有大量的输入和输出，同时双缓冲很难匹配设备和CPU的处理速度。因此现代计算机系统中一般使用环形缓冲或缓冲池结构。,3) 环形缓冲环形缓冲技术是在主存中分配一组大小相等的存储区作为缓冲区，并将这些缓冲区链接起来，每个缓冲区中有一个指向下一个缓冲区的指针，最后一个缓冲区的指针指向第一个缓冲区，这样n个缓冲区就成了一个环形。此外，系统中有个缓冲区链首指针指向第一个缓冲区。环形缓冲区结构如图8-9所示。,图8-9 环形缓冲,4) 缓冲池将系统内所有的缓冲区统一管理起来，就形成了能用于输入/输出的缓冲池。缓冲池通常由若干大小相同的缓冲区组成，是系统的公用资源，任何进程都可以申请使用缓冲池中的各个缓冲区。对于既可用于输入又可用于输出的公用缓冲池，其中至少应含有三种类型的缓冲区：空(闲)缓冲区、装满输入数据的缓冲区和装满输出数据的缓冲区。,为了管理上的方便，可将相同类型的缓冲区链成一个队列，于是可形成以下三个队列：空缓冲队列，是由空缓冲区所链成的队列；输入队列，是由装满输入数据的缓冲区所链成的队列；输出队列，是由装满输出数据的缓冲区所链成的队列。缓冲区可以在四种方式下工作，如图8-10所示。(1) 收容输入工作方式。当输入进程需要输入数据时，从空缓冲队列的队首取一个空缓冲区用作收容输入缓冲区。输入设备将数据输入收容输入缓冲区并装满，并将此缓冲区挂到输入队列队尾。,(2) 提取输入工作方式。当计算进程需要输入数据时，从输入队列队首取一个装满数据的缓冲区用作提取输入缓冲区。CPU从提取输入缓冲区中取出数据至用完，并将空缓冲区挂到空缓冲队列队尾。(3) 收容输出工作方式。当计算进程需要输出数据时，从空缓冲队列队首取一个空缓冲区用作收容输出缓冲区。CPU将数据输入其中并装满，将收容输出缓冲区挂到输出队列队尾。(4) 提取输出工作方式。当输出进程需要输出数据时，从输出队列队首取一个装满输出数据的缓冲区用作提取输出缓冲区。输出设备从中取出数据至用完，并将空缓冲区挂到空缓冲队列队尾。,图8-10 缓冲区的工作方式,8.4.1 设备分配的原则设备分配的原则是根据设备本身固有的特性、用户要求和系统配置情况决定的，总的原则是：(1) 高效率，即要充分发挥设备的使用效率，使设备尽可能忙；(2) 安全性，即要避免不合理的分配方法造成进程死锁；(3) 与物理设备无关性，即用户面对的是逻辑设备，分配程序根据当前请求以及设备分配情况在相应类别的设备中选一个空闲物理设备并将其分配给申请者。常用的设备分配方式有静态分配和动态分配两种方式。,8.4 设 备 分 配,1. 静态分配静态分配方式的基本思想是在用户作业运行之前，由系统按照作业的资源清单，一次性将其需要的所有资源(包括控制器、通道)全部分配给它。采用此方式，一旦分配之后，设备资源一直为该作业所占用，直到该作业被撤离(正常终止或因故撤销)。针对独享设备，系统一般采用静态分配方式，即在一个作业执行前，将它所需要使用的这类设备分配给它，当作业结束撤离时，才将分配给它的独享设备收回。,对于静态分配方式，由于作业所需要的全部资源在运行之前已经得到满足，所以在运行过程中不会再提出资源请求，所以该作业可以顺利完成并释放其所占有的全部资源给系统，这时其他进程可以申请使用，因此，静态分配方式不会出现死锁。但缺点是很明显的，设备的使用效率低，因为作业在运行过程中只需要使用部分资源，而其他资源是闲置的，根据静态分配的思想在作业运行结束之前将一直占有资源，使得其他的进程想用但不能用，造成资源的严重浪费。,2. 动态分配动态分配方式是根据进程在执行过程中提出设备输入输出请求而实施的一种分配方式。对共享设备的分配一般采用动态分配方式。进程具有异步性，以“走走停停”的方式运行，进程只要拥有部分资源就可以启动运行，在运行过程中可以向系统提出资源的请求，系统可以根据当前资源的分配情况来决定是否满足用户的需要，这样，进程可能会因为申请某种资源得不到而陷入阻塞的状态，或是得到资源继续运行。采用动态分配方式资源的利用率被大大提高了，但是在分配的过程中，可能会出现系统中的进程因互相等待对方的资源而陷入一种僵局的状态，即死锁。,8.4.2 设备独立性设备独立性是指用户程序申请使用设备时，只需要指定逻辑设备名，而不用指定具体的物理设备，系统根据当前的请求及设备分配的情况，在相同类别设备中，选择一个空闲设备，并将其分配给一个申请进程。这样，通过屏蔽设备的物理特性使得用户可以方便地使用系统中的设备。,实现设备独立性具有以下几个优点：(1) 提高了资源的利用率，系统中的某类设备可能有多个，用户在使用设备时不需要指定设备的物理位置。实际上，系统中的该类设备还有空闲的设备2，但是由于用户指定的是物理地址，所以有空闲设备也得不到满足，因此，采用指定物理位置的方式，资源的利用率是很低的。而如果采用逻辑名进行访问，上述情况下用户A就可以得到满足，提高了资源的利用率。(2) 方便用户，用户不需要知道设备的状态和具体使用情况，用户只需要给出逻辑设备名就可以申请使用设备。,8.4.3 Spooling技术Spooling技术是一种虚拟设备技术，它可以把一台独占设备改造成虚拟设备。为了缓解CPU和I/O设备之间的矛盾，引入了脱机输入、脱机输出技术。该技术是利用专门的外围处理机，将低速I/O设备上的数据送入到高速的磁盘上，或者相反。,事实上，当系统引入多道程序设计技术后，完全可以利用两道程序来模拟脱机输入时的外围机和脱机输出时的外围机的功能。这样，就可以在主机的控制下，实现脱机输入、脱机输出功能，此时的外围操作和CPU对数据的处理是同时进行的，把这种在联机情况下实现的同时外围操作称为Spooling，或者称为假脱机操作。Spooling技术是对脱机输入、输出系统的模拟。相应的，Spooling系统必须建立在具有多道程序功能的操作系统之上。Spooling系统主要由以下几部分组成(如图8-11所示)。,图8-11 Spooling系统,1. 输入井和输出井输入井和输出井是在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘，用于存储I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于存储用户进程计算产生的输出数据。2. 输入缓冲区和输出缓冲区 输入缓冲区和输出缓冲区是在内存中开辟的一个存储区域。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。,3. 输入进程和输出进程输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机经过输入缓冲区再送入输入井，之后，当CPU需要输入数据时，则直接由输入井读至内存。输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据先由内存送到输出井暂存，当输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。下面通过一个例子来看看Spooling系统是如何实现虚拟分配的。,通过上述分析，假脱机系统具有如下几个特点：(1) 提高了I/O速度。从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作，如同脱机操作一样，提高了I/O速度，缓和了CPU与低速I/O设备之间速度不匹配的矛盾。(2) 设备并没有分配给任何进程。在输入井或输出井中，分配给进程的是一个存储区和建立一张I/O请求表。(3) 实现了虚拟设备功能。多个进程同时使用一个独占设备，而对每一进程而言，都认为自己独占这一设备，不过，该设备是逻辑上的设备。,8.5.1 磁盘的结构磁盘是一种高速、大容量、旋转型的存储设备，由若干张盘片构成，它能把信息记录在盘片上，也能把盘片上的信息读出。每个盘片有正反两面，每一面称为一个盘面，盘面被划分成磁道，由外向内编号，称为磁道号，例如0磁道、1磁道等。若干张盘片可以组成一个盘组，一个盘组中的盘片都被固定在一个轴上。各盘面上序号相同的磁道构成柱面，由外向内编号，例如0柱面、1柱面等。,8.5 磁盘的驱动调度,磁盘的主要类型分为固定头磁盘和移动头磁盘两种。1固定头磁盘这种磁盘在每条磁道上都有一个读/写磁头，所有的磁头都被装在一个钢性磁臂上。通过这些磁头可访问所有磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。这种结构的磁盘主要用于大容量磁盘上。,2移动头磁盘每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单，故仍广泛应用于中小型磁盘设备中。,要往磁盘写数据或是从磁盘中读取数据时，磁盘的访问时间主要由以下几部分组成。1) 寻道时间Ts寻道时间是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即：Ts=mn+s其中，m是一常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2 ms；对高速磁盘，m0.1 ms，磁臂的启动时间约为2 ms。这样，对一般的磁盘，其寻道时间将随寻道距离的增加而增大，大体上是530 ms。,2) 旋转延迟时间T旋转延迟时间是指扇区移动到磁头下面所经历的时间。对于硬盘，典型的旋转速度大多为5400 r/min，每转需时11.1 ms，平均旋转延迟时间T为5.55 ms；对于软盘，其旋转速度为300 r/min或600 r/min，这样，平均T为50100 ms。,3) 传输时间Tt传输时间是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关：,其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与T相同，因此，可将访问时间Ta表示为：,所以磁盘访问时间可以简单用一个公式来表示： 访问时间=寻道时间+旋转时间+存取时间,8.5.2 磁盘的驱动调度算法 系统中有多个进程请求磁盘操作时，系统要根据一定的策略来决定访问者的执行次序，常用的磁盘调度算法有先来先服务、最短寻道时间优先和扫描算法。1. 先来先服务先来先服务调度算法是最简单的磁盘调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。,如果现在磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面号为98，183，37，122，14，124，65，67，那么，当53号柱面上的操作结束后，移动臂将按请求的先后次序先移到 98号柱面，最后到达67号柱面，采用先来先服务算法如图8-12所示。,图8-12 先来先服务调度算法,从图8-12中可以看到采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂将来回地移动，读写磁头总共移动了640个柱面的距离。先来先服务算法花费的寻道时间较长，从而导致执行输入输出操作的总时间也很长。,2. 最短寻道时间优先“最短寻道时间优先调度算法”总是从等待访问者中挑选寻道时间最短的那个作业请求执行，而不管访问者来到的先后次序。还是采用上一个例子来讨论，现在当53号柱面的操作结束后，应该先处理65号柱面的请求，然后到达67号柱面执行操作。随后应处理37号柱面的请求(它与67号柱面相距30个柱面)而不是98号柱面的请求(它与67号柱面相距31个柱面)，后继操作的次序应该是14，98，122，124，183。如图8-13所示。,图8-13 最短寻道调度算法,从图8-13中可以看到采用最短寻道时间优先算法决定等待访问者执行输入输出操作的次序时，读写磁头总共移动了236个柱面的距离。与先来先服务算法相比，大幅度地减少了寻道时间，因而缩短了为各请求访问者服务的平均时间，也就提高了系统效率。,3. 扫描算法(Scan算法，又称电梯算法)扫描算法，总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客A，B，C，他们的要求是：A在2层等待去10层；B在5层等待去底层；C在8层等待上15层。电梯管理员不是按照乘客来到的先后次序服务，而是考虑电梯的效率。在这种情况下，沿电梯运动方向总是先把乘客C带到15层，然后把乘客B带到底层，最后再把乘客A送到10层。,仍采用同一例子来讨论“电梯调度”算法的情况，由于该算法是与移动臂的方向有关，所以，应分两种情况来讨论。1) 移动臂是向外移的当前正在53号柱面执行操作的读写磁头是由移动臂由里向外(向0号柱面方向)带到53号柱面的位置，因此，当访问53号柱面的操作结束后，沿臂移动方向最近的柱面是37号柱面。所以，应先为37号柱面的访问者服务，然后是为14号柱面的访问者服务。之后，由于外移方向已无等待访问者，故改变臂的移动方向，由外向里依次为各访问者服务。可见，在这种情况下为等待访问者服务的次序是37，14，65，67，98，122，124，183，如图8-14(a)所示。,2) 移动臂是向里移的当前正在53号柱面执行操作的读写磁头是由移动臂由外向里(向柱面号增大方向)带到53号柱面的位置，因此，当访问53号柱面的操作结束后，沿臂移动方向最近的柱面是65号柱面。所以，应先为65号柱面的访问者服务，然后按臂里移方向依次为67，98，122，124，183柱面的访问者服务。当183号柱面的操作结束后，里移方向已无等待访问者，故改变臂的移动方向，由里向外依次为37，14柱面的访问者服务，如图8-14(b)所示。,由图8-14可以看到，当移动臂原来是由里向外移动(向柱面号减小方向)时，读写磁头共移动了208个柱面的距离；当移动臂原来是由外向里移动(向柱面号增大方向)时，读写磁头共移动了299个柱面的距离。,“电梯调度”与“最短寻道时间优先调度算法”都是要尽量减少移动臂移动时所花的时间，所不同的是“最短寻道时间优先调度算法”不考虑臂的移动方向，总是选择距当前读写磁头最近的那个柱面的访问者，这种选择可能导致移动臂来回改变移动方向；“电梯调度”是沿着臂的移动方向去选择离当前读写磁头最近的那个柱面的访问者，仅当沿臂移动方向无等待访问者时才改变臂的移动方向。由于移动臂改变方向是机械动作，故速度相对较慢。相比之下，电梯调度算法是一种简单、实用且高效的调度算法。但是，在实现时除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向。,图8-14 电梯调度算法,1. 实验内容Spooling算法模拟实验。2. 实验目的通过模拟Spooling算法操作过程，了解Spooling技术特点及操作过程。3. 实验题目设计一段程序模拟Spooling算法，要求系统中两个进程同时向一台共享打印机输出信息，通过Spooling技术同步打印进程，以实现正确的打印输出。,8.6 Spooling技术的实现举例,4. 实验提示(1) Spooling是为了能够使多个用户共享同一物理I/O设备而采用的一种虚拟技术。它主要包括三个部分： 输入井和输出井。 输入缓冲区和输出缓冲区。 输入进程SPi和输出进程SPo。该算法是通过输入井和输出井模拟物理I/O设备，并暂存用户的I/O数据的。通过输入进程和输出进程操作物理I/O设备，从而实现将一个物理I/O设备虚拟成多个软I/O，这样在进程访问I/O设备时每个进程就都能以独享的方式访问软I/O。从而简化了进程的I/O操作，提高了进程对I/O的访问速度。,(2) 题目中只要求模拟输出操作，可以只在程序中模拟输出设备、输出井和输出缓冲区。输出到打印机的部分是通过一个函数将要输出的内容显示在屏幕上模拟的。两个进程可以定义两个进程控制块来表示。为了使模拟更真实，两个进程输出信息所用的时间多少由用户输入指定，具体输出的信息随机产生。(3) 系统中的进程可用进程控制块PCB表示，如表8-1所示。,表8-1 PCB结构,(4) 在主函数中随机调用打印进程和Spooling进程。当调用打印进程时将要打印的内容输出到虚拟的打印设备输出井，存储在输出缓冲区中。当调用Spooling进程时，输出进程从输出缓冲区读出打印数据并输出到物理设备打印机中去，完成打印操作。(5) 主要变量及函数说明，如表8-2所示。,表8-2 主要变量及函数说明,5. 实例代码/SPOOLING算法实例 spooling.c/运行环境Redhad9.0 gcc 4.0#include stdio.h#include stdlib.h#include time.h/进程控制块PCB结构struct pcb ,6. 结果分析正如运行结果显示的一样，两个进程同时使用打印机并完成打印操作。两个进程打印时只是将打印信息输出到各自的虚拟输出设备中，真正到物理设备的输出是通过Spooling的输出进程完成的。,1. 试说明设备控制器的组成。2. 为了实现CPU与设备控制器间的通信，设备控制器应具备哪些功能？ 3. 什么是字节多路通道？什么是数组选择通道和数组多路通道？ 4. 如何解决因通道不足而产生的瓶颈问题？ 5. 有哪几种I/O控制方式？各适用于何种场合？ 6. 试说明 DMA 的工作流程。,习 题,7. 引入缓冲的主要原因是什么？ 8. 为何要引入设备独立性？如何实现设备的独立性？ 9. 何谓设备虚拟？实现设备虚拟时所依赖的关键技术是什么？ 10. 试说明 Spooling系统的组成。 11. 磁盘访问时间由哪几部分组成？每部分时间应如何计算？ 12. 目前常用的磁盘调度算法有哪几种？每种算法优先考虑的问题是什么？13. 以一台打印机为例，简述Spooling技术如何实现虚拟设备。,