chapter6_输入输出系统.ppt

扫描算法（SCAN） Scan算法往复扫描各个柱面（磁道）并为途经柱面（磁道）的请求服务。 起始时磁头处于最外柱面，并向内柱面移动。在移动的过程中，如果途经的柱面有访问请求，则为其服务，如此一直移动到最内柱面，然后改变方向由内柱面向外柱面移动，并以相同的方式为途经的请求服务。 Scan算法每次都扫描到柱面的尽头，无论最内（最外）柱面处是否有访问请求。 扫描算法（SCAN） 假定：磁头向磁道号增加的方向移动。 下磁道 移道数 65 12 67 2 98 31 122 24 124 2 183 59 199 16 37 162 14 23 总道数 331 平均 41.4 Look算法（电梯算法） Look算法也称电梯算法，因其基本思想与电梯的工作原理相似而得名。 无访问请求时，磁头引臂停止不动；当有访问请求时，起始时磁头由最外柱面向内柱面移动，并为途经的请求服务。一旦内柱面没有访问请求，则改变移动方向（如外柱面有请求）或停止移动（外柱面也无请求）。 假定：磁头向磁道号增加的方向移动。 下磁道 移道数 65 12 67 2 98 31 122 24 124 2 183 59 37 146 14 23 总道数 299 平均 37.4 Look算法（电梯算法） SCAN / LOOK算法评价 对于SCAN(LOOK)算法来说，位于不同磁道（柱面）的I/O请求与获取服务所需的等待时间是不同的。 对于靠近边缘的柱面，最坏情况的移动量为2N-1（N为柱面数）；对于靠近中部的柱面，最坏情况为N-1。平均情况分别约为N和N/2。 返回 循环扫描算法（Circular SCAN / LOOK） 是为了消除边缘柱面与中部柱面等待时间差异而进行的改进。 磁头只在单方向移动过程中才为途经的请求服务，一旦达到边缘，则立即快速移动至另一边缘，在此移动过程中并不处理访问请求，然后重新开始新一轮扫描。 循环扫描算法（CSCAN） 特点：消除了对两端磁道请求的不公平。 下磁道 移道数 65 12 67 2 98 31 122 24 124 2 183 59 14 169 37 23 总道数 322 平均 40.3 返回 N-STEP-SCAN调度算法 SSTF、SCAN及CSCAN存在的问题---磁臂粘着 在SSTF、SCAN及CSCAN几种调度算法中，可能出现磁臂停留在某处的情况，即反复请求某一磁道，从而垄断了整个磁盘设备，这种现象称为磁臂粘着。 N-STEP-SCAN调度算法 将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，而每一子队列按SCAN算法处理。 N=1 FCFS算法 N很大 SCAN算法 N取半长度 FSCAN算法 返回 本章作业 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磁盘调度算法响应请求的次序及磁头移动的总距离。 返回 在设备和处理机之间设置一个缓冲。设备与处理机交换数据时，先把交换的数据写入缓冲区，然后需要数据的设备/处理机再从缓冲区中取走数据。 特点：缓冲区数只有一个；设备与处理机对缓冲区的操作是串行的。 图示 外部设备 缓冲区 OS 用户进程 6.7.2单缓冲和双缓冲 1、单缓冲Single Buffer 一块数据的处理时间 工作区 缓冲区 用户进程 操作系统 传送 输入 I/O设备 T M C 返回 无缓冲区时，该时间为T+C 由于C和T可并行，M和C或M和T不能并行，因此处理一块数据时间：Max(C，T)+M 2、双缓冲Double Buffer、Buffer Swapping 增加一个缓冲区，两个缓冲区可以交替使用 若用户进程阵发性I/O的数据超过一个缓冲区而不足两个缓冲区，双缓冲使进程不会在I/O数据期间被阻塞。 在设备和处理机之间设置2个缓冲。设备与处理机交换数据时，先把交换的数据写入缓冲区，然后需要数据的设备/处理机再从缓冲区中取走数据。因缓冲区有2个，提高了设备与处理机并行操作的程度，只有当两个均为空时，需数据的进程才等待。 特点：缓冲区数有2个；