操作系统-第五章设备管理.ppt

《操作系统-第五章设备管理.ppt》由会员分享，可在线阅读，更多相关《操作系统-第五章设备管理.ppt（81页珍藏版）》请在三一办公上搜索。

1、第五章 设备管理,设备管理是操作系统中负责直接处理硬件设备的部分，它对硬件设备进行抽象，使用户程序通过操作系统完成对I/O设备的操作。基本任务：完成用户提出的I/O请求，提高I/O速率以及改善I/O设备的利用率。,5.1 概述5.1.1 I/O管理的重要性,I/O设备就像计算机系统的五官和四肢2.I/O性能经常成为系统性能的瓶颈(1)CPU性能不等于系统性能 响应时间也是一个重要因素(2)CPU性能越高，与I/O差距越大 弥补：更多的进程(3)进程切换多，系统开销大,3.操作系统庞大复杂的原因之一是：资源多、杂，并发，均来自I/O4.理解I/O的工作过程与结构是理解操作系统的工作过程与结构的关

2、键5.与其他功能联系密切，特别是文件系统,5.1.2 设备的分类,按传输速率:低速(100KB/s)按信息交换单位分类块设备:读写的基本单位是数据块,如磁盘字符设备:读写的基本单位是字符,如键盘按共享属性分类独占设备：在一段时间内只能有一个进程使用的设备，一般为低速I/O设备。（如打印机，磁带等）共享设备：在一段时间内可有多个进程以交叉的方式来共同使用的设备，其资源利用率高。（如硬盘）虚拟设备：在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚拟设备。目的是将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率。,5.1.3 设备管理的目标和

3、任务,按照用户的请求,控制设备的各种操作,完成I/O设备与内存之间的数据交换,最终完成用户的I/O请求完成功能:(1)设备分配与回收 记录设备的状态 根据用户的请求和设备的类型,采用一定的分配算法,选择一条数据通路(2)建立统一的独立于设备的接口(3)完成设备驱动程序，实现真正的I/O操作(4)处理外部设备的中断处理(5)管理I/O缓冲区,2.向用户提供使用外部设备的方便接口，屏蔽了硬件细节(设备的物理细节,错误处理,不同I/O的差异性)使用户摆脱繁琐的编程负担。方便性、友好界面、透明性3.利用各种技术(通道,中断,缓冲等)提高CPU与设备、设备与设备之间的并行工作能力,提高资源利用率 并行性

4、 均衡性（使设备充分忙碌）4.保证在多道环境下,多个进程竞争使用设备时,按一定策略分配和管理各种设备,使系统能有条不紊的工作5.保护 设备传送或管理的数据应该是安全的、不被破坏的、保密的,6.与设备无关性(设备独立性)用户在编制程序时,使用逻辑设备名,由系统实现从逻辑设备到物理设备(实际设备)的转换。用户能独立于具体物理设备而方便的使用设备,用户申请使用设备时,只需要指定设备类型,而无须指定具体物理设备,系统根据当前的请求,及设备分配的情况,在相同类别设备中,选择一个空闲设备,并将其分配给一个申请进程。7.统一性：对不同的设备采取统一的操作方式,在用户程序中使用的是逻辑设备。优点是:设备忙碌或

5、设备故障时，用户不必修改程序改善了系统的可适应性和可扩展性,5.1.4 I/O系统的结构,1.微机I/O系统,2.具有通道的I/O系统结构,总线（BUS）数据总线(data bus)并行传送数据的一组线。64位地址总线(address bus)并行传送地址的一组线。32位控制总线(control bus)传送控制信息中的一组并行线I/O总线（BUS）当总线连接的是CPU和I/O设备时,就称它为I/O总线Intel 80 x86微处理器只使用了32位地址总线中的16 位对I/O设备进行寻址,使用64位数据总线中的8位、16位或32位传送数据。每个I/O设备都通过设备控制器连接到I/O总线上。CP

6、U通过I/O总线的各I/O端口与不同的控制器交换信息,从而访问对应的设备。,PC的I/O体系结构,CPU,I/O BUS,I/O port,I/O Controler,I/O port,I/O设备,I/O端口(I/Oport),每个连接到I/O总线上的设备控制器都有自己的I/O地址集,即一组I/O端口,所以每个设备对应一组端口;在IBM PC体系结构中,I/O地址空间共提供了65,536个8位I/O端口。有四条专用汇编指令允许CPU对I/O端口进行读写。即：in、ins、out和outs在执行指令时,CPU用地址总线选择所请求的I/O端口,用数据总线在CPU和设备控制器之间传送数据。I/O端口

7、还可以被映射到物理地址空间 因此,处理器和I/O设备之间的通信还可直接使用对内存进行操作的汇编指令(例如:mov、and等等),5.1.5 设备控制器,控制器是CPU与I/O设备之间的接口；接收从CPU发来的命令,并控制I/O设备工作。控制器是一个可编址设备,例如PC中硬盘控制器的I/O端口地址。从物理上看,控制器是一块接口卡或主板上的一个功能模块。,设备控制器的组成,设备控制器的功能,地址识别:识别I/O端口地址,使I/O操作与设备对应。接收和识别命令指挥设备执行 接收CPU通过I/O总线发来的命令和参数,存储在控制器中相应的控制寄存器中,并对它进行译码识别,转换成适当的电信号,通过控制器与

8、设备的接口向设备发送,指挥设备执行特定的操作。接收和记录设备的状态 接收从设备发来的电信号,进行转换和解释,变为设备的状态信息,将此结果记录在控制器的状态寄存器上,供CPU了解。数据交换 实现CPU控制器设备的数据交换,从而实现了CPU到设备的数据传递和设备到CPU的数据传递。,5.2 I/O控制方式一、循环I/O测试方式（程序I/O方式）二、程序中断I/O方式三、DMA（直接存储器访问）方式四、通道技术,5.2.1 程序I/O方式,CPUI/OI/O CPUCPU忙等循环检测I/O CPUCPU 内存,5.2.2 中断驱动I/O 控制方式,当某进程要启动某个I/O设备工作时,便由CPU向相应

9、的设备控制器发出一条I/O指令,然后立即返回继续执行原来的任务。设备控制器便按该指令的要求去控制指定的I/O设备。此时,CPU可以去做其它事情与I/O设备并行工作。例如,在输入时,当设备控制器收到CPU 发来的读命令后,便去控制相应的输入设备读数据。数据进入数据寄存器后,设备控制器通过中断控制器和控制总线向CPU发出中断信号,CPU响应中断,读设备控制器状态检查是否出错,若无错,则通过数据总线从设备控制器中读出数据,写入存储器。,CPUI/OI/O CPUI/O CPUCPU 内存,5.2.3 DMA(direct memory access)控制方式,DMA控制方式的引入 中断方式是以字节(

10、字)为单位进行I/O的,每完成一个字节(字)CPU要处理一次中断,这种方法用于块设备效率极低,为了进一步减少CPU对I/O的干预,提高CPU与I/O设备的并行度引入DMA控制方式。DMA方式的特点为：数据传送的基本单位是数据块。数据是直接在设备内存之间传送的。仅在传送一个或多个数据块的开始和结束时才需要CPU对I/O的干预,传送工作本身是由DMA控制器完成的。,DMA控制器的组成主机与DMA控制器的接口数据寄存器(DR)内存地址寄存器(MAR)数据计数器(DC)命令/状态寄存器(CR)DMA控制器与块设备的接口I/O控制逻辑,DMA方式从磁盘读入数据块的工作流程:,DMA工作原理窃取总线控制权

11、 存放输入数据的内存起始地址、要传送的字节数送入 DMA控制器的内存地址寄存器和传送字节计数器;中断允许位和启动位置成1,启动设备。发出传输要求进程进入等待状态,其他进程占据CPU。DMA控制器不断窃取总线控制权,数据不断写入内存。传送完毕,发出中断信号。CPU接到中断信号转入中断处理程序处理。中断处理结束,CPU返回原进程或切换到新的进程。,DMA方式与中断的主要区别 中断方式的数据传送到存储器是由CPU控制完成的。而DMA方式的数据传送到存储器则不经过CPU,由DMA控制器直接完成。中断方式在设备控制器的数据缓冲寄存区满后,发中断请求,CPU进行中断处理将缓冲区数据传送到内存。而DMA方式

12、则是在所要求传送的数据块全部传送到内存结束时,发中断请求,CPU进行中断处理。大大减少了CPU进行中断处理的次数和时间。,通道技术1.定义：通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入、输出操作可与CPU并行操作。2.引入通道的目的 为了使CPU从I/O事务中解脱出来，同时为了提高CPU与设备，设备与设备之间的并行工作能力,I/O通道的特点I/O通道是一种特殊的处理机具有执行I/O指令的能力通过执行通道程序来控制I/O操作指令类型单一,没有自己的内存,3.通道程序 通过执行通道程序,并与设备控制器共同完成对I

13、/O设备的控制,通道程序的每条指令含如下信息:操作码,内存地址,计数,结束位P,记录结束R 通道可实现CPU、通道和I/O设备三者并行工作。例：,4.分类1)字节多路通道 字节多路通道以字节为单位传输信息，它可以分时地执行多个通道程序。当一个通道程序控制某台设备传送一个字节后，通道硬件就控制转去执行另一个通道程序，控制另一台设备传送信息。特点：主要连接以字节为单位的低速I/O设备。如打印机，终端。以字节为单位交叉传输，当一台传送一个字节后，立即转去为另一台传送字节含有许多非分配型子通道(几十到几百),每个子通道连接一台低速或中速字节设备,子通道按时间片轮转方式共享主通道,只要扫描一轮的速率足够

14、快,便不会丢失信息。,2)数组选择通道 数组选择通道是以成组方式工作的，即每次传送一批数据，故传送速度很高。选择通道在一段时间内只能执行一个通道程序，只允许一台设备进行数据传输，当这台设备数据传输完成后，再选择与通道连接的另一台设备，执行它的相应的通道程序主要连接磁盘，磁带等高速I/O设备可连接多台高速块设备,但由于只含有一个分配型子通道,当某台设备占用了该通道,便由它独占,直到用完释放为止,显然它的利用率低。,3)数组多路通道 它结合了选择通道传送速度高和字节多路通道能进行分时并行操作的优点。它先为一台设备执行一条通道指令，然后自动转接，为另一台设备执行一条通道指令主要连接高速设备将以上两种

15、结合,它含有多个非分配型子通道,具有很高的传输速率,又有满意的通道利用率。这样，对于连接多台磁盘机的数组多路通道，它可以启动它们同时执行移臂定位操作，然后，按序交叉地传输一批批数据。数据多路通道实际上是对通道程序采用多道程序设计的硬件实现,4.解决瓶颈问题,交叉连接,5.3 缓冲技术1.缓冲技术的引入 凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。在操作系统中采用缓冲是为了实现数据的I/O操作，以缓解CPU与外部设备之间速度不匹配的矛盾，提高资源利用率缓冲技术减少了I/O设备对处理器的中断请求次数简化了中断机制节省了系统开销,2.缓冲区设置硬缓冲：在设备中设置缓冲区，由硬件实现软缓冲：在

16、内存中开辟一个空间，用作缓冲区3.缓冲区管理 单缓冲：操作系统中设置一个缓冲区 双缓冲：操作系统中为某一设备设置两个缓冲区 循环缓冲：将多个缓冲区组织成循环缓冲 缓冲池：多个缓冲区连接起来统一管理，常采用多缓冲管理,1.单缓冲(Single Buffer)块设备输入时,输入到缓冲区的时间为T,OS将数据从缓冲区传到用户区的时间为M,CPU处理这块数据的时间为C;显然T和C是可以并行的。,字符设备输入输出时,缓冲区用于暂存一行数据。,2.双缓冲(Doubel Buffer)为了加快I/O速度提高设备利用率,又引入了双缓冲机制(缓冲对换 Buffer Swapping);如果CT,块设备可连续输入

17、。,如果要实现两台机器之间同时双向通信,必须在两台机器中都设置两个缓冲区,一个发送一个接收。,3.循环缓冲 I/O进程和计算进程对缓冲区的使用相当于生产者消费者问题,当两者之间速度基本相匹配时,双缓冲能获得较好的效果,但两者之间速度变化很大相差很远时效果不理想;可将多个缓冲组成循环形式。以输入为例,空缓冲区为R,已装满数据的缓冲区为G,正在使用的工作缓冲区为C,使用时要考虑进程的同步:,当计算进程要用缓冲区的数据时调用Getbuf(Nextg)过程,将Nextg指示的缓冲区提供给计算进程使用,并令Current 指针指向它的第一单元,Nextg 移向下一个G。当输入进程要空缓冲区输入数据时调G

18、etbuf(Nexti)过程,将Nexti指示的缓冲区供给输入进程,Nexti下移。,当计算进程把当前缓冲区C中的数据提取完时,调用Releasebuf()过程,将该空缓冲区释放,将其状态该为R。当输入进程把缓冲区装满时,也应调用Releasebuf()过程,将该空缓冲区释放,将其状态该为G。注意:计算进程和输入进程的同步,Nexti 和 Nextg 追赶。,4.缓冲池(Buffer Pool),缓冲池的组成 空缓冲链队列emp:由空缓冲区组成 输入缓冲链队列inq:由装满输入数据的缓冲区组成 输出缓冲链队列out:由装满输出数据的缓冲区组成 4种工作缓冲区 收容输入、提取输入、收容输出、提取

19、输出。从某队列上取下来操作完后再挂到另一队列上对缓冲池队列操作的两个过程 缓冲池中的队列是临界资源要考虑互斥与同步,缓冲区工作方式,提取输出,收容输入,提取输入,收容输出,缓冲池,hin,sin,sout,hout,用户程序,收容输入的工作方式:当输入进程需要输入数据时调用Getbuf(emp,hin)过程,从emp队列首摘下空缓 冲区作为收容输入工作缓冲区hin(2)把数据输入到工作缓冲区hin(3)调用Putbuf(inq,hin),将hin挂到inq队列尾,提取输入工作方式：当计算进程需要提取输入数据时(1)调用Getbuf(inq,sin)过程,从inq队列头摘下缓冲区 作为提取输入工

20、作缓冲区sin(2)计算进程从工作缓冲区sin中提取数据(3)调用Putbuf(emp,sin),将sin挂在emp队列尾,Procedure Getbuf(q,buf);从q队列头摘下缓冲区buf begin Wait(RS(q);信号量RS(q)是队列q的长度 Wait(MS(q);MS(q)是对q操作的互斥信号量 buf:=Takbuf(q);Signal(MS(q);endProcedure Putbuf(q,buf);buf加到q队列的队尾 begin Wait(MS(q);Addbuf(q,buf);Signal(MS(q)Signal(RS(q);end,5.4 设备分配,多道程

21、序环境下 用户进程提出I/O请求，设备分配程序按一定策略把用户所需的设备分配给用户进程。OS是怎样对设备进行分配的？采用了哪些数据结构？,5.4.1 设备分配中的数据结构,具有通道的I/O系统结构,1.系统设备表（SDT）,表目1.表目i.,设备类型设备标识符设备状态:忙/闲设备队列的队首指针指向控制器表的指针重复执行次数或时间驱动程序入口,设备控制表DCT,系统设一张系统设备表,记录系统中全部设备的情况,每个设备占一个表目。,2.控制器控制表、通道控制表,COCT,CHCT,每个控制器设一张COCT,每个通道设一张CHCT,控制器标识符控制器状态:忙/闲指向相连通道表的指针控制器队列的首指针

22、控制器队列的尾指针,通道标识符通道状态:忙/闲相连控制器表的指针通道队列的首指针通道队列的尾指针,设备分配时涉及的问题,1.设备的固有属性 独占、共享、虚拟2.设备分配算法 先来先服务、优先级高者优先3.设备分配的安全性安全分配方式:进程发出I/O请求便被阻塞直到I/O完成不安全分配方式:进程发出I/O请求后继续执行,需要时 又发出第二个第三个I/O请求,满足请求保持条 件可能引起死锁。进程推进速度快。4.设备的独立性,设备独立性,1.设备独立性(Device Independence)为了提高OS的可适应性和可扩展性,现代OS都实现了设备独立性(设备无关性),引入了逻辑设备和物理设备两个概念

23、,使应用程序用逻辑设备名来请求某类设备,独立于具体的物理设备。OS将逻辑设备名转换为具体的物理设备。带来的好处是:(1)设备分配的灵活性(2)易于实现I/O的重定向,2.设备独立性软件(1)执行所有设备的公有操作 对独立设备的分配和回收 将逻辑设备名映射为物理设备名找到驱动程序 对设备进行保护 缓冲管理 差错控制(2)向用户层软件提供统一接口 I/O软件组织成一种层次结构,低层软件用来屏蔽具体设备细节,高层软件则为用户提供一个简洁规范的界面。它体现了I/O 设计的关键的概念:设备无关性,其含义就是使程序员写的软件无须修改,就能进行不同设备上的I/O操作。如对各种设备的读操作都使用read;对各

24、种设备的写操作都使用write。,I/O软件的层次结构及功能,3.逻辑设备名到物理设备名映射(1)逻辑设备表(LUT)逻辑设备名 物理设备名驱动程序入口地址/dev/tty 3 1024/dev/print 5 2048(2)逻辑设备表的设置 整个系统只设一张LUT不允许有相同的逻辑设备名,用在单用户系统中。每个用户设一张LUT,用户登录建立进程时,建立一张LUT并将该表放入该进程的PCB中,用在多用户系统中。,(1)分配设备:根据物理设备名,查找系统设备表SDT,找出该设备的设备控制表DCT,再根据DCT中的设备状态字忙否执行,若忙将请求I/O的进程挂在设备等待队列上,否则检查安全性,安全则

25、分配。(2)分配控制器:分到设备后,再到DCT中找出与之连结的控制器控制表COCT,再根据COCT中的状态字忙否执行等待或分配控制器。(3)分配通道:在COCT中找到与之连结的通道控制表CHCT,再根据CHCT中的状态字忙否执行等待或分配通道。,5.4.4 独占设备的分配程序,5.4.5 SPOOLing 技术Simultaneous Peripheral Operations On-Line,脱机输入输出是利用外围机脱机进行I/O操作。SPOOLing是联机情况的同时外围操作(假脱机操作)用输入进程 SPI 模拟脱机输入时外围机的功能,把低速输入设备的数据送到高速磁盘上。用输出进程 SPO模

26、拟脱机输出时外围机的功能,把高速磁盘的数据送到低速输出设备上。SPOOLing系统特点 提高了I/O速度,缓和CPU高速与I/O慢速的矛盾。将独占设备改造为共享设备。实现虚拟设备,一台物理设备变为多台逻辑设备。,SPOOLing 系统的组成,(1)输入井、输出井:收容输入/出的数据(2)输入/出缓冲区Bi/Bo:内存缓冲区,暂存输入/出数据(3)输入/出进程SPi/SPo:模拟脱机输入/出时的外围机,实例:共享打印机,把一台打印机改造为多个用户可共享(1)由输出进程 SPo 将打印的数据从内存送到输出井(2)由SPo将用户要求填入请求打印表中,并将请求打印表挂到请求打印队列上(4)若打印机空闲

27、,SPo将从请求打印队列的队首取一张请求打印表,根据打印要求将打印数据从输出井送到Bo,再由打印机打印。,5.5 设备处理,5.5.1 设备驱动程序的功能和特点1.设备驱动程序的功能(1)将接受到的抽象(逻辑)要求转化为具体(物理)要求。(2)检查用户I/O请求的合法性,读出和检查I/O设备的状态,传递有关参数,设置设备的工作方式。(3)发出I/O命令,若设备空闲则启动I/O设备,否则将请求进程挂到设备等待队列上。(4)及时响应由控制器或通道发来的中断请求,并根据中断类型调用相应的中断处理程序进行处理。(5)对于设置通道的计算机系统,驱动程序还应能够根据用户的I/O请求,自动地构造通道程序。,

28、2.设备处理方式(1)为每类设备设置一个I/O进程。(2)整个系统设置一个I/O进程。(3)只为各类设备设置相应的设备处理程序供调用。,3.设备驱动程序的特点(1)驱动程序主要是在请求I/O的进程与设备控制器之间的一个通信程序。(2)驱动程序与I/O设备的特性密切相关。(3)驱动程序与I/O控制方式相关。(4)有些驱动程序固化在ROM上。,将抽象的要求转化为具体的要求如:将逻辑盘块号转换为具体的盘面、磁道和扇区2.检查I/O请求的合法性如:打印机请求读,以读方式打开磁盘后请求写3.读出并检查设备的状态如:读并查状态是否为就绪,确定启动控制器或等待4.传送必要的参数如:启动磁盘,先将字节数和内存

29、起始地址送控制器5.工作方式的设置如:异步通信,先设置波特率、校验方式、停止位等6.启动I/O设备:向控制器发送控制命令,将自己阻塞进入睡眠状态。在控制器控制下进行指定的I/O操作。7.完成I/O后,设备控制器向CPU发出中断请求;CPU响应转向中断处理程序唤醒相应的设备驱动进程。,设备驱动程序的处理过程,在设备控制器的控制下,设备完成I/O操作后,设备控制器便向CPU发出一个中断请求;CPU响应后,转向中断处理程序,中断处理含以下几个步骤：(1)唤醒被阻塞的驱动(程序)进程(2)保护被中断进程的CPU环境(3)分析中断原因转入相应的设备处理程序(4)进行中断处理(5)恢复被中断进程的现场,5

30、.5.3 I/O完成中断处理程序的处理过程,5.6.1 磁盘性能简述1.磁盘的特点和结构:容量大,断电后仍可保存信息,存取速度较块,成本较低,可实现直接(随机)存取,存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。盘设备由两部分组成:驱动部分+存储介质(磁盘)磁盘以恒定转速旋转,磁臂沿径向驱动磁头移动到所要求的磁道上,并等待所要求的扇区开始位置旋转到磁头下,开始读写数据,在磁头和缓冲区间传输数据。,5.6 磁盘存取设备管理,2.磁盘数据组织和格式 信息记录在磁道上,多个盘片,正反两面都用来记录信息,每面一个磁头,所有盘面中处于同一磁道号上的所有磁道组成一个柱面。,物理地址形式:磁头号(盘

31、面号)、磁道号(柱面号)、扇区号 磁盘格式化的一种形式：p172图5-22每个物理扇区600个字节包含：标识符字段 数据字段 Track#:磁道号Gap:为间隙Head#:磁头号 Synch:为定界符Sector#:扇区号CRC:用于校验,3.磁盘类型：磁盘分为硬盘和软盘,单片盘和多片盘,固定头磁盘和移动头磁盘等。固定头磁盘:每个磁道设置一个磁头,所有磁头都被安装在一个刚性磁臂中,各磁头并行读写,磁头不需要机械移动,速度快但成本高,用于大容量硬盘上。移动头磁盘:一个盘面只有一个磁头,变换磁道时需要移动磁头,速度慢但成本低,微机上配置的软盘和硬盘(温盘)都采用这种结构。活动硬盘:增加灵活性和便携

32、性。,4.磁盘访问时间（Ta),寻道时间Ts:把磁头移动定位到指定磁道所经历的时间,启动时间s与移动n条磁道时间之和 Ts=mn+s 一般为530ms旋转时间Tr 等待指定扇区旋转移动到磁头下面所经历的时间 5400r/min=90r/sec的硬盘:平均Tr=1/2r=5.55ms传输时间Tt 从磁盘到内存读写数据实际经历的时间:Tt=b/rN 其中b为读写字节数,N为一条磁道总字节数 访问时间:Ta=Ts+1/2r+b/rN 主要与Ts有关,5.6.2 磁盘调度,当多个进程都需要访问磁盘时,访盘请求在等待,应采用一定的策略,对这些请求的服务顺序调整安排,旨在降低平均磁盘服务时间,达到公平、高

33、效。公平：一个I/O请求在有限时间内满足。高效：减少设备机械运动所带来的时间浪费。磁盘调度考虑的问题：一次访盘时间=寻道时间+旋转延迟时间+存取时间(1)减少寻道时间(活动头磁盘)(2)减少延迟时间(固定头磁盘)磁盘调度算法:,1.先来先服务FCFS(First-Come First Served)按访问请求到达的先后次序服务优点：简单,公平；缺点：效率低,相临两次请求可能会造成最内到最外的柱面寻道,使磁头反复移动,增加了平均寻道时间设磁盘访问序列:80,55,58,39,18,90,160,150,38,184,2.最短寻道时间优先SSTF(Shortest Seek Time First)

34、优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先 优点：磁盘的平均寻道时间最小 缺点：进程饥饿现象,有时会造成与当前磁道距离远的访问请求长期等待得不到服务(不公平)磁盘访问序列:80,55,58,39,18,90,160,150,38,184,3.扫描算法SCAN电梯调度算法 克服最短寻道优先的缺点,既考虑距离,又考虑方向 具体做法:当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中对遇到的访问请求进行服务,然后,判断该方向上是否还有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。,4.循环扫描(CSCAN)算法 SCAN算

35、法对两端磁道请求不利,可改进为循环扫描算法CSCAN。本算法规定磁头单向移动(如向外),移动到最外磁道后立即返回最里面要访问的磁道,构成循环扫描。,5.N-Step-SCAN 和FSCAN算法(1)磁臂粘着现象:进程对某一磁道反复访问,从而垄断了整个磁盘,引起磁臂粘着(2)N-Step-SCAN 和FSCAN算法:将磁盘请求队列按请求顺序分为多个(或2个)长度为N的子队列,每个子队列用SCAN算法;当N很大时接近于SCAN算法,当 N=1时蜕化为FCFS算法。FSCAN算法是2个子队列的N-Step-SCAN算法,一 个是由当前所有磁盘请求形成的队列,按SCAN算法进行处理;扫描期间新的磁盘请

36、求放入另一个等待队列,前一个队列处理完后,再处理新队列。如此反复,公平合理。,5.6.3 磁盘高速缓存(Disk Cache),1.磁盘高速缓存的形式(1)专用:在内存中单独开辟一块固定的区域专用。(2)共享:所有空闲内存为缓冲池与请求分页系统共享2.数据交付方式(1)数据交付(2)指针交付3.置换算法 常用的算法有:最近最久未使用算法LRU,最近未使用算法NRU和最少使用算法LFU。许多系统除了考虑最近最久未使用这一原则外还要考虑：访问频率、可预见性、数据的一致性。4.周期性地写回磁盘 根据LRU算法,经常访问的盘块可能长期不被回写,可能导致丢失数据,可采用周期性(几十秒)地写回磁盘。,5.

37、6.4 提高磁盘I/O速度的其他方法,1.提前读 预先将下一盘块数据一次读入减少读盘次数。2.延迟写 考虑缓冲区的数据不久之后可能还会访问故暂时不写入磁盘,将它挂在空闲队列的末尾,当它最久未被访问，到了队列之首要被淘汰时再写入磁盘。3.优化物理块的分布 分配物理块时,把有可能顺序存取的块放在一起,尽量分布在同一柱面或相邻柱面上,从而减少磁盘臂的移动次数。但采用线性链表来组织空闲块时比较困难,此时,将同一磁道的若干个盘块组织成一簇,以簇为单位进行分配,可减少磁头的平均移动距离。4.虚拟盘 利用内存空间去仿真磁盘,又称RAM盘;断电或关机后虚拟盘的数据将丢失,因此虚拟盘仅放临时数据。,5.6.5

38、磁盘冗余阵列,1.并行交叉存取 为提高对磁盘的访问速度,用N台磁盘驱动器组成磁盘阵列,系统将数据分为若干个子盘块数据分别存储到各个磁盘的相同位置上,并行传输到内存,由于采用了并行存取方式加快了访问速度N-1倍。2.廉价磁盘冗余阵列(Redundant Array of Inexpensive Disk)为提高磁盘存储数据的可靠性,采用冗余存储;如:N=7,6个盘做数据盘,1个盘做奇偶校验盘,校验盘存储6个数据盘的奇偶校验值;当某个盘损坏时可以用其它6个盘的数据盘恢复数据;RAID 有 0-7级,其中 0 级无冗余,1 级是镜像存储冗余50%,3 级使用专用校验盘,5 级将校验值螺旋分布在阵列的

39、所有磁盘上。3.RAID的优点 可靠性高、磁盘的访问速度高、性能/价格比高。,校验值螺旋分布在阵列的所有磁盘上,I/O 设备分类按传输速率:低速(100KB/s)按信息交换单位分类:块设备、字符设备 按共享属性分类:独占设备、共享设备、虚拟设备2.设备控制器 控制器CPU与I/O设备之间的接口,可编址 接收从CPU发来的命令,并控制I/O设备工作。3.设备控制器的功能 地址识别、接收和识别命令、指挥设备执行 接收和记录设备的状态向CPU发中断请求。数据交换、数据缓冲、差错控制4.Unix用设备文件表示I/O设备 主要属性:文件名、类型、主设备号、次设备号,5.I/O通道 I/O通道是一种特殊的

40、处理机 具有执行I/O指令的能力 通过执行通道程序来控制I/O操作 指令类型单一,没有自己的内存6.通道类型 字节多路通道、数组选择通道、数组多路通道7.微机I/O总线 PC/XT、ISA、EISA、VESA、PCI、USB、SCSI8.I/O控制方式 程序I/O方式、中断方式、DMA方式、I/O通道方式9.I/O缓冲方式 单缓冲、双缓冲、循环缓冲、缓冲池,10.缓冲池组成链队列emp,inq,out,队列操作过程Getbuf,Putbuf4种工作缓冲区:hin、sin、sout、hout11.设备分配中的数据结构 设备控制表DCT、控制器控制表COCT、通道控制表CHCT、系统设备表 SDT

41、12.设备分配策略 设备的固有属性:独占、共享、虚拟 设备分配算法:先来先服务、优先级高者优先 安全性:安全分配方式、不安全分配方式(快速会死锁)设备的独立性(设备无关性):逻辑设备和物理设备13.SPOOLing系统(联机情况的同时外围操作)组成:输入/出井、缓冲区Bi/Bo、输入/出进程SPi/Spo 用SPi/Spo模拟脱机输入/出时外围机的功能,14.设备驱动程序的功能(1)将接受到的抽象(逻辑)要求转化为具体(物理)要求。(2)检查用户I/O请求的合法性,设置设备的工作方式。(3)发出I/O命令(4)及时响应由控制器或通道发来的中断请求(5)对有通道系统,能根据I/O请求,自动地构造

42、通道程序15.设备驱动程序的处理过程(1)将抽象的要求转化为具体的要求(2)检查I/O请求的合法性、读出并检查设备的状态(3)传送必要的参数、设置工作方式(4)向控制器发送控制命令启动I/O设备,将自己阻塞(5)完成I/O后,CPU响应中断唤醒相应的设备驱动进程16.磁盘存取时间 寻道时间Ts、旋转时间Tr、传输时间Tt,17.磁盘调度算法 先来先服务FCFS、最短寻道时间优先SSTF 扫描算法SCAN电梯调度算法、循环扫描(CSCAN)N-Step-SCAN:分为多个长度为N的子队列 FSCAN算法:分2个子队列(当前和另一队列长度不定)18.磁盘高速缓存 形式:专用-开辟固定专用区,共享-与请求分页系统共享 数据交付方式:数据交付、指针交付 置换算法:最近最久未用LRU算法(多用)最近未用NRU算法和最少使用LFU算法。周期性地写回磁盘:保证不丢失数据周期性地写回19.提高磁盘I/O速度的其他方法 提前读,延迟写,优化物理块的分布,虚拟盘,磁盘阵列20.廉价磁盘冗余阵列RAID(冗余存储,提高可靠性)优点:可靠性高、磁盘的访问速度高、性能/价格比高,作业,P1981、2、3、4、6、9、10、11,