操作系统第五章设备管理 2012

1、第五章,设备管理,设备管理,外部设备 中央处理器(CPU)和主存储器(MM)构成计算机的主体，称为主机。 主机以外的大部分硬设备都称为外部设备或外围设备，简称外设。 它包括常用的输入输出设备，外存储器，脱机输入输出设备等。 在第四代计算机出现以后，特别是进入80年代以来，以个人计算机和工作站为代表的微型机迅速普及，计算机的应用领域有了突破性的进展，外部设备开始向多样化、智能化的方向发展。,输入设备： 键盘 图形输入设备(鼠标器、图形板、跟踪球、操纵杆、光笔) 图像输入设备(摄像机、扫描仪、数字相机) 条形码 光学字符识别 语言与文字输入,输出设备： 显示器(字符、汉字、图形、图像) 打印设备(

2、针式打印机、激光打印机、喷墨打印机、 热转印打印机) 绘图机(平板式、滚筒式) 语音输出 终端设备(键盘+显示器),5.1 I/O 系统的组成（二）,2。按传消息交换的单位分类 块设备 信息存取以数据块为单位，属于有结构设备。 字符设备 信息存取以字符为单位，属于无结构设备。,3。按设备的共享属性分类 独占设备 在一段时间只允许一个进程访问的设备。 共享设备 在一段时间允许多个进程同时访问的设备。 虚拟设备 使用虚拟技术，将一台独占设备变为逻辑上的多台 设备。,二、I/O设备及分类,1。按传输速率分类 低速设备 中速设备 高速设备,设 备 管 理 （一）,设备管理是操作系统最基本、最繁杂的组成

3、部分。且与硬件的关系最密切。,外设按功能分为两类 ,存储设备 存取控制部分（控制电路伺服系统、读写控制电路、磁头、光头等） 信息载体 （磁盘、磁带、光盘等）,I/O设备 存储设备,I/O设备 输入设备 模拟信号 数字信号（A/D转换） 输出设备 数字信号 模拟信号（D/A转换）,设 备 管 理 （二）,设备管理的基本任务是： （1） 控制 I/O 操作；进行设备分配；提高CPU与设备之间的并行工作程度。协调和保证设备的正常与高效工作。 （2） 向用户提供一个使用设备的方便接口。完成用户的I/O请求。,I/O 系统的组成 I/O 控制方式 I/O 数据传输与缓冲技术 虚拟设备与Spooling技

4、术,主要讨论以下问题,I/O 系统的组成 I/O 数据传输控制方式 I/O 缓冲技术 I/O 软件与设备分配 虚拟设备与Spooling技术,5.1 I/O 系统的组成（一）,1。微机I/O系统 CPU通过总线与设备控制器相连接，设备 控制器是CPU 与设备之间的接口。 2。主机I/O系统 使用I/O通道（I/O处理机），实现对设备 控制器的控制。,I/O系统应该由以下部分组成： I/O设备 设备控制器 总线或通道,一、I/O 系统的结构,图 5-1 设备与控制器间的接口,图 5-6 总线型I/O系统结构,5.1 I/O 系统的组成（三）,1。设备控制器的功能 接收和识别CPU发出的命令，因此

5、，设备控制器中设有多个寄存器，用来存放命令和参数，同时，还设有命令译码器。 实现数据交换，即CPU与控制器之间，控制器与设备之间的数据交换。 记录设备的状态，以便CPU启动控制器。为此，在控制器中设置一个状态寄存器。 识别设备地址。使CPU能够从设备控制器的寄存器中读写数据。,三、设备控制器,设备控制器是CPU与设备之间的接口，接收CPU的命令，控制设备工作,实现设备与计算机之间数据交换。,5.1 I/O 系统的组成（四）,2。设备控制器的组成,由CPU与控制器接口、控制器与设备接口、 I/O逻辑三部分组成。三类信号线：数据线、地址线、控制线。,5.1 I/O 系统的组成（五）,通道（Chan

6、nel） 也称 I/O处理机。 是为了减轻CPU的工作负载，在 CPU 与设备控制器之间而设置的一种专门用于 I/O 的简单处理机。 通道指令系统 也称通道控制字（CCW），是通道能够独立执行的I/O指令。,按照信息交换方式分类： 字节多路通道 用于低、中速设备 含多个非分配型的子通道，子通道按时间片轮转共享主通道。按字节传送。传输速度慢(P149 图5-3）。 数组选择通道 连接中、高速设备 含一个分配型的子通道，一段时间内只能执行、控制一台设备工作。通道利用率低，传输速度快。 数组多路通道 连接中、高速设备 综合前两类的优点。,四、I/O通道,1、为什么引入通道,2、通道的类型,5.1 I

7、/O 系统的组成（六）,中央处理机,内存,字节多路通道,成组多路通道,选择通道,卡片 输入机,卡片 输入机,打印机,磁盘,磁带,通 道 结 构,5.1 I/O 系统的组成（七）,图5-6 解决“瓶颈问题”的多通路系统,3、“瓶颈问题”,由于通道及设备控制器的数量有限，可能造成I/O的瓶颈。,5.2 I/O 控制方式 （一）,（1）中断控制方式 （2）DMA 控制方式 （3）通道控制方式,设备管理的主要任务之一是控制设备与内存或CPU 之间的数据传送，选择控制方式的原则是： 保证在足够的传输速度下数据的正确传送。 系统开销小。 充分发挥硬件资源的能力。,本节讨论CPU 通过设备控制器来控制数据I

8、/O的方式。,常用的I/O控制方式,5.2 I/O 控制方式（二）,一、中断控制方式,中断 当主机接到外部信号时（如 I/O完成信号）即停止 原来的工作，转去处理这一事件，处理完后，主机 又回到原来的断点继续工作。,中断处理过程：,（向CPU）,中断源,中断请求,中断响应,转中断 处理程序,退出中断,保护CPU现场 识别中断源,恢复CPU现场,5.2 I/O 控制方式（三）,也称中断驱动（Interrupt - Driver）I/O方式。 1、中断控制过程 进程提出I/O请求， CPU向设备控制器发出I/O指令后，返回继续执行。 设备控制器按指令执行（与CPU并行工作）。 一次I/O操作（1字

9、节）完成，向CPU发中断信号，CPU作中断处理。 P152图57 （b）给出输入字符的中断控制过程。,一、中断控制方式,是以字节为单位进行I/O的，只适宜字符设备。效率虽然比程序I/O方式高，但不适宜块设备。,2、特点,中断处理过程（CPU、设备）,中断处理过程,5.2 I/O 控制方式（四）,由于大多数的小型、微型计算机采用总线结构，DMA方式是“窃取”或“挪用” CPU总线的控制权，即要求CPU暂停若干总线周期，由DMA控制器占有存储器周期进行设备与内存之间的数据交换。,直接存储器访问 DMA（Direct Memory Access） 方式的引入是为解决中断控制方式对块设备低效的问 题。

10、减少中断次数。,二、DMA控制方式,1、DMA方式的基本思想,（1）以数据块为单位进行数据传送。 （2）设备与内存之间直接交换数据。,5.2 I/O 控制方式（五）,DR 数据寄存器，暂时存放设备内存间传送的信息。 MAR 内存地址寄存器。 DC 传送字（节）数寄存器。 CR 命令/状态寄存器。接收从CPU发来的 I/O命令、控制信息、 设备状态。,主机-控制器接口 控制器-块设备接口,2、DMA控制器的组成,DR,MAR,DC,CR,I/O 控 制 逻 辑,CPU,内存,命令,系统总线,DMA控制器,。 。 。,count,磁 盘,源地址,数据,DMA控制器的工作原理,当CPU欲把一块数据从

11、某I/O设备读入内存某处或把一块数据从内存某处写入某I/O设备时，CPU将把相关数据块的长度通过DMA的“Data Lines”脚写入DMA的“Data Count”寄存器中，把内存起始地址和I/O设备地址通过DMA的“Data Lines”脚写入DMA的“Address Register”寄存器中，同时通过DMA的 “Read” 脚或“Write”脚向DMA发出读或写命令。 在工作期间，DMA将通过“DMA Request”脚 和 “DMA Acknowledge”脚控制相关的I/O设备，通过“Data Lines”脚与I/O设备以及内存交换数据，并通过“Address Lines”脚寻址内

12、存。,5.2 I/O 控制方式（六）,以CPU从磁盘读入数据为例： 预置DMA的寄存器 CPU命令 CR 内存地址 MAR 要读数据字数 DC 磁盘地址 I/O控制逻辑 启动DMA，CPU返回工作 设置CR中允许中断位和启动位为1，启动DMA工作。,3、DMA工作过程,传送数据块 挪用存储器周期，传送一个数据字（节）后，MAR加1，DC减1。 I/O 中断处理 重复执行 ，直至DC=0。 磁盘控制器向CPU发中断请求。,5.2 I/O 控制方式（七）,P154 图5-9 DMA 方式的工作流程,3、DMA工作过程,设置CR和DC初值,启动DMA传送命令,挪用存储器周期 传送数据字（节）,存储器

13、地址增1 DC减1,DC=0,N,继续执行进程 准备传送下一数据字,Y,请求中断,CPU命令 CR 内存始址 MAR 要读数据字数 DC 磁盘地址 I/O控制逻辑,DMA控制方式（CPU、设备）,5.2 I/O 控制方式（八）,CCW的信息： 操作码 内存地址 传送数据字节数 通道程序结束位P（P =1 结束） 记录结束标志R ,通道（Channel） 是比DMA方式更加完善，功能更强的I/O 控制方式。 DMA与通道方式的异同： 相同：以内存为中心，实现设备与内存之间直接交换数据 的控制方式。 不同：通道是专门控制 I/O的处理机。其指令称为通道控 制字（CCW），由CCW编制的通道程序，独

14、立执 行I/O任务。,三、通道控制方式,1、I/O处理机,0 指令处理同一记录 1 处理记录结束,5.2 I/O 控制方式（九）,DMA方式与通道控制方式的数据传送过程有何相同和不同之处？ 画出DMA及通道控制方式的控制流程图（分别画出输入、输出两种情况）。,2、通道的控制过程： CPU启动通道 通道程序的始址存放在称为通道地址字（CAW）的内存单元中，由 CPU启动通道程序后，CPU可去执行其他任务。 执行通道指令CCW ，向设备控制器发出I/O操作命令。 设备根据CCW将数据传送到内存指定单元。 数据传送结束，I/O控制器向CPU 发出中断请求命令。,思 考 题,5.3 缓冲管理（一）,1

15、、单缓冲区（single buffer） 在设备和主机之间设置一个缓冲区。只能缓解速度匹配的问题。不能实现设备之间的并行操作。,1、缓解CPU与外设速度不匹配的问题。 2、减少CPU中断响应次数，放宽响应时间。 3、提高CPU与I/O设备，I/O设备之间的并行操作能力。 缓冲技术的基本思想： 在内存中开辟一个或多个专用区域（缓冲区），作为CPU 与I/O设备间信息的集散地。,一、为什么引入缓冲技术,二、缓冲区的组织,缓冲区,用户进程,传送,操作系统,输入,I/O设备,5.3 缓冲管理（二）,一般是建立两个大小相等的缓冲区，设备交替对两个缓冲区输入数据，操作系统也交替地从两个缓冲区移出数据送用户

16、进程区。,二、双缓冲区（double buffer）,5.3 缓冲管理（三）,三、循环缓冲（circular buffer） 循环缓冲即是多个大小相同的缓冲区构成循环队列，有三种缓冲区：空缓冲区(R)，满缓冲区(G)，正使用的缓冲区(C)。,例如：生产者消费者问题,生产者进程 Pi（P1，P2，Pk）; 消费者进程 Ci（C1，C2，Cm）。 in 指向下一空缓冲区的指针。 Out 指向下一满缓冲区的指针。 current 指向当前工作缓冲区的指针。,（循环缓冲的工作过程自学 P158-P159）,5.3 缓冲管理（三）,1、缓冲池的结构 缓冲池由多个缓冲区构成。每个缓冲区又分为缓冲区首部和缓

17、冲体。,四、缓冲池（buffer pool）,设备号 缓冲区号 缓冲区地址 缓冲区状态（忙/闲） 数据块号 互斥标识位 设备缓冲队列指针,缓冲区首部,将缓冲区连接成三种队列： 空缓冲区队列（emq） 满输入缓冲区队列（inq） 满输出缓冲区队列（outq）,有四类工作缓冲区： sin 提取输入的工作缓冲区 hin 收容输入数据的缓冲区 sout 提取输出的工作缓冲区 hout 收容输出数据的缓冲区,5.3 缓冲管理（四）,2、缓冲池管理方式,输 入 输 出 设 备,数 据 处 理 程 序,hin,sout,sin,hout,inq,emq,outq,putbuf（inq，hin）,putbuf

18、（emq，sout）,getbuf（inq）,getbuf（emq）,putbuf（emq，sin）,getbuf（outq）,getbuf（emq）,putbuf（outq，hout）,提取 输入,提取 输出,收容 输入,收容 输出,典型的缓冲池管理,收容 输入,getbuf（emq）,hin,putbuf（inq，hin）,提取 输入,getbuf（inq）,sin,putbuf（emq，sin）,5.3 缓冲管理（七）,（2）提取输入 当需要处理输入数据时，计算进程调用getbuf（ inq），从满输入缓冲区队列（inq）的队首取出一缓冲区提取输入的工作缓冲区（sin）。 计算进程从si

19、n提取数据处理。 调用过程putbuf（emq，sin），释放工作缓冲区sin，并插入空缓冲队列尾。,（1）收容输入 输入进程调用过程getbuf（emq），从空缓冲队列中 申请一空缓冲区收容输入数据的缓冲区（hin）。 从设备输入数据到 hin。 调用过程putbuf（inq，hin），将满缓冲区hin插入满 输入缓冲区队列（inq）的队尾。,缓冲池管理过程（以输入为例）,缓冲输出过程（收容输出、提取输出）与输入类似。,5.3 缓冲管理（五）,3、缓冲队列操作过程 两个基本的过程 过程 Addbuf（type，number） 将由number指示的缓冲区，挂在type队列上。 过程 take

20、buf（type） 从type所指定队列中取出一缓冲区。 注意：这两个过程需修改后，才能运用于多进程环境。, getbuf（type） 从缓冲队列获取一个缓冲区。 putbuf（type，n） 将 n 所指示的缓冲区，插入type队列。,5.3 缓冲管理（六）,Procedure putbuf（type，n）； begin P（S（type）； Addbuf（type，n）； V（S（type）； V（RS（type）； end；,Procedure Getbuf（type）； begin P（RS（type）； P（S（type）； B（n）：=Takebuf（type）； V（S（type

21、）； end；,过程 Getbuf,过程 Putbuf,其中： RS（type） 资源信号量，type 队列中缓冲区数。初值为n。 S（type） 互斥信号量，对type队列互斥使用。初值为1。,5.4 I/O软件,确保I/O 设备与CPU的并发性，以提高资源的利用率。,2. 通用性 尽可能提供简单清晰，抽象统一的接口，来管理所有 的设备以及所需的I/O操作,1、高效率,I/O软件的总体设计目标是高效率和通用性。,5.4 I/O软件, 通常采用层次结构 1.用户层软件 2.设备独立性软件 3.设备驱动程序 4. 中断处理程序 5. 硬件 低层软件实现与硬件相关的操作，并可屏蔽硬件的具体细节，高

22、层软件则主要向用户提供一个简洁，友好和规范的接口。 每一层具有一个要执行的定义明确的功能和一个与邻近层次定义明确的接口。,I/O软件结构,5.4 设备分配（五）, 为了实现设备独立性，进程使用逻辑设备名。即系统为 每个进程建立一张逻辑设备表LUT（Logical Unit table）。, 有利于改善资源的利用率。提供了设备分配的灵活性。 为用户程序提供了与设备无关的接口，为I/O重定位提供方便，因此，提高了用户程序的可适应性。,设备独立性, LUT 包括：逻辑设备名、物理设备名、驱动程序地址。 通过LUT 实现用户程序中逻辑设备名到物理设备名的映射。,1、逻辑设备表,设备独立性（device

23、 independence）是I/O软件的一个关键性概念，是指用户程序独立于使用的物理设备。,2、使用逻辑设备名的优点,逻辑设备名到物理设备名映射的实现,逻辑设备表,5.5 设备处理（二）,二。I/O设备驱动程序,设备驱动程序是是请求I/O的进程与设备控制器之间的一个通信和转换程序。它将进程的I/O 请求经过转换后，传给控制器，又把控制器中所记录的设备状态和I/O操作完成情况及时反映给请求I/O的进程。一般为每类（个）设备设置一个驱动程序。,驱动程序,启动过程 启动一个I/O操作。 继续过程 处理中断和完成数据传送。,驱动程序执行步骤：,1、服务请求校验 确定请求的操作，检验硬件支持。 2、确

24、认设备状态 确定设备（状态寄存器）是否可用。 3、启动I/O请求 若确认设备状态可用，启动I/O。 4、中断处理 CPU处理I/O过程的中断。驱动程序应保存处 理器的当前状态，以便进程重新执行。 5、I/O请求完成 驱动程序识别I/O完成，将控制返回IOCS， 将被中断的进程置为就绪。,设备驱动程序的功能,(1) 接收由I/O进程发来的命令和参数， 并将命令中的抽象要求转换为具体要求， 例如，将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。 (2) 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。 (3) 发出I/O命令，如果设备空闲，便立即启动I/O设备去完

25、成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。,(4) 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。 (5) 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。,设备驱动程序的处理过程,将抽象要求转换为具体要求 2. 检查I/O请求的合法性 3. 读出和检查设备的状态 4. 传送必要的参数 5. 工作方式的设置 6. 启动I/O设备,图 5-20 中断现场保护示意图,中断处理流程,5.5 设备处理（一）,I/O请求的处理过程，由输入/输出控制系统IOCS完成，其中最主要的部分是设备驱

26、动程序。它是I/O请求进程与设备控制器之间的通信程序。,1、用户进程向IOCS发出I/O请求。 2、IOCS查逻辑设备表（LUT），将逻辑请求转换为物 理请求。 3、IOCS调用驱动程序的“启动过程”启动I/O设备。 4、IOCS将有关信息放入中断表中。 5、将用户进程挂起，放入I/O等待队列。 6、执行驱动程序的“继续过程”（中断处理、传送 I/O 数据）。 7、完成I/O操作，重新启动用户进程。,一、I/O请求处理过程,5.4 设备分配（一）,2、控制器控制表COCT（Controler Control Table） 记录I/O控制器使用情况及与通道连接情况。（DMA无）,设备分配是设备管

27、理的重要问题。讨论设备分配的数据结构，分配原则及分配算法。 一、设备分配的数据结构,1、设备控制表DCT（Device Control Table） 反映设备特性，设备与I/O控制器连接情况。,5.4 设备分配（二）,4、系统设备表SDT（System Device Table） 整个系统一张，记录已连接到系统中的设备情况，每个设备在SDT中占一表项。,3、通道控制表CHCT（Channel Control Table） 描述通道的使用情况。,针,5.4 设备分配（三）,设备分配的数据结构,针,SDT,DCT,COCT,CHCT,5.4 设备分配（四）,设备分配的方式： 静态分配 一次分配所有

28、需要的设备。不符合分配 原则。 动态分配 进程执行过程中，按需分配。,设备分配总原则：充分发挥设备利用率，避免由于不合理分配引起进程死锁。 具体考虑以下方面： 1、设备的固有属性 （独占、共享、虚拟）。 2、设备分配算法（先来先服务、优先级）。 3、设备分配的安全性（安全或不安全分配方式，指是否保持“请求与保持”条件）。 4、设备独立性。,二、设备分配的原则及方式,5.4 设备分配（六）,三、设备分配流程,进程P发出I/O请求,搜索SDT找到DCT指针,查DCT 设备忙？,进程P按分配算法 入I/O队列,Y,N,按分配算法选择进程,进程P选中？,进程P等待 设备空闲,N,Y,检查设备分配的安全

29、性,安全吗？,N,Y,设备分配给进程P,1,1,搜索DCT找到COCT指针,控制器忙？,Y,进程P等待 控制器,N,分配控制器给进程P,搜索COCT找到CHCT指针,CHCT忙,Y,进程P等 待通道,N,分配通道给进程 P,启动 I/O,5.4 设备分配（七）,多道程序系统中，进程对设备的需求频繁，尤其是独占设备数量有限、效率低，故引入虚拟设备管理技术。 基本思想：用大容量的快速设备（磁盘）模拟慢速度的 独占设备，把一台物理上的独占设备变为逻辑上的多台共享设备。,SPOOLing是一种典型的虚拟设备技术， SPOOLing 是 Simultaneous Peripheral Operation

30、s On Line （外围设 备同时联机操作）的缩写，是用程序模拟脱机I/O的功能，故又称为假脱机技术。,四、虚拟设备与SPOOLing技术,2、SPOOLing 技术,1、虚拟设备管理,早期脱机批处理模型,5.4 设备分配（八）,SPOOLing 系统的组成: 输入井、输出井 输入进程、输出进程 I/O缓冲区,输入设备,输入设备,通 道,5.4 设备分配（九）,以打印机为例，说明SPOOLing 系统的工作过程： 当进程请求打印输出时，OS并不是把设备分配给它。 1、输出进程为其申请输出井中的一块空闲区（虚拟打印机）， 并送入输出数据。 2、输出井中形成各进程的打印队列（printer qu

31、eue）。 3、由SPOOLing 系统的缓冲输出程序依次输出到打印机。,打印机 独占设备 虚拟打印机 共享设备,5.6 磁盘存储器管理（一）,一、磁盘的工作过程,大容量磁盘(固定头磁盘） - 磁盘的每条磁道上都有一个读/写磁头，并行读/写。 中小型磁盘设备（活动头磁盘） - 每个盘面配置一个磁头，串行读/写。 - 为了读/写某磁道、某扇区的数据，首先让磁头移动，寻找指定磁道，再旋转磁盘将相应扇区定位到磁头下面。,磁盘驱动器发出寻道命令后便释放相关的通道控制器， 以便系统用它来处理其它I/O操作。当磁臂(磁头)被移动到指定的磁道时，磁盘驱动器便开始驱动磁盘旋转，以便把指定扇区的起始位置定位到磁

32、臂(磁头)下。一旦指定扇区的起始位置被定位到磁臂(磁头)下，磁盘驱动器便重新申请通道控制器，以便建立到主机的通路。如果请求失败，磁盘驱动器将驱动磁盘旋转一周后再次申请通道控制器。,5.6 磁盘存储器管理（二）,主要对移动头磁盘进行讨论： 二、访盘时间 1、寻道时间Ts 将磁头移动到指定磁道上的时间。,其中： M 常数（一般0.5，高速小于0.1） S 磁盘启动时间 n 磁头移动磁道数,2、旋转延迟时间Tr 把指定扇区的起始位置置于磁头下所花费的时间。与磁盘转速有关。 Tr 1/(2r) 3、传输时间Tt 读/写数据的时间。,Tt = b/ rN 其中：r 磁盘旋转速度；N 一条磁道上的字节数；

33、 b 读/写的总字节数。,Ts = m n + S,5.6 磁盘存储器管理（三）,主要讨论移动头磁盘的调度算法： 磁盘驱动程序一般要考虑磁盘的调度策略，在三类访问时间中，寻道所占时间最长。所以大多数磁盘驱动程序都是以寻道优化为出发点的，主要讨论寻道算法。,问 题 三类访问时间中，哪类时间最长？,5.6 磁盘存储器管理（四）,主要讨论移动头磁盘的调度算法： 二、磁盘的访问时间（P194） 1、寻道时间Ts (Seek Time) Ts = m n + S 2、旋转延时Tr (Rotational Delay) 与磁盘的转速有关。 3、数据传输时间Tt (Transfer Time) 磁盘驱动程序

34、一般要考虑磁盘的调度策略，在三类访问时间中，寻道所占时间最长。所以大多数磁盘驱动程序都是以寻道优化为出发点的，主要讨论寻道算法。,播 放,5.6 磁盘的调度与驱动（二）,三、常用的调度算法 1、先来先服务（FCFS） 按照申请服务的先后次序。未考虑寻道优化。 2、最短寻道优先算法（SSTF） 优先选择离磁头最近的请求。未考虑磁头来回摆动。可能出现老进程的“饥饿”现象。 3、扫描算法（SCAN） 既考虑请求与磁头的距离，又考虑磁头移动的方向；又称为：电梯法。 4、循环扫描算法（C-SCAN） 规定磁头单向移动，即将最小磁道号与最大磁道号构成循环，进行循环扫描。,5.6 磁盘存储器管理（四）,N-

35、Step- SCAN算法，F- SCAN算法请自学。,1. 先来先服务FCFS(First-Come, First Served),2. 最短寻道时间优先SSTF(Shortest Seek Time First),2) SCAN算法调度算法示例,4. 循环扫描(CSCAN)算法,5.7 提高磁盘I/O速度的技术,一、磁盘高速缓存（Disk Cache) 把磁盘I/O缓冲区叫做磁盘高速缓存（Disk Cache），但它并不是一种硬件设施。事实上，磁盘I/O缓冲区仍然是内存中的一个区域。其组织形式基于程序引用的局部性原理。,其工作原理类似Cache Memory) 以输入为例：当用户进程请求从磁

36、盘上读入一个扇区时， 系统首先在磁盘I/O缓冲区中寻找该扇区的副本：如果能够找到，那么系统将从磁盘I/O缓冲区中取出该扇区的副本并返给用户进程；否则，系统首先从磁盘上读入该扇区并在磁盘I/O缓冲区中为其建立一个副本，然后将该副本返给用户进程。,其置换算法类似请求调页存储管理中的页面置换算法（LRU、NRU、LFU等）。,5.7 提高磁盘I/O速度的技术,最近最少使用置换算法（LRU置换算法） 置换在最近一段时间内最久没有被访问过的扇区。 最小访问频度置换算法（LFU置换算法） 置换被引用次数最少的扇区。,其置换算法类似请求调页存储管理中的页面置换算法，如：,二、提前读（Read Ahead)与延后写（Write Postponing） 用户进程从 I/O缓冲区中取走前一个数据后立即发出对下一个数据的输入请求；即用户进程加工前一个数据的工作与OS输入下一个数据的工作可以同时进行。通常把这种I/O缓