操作系统原理操作系统原理 (60).pdf

《操作系统原理操作系统原理 (60).pdf》由会员分享，可在线阅读，更多相关《操作系统原理操作系统原理 (60).pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 操作系统操作系统原理原理 Operating System PrincipleOperating System Principle 1111-2 2 磁盘调度磁盘调度 A Minimize seek time 最小寻道时间 Disk Scheduling 磁盘调度 B Seek time seek distance 寻道时间 寻道距离 C Disk Scheduling 磁盘调度 A B Several algorithms exist to schedule the servicing of disk I/O requests.Several algorithms exist to sch

2、edule the servicing of disk I/O requests.有几种磁盘有几种磁盘I/OI/O请求的服务调度算法请求的服务调度算法 We illustrate them with a request queue(0We illustrate them with a request queue(0-199).199).我们假设一个请求序列。我们假设一个请求序列。98,183,37,122,14,124,65,6798,183,37,122,14,124,65,67 Head pointer 53 Head pointer 53 磁头当前的位置在磁头当前的位置在5353。Dis

3、k Scheduling(Cont.)磁盘调度（续）queue=98,183,37,122,14,124,65,67 head starts at 53 0 14 37 53 65 67 98 122 124 183 199 Illustration shows total head movement of 640 cylinders.如下图所示，磁头总共移动了640个柱面的距离。FCFS 先来先服务 A A Selects the request with the minimum seek time from the current head position.选择从当前磁头位置所需 寻道时

4、间最短的请求。B B SSTF scheduling is a form of SJF scheduling;may cause starvation of some requests.SSTF是SJF调度的一种形式；有可能引起某些请求的饥饿。SSTF 最短寻道时间优先 SSTF(Cont.)queue=98,183,37,122,14,124,65,67 head starts at 53 0 14 37 53 65 67 98 122 124 183 199 磁头移动的总距离是208柱面。进程“饥饿”现象 对于SSTF算法 只要不断有新进程到达，且新进程所要访问的磁道与磁头当前所在磁道的距

5、离较近，则新进程一定优先满足，而某些老进程则会发生“饥饿”现象。如何防止 如何防止“饥饿”现象 SCAN算法 不仅考虑到欲访问的磁道与磁头当前位置间的距离，更优先考虑的是磁头当前的移动方向。算法所选择的访问对象应当是与磁头当前的移动方向一致且距离最近的。现象 A B The disk arm starts at one end of the disk,and moves toward the other end,The disk arm starts at one end of the disk,and moves toward the other end,servicing requests

6、 until it gets to the other end of the disk,where the head servicing requests until it gets to the other end of the disk,where the head movement is reversed and servicing continues.movement is reversed and servicing continues.磁头从磁盘的一端开始向另一端磁头从磁盘的一端开始向另一端移动，沿途响应访问请求，直到到达了磁盘的另一端，此时磁头反向移动并继移动，沿途响应访问请求，

7、直到到达了磁盘的另一端，此时磁头反向移动并继续响应服务请求。续响应服务请求。Sometimes called the elevator algorithm.Sometimes called the elevator algorithm.有时也称为有时也称为电梯算法电梯算法。SCAN 扫描算法 SCAN(Cont.)queue=98,183,37,122,14,124,65,67 head starts at 53,朝磁道号减小的方向移动 0 14 37 53 65 67 98 122 124 183 199 磁头移动的总距离是236柱面 C-SCAN A Provides a more uni

8、form wait time than SCAN.提供比扫描算法更均衡的等待时间。B The head moves from one end of the disk to the other.servicing requests as it goes.When it reaches the other end,however,it immediately returns to the beginning of the disk,without servicing any requests on the return trip.磁头从磁盘的一段向另一端移动，沿途响应请求。当它到了另一端，就立即回

9、到磁盘的开始处，在返回的途中不响应任何请求。C Treats the cylinders as a circular list that wraps around from the last cylinder to the first one.把所有柱面看成一个循环的序列，最后一个柱面接续第一个柱面。C-SCAN(Cont.)queue=98,183,37,122,14,124,65,67 head starts at 53，朝磁道号增加的方向移动 0 14 37 53 65 67 98 122 124 183 199 Version of SCAN Version of SCAN SCANS

10、CAN算法的一种形式。算法的一种形式。Arm only goes as far as the last request in each direction,then Arm only goes as far as the last request in each direction,then reverses direction immediately,without first going all the way to the reverses direction immediately,without first going all the way to the end of the di

11、sk.end of the disk.磁臂在每个方向上仅仅移动到最远的请求位置，然磁臂在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的一端后立即反向移动，而不需要移动到磁盘的一端 LOOK LOOK 0 14 37 53 65 67 98 122 124 183 199 Queue=98,183,37,122,14,124,65,67 head stars at 53，朝磁道号减小的方向移动 total head movement of 198 cylinders.A B Version of CVersion of C-SCAN SCAN C C-SCANSCAN

12、算法的一种形式。算法的一种形式。Arm only goes as far as the last request in each direction,then reverses Arm only goes as far as the last request in each direction,then reverses direction immediately,without first going all the way to the end of the disk.direction immediately,without first going all the way to the end of the disk.磁臂在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而磁臂在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而 不需要移动到磁盘的一端。不需要移动到磁盘的一端。C-LOOK C-LOOK(Cont.)queue=98,183,37,122,14,124,65,67 head starts at 53，朝磁道号增加的方向移动 0 14 37 53 65 67 98 122 124 183 199