《OS06设备管理6.7-6.8-2014-2015-2课件分解》由会员分享，可在线阅读，更多相关《OS06设备管理6.7-6.8-2014-2015-2课件分解（64页珍藏版）》请在金锄头文库上搜索。
1、操作系统OperatingSystems 第六章输入输出系统 6 7缓冲区管理 缓冲的引入单缓冲和双缓冲循环缓冲缓冲池 缓冲的引入 缓和CPU与I O设备间速度不匹配的矛盾凡在数据到达速率与其离去速率不同的地方 都可设置缓冲区 减少对CPU的中断频率 放宽对CPU中断响应时间的限制 必须在每收到一位数据时 便中断一次CPU并在下位到来之前要求CPU进行中断处理 以取走输入的数据 0 100 中断CPU的频率为9 6Kb s 每100 s中断一次CPU CPU必须在100 s内响应 否则数据会被冲掉 1 9 6 1024 0 1ms 可以每收8位数据中断一次CPU 但在第9位数据到来之间必须完成
2、中断处理 CPU每隔800 s中断一次 要求CPU必须在100 s时间内予以响应 0 900 800 缓冲的引入 可每收8位数据中断一次 允许CPU在下一个8位数据到来期间完成前8位数据的中断处理 提高CPU和I O设备之间的并行性提高系统的吞吐量和设备的利用率 发出中断 响应时间可为800 s 单缓冲 单缓冲 数据处理时间约为max C T M 双缓冲 缓冲对换 数据处理时间约为max M C T 保证块设备连续工作 一块数据的传输和处理时间为T max C T 如果C T 在将磁盘上的一块数据传送到缓冲区其间 计算机已完成将另一个缓冲区中的数据传送到用户区并对这块数据进行计算的工作 这种情
3、况下可保证块设备连续工作 C M T 进程不必要等待I O 如果C T 一块数据的传输和处理时间为max C T M C M 这种情况下进程不必要等待I O C M T 双机通信时缓冲区的设置 只能实现单向的数据传输 6 7 3环形缓冲区 用于装输入数据的空缓冲区 已装满数据的缓冲区 计算进程正在使用的现行工作缓冲区 指示计算进程下一个可用缓冲区 输入进程下次可用的空缓冲区R的指针 计算进程正在使用的缓冲区C的指针 2 环形缓冲区的使用 计算进程和输入进程利用下述过程来使用环形缓冲区 1 Getbuf过程当计算进程要使用缓冲区中数据时 调用Getbuf过程当输入进程要使用空缓冲区来装入数据时
4、调用Getbuf 2 Releasebuf过程当计算进程把缓冲区中的数据提取完毕时当输入进程把缓冲区装满时 当计算进程要使用缓冲区中数据时 可调用Getbuf过程 计算进程 1 C 计算进程从C提取数据 当计算进程把C缓冲区中的数据提取完毕时 便调用Releasebuf过程 将缓冲区C释放 计算进程 2 R 计算进程从C提取完毕 当输入进程要使用空缓冲区来装入数据时 调用Getbuf 输入进程 1 输入进程用R来装数据 当输入进程把缓冲区装满时 也应调用Releasebuf过程 输入进程 2 G 输入进程已装满数据 3 进程同步 输入进程和计算进程并行执行Nexti指针追上Nextg指针可用空
5、缓冲区已满 输入进程应阻塞计算进程调用Releasebuf过程将输入进程唤醒 Nextg G G G 3 进程同步 Nextg指针追上Nexti指针装有输入数据的缓冲区都被抽空计算进程应阻塞输入进程调用Releasebuf过程将计算进程唤醒 R R R 6 7 4缓冲池 BufferPool 专用缓冲的利用率不高仅适用于某特定的I O进程和计算进程消耗大量的内存空间缓冲池系统的公用资源 可供多个进程共享既能用于输入 也能用于输出缓冲池组成空 闲 缓冲区 装满输入数据的缓冲区 装满输出数据的缓冲区 缓冲队列 可将相同类型的缓冲区链成一个队列可形成以下三个队列 空缓冲队列emq 输入队列inq 输
6、出队列outq 四种工作缓冲区 用于收容输入数据的工作缓冲区hin 用于提取输入数据的工作缓冲区sin 用于收容输出数据的工作缓冲区hout 用于提取输出数据的工作缓冲区sout 收容输入 在输入进程需要输入数据时 调用Getbuf emq 过程从空缓冲队列emq的队首摘下一空缓冲区 把它作为收容输入工作缓冲区hin 把数据输入其中 装满后再调用Putbuf inq hin 过程将该缓冲区挂在输入队列inq上 L emq F inq hin 提取输入 当计算进程需要输入数据时 调用Getbuf inq 过程从输入队列inq的队首取得一个缓冲区 作为提取输入工作缓冲区 sin 计算进程从中提取数
7、据计算进程用完该数据后 再调用Putbuf emq sin 过程将该缓冲区挂到空缓冲队列emq上 L inq F emq sin 收容输出 当计算进程需要输出时 调用Getbuf emq 过程从空缓冲队列emq的队首取得一个空缓冲区 作为收容输出工作缓冲区hout 当其中装满输出数据后 调用Putbuf outq hout 过程 将该缓冲区挂在outq末尾 L emq F outq hout 提取输出 由输出进程调用Getbuf outq 过程从输出队列的队首取得一装满输出数据的缓冲区 作为提取输出工作缓冲区sout 在数据提取完后 再调用Putbuf emq sout 过程 将该缓冲区挂在空
8、缓冲队列末尾 L outq F emq sout 6 8磁盘存储器的性能和调度 6 8 1磁盘性能描述1 数据的组织和格式 磁盘扇区一个扇区称为一个盘块 或数据块 磁盘结构 每个盘面有一个读写磁头所有的读写磁头都固定在唯一的移动臂上同时移动在磁头位置下的所有磁道组成的圆柱体称柱面 磁盘 磁盘性能简述 2 磁盘的类型 固定头磁盘在每条磁道上都有一读 写磁头 所有的磁头都被装在一刚性磁臂中 这些磁头可访问所有各磁道 并进行并行读 写 这种结构的磁盘主要用于大容量磁盘上 2 移动头磁盘每一个盘面仅配有一个磁头 也被装入磁臂中 该磁头必须能移动以进行寻道 本节主要针对这类磁盘的I O进行讨论 3磁盘访
9、问时间 寻道时间移动磁头到指定磁道上所经历的时间 旋转延迟时间移动某扇区到磁头下所经历时间 传输时间从磁盘读或向磁盘写数据所经历时间 适当地集中数据 不要太零散 传输 将有利于提高传输效率 所读 写数据的多少无关 6 8 2早期的磁盘调度算法 1 先来先服务算法2 最短寻道时间优先算法 在访问磁盘的时间中 主要是寻道时间 因此 磁盘调度的目标就是使磁盘的平均寻道时间最少 先来先服务算法 根据进程请求访问磁盘的先后次序进行调度优点 简单 公平 不会出现请求长期得不到满足缺点 未优化 平均寻道时间长磁盘调度 555839189016015038184 0 38 39 55 58 90 100 15
10、0 160 184 18 先来先服务算法 平均寻道长度 55 3 146 184 112 38 10 150 70 160 72 90 21 18 19 39 3 58 45 55 移动距离 被访问的下一个磁道 100道开始 最短寻道时间优先算法SSTF 要求访问的磁道与当前磁头所在的磁道距离最近优点 使每次寻道时间最短缺点 不能保证平均寻道时间最短 可能导致距离远的进程总也得不到服务 0 38 39 55 58 90 100 150 160 184 18 磁盘调度 555839189016015038184 FCFS调度算法SSTF调度算法 进程 饥饿 现象 SSTF算法可能导致某个进程发生
11、 饥饿 现象 不断有新进程的请求到达 且其所要访问的磁道与磁头当前所在磁道的距离较近这种新进程的I O请求必然优先满足 可防止老进程出现 饥饿 现象对SSTF算法略加修改后所形成的SCAN算法 6 8 3基于扫描的磁盘调度算法 1 扫描 SCAN 算法 电梯调度算法 2 循环扫描 CSCAN 算法3 NStepSCan和FSCAN调度算法 在访问磁盘的时间中 主要是寻道时间 因此 磁盘调度的目标就是使磁盘的平均寻道时间最少 扫描 SCAN 算法 不仅考虑欲访问的磁道与当前磁道的距离 更优先考虑的是磁头当前的移动方向又称为 电梯调度算法 缺点 刚移过的磁道的等待时间长 0255075100125
12、150175200 150 160 184 90 58 55 38 39 18 扫描 SCAN 算法 电梯调度算法 555839189016015038184 SCAN调度算法SSTF调度算法 循环扫描 算法CSCAN 规定磁头单向移动减少刚移过的磁道的等待时间 循环扫描 算法CSCAN 555839189016015038184 0255075100125150175200 150 160 184 90 58 55 38 39 18 SCAN调度算法CSCAN调度算法 N步SCAN算法 磁臂粘着 在SSTF SCAN及CSCAN几种调度算法中 都可能出现磁臂停留在某处不动的情况N步SCAN算
13、法将磁盘请求队列分成若干个长度为N的子队列 磁盘调度将按FCFS算法依次处理这些子队列 每处理一个队列时又是按SCAN算法 对一个队列处理完后 再处理其他队列当N值很大时 N步扫描性能接近于SCAN性能 N 1 N步扫描性能便退化为FCFS FSCAN算法 FSCAN算法是N步SCAN算法的简化只将磁盘请求队列分成两个子队列 一是由当前所有请求I O的进程形成的队列由磁盘调度按SCAN算法进行处理 另一个等待处理的请求队列在扫描期间 新出现的所有请求I O的进程加入此队列 1 下列哪一条不是磁盘设备的特点 A传输速率较高 以数据块为传输单位B一段时间内只允许一个用户 进程 访问CI O控制方式
14、常采用DMA方式D可以寻址 随机地读 写任意数据块2 目前广泛流行既可用于输入又可用于输出的 该缓冲中设置了多个可供若干进程共享的缓冲区 A单缓冲区 双缓冲区 环形缓冲区 缓冲池 B C 设从磁盘将一块数据传送到缓冲区所用时间为80 s 将缓冲区中数据传送到用户区所用时间为40 s CPU处理数据所用时间为30 s 则处理该数据 采用单缓冲传送某磁盘数据 系统所用总时间为 A 120 s B 110 s C 150 s D 70 s A max C T M 80 s 40 s C 30 s 假定把磁盘上一个数据块中的信息输入到一双缓冲区的时间T为100 s 将缓冲区中的数据传送到用户区的时间M
15、为50 s 而CPU对这一数据进行计算的时间C为50 s 这样 系统对每一块数据的处理时间为 A50 s B100 s C150 s D200 s E250 s max M C T B 100 s 50 s C 50 s 5 假定磁盘有200个柱面 编号0 199 当前存取臂的位置在143号柱面上 并刚刚完成了125号柱面的服务请求 如果请求队列的先后顺序是 86 147 91 177 94 150 102 175 130 试问 为完成上述请求 下列算法存取臂移动的总量是多少 并算出存取臂移动的顺序 1 先来先服务算法FCFS 2 最短查找时间优先算法SSTF 3 扫描算法SCAN 电梯调度
16、4 循环扫描算法 CSCAN 5 比较上述算法 答 1 先来先服务算法FCFS请求队列 86 147 91 177 94 150 102 175 130依次为 143 86 147 91 177 94 150 102 175 130 143 86 147 86 147 91 177 91 177 94 150 94 150 102 175 102 175 130 565 2 最短查找时间优先算法SSTF为 请求队列 86 147 91 177 94 150 102 175 130依次为143 147 150 130 102 94 91 86 175 177移动的总量 162 8095110125140155170185200 143 150 175 130 102 94 86 91 86 147 91 177 94 150 102 175 130 147 177 移动的总量 125 电梯调度 8095110125140155170185200 143 150 175 130 102 94 86 91 86 147 91 177 94 150 102 175 130 147 177 CS
