[精选]操作系统-第5章 设备管理.pptx

《[精选]操作系统-第5章 设备管理.pptx》由会员分享，可在线阅读，更多相关《[精选]操作系统-第5章 设备管理.pptx（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第7章章 设备管理管理安徽理工大学计算机系 第7章 外部设备管理n7.1 引言引言 n7.2 缓冲技冲技术n 7.3 设备分配分配 n7.4 设备控制控制 n7.5 磁磁盘设备管理管理 n7.6 设备管理管理举例例外设的特点：种类多 差异大(控制和速度)外设管理目的包括：外设资源的控制外设资源的共享提高外设资源的利用率。7.1 引言引言n7.1.1 外部外部设备类型和特征型和特征n7.1.2 I/O控制技控制技术 n7.1.3 外外设管理的目的和功能管理的目的和功能 n7.1.4 外外设管理管理结构构7.1.1 外部设备类型和特征外部设备类型和特征1.按交互按交互对象分象分类n人机交互人机交

2、互设备：视频显示示设备、键盘、鼠、鼠标、打印机打印机 n与与计算机或其他算机或其他电子子设备交互交互的的设备：磁：磁盘、磁磁带、传感器、控制器感器、控制器 n计算机算机间的的通信通信设备：网卡、：网卡、调制解制解调器器2.按交互方向分类按交互方向分类n输入入（可（可读）：）：键盘、扫描描仪n 输出出（可写）：（可写）：显示示设备、打印机、打印机 n输入入/输出出（可（可读写）：磁写）：磁盘、网卡、网卡3.按外按外设特性分特性分类使用特征使用特征：存：存储、输入入/输出、出、终端端 数据数据传输率率：低速：低速(如如键盘)、中速、中速(如打印机如打印机)、高速高速(如网卡、磁如网卡、磁盘)信息信

3、息组织特征特征：字符：字符设备(如打印机如打印机)、块设备(如磁如磁盘)7.1.1 外部设备类型和特征4按按设备的共享属性分的共享属性分类 (1)独占独占设备。它是指在一段。它是指在一段时间内只允内只允许一个一个用用户(进程程)访问的的设备，即，即临界界资源。因而，源。因而，对多个并多个并发进程而言，程而言，应互斥地互斥地访问这类设备。系系统一旦把一旦把这类设备分配分配给某后，便由某后，便由该进程程独占，直至用完独占，直至用完释放。放。应当注意，独占当注意，独占设备的的分配有可能引起分配有可能引起进程死程死7.1.1 外部设备类型和特征(2)共享共享设备。它是指在一段。它是指在一段时间内允内允

4、许多个多个进程同程同时访问的的设备。当然，。当然，时刻而言，刻而言，该类设备仍然只允仍然只允许一一个个进程程访问。显然，共享然，共享设备必必须是可是可寻址的相可随址的相可随访问的的设备。典型的共享。典型的共享设备是磁是磁盘。对共享共享设备不不仅可可获得良好的得良好的设备莉用率，而且莉用率，而且实现文件系文件系统和数和数据据库系系统的物的物质基基础。(3)虚虚拟设备。它是指通。它是指通过虚虚拟技技术将一台独占将一台独占设备变换为若干台若干台逻辑设备，供若干个用，供若干个用户(进程程)同同时使用，使用，通常把通常把这种种经过虚虚拟技技术处理后的理后的设备，称，称为虚虚拟设备。7.1.2 I/O控制

5、技术n1.1.程序控制程序控制I/O(programmed I/O)I/O(programmed I/O)I/O操作由程操作由程序序发起，并等待操作完成。数据的每次起，并等待操作完成。数据的每次读写通写通过CPU。缺点缺点：在外：在外设进行数据行数据处理理时，CPU只能等待。只能等待。n2.中断中断驱动方式方式(interrupt-driven I/O)I/O操操作由程序作由程序发起，在操作完成起，在操作完成时（如数据可（如数据可读或已或已经写入）写入）由外由外设向向CPU发出中断，通知出中断，通知该程序。数据的每次程序。数据的每次读写通写通过CPU。n优点点：在外：在外设进行数据行数据处理理

6、时，CPU不必等待，可不必等待，可以以继续执行行该程序或其他程序。程序或其他程序。n缺点缺点：CPU每次每次处理的数据量少（通常不超理的数据量少（通常不超过几个几个字字节），只适于数据），只适于数据传输率率较低的低的设备。3.直接存储访问方式直接存储访问方式(DMA)由程序由程序设置置DMA控制器中的若干寄存器控制器中的若干寄存器值（如内存始址，（如内存始址，传送字送字节数），然后数），然后发起起I/O操作，而后者操作，而后者完成完成内存内存与外与外设的成批数据交的成批数据交换，在操作完成，在操作完成时由由DMA控制器控制器向向CPU发出出中断中断。优点点：CPU只需干只需干预I/O操作的开始

7、和操作的开始和结束，而其中的束，而其中的一批数据一批数据读写无需写无需CPU控制，适于高速控制，适于高速设备。4.通道控制方式通道控制方式(Channel I/O)n通道又称为I/O处理机，它能完成主存储器和外设之间的信息传输，并与中央处理机并行操作。n采用通道技术解决了I/0操作的独立性和各部件工作的并行性。通道把中央处理机从繁琐的输入输出操作中解放出来。n采用通道技术后，不仅能实现CPU和通道的并行操作，而且通道与通道之间也能实现并行操作，各通道上的外围设备也能实现并行操作，从而可达到提高整个系统的效率之根本目的：7.1.2 I/O控制技术通道控制器通道控制器(Channel Proces

8、sor)有自己的有自己的专用用存存储器，可以器，可以执行由行由通道指令通道指令组成的通道程序，成的通道程序，因此可以因此可以进行行较为复复杂的的I/O控制控制，如网卡上，如网卡上信道信道访问控制。通道程序通常由操作系控制。通道程序通常由操作系统所构所构造，放在内存里。造，放在内存里。优点：点：执行一个通道程序可以完成几批行一个通道程序可以完成几批I/O操作。操作。具有通道结构的具有通道结构的计算机系统，计算机系统，主存、通道、主存、通道、控制器和设备控制器和设备之间采用四级之间采用四级连接，实施三连接，实施三级控制。级控制。图为图为单通路单通路I/OI/O系统系统结构结构7.1.2 I/O控制

9、技术7.1.2 I/O控制技术字字节多路通道多路通道：它是：它是为连接大量慢速外接大量慢速外围设备，如如纸带输入机、入机、纸带输出机、卡片出机、卡片输入机、卡入机、卡片片输入机、行式打印机等入机、行式打印机等设置的。置的。选择通道通道(selector channel)：可以：可以连接多个接多个外外设，而一次只能，而一次只能访问其中一个外其中一个外设。多路通道多路通道(multiplexor channel)：可以并：可以并发访问多个外多个外设。分。分为字字节多路多路(byte)和数和数组多路多路(block)通道。通道。7.1.2 I/O控制技控制技术nI/O控制的通道控制方式控制的通道控制

10、方式 7.1.2 I/O控制技术7.1.2 I/O控制技术如上如上图可可见，设备E,F,G,H均有四条通路到达主存。均有四条通路到达主存。例如例如设备E到达主存的四条通路是：到达主存的四条通路是：通道通道A控制器控制器C设备E 通道通道A控制器控制器D设备E 通道通道B控制器控制器C设备E 通道通道B控制器控制器D设备E7.1.3 外设管理的目的和功能1.外外设管理目的管理目的n提高效率提高效率：提高：提高I/O访问效率，匹配效率，匹配CPU和多和多种不同种不同处理速度的外理速度的外设 n方便使用方便使用：方便用：方便用户使用，使用，对不同不同类型的型的设备统一使用方法，一使用方法，协调对设备

11、的并的并发使用使用 n方便控制方便控制：方便：方便OS内部内部对设备的控制：增加和的控制：增加和删除除设备，适，适应新的新的设备类型型7.1.3 外外设管理的目的和功能管理的目的和功能2.外外设管理功能管理功能 n动态地掌握并地掌握并记录设备的状的状态。在设置有通道的系统中，还应掌握通道、控制器的使用状态。n完成完成实际的的I/O操作操作 首先首先，设备管理程序根据用户提出的I/O请求构成相应的通道程序(或称I/O程序)，提供给通道执行；其次其次，启动指定的设备进行I/O操作；最后，对通道发来的中断请求作出及时的响应和处理。7.1.3 外设管理的目的和功能n提供提供设备使用的用使用的用户接口接

12、口：命令接口和：命令接口和编程接程接口口 n设备分配和分配和释放放：使用：使用设备前，需要分配前，需要分配设备和相和相应的通道、控制器。的通道、控制器。n设备的的访问和控制和控制：包括并：包括并发访问和差和差错处理。理。nI/OI/O缓冲和冲和调度度：目：目标是提高是提高I/OI/O访问效率效率7.1.3 外设管理的目的和功能设备管理管理软件件，为实现上述基本功能通常由以下上述基本功能通常由以下程序程序组成：成：n I/O交通管制程序；交通管制程序；n I/O调度程序；即度程序；即设备分配程序；分配程序；n I/O设备处理程序；通常每理程序；通常每类设备都有自己的都有自己的IO设备处理程序。理

13、程序。7.2 I/O缓冲技术缓冲技术缓冲技术可提高外设利用率，尽可能使外设处于缓冲技术可提高外设利用率，尽可能使外设处于忙状态；但有一个限制：进程的忙状态；但有一个限制：进程的I/OI/O请求不能请求不能超过外设的处理能力。超过外设的处理能力。引入引入缓冲的主要原因有以下几个方面：冲的主要原因有以下几个方面：(1)缓和和CPU与与I/O设备间速度不匹配的矛盾速度不匹配的矛盾 (2)减少减少对CPU的中断的中断频率，放率，放宽对中断响中断响应时间的限制的限制 (3)提高提高CPU和和I/O设备之之间的并行性的并行性7.2 I/O缓冲技术1.引入缓冲技术的目的引入缓冲技术的目的匹配匹配CPU或用或

14、用户应用用进程与外程与外设的不同的不同处理速度理速度 减少减少对CPU的中断次数，提高的中断次数，提高CPU和和I/O设备之之间以及各个以及各个I/O设备之之间的的处理并行性。理并行性。因此，因此，缓冲区所在的位置：内存，控制器或外冲区所在的位置：内存，控制器或外设。这些在不同位置的些在不同位置的缓冲区冲区组合在一起，构成合在一起，构成多多级缓冲机制。冲机制。7.2 I/O缓冲技冲技术2.单方向方向缓冲冲 单缓冲冲(single buffer)：一个：一个缓冲区，冲区，CPU和和外外设轮流使用，一方流使用，一方处理完之后接着等待理完之后接着等待对方方处理。理。双双缓冲冲(double buff

15、er)：两个：两个缓冲区，冲区，CPU和和外外设都可以都可以连续处理而无需等待理而无需等待对方。要求方。要求CPU和外和外设的速度相近。的速度相近。环形形缓冲冲(circular buffer)：多个：多个缓冲区，冲区，CPU和外和外设的的处理速度可以相差理速度可以相差较大。大。7.2 I/O缓冲技术1环形形缓冲的冲的组成成(1)多个多个缓冲区冲区 在循在循环冲冲中含有多个中含有多个缓冲区，每个冲区，每个缓冲区的大小相同。冲区的大小相同。缓冲区可分成三种冲区可分成三种类型：型：空空缓冲区冲区R。用于存放。用于存放输入数据；入数据；已装已装满数据的数据的缓冲区冲区G。其中的数据提供。其中的数据提

16、供给计算算进程使用程使用;现行工作行工作缓冲区冲区C。这是是计算算进程正在使用的程正在使用的缓冲区。冲区。循循环缓冲的冲的组成如下成如下图所示。所示。7.2 I/O缓冲技术空空缓冲区冲区R；已装；已装满数据的数据的缓冲区冲区G；现行工作行工作缓冲区冲区C。循环缓冲循环缓冲 7.2 I/O缓冲技术(2)多个指多个指针 对用于用于输入的多入的多缓冲，冲，应设置置这样三个指三个指针：Nextg，指示，指示计算算进程下一个可用的程下一个可用的缓冲区冲区G；Nexti，指示，指示输入入进程下次可用的空程下次可用的空缓冲区冲区R；Current。指示。指示计算算进程正在使用的程正在使用的缓冲区冲区单元。元

17、。开始开始时，它指向第一个，它指向第一个单元，随元，随计算算进程的使程的使用，它将逐次地指向第用，它将逐次地指向第2个个单元，第元，第3、4等等单元，直至元，直至缓冲区的最后一个含数据的冲区的最后一个含数据的单元。元。7.2 I/O缓冲技术2缓冲区的使用冲区的使用 计算算进程和程和输入入进程可利用下程可利用下述两个述两个过程使用循程使用循环缓冲区：冲区：(1)Getbuf过程程 每当每当计算算进程要使用程要使用缓冲区中的数据冲区中的数据时，可，可调用用Getbuf过程。程。该过程将指程将指针Nextg所指的所指的缓冲区提供冲区提供给进程使用，相程使用，相应地，地，须把它改把它改为现行工作行工作

18、缓冲区，冲区，用用Cment指指针指指简该缓冲区的第冲区的第1个个单元，元，同同时将将Nextg移向下一个移向下一个G缓冲区。冲区。类似地，每当似地，每当输入入避程要使用空避程要使用空缓冲来装入数据冲来装入数据时，也可，也可调用用Getbuf过程。由程。由该过程将指程将指针Nexti所指所指缓冲区提供冲区提供给输入入进程程使用，同使用，同时将将Nexti指指针移向下一个移向下一个R缓冲区。冲区。7.2 I/O缓冲技术(2)Releasebuf过程程 当当计算算进程把程把G缓冲区中冲区中的数据提取完的数据提取完时，便可，便可调用用Releasebuf过程，程，将将该缓冲区冲区释放。此放。此时，把

19、，把该缓冲区由当前冲区由当前(现行行)工作工作缓冲区冲区C改改为空空缓冲区冲区R。类似地，似地，当当输入入进程将程将缓冲区装冲区装满时，也，也调用用Releasebuf过程，将程，将该缓冲区冲区释放，并改放，并改为G缓冲区。冲区。7.2 I/O缓冲技术3进程的同步程的同步 使用使用输入入缓冲可使冲可使输入入进程和程和计算算进程并行程并行执行。相行。相应地，指地，指针Nexti和指和指针Nextg将不断地沿将不断地沿顺时针方向移方向移动，这样就可能出就可能出现下述两种情况：下述两种情况：(1)Nexti指指针追赶上追赶上Nextg指指针 这意味着意味着输入入进程程输入数据的速入数据的速度大于度大

20、于计算算进程程处理数据的速度，已把全部理数据的速度，已把全部缓冲区冲区(可用空可用空缓冲冲)装装满。此。此时，输入入进程程应该阻塞，直至阻塞，直至计算算进程把某个程把某个缓冲区中数据全部提取完，使之成冲区中数据全部提取完，使之成为空空缓冲冲R，并，并调用用Releasebuf过程将它程将它释放放时，这种种情况被称情况被称为系系统受受计算限制。算限制。7.3 设备分配设备分配由于外设资源的有限，需解决进程间的外设共享问题，以提高外设资源的利用率。设备分配是对进程使用外设过程的管理。这里有两种作法：1)在进程间切换使用切换使用外设，如键盘和鼠标；2)通过一个虚拟设备虚拟设备把外设与应用进程隔开，只

21、由虚拟设备来使用设备。n7.3.1 设备分配数据分配数据结构构 n7.3.2 设备分配原分配原则 n7.3.3 假脱机技假脱机技术7.3.1 7.3.1 设备分配数据结构设备分配数据结构设备控制表控制表(DCT,Device Control Table)：每：每个个设备一一张，描述描述设备特性和状特性和状态。反映。反映设备的特性、的特性、设备和控制器的和控制器的连接情况。接情况。DCTDCT的内容主要包括的内容主要包括：设备标识：用来区：用来区别不同不同的的设备；设备类型：反映型：反映设备的特性；如：的特性；如：块设备或字符或字符设备；设备配置：配置：I/O地址等；地址等；设备状状态：工作或空

22、：工作或空闲状状态；等待等待队列：等列：等待使用待使用该设备的的进程程队列；列；7.3.1 设备分配数据结构设备分配数据结构系系统设备表表(SDT,System Device Table)：系：系统内一内一张，反映，反映系系统中中设备资源的状源的状态，记录所有所有设备的状的状态及其及其设备控制表的入口。控制表的入口。SDTSDT表项的主要组成表项的主要组成：DCT指指针：指向相：指向相应设备的的DCT；设备使用使用进程程标识：正在使用：正在使用该设备的的进程程标识；DCT信息：信息：为引用方便而保引用方便而保存的存的DCT信息，如：信息，如：设备标识、设备类型等；型等；7.3.1 设备分配数据

23、结构设备分配数据结构控制器控制表控制器控制表(COCT,COntroller Control Table)：每个：每个设备控制器一控制器一张，描述，描述I/O控制控制器的配置和状器的配置和状态。如。如DMA控制器所占用的中断控制器所占用的中断号、号、DMA数据通道的分配。数据通道的分配。通道控制表通道控制表(CHCT,CHannel Control Table)：每个通道一每个通道一张，描述通道工作状，描述通道工作状态。7.3.2 设备分配原则设备分配原则设备分配原则设备分配原则是合理使用外设是合理使用外设(公平和避免死锁公平和避免死锁)，提高，提高设备利用率。设备利用率。引入引入I/O调度程

24、序，来满足调度程序，来满足I/O请求，决请求，决定设备的分配策略。定设备的分配策略。与与设备分配有关的分配有关的设备属性属性：独享独享设备：打印机等；：打印机等；共享共享设备：磁：磁盘、网卡等；、网卡等；设备分配方式分配方式：各有：各有优缺点缺点 静静态分配分配：在：在进程分程分创建建时分配，在分配，在进程退出程退出时释放；放；不会出不会出现死死锁；设备利用率不高；利用率不高；7.3.2 设备分配原则动态分配分配：在：在进程程执行行过程中根据需要分配，使程中根据需要分配，使用用结束后束后释放；放；需要考需要考虑死死锁问题 有利于提有利于提高高设备利用率利用率动态分配策略分配策略：针对特定特定设

25、备采用特定的分配策采用特定的分配策 略略 先来先服先来先服务(FCFS)：按按I/O请求的先后求的先后顺序，序，排成排成I/O请求命令求命令队列；按列；按FCFS分配分配设备；基于基于优先先级：依据：依据进程的程的优先先级，指定，指定I/O请求的求的优先先级，排成不同，排成不同优先先级队列；按列；按优先先级高低分配高低分配设备；7.3.2 设备分配原则设备分配的安全性分配的安全性 为了加快了加快进程推程推进的速度，使的速度，使CPU和和I/O设备能并行工作，能并行工作，应使某些使某些进程程发出出I/O请求之后，求之后，仍可以仍可以继续运行，需要运行，需要时又可以又可以发出第二个出第二个I/O请

26、求、第三个求、第三个I/O请求。求。仅当当进程所程所请求求的的设备已已经为另外一个另外一个进程占用程占用时才才进入阻塞入阻塞状状态。这样就可以同就可以同时操作多个外部操作多个外部设备。但但是，是，这种多种多请求方式，会求方式，会导致致设备分配不安全，分配不安全，又可能又可能产生死生死锁现象。因此，再多象。因此，再多请求方式中，求方式中，设备分配分配应该保保证安全而不出安全而不出现死死锁。7.3.2 设备分配原则与与设备无关性无关性 与与设备无关性，即用无关性，即用户程序中程序中所使用的所使用的设备(逻辑设备)与系与系统配置的配置的实际物物理理设备无关。无关。7.3.3 设备分配程序设备分配程序

27、设备分配程序的主要功能分配程序的主要功能是：当是：当进程向系程向系统提出提出I/O请求后，求后，设备分配程序按照一定的策略，分配程序按照一定的策略，把所要求的把所要求的设备分配分配给它。它。I/O交通管制程序交通管制程序I/O调度程序都是度程序都是专门用于完成用于完成设备分配任分配任务的程序。的程序。I/O交通管制程序交通管制程序 I/O交通管交通管制程序的主要功能是管理制程序的主要功能是管理设备、控制器和通道、控制器和通道的全部状的全部状态信息。信息。主要解决的主要解决的问题是是：7.3.3 假脱机技术假脱机技术利用假脱机技术利用假脱机技术(SPOOLing,Simultaneous Per

28、ipheral Operation On Line,也称为虚拟也称为虚拟设备技术设备技术)可可把独享设备转变成具有共享特征把独享设备转变成具有共享特征的虚拟设备的虚拟设备，从而提高设备利用率。，从而提高设备利用率。引入：在多道批引入：在多道批处理系理系统中，中，专门利用一道程序利用一道程序（SPOOLing程序）来完成程序）来完成对设备的的I/O操作。操作。无需使用外无需使用外围I/O处理机。理机。7.3.3 假脱机技术假脱机技术假脱机的原理：假脱机的原理：SPOOLing程序和外程序和外设进行数据交行数据交换，可以称，可以称为“实际I/O”。一方面，。一方面，SPOOLing程序程序预先从先

29、从外外设输入数据并加以入数据并加以缓冲，在以后需要的冲，在以后需要的时候候输入到入到应用程序；用程序；另一方面，另一方面，SPOOLing程程序接受序接受应用程序的用程序的输出数据并加以出数据并加以缓冲，在以冲，在以后适当的后适当的时候候输出到外出到外设。在在SPOOLing程程序中，需要管理两序中，需要管理两级缓冲区：内存冲区：内存缓冲区和快冲区和快速外存上的速外存上的缓冲池，后者可以冲池，后者可以暂存多批存多批I/O操操作的作的较多数据。多数据。7.4 磁盘设备管理磁盘设备管理CPU和内存的和内存的访问速度访问速度比磁盘要快若干个数量级，比磁盘要快若干个数量级，磁盘系统的性能磁盘系统的性能

30、对整个系统的性能有重要影响对整个系统的性能有重要影响，磁盘设备管理的目标就是提高磁盘系统的性能。磁盘设备管理的目标就是提高磁盘系统的性能。7.4.1 磁磁盘I/O访问时间的的组成成 7.4.2 磁磁盘I/O调度策略度策略 7.4.3 磁磁盘缓存置存置换算法算法7.4.1 磁盘I/O访问时间的组成柱面定位柱面定位时间：磁：磁头移移动到指定柱面的机械运到指定柱面的机械运动时间；旋旋转延延迟时间：磁：磁盘旋旋转到指定扇区的机械运到指定扇区的机械运动时间；它与磁；它与磁盘转速相关，如：速相关，如：软盘转速可速可为600rpm(每分每分钟转速速)，硬，硬盘可可为3600rpm。数据数据传送送时间：从指定

31、扇区：从指定扇区读写数据的写数据的时间。7.4.1 磁磁盘I/O访问时间的的组成成由于由于柱面定位时间柱面定位时间在访问时间中占主要部分，在访问时间中占主要部分，合合理组成磁盘数据的存储位置理组成磁盘数据的存储位置可提高磁盘可提高磁盘I/O性性能。能。例子：读一个例子：读一个128KB大小的文件：大小的文件：(1)文件由文件由8个连续磁道个连续磁道(每个磁道每个磁道32个扇区个扇区)上的上的256个扇个扇区构成：区构成：20ms+(7.3ms+17.7ms)*8=220ms;其中，其中，柱面定位时间为柱面定位时间为20ms，旋转延迟时间为，旋转延迟时间为7.3ms，32扇区数据传送时间为扇区数

32、据传送时间为17.7ms；7.4.1 磁盘I/O访问时间的组成(2)文件由文件由256个随机分布的扇区个随机分布的扇区构成：构成：(20ms+7.3ms+0.5ms)*256=7373ms;其中，其中，1扇扇区数据区数据传送送时间为0.5ms；随机分布随机分布时的的访问时间为连续分布分布时的的33.5倍倍。7.4.2 磁盘I/O调度策略来自不同进程的磁盘来自不同进程的磁盘I/O请求构成请求构成一个随机分布一个随机分布的请求队列的请求队列。磁盘磁盘I/O调度算法：调度算法：先先进先出算法先出算法 优先先级算法算法 后后进先出算法先出算法 短短查找找时间优先算法先算法 扫描描(SCAN)算法算法

33、循循环扫描描(C-SCAN)算法算法 N步步扫描描(N-step-SCAN)算法算法 双双队列列扫描描(FSCAN)算法算法7.4.2 磁盘I/O调度策略n先先进先出先出(FIFO,First In First Out)算法算法：磁：磁盘I/O执行行顺序序为磁磁盘I/O请求的先后求的先后顺序。序。该算法的特点是公平性；在磁算法的特点是公平性；在磁盘I/O负载较轻且每次且每次读写多个写多个连续扇区扇区时，性能，性能较好。好。n优先先级算法算法：依据：依据进程程优先先级来来调整磁整磁盘I/O请求的求的执行行顺序。序。该算法反映算法反映进程在系程在系统的的优先先级特征，目特征，目标是系是系统目目标的

34、的实现，而不是，而不是改改进磁磁盘I/O性能。性能。7.4.2 磁盘I/O调度策略n后后进先出先出(LIFO,Last In First Out)算法算法：后：后产生的磁生的磁盘I/O请求，先求，先执行。行。该算法是基于算法是基于事事务系系统中中顺序文件中磁序文件中磁盘I/O的局部性特征，的局部性特征，相相邻访问的位置也相的位置也相邻。它的它的问题在于系在于系统负载重重时，可能有，可能有进程的磁程的磁盘I/O永永远不能不能执行，行，处于于饥饿状状态。7.4.2 磁盘I/O调度策略n短短查找找时间优先先(SSTF,Shortest Service Time First)算法算法：考：考虑磁磁盘I

35、/O请求求队列中各列中各请求的磁求的磁头定定位位置，位位置，选择从当前磁从当前磁头位置出位置出发，移，移动最少的磁最少的磁盘I/O请求。求。该算法的目算法的目标是使每次磁是使每次磁头移移动时间最少。最少。它不一定是最短平均柱面定位它不一定是最短平均柱面定位时间，但比，但比FIFO算法有算法有更好的性能。更好的性能。对中中间的磁道有利，可能会有的磁道有利，可能会有进程程处于于饥饿状状态。n扫描描(SCAN)算法算法：选择在磁在磁头方向上从当前位置移方向上从当前位置移动最少的磁最少的磁盘I/O请求求执行，没有前行，没有前进方向上的方向上的请求求时才改才改变方向。方向。该算法是算法是对SSTF算法的

36、改算法的改进，磁，磁盘I/O较好，且没有好，且没有进程会程会饿死。死。7.4.2 磁盘I/O调度策略n循循环扫描描(C-SCAN)算法算法：在一个方向上使用：在一个方向上使用扫描算法，描算法，当到达当到达边沿沿时直接移直接移动到另一沿的第一个位置。到另一沿的第一个位置。该算算法可改法可改进扫描算法描算法对中中间磁道的偏好。磁道的偏好。实验表明，表明，该算法在中算法在中负载或重或重负载时，磁，磁盘I/O性能比性能比扫描算法描算法好。好。nN步步扫描描(N-step-SCAN)算法算法：把磁：把磁盘I/O请求求队列列分成分成长度度为N的段，每次使用的段，每次使用扫描算法描算法处理理这N个个请求。求

37、。当当N=1时，该算法退化算法退化为FIFO算法。算法。该算法的目算法的目标是改是改进前几种算法可能在多磁前几种算法可能在多磁头系系统中出中出现磁磁头静止静止在一个磁道上，在一个磁道上，导致其它致其它进程无法及程无法及时进行磁行磁盘I/O。7.4.2 磁盘I/O调度策略n双双队列列扫描描(FSCAN)算法算法：把磁：把磁盘I/O请求分成求分成两个两个队列，交替使用列，交替使用扫描算法描算法处理一个理一个队列，列，新生成的磁新生成的磁盘I/O请求放入另一求放入另一队列中。列中。该算算法的目法的目标与与N步步扫描算法一致。描算法一致。7.6 设备管理举例n7.7.1 UNIX的的设备管理管理 n7

38、.7.2 Windows NT的的设备管理管理7.7.1 UNIX的设备管理UNIX的外设与特殊文件对应，由文件系统按文件管理方式进行管理，向上提供一个与文件系统统一的接口。UNIX的文件系统与设备驱动程序之间的接口是设备开关表：块设备开关表和字符设备开关表。硬件与驱动程序之间的接口包括与机器有关的控制寄存器或者I/O指令，用来管理设备和中断矢量。1.UNIX的I/O结构无无缓存存I/O(Buffered I/O)：在：在进程程I/O区区域与系域与系统I/O模模块间直接直接进行数据交行数据交换；有有缓存存I/O(Unbuffered I/O)：有：有缓存存I/O要要经过系系统的的缓冲区管理机冲

39、区管理机构；它分成系构；它分成系统缓冲冲区区(system buffer caches)和字符和字符队列列(character queues)两种。两种。2.块设备块设备(block device)的缓冲的缓冲区管理区管理缓冲区采用缓冲池结构，主要用于磁盘等外存的缓存。缓冲区采用缓冲池结构，主要用于磁盘等外存的缓存。块设备缓冲区冲区结构：构：缓存存块是是缓存使用的基本存使用的基本单位，位，它与外它与外设数据数据块相相对应；每个；每个缓存存块由分立的两部由分立的两部分分组成：成：缓冲控制冲控制块和和缓冲数据区冲数据区。前者用于。前者用于缓冲冲区管理，后者用于存放数据（区管理，后者用于存放数据（长

40、度度为512或或1024字字节）。）。缓冲控制冲控制块：也称也称为缓冲首部。内容包括：冲首部。内容包括：逻辑设备号，物理号，物理块号，号，缓冲区状冲区状态（如空（如空闲、延、延迟写、写、锁定等定等标志），指向志），指向缓冲数据区的指冲数据区的指针，哈希，哈希队列的列的前后向指前后向指针，空，空闲队列的前后向指列的前后向指针。2.块设备(block device)的缓冲区管理缓冲区管理的相关数据冲区管理的相关数据结构构 空空闲缓冲冲队列列(Free list)：系系统的所有空的所有空闲缓冲区列表；冲区列表；设备I/O请求求队列列(Driver I/O queue)：正与外正与外设进行行I/O操作

41、的操作的缓存存块列表；一个列表；一个缓存存块必必须处于空于空闲或操作状或操作状态；设备缓冲区冲区队列列(Device list)：与各外与各外设相关的相关的缓存存块列列表，其中有表，其中有缓存数据；存数据；缓冲区冲区检索索 设备缓冲区冲区队列列为Hash队列列：为了了检索方索方便，便，设备缓冲区冲区队列列为一个按一个按(逻辑设备号，物理号，物理块号号)组织的的Hash队列。把列。把逻辑设备号和物理号和物理块号之和号之和对64取模作取模作为哈希函数哈希函数值，据此建立多个哈希，据此建立多个哈希队列（列（64个个队列）。列）。(1)自由buf队列一个可被分配作它用的缓冲存储区，其相应的一个可被分配

42、作它用的缓冲存储区，其相应的buf位于自由位于自由buf队列中。在自由队列的所有队列中。在自由队列的所有buf的的b_flag标志不为标志不为B_BUSY。自由。自由buf队队列的控制块为列的控制块为bfreelist。(2)设备buf队列每每类设备都有一个都有一个设备bufbuf队列，其列，其队首和首和队尾尾分分别用指用指针b_forwb_forw和和b_backb_back双向勾双向勾连。一个一个缓存被分配用于存被分配用于读、写某、写某类块设备上的某一字上的某一字符符块时，其相，其相应的的bufbuf就就进入入该类设备的的bufbuf队列，除非被列，除非被“移作它用移作它用”，否，否则一直

43、保留在一直保留在该队列中。列中。(3)NODEVNODEV设备队列设备队列1 1）特殊的设备队列）特殊的设备队列“空设备队列空设备队列”，也称，也称“NODEV“NODEV设备队列设备队列”。当系统需要使用缓存，。当系统需要使用缓存，但不与特定的设备字符块相连时，则将分配到但不与特定的设备字符块相连时，则将分配到的缓存控制块的缓存控制块bufbuf送入送入NODEVNODEV设备队列设备队列。2 2）有两种情况将缓存控制块）有两种情况将缓存控制块bufbuf送入送入NODEVNODEV设备设备队列：队列：第一种：在进程执行目标程序的开始阶段，它用第一种：在进程执行目标程序的开始阶段，它用缓存存

44、放传向该目标程序的参数；缓存存放传向该目标程序的参数；第二种：是用缓存存放文件系统的资源管理块。第二种：是用缓存存放文件系统的资源管理块。在系统初启时，所有的空闲在系统初启时，所有的空闲BUFBUF即在自由即在自由bufbuf队队列又在列又在NODEVNODEV设备队列中。设备队列中。2.块设备(block device)的缓冲区管理缓存存块可同可同时链入入设备缓冲区冲区队列和空列和空闲缓冲冲队列：列：一个一个缓存存块在分配在分配给一个外一个外设后，一直与后，一直与该外外设相关相关(既使既使该缓存存块在空在空闲缓冲冲队列中列中)，直到，直到分配分配给另一外另一外设。即：。即：设备释放放缓冲区后

45、，冲区后，该缓冲区可冲区可处于于延延迟写写状状态，等待被写入到外，等待被写入到外设；该缓冲区被重新分配之前，要将其写入到冲区被重新分配之前，要将其写入到外外设。2.块设备(block device)的缓冲区管理n缓冲区的置冲区的置换算法算法:最近最久未使用算法最近最久未使用算法(LRU)算法算法n缓冲区数据冲区数据读写：写：外外设与核心与核心缓冲区冲区间：一一般般读(从外从外设读入指定的数据入指定的数据块)、预先先读(在在一般一般读的基的基础上，异步上，异步读入另一入另一块，以提高数，以提高数据据读取速度取速度)；一般写一般写（立即起（立即起动I/O并等待并等待完成）、完成）、异步写异步写（立

46、即起（立即起动I/O而不等待完成，而不等待完成，以提高写速度）、以提高写速度）、延延迟写写（不立即起（不立即起动I/O，以减少不必要的以减少不必要的I/O操作，但系操作，但系统故障故障时会会产生数据生数据错误）3.字符设备的缓冲区管理字符字符缓冲区采用冲区采用缓冲池冲池结构，构成一个字符构，构成一个字符队列列(Character Queue)，它不同于，它不同于块设备缓冲区冲区的多次的多次读写，写，缓冲区中每个字符只能冲区中每个字符只能读一次，一次，读后被破坏。后被破坏。字符字符缓冲池的基本分配冲池的基本分配单位位为字符字符缓冲区冲区cblock：供各种字符：供各种字符设备（的（的设备驱动程序

47、）使用。程序）使用。每个每个缓冲区大小冲区大小为70字字节，内容包括：第一个，内容包括：第一个字符和最后一个字符的位置（便于从开字符和最后一个字符的位置（便于从开头移出移出字符和向末尾添加字符），指向下一个字符和向末尾添加字符），指向下一个缓冲区冲区的指的指针c_next，可存放，可存放64个字符个字符的数据区的数据区.3.字符设备字符设备(character device)的缓冲区管理的缓冲区管理字符字符设备缓冲冲队列列clist：每个字符每个字符设备驱动程序程序对应一一个个clist。由若干个由若干个cblock依次依次链接而成，而接而成，而clist指向指向第一个和最后一个第一个和最后一

48、个cblock.所有的空所有的空闲缓冲区也冲区也对应一个一个clist。字符缓存的结构如下：字符缓存的结构如下：struct cblock struct cblock*c_next;/*字符缓存指针字符缓存指针*/char info6;/*字符缓存信息区字符缓存信息区*/;UNIX设置了设置了100个字符缓存，从而构成了字符缓冲池，个字符缓存，从而构成了字符缓冲池，其说明为：其说明为：struct cblock cfreeNCLIST;(1)自由字符缓存队列struct cblock*cfreelist;/自由队列如图自由队列如图7.24所示。所示。字符缓存的分配和释放都是在队首进行的字符缓存

49、的分配和释放都是在队首进行的.(2)I/O字符缓存队列 字符设备通过字符缓存进行输入或输出。各个正字符设备通过字符缓存进行输入或输出。各个正被使用的字符缓存按照它们的不同用途形成多被使用的字符缓存按照它们的不同用途形成多个个I/O队列，每个队列设置一个控制块，其结队列，每个队列设置一个控制块，其结构如下：构如下：struct list int c_cc;/*字符计数字符计数器器*/int c_cf;/*缓存队列缓存队列首指针首指针*/int c_cl;/*缓存队列尾指针缓存队列尾指针*/;3.字符设备字符设备(character device)的缓冲区管理的缓冲区管理（1）取字符和释放字符缓存

50、）取字符和释放字符缓存 根据缓存队列首根据缓存队列首指针指针c_cf顺次取出字符，图顺次取出字符，图7.26取出字符取出字符U、N、I后，就释放缓存，将其归还自由队列，原后，就释放缓存，将其归还自由队列，原设备队列变为图设备队列变为图7.26所示。所示。3.字符设备字符设备(character device)的缓冲区管理的缓冲区管理（2）送字符和分配字符缓存）送字符和分配字符缓存 当当I/O设备向缓存设备向缓存送入字符时，先检查送入字符时，先检查c_cl是否已满，如果已满是否已满，如果已满则应先分配自由字符缓存，将其接入则应先分配自由字符缓存，将其接入I/O字符字符缓存队尾，然后送字符进入新分