第五章设备管理

1、广州商学院计算机系广州商学院计算机系 kyykyy5.1 I/O硬件原理硬件原理5.2 I/O软件原理软件原理5.3 缓冲技术缓冲技术5.4 驱动调度技术驱动调度技术5.5 设备分配设备分配5.6 虚拟设备虚拟设备第五章 设备管理广州商学院计算机系广州商学院计算机系 kyykyy计算机的外部设备分为两类：存储型设备、I/O型设备n设备管理要克服设备和CPU速度不匹配所引起的问题n设备管理的主要功能n设备中断处理n设备的分配和去配n设备驱动调度n缓冲区管理n虚拟设备及其实现n系统将所有设备都定义为文件广州商学院计算机系广州商学院计算机系 kyykyyn5.1.1 I/O系统系统n5.1.2 I/

2、O控制方式控制方式 n5.1.3 设备控制器设备控制器5.1 I/O5.1 I/O硬件原理硬件原理广州商学院计算机系广州商学院计算机系 kyykyynI/O设备及其接口线路、控制部件、通道和管理软件称为I/O系统。nI/O操作指的是计算机的主存和外围设备的介质之间的信息传送操作。5.1.1 I/O系统系统广州商学院计算机系广州商学院计算机系 kyykyy处理器内存I/O设备I/O设备I/O设备I/O设备I/O设备广州商学院计算机系广州商学院计算机系 kyykyy处理器内存I/O设备I/O设备I/O设备I/O设备I/O设备控制器控制器控制器广州商学院计算机系广州商学院计算机系 kyykyy处理器

3、内存I/O设备I/O设备I/O设备I/O设备I/O设备通道通道通道广州商学院计算机系广州商学院计算机系 kyykyy处理器内存I/O设备I/O设备I/O设备I/O设备I/O设备通道控制器通道控制器控制器控制器广州商学院计算机系广州商学院计算机系 kyykyyn按照按照I/O特性特性,I/O可分为：可分为：n输入型设备输入型设备n输出型设备输出型设备n存储型设备存储型设备n顺序存取存储设备顺序存取存储设备n直接存取存储设备直接存取存储设备n按照按照I/O信息交换的单位可分为：信息交换的单位可分为：n字符设备字符设备n输入型设备和输出型设备一般为字符设备，与内存进输入型设备和输出型设备一般为字符设

4、备，与内存进行信息交换的单位是字节行信息交换的单位是字节n块设备块设备n存储型设备一般为块设备存储型设备一般为块设备I/OI/O设备类型设备类型广州商学院计算机系广州商学院计算机系 kyykyyn按照按照I/OI/O控制器功能的强弱，以及和控制器功能的强弱，以及和CPUCPU之间联系方式之间联系方式的不同，对的不同，对I/OI/O设备的控制方式分类：设备的控制方式分类：n轮询方式轮询方式n中断方式中断方式nDMADMA方式方式n通道方式通道方式n主要差别：中央处理器和设备并行工作的方式和程度主要差别：中央处理器和设备并行工作的方式和程度不同。不同。5.1.2 I/O控制方式控制方式广州商学院计

5、算机系广州商学院计算机系 kyykyy1 、轮询方式、轮询方式n又称程序直接控制方式，使用查询指又称程序直接控制方式，使用查询指令测试设备控制器的忙闲标志位，确令测试设备控制器的忙闲标志位，确定主存和设备是否能交换数据定主存和设备是否能交换数据n如正运行的程序需从设备读入一批数如正运行的程序需从设备读入一批数据，则该程序设置交换字节数和数据据，则该程序设置交换字节数和数据读入主存的起始地址，然后向设备发读入主存的起始地址，然后向设备发出查询指令，设备控制器便把状态返出查询指令，设备控制器便把状态返回给回给CPU。n如果如果I/O操作忙或未就绪，则重复测试操作忙或未就绪，则重复测试过程，继续查询

6、过程，继续查询n否则开始数据传送，否则开始数据传送，CPU从从I/O接口（接口（控制器寄存器）读取一个字，再用存控制器寄存器）读取一个字，再用存储指令保存到主存储指令保存到主存n如果传送尚未结束，再次向设备发出如果传送尚未结束，再次向设备发出查询指令，直到全部数据传送完成查询指令，直到全部数据传送完成否开始读外设状态 就绪传送一个字到内存修改计数值是是否设置计数值完成完成结束I/O广州商学院计算机系广州商学院计算机系 kyykyy2 中断方式中断方式现代计算机系统中，都毫无例外地引入了中断机构，致使现代计算机系统中，都毫无例外地引入了中断机构，致使对对I/OI/O设备的控制，广泛采用中断方式，

7、即当某进程要启动设备的控制，广泛采用中断方式，即当某进程要启动某个某个I/OI/O设备工作时，便由设备工作时，便由CPUCPU向相应的设备控制器发出一向相应的设备控制器发出一条条I/OI/O命令，然后立即返回继续执行原来的任务。设备控制命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定器于是按照该命令的要求去控制指定I/OI/O设备。此时，设备。此时，CPUCPU与与I/OI/O设备并行操作。例如，在输入时，当设备控制器收到设备并行操作。例如，在输入时，当设备控制器收到CPUCPU发来的读命令后，便去控制相应的输入设备读数据。一发来的读命令后，便去控制相应的输入设备

8、读数据。一旦数据进入数据寄存器，控制器便通过控制线向旦数据进入数据寄存器，控制器便通过控制线向CPUCPU发送一发送一中断信号，由中断信号，由CPUCPU检查输入过程中是否出错，若无错，便向检查输入过程中是否出错，若无错，便向控制器发送取走数据的信号，然后再通过控制器及数据线控制器发送取走数据的信号，然后再通过控制器及数据线将数据写入内存指定单元中。将数据写入内存指定单元中。广州商学院计算机系广州商学院计算机系 kyykyy在在I/OI/O设备输入每个数据的过程中，由于无需设备输入每个数据的过程中，由于无需CPUCPU干预，干预，因而可使因而可使CPUCPU与与I/OI/O设备并行工作。仅当输

9、完一个数据时，才设备并行工作。仅当输完一个数据时，才需需CPUCPU花费极短的时间去做些中断处理。可见，这样可使花费极短的时间去做些中断处理。可见，这样可使CPUCPU和和I/OI/O设备都处于忙碌状态，从而提高了整个系统的资源利设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐量。例如，从终端输入一个字符的时间约为用率及吞吐量。例如，从终端输入一个字符的时间约为100 100 msms，而将字符送入终端缓冲区的时间小于，而将字符送入终端缓冲区的时间小于0.1 ms0.1 ms。若采用查。若采用查询询I/OI/O方式，方式，CPUCPU约有约有99.9 ms99.9 ms的时间处于忙的时

10、间处于忙等待的过程中。等待的过程中。但采用中断驱动方式后，但采用中断驱动方式后，CPUCPU可利用这可利用这99.9 ms99.9 ms的时间去做其的时间去做其它的事情，而仅用它的事情，而仅用0.1 ms0.1 ms的时间来处理由控制器发来的中断的时间来处理由控制器发来的中断请求。可见，中断驱动方式可以成百倍地提高请求。可见，中断驱动方式可以成百倍地提高CPUCPU的利用率。的利用率。 广州商学院计算机系广州商学院计算机系 kyykyy虽然中断驱动虽然中断驱动I/OI/O比程序比程序I/OI/O方式更有效，但须注意，它仍是以方式更有效，但须注意，它仍是以字字( (节节) )为单位进行为单位进行

11、I/OI/O的，每当完成一个字的，每当完成一个字( (节节) )的的I/OI/O时，控制时，控制器便要向器便要向CPUCPU请求一次中断。换言之，采用中断驱动请求一次中断。换言之，采用中断驱动I/OI/O方式时方式时的的CPUCPU是以字是以字( (节节) )为单位进行干预的。如果将这种方式用于块设为单位进行干预的。如果将这种方式用于块设备的备的I/OI/O，显然是极其低效的。例如，为了从磁盘中读出，显然是极其低效的。例如，为了从磁盘中读出1 KB1 KB的的数据块，需要中断数据块，需要中断CPU 1KCPU 1K次。如果次。如果I/OI/O设备能直接与主存交换数设备能直接与主存交换数据而不占

12、用据而不占用CPU,CPUCPU,CPU的利用率还可提高的利用率还可提高, ,这就出现了直接存储器这就出现了直接存储器存取存取DMADMA方式。方式。该方式的特点是：该方式的特点是：(1) (1) 数据传输的基本单位是数据块数据传输的基本单位是数据块，即在主机与，即在主机与I/OI/O设备之间，设备之间，每次传送至少一个数据块；每次传送至少一个数据块； (2) (2) 仅在传送一个或多个数据块的开始和结束时，才需仅在传送一个或多个数据块的开始和结束时，才需CPUCPU干预，干预，整块数据的传送是在控制器的控制下完成的整块数据的传送是在控制器的控制下完成的。可见，可见，DMADMA方式较之中断驱

13、动方式，又是成百倍地减少了方式较之中断驱动方式，又是成百倍地减少了CPUCPU对对I/OI/O的干预，进一步提高了的干预，进一步提高了CPUCPU与与I/OI/O设备的并行操作程度。设备的并行操作程度。 3 DMA方式方式广州商学院计算机系广州商学院计算机系 kyykyyDMA 控制器的组成DRMARDCCRI/O控控制制逻逻辑辑。主机主机控制器接口控制器接口 控制器与块设备接口控制器与块设备接口count内存内存CPU命令命令系统总线系统总线DMA控制器控制器命令命令/状态寄存器状态寄存器(CR)。用于接收从。用于接收从CPU发来的发来的I/O命令，或有关控制信息，命令，或有关控制信息，或设

14、备的状态或设备的状态;主存地址寄存器主存地址寄存器(MAR):存放主存中需要交换的数据的地址存放主存中需要交换的数据的地址.DMA传送前传送前,由程由程序送入首地址序送入首地址,在在DMA传送中传送中,每交换一次数据每交换一次数据,把地址寄存器内容加把地址寄存器内容加1;数据缓冲寄存器或数据缓冲区数据缓冲寄存器或数据缓冲区(DR):暂存每次传送的数据暂存每次传送的数据; 字计数器字计数器(DC):记录传送数据的总字数记录传送数据的总字数,每传送一个字每传送一个字,字计数器减字计数器减1设备地址寄存器设备地址寄存器:存放存放I/O设备信息设备信息,如磁盘的柱面号、磁头号、扇区号等如磁盘的柱面号、

15、磁头号、扇区号等.中断机制和控制逻辑。中断机制和控制逻辑。广州商学院计算机系广州商学院计算机系 kyykyy 虽然虽然DMADMA方式比起中断方式来已经显著地减少了方式比起中断方式来已经显著地减少了CPUCPU的干预，的干预，即已由以字即已由以字( (节节) )为单位的干预减少到以数据块为单位的干预，为单位的干预减少到以数据块为单位的干预，但但CPUCPU每发出一条每发出一条I/OI/O指令，也只能去读指令，也只能去读( (或写或写) )一个连续的数据一个连续的数据块。而当我们需要一次去读多个数据块且将它们分别传送到不块。而当我们需要一次去读多个数据块且将它们分别传送到不同的内存区域，或者相反

16、时，则须由同的内存区域，或者相反时，则须由CPUCPU分别发出多条分别发出多条I/OI/O指令指令及进行多次中断处理才能完成。及进行多次中断处理才能完成。 I/OI/O通道方式是通道方式是DMADMA方式的发展，它可进一步减少方式的发展，它可进一步减少CPUCPU的干的干预，即把对一个数据块的读预，即把对一个数据块的读( (或写或写) )为单位的干预减少为对一组为单位的干预减少为对一组数据块的读数据块的读( (或写或写) )及有关的控制和管理为单位的干预。同时，及有关的控制和管理为单位的干预。同时，又可实现又可实现CPUCPU、通道和、通道和I/OI/O设备三者的并行操作，从而更有效地设备三者

17、的并行操作，从而更有效地提高整个系统的资源利用率。例如，当提高整个系统的资源利用率。例如，当CPUCPU要完成一组相关的要完成一组相关的读读( (或写或写) )操作及有关控制时，只需向操作及有关控制时，只需向I/OI/O通道发送一条通道发送一条I/OI/O指令，指令，以给出其所要执行的通道程序的首址和要访问的以给出其所要执行的通道程序的首址和要访问的I/OI/O设备，通设备，通道接到该指令后，通过执行通道程序便可完成道接到该指令后，通过执行通道程序便可完成CPUCPU指定的指定的I/OI/O任任务。务。 4 通道方式通道方式广州商学院计算机系广州商学院计算机系 kyykyy 通道也叫输入输出处

18、理器通道也叫输入输出处理器. .通道是独立于通道是独立于CPUCPU的专门负责数的专门负责数据输入据输入/ /输出传输工作的处理机，对外部设备实现统一管理，输出传输工作的处理机，对外部设备实现统一管理，代替代替CPUCPU对输入对输入/ /输出操作进行控制，从而使输入，输出操作可输出操作进行控制，从而使输入，输出操作可与与CPUCPU并行操作并行操作 通道负责管理设备与内存之间的数据传送的一切工作，能通道负责管理设备与内存之间的数据传送的一切工作，能完成主存和外围设备间的信息传送，与完成主存和外围设备间的信息传送，与CPUCPU并行地执行操作。并行地执行操作。通道技术解决了通道技术解决了I/O

19、I/O操作的独立性和各部件工作的并行性操作的独立性和各部件工作的并行性n由通道管理和控制由通道管理和控制I/OI/O操作，减少了外围设备和操作，减少了外围设备和CPUCPU的逻辑联的逻辑联系。把系。把CPUCPU从琐碎的从琐碎的I/OI/O操作中解放出来操作中解放出来n外围设备和外围设备和CPUCPU能实现并行操作能实现并行操作n通道和通道之间能实现并行操作通道和通道之间能实现并行操作n各通道上的外围设备也能实现并行操作，达到提高整个系统各通道上的外围设备也能实现并行操作，达到提高整个系统效率这一根本目的效率这一根本目的广州商学院计算机系广州商学院计算机系 kyykyy5.1.3设备控制器设备

20、控制器v传统的设备传统的设备= =机械部分机械部分+ +电子部分。电子部分。v 电子部分在系统的控制下驱动机械部分运转，完成电子部分在系统的控制下驱动机械部分运转，完成I/OI/O操作。操作。由于设备中的电子部分比机械部分的速度快得多。为了降低硬由于设备中的电子部分比机械部分的速度快得多。为了降低硬件成本，将件成本，将电子部分电子部分从设备中分离出来作为一个独立的部件，从设备中分离出来作为一个独立的部件，这就是这就是控制器控制器。v分离之后的设备仅由机械部分构成，一个控制器可与多个设备分离之后的设备仅由机械部分构成，一个控制器可与多个设备相连，交替地或分时的控制欲其相连的设备。相连，交替地或分

21、时的控制欲其相连的设备。v设备并不是直接与设备并不是直接与CPUCPU进行通信，而是与设备控制器通信。进行通信，而是与设备控制器通信。v操作系统基本上与控制器打交道，而非设备本身。操作系统基本上与控制器打交道，而非设备本身。广州商学院计算机系广州商学院计算机系 kyykyy1) 1) 设备控制器与处理机的接口设备控制器与处理机的接口：该接口用于实现：该接口用于实现CPU与设备与设备控制器之间的通信。共有三类信号线控制器之间的通信。共有三类信号线: 数据线、地址线和控制数据线、地址线和控制线。线。2)2)设备控制器与设备的接口设备控制器与设备的接口：在一个设备控制器上，可以连在一个设备控制器上，

22、可以连接一个或多个设备。相应地，在控制器中便有一个或多个设接一个或多个设备。相应地，在控制器中便有一个或多个设备接口，一个接口连接一台设备。在每个接口中都存在数据、备接口，一个接口连接一台设备。在每个接口中都存在数据、控制和状态三种类型的信号。控制器中的控制和状态三种类型的信号。控制器中的I/O逻辑根据处理逻辑根据处理机发来的地址信号去选择一个设备接口。机发来的地址信号去选择一个设备接口。 3)3)I/OI/O逻辑逻辑：在设备控制器中的在设备控制器中的I/O逻辑用于实现对设备的控逻辑用于实现对设备的控制。它通过一组控制线与处理机交互，制。它通过一组控制线与处理机交互， CPU利用该逻辑向控利用

23、该逻辑向控制器发送制器发送I/O命令；命令；I/O逻辑对收到的命令进行译码。每当逻辑对收到的命令进行译码。每当CPU要启动一个设备时，一方面将启动命令发送给控制器；要启动一个设备时，一方面将启动命令发送给控制器；另一方面又同时通过地址线把地址发送给控制器，由控制器另一方面又同时通过地址线把地址发送给控制器，由控制器的的I/O逻辑对收到的地址进行译码，再根据所译出的命令对逻辑对收到的地址进行译码，再根据所译出的命令对所选设备进行控制。所选设备进行控制。广州商学院计算机系广州商学院计算机系 kyykyy数据寄存器控制/状态寄存器数据线I/O逻辑控制器与设备接口1控制器与设备接口i数据状态控制数据状

24、态控制地址线控制线CPU与控制器接口控 制 器 与 设 备 接 口广州商学院计算机系广州商学院计算机系 kyykyyn接收和识别CPU或通道发来的命令n实现数据交换,包括设备和控制器间的数据传输n发现和记录设备及自身的状态信息,供CPU处理使用n设备地址识别设备控制器主要功能设备控制器主要功能广州商学院计算机系广州商学院计算机系 kyykyyn5.2.1 I/O软件的设计目标和原则n5.2.2 I/O中断处理程序n5.2.3 I/O设备驱动程序n5.2.4 独立于设备的I/O软件n5.2.5 用户空间的I/O软件5.2 I/O软件原理软件原理广州商学院计算机系广州商学院计算机系 kyykyyn

25、I/O软件总体设计目标:n高效率n通用性 n I/O软件总体设计要考虑的问题： n设备无关性 n出错处理 n同步（阻塞）异步（中断驱动）传输 n缓冲技术5.2.1 I/O软件的设计目标和原则软件的设计目标和原则广州商学院计算机系广州商学院计算机系 kyykyyn当一个进程请求I/O操作时，该进程将被阻塞，直到I/O操作结束并发生中断。当中断发生时，中断处理程序执行相应的处理，并解除相应进程的阻塞状态。n中断处理程序的主要工作有：n处理中断信号n修改进程状态等5.2.2 I/O中断处理程序中断处理程序广州商学院计算机系广州商学院计算机系 kyykyyn设备驱动程序的工作是把用户提交的逻辑I/O请

26、求转化为物理I/O操作的启动和执行，如设备名转化为端口地址、逻辑记录转化为物理记录、逻辑操作转化为物理操作等n驱动程序发出I/O命令后的动作，有两种可能性：n1)驱动程序阻塞，直到中断信号到达时才被唤醒。因为I/O操作通常需要花费一定的时间才能完成n2) I/O操作没有任何延迟，驱动程序无需阻塞。例如向屏幕上输出一些信息5.2.3 5.2.3 设备驱动程序设备驱动程序广州商学院计算机系广州商学院计算机系 kyykyynI/O操作完成后驱动程序的工作:nI/O操作完成，驱动程序被唤醒后，便检查有无错误，若一切正常，则驱动程序将数据传送给上层的设备无关软件，最后，向它的调用者返回一个关于错误报告的

27、状态信息。若请求队列中有别的请求则它选中一个进行处理，若没有则它阻塞，等待下一个请求设备驱动程序设备驱动程序( (续续) )广州商学院计算机系广州商学院计算机系 kyykyyn设备驱动程序包含的功能n1.设备初始化 预置设备和控制器及通道的状态n2.执行设备驱动例行程序 负责启动设备，进行数据传输，启动通道工作n3.执行中断处理程序 负责处理设备和控制器及通道发出的各种中断设备驱动程序设备驱动程序( (续续) )广州商学院计算机系广州商学院计算机系 kyykyyn设备无关软件完成的功能：n 设备命名和设备保护n提供与设备无关的块尺寸n缓冲技术n设备分配和状态跟踪n错误处理报告5.2.4 独立于

28、设备的独立于设备的I/O软件软件广州商学院计算机系广州商学院计算机系 kyykyyn 1.设备命名和设备保护n 设备都被视为文件，有相应的名字和支持与文件 相关的系统调用，如open，read，stat等n设备保护检查设备是否有权访问所申请的设备nI/O指令为特权指令，用户通过系统调用间接使用n设备文件依赖inode来实现 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn 2.提供与设备无关的尺寸n操作系统为每个磁盘都配备一张记录空闲块的表或位示图n分配空闲块的算法独立于设备，可在高于设备驱动的程序处理n不同磁盘的扇区大小可能不同，必须屏蔽

29、这一事实，向高层软件提供统一的数据块尺寸。 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn 3.缓冲技术n缓冲区的引入n消除填满速率和清空速率的影响n块设备和字符设备的不一致n提供数据和消耗数据不一致时n缓冲区的实现n可通过在主存建立缓冲区n通常在内核开辟，数据在缓冲区缓冲后，在用户缓冲区和设备之间传输n缓冲区涉及大量复制操作，影响I/O性能 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn 4.设备分配与状态跟踪n分配：n根据设备的物理特性，系统制订分配策略n静态分配n动态分配n虚拟

30、分配n状态跟踪n系统检查相应设备的使用状态，来决定是否接受请求n一种简单的处理办法，用OPEN打开设备相应文件 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn 5.错误处理和报告nI/O经常出错，多数错误是与硬件紧密相关，应尽可能在底层处理n通常驱动程序知道如何处理错误n如果处理不成功，报告给独立于设备的I/O软件 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn1.库函数n大部分I/O软件属于操作系统,但是有一小部分是与用户程序链接在一起的库函数。nI/O系统调用通常先是库函数调用5

31、.2.5 用户空间的用户空间的I/O软件软件n2.spooling软件nSPOOLing又称为假脱机操作，它是在多道程序环境下，利用其中一道程序来模拟脱机输入时的外围控制机的功能，把低速I/O设备上的数据传送到高速磁盘上；再利用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。此时的外围操作与CPU对数据的处理同时进行。这种在联机的情况下实现的同时外围操作称为SPOOLing 广州商学院计算机系广州商学院计算机系 kyykyy用户进程进 行 I / O 调 用 ； 格 式 化 I / O ；SPOOLING设备无关软件命名；保护；阻塞；缓冲；分配设备驱动程序建立设备

32、寄存器；检查状态硬件执行I/O操作中断处理程序当I/O结束时，唤醒驱动程序层次I/O应答I/O功能I/O请求I/OI/O软件组织成四个层次：软件组织成四个层次： I/OI/O中断处理程序、设备驱动程中断处理程序、设备驱动程序、与设备无关的操作系统序、与设备无关的操作系统I/OI/O软件、用户层软件、用户层I/OI/O软件软件广州商学院计算机系广州商学院计算机系 kyykyyn实现一个I/O操作所应执行的步骤n应用进程对已打开文件的文件描述符执行读库函数nI/O软件检查参数是否正确n若正确，检查高速缓存中有无要读取的信息块n若有，从缓冲区直接读至用户区，完成I/O请求n若无，执行物理I/O操作，

33、并阻塞应用进程，成功完成物理I/O操作时，则将应用进程放入就绪队列n物理I/O操作完成，应用程序从断点恢复 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广州商学院计算机系 kyykyyn执行物理I/O操作的过程：n内核启动设备驱动程序，分配缓冲区，并向设备控制寄存器发送启动买了，或建立DMA传输，启动I/On设备控制器操纵设备，执行数据传输n采用DMA控制器控制时间传输时，一旦完成，则产生I/O结束中断nCPU响应中断，转向中断处理，检查中断原因n若有错，处理错误n若无错，将数据传输该指定的用户空间 独立于设备的独立于设备的I/O软件（续）软件（续）广州商学院计算机系广

34、州商学院计算机系 kyykyyn5.3.1 单缓冲 n5.3.2 双缓冲 n5.3.3 多缓冲n5.3.4缓冲区高速缓存5.3 缓冲技术缓冲技术广州商学院计算机系广州商学院计算机系 kyykyyn 改善中央处理器与外围设备之间速度不匹配的矛盾n 协调逻辑记录大小与物理记录大小不一致n 提高CPU和I/O设备的并行性 n 减少I/O操作对CPU的中断次数n 放宽对CPU中断响应时间的要求引入缓冲技术的目的广州商学院计算机系广州商学院计算机系 kyykyyn进程执行写操作输出数据时，向系统申请一个缓冲区，若为顺序写请求，则不断把数据填到缓冲区，直到被装满。此后，进程继续它的计算，系统将缓冲区内容写

35、到I/O设备上n进程执行读操作输入数据时，向系统申请一个缓冲区，系统将一个物理记录的内容读到缓冲区，根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程n在输出数据时，只有在系统还来不及腾空缓冲而进程又要写数据时，它才需要等待n在输入数据时，仅当缓冲区空而进程又要从中读取数据时，它才被迫等待缓冲技术实现基本思想广州商学院计算机系广州商学院计算机系 kyykyy缓冲区的类型n缓冲区有不同的类型：n1.单缓冲n2.双缓冲n3.循环缓冲：空缓冲区、装满数据的缓冲区n4.缓冲池：空缓冲区、装满输入数据的缓冲区、装满输出数据的缓冲区广州商学院计算机系广州商学院计算机系 kyykyy在单缓冲情况下

36、，每当用户进程发出一在单缓冲情况下，每当用户进程发出一I/OI/O请求时，操作系统请求时，操作系统便在主存中为之分配一缓冲区。假定从磁盘把一块数据输入到缓便在主存中为之分配一缓冲区。假定从磁盘把一块数据输入到缓冲区的时间为冲区的时间为T T，操作系统将该缓冲区中的数据传送到用户区的时，操作系统将该缓冲区中的数据传送到用户区的时间为间为M M，而，而CPUCPU对这一块数据处理对这一块数据处理( (计算计算) )的时间为的时间为C C。由于。由于T T和和C C是可是可以并行的，以并行的，当当TC时，系统对每一块数据的处理时间为时，系统对每一块数据的处理时间为M+T，反，反之则为之则为M+C可把

37、系统对每一块数据的处理时间表示为可把系统对每一块数据的处理时间表示为Max(C，T)+M。 1单缓冲单缓冲(Single Buffer)工作区工作区处理处理(C)缓冲区缓冲区传送传送(M)输入输入(T)I/O设备设备(a)用户进程用户进程T1M1C1T2M2C2T3M3C3T4t(b)广州商学院计算机系广州商学院计算机系 kyykyy为了加快输入和输出速度，提高设备利用率，引入了双为了加快输入和输出速度，提高设备利用率，引入了双缓冲区机制，也称为缓冲对换缓冲区机制，也称为缓冲对换(Buffer Swapping)(Buffer Swapping)。在设备输。在设备输入时，先将数据送入第一缓冲区

38、，装满后便转向第二缓冲区。入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进此时操作系统可以从第一缓冲区中移出数据，并送入用户进程。接着由程。接着由CPU对数据进行计算。对数据进行计算。工作区工作区用户进程用户进程缓冲区缓冲区1缓冲区缓冲区2I/O 设备设备(a)2双缓冲双缓冲(Double Buffer)广州商学院计算机系广州商学院计算机系 kyykyy在双缓冲时，系统处理一块数据的时间可以粗略地认为在双缓冲时，系统处理一块数据的时间可以粗略地认为是是Max(C，T)。如果。如果CT，则可使则可使CPU不必等待设备输入。对于字符设备，若

39、采用行输不必等待设备输入。对于字符设备，若采用行输入方式，则采用双缓冲通常能消除用户的等待时间，即用户入方式，则采用双缓冲通常能消除用户的等待时间，即用户在输入完第一行之后，在在输入完第一行之后，在CPU执行第一行中的命令时，用户执行第一行中的命令时，用户可继续向第二缓冲区输入下一行数据。可继续向第二缓冲区输入下一行数据。 2双缓冲双缓冲(Double Buffer)T1(缓冲缓冲1)M1C1(b)T2(缓冲缓冲2)T3(缓冲缓冲3)T4(缓冲缓冲4)M2M3M4C2C4C3广州商学院计算机系广州商学院计算机系 kyykyy循环缓冲循环缓冲由由多个缓冲区和多个指针组成。其中每个缓冲区多个缓冲区

40、和多个指针组成。其中每个缓冲区的大小相同。作为输入的多缓冲区可分为三种类型：用于的大小相同。作为输入的多缓冲区可分为三种类型：用于装输入数据的空缓冲区装输入数据的空缓冲区R、已装满数据的缓冲区、已装满数据的缓冲区G以及计算以及计算进程正在使用的现行工作缓冲区进程正在使用的现行工作缓冲区C。3.循环缓冲循环缓冲RGGGRG165423NextiNextgRGGGRC165423NextiNextgCurrent广州商学院计算机系广州商学院计算机系 kyykyyv上述三种缓冲区的组织形式仅适用于某种特定的上述三种缓冲区的组织形式仅适用于某种特定的I/O进程和进程和计算进程，属于专用缓冲。计算进程，

41、属于专用缓冲。v当系统中的设备很多时，将会有许多这样的循环缓冲区，当系统中的设备很多时，将会有许多这样的循环缓冲区，消耗大量的内存空间，而且其利用率也不高。消耗大量的内存空间，而且其利用率也不高。v为了提高缓冲区的利用率，可以采用为了提高缓冲区的利用率，可以采用公共缓冲池技术公共缓冲池技术，其，其中的缓冲区可为多个设备和进程服务。中的缓冲区可为多个设备和进程服务。v两种缓冲池：分别用于块型设备和字符型设备。两种缓冲池：分别用于块型设备和字符型设备。T用于块型设备的缓冲池：缓冲区较大，其长度通常与外用于块型设备的缓冲池：缓冲区较大，其长度通常与外部设备物理块的长度相同；部设备物理块的长度相同；T

42、用于字符型设备的缓冲池：缓冲区较小，其长度通常为用于字符型设备的缓冲池：缓冲区较小，其长度通常为8 8个字节、个字节、1616个字节等；个字节等；4.缓冲池缓冲池广州商学院计算机系广州商学院计算机系 kyykyyv缓冲池中的缓冲区通常组织成链表结构。缓冲池中的缓冲区通常组织成链表结构。需要缓冲区时，从链表中申请一个或多个缓冲区。使用需要缓冲区时，从链表中申请一个或多个缓冲区。使用完毕时，释放的缓冲区将被链接到链表中。完毕时，释放的缓冲区将被链接到链表中。v缓冲区和缓冲池都属于操作系统空间，用户进程不能直接缓冲区和缓冲池都属于操作系统空间，用户进程不能直接对缓冲区中的数据进行操作对缓冲区中的数据

43、进行操作只能通过系统调用间接地使用；只能通过系统调用间接地使用；或让操作系统将缓冲区中的数据复制到用户进程空间或或让操作系统将缓冲区中的数据复制到用户进程空间或相反。相反。4.缓冲池缓冲池广州商学院计算机系广州商学院计算机系 kyykyy缓冲区高速缓存缓冲区高速缓存n为避免数据项的重复产生，内核建立了一个数据缓冲区为避免数据项的重复产生，内核建立了一个数据缓冲区高速缓存，专门用于保存最近使用过的磁盘数据块高速缓存，专门用于保存最近使用过的磁盘数据块n高速缓存的思想：高速缓存的思想：n1 1）当请求从指定文件读写数据时，给定磁盘号和块号，）当请求从指定文件读写数据时，给定磁盘号和块号，查询是否在

44、缓存中，如果在，则从对应的缓冲区获得数查询是否在缓存中，如果在，则从对应的缓冲区获得数据；类似的，向磁盘写入数据时，也可以暂存缓存。据；类似的，向磁盘写入数据时，也可以暂存缓存。n2 2）当文件关闭或撤销时，需要采用一定的策略解决释放）当文件关闭或撤销时，需要采用一定的策略解决释放缓冲区的重用的问题缓冲区的重用的问题n3 3）提供一组高速缓存操作，如写缓存，为文件驱动程序）提供一组高速缓存操作，如写缓存，为文件驱动程序实现读写文件数据。实现读写文件数据。广州商学院计算机系广州商学院计算机系 kyykyyn5.4.1 存储设备的物理结构 n5.4.2 循环排序 n5.4.3 优化分布n5.4.4

45、 搜查定位 n5.4.5 提高磁盘I/O速度的方法5.4 驱动调度技术驱动调度技术广州商学院计算机系广州商学院计算机系 kyykyy5.4.1 存储设备的物理结构存储设备的物理结构n磁盘是一种直接(随机)存取存储设备。每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置 读写磁头读写磁头移动臂移动臂磁头号磁头号1磁头号磁头号2磁头号磁头号3磁头号磁头号4磁头号磁头号5磁头号磁头号6磁头号磁头号7磁头号磁头号8磁头号磁头号9扇区扇区柱面柱面柱面间隔柱面间隔扇区间隔扇区间隔柱面柱面广州商学院计算机系广州商学院计算机系 kyykyyn磁盘记录参数：柱面号、磁头号

46、、扇区号n磁盘访问操作过程：根据信息的参数，移动磁头、搜索数据块、对数据块进行读写n查找时间：磁盘根据给出的柱面号，控制臂移动，使读写磁头到达指定柱面所需时间，即移动磁头时间。平均约20msn搜索延迟：被访问扇区旋转到读写磁头下所需要的时间。平均约10msn传送时间：是读写磁头对数据块读写所需要的时间。平均约10ms广州商学院计算机系广州商学院计算机系 kyykyy5.4.2 循环排序循环排序n考虑磁道保存4个记录的旋转型设备，假定收到四个I/O请求 请求次序 记录号 （1） 读记录4 （2） 读记录3 （3） 读记录2 （4） 读记录1广州商学院计算机系广州商学院计算机系 kyykyyn方法

47、1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理时间等于1/2+1/4+3*3/4=3周，即60毫秒n定位并读出记录4需要1/2+1/4毫秒,读出记录4后,磁盘已经旋转到记录1,再旋转2/4周,到达记录3,再旋转1/4周,读出记录3.同理,读出记录3后,磁盘旋转到记录4,再旋转3/4周,读出记录2.读出记录1也需要3/4周时间1234广州商学院计算机系广州商学院计算机系 kyykyyn方法2：如果次序为读记录1、2、3、4。总处理时间等于1/2+1/4+3*1/4=1.5周，即30毫秒n定位并读出记录1需要1/2+1/4周时间,读出记录1后,磁盘已

48、经旋转到纪录2,定位并读出纪录2的时间是1/4周,定位并读出纪录3和记录4的时间也都是1/4周1234n方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3。总处理时间等于周，即20毫秒n如果知道当前读位置是记录3,则不必花费平均1/2周去寻找某个记录.因为当前的读位置是记录3,所以只需旋转1/4周即可读出记录4,然后再旋转1/4周即可读出记录1,旋转一周可读出4个记录广州商学院计算机系广州商学院计算机系 kyykyy5.4.3 优化分布优化分布n信息在存储空间的排列方式会影响存取等待时间。考虑10个逻辑记录A，B，J被存于旋转型设备上，每道存放10个记录，安排如下： 物理块

49、逻辑纪录 1-10 A-Jn假定旋转速度为20ms/周,处理程序读出每个记录后花4ms进行处理.则读出记录A需要旋转20/10=2ms,即旋转一个扇区,处理完记录A之后磁盘又旋转了B、C两个扇区(因为处理每个记录需4ms时间),将转到记录D的开始.所以为了读出B,必须再转一周.从D开始旋转到B开始共有8个扇区,需耗时16ms广州商学院计算机系广州商学院计算机系 kyykyyn处理10个记录的总时间 ：n10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+916毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录)n 214毫秒ABCDEFGHIJ广州商学院计算

50、机系广州商学院计算机系 kyykyyn按照下面方式对信息优化分布AHEBIFCJGDn则读出记录A并处理结束后,恰巧转至记录B的位置,立即就可读出并处理.除了记录A需要1/2周(10ms)旋转寻道时间外,其它9个记录没有旋转寻道时间.10个记录都需要2ms的读出一个扇区的时间和4ms的处理时间n处理10个记录的总时间 ：10毫秒(移动到记录A的平均时间)+102毫秒（读记录）+4毫秒（处理记录） =70毫秒AHEBIFCJGD广州商学院计算机系广州商学院计算机系 kyykyy5.4.4 搜查定位搜查定位n对于磁盘除旋转延迟外，还有搜查寻道延迟nI/O请求需要3个参数：柱面号，磁头号和扇区号如

51、以下的5个磁盘访问请求：n对于磁盘设备，应考虑使移动臂的移动时间最短的一些调度策略柱面号磁头号扇区号7774024446718547广州商学院计算机系广州商学院计算机系 kyykyyn移臂调度的若干策略 n (1)先来先服务算法n (2)“最短寻道（查找）时间优先”算法 n (3) “电梯调度”算法n (4) “循环扫描”算法n (5) “分步扫描”算法广州商学院计算机系广州商学院计算机系 kyykyy(1)(1)先来先服务先来先服务(FCFS)(FCFS)算法算法举例：假定磁头位置当前在100号柱面，这时9个进程先后提出访问以下磁道：55、58 、39、18、90、160、150、38、18

52、4。按“先来先服务”调度算法，请给出移动的 总磁道数。这是一种最简单的磁盘调度算法。它根据进程请求访问磁这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。致使平均寻道时间可能较长。广州商学院计算机系广州商学院计算机系 kyykyyFCFS调度算法 (从从10

53、0100号柱面开始号柱面开始) 被访问的下被访问的下 一个柱面号一个柱面号 移动距离移动距离 (柱面数柱面数) 55 45 58 3 39 19 18 21 90 72 160 70 150 10 38 112 184 146 平均寻道长度平均寻道长度: 55.3n本算法不会导致某一个进程的请求长期得不到满足，产生饥饿广州商学院计算机系广州商学院计算机系 kyykyy该算法选择这样的进程：其要求访问的柱面与当前磁头该算法选择这样的进程：其要求访问的柱面与当前磁头所在的柱面距离最近，以使每次的寻道时间最短。但这种算所在的柱面距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。法

54、不能保证平均寻道时间最短。( (从从100100号柱面开始号柱面开始) )被访问的下被访问的下 一个柱面号一个柱面号 移动距离移动距离 (柱面数柱面数) 90 10 58 32 55 3 39 1638 1 18 20 150 132160 10 184 24 平均寻道长度平均寻道长度: 27.5(2)(2)“最短查找时间优先最短查找时间优先”(SSTF)(SSTF)算法算法广州商学院计算机系广州商学院计算机系 kyykyy(3) “(3) “电梯调度电梯调度”算法算法 “最短查找时间优先最短查找时间优先”算法虽然能获得较好的寻道性能，算法虽然能获得较好的寻道性能，但却可能导致某个进程发生但却

55、可能导致某个进程发生“饥饿饥饿”。 “电梯调度电梯调度”算法不仅考虑到欲访问的柱面与当前柱面间的算法不仅考虑到欲访问的柱面与当前柱面间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，电梯调度算法所考虑的下一个访问对正在自里向外移动时，电梯调度算法所考虑的下一个访问对象，应是其欲访问的柱面既在当前柱面之外，又是距离最近象，应是其欲访问的柱面既在当前柱面之外，又是距离最近的。这样自里向外地访问，直至再无更外的柱面需要访问时，的。这样自里向外地访问，直至再无更外的柱面需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每

56、次选择这才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的柱面在当前位置内距离最近者，样的进程来调度，即要访问的柱面在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的柱面这样，磁头又逐步地从外向里移动，直至再无更里面的柱面要访问，从而避免了出现要访问，从而避免了出现“饥饿饥饿”现象。由于在这种算法中现象。由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。算法。广州商学院计算机系广州商学院计算机系 kyykyy从从100100号柱面开始号柱面开始向柱面号增加方向访问向柱面

57、号增加方向访问 被访问的下被访问的下 一个柱面号一个柱面号 移动距离移动距离 (柱面数柱面数) 150 50 160 10 18424 9094 5832 53 3 39 16 38 1 18 20 平均寻道长度平均寻道长度: 27.8 电梯调度算法示例 广州商学院计算机系广州商学院计算机系 kyykyy电梯调度算法存在这样的问题：当磁头刚从里向外移动而电梯调度算法存在这样的问题：当磁头刚从里向外移动而越过了某一柱面时，恰好又有一进程请求访问此柱面，这时，越过了某一柱面时，恰好又有一进程请求访问此柱面，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫该进程必须等待，待磁头继续从里向外

58、，然后再从外向里扫描完所有要访问的柱面后，才处理该进程的请求，致使该进描完所有要访问的柱面后，才处理该进程的请求，致使该进程的请求被大大地推迟。程的请求被大大地推迟。为了减少这种延迟，循环扫描算法规定磁头单向移动，例如，为了减少这种延迟，循环扫描算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的柱面并访问后，磁头只是自里向外移动，当磁头移到最外的柱面并访问后，磁头立即返回到最里的欲访问的柱面，亦即将最小柱面号紧接着立即返回到最里的欲访问的柱面，亦即将最小柱面号紧接着最大柱面号构成循环，进行循环扫描。采用循环扫描方式后，最大柱面号构成循环，进行循环扫描。采用循环扫描方式后，上述请求进

59、程的请求延迟将从原来的上述请求进程的请求延迟将从原来的2T2T减为减为T + SmaxT + Smax，其中，其中，T T为由里向外或由外向里单向扫描完要访问的柱面所需的寻为由里向外或由外向里单向扫描完要访问的柱面所需的寻道时间，而道时间，而SmaxSmax是将磁头从最外面被访问的柱面直接移到最是将磁头从最外面被访问的柱面直接移到最里面欲访问的柱面里面欲访问的柱面( (或相反或相反) )的寻道时间。的寻道时间。 (4) (4)“循环扫描循环扫描”(SCAN)(SCAN)算法算法广州商学院计算机系广州商学院计算机系 kyykyy从从100100号柱面开始号柱面开始向柱面号增加方向访问向柱面号增加

60、方向访问 被访问的下被访问的下 一个柱面号一个柱面号 移动距离移动距离 (柱面数柱面数) 150 50 160 10 18424 18166 3820 39 155 16 58 390 32平均寻道长度平均寻道长度: 35.8 循环扫描算法示例循环扫描算法示例 广州商学院计算机系广州商学院计算机系 kyykyyn(5)“分步扫描”算法n将磁盘请求队列分成若干个长度为N的子队列，磁盘调度按先来先服务算法依次处理这些队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其它队列。每个队列按电梯算法处理nN很大时性能接近电梯算法nN很小时蜕化为FCFS算法广州商学院计算机系广州