虚拟存储器培训

计算机操作系统计算机操作系统主讲教师：曹建秋主讲教师：曹建秋 贺清碧贺清碧课程主要内容课程主要内容操作系统引论（操作系统引论（1 1章）章）进程管理（进程管理（2-32-3章）章）存储管理（存储管理（4 4章）章）设备管理（设备管理（5 5章）章）文件管理（文件管理（6 6章）章）操作系统接口（操作系统接口（7 7章）章）系统安全性（系统安全性（9 9章）章）*分布式操作系统分布式操作系统第第5 5章章 设设 备备 管管 理理vI/OI/O系统系统vI/OI/O控制方式控制方式v缓冲管理缓冲管理v设备分配设备分配v设备处理设备处理v磁盘存储器管理磁盘存储器管理 v*UNIXUNIX系统中的设备管理系统中的设备管理本章作业本章作业5.1 I/O 5.1 I/O 系统系统qI/O设备q设备控制器qI/O通道qI/O系统的总线系统qI/O系统的结构I/O I/O 系统的组成系统的组成:I/O设备、设备控制器、I/O通道*、总线及相应软件5.1.1 I/O 5.1.1 I/O 设备设备 1 1、I/O I/O设备的类型设备的类型系统设备1）按设备的从属关系分类用户设备系统设备：在OS生成时就已登记在系统中的标准设备，如键盘、显示器、打印机等。用户设备：在OS生成时未登记在系统中的非标准设备，如鼠标、绘图仪、扫描仪等。独享设备2）按使用方式/共享属性分类共享设备虚拟设备独享/独占设备：在一段时间只允许一个用户进程访问的设备。多数低速设备属此类，打印机就典型的独享设备。共享设备：在一段时间只允许多个用户进程同时访问的设备。磁盘就典型的共享设备。虚拟设备：指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户进程同时使用，通常把这种经过虚拟技术处理后的设备称为虚拟设备。低速设备3）按传输速率分类中速设备高速设备低速设备：传输速率仅为每秒钟几个字节至数百个字节的设备。典型的有：键盘、鼠标、语音的输入/输出等。中速设备：传输速率仅为每秒钟数千个字节至数数万个字节的设备。典型的有：打印机等。高速设备：传输速率仅为每秒钟数百千个字节至数十兆字节的设备。典型的有：磁盘机、磁带机、光盘机等。块设备 4）按信息交换的单位分类 字符设备 块设备：信息交换的基本单位为字符块，属于有结构设备，块大小一般为512B-4KB，典型的有：磁盘、磁带等。字符设备：信息交换的基本单位为字符，典型的有：键盘、打印机和显示器等。2、设备与控制器之间的接口（P145 图5-1）三种信号线5.1.2 5.1.2 设备控制器设备控制器v设备控制器是处于CPU与I/O设备之间的接口，接收CPU发来的命令，并控制I/O设备工作，是一个可编址设备。v功能：接收和识别命令、实现数据交换、了解设备状态以及识别设备地址。设备控制器的组成n设备控制器与处理机的接口n设备控制器与设备接口nI/O逻辑寄存器：控制寄存器(存放命令及参数)、数据寄存器(存放数据)、状态寄存器(记录设备状态).设备控制器的组成数据数据寄存器寄存器控制、状态控制、状态寄存器寄存器I/O逻辑逻辑控制器控制器与设备与设备接口接口1控制器控制器与设备与设备接口接口iCPU与控制器接口与控制器接口控制器与设备接口控制器与设备接口数据线数据线地址线地址线控制线控制线数据数据状态状态控制控制数据数据状态状态控制控制.5.1.3 I/O 5.1.3 I/O 通道通道根据信息交换方式的不同，通道可分成以下几种类型：字节多路通道数组选择通道数组多路通道注：“瓶颈”问题字节多路通道字节多路通道q其工作原理:数据传送是按字节交叉方式工作。1)有一个主通道。2)含有多个子通道A、B、C3)每子通道通过一控制器与一台中中/低低速速的I/O设备相连，可同时并行向主通道传数据。4)各子通道以时间片轮转方式按字节交叉使用主通道。q优点：可连多台中/低速设备；能分时并行操作。q缺点：传输率较低。数组选择通道数据传送是按成组方式进行工作，每次传输一批数据。主要用于连接高速I/O设备。1)有一个主通道2)含有多个子通道A、B、C3)每子通道通过一控制器与一台中/低速的I/O设备相连，在一段时间内只能选择一个子通道程序执行。优点：可连多台高速设备；传输率较高。缺点：某子通道不传数据，而使主通道闲置，其它子通道也不能传数据。所以通道的利用率很低。数组多路通道数组多路通道数据传送仍是按数组方式工作。工作原理（结合两者：并行+数组）1)有一个主通道2)含有多个子通道A、B、C3)每子通道通过一控制器与一台高高/中中速速的I/O设备相连，可同时并行向主通道传数据。4)各子通道以时间片轮转方式按数组方式使用主通道。v优点：可连多台高/中速设备；能分时并行操作，传输率较高。“瓶颈瓶颈”问题问题存储器存储器通道通道1通道通道2控制器控制器1控制器控制器2控制器控制器3控制器控制器4设备设备1设备设备2设备设备3设备设备4设备设备5设备设备6设备设备7单通路I/O系统解决解决“瓶颈瓶颈”问题的方法问题的方法-多路方式多路方式通道通道2设备设备1设备设备2设备设备3设备设备4存储器存储器通道通道1控制器控制器1控制器控制器2多通路I/O系统5.1.5 I/O 5.1.5 I/O 系统的结构系统的结构CPU存储器存储器磁盘磁盘控制器控制器打印机打印机控制器控制器其它其它控制器控制器磁盘驱动器磁盘驱动器打印机打印机微型机微型机I/O系统结构系统结构-总线型总线型计算机计算机I/O通道通道1I/O通道通道2控制器控制器控制器控制器控制器控制器控制器控制器主机主机I/O系统系统具有通道具有通道设设备备5.2 I/O 5.2 I/O 控制方式控制方式常用的输入/输出控制方式：1、程序控制方式2、中断控制方式3、直接存储器访问DMA方式4、通道控制方式1、程序直接控制方式、程序直接控制方式处理机对I/O的控制采用程序直接控制方式。工作原理：主程序设备是否“准备就绪”传送数据否特点特点：控制简单，但CPU的利用率低（串行），出现忙等待（循环等待设备的I/O操作）-即轮询（轮询（Polling）问题-I/O中断 继续主程序控制设备状态的控制位控制设备状态的控制位1）command-ready （等待命令）2）Busy（忙）3）Error（错误）2、中断控制方式、中断控制方式）需数据的进程向CPU发出指令启动I/O设备输入数据。）该进程放弃处理机，等待输入完成。）输入完成后，I/O控制器向CPU发出中断请求，CPU收到后，转向中断服务程序。中断服务程序将数数据据输输入入寄寄存存器器中的数据送指定内存单元，并将原进程唤醒，继续执行。）在以后，该进程再被调度，从内存单元取出数据进行处理。优点CPU利用率大大提高（可以与I/O设备并行工作）。缺点-若中断次数较多将耗去大量CPU处理时间。3、DMA方式方式1）需数据的进程向CPU发出指令,向DMA控制器写入数据存放的内存始址、传送的字节数,并置中断位和启动位,启动I/O设备输入数据并允许中断。2）该进程放弃处理机等待输入完成，处理机被其它进程占据。3）DMA控制器采用挪用CPU周期，将一批数据写入内存中。4）DMA控制器传送完数据后，向CPU发中断请求，CPU响应后转向中断服务程序，唤醒进程，并返回被中断程序。5）在以后该进程再被调度，从内存单元取出数据进行处理。优点CPU利用率进一步提高（并行度有所提高）。缺点数据传送方向、字节数、内存地址等需由CPU控制，且每一设备需一台DMA控制器，设备增多时，不经济。4、通道控制方式、通道控制方式1）需数据的进程向CPU发出指令，CPU发启动指令指明I/O操作、设备号和对应的通道。2）该进程放弃CPU等待输入完成，CPU被其它进程占据。3）通道接收到CPU发来的启动指令后，取出内存中的通道程序执行，控制设备将数据传送到内存指定区域。4）传送完数据后，通道向CPU发中断请求，CPU响应后转向中断服务程序，唤醒进程，并返回被中断程序。5）在以后该进程再被调度，从内存取出数据进行处理。优点一个通道可控制多设备，所需CPU干预更少。CPU利用率较高（并行度较高）。缺点：通道价格较高。5.3 5.3 缓冲管理缓冲管理1、提高处理机与I/O设备的并行工作的技术：）数据传送控制方式）缓冲技术2、操作系统中，引入缓冲的主要原因1）缓冲CPU与I/O设备间速度不匹配的矛盾。2）减少中断CPU的次数、3）提高CPU与I/O设备的并行性3、缓冲实现方法两种：1）采用硬件缓冲器实现2）用软件缓冲区来实现缓冲就是用来对数据传送速度不同的设备的传送速度进行匹配/缓冲的一种常用手段。其实现方法除在关键地方可采用硬件缓冲器外，大都采用软件缓冲来实现。软件缓冲区是指在I/O操作期间，专门用来临时存放输入/输出数据的一块存储区域。4、缓冲技术的分类 单缓冲 双缓冲 循环缓冲 缓冲池 5.3 5.3 缓冲管理缓冲管理单单 缓缓 冲冲在设备和处理机之间设置一个缓冲。设备与处理机交换数据时，先把交换的数据写入缓冲区，然后需要数据的设备/处理机再从缓冲区中取走数据。特点：缓冲区数只有一个；设备与处理机对缓冲区的操作是串行的。用户进程操作系统传送输入I/O设备一块数据的处理时间一块数据的处理时间v在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间T，CPU对一块数据进行处理的时间为C，将缓冲区的数据传送到用户区所花时间为M，那么在单缓冲情况下，系统处理大量数据时，一块数据的处理时间为多少？用户进程操作系统传送输入I/O设备TMCMax(T,C)+MP156图5-11双双 缓缓 冲冲 在设备和处理机之间设置2个缓冲。设备与处理机交换数据时，先把交换的数据写入缓冲区，然后需要数据的设备/处理机再从缓冲区中取走数据。因缓冲区有2个，提高了设备与处理机并行操作的程度，只有当两个均为空时，需数据的进程才等待。特点：缓冲区数有2个；设备与处理机对缓冲区的操作可并行，提高了设备与处理机并行操作的程度。用户进程操作系统传送输入I/O设备一块数据的处理时间一块数据的处理时间v在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间T，CPU对一块数据进行处理的时间为C，将缓冲区的数据传送到用户区所花时间为M，那么在双缓冲情况下，系统处理大量数据时，一块数据的处理时间为多少？TMC当CT：C+M即MAX（C，T）+M当CT：MAX（C，T）图5-12用户进程操作系统传送输入I/O设备循循 环环 缓缓 冲冲 在设备和处理机之间设置多个大小相等的缓冲区，这些缓冲区构成环形，每一个缓冲区中含一指针指向下一个缓冲区，最后一个指向第一个缓冲区，同时还含有2个用于输入/输出的指针IN和OUT。特点：缓冲区数有多个；设备与处理机对缓冲区的操作可并行，进一步提高了设备与处理机并行操作的程度。RGGGGR123456NextiNextgRGGGGR123456NexticurrentNextg循环缓冲的组成循环缓冲缓冲区的使用Getbuf过程Releasebuf过程进程同步Nexti指针追赶上Nextg指针输入进程阻塞Nextg指针追赶上Nexti指针计算进程阻塞1、缓冲池：将系统内所有的缓冲区统一管理起来，就形成了能用于输入/输出的缓冲池。缓冲池通常由若干大小相同的缓冲区组成，是系统的公用资源，任何进程都可以申请使用缓冲池中的各个缓冲区。2、缓冲池的组成（数据结构）三个队列：空缓冲队列、装满输入数据队列、装满输出数据队列四个工作缓冲区：收容输入缓冲区、提取输入收容输出、提取输出缓冲区缓缓 冲冲 池池3、getbufgetbuf过程和过程和putbufputbuf过程过程ProcedureGetbuf(type)beginwait(rs(type);wait(ms(type);B(number):=Takebuf(type);signal(ms(type);end缓冲池 Procedure putbuf(type)begin wait(ms(type);Addbuf(type,number);signal(ms(type);signal(rs(type);end4 4、操作系统对缓冲池的管理、操作系统对缓冲池的管理-工作方式工作方式hinsinsouthout用户程序缓冲池提取输入收容输出提取输出收容输入缓冲区的工作方式缓冲区的工作方式输入进程需要输入数据时：输入设备收容输入缓冲区-Getbuf(emq)1)从空缓冲队列的队首取一空缓冲区用作收容输入缓冲区2)输入设备将数据输入收容输入缓冲区并装满3)将此缓冲区挂到装满输入数据队列队尾。计算进程需要输入数据时：提取输入缓冲区CPU-Getbuf(inq)1)从装满输入数据队列队首取一满缓冲区用作提取输入缓冲区2)CPU从提取输入缓冲区中取出数据至用完3)将空缓冲区挂到空缓冲队列队尾。4 4、操作系统对缓冲池的管理、操作系统对缓冲池的管理-工作方式工作方式计算进程需要输出数据时：CPU 收容输出缓冲区-getbuf(emq)1)从空缓冲队列队首取一空缓冲区用作收容输出缓冲区2)CPU将数据输入其中并装满3)将收容输出缓冲区挂到装满输出数据队列队尾。输出进程需要输出数据时：提取输出缓冲区-输出设备-getbuf(outq)1)从装满输出数据队列队首取一满缓冲区用作提取输出缓冲区2)输出设备从中取出数据至用完3)将空缓冲区挂到空缓冲队列队尾4 4、操作系统对缓冲池的管理、操作系统对缓冲池的管理-工作方式工作方式5.5.4 4 设备分配设备分配设备分配中的数据结构设备分配的策略/应考虑的因素设备独立性设备分配程序SPOOLING技术7.4.1 7.4.1 设备分配中的数据结构设备分配中的数据结构设备控制表DCT(device control table)控制器控制表COCT(controller control table)通道控制表CHCT（channel control table）系统设备表SDT(system device table)DCT表目1表目i设备类型 设备标识符DCT指针获得设备的进程控制器标识符 控制器状态：忙/闲CHCT指针控制器等待队列指针通道标识符通道状态：忙/闲通道等待队列指针SDTCOCTCHDT设备类型 设备标识符设备状态：忙/闲COCT指针设备等待队列指针5.4.2 5.4.2 设备分配策略设备分配策略/应考虑的因素应考虑的因素1、设备的使用性质/固有属性 （独享分配、共享分配、虚拟分配）2、设备分配算法 （先请求先服务、优先级高者优先）3、设备分配的安全性（防止进程死锁）4、设备独立性：是指用户在编制程序时所用的设备(逻辑)与实际使用的设备无关 先请求先服务先请求先服务当有多进程对同一设备提出I/O请求时，系统根据这些进程发出请求的先后次序将它们排成一个设备请求队列，设备分配程序总是把设备分配给队首的进程。优先级高者优先优先级高者优先按照进程优先级的高低进行分配。即当多进程对同一设备提出I/O请求时，谁优先级高，就将设备分配给谁。若优先级相同，则按先请求先服务进行分配。5.4.3 5.4.3 设备独立性设备独立性v设备独立性概念（设备无关性）v设备独立性的实现n逻辑设备（应用程序）和物理设备（执行）n设备分配时的灵活性n易于实现I/O重定向n设备独立性软件n执行所有设备的公有操作n向用户层（文件层）软件提供统一的接口n逻辑设备名到物理设备名映射的实现n逻辑设备表LUT(LogicalUnitTable)nLUT设置问题(图5-8)整个系统设置一张LUT；每个用户设一张LUT设备独立性相关概念设备独立性相关概念v设备独立性概念（设备无关性）为提高OS的可适应性和可扩展性，而将应用程序独立于具体使用的物理设备。vI/O重定向指用于I/O操作的设备可以更换，即重定向，而不必改变应用程序。v所有设备的公有操作独立设备的分配与回收；将逻辑设备名映射为物理设备名；对设备进行保护（禁直访）；缓冲管理；差错控制。逻辑设备表逻辑设备表LUT(Logical Unit Table)逻辑设备名物理设备名驱动程序入口地址/dev/tty31024/dev/print52046逻辑设备名系统设备表指针/dev/tty3/dev/print5(a)(b)5.4.4 5.4.4 独占独占设备的分配程序设备的分配程序v基本的设备分配程序n分配设备n分配控制器n分配通道n问题（“瓶颈”）n进程以物理设备名来提出I/O请求n采用的是单通路的I/O系统结构v设备分配程序的改进n增加设备的独立性(进程以逻辑设备名来提出I/O请求)n考虑多通路情况分配设备分配设备物理设备名物理设备名在在SDT找找DCT设备状态设备状态忙忙进程插入进程插入设备等待队列设备等待队列按算法计算按算法计算本次分配的安全性本次分配的安全性安全安全分配设备分配设备进程插入进程插入设备等待队列设备等待队列返回返回yNNY分配控制器分配控制器物理设备分配物理设备分配DCT找找COCT控制器状态控制器状态忙忙进程插入进程插入控制器等待队列控制器等待队列分配控制器分配控制器返回返回YN分配通道分配通道控制器分配控制器分配COCT找找CHT通道状态通道状态忙忙进程插入进程插入通道等待队列通道等待队列分配通道分配通道返回返回YNSPOOLINGSPOOLING技术技术(Simultaneaus Periphernal Operations On-Line)(Simultaneaus Periphernal Operations On-Line)v脱机输入、输出技术 为了缓和CPU的高速性与I/O设备的低速性间矛盾而引入，该技术在外围控制机的控制下实现低速的I/O设备与高速的磁盘之间进行数据传送。vSPOOLING技术vSPOOLING系统的组成vSPOOLING系统的特点n提高了I/O速度n将独占设备改造为共享设备n实现了虚拟设备功能SPOOLING技术技术(Simultaneaus Periphernal Operations On-Line)vSPOOLINGSPOOLING技术技术 在多道程序下，用一程序来模拟外围控制机，实现将数据从磁盘传送到低速的输出设备上，从而可在主机的直接控制下，实现脱机输入、输出功能，进而实现外围操作与CPU对数据处理的并行操作,这种在联机情况下实现的同时外围操作称为SPOOLING技术，是对脱机输入、输出工作的模拟，是操作系统中采用的一项将独占设备改造成为共享设备的技术。SPOOLING系统的组成输入进程输入进程 输出进程输出进程输入缓冲区输入缓冲区输出缓冲区输出缓冲区输入设备输入设备输出设备输出设备输入井输入井输出井输出井外存外存内存组成1、输入井、输出井 2、输入缓冲区、输出缓冲区3、输入进程、输出进程 4、请求打印队列SPOOLING技术技术v在操作系统中，引入虚拟设备的原因在操作系统中，引入虚拟设备的原因 引入虚拟设备是为了克服独占设备速度较慢、降低设备资源利用率的缺点，从而提高设备的利用率。v虚拟设备虚拟设备 是指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户进程使用，通常把这种经过虚拟技术处理后的设备称为虚拟设备。5.5 5.5 设备处理设备处理v设备驱动程序的功能和特点n设备驱动程序的功能n设备处理方式n设备驱动程序的特点v设备驱动程序的的处理过程v中断处理程序的处理过程设备驱动程序的功能设备驱动程序的功能v将接收到的抽象要求转换为具体要求。v检查用户I/O请求的合法性，I/O设备状态，传参数，设设备的工作方式。v按处理机的I/O请求去启动指定的设备进行I/O操作v及时响应由控制器或通道发来的中断请求，并进行相应处理v按I/O请求构成相应通道程序。设备处理方式设备处理方式v为每一类设备设置一进程，专门执行其I/O操作。v在整个系统中设置一个进程，执行所有的I/O操作。v不设置专门的设备处理进程，而为各类设备设置相应的设备驱动程序。设备驱动程序的特点设备驱动程序的特点v是请求I/O的进程与设备控制器之间的一个通信程序。v与I/O设备的特性紧密相关v与I/O控制方式紧密相关v与硬件紧密相关，因而其中一部分程序必须用汇编语言编写。设备驱动程序的的处理过程设备驱动程序的的处理过程v将接收到的抽象要求转换为具体要求。v检查用户I/O请求的合法性v读出和检查 I/O设备状态v传送必要参数v设置设备的工作方式。v按处理机的I/O请求去启动指定的设备进行I/O操作中断处理程序的处理过程中断处理程序的处理过程v唤醒被阻塞的驱动程序进程v保护被中断进程的CPU环境v分析中断原因、转入相应的设备中断处理程序v进行中断处理v恢复被中断进程的现场5.6 磁盘存储器磁盘存储器提高磁盘I/O速度的主要途径：（1）选择性能好的磁盘（2）采用好的磁盘调度算法（3）设置磁盘高速缓存（Disk Cache）（4）其它方法（5）采用高度可靠、快速的容量磁盘系统_谦价磁盘冗余阵列1 1、磁盘性能、磁盘性能v磁盘性能简述磁盘性能简述n数据的组织数据的组织n磁盘结构磁盘结构、磁道、柱面、扇区、磁盘格式化、磁道、柱面、扇区、磁盘格式化n磁盘物理块的地址：磁盘物理块的地址：柱面号柱面号 磁头号磁头号 扇区号扇区号n磁盘类型（磁盘类型（固定头磁盘、移动头磁盘固定头磁盘、移动头磁盘）n访问时间访问时间n寻道时间：寻道时间：将磁头从当前位置移到指定磁道所经历时间将磁头从当前位置移到指定磁道所经历时间n旋转延迟时间：旋转延迟时间：指定扇区移动到磁头下面所经历时间指定扇区移动到磁头下面所经历时间n传输时间：传输时间：将扇区上的数据从磁盘读出将扇区上的数据从磁盘读出/向磁盘写入数据所经历的向磁盘写入数据所经历的时间。时间。磁 盘 结 构磁臂磁头2 2、磁盘调度算法磁盘调度算法v磁盘调度算法磁盘调度算法n早期的磁盘调度算法早期的磁盘调度算法n先来先服务先来先服务FCFSFCFSn最短寻道时间优先最短寻道时间优先SSTFSSTFn扫描算法扫描算法n扫描扫描(SCAN)(SCAN)算法算法n循环扫描循环扫描(CSCAN)(CSCAN)算法算法n*N-STEP-SCANN-STEP-SCAN调度算法调度算法n*FSCAN*FSCAN调度算法调度算法例例：假设一个请求序列：假设一个请求序列：98,183,37,122,14,124,65,67 98,183,37,122,14,124,65,67 磁头当前的位置在磁头当前的位置在5353。FCFS FCFS 先来先服务先来先服务按进程请求访问磁盘的先后次序进行调度。下磁道移道数98451838537146122 85141081241106559672总道数总道数640平均平均80特点：简单、较合理，但未对寻道进行优化。最短寻道时间优先（最短寻道时间优先（SSTFSSTF）l选择从当前磁头位置所需寻道时间最短的请求。选择从当前磁头位置所需寻道时间最短的请求。下磁道下磁道移道数移道数6512672373014 23988412224124218359总道数总道数236平均平均29.5特点：寻道性能比FCFS好，但不能保证寻道时间最短，且有可能引起某些请求的饥饿。扫描算法（扫描算法（SCANSCAN）v磁头从磁盘的一端开始向另一端移动，沿途响应访问请求，直到到达了磁盘的另一端，此时磁头反向移动并继续响应服务请求。有时也称为电梯算法。磁头向磁道号增加的方向移动。下磁道移道数65126729831122 24124218359371461423总道数299平均37.4下磁道移道数37161423655167 2983112224124218359总道数208平均26 磁头开始向磁道号减少的方向移动磁头开始向磁道号减少的方向移动特点特点：寻道性能较好，避免了饥饿，但不利于远离磁头一：寻道性能较好，避免了饥饿，但不利于远离磁头一端的访问请求。端的访问请求。循环扫描算法（循环扫描算法（CSCANCSCAN）l l规定磁头单向移动规定磁头单向移动。特点：消除了对两端磁道请求的不公平。特点：消除了对两端磁道请求的不公平。下磁道移道数65126729831122 24124218359141693723总道数322平均40.3N-STEP-SCAN调度算法vSSTFSSTF、SCANSCAN及及CSCANCSCAN存在的问题存在的问题-磁臂粘着磁臂粘着在SSTF、SCAN及CSCAN几种调度算法中，可能出现磁臂停留在某处的情况，即反复请求某一磁道，从而垄断了整个磁盘设备，这种现象称为磁臂粘着。vN-STEP-SCANN-STEP-SCAN调度算法调度算法 将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，而每一子队列按SCAN算法处理。N=1 FCFS算法 N很大 SCAN算法 N取半长度 FSCAN算法3、设置磁盘高速缓存（Disk Cache）目前，由于磁盘的目前，由于磁盘的I/OI/O速度远低内存的访问速度，而致使磁速度远低内存的访问速度，而致使磁盘的盘的I/OI/O成为计算机系统的瓶颈。为提高磁盘的成为计算机系统的瓶颈。为提高磁盘的I/OI/O速度，便采速度，便采用磁盘高速缓存。用磁盘高速缓存。n磁盘高速缓存的形式磁盘高速缓存的形式 n数据交付方式数据交付方式n置换算法置换算法n周期性地写回磁盘周期性地写回磁盘(1)磁盘高速缓存的形式v 磁盘高速缓存磁盘高速缓存 是指内存中的一部分存储空间，用来暂存从磁盘读出的一是指内存中的一部分存储空间，用来暂存从磁盘读出的一系列盘块中的信息。所以它是一组在逻辑上属于磁盘，而物理系列盘块中的信息。所以它是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。上是驻留在内存中的盘块。v磁盘高速缓存的形式磁盘高速缓存的形式n内存中单独的存储空间（大小固定）内存中单独的存储空间（大小固定）n未利用的存储空间未利用的存储空间_缓冲池（大小不固定）缓冲池（大小不固定）(2)(2)数据交付方式数据交付方式v 数据交付方式 是指磁盘高速缓存中的数据传送给请求者进程。系统采取两是指磁盘高速缓存中的数据传送给请求者进程。系统采取两种方式，将数据交付给请求进程：种方式，将数据交付给请求进程：n数据交付 系统直接将磁盘高速缓存中的数据传送系统直接将磁盘高速缓存中的数据传送到请求者进程的内存工作区。到请求者进程的内存工作区。n指针交付 只将指向磁盘高速缓存中该数据的指针，只将指向磁盘高速缓存中该数据的指针，交付给请求者进程。交付给请求者进程。(3)(3)置换算法置换算法 在将磁盘中的盘块读入到磁盘高速缓存中时，若因磁盘高速缓存已满，则在将磁盘中的盘块读入到磁盘高速缓存中时，若因磁盘高速缓存已满，则采用常用的算法进行置换：采用常用的算法进行置换：n最近最久未使用算法LRU n最近未使用算法NRUn最少使用算法LFUn置换时除算法外还应考虑的问题n访问频率访问频率n可预见性可预见性n数据的一致性数据的一致性 _解决方法将系统中所有盘块数据，拉成一解决方法将系统中所有盘块数据，拉成一条条LRU链，对将会严重影响到数据一致性的数据和很久都可链，对将会严重影响到数据一致性的数据和很久都可能不再使用的盘块数据，能不再使用的盘块数据，放在放在LRU头部，到时优先写回磁盘。头部，到时优先写回磁盘。(4)(4)周期性地写回磁盘周期性地写回磁盘 系统中所有盘块数据，拉成一条系统中所有盘块数据，拉成一条LRU链，对将会严重影响到数据链，对将会严重影响到数据一致性的数据和很久都可能不再使用的盘块数据，一致性的数据和很久都可能不再使用的盘块数据，放在放在LRU头部，头部，到时才优先写回磁盘。若经常访问的数据将一直保留磁盘高速缓存到时才优先写回磁盘。若经常访问的数据将一直保留磁盘高速缓存中，长期不会被写回磁盘，若系统出故障，则存在磁盘高速缓存中中，长期不会被写回磁盘，若系统出故障，则存在磁盘高速缓存中的数据将丢失。的数据将丢失。v问题解决n周期性地将磁盘高速缓存中的数据写回磁盘。周期性地将磁盘高速缓存中的数据写回磁盘。n磁盘高速缓存中的数据若修改，则立即写回磁盘。磁盘高速缓存中的数据若修改，则立即写回磁盘。4 4、提高磁盘、提高磁盘I/OI/O速度的其它方法速度的其它方法 v提前读（Read_Ahead）由于用户对文件的访问常用顺序方式，在读当前块时，可预知下一次要由于用户对文件的访问常用顺序方式，在读当前块时，可预知下一次要读的盘块，所以，可采用预先读方式，即在读当前块的同时，连同将下一块读的盘块，所以，可采用预先读方式，即在读当前块的同时，连同将下一块提前读入缓冲。当访问下一块数据时，其已在缓冲中，而不需去启动磁盘提前读入缓冲。当访问下一块数据时，其已在缓冲中，而不需去启动磁盘I/OI/O。v延迟写 在缓存中的数据在缓存中的数据,本应立即写回磁盘本应立即写回磁盘,考虑不久之后可能会再用考虑不久之后可能会再用,故不立即故不立即写回磁盘。写回磁盘。v优化物理块的分布 使磁头移动的距离最小（优化物理块的分布、优化使磁头移动的距离最小（优化物理块的分布、优化索引结点的分布）。索引结点的分布）。v虚拟盘 利用内存去访真磁盘，又称为利用内存去访真磁盘，又称为RAMRAM盘。（与磁盘高速缓存的区别：盘。（与磁盘高速缓存的区别：RAMRAM盘中盘中的内容由用户控制，而缓存中的内容则由的内容由用户控制，而缓存中的内容则由OSOS控制）控制）5 5、谦价磁盘冗余阵列（、谦价磁盘冗余阵列（RAIDRAID）是是19871987年由美国加利福尼来大学伯莱分校提出的，年由美国加利福尼来大学伯莱分校提出的，19881988年问世，即利用一台磁盘陈列控制器，来统一管理和控制年问世，即利用一台磁盘陈列控制器，来统一管理和控制一组磁盘驱动器一组磁盘驱动器，组成一个高度可靠的、快速的大容量磁，组成一个高度可靠的、快速的大容量磁盘系统。盘系统。n并行交叉存取并行交叉存取 nRAIDRAID的分级的分级nRAIDRAID的优点的优点（1 1）并行交叉存取并行交叉存取 为提高磁盘的访问速度而在大、中型机中采用的交叉存取技为提高磁盘的访问速度而在大、中型机中采用的交叉存取技术，即在一个配置多台磁盘驱动器的系统中，如术，即在一个配置多台磁盘驱动器的系统中，如P179P179页图页图5-275-27所示。系统将每一盘块的数据分成若干个子盘块数据，再把每所示。系统将每一盘块的数据分成若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上，一个子盘块的数据分别存储到各个不同磁盘中的相同位置上，在以后，当要将一个盘块的数据传送到内存时，采取并行传输在以后，当要将一个盘块的数据传送到内存时，采取并行传输方式，将该盘块中的各个子盘块数据同时向内存传输，从而使方式，将该盘块中的各个子盘块数据同时向内存传输，从而使传输时间大大减少。传输时间大大减少。（2 2）谦价磁盘冗余阵列（）谦价磁盘冗余阵列（RAID RAID）的分）的分级级 vRAID 0级 本级仅提供了并行存取技术，无冗余校验功能，至使磁盘系统的可靠性本级仅提供了并行存取技术，无冗余校验功能，至使磁盘系统的可靠性不好，故较少使用。不好，故较少使用。vRAID 1级 本级具有磁盘锁像功能，即每次访问磁盘时，采用并行技术将数据同时本级具有磁盘锁像功能，即每次访问磁盘时，采用并行技术将数据同时主盘（数据盘）和磁盘镜像盘中。磁盘系统的可靠性好，但磁盘利用率不高。主盘（数据盘）和磁盘镜像盘中。磁盘系统的可靠性好，但磁盘利用率不高。vRAID 3级 本级采用并行存取技术，增加了冗余校验功能，即用一个盘作校验盘，本级采用并行存取技术，增加了冗余校验功能，即用一个盘作校验盘，常用科学计算和图像处理。常用科学计算和图像处理。vRAID 5级 本级具有独立传送功能，各磁盘驱动器可独立读、写，校验信息在所有本级具有独立传送功能，各磁盘驱动器可独立读、写，校验信息在所有盘上，常用于盘上，常用于I/OI/O较频繁的事务处理中。较频繁的事务处理中。vRAID 6级 本级设置了一个专用的、可快速访问的异步校验盘，该盘具有独立的数本级设置了一个专用的、可快速访问的异步校验盘，该盘具有独立的数据访问通路。据访问通路。vRAID 7级 本级是对本级是对RAID 6RAID 6级的改进，所有磁盘均具有较高的传输速率和优异的性能，级的改进，所有磁盘均具有较高的传输速率和优异的性能，是目前最高档次的磁盘阵列是目前最高档次的磁盘阵列 。（3 3）谦价磁盘冗余阵列（）谦价磁盘冗余阵列（RAID RAID）的优）的优点点 v可靠性高 是是RAID RAID 的最大优点（除的最大优点（除RAID 0 RAID 0 级外）级外）v磁盘I/O速度高 由于由于RAID RAID 可采用并行交叉存取方式，故提高了磁盘可采用并行交叉存取方式，故提高了磁盘I/OI/O速度。速度。v性能/价格比高 用用RAIDRAID技术实现大容量存储器时，与大型磁盘系统相比，其技术实现大容量存储器时，与大型磁盘系统相比，其体积和价格只是它的体积和价格只是它的1/31/3，且可靠性高。，且可靠性高。5.7 UNIX5.7 UNIX系统中的设备管理系统中的设备管理Unix系统中，设备管理被作为一种特殊的文件，由文件系统统一进行。v设备缓冲管理n字符设备缓冲管理n块设备缓冲管理v设备处理程序n核心与驱动程序的接口n磁盘驱动程序、磁盘读（写）程序字符设备缓冲管理字符设备缓冲管理v空闲缓冲区链v字符缓冲区的分配与回收nGetcf从空闲缓冲区链首取一缓冲区，收容设备的I/O数据nPutcf将空闲缓冲区归还到空闲缓冲区链中（首）。字符设备空闲缓冲区队列字符设备空闲缓冲区队列C-nextC-nextC-nextC-nextCblock0Cblock1Cblock2Cblockn-1cfreelist第一个字符的位置最后一个字符的位置指向下个缓冲区的指针余下64个字符Cblocki块设备缓冲管理块设备缓冲管理v块设备缓冲队列的结构n盘块缓冲区的组成n盘块缓冲池的构成v块设备缓冲区的分配与回收n块缓冲区的分配nGetblk()过程nGetblk(dev,blkno)过程n块缓冲区的回收-brelse过程n唤醒等待空闲缓冲区的所有进程n将空闲块缓冲区放入空闲队列n在缓冲区首置空闲标志，空闲块缓冲区数加1盘块缓冲区的组成盘块缓冲区的组成v缓冲区：存放数据本身v缓冲控制块（缓冲首部）：存放缓冲区的管理信息设备号块号状号缓冲区指针散列队列的前向指针散列队列的后向指针空闲表上的前向指针空闲表上的后向指针盘块缓冲池的构成盘块缓冲池的构成v空闲链表（双向，getblk过程，brelse过程）v散列队列按其块号计算的散列值不同而多个散列队列，如P425图14-3；任一缓冲区在某个散列队列中；而空闲缓冲区在空闲链中。v对空缓冲区的查找方法n要求获任一缓冲区-空闲链n要求获一特定缓冲区-散列队列核心与驱动程序的接口核心与驱动程序的接口图图10-1510-15v设备开关表n块设备开关表n字符设备开关表块设备开关表表项openclosestrategy0GdopenGdcloseGdstrategy1gtopenGtcloseGtstrategy核心与驱动程序的接口核心与驱动程序的接口图图10-1510-15v设备开关表n块设备开关表n字符设备开关表字符设备开关表表项openclosereadwriteioctl0conopenconcloseconreadconwriteconioctl1dzbopendzbclosedzbreaddzbwritedzbioctl磁盘驱动程序、磁盘读写程序磁盘驱动程序、磁盘读写程序v磁盘驱动程序nGdopen-打开指定磁盘驱动器nGdstrat-取一缓冲区，并启动磁盘控制器nGdstrategy-把指定的缓冲排在队尾，并启动磁盘控制器。nGdintr-响应中断进行磁盘中断处理。v磁盘读写程序n读方式n一般读方式breadn提前读方式breadan写方式n一般写方式bwriten异步写方式bawriten延迟写方式bdwrite本章作业本章作业1、为什么要设置内存I/O缓冲区？，通常有哪几类缓冲区？2、如何将独占型输入设备改造成可共享使用的虚拟设备？3、在设备管理中，何谓设备独立性？如何实现设备独立性？4、为什么要引入SPOOLING技术？SPOOLING技术可带来哪些好处？5、设某磁盘有200个柱面，编号为0，1，2，199，磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进行读写：86，147，91，177，94，150，102，175，130 试分别求FCFS、SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。